Rosetta Code

Tonelli-Shanks algorithm: Difference between revisions

Page Discussion

Tonelli-Shanks algorithm (view source)

Revision as of 13:58, 25 October 2016

120 bytes removed ,  7 years ago
m
→‎{{header|Sidef}}: code simplifications
m (→‎{{header|Sidef}}: code simplifications)
Line 542:
legendre(n, p) == 1 || die "not a square (mod p)"
var q = p-1
var s = 0valuation(q, 2)
s == 1 ? return (powmod(n, (p + 1) >> 2, p)) : (q >>= s)▼
while (q.is_even) {
var c = powmod(2 if..^ p -> first {|z| (legendre(z, p) == -1)}, {q, p)▼
q >>= 1
s += 1
}
if (s == 1) {
▲ return powmod(n, (p + 1) >> 2, p)
}
var c
for z in (2 ..^ p) {
▲ if (legendre(z, p) == -1) {
c = powmod(z, q, p)
break
}
}
var r = powmod(n, (q + 1) >> 1, p)
var t = powmod(n, q, p)
Trizen
2,756

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/266646"