Tonelli-Shanks algorithm: Difference between revisions
added REXX which works for the smaller numbers
(Added Java) |
Walterpachl (talk | contribs) (added REXX which works for the smaller numbers) |
||
Line 1,499:
n = 41660815127637347468140745042827704103445750172002 p = 100000000000000000000000000000000000000000000000577
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}}==
| |||