(42S) Quadratic Equation Solution Modulo a Prime - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: General Software Library (/forum-13.html) +--- Thread: (42S) Quadratic Equation Solution Modulo a Prime (/thread-1732.html) (42S) Quadratic Equation Solution Modulo a Prime - Gerald H - 06-28-2014 02:58 PM 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 RE: HP 42S Quadratic Equation Solution Modulo a Prime - Gerald H - 06-28-2014 03:38 PM Edited at 17:37 Vienna time, previously stack entry for INVM was wrong.