miller rabin Algorithm
The Miller-Rabin algorithm is a probabilistic primality test used to determine whether a given number is a prime or not. It was independently developed by Gary L. Miller in 1976 and Michael O. Rabin in 1980. The algorithm is based on the mathematical property that if a number n is prime, then for any random a such that 1 < a < n, either a^(n-1) is congruent to 1 mod n or there exists an integer r such that 0 <= r < n-1 and a^(2^r * (n-1)) is congruent to -1 mod n. The Miller-Rabin algorithm iteratively checks this property for randomly chosen values of a, increasing the probability of the number being prime with each successful iteration.
The Miller-Rabin algorithm works by first representing the given number n-1 as 2^k * m, where m is an odd integer and k is a non-negative integer (i.e., the largest power of 2 that divides n-1). Then, a random value a is chosen between 1 and n-1. The algorithm computes a^m mod n and checks if the result is 1 or -1 (n-1). If either of these conditions hold, the algorithm moves on to the next iteration with a new random value of a. However, if the result is not 1 or -1, the algorithm proceeds by squaring the result and checking if it is congruent to -1 mod n. This step is repeated k times. If none of the computed values are congruent to -1 mod n, the number is declared composite (i.e., not prime). If at least one of the computed values is congruent to -1 mod n, the number is considered probably prime, and the algorithm moves on to the next iteration with a new random value of a. The more iterations performed, the higher the probability that the number is indeed prime.
import random
from .binary_exp_mod import bin_exp_mod
# This is a probabilistic check to test primality, useful for big numbers!
# if it's a prime, it will return true
# if it's not a prime, the chance of it returning true is at most 1/4**prec
def is_prime(n, prec=1000):
"""
>>> from .prime_check import prime_check
>>> all(is_prime(i) == prime_check(i) for i in range(1000))
True
"""
if n < 2:
return False
if n % 2 == 0:
return n == 2
# this means n is odd
d = n - 1
exp = 0
while d % 2 == 0:
d /= 2
exp += 1
# n - 1=d*(2**exp)
count = 0
while count < prec:
a = random.randint(2, n - 1)
b = bin_exp_mod(a, d, n)
if b != 1:
flag = True
for i in range(exp):
if b == n - 1:
flag = False
break
b = b * b
b %= n
if flag:
return False
count += 1
return True
if __name__ == "__main__":
n = abs(int(input("Enter bound : ").strip()))
print("Here's the list of primes:")
print(", ".join(str(i) for i in range(n + 1) if is_prime(i)))
