Fermatscher primality test
The Fermat's prime test is a prime test based on Fermat's small theorem . It is used to distinguish prime numbers from composite numbers .
Fermatscher primality test
The Fermat's prime number test is based on Fermat's small theorem:
For every prime number and every coprime natural number , the following congruence is fulfilled:
- .
By reversing this condition, one can test for natural numbers whether they are composed. If for a basis that is too coprime it is not divisible by, then it can not be prime. For example, one can conclude that the number is a compound.
The Fermatsche primality test goes like this:
- Input :, the natural number to be tested, result: composite or no statement
- Choose a base with . Check whether and are coprime.
- If they are not coprime then the result is composite . Otherwise:
- If so, the result is a composite .
- Otherwise the result is not a statement
If the test is repeated several times with different bases, no statement can be interpreted as a presumably prime number .
Fermatsche pseudoprimes
However, there are natural numbers that are not prime numbers and for which it still holds for a relatively prime basis that is divisible by . Such numbers are called Fermatian pseudoprimes for the base . The Carmichael numbers are particularly stubborn Fermatian pseudoprimes . For this is for all to prime bases by divisible.
If you use Fermat's prime number test with the base , you can determine with a high degree of certainty whether a number is a prime number or not. The following table shows the result of the calculation for the numbers 3 to 29.
3 | 4th | 5 | 6th | 7th | 8th | 9 | 10 | 11 | 12 | 13 | 14th | 15th | 16 | 17th | 18th | 19th | 20th | 21st | 22nd | 23 | 24 | 25th | 26th | 27 | 28 | 29 | |
1 | 0 | 1 | 2 | 1 | 0 | 4th | 2 | 1 | 8th | 1 | 2 | 4th | 0 | 1 | 14th | 1 | 8th | 4th | 2 | 1 | 8th | 16 | 2 | 13 | 8th | 1 |
This table can to be continued and is always under each prime number is a 1 and below each composite number is a number other than 1. The 341 is namely the first Fermat pseudoprime respect to the base 2: 341 is a divisor of , but due not prime.
Until there are 303 prime numbers, but only 7 Fermatian pseudoprimes with respect to 2, namely 341, 561, 645, 1105, 1387, 1729 and 1905 (sequence A001567 in OEIS ). If you choose a different basis, you get similar results. It was proved by Paul Erdős that the pseudoprimes are infinitesimally few on each base compared to the prime numbers (for each base , the number of Fermat's pseudoprimes is smaller than divided by the number of prime numbers smaller than converges with increasing to zero).
Deterministic Uses and Alternatives
If you use base 2, then you are sure to get a correct result up to the number 340. If you test with several bases (for example 2, 3 and 5), the safe limit increases. For example, the test with bases 2 and 3 is correct up to 1104; when using bases 2, 3 and 5 the limit increases to 1728.
In practice other primality tests are preferred, e.g. B. the Miller-Selfridge-Rabin test , as they are more likely to rule out the case that a composite number is not recognized as such.
However, there were further developments of the Fermat primality tests: for example, introduced in 1983, the mathematician Leonard M. A dleman , Carl P omerance , Robert R umely , H. C heights and Hendrik W. L coastal road Jr. named after them APRCL test before .
More primality tests
literature
- Paulo Ribenboim : The world of prime numbers . Springer Verlag, 1996