Fermat's primality test

Fermat's primality test is a test, prich determines, whether the given integer is a prime or not. It is based on Fermat's little theorem, which states that for every prime p and its coprime a it holds that:

{ a^{p-1} \\equiv 1 \\bmod p}

If the equality does not hold, then we can be sure that the number is not a prime. If it does hold, the number might be a prime.

Example

Testing: 15
We choose: a = 5
We suppose:
 {2^{14} \\equiv 1 \\bmod 15}

The test:
 2^{14} = 2^{4} \\cdot 2^{4} \\cdot 2^{4} \\cdot 2^{2} = 16 \\cdot 16 \\cdot 16 \\cdot 4 = 1 \\cdot 1 \\cdot 1 \\cdot 4 = 4 \\;\\; in \\;\\; Z_{15}

Number 5 is a witness that 15 is not a prime.

Example 2

Testing: 15
We choose: a = 4
We suppose:
{4^{14} \\equiv 1 \\bmod 15}

The test:
 4^{14} = (4^2)^7 = 16^7 = 1^7 = 1 \\;\\; in \\;\\; Z_{15}

Number 4 implies that 15 is a prime, however it is not (we have determined that it is composite by the previous test). Let's denote number 4 as Fermat liar.

The flaw

The main flaw of the Fermat's primality test is existence of Carmichael numbers. The Carmichael numbers are absolute Fermat's pseudoprimes, which means that they will always pass this test as primes (regardless which base we choose). This implies that there is no way to compute the probability that the number is (not) a prime, provided it has passed through k iterations of the test.

For this reason Fermat's test is not often used in favor to other primality tests – for example Rabin-Miller, Solovay-Strassen or Lehmann test.


www.EuAutodily.cz SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?