Overview
The Fermat primality test raises bases a to n - 1 modulo n and expects the result to be 1 for primes that do not divide a. It is fast, but Carmichael numbers and other pseudoprimes make it weaker than Miller-Rabin.
CoreSource checked
Fermat Primality Test
Checks probable primality using Fermat's congruence for selected bases.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Cryptography
- Difficulty
- Intermediate
- Family
- Primality Testing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
probabilistic primality testingprimality testingmodular arithmeticcryptography
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(k)
Average
O(k^2)
Worst
O(k^3)
Space
O(k)
When to Use
- Use as a lightweight screen when false probable-prime results are acceptable.
- Use to teach why stronger tests such as Miller-Rabin are needed.
When Not to Use
- Avoid for cryptographic prime generation by itself.
- Avoid when Carmichael-number false positives would be unacceptable.
What It Does
- Chooses bases that are coprime to n
- Computes a^(n - 1) modulo n
- Rejects n when Fermat's congruence fails
Use Cases
- Fast educational probable-prime checks
- Initial screening before stronger primality tests
- Demonstrating modular arithmetic and pseudoprimes
Inputs
- Message, key, modulus, seed, or public parameters
- Security parameter or nonce when required
Outputs
- Cryptographic value such as signature, random bits, proof, or modular result
Pseudocode
- 1.Reject n < 2 and handle small primes
- 2.For each selected base a, compute g = gcd(a, n)
- 3.If g > 1, return composite unless g = n
- 4.Compute a^(n - 1) mod n
- 5.Return composite if the result is not 1
- 6.Return probably prime after all selected bases pass
Canonical Example
- Input
- n = 15, base = 2
- Output
- composite
- Explanation
- 2^14 mod 15 is not 1, so 15 fails Fermat's congruence for base 2.
Implementation Notes
- Handle n < 2, n = 2, and even n before modular exponentiation.
- Use fast modular exponentiation and reject when gcd(a, n) reveals a factor.
- Follow with Miller-Rabin when a stronger probable-prime result is needed.
Common Pitfalls
- Assuming passing several bases proves primality.
- Forgetting to check gcd(a, n) before applying the congruence.
- Ignoring small n, even n, and base-range edge cases.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow testing whether Fermat's congruence holds for selected bases on a small probabilistic primality testing example.
Step 1 of 6: Reject n < 2 and handle small primes
cryptography-mechanismNotes
Fermat testing is best treated as a screen, not as a final primality decision for security-sensitive code.
Sources (2)
What each reference supports for this entry.
Handbook of Applied Cryptography
BookCryptographic reference for Fermat Primality Test's number-theoretic primitive, modular arithmetic, primality, or factorization context.
Open sourceModern Computer Arithmetic
BookReference for Fermat Primality Test's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toMiller-Rabin Primality Test
Cryptography · Core
Miller-Rabin catches many Fermat pseudoprimes by checking additional square-root conditions.
Compare with thisRelationships
View full relationship pageAlternative toMiller-Rabin Primality Test
Miller-Rabin catches many Fermat pseudoprimes by checking additional square-root conditions.
Fermat testing may use gcd to detect bases that already share a factor with n.
Often paired withModular Exponentiation
The test depends on efficient modular exponentiation.
Related Algorithms
Tags
Cryptography