(38G) Square Root Modulo a Prime

[Gerald H]

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

Code:

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: