Python:实现miller rabin米勒-拉宾素性检验算法(附完整源码)

import random
from .binary_exp_mod import bin_exp_mod
def is_prime_big(n, prec=1000):
  
    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_big(i)))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41