Cipolla's algorithm: Difference between revisions
Added 11l
Alextretyak (talk | contribs) (Added 11l) |
|||
Line 75:
* [[Tonelli-Shanks algorithm]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<lang 11l>F convertToBase(n, b)
I (n < 2)
R [n]
V temp = n
V ans = [Int]()
L (temp != 0)
ans = [temp % b] [+] ans
temp I/= b
R ans
F cipolla(=n, p)
n %= p
I (n == 0 | n == 1)
R [n, (p - n) % p]
V phi = p - 1
I (pow(BigInt(n), phi I/ 2, p) != 1)
R [Int]()
I (p % 4 == 3)
V ans = Int(pow(BigInt(n), (p + 1) I/ 4, p))
R [ans, (p - ans) % p]
V aa = 0
L(i) 1 .< p
V temp = pow(BigInt((i * i - n) % p), phi I/ 2, p)
I (temp == phi)
aa = i
L.break
V exponent = convertToBase((p + 1) I/ 2, 2)
F cipollaMult(ab, cd, w, p)
V (a, b) = ab
V (c, d) = cd
R ((a * c + b * d * w) % p, (a * d + b * c) % p)
V x1 = (aa, 1)
V x2 = cipollaMult(x1, x1, aa * aa - n, p)
L(i) 1 .< exponent.len
I (exponent[i] == 0)
x2 = cipollaMult(x2, x1, aa * aa - n, p)
x1 = cipollaMult(x1, x1, aa * aa - n, p)
E
x1 = cipollaMult(x1, x2, aa * aa - n, p)
x2 = cipollaMult(x2, x2, aa * aa - n, p)
R [x1[0], (p - x1[0]) % p]
print(‘Roots of 2 mod 7: ’cipolla(2, 7))
print(‘Roots of 8218 mod 10007: ’cipolla(8218, 10007))
print(‘Roots of 56 mod 101: ’cipolla(56, 101))
print(‘Roots of 1 mod 11: ’cipolla(1, 11))
print(‘Roots of 8219 mod 10007: ’cipolla(8219, 10007))</lang>
{{out}}
<pre>
Roots of 2 mod 7: [4, 3]
Roots of 8218 mod 10007: [9872, 135]
Roots of 56 mod 101: [37, 64]
Roots of 1 mod 11: [1, 10]
Roots of 8219 mod 10007: []
</pre>
=={{header|C}}==
| |||