(40G) & gs: Square Root Modulo a Prime

[Gerald H]

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):