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: ${\ displaystyle p}$ ${\ displaystyle a}$

{\ displaystyle a ^ {p-1} \ equiv 1 \ mod p}

.

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. ${\ displaystyle a ^ {n-1} -1}$ ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle 2 ^ {8} = 256 = 28 \ cdot 9 + 4 \ equiv 4 \ mod 9}$ ${\ displaystyle n = 9}$

The Fermatsche primality test goes like this:

Input :, the natural number to be tested, result: composite or no statement ${\ displaystyle n}$
Choose a base with . Check whether and are coprime. ${\ displaystyle a}$ ${\ displaystyle 1 <a <n}$ ${\ displaystyle n}$ ${\ displaystyle a}$

If they are not coprime then the result is composite . Otherwise:

If so, the result is a composite .

{\ displaystyle a ^ {n-1} \ not \ equiv 1 \ mod n}

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. ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle a ^ {n-1} -1}$ ${\ displaystyle n}$ ${\ displaystyle a}$ ${\ displaystyle a ^ {n-1} -1}$ ${\ displaystyle n}$ ${\ displaystyle n}$

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. ${\ displaystyle a = 2}$

${\ displaystyle n}$	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
${\ displaystyle 2 ^ {n-1} {\ bmod {n}}}$	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. ${\ displaystyle n = 340}$ ${\ displaystyle 2 ^ {340} -1}$ ${\ displaystyle 341 = 11 \ cdot 31}$

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). ${\ displaystyle n = 2000}$ ${\ displaystyle a}$ ${\ displaystyle x}$ ${\ displaystyle x}$ ${\ displaystyle x}$

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