Algorithm problem | | prime Numbers determine the cryptography algorithms you can think of several? (on)

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”. This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Hello everyone, I am wearing Wolf skin 🐏. Today I will introduce several deterministic algorithms for primality test, which is suitable for judging whether a given integer N is prime. Note that 0, 1 and other numbers that are not prime or composite are not considered here, so remember to use the if judgment yourself.

Trial Division + optimization

The most straightforward method is to iterate over all numbers from 2 to n-1 and check if they are divisible by n, returning False if found.

def is_prime(n) :
    for x in range(2, n):
        if n % x == 0:
            return False
    return True
Copy the code

Optimization of 1

If n is composite, there must be two divisible numbers p1p_1p1 and p2p_2p2, and p1≤n≤p2p_1 \le \ SQRT {n} \le p_2P1 ≤n≤p2. N \ SQRT {n}n is the axis of symmetry. We don’t have to try all the numbers less than n-1 at once, until x == SQRT (n).

from math importIsqrt // Python version >=3.8

def is_prime(n) :
    for x in range(2, isqrt(n) + 1) :if n % x == 0:
            return False
    return True
Copy the code

Optimization of 2

If n is divisible by an even number, then it must be divisible by 2, right? Therefore, we can skip all even numbers except 2.

from math importIsqrt // Python version >=3.8

def is_prime(n) :
    if n == 2:
        return True
    elif n % 2= =0:
        return False
        
    for x in range(3, isqrt(n) + 1.2) :if n % x == 0:
            return False
    return True
Copy the code

Optimization of 3

All primes except 2 and 3 must be expressed as 6k+1 or 6k+5, where k is a positive integer.

(A prime number can always be expressed in this form, but a number that can be expressed in this form is not necessarily prime.)

argument

6kCan it be6Divisible, not prime;
6k+2 和 6k+4Can it be2Divisible, not prime;
6k+3Can it be3Divisible, not prime;

So that leaves 6k plus 1 and 6k plus 5 as possible prime numbers.

Note: 6k+5 can also be written as 6k-1 because 5≡−1(mod6)5 \ equiv-1 \pmod 65≡−1(mod6).

For numbers that might be prime, we use trial division, which Narrows the range even further by looking for factors in numbers that can be expressed as 6k+1 or 6k+5.

Why is that?

All composite numbers can be decomposed into prime numbers, so n only needs to be evaluated against numbers that are likely to be prime (i.e., 6k+1 or 6k+5).

def is_prime3(n) :
    if n == 2 or n == 3:
        return True
    # A number that cannot be expressed as 6k+1 or 6k+5 must not be prime
    if n % 6! =1 and n % 6! =5:
        return False
    # Further judgment
    for x in range(5.int(sqrt(n)) + 1.6) :if n % x == 0 or n % (x + 2) = =0:
            return False
    return True
Copy the code

Wilson’s Theorem

One of the four theorems of number theory:

If and only if NNN is prime:
$(n – 1)! \equiv -1 \pmod n$

Simply put, if n is prime, then the remainder of n minus 1 factorial plus 1 over n is 0.

argument

{1, 2,… , n – 1}, {1, 2, \ dots, n – 1 \} {1, 2,… Every element aaa in n−1} has a reciprocal of modular NNN A ∗∈{1,2… , n – 1} a ^ * \ in \ {1, 2, \ dots, n – 1 \} a ∗ ∈ {1, 2,… ,n−1}, that is aa∗≡1(modn) AA ^* \equiv 1 \pmod Naa ∗≡1(MOdn). (This statement will not be argued here…)

If a=a∗a =a ^*a=a∗,

\begin{aligned} a^2 &\equiv 1 \pmod n \\ a^2 – 1 &\equiv 0 \\ (a – 1)(a + 1) &\equiv 0\\ \\ a &\in \{1,\,n-1\} \end{aligned}

Only the modulo reciprocal of 1 and n−1n-1n−1 is itself, {2,3… , n – 2} \ {2, 3, \ dots, n – 2 \} {2, 3,… Each number in,n−2} has a unique modular reciprocal. Pairwise, so we have some pairs of modules NNN is equal to 111.

\begin{aligned} (n-1)! &\equiv -1 \pmod n \\ 1 \times [2 \times 3 \times \dots \times (n – 2)] \times (n-1) &\equiv -1 \\ 1 \times 1 \times (n – 1) &\equiv -1 \\ n – 1 &\equiv -1 \\ n &\equiv 0 \end{aligned}

Proof done. Code up.

from math import factorial

