prime_fermat_test


prime_fermat_test, an Octave code which calls prime_fermat(), which applies Fermat's primality test to an integer n, which always correctly identifies primes, but sometimes also accepts nonprimes. Nonetheless, the test is useful for weeding out most nonprimes. The accuracy of the test can be improved by running it for several bases.

The test is based on Fermat's little theorem. If n is prime, and a is any number not divisible by n, then

      a^(n-1) = 1 mod n.
To test whether n is prime, we can pick a random value a and see if the congruence holds. If it does not, then n is definitely not prime. If it holds, we are not sure. We can repeat the test for several values of a to improve our confidence.

Licensing:

The information on this web page is distributed under the MIT license.

Related Data and Programs:

prime_fermat, an Octave code which applies Fermat's primality test to an integer n, which always correctly identifies primes, but sometimes also accepts nonprimes. Nonetheless, the test is useful for weeding out most nonprimes. The accuracy of the test can be improved by running it for several bases.

Source Code:


Last revised on 21 September 2024.