Детерминированная реализация теста Первичности Миллера-Рабина в предположении, что N & lt; 9,080,191
import sys
import random
def miller_rabin_pass(a, n):
d = n - 1
s = 0
while d % 2 == 0:
d >>= 1
s += 1
a_to_power = pow(a, d, n)
if a_to_power == 1:
return True
for i in xrange(s-1):
if a_to_power == n - 1:
return True
a_to_power = (a_to_power * a_to_power) % n
return a_to_power == n - 1
def miller_rabin(n):
for a in [2, 3, 37, 73]:
if not miller_rabin_pass(a, n):
return False
return True
n = int(sys.argv[1])
primes = [2]
for p in range(3,n,2):
if miller_rabin(p):
primes.append(p)
print len(primes)
Согласно статье в Википедии ( http://en.wikipedia.org/wiki/Miller-Rabin_primality_test ) тестирование N & lt; 9,080,191 для a = 2,3,37 и 73 достаточно, чтобы решить, является ли N составным или нет.
И я адаптировал исходный код из вероятностной реализации оригинального теста Миллера-Рабина, найденного здесь: http://en.literateprograms.org/Miller-Rabin_primality_test_ (Python)