Number theory part 1: Prime numbers and prime tests
A number is prime (also called prime) if and only if it has only two divisors — 1 and itself. It says that these two divisor numbers cannot be the same, so 1 is not prime. The study of prime numbers is in the realm of number theory, and you can see that many mathematicians will come up with primes that conform to certain properties and call them prime numbers. Almost the whole of number theory revolved around words like divisible and prime. Prime numbers are more important than anyone who writes code might think. Google BigPrime or big_prime and you’ll find a ton of code that uses prime constants. Usually nothing can write down some prime numbers for emergency use. I would pick some prime numbers that are easy to remember, such as 4567, 124567, 3214567, 23456789, 55566677, 1234567894987654321, 1111111111111111111111111 (23 ones). The first 10 digits of my cell phone number are prime numbers. The ASCII code for my web domain name (77 97 116 114 105 120 54 55 46 99 111 109) is also prime. Also, the eighth birthday of one of my MMS is a prime number. I take her birthday every time I need a BigPrime constant to write a Hash function or something, hoping she’ll bring me good luck. Once in a while I call her plain MM, and no one knows what that means, not even her. Prime numbers have a lot of amazing properties. I’ll write 5 below for you to enjoy.
Proof: if the largest prime number P exists, then we can construct a new number 2 * 3 * 5 * 7 *… * P + 1 (all prime numbers multiplied by 1). Obviously this number is not divisible by any prime (all prime divisible by it has a remainder of 1), which means we have found a larger prime.
2. The existence of an arbitrarily long sequence of consecutive numbers, in which all numbers are composite numbers (the interval between adjacent prime numbers is arbitrarily large) proves: when 0
3. All prime numbers greater than 2 can be uniquely expressed as the difference between two squares. Proof: any prime greater than 2 is odd. Let’s say this number is 2n plus 1. Since (n+1)^2=n^2+2n+1, (n+1)^2 and n^2 are the two squares we’re looking for. The following shows that this scheme is unique. If the prime number p can be expressed as a^2-b^2, then p=a^2-b^2=(a+b)(a-b). Since p is prime, it is only possible that a+b=p and a-b=1, which gives a unique solution to a and b.
4. When n is an integer greater than 2, if one of the numbers 2^n+1 and 2^n-1 is prime, the other must be composite. Proof: 2^n is not divisible by 3. If it’s divisible by 3, then 2 to the n minus 1 is divisible by 3; If you divide 2 by 3, then 2 to the n plus 1 is divisible by 3. Anyway, at least one of 2 to the n plus 1 and 2 to the n minus 1 is composite.
5. If p is prime and a is a positive integer less than p, then a^(p-1) mod p = 1. This proof is a little bit tricky. First we prove that if P is a prime number, then for any positive integer a, A, 2a, 3a… P minus 1, the remainder of a over p is just a permutation from 1 to p minus 1. For example, 5 is a prime number, and the remainder of 3, 6, 9, 12 divided by 5 is 3, 1, 4, 2, exactly the same numbers as 1 through 4. If this proves not true, then it means that there are two positive integers m and n less than P such that na and ma have the same remainder over p. If n is greater than m, p is divisible into a(n-m). But p is prime, so at least one of a and n-m has a factor p. This is obviously impossible, because a and N-m are both smaller than P. In terms of congruence, we prove that: (p-1)! ≡ A * 2a * 3a *… * (p-1)a (mod p) = (p-1)! ≡ (p – 1)! A to the p minus 1 mod p divide both sides by p minus 1 factorial. , and we get our final conclusion: 1 ≡ a^(p-1) (mod p)
Unfortunately, I didn’t prove this theorem in the first place. This was proved by Fermat, the great mathematician, and it’s called Fermat’s Little Theorem. Euler generalized this theorem and called it Euler theorem. There are too many Euler theorems in Euler lifetime. In order to distinguish it from other “Euler theorems”, some places are called Euler extension of Fermat’s Little theorem. The Euler theorem requires a function f(m), which expresses how many positive integers less than m are coprime with m (two numbers that have only a common divisor 1 are called coprime). For convenience, this function (called the Euler function) is usually denoted by the notation φ(m). Euler states that if a and m are mutually prime, then a^φ(m) ≡ 1 (mod m). It can be seen that φ(m) is equal to m-1 when m is prime (all positive integers less than m are mutually prime to m), so it is a generalization of Fermat’s little theorem. The proof of the theorem is almost the same as Fermat’s little theorem, except that the formula to be considered becomes the product of all numbers that are mutually prime to M: m_1 * m_2… M_ φ(m) ≡ (A * m_1)(A * m_2)… (a * m_φ(m)) (mod m). Why should I mention Euler’s theorem in passing? The Theorems are in The Hundred Greatest Theorems.
When it comes to Fermat’s little theorem, the history of mathematics is full of misconceptions. For a long time, it was thought that the inverse of Fermat’s little theorem was true, and someone had personally verified all the cases where a=2 and P <300. There is even a saying abroad that China proved such a theorem in the time of Confucius: if n goes exactly into 2^(n-1)-1, then N is prime. Later a British scholar did his research and found that it was because they had made a mistake in translating ancient Chinese texts. In 1819 someone found the first counterexample of the inverse of Fermat’s little theorem: although 2 to the power 340 divided by 341 is more than 1, 341=11*31. Later, people found that the numbers 561, 645, 1105 and so on all show that the converse of Fermat’s little theorem is not valid when a=2. Although such numbers are few, they cannot be ignored. Therefore, all compound n that divisible exactly into 2^(n-1)-1 is called a pseudoprime, which means that the prime number is false. N that does not satisfy 2^(n-1) mod n = 1 must not be prime; If it does, it’s probably prime. In this way, a method of prime judgment with higher efficiency than trial division appears: make a list of pseudo prime numbers and record all pseudo prime numbers in a certain range. Then all n numbers satisfying 2^(n-1) mod n = 1 and not in the list of pseudo prime numbers are prime numbers. This is faster because we can quickly compute 2^(n-1) mod n using dichotomy, which is made very easy with the help of a computer; In computer, binary search for ordered sequence, Hash table opening Hash, Trie tree construction and other methods can be used to make the search for pseudo-prime number table more efficient. One would naturally be concerned with the question: How many pseudo-prime numbers are there? In other words, if I only calculate 2^(n-1) mod n, and do not prepare a list of pseudo-prime numbers, what is the probability that the prime judgment will be wrong? It is valuable to study this question, after all, we are OIer, we can not memorize an array of thousands of constants with the exam. Statistics show that there are 50847534 primes in the first billion natural numbers, while there are 5597 composite numbers n satisfying 2^(n-1) mod n = 1. That works out to about 0.00011 chances of the algorithm getting it wrong. This probability is too high, if we want to avoid the work of building pseudo prime number table, we need to improve the algorithm of prime judgment.
The simplest way to think about it is, we just looked at the case where a is equal to 2. For a to the n minus 1 mod n, taking different a’s might give you different results. A composite number might pass the test at a=2, but the result at A =3 would rule out primes. Therefore, people extend the definition of pseudoprime, and say that a composite number n satisfying a^(n-1) mod n = 1 is called pseudoprime to base A. There are only 1,272 pseudo-prime numbers with bases 2 and 3 in the first billion natural numbers, less than a quarter of that number. This tells us that if we check both a=2 and a=3, the probability of error drops to 0.000025. It’s easy to imagine that the more A’s you choose to test, the more accurate the algorithm will be. The usual way to do this is to randomly select a number of positive integers smaller than the number to be tested as base A several times, and as soon as one of them fails the test, immediately throw that number into the world of turns. This is the Fermat prime test. The natural thing to think about is, if you take all the bases a that are less than n, can the probability of making an error go down to zero? Unexpectedly, there is such a composite number, it can pass all a tests (this statement is not accurate, please refer to my reply in the core floor). Carmichael was the first to discover such extreme pseudo-prime numbers, which he called Carmichael numbers. You’d think that would be a huge number. Fault. The first Carmichael number is surprisingly small, just a three-digit number, 561. There are 600 Carmichael numbers in the first billion natural numbers. The existence of Carmichael number shows that we need to continue to strengthen the algorithm of prime judgment.
The work of Miller and Rabin revolutionized Fermat prime testing by establishing the fabled Miller-Rabin prime testing algorithm. The new test is based on the following theorem: if p is prime, x is a positive integer less than p, and x^2 mod p =1, then either x=1 or x=p-1. This is obvious, because x squared mod p = 1 is the same thing as p goes into x squared minus 1, which is the same thing as p goes into x plus 1 times x minus 1. Since p is prime, it is only possible that x-1 is divisible by p (where x=1) or x+1 is divisible by P (where x=p-1). Let’s demonstrate how the above theorem can be applied to Fermat primality tests. It was stated that 341 can pass the Fermat test with base 2 because 2^340 mod 341=1. If 341 is really prime, then 2^170 mod 341 can only be 1 or 340; When we calculate that 2 to the 170 mod 341 does equal 1, we can go ahead and look at 2 to the 85 divided by 341. We find that 2^85 mod 341=32, which removes the prime-number crown from 341, revealing the real face behind the mask, and exposing the attempt to pretend to be a prime number and interact with my prime MM. That’s how the Miller-Rabin primitivity test works. Continuously extract the factor 2 of the exponent n-1 and express n-1 as d*2^r (where D is an odd number). So what we need to compute becomes the remainder of a to the d times 2 to the r divided by n. So a to the d times 2 to the r minus 1 is either 1 or n minus 1. If a^(d * 2^(r-1)) is equal to 1, the theorem continues to apply to a^(d * 2^(r-2)), and so on and so on, until for some I a^(d * 2^ I) mod n= n-1 or until the 2 in the exponent runs out of a^d mod n=1 or n-1. In this way, Fermat’s little theorem is strengthened into the following form: If n is a prime number, then either a^d mod n=1, or there is some I such that a^(d*2^ I) mod n=n-1 (0<= I
1 function pow( a, d, n:longint ):longint;
2 begin
3 if d=0 then exit(1)
4 else if d=1 then exit(a)
5 else if d and 1=0 then exit( pow( a*a mod n, d div 2, n) mod n)
6 else exit( (pow( a*a mod n, d div 2, n) * a) mod n);
7 end;
8
9 function IsPrime( a,n:longint ):boolean;
10 var
11 d,t:longint;
12 begin
13 if n=2 then exit(true);
14 if (n=1) or (n and 1=0) then exit(false);
15 d:=n-1;
16 while d and 1=0 do d:=d shr 1;
17 t:=pow( a, d, n );
18 while ( d<>n-1 ) and ( t<>1 ) and ( t<>n-1 ) do
19 begin
20 t:=(t * t)mod n;
21 d:=d shl 1;
22 end;
23 exit( (t=n-1) or (d and 1=1) );
24 end;
Copy the codeAt present, miller-Rabin algorithm is most widely used in prime judgment of large numbers. In general, the base is still chosen randomly, but when the number to be tested is not too large, there are some tricks to choosing the test base. For example, if the number being tested is less than 4, 759, 123, 141, then only three bases 2, 7, and 61 need to be tested. Of course, the more you test, the greater the range. If you test with the first seven prime numbers (2, 3, 5, 7, 11, 13 and 17) every time, all numbers up to 341 550 071 728 320 are correct. If 2, 3, 7, 61 and 24251 are chosen as bases, then the only strong pseudo-prime numbers in 10^16 are 46 856 248 255 981. Such conclusions make the Miller-Rabin algorithm very useful in OI. It is generally considered that the accuracy of miller-Rabin primality test is acceptable, and the error rate of the test algorithm is about 4^(-k) when selecting k bases randomly.
The Miller-Rabin algorithm is an RP algorithm. RP is a kind of time complexity, mainly for deterministic problems. One algorithm is the RP algorithm, which shows that it can be done in polynomial time and can make accurate judgments for cases where the answer is no, but at the same time it is possible to make a wrong judgment for a correct one (the probability of error is no more than 1/2). RP algorithm is based on randomization, so running the algorithm multiple times can reduce the error rate. Other prime testing algorithms are also probabilistic, such as Solovay-Strassen. Other prime testing algorithms require some auxiliary information in advance (such as the prime factor of n-1), or the number to be measured must satisfy some conditions (such as the number to be measured must be of the form 2^n-1). The AKS algorithm took the world by storm a few years ago. It was the first polynomial, deterministic, primality determination algorithm that required no other conditions. At that time, a paper was published, the title was called PRIMES is in P, and then the whole world went crazy, several MMS in our class also came to menstruate that day. The algorithm is based on the fact that n is a prime number if and only if (X-a)^n≡(x^n-a) (mod n). Notice that this x is a polynomial, and we have a polynomial on both sides. For example, when a=1, the statement is equivalent to the following conclusion: When n is prime, the n+1 row of Yang Hui’s triangle is divisible by n except for the 1 at both ends.