(40G) & gs: Square Root Modulo a Prime
09-24-2015, 07:53 PM (This post was last modified: 06-15-2017 01:53 PM by Gene.)
Post: #1
 Gerald H Senior Member Posts: 1,430 Joined: May 2014
(40G) & gs: Square Root Modulo a Prime
Edit: Programme simplified.

For input

{ n , p }

n an integer, n < p, p prime the programme SQRTMODP finds the integer square root of n modulo p or returns zero if there is no square root. This is a stand alone programme.

eg For input

{ 7777777 , 98765432167 }

the programme finds

41653959691. The answer is returned in Ans & stored in Q.

SQRTMODP

Code:
 Ans►L1: MODSTO(Ans(2))►M: L1(1) MOD M►C: √Ans►Q: IF FRAC(Ans) THEN IF POWMOD(C,(M-1)/2)+1 THEN M-1►D: 0►E: DO D/2►D: E+1►E: UNTIL D MOD 2 END: 1►G: DO 1+G►G: UNTIL POWMOD(Ans,(M-1)/2)-1 END: POWMOD(G,D)►L: POWMOD(C,(D-1)/2)►Q: MULTMOD(MULTMOD(Ans,Ans),XQ(C))►O: MULTMOD(XQ(C),XQ(Q))►Q: WHILE O ≠ 1 REPEAT 0►P: DO P+1►P: UNTIL POWMOD(O,2^P)==1 END: POWMOD(L,2^(E-P-1))►X: MULTMOD(Ans,Ans)►L: P►E: MULTMOD(XQ(X),XQ(Q))►Q: MULTMOD(XQ(L),XQ(O))►O: END: ELSE 0►Q: END: END: ABS(Q):
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)