In the field of information security, some large prime numbers are often needed. For example, the famous RSA algorithm must rely on two large prime numbers. Fortunately, there are plenty of primes in natural numbers (it’s easy to prove there are infinitely many) and the density is not so low that it’s not that hard to find one, but it’s harder to find one that works in RSA.

Try in addition to the violence

What would you do if you had to find a prime number? I remember that just after I learned the basic grammar of C language in college, there was an after-class problem to determine whether a number is prime. People with basic programming ability must be able to write the following code:

boolean checkPrime(int n) {
    for (int i = 2; i*i <= n; i++) {
        if (n%i == 0) {
            return false; }}return true;
}
Copy the code

The easiest way to determine prime numbers is by trial division, which is the code above. It works from 2 to the square root of n, to see if n is divisible by something, and if it is, then n is not prime, and vice versa. This is a really simple, crude and correct method, the only problem is that it’s too slow to determine the time complexity of a number is order n. If you were to use this method to determine whether a number with hundreds of digits is prime or not, it would take n years with the most modern computers.

Screening method

Of course, there is a faster batch algorithm for prime numbers, which is called The Estrian filter. It only takes O(n log log n) time to find all primes up to n.

Here’s how it works: set up an array of markers, start with all the multiples of 2 marked, then go back and see that 3 is not marked, that 3 must be prime, then mark off all the multiples of 3 in the array marked, then see that 4 is marked and skip to 5… , until all numbers are marked, the remaining unmarked numbers are prime numbers, as shown in the figure above:

int[] signs = new int[n+1];
void eratosthenes(int n) {
    for (int i = 2; i <= n; i++) {
        if (signs[i] == 0) {
            for (int j = i * i; j <= n; j += i) {
                signs[j] = 1; }}}}Copy the code

The Ehrlich screening method, while seemingly faster, has its own problems. First of all, he can only batch, and the judgment of a single n also needs to screen out all the prime numbers less than n. Second, it relies on storage space to store tags. So it still can’t be used to determine super-large prime numbers.

Is there a faster way to find a prime number? Since the middle Ages, many mathematicians have been working to find the formula for prime numbers. For example, Euler discovered in 1772 that f(n)=n2+n+ 41F (n)=n ^2 +n+ 41F (n)=n2+n+41 that f(n) values were all prime numbers when n was less than 41. Although mathematicians discovered formulas that could generate larger prime numbers one after another, the number generated by these formulas was still very limited. By gauss’s time, it was basically confirmed that the simple prime number formula does not exist, so Gauss thought that the determination of prime is a very difficult problem.

Fermat’s Little theorem

However, things always turn up. Back in 1636, fermat, a famous mathematician, wrote this formula in a letter.

If p is a prime number and a is not a multiple of P, then a^(p-1) ≡ 1(mod p)

It turns out that a is not a multiple of P and that’s not a requirement. This theorem states that as long as P is prime, (a(p−1))modp(a^(p-1))mod P (a(P −1))modp is identical to 1. This is known as Fermat’s Little theorem. You’re probably already wondering if you can use this theorem to determine prime numbers, and indeed Fermat’s little theorem is almost true the other way around, if a number p makes a^(p-1) ≡ 1(mod p), p has a high probability of being prime, and notice it’s almost true here.

public class PrimeNumCheck {
    public static boolean check(long a, long p) {
        long res = fastMod(a, p-1, p);
        return res == 1;
    }

    public static long fastMod(long x, long n, long m) {
        if (n == 1) {
            return x % m;
        }
        long tmp = fastMod(x, n>>1, m);
        if (n % 2= =0) {
            return (tmp * tmp) % m;
        } else {
            return(tmp * tmp * x) % m; }}public static void main(String[] args) {
        System.out.println(check(2.7)); }}Copy the code

Using the Java code above, you can quickly determine whether a number is prime with probability (the result is not 100% accurate), depending on the selection of a in the code above. It uses a fast power algorithm, which can reduce the time complexity of modulo n of a number to O(logn). It seems that we can reduce the decision time complexity of prime numbers from O(n) to O(logn), which is a qualitative leap from almost uncomputable to computable, which paves the way for the application of large prime numbers.

But don’t worry, it still has minor flaws. I just said that fermat’s little theorem is almost true in reverse, and I keep saying almost. Because some and number n can also make a (n – 1) ≡ 1 (modn) a ^ (n – 1) ≡ 1 (mod n) (n – 1) ≡ 1 a (modn) was set up, These make composite numbers a(n−1)≡1(modn) A ^(n-1) ≡1(modn) A (n−1)≡1(modn) known as a-based pseudo-prime numbers, for example, the first few pseudo-prime numbers based on 2 were 341, 561, 645… . In fact, for a 512 bit number, there are fewer than 1/10^20 pseudo-primes based on 2, and less than 1/10^41 pseudo-primes based on 1024 bits. What are the odds? For example, you’re less likely to find a random 512-digit pseudo-prime number based on two than you are to win five million. So you’re picking a random prime number, and fermat’s Theorem based on two is good enough.

Of course, if you want to pursue higher accuracy, you can still optimize, after all, the pseudo-prime number based on 2 is not necessarily based on the pseudo-prime number of other A, so we can change several different A to further improve the accuracy of the above code. But history tells us there are always surprises. Some composite numbers that fermat’s theorem holds for any a are called Carmichael numbers. The first Carmichael numbers are 561 1105 1729… The Carmichael number is another story.

summary

Probabilistic solutions to Fermat’s Little Theorem give us a new way to solve problems, like using Bloom’s filter. They are not 100% accurate, but they can lead to more efficient solutions with controllable accuracy. The computer world can not only trade space for time, but also accuracy for time.

Fermat’s theorem, such a magical mathematical theorem, I feel that this seems to be god in the creation of a small egg about the number, and I also believe that there are many small eggs, maybe one day we can find god hidden in the PI joke!!

The resources

  • Wikipedia prime number test
  • Wikipedia Sieve of Eratosthenes
  • Wikipedia Carmichael count
  • Chapter 31 in introduction to algorithms. Testing prime numbers