Tonelli-Shanks algorithm: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: add lib header) |
(add nim version) |
||
Line 1,503: | Line 1,503: | ||
root1 = 32102985369940620849741983987300038903725266634508 |
root1 = 32102985369940620849741983987300038903725266634508 |
||
root2 = 67897014630059379150258016012699961096274733366069 |
root2 = 67897014630059379150258016012699961096274733366069 |
||
</pre> |
|||
=={{header|Nim}}== |
|||
Based algorithm pseudo-code, referencing python 3. |
|||
<lang Nim> |
|||
proc pow*[T:SomeInteger](x,n,p:T):T = |
|||
var t = x mod p |
|||
var e = n |
|||
result = 1 |
|||
while e > 0: |
|||
if (e and 1) == 1: |
|||
result = result * t mod p |
|||
t = t * t mod p |
|||
e = e shr 1 |
|||
proc legendre*[T:SomeInteger](a,p:T):T = pow(a, (p-1) shr 1, p) |
|||
proc tonelliShanks*[T:SomeInteger](n,p:T): T = |
|||
# Check that n is indeed a square |
|||
if legendre(n,p) != 1: |
|||
raise newException(ArithmeticError, "Not a square") |
|||
# factor out power of 2 from p-1 |
|||
var q = p - 1 |
|||
var s = 0 |
|||
while (q and 1) == 0: |
|||
s += 1 |
|||
q = q shr 1 |
|||
if s == 1: |
|||
return pow(n, (p+1) shr 2, p) |
|||
# Select a non-square z such as (z | p) = -1 |
|||
var z = 2 |
|||
while legendre(z,p) != p - 1: |
|||
z += 1 |
|||
var |
|||
c = pow(z, q, p) |
|||
t = pow(n, q, p) |
|||
m = s |
|||
result = pow(n, (q+1) shr 1, p) |
|||
while t != 1: |
|||
var |
|||
i = 1 |
|||
z = t * t mod p |
|||
while z != 1 and i < m-1: |
|||
i += 1 |
|||
z = z * z mod p |
|||
var b = pow(c, 1 shl (m-i-1), p) |
|||
c = b * b mod p |
|||
t = t * c mod p |
|||
m = i |
|||
result = result * b mod p |
|||
when isMainModule: |
|||
proc run(n,p:SomeInteger) = |
|||
try: |
|||
let r = tonelliShanks(n,p) |
|||
echo r, " ", p-r |
|||
except ArithmeticError: |
|||
echo getCurrentExceptionMsg() |
|||
run(10,13) |
|||
run(56,101) |
|||
run(1030, 10009) |
|||
run(1032, 10009) |
|||
run(44402, 100049) |
|||
run(665820697, 1000000009) |
|||
</lang> |
|||
output: |
|||
<pre> |
|||
7 6 |
|||
37 64 |
|||
1632 8377 |
|||
Not a square |
|||
30468 69581 |
|||
378633312 621366697 |
|||
</pre> |
</pre> |
||