(notes by Roberto Bigoni)
As we know from our early arithmetic studies, prime numbers are the natural numbers greater than 1, which aren't the product of two other numbers both less than the number itself.
This definition implies that 1 is not a prime number, and that the only even prime number is 2.
Prime numbers are infinite, that is, the set of prime numbers does not have maximum. A proof by contradiction of this theorem is due to Euclid.
If prime numbers were not infinite, then would exist the maximum prime number M, and it would be possible to calculate the number P = 2·3·5·7·11·13·…·M, equal to the product of all the prime numbers.
Let us consider the natural number S immediately following P: S=P+1.
It is impossible that S is a prime number, because it is greater than the maximum M.
If we were to divide S for any prime number, we would have a quotient given by the product of the remaining prime numbers and the remainder 1, then S is not divisible by any of the prime numbers, so it must be prime.
We get two contradictory statements and we must therefore conclude that the primes are infinite.
Natural numbers greater than 1 that are not prime are said composite numbers.
The easiest method to get the set P_{n} of the primes ≤ n (n>13) is the
Sieve of Eratosthenes
(sieve: a tool used for separating coarse from fine parts of loose matter):
To determine if an odd number n is prime, that is, to check its primality, we can build the set P_{n} and check whether n ∈ P_{n}.
This procedure, however, is unnecessarily costly since a possible divisor of n can not exceed its square root. Therefore, we should
But even with this improvement, if n is very large, the sieve becomes impractical because it may require too much computation time. Direct primality tests, that is such that do not require the previous calculation of a huge number of primes, were searched and are searched even today.
One of the first direct primality test is due to P. de Fermat.
Given the odd number n, the Fermat's method is based on the research of two numbers h and k such that
If n is a perfect square, the solution is immediate because in this case n is equal to the product of its square root for itself and, of course, n is not prime.
If n is not too big it is convenient to apply the Sieve of Eratosthenes.
Otherwise we can always express hk as a difference of two squares:
then, with
we get
The problem is solved if we find a number a such that a^{2}-n is a perfect square.
For this purpose we proceed by trials:
Given a e b, we have
If a-b = 1, n is prime; otherwise the two factors a-b and a-b (that is h e k) are different and less than n, then n is composite.
Fermat's method requires that we repeatedly check whether a natural number n is a perfect square. It is not possible to directly determine this property of n. However, in many cases we can eliminate quickly enough this possibility, noting that the quadratic residues modulo m, for a fixed number m, are quite a few.
For example, the quadratic residues modulo 8 for the squares of the first 100 natural numbers, using WolframAlpha, are
Even without a formal proof, it can safely be conjectured that by calculating the remainder of the division of a natural number by 8, if the remainder is equal to 0, 1, 4, the number is not a perfect square.
A further example is provided by the set of the quadratic residues modulo 9.
Even in this case we can safely conjecture that by calculating the remainder of the division of a number by 9, if the remainder is equal to 0, 1, 4, 7, the number is not a perfect square.
But to pass a test of this kind is necessary but not sufficient condition to conclude that n is a perfect square. It is a useful control to narrow down the search for possible perfect squares, but not conclusive. To successfully identify a perfect square we inevitably need a more expensive procedure, like the following bisection algorithm.
We consider the sequence of the natural numbers q_{i} that, starting from 4, is formed by numbers such that each of them is the square of the previous number.
Example.
Let n = 40401
We have 40401≡1 (mod 8) and 40401≡0 (mod 9), so n passes the two proposed preliminary tests. Now we apply the bisection algorithm:
A natural number n, greater than 1, either is prime or is composite. If n is composite, by the Fermat method, n can be expressed as the product of two natural numbers h and k less than n. In their turn, each of the numbers h and k either is prime or is composite. If they are both prime, their product is the decomposition of n into prime factors product (or factorization of n). Otherwise, we can apply the Fermat's method to the composite factors and repeat the process until we have only prime factors. If at the end of the procedure a factor appears several times, the product of the identical factors is replaced by a power and the product of these powers (with exponent ≥ 1) is the unique decomposition of n into product of powers of prime factors.
The Fermat's method works satisfactorily for not too big numbers or, even for big numbers, if the two factors h and k are both next to √n. Otherwise, it may take an impractical computing time even on the fastest systems, particulary when the number n that we try to factorize is a big prime number, for which the sought factors h and k are n itself and 1, then very distant from √n.
Alternatively we could use the Sieve of Eratosthenes.
However, if n is very big, even √n is big and is also huge the number of the elements of Q_{n} whose calculation can require an impratical time, especially if n is prime, because it is necessary to perform the the division of n by each q_{i} before coming to the conclusion that n is prime.
So before we try factoring large numbers, we do well to ensure with more efficient methods that n is not a prime number. In general these methods are probabilistic, that is such as not to produce the mathematical certainty of the primality of n, but to guarantee it with such a high degree of probability to be fully reliable in many operating situations.
Historically, the first of these methods is even due to Fermat and is based on a theorem enunciated by Fermat himself, but subsequently demonstrated by L. Euler, known as Fermat's little theorem.
If p is a prime number, then, for any integer n,
where n^{p} ≡ n(mod p) means that the divisions by p of n^{p} and n give equal remainders. We say that n^{p} and n are congruent modulo p.
For example: given n=10 and p=3, we have:
A demonstration of the theorem may be obtained by induction.
First of all we observe that, if p is prime,
In fact, if we expand the power of the binomial, we get
where
The theorem holds for n=0 and n=1:
If the theorem holds for n
from the equation (1) we get
Then, by induction, the theorem holds for all n.
In particular, if n has no common divisors with p, that is it is coprime with respect to p, we have
The theorem states a necessary, but not sufficient condition, that is any prime p verify the stated congruence, but this congruence may be verified also by some composite number c. These numbers are said Fermat pseudoprimes with respect to n. In particular, the pseudoprimes c with respect to any n coprime with respect to c are said Carmichael numbers.
So, if a number q does not verify the theorem with respect to a coprime n, we can say that q is composite, but if it verifies the congruence, we can not say that it is prime, but only that it is a probable prime.
If we try with many random values of n with always positive results, we can operationally assume q as a prime number.
Examples.
1. Let q=41.
The probability that q is not a prime number is quite small. Indeed 41 is prime, as we can check with the Sieve of Eratosthenes.
2. Let q=91.
3. Let q=561.
If we apply the Fermat's factorization method, we get 561 = 17 · 33. So 561 is composite.
Now we try the Fermat primality test:
The Fermat primality test, even with several trials, can fail, that is it can lead us to consider as prime a number that instead is composite. We can reduce this risk and estimate the probability of getting the correct answer, noting that a prime number q>2 must be odd and then q-1 must be even. Moreover, every even number can be decomposed into the product of an odd number d and a power s of 2.
By Fermat's theorem, if q is prime, and n is coprime with respect to q, , we have
If this root is ≡ 1(mod q), then the next will be ≡ ±1 (mod q), and so on.
If all the roots are ≡ 1 (mod q), so even n^{d}≡1 (mod q), q passes the test and is probably prime.
If the first root not ≡ 1 (mod q) is = -1 (mod q), q passes the test and is probably prime.
Otherwise q is composite.
In conclusion, to determine whether q is probably prime:
The probability that a composite number q passes the test is at most ¼. Therefore, by repeating the test with other values of n, the probability that q can pass them all decreases exponentially.
Examples.
1. As we have seen the number q=561, is a Fermat pseudoprime, therefore, while being composite, it passes the Fermat test.
We decompose 560 into the product between an odd number and a power of 2: 560=35·2^{4}
With n=2, we have 2^{35}=34359738368; 2^{35}≡ 263 (mod 561)
35·2^{3}=280;
2^{280}=1942668892225729070919461906823518906642406839052139521251812409738904285205208498176
2^{280}≡1 (mod 561)
35·2^{2}=140;
2^{140}=1393796574908163946345982392040522594123776
2^{140}≡67 (mod 561)
So q is composite.
2. Let q=601
With n=2, we have
2^{600}=414951556888099295851240786369116115101244623224243689999565732969065281141290814639970704894710379428
8197886611300789182395151075411775307886874834113963687061181803401509523685376
2^{600}≡1 (mod 601): the number passes the Fermat test.
600=75*2^{3}
With n=2 we have
2^{75}=37778931862957161709568; 2^{75}≡ 1 (mod 601): 601 is a probable prime.
3. Let q=401
With n=2, we have
2^{400}=2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493376
2^{400}≡1 (mod 401): 401 passes the Fermat test.
400=25·2^{4}
With n=2 we have
2^{25}=33554432; 2^{75}≡356 (mod 401)
2^{200}=1606938044258990275541962092341162602522202993782792835301376; 2^{200}≡ 1 (mod 401);
2^{100}=1267650600228229401496703205376; 2^{100}≡ -1 (mod 401): 401 is a probable prime.
The applications of this page are implemented in JS and, while enhanced by the BigInt library of Leemon Baird, they are inevitably too slow to handle very big numbers. If we have to decompose in very large numbers, we can try to use WolframAlpha.
It should however be noted that, even using the most advanced software and specially designed hardware, the factorization of a very big number may require unworkable computational time and this fact is the basis of the most efficicient encryption methods, such as RSA.
last revision 26/06/2016