(38G) Square Root 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: (38G) Square Root Modulo a Prime (/thread-3448.html) (38G) Square Root Modulo a Prime - Gerald H - 03-21-2015 06:00 AM For input { n , p } n an integer, n < p, p prime the programme finds the integer square root of n modulo p or returns zero if there is no square root. eg For input { 7777777 , 98765432167 } the programme finds 57111472476. The answer is returned in Ans & stored in Q. The programme KRON can be found here http://www.hpmuseum.org/forum/thread-3438.html & the other sub-programmes here http://www.hpmuseum.org/forum/thread-3380.html Ans►L1: Ans(2)►M: L1(1) MOD M►C: √Ans MOD M►Q: IF FRAC(Ans) THEN L1: RUN KRON: IF Ans==1 THEN M-1►D: 0►E: WHILE NOT(D MOD 2) REPEAT D/2►D: E+1►E: END: 1►G: WHILE Ans≠-1 REPEAT 1+G►G: {Ans,M}: RUN KRON: END: G►A: D►N: RUN PMOD: Ans►L: C►A: (D-1)/2►N: RUN PMOD: Ans►Q: RUN SMOD: Ans►X: C►H: RUN MMOD: Ans►O: C►H: Q►X: RUN MMOD: Ans►Q: WHILE O≠1 REPEAT 0►P: WHILE Ans≠1 REPEAT P+1►P: O►A: 2^P►N: RUN PMOD: END: L►A: 2^(E-P-1)►N: RUN PMOD: Ans►H: RUN SMOD: Ans►L: P►E: Q►X: RUN MMOD: Ans►Q: L►X: O►H: RUN MMOD: Ans►O: END: ELSE 0►Q: END: END: Q: