Simplicity Algorithm for O (log N)

Check for simplicity

To determine whether a given number N is simple, it is certainly enough to write a simple search cycle for divisors of the number N :

bool prime(long long n){ for(long long i=2;i<=sqrt(n);i++) if(n%i==0) return false; return true; } 

This function of checking the number for simplicity is quite effective - the asymptotics of its work is O (sqrt (N)) . However, sometimes in sports programming you need to be able to check the number for simplicity more quickly.
')
In some cases, when it is required to perform such a check for numbers from a certain range, it is advisable to use the Sieve of Eratosthenes algorithm.

In this article I will look at another way to perform single checks for simplicity - the Farm test .

Probabilistic algorithm for O (log N) with the Farm test

The mathematical justification for Fermat’s test is fairly well described here .

I will give its concrete implementation in C ++, and also show you how to deal with the overflow of the type long long during exponentiation.

Farm test

In order to check the number N for simplicity with a sufficiently good error probability, it is sufficient to check the random number A with the Fermat test 100 times:


It is also worth noting that the numbers A and N should be mutually simple. If this condition is not met, then the number N is obviously not simple.

 bool ferma(long long x){ if(x == 2) return true; srand(time(NULL)); for(int i=0;i<100;i++){ long long a = (rand() % (x - 2)) + 2; if (gcd(a, x) != 1) return false; if( pows(a, x-1, x) != 1) return false; } return true; } 

I note that this verification function uses the functions of finding the GCD, as well as the rapid exponentiation modulo.

Finding the GCD

Actually, in finding the NOD of the two numbers of problems the least. We use the Euclidean algorithm :

 long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b, a%b); } 

Fast exponentiation modulo

Rapid exponentiation (binary) is widely known. I will only note that when two long numbers are multiplied, a type overflow may occur even before we take the result modulo. Therefore, we use the function of binary multiplication of two numbers also modulo. Its meaning is very similar to the rapid exponentiation.

 long long mul(long long a, long long b, long long m){ if(b==1) return a; if(b%2==0){ long long t = mul(a, b/2, m); return (2 * t) % m; } return (mul(a, b-1, m) + a) % m; } long long pows(long long a, long long b, long long m){ if(b==0) return 1; if(b%2==0){ long long t = pows(a, b/2, m); return mul(t , t, m) % m; } return ( mul(pows(a, b-1, m) , a, m)) % m; } 

In the same way as in exponentiation, if the second factor is even, then we can divide it by 2, and proceed to the calculation of the product of numbers A and B / 2 . Otherwise, it is necessary to calculate the product of the numbers A and B - 1 .

Asymptotic solution

The resulting asymptotic test for simplicity is O (K * log N * log N) , where K is the number of Fermat test iterations, which usually equals 100. If you want to test the int number for simplicity, you can do without binary multiplication. Then the asymptotics of the test for simplicity will be equal to O (K * log N) .