Example of how to use Python to detect prime numbers

This article mainly introduces the method of Python prime number detection. It analyzes the related skills of Python prime number detection with examples. Friends in need can refer to it. The details are as follows:

## Factor detection:

Detection factor, time complexity O(n^(1/2))

def is_prime(n):
  if n < 2:
    return False
  for i in xrange(2, int(n**0.5+1)):
    if n%i == 0:
      return False
  return True

Fermat’s Little Theorem:

If n is a prime number and a is any positive integer less than n, then the nth power of a is congruent with a modulo n

Implementation method:

Choose a base (for example, 2 ), for a large integer p, if 2^(p-1) and 1 are not congruent modulo p, then p must not be a prime number; otherwise, p is likely to be a prime number

2**(n-1)% n is not an easy number to calculate

Rule of modular operation:

(a^b) % p = ((a % p)^b) % p
(a * b) % p = (a % p * b % p) % p

Calculate X^N(% P)

Yes

If N is an even number, then X^ N = (X*X)^[N/2];
If N is an odd number, then X^N = X*X^(N-1) = X * (X*X)^[N/2] ;

def xn_mod_p(x, n, p):
  if n == 0:
    return 1
  res = xn_mod_p((x*x)%p, n>>1, p)
  if n&1 != 0:
    res = (res*x)%p
  return res

It can also be summarized as the following algorithm. The two functions are the same

def xn_mod_p2(x, n, p):
  res = 1
  n_bin = bin(n)[2:]
  for i in range(0, len(n_bin)):
    res = res**2 % p
    if n_bin[i] == '1':
      res = res * x % p
  return res

With the fast processing of modular exponentiation operation, Fermat test can be realized

Fermat test When a negative conclusion is given, it is accurate, but the positive conclusion may be wrong. It is very efficient for large integers, and the misjudgment rate decreases as the integer increases

def fermat_test_prime(n):
  if n == 1:
    return False
  if n == 2:
    return True
  res = xn_mod_p(2, n-1, n)
  return res == 1

MILLER-RABIN test

Miller-Rabin test is a widely used one at present

Quadratic detection theorem: If p is a prime number, and 0Fermat’s Little Theorem: a^(p-1) ≡ 1(mod p)
This is Miller-Rabin primality test method. Continuously extract the factor 2 in the index n-1, and express n-1 as d*2^r (where d is an odd number). Then what we need to calculate becomes the remainder of a divided by n to the d*2^r power. Therefore, a^(d * 2^(r-1)) is either equal to 1 or equal to n-1. If a^(d * 2^(r-1)) is equal to 1, the theorem continues to apply to a^(d * 2^(r-2)), and the square root is continued in this way until a^ is satisfied for a certain i (d * 2^i) mod n = n-1 or the 2 in the last exponent is used up to get a^d mod n=1 or n-1. In this way, Fermat's little theorem is strengthened into the following form:

Extract factor 2 as much as possible, and express n-1 as d*2^r. If n is a prime number, then or a^d mod n=1, Or there is a certain i such that a^(d*2^i) mod n=n-1 (0Theorem: If n is a prime number and a is a positive integer less than n, then n pairs a-based Miller test, and the result is true.

Miller test is performed k times , the error probability of treating composite numbers as prime numbers will not exceed 4^(-k) at most

def miller_rabin_witness(a, p):
  if p == 1:
    return False
  if p == 2:
    return True
  #p-1 = u*2^t 求解 u, t
  n = p - 1
  t = int(math.floor(math.log(n, 2)))
  u = 1
  while t > 0:
    u = n / 2**t
    if n % 2**t == 0 and u % 2 == 1:
      break
    t = t - 1
  b1 = b2 = xn_mod_p2(a, u, p)
  for i in range(1, t + 1):
    b2 = b1**2 % p
    if b2 == 1 and b1 != 1 and b1 != (p - 1):
      return False
    b1 = b2
  if b1 != 1:
    return False
  return True
def prime_test_miller_rabin(p, k):
  while k > 0:
    a = randint(1, p - 1)
    if not miller_rabin_witness(a, p):
      return False
    k = k - 1
  return True

The above is the detailed content of Example of how to use Python to detect prime numbers. For more information, please follow other related articles on the PHP Chinese website!