fermat_prime: Tests if an integer is (probably) prime using the Fermat...

In aschleg/numberr: Numberr is a package containing number-theoretic algorithms and functions primarily written in C++ using Rcpp

Description

Fermat's primality test is a probabilistic method (there is a chance, albeit very small, that a composite number will be flagged as prime) for identifying prime numbers. The test is based on Fermat's Little Theorem, which states that if p is prime and a_{p-1} is not divisible by p, then:

Usage

fermat_prime(n, k = 1000L)

Arguments

n	integer
k	integer, default 1000

Details

a^{p-1} \equiv 1 \space (text{mod} \space p)

The test proceeds as follows: Select a value for a at random that is not divisible by p and check if the equality holds. This test is performed k times and if the equality does not hold, the integer p is composite. It is possible the test will falsely identify a composite number as prime.

Value

TRUE if n is probably prime, FALSE otherwise

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). "Section 31.8: Primality testing". Introduction to Algorithms (Second ed.). MIT Press; McGraw-Hill. Weisstein, Eric W. "Fermat's Little Theorem." From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/FermatsLittleTheorem.html Weisstein, Eric W. "Primality Test." From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/PrimalityTest.html

Examples

fermat_prime(11)
fermat_prime(221)

aschleg/numberr documentation built on May 14, 2019, 10:31 a.m.