def is_prime(n) :
    return (factorial(n - 1) + 1) % n == 0
Copy the code

AKS (Agrawal — Kayal — Saxena Primality Test)

NNN is prime if and only if:

NNN aliquot n (x + 1) – (xn + 1) (x + 1) ^ n – (x ^ n + 1) n (x + 1) – (xn + 1) of all the coefficient of expansion.

argument

Using binomial theorem, expand the original expression:

\begin{aligned} (x + 1)^n – (x^n + 1) &= \sum_{r=0}^{n}{\binom{n}{r} x^r} – (x^n + 1) \\ &= \sum_{r=1}^{n-1}{\binom{n}{r} x^r} \end{aligned}

You can see that xn plus 1x to the n plus 1xn plus 1 gets rid of x plus 1 n times x plus 1 to the n times x plus 1. So the theorem above can also be expressed like this:

NNN is prime if and only if:

NNN is divisible by (nr),r=1,2… , n – 2, n – 1 \ binom {n} {r}, r = 1, 2, \ dots, n – 2, n – 1 (rn), r = 1, 2,… , n – 2 n – 1.

Let N=(nr)N = \binom{N}{r}N=(rn),

\begin{aligned} N &= \frac{n! }{(n-r)! \,r! } \\ n! &= N(n-r)! \,r! \end{aligned}

Obviously NNN divisible by n factorial. n! n! , then NNN is divisible by N(N − R)! R!!! N(n-r)! \,r! N (N – r)! r! . If a number is divisible by the product of several numbers, it must be divisible by at least one of them. Because PPP is not divisible

P – (r)! (p-r)! P – (r)! , because (p−k)
r! r! r! , because k

So it must be divisible by NNN.

This theorem holds for prime numbers.

When NNN is composite,

Let CCC be a factor of NNN, n= CDN = CDN = CD. C,d∈{1,2… , n – 1} c, d \ in \ {1, 2, \ dots, n – 1 \} c, d ∈ {1, 2,… , n – 1}.

\begin{aligned} \binom{n}{c} &= \frac{n! }{(n-c)! \,c! } \\ &= \frac{n(n-1)\dots(n-c+1)\cancel{(n-c)! }}{\cancel{(n-c)! }\,c! } \\ &= \frac{n(n-1)\dots(n-c+1)}{c! } \end{aligned}

If the upper expression is divisible by NNN, then there must be a positive integer KKK such that (nc)=kn\binom{n}{c} =kn (cn)=kn.

\begin{aligned} \frac{\cancel{n}(n-1)\dots(n-c+1)}{c! } &= k\cancel{n} \\ k &= \frac{(n-1)(n-2)\dots(n-c+1)}{c! } \end{aligned}

Let’s see if KKK is an integer.

\begin{aligned} (n-1)(n-2)\dots(n-c+1) &\equiv (p-1)\times(p-2)\times\dots\times1 \pmod p \\ &\equiv (p-1)! \end{aligned}

According to Wilson’s theorem,

(p-1)! \equiv -1 \pmod p

KKK can’t be a whole number. This theorem does not hold for composite numbers.

Argumentation completed, the code is as follows:

from math importComb // Python version >=3.8

def is_prime(n) :
    for r in range(1, n):  // (n-1) + 1 = n
        ifcomb(n, r) % n ! =0:
            return False
    return True
Copy the code

To optimize the

$\binom{n}{k}=\binom{n}{n-k}$

(n1) = (nn) – 1 \ binom {n} {1} = \ binom {n} {n – 1} (1, n) = n (n – 1), (n2) = (nn) – 2 \ binom {n} {2} = \ binom {n} {n – 2} (2 n) = 2 n (n -) and so on. Therefore, the range can be reduced by half.

from math importComb // Python version >=3.8

def is_prime(n) :
    for r in range(1, n // 2 + 1) :ifcomb(n, r) % n ! =0:
            return False
    return True
Copy the code

Give it a thumbs up, or that’s what your next interview will be about.

In the next article, WE will introduce several more efficient probabilistic test algorithms. That’s it. Bye.

Algorithm problem | | prime Numbers determine the cryptography algorithms you can think of several? (on)

Trial Division + optimization

Optimization of 1

Optimization of 2

Optimization of 3

Wilson’s Theorem

AKS (Agrawal — Kayal — Saxena Primality Test)

To optimize the

Related Posts

A trick to make API parallel calls silky smooth

How do I encounter a write bottleneck in monitoring Log4j2 asynchronous logs

Liu Qi: The database market presents a trend of diversification. 20% of traditional databases will be replaced in the next two years