Prime number algo... what's wrong?
amk at amk.ca
Sun Mar 23 00:55:39 CET 2003
On Sat, 22 Mar 2003 13:08:37 GMT,
L. B. <lorenzo at mysurname.net> wrote:
> Also are you aware of more sophisticated and efficient algos for prime
> testing implemented in Python?
Here's a straightforward implementation of the Rabin-Miller probabilistic
primality test. The Python cryptography toolkit contains a faster
implementation of it that's less readable. mathworld.wolfram.com has an
explanation of the Rabin-Miller test; textbooks on algorithms or number
theory may also discuss it.
(Has anyone implemented the polynomial-time primality test discovered a few
months back? Wonder how complicated it is...)
HAMLET: Angels and ministers of grace defend us!
-- _Hamlet_, I, iv
# Say that 1 and 2 are prime.
if n==1 or n==2:
# If even, it's obviously composite.
if (n % 2) == 0:
# Straightforward Rabin-Miller test...
# Compute r,s, such that N = s*2**r + 1.
n1 = n-1
r = 1
div = n1/(2**r)
if div*(2**r) != n1:
r += 1
r = r-1 ; s = n1/(2**r)
# Try a bunch of integers. If a**s == 1, or
# a**(s*2**j) == -1, for j in 0...r, the
# number is prime. (Trying more values of 'a'
# will decrease the risk that n isn't really prime.)
for a in range(2, min(10,n)):
t1 = pow(a,s,n)
if t1 == 1:
prime = 0
for j in range(0, r):
t2 = pow(a, s*(2**j), n)
if t2 == (n-1):
# Test small numbers
for i in range(1, 255, 2):
p = rm_test(i)
# Look for a 256-bit prime
i = 2**256+1
while not rm_test(i):
i += 2
print 'Prime:', i
More information about the Python-list