+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: HP-41C Software Library (/forum-11.html)
+--- Thread: Square Root Modulo An Odd Prime Programme (/thread-5771.html)
Square Root Modulo An Odd Prime Programme - Gerald H - 02-26-2016 08:10 AM
The programme MSQRT finds the modulo square root of a positive integer for a prime modulus.
eg For input
18081955
9999999929
where 9999999929 is the prime modulus (the largest prime < 10^10 & = 1 mod 4)
the programme returns
1058134345
to the stack.
The programme calls various sub-programmes.
SQM finds the square modulo the prime modulus:
Code:
1. ►LBL SQM
2. STO Y
3. 1E5
4. MOD
5. STO Z
6. –
7. ENTER
8. X^2
9. RCL 00
10. MOD
11. X<>Y
12. R↑
13. ST* T
14. *
15. RCL 01
16. MOD
17. RCL 00
18. X<>Y
19. +
20. LASTX
21. +
22. RCL 01
23. MOD
24. +
25. RCL 00
26. MOD
27. +
28. RCL 01
29. MOD
30. ENDM* multiplies two integers modulo the modulus:
Code:
1. ►LBL M*
2. STO 09
3. X<>Y
4. ENTER
5. ENTER
6. 1E5
7. MOD
8. STO 05
9. –
10. STO 06
11. RCL 09
12. ENTER
13. ENTER
14. 1E5
15. MOD
16. STO 07
17. –
18. STO 08
19. RCL 06
20. *
21. RCL 00
22. MOD
23. RCL 08
24. RCL 05
25. *
26. RCL 01
27. MOD
28. +
29. RCL 00
30. MOD
31. RCL 06
32. RCL 07
33. *
34. RCL 01
35. MOD
36. +
37. RCL 00
38. MOD
39. RCL 07
40. RCL 05
41. *
42. +
43. RCL 01
44. MOD
45. STO 09
46. ENDM↑ calculates the x stack level power of the y stack level modulo the modulus:
Code:
1. ►LBL M↑
2. STO 02
3. RDN
4. STO 03
5. SIGN
6. GTO 00
7. ►LBL 01
8. 2
9. MOD
10. X≠0?
11. GTO 02
12. LASTX
13. STO/ 02
14. RCL 03
15. XEQ SQM
16. STO 03
17. RCL 02
18. GTO 01
19. ►LBL 02
20. STO- 02
21. RCL 04
22. RCL 03
23. XEQ M*
24. ►LBL 00
25. STO 04
26. RCL 02
27. X≠0?
28. GTO 01
29. RDN
30. ENDKRON is a stand alone programme to find the Kronecker sign of stack level y with respect to stack level x, ie whether y is a quadratic residue of x:
Code:
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 05
24. GTO 03
25. ►LBL 05
26. ABS
27. STO 02
28. RCL 04
29. SIGN
30. STO* 03
31. ►LBL 03
32. RCL 04
33. X=0?
34. GTO 04
35. CLX
36. XEQ 01
37. RCL 04
38. 4
39. MOD
40. RCL 02
41. LASTX
42. MOD
43. *
44. 9
45. X=Y?
46. CHS
47. SIGN
48. STO* 03
49. RCL 04
50. ABS
51. ENTER
52. X<> 02
53. X<>Y
54. MOD
55. STO 04
56. GTO 03
57. ►LBL 01
58. RCL 04
59. 2
60. MOD
61. X≠0?
62. GTO 02
63. 2
64. STO/ 04
65. RCL Z
66. 1
67. +
68. CHS
69. GTO 01
70. ►LBL 02
71. RDN
72. X=0?
73. RTN
74. RCL 02
75. 8
76. MOD
77. 4
78. –
79. ABS
80. 1
81. X=Y?
82. CHS
83. STO* 03
84. RTN
85. ►LBL 04
86. RCL 02
87. 1
88. X≠Y?
89. 0
90. RCL 03
91. *
92. RTN
93. ►LBL 00
94. RDN
95. ABS
96. 1
97. X≠Y?
98. CLX
99. END& finally MSQRT:
Code:
1. ►LBL MSQRT
2. CHS
3. STO 00
4. CHS
5. STO 01
6. MOD
7. ENTER
8. SQRT
9. ENTER
10. FRC
11. X≠0?
12. GTO 07
13. RDN
14. RTN
15. ►LBL 07
16. RCL Z
17. STO 13
18. RCL 01
19. XEQ KRON
20. 1
21. +
22. X=0?
23. RTN
24. RCL 01
25. 4
26. MOD
27. 1
28. –
29. X=0?
30. GTO 08
31. RCL 13
32. RCL 01
33. 1
34. +
35. 4
36. /
37. XEQ M↑
38. RTN
39. ►LBL 08
40. STO 14
41. RCL 01
42. DSE X
43. ►LBL 00
44. STO Y
45. 2
46. MOD
47. X≠0?
48. GTO 01
49. RDN
50. LASTX
51. /
52. ISG 14
53. CLA
54. GTO 00
55. ►LBL 01
56. RDN
57. STO 15
58. 1
59. STO 16
60. ►LBL 02
61. 1
62. STO+ 16
63. RCL 16
64. RCL 01
65. XEQ KRON
66. X>0?
67. GTO 02
68. RCL 16
69. RCL 15
70. XEQ M↑
71. STO 17
72. RCL 14
73. STO 16
74. RCL 13
75. –1
76. RCL 15
77. +
78. 2
79. /
80. XEQ M↑
81. STO 18
82. RCL 13
83. XEQ M*
84. ENTER
85. X<> 18
86. XEQ M*
87. ►LBL 04
88. STO 13
89. 1
90. X=Y?
91. GTO 05
92. STO 14
93. RDN
94. ►LBL 06
95. XEQ SQM
96. 1
97. X=Y?
98. GTO 03
99. STO+ 14
100. RDN
101. GTO 06
102. ►LBL 03
103. RCL 17
104. 2
105. RCL 16
106. RCL 14
107. -
108. 1
109. –
110. Y^X
111. XEQ M↑
112. XEQ SQM
113. STO 17
114. RCL 14
115. STO 16
116. RCL 18
117. RCL 04
118. XEQ M*
119. STO 18
120. RCL 13
121. RCL 17
122. XEQ M*
123. GTO 04
124. ►LBL 05
125. RCL 18
126. END