Tonelli-Shanks algorithm: Difference between revisions
Added 11l
m (→{{header|OCaml}}: reduce scope of q; ocamlformat) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 69:
* [[Cipolla's algorithm]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<lang 11l>F legendre(a, p)
R pow(a, (p - 1) I/ 2, p)
F tonelli(n, p)
assert(legendre(n, p) == 1, ‘not a square (mod p)’)
V q = p - 1
V s = 0
L q % 2 == 0
q I/= 2
s++
I s == 1
R pow(n, (p + 1) I/ 4, p)
V z = 2
L
I p - 1 == legendre(z, p)
L.break
z++
V c = pow(z, q, p)
V r = pow(n, (q + 1) I/ 2, p)
V t = pow(n, q, p)
V m = s
V t2 = BigInt(0)
L (t - 1) % p != 0
t2 = (t * t) % p
V i = 1
L(ii) 1 .< m
I (t2 - 1) % p == 0
i = ii
L.break
t2 = (t2 * t2) % p
V b = pow(c, Int64(1 << (m - i - 1)), p)
r = (r * b) % p
c = (b * b) % p
t = (t * c) % p
m = i
R r
V ttest = [(BigInt(10), BigInt(13)), (BigInt(56), BigInt(101)), (BigInt(1030), BigInt(10009)), (BigInt(44402), BigInt(100049)),
(BigInt(665820697), BigInt(1000000009)), (BigInt(881398088036), BigInt(1000000000039)),
(BigInt(‘41660815127637347468140745042827704103445750172002’), BigInt(10) ^ 50 + 577)]
L(n, p) ttest
V r = tonelli(n, p)
assert((r * r - n) % p == 0)
print(‘n = #. p = #.’.format(n, p))
print("\t roots : #. #.".format(r, p - r))</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
n = 665820697 p = 1000000009
roots : 378633312 621366697
n = 881398088036 p = 1000000000039
roots : 791399408049 208600591990
n = 41660815127637347468140745042827704103445750172002 p = 100000000000000000000000000000000000000000000000577
roots : 32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
Line 524 ⟶ 591:
Program normal end.
</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
| |||