Primality Test

A primality test is a mathematical procedure for determining whether a given number is a prime number (i.e. it has no divisor other than by 1 or itself).

To determine if a number is prime, it must pass a primality test which confirms its status as a prime number.

Different test algorithms can be used to perform this verification.

There exist several primeness tests to know if a number is a prime number, the oldest is the Sieve of Eratosthenes, and the most common are Miller–Rabin and Lucas-Lehmer tests.

Eratosthenes' sieve is an old and efficient algorithm to find all prime numbers up to a certain number N. It goes through all numbers between 2 and root of N, and eliminates their multiples, the remaining numbers are numbers first.

For numbers less than 10^10, the tests are deterministic, with a verification of dividing potentials.

For numbers less than 10^16, dCode uses the Rabin-Miller test then the Lucas pseudo-primality test, the result is guaranteed.

For higher numbers, the tests are identical, but the result is no longer mathematically certain, however the false positive rate is extremely low (less than 10^-10).

A deterministic primality test provides a certain answer about the primality of a number, i.e. it guarantees whether the number is prime or not. In contrast, a probabilistic test provides a probable answer, with a controlled margin of error, which means it can tell whether a number is probably prime or probably composite.

The very definition of a prime number requires that it have exactly two distinct divisors: 1 and itself. In the case of 1, it does not satisfy this condition, because it has only one divisor.

However, it is mainly a mathematical convention that avoids many problems in mathematical definitions and theorems (where one would have to exclude 1 or treat it as a special case). Another advantage is that the prime factor decomposition is unique 6 = 2*3 and not 1*2*3 or 1*1*1*2*3.

The deterministic algorithm tries all or almost all numbers (it avoids even numbers and multiples of 3). Here is a pseudo code applicable for prime numbers not too large: // pseudo-code
function isPrime(n) {
if n ≤ 1 return FALSE
else if n ≤ 3 return TRUE
else if (n mod 2 = 0) or (n mod 3 = 0) return FALSE
i = 5
while (i*i ≤ n) {
if (n mod i = 0) or (n mod (i + 2) = 0) return FALSE
i = i + 6
}
return TRUE

This function checks if a given number n is prime or not using trial division method, which involves dividing n by all integers from 2 up to the square root of n. If no divisors are found within that range, the number is prime. The optimization in this pseudo-code avoids checking multiples of 2 and 3, to speed up the process.

Quantum computers could potentially revolutionize primality testing by using algorithms specific to quantum mechanics.

Some quantum algorithms, such as Shor's algorithm, could factorize large numbers quickly, questioning the security of some current cryptography methods based on the difficulty of factorization.

Twin prime numbers are two consecutive prime numbers with a difference of 2.

Mersenne primes are prime numbers of the form $ 2^n - 1 $.

The Lucas-Lehmer primality test is very effective for testing Mersenne numbers, thus the largest known prime numbers are all Mersenne numbers.

A primality test only allows you to determine whether a number is prime or not.

Prime factorization is a separate process and the methods used often do not allow us to know the divisors.

NB: If the number is prime, then its factorization is itself.