Tonelli-Shanks algorithm: Difference between revisions
Content added Content deleted
(Added Java) |
Walterpachl (talk | contribs) (added REXX which works for the smaller numbers) |
||
Line 1,499: | Line 1,499: | ||
n = 41660815127637347468140745042827704103445750172002 p = 100000000000000000000000000000000000000000000000577 |
n = 41660815127637347468140745042827704103445750172002 p = 100000000000000000000000000000000000000000000000577 |
||
roots : 32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069</pre> |
roots : 32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069</pre> |
||
=={{header|REXX}}== |
|||
{{trans|Python}} |
|||
The large numbers cannot reasonably be handled by the pow function shown here. |
|||
<lang rexx>Numeric Digits 1000000 |
|||
ttest ='[(10, 13), (56, 101), (1030, 10009), (44402, 100049)]' |
|||
Do While pos('(',ttest)>0 |
|||
Parse Var ttest '(' n ',' p ')' ttest |
|||
r = tonelli(n, p) |
|||
Say "n =" n "p =" p |
|||
Say " roots :" r (p - r) |
|||
End |
|||
Exit |
|||
legendre: Procedure |
|||
Parse Arg a, p |
|||
return pow(a, (p - 1) % 2, p) |
|||
tonelli: Procedure |
|||
Parse Arg n, p |
|||
q = p - 1 |
|||
s = 0 |
|||
Do while q // 2 == 0 |
|||
q = q % 2 |
|||
s += 1 |
|||
End |
|||
if s == 1 Then |
|||
return pow(n, (p + 1) % 4, p) |
|||
Do z=2 To p |
|||
if p - 1 == legendre(z, p) Then |
|||
Leave |
|||
End |
|||
c = pow(z, q, p) |
|||
r = pow(n, (q + 1) / 2, p) |
|||
t = pow(n, q, p) |
|||
m = s |
|||
t2 = 0 |
|||
Do while (t - 1) // p <> 0 |
|||
t2 = (t * t) // p |
|||
Do i=1 To m |
|||
if (t2 - 1) // p == 0 Then |
|||
Leave |
|||
t2 = (t2 * t2) // p |
|||
End |
|||
y=2**(m - i - 1) |
|||
b = pow(c, y, p) |
|||
If b=10008 Then Trace ?R |
|||
r = (r * b) // p |
|||
c = (b * b) // p |
|||
t = (t * c) // p |
|||
m = i |
|||
End |
|||
return r |
|||
pow: Procedure |
|||
Parse Arg x,y,z |
|||
If y>0 Then |
|||
p=x**y |
|||
Else p=x |
|||
If z>'' Then |
|||
p=p//z |
|||
Return p</lang> |
|||
{{out}} |
|||
<pre>n = 10 p = 13 |
|||
roots : 7 6 |
|||
n = 56 p = 101 |
|||
roots : 37 64 |
|||
n = 1030 p = 10009 |
|||
roots : 1632 8377 |
|||
n = 44402 p = 100049 |
|||
roots : 30468 69581</pre> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |