Tonelli-Shanks algorithm: Difference between revisions

Content added Content deleted
(→‎{{header|Haskell}}: added solution)
(Replaced deprecated "ArithmeticError" with "ValueError". Added some spaces to improve readability.)
Line 2,591: Line 2,591:
Based algorithm pseudo-code, referencing python 3.
Based algorithm pseudo-code, referencing python 3.


⚫
<lang Nim>proc pow*[T: SomeInteger](x, n, p: T): T =
<lang Nim>
⚫
proc pow*[T:SomeInteger](x,n,p:T):T =
var t = x mod p
var t = x mod p
var e = n
var e = n
Line 2,601: Line 2,600:
t = t * t mod p
t = t * t mod p
e = e shr 1
e = e shr 1

proc legendre*[T:SomeInteger](a,p:T):T = pow(a, (p-1) shr 1, p)
proc legendre*[T: SomeInteger](a, p: T): T = pow(a, (p-1) shr 1, p)

proc tonelliShanks*[T:SomeInteger](n,p:T): T =
proc tonelliShanks*[T: SomeInteger](n, p: T): T =
# Check that n is indeed a square
# Check that n is indeed a square.
if legendre(n,p) != 1:
if legendre(n, p) != 1:
raise newException(ArithmeticError, "Not a square")
raise newException(ValueError, "Not a square")

# factor out power of 2 from p-1
# Factor out power of 2 from p-1.
var q = p - 1
var q = p - 1
var s = 0
var s = 0
Line 2,615: Line 2,614:
s += 1
s += 1
q = q shr 1
q = q shr 1

if s == 1:
if s == 1:
return pow(n, (p+1) shr 2, p)
return pow(n, (p+1) shr 2, p)
# Select a non-square z such as (z | p) = -1
# Select a non-square z such as (z | p) = -1.
var z = 2
var z = 2
while legendre(z,p) != p - 1:
while legendre(z, p) != p - 1:
z += 1
z += 1

var
var
c = pow(z, q, p)
c = pow(z, q, p)
Line 2,636: Line 2,635:
i += 1
i += 1
z = z * z mod p
z = z * z mod p

var b = pow(c, 1 shl (m-i-1), p)
var b = pow(c, 1 shl (m-i-1), p)
c = b * b mod p
c = b * b mod p
Line 2,642: Line 2,641:
m = i
m = i
result = result * b mod p
result = result * b mod p

when isMainModule:
when isMainModule:
proc run(n,p:SomeInteger) =
proc run(n, p: SomeInteger) =
try:
try:
let r = tonelliShanks(n,p)
let r = tonelliShanks(n, p)
echo r, " ", p-r
echo r, " ", p-r
except ArithmeticError:
except ValueError:
echo getCurrentExceptionMsg()
echo getCurrentExceptionMsg()

run(10,13)
run(10, 13)
run(56,101)
run(56, 101)
run(1030, 10009)
run(1030, 10009)
run(1032, 10009)
run(1032, 10009)
run(44402, 100049)
run(44402, 100049)
run(665820697, 1000000009)
run(665820697, 1000000009)</lang>
</lang>


output:
output:
<pre>
<pre>7 6
7 6
37 64
37 64
1632 8377
1632 8377
Not a square
Not a square
30468 69581
30468 69581
378633312 621366697
378633312 621366697</pre>
</pre>


=={{header|Perl}}==
=={{header|Perl}}==
Retrieved from "https://rosettacode.org/wiki/Tonelli-Shanks_algorithm"