|
===Python: Probably correct answers===
This versions will give answers with a very small probability of being false. That probability being dependent onnumber _mrpt_num_trialsof andtrials the(automatically random numbers used for name <code>a</code> passedset to function try_composite8).
<lang python>import random
import random
_mrpt_num_trials = 5 # number of bases to test
def is_probable_primeis_Prime(n):
"""
Miller-Rabin primality test.
A return value of False means n is certainly not prime. A return value of
True means n is very likely a prime.
>>> is_probable_prime(1)
Traceback (most recent call last):
AssertionError
>>> is_probable_prime(2)
True
>>> is_probable_prime(3)
True
>>> is_probable_prime(4)
>>> is_probable_prime(5)
True
>>> is_probable_prime(123456789)
False
>>> primes_under_1000 = [i for i in range(2, 1000) if is_probable_prime(i)]
>>> len(primes_under_1000)
168
>>> primes_under_1000[-10:]
[937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
>>> is_probable_prime(6438080068035544392301298549614926991513861075340134\
3291807343952413826484237063006136971539473913409092293733259038472039\
7133335969549256322620979036686633213903952966175107096769180017646161\
851573147596390153)
True
>>> is_probable_prime(7438080068035544392301298549614926991513861075340134\
3291807343952413826484237063006136971539473913409092293733259038472039\
7133335969549256322620979036686633213903952966175107096769180017646161\
851573147596390153)
False
"""
assertif n >!= 2int(n):
# special case 2 return False
if n == 2:int(n)
#Miller-Rabin test for prime
if n==0 or n==1 or n==4 or n==6 or n==8 or n==9:
if n ==2 %or 2n==3 or n== 5 0or n==7: ▼ return True
# ensure n is odd
return False
# write n-1 as 2**s * d
# repeatedly try to divide n-1 by 2
s = 0
d = n-1
while Trued%2==0:
quotient, remainder = divmod(d, 2)>>=1
if remainder s+== 1:
break
s += 1
d = quotient
assert(2**s * d == n-1)
def try_compositetrial_composite(a): ▼ # test the base a to see whether it is a witness for the compositeness of n
if pow(a, d, n) == 1:
return False
if pow(a, 2**i * d, n) == n-1:
return False
return True # n is definitely composite
for i in range(_mrpt_num_trials8):#number of trials
a = random.randrange(2, n)
if try_compositetrial_composite(a):
return False
return True # no base tested showed n as composite</lang>
===Python: Proved correct up to large N===
|