# HP Forums

Full Version: (38G) Square Root Modulo a Prime
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
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

& the other sub-programmes here

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:
Reference URL's
• HP Forums: https://www.hpmuseum.org/forum/index.php
• :