(42S) Quadratic Equation Solution Modulo a Prime

[Gerald H]

QEMP returns the two roots of the quadratic equation

A2x2+A1x+A0=0

modulo a prime P.

Stack entry is

A0
A1
A2
P

And the two roots are returned in the X & Y registers, or zero is returned if there is no solution.

QEMP uses two sub-programmes, see below.

0. { 103-Byte Prgm }
1. LBL “QEMP”
2. STO “P”
3. R↓
4. STO “A2”
5. R↓
6. STO “A1”
7. R↓
8. STO “A0”
9. RCL “A1”
10. RCL* ST X
11. 4
12. RCL* “A0”
13. RCL* “A2”
14. –
15. STO “D”
16. RCL “P”
17. STO 01
18. +/-
19. STO 00
20. X<>Y
21. XEQ “M√”
22. X=0?
23. RTN
24. STO “E”
25. RCL- “A1”
26. 2
27. RCL* “A2”
28. XEQ “M/”
29. STO “R1”
30. RCL “E”
31. RCL+ “A1”
32. +/-
33. 2
34. RCL* “A2”
35. XEQ “M/”
36. RCL “R1”
37. END

M√ finds a square root of the X register modulo a prime P previously stored in reg 01 & -P in reg 00.

M√ uses four sub-programmes, see below.

0. { 203-Byte Prgm }
1. LBL “M√”
2. RCL 01
3. MOD
4. ENTER
5. SQRT
6. ENTER
7. FP
8. X≠0?
9. GTO 07
10. R↓
11. RTN
12. LBL 07
13. RCL ST Z
14. STO 06
15. RCL 01
16. XEQ “KRON”
17. 1
18. +
19. X=0?
20. RTN
21. RCL 01
22. 4
23. MOD
24. 1
25. –
26. X=0?
27. GTO 08
28. RCL 06
29. RCL 01
30. 1
31. +
32. 4
33. /
34. XEQ “M↑”
35. RTN
36. LBL 08
37. STO 07
38. RCL 01
39. DSE ST X
40. LBL 00
41. STO ST Y
42. 2
43. MOD
44. X≠0?
45. GTO 01
46. R↓
47. RCL/ ST L
48. ISG 07
49. CLA
50. GTO 00
51. LBL 01
52. R↓
53. STO 08
54. 1
55. STO 09
56. LBL 02
57. 1
58. STO+ 09
59. RCL 09
60. RCL 01
61. XEQ “KRON”
62. X>0?
63. GTO 02
64. RCL 09
65. RCL 08
66. XEQ “M↑”
67. STO 10
68. RCL 07
69. STO 09
70. RCL 06
71. –1
72. RCL+ 08
73. 2
74. /
75. XEQ “M↑”
76. STO 05
77. RCL 06
78. XEQ “M*”
79. ENTER
80. X<> 05
81. XEQ “M*”
82. LBL 04
83. STO 06
84. 1
85. X=Y?
86. GTO 05
87. STO 07
88. R↓
89. LBL 06
90. XEQ “SQM”
91. 1
92. X=Y?
93. GTO 03
94. STO+ 07
95. R↓
96. GTO 06
97. LBL 03
98. RCL 10
99. 2
100. RCL 09
101. RCL- 07
102. 1
103. –
104. Y^X
105. XEQ “M↑”
106. XEQ “SQM”
107. STO 10
108. RCL 07
109. STO 09
110. RCL 05
111. RCL 04
112. XEQ “M*”
113. STO 05
114. RCL 06
115. RCL 10
116. XEQ “M*”
117. GTO 04
118. LBL 05
119. RCL 05
120. END

M/ & M* return the results of division & multiplication modulo a prime P previously stored in reg 01 & -P in reg 00.

M/ uses one sub-programme, see below.

0. { 77-Byte Prgm }
1. LBL “M/”
2. X<>Y
3. STO 02
4. R↓
5. RCL 01
6. XEQ “INVM”
7. X=0?
8. RTN
9. RCL 02
10. LBL “M*”
11. RCL ST X
12. 1E6
13. MOD
14. X<>Y
15. RCL- ST Y
16. COMPLEX
17. X<>Y
18. 1E6
19. MOD
20. RCL ST Z
21. RCL- ST Y
22. RCL* ST Z
23. X<>Y
24. RCL* ST Z
25. COMPLEX
26. RCL 00
27. MOD
28. +
29. RCL 01
30. MOD
31. X<>Y
32. COMPLEX
33. RCL 00
34. MOD
35. X<>Y
36. RCL 01
37. MOD
38. +
39. RCL 00
40. MOD
41. +
42. RCL 01
43. MOD
44. END

M↑ returns register Y to the power of register X modulo a prime P previously stored in reg 01 & -P in reg 00.

M↑ uses two sub-programmes, see above & below.

0. { 60-Byte Prgm }
1. LBL “MOD↑”
2. STO 01
3. +/-
4. STO 00
5. R↓
6. LBL “M↑”
7. STO 02
8. R↓
9. STO 03
10. SIGN
11. GTO 00
12. LBL 01
13. 2
14. MOD
15. X≠0?
16. GTO 02
17. LASTX
18. STO/ 02
19. RCL 03
20. XEQ “SQM”
21. STO 03
22. RCL 02
23. GTO 01
24. LBL 02
25. STO- 02
26. RCL 04
27. RCL 03
28. XEQ “M*”
29. LBL 00
30. STO 04
31. RCL 02
32. X≠0?
33. GTO 01
34. R↓
35. END

SQM finds the square of register X modulo a prime P previously stored in reg 01 & -P in reg 00.

0. { 42-Byte Prgm }
1. LBL “SQM”
2. STO ST Y
3. 1E6
4. MOD
5. STO ST Z
6. –
7. ENTER
8. X^2
9. RCL 00
10. MOD
11. X<>Y
12. R↑
13. STO* ST T
14. *
15. RCL 01
16. MOD
17. RCL- ST L
18. RCL+ ST L
19. RCL 01
20. MOD
21. +
22. RCL 00
23. MOD
24. +
25. RCL 01
26. MOD
27. END

INVM finds the multiplicative inverse of register Y modulo a prime P in register X.

INVM uses one sub-programme, see below.

0. { 26-Byte Prgm }
1. LBL “INVM”
2. XEQ “BEZO”
3. RCL ST Z
4. DSE ST X
5. GTO 00
6. RCL 05
7. RCL 08
8. MOD
9. RTN
10. LBL 00
11. CLX
12. END

BEZO finds X, Y & Z for integer A & B in the equation

A*X+B*Y=Z

Where Z is the GCD of A & B.

0. { 75-Byte Prgm }
1. LBL “BEZO”
2. STO 08
3. 1
4. COMPLEX
5. X<>Y
6. STO 07
7. 0
8. COMPLEX
9. LBL 00
10. ENTER
11. COMPLEX
12. R↓
13. X=0?
14. GTO 01
15. RCL ST Z
16. X<>Y
17. /
18. COMPLEX
19. R↓
20. IP
21. RCL* ST Y
22. RCL- ST Z
23. +/-
24. GTO 00
25. LBL 01
26. RCL ST Z
27. COMPLEX
28. RCL ST Y
29. RCL ST Y
30. RCL* 08
31. –
32. RCL/ 07
33. STO 05
34. COMPLEX
35. RCL ST Y
36. SIGN
37. STO* 05
38. STO* ST Z
39. *
40. RCL 08
41. RCL 07
42. COMPLEX
43. END

Edit: Sorry, I forgot the prog Kron. Here it is:

KRON shows the quadratic character of stack Y with respect to stack level X, returning 1 if Y is a quadratic residue for X & -1 if not or 0 if the GCD of X & Y > 1.

0. { 131-Byte Prgm }
1. LBL “KRON”
2. X=0?
3. GTO 00
4. STO 04
5. X<>Y
6. STO 02
7. 2
8. MOD
9. X<>Y
10. LASTX
11. MOD
12. +
13. X=0?
14. RTN
15. SIGN
16. STO 03
17. CLX
18. XEQ 01
19. RCL 02
20. X<> 04
21. STO 02
22. X>=0?
23. GTO 03
24. ABS
25. STO 02
26. RCL 04
27. SIGN
28. STO* 03
29. LBL 03
30. RCL 04
31. X=0?
32. GTO 04
33. CLX
34. XEQ 01
35. RCL 04
36. 4
37. MOD
38. RCL 02
39. LASTX
40. MOD
41. *
42. 9
43. X=Y?
44. +/-
45. SIGN
46. STO* 03
47. RCL 04
48. ABS
49. ENTER
50. X<> 02
51. X<>Y
52. MOD
53. STO 04
54. GTO 03
55. LBL 01
56. RCL 04
57. 2
58. MOD
59. X≠0?
60. GTO 02
61. 2
62. STO/ 04
63. RCL ST Z
64. NOT
65. GTO 01
66. LBL 02
67. R↓
68. X=0?
69. RTN
70. RCL 02
71. 8
72. MOD
73. 4
74. –
75. ABS
76. 1
77. X=Y?
78. +/-
79. STO* 03
80. RTN
81. LBL 04
82. RCL 02
83. 1
84. X≠Y?
85. CLX
86. RCL* 03
87. RTN
88. LBL 00
89. R↓
90. ABS
91. 1
92. X≠Y?
93. CLX
94. END

[Gerald H]

Edited at 17:37 Vienna time, previously stack entry for INVM was wrong.