Miller–Rabin primality test: Difference between revisions

Content added Content deleted
(→‎{{header|Python}}: Corrected a notable error)
(Undo revision 182035 by Qwr (talk) code is questionable, see discussion)
Line 2,134: Line 2,134:
if pow(a, d, n) == 1:
if pow(a, d, n) == 1:
return False
return False
for i in range(1, s):
for i in range(s):
if pow(a, 2**i * d, n) == n-1:
if pow(a, 2**i * d, n) == n-1:
return False
return False
Line 2,153: Line 2,153:
if pow(a, d, n) == 1:
if pow(a, d, n) == 1:
return False
return False
for i in range(1, s):
for i in range(s):
if pow(a, 2**i * d, n) == n-1:
if pow(a, 2**i * d, n) == n-1:
return False
return False
Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"