galois.is_prime_fermat¶
- class galois.is_prime_fermat(n)¶
Determines if \(n\) is composite.
This function implements Fermat’s primality test. The test says that for an integer \(n\), select an integer \(a\) coprime with \(n\). If \(a^{n-1} \equiv 1 (\textrm{mod}\ n)\), then \(n\) is prime or pseudoprime.
- Parameters
n (int) – A positive integer.
- Returns
False
if \(n\) is known to be composite.True
if \(n\) is prime or pseudoprime.- Return type
References
Examples
# List of some primes In [518]: primes = [257, 24841, 65497] In [519]: for prime in primes: .....: is_prime = galois.is_prime_fermat(prime) .....: p, k = galois.prime_factors(prime) .....: print("Prime = {:5d}, Fermat's Prime Test = {}, Prime factors = {}".format(prime, is_prime, list(p))) .....: Prime = 257, Fermat's Prime Test = True, Prime factors = [257] Prime = 24841, Fermat's Prime Test = True, Prime factors = [24841] Prime = 65497, Fermat's Prime Test = True, Prime factors = [65497] # List of some strong pseudoprimes with base 2 In [520]: pseudoprimes = [2047, 29341, 65281] In [521]: for pseudoprime in pseudoprimes: .....: is_prime = galois.is_prime_fermat(pseudoprime) .....: p, k = galois.prime_factors(pseudoprime) .....: print("Pseudoprime = {:5d}, Fermat's Prime Test = {}, Prime factors = {}".format(pseudoprime, is_prime, list(p))) .....: Pseudoprime = 2047, Fermat's Prime Test = True, Prime factors = [23, 89] Pseudoprime = 29341, Fermat's Prime Test = True, Prime factors = [13, 37, 61] Pseudoprime = 65281, Fermat's Prime Test = True, Prime factors = [97, 673]