A primality test determines whether an integer greater than one is prime or composite. Simple methods, such as trial division, can be effective for small integers but become expensive for very large inputs. Randomized primality tests use selected bases or random values to examine mathematical properties of a candidate integer. The Fermat primality test is based on Fermat's little theorem, which states that if p is prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p). If an integer fails this condition for a suitable base, it is definitely composite. However, some composite integers satisfy the condition for particular bases, so passing a Fermat test does not always establish primality. The Miller–Rabin test improves on this approach by examining the factorization of n − 1 and checking modular exponentiation conditions. A composite number that passes a Miller–Rabin round for a randomly selected suitable base is called a strong probable prime to that base. Repeating the test with independently selected bases reduces the probability of accepting a composite number. The test is widely used in practical computational number theory and cryptographic software. A probabilistic test must be distinguished from a deterministic primality test, which guarantees a correct classification under its stated assumptions.
Randomized Primality Testing
Randomized primality testing uses algorithms involving selected numerical bases or random choices to determine whether an integer is prime or composite. Some tests can provide probabilistic evidence of primality with a controllably small error probability.
| Name | Expression | Description |
|---|---|---|
Fermat's little theorem | a^(p − 1) ≡ 1 (mod p), when p is prime and gcd(a, p) = 1 | A necessary modular condition for primality used in the Fermat test. |
Factorization used by Miller–Rabin | n − 1 = 2^s × d, where d is odd | Every even factor of n − 1 is separated to express the remaining factor d as odd. |
Miller–Rabin modular conditions | a^d ≡ 1 (mod n), or a^(2ʳd) ≡ −1 (mod n) for some 0 ≤ r < s | These are the principal conditions a selected base may satisfy during a Miller–Rabin round. |
Miller–Rabin error bound | P(false probable-prime result) ≤ 4^(−k) | For an odd composite candidate, the standard bound after k independent uniformly selected suitable bases is at most 4 to the power of negative k. |
Explanation
Variables
| Symbol | Meaning |
|---|---|
n | The integer being tested. |
p | A prime integer in Fermat's little theorem. |
a | A selected test base. |
s | The number of factors of 2 in n − 1. |
d | The odd factor in the representation n − 1 = 2^s d. |
k | The number of independent Miller–Rabin rounds. |
r | An integer index used in the Miller–Rabin modular conditions. |
Example or application
A worked example has not yet been added.
Definition
Randomized primality testing is a computational method that uses randomly selected values or bases to test whether an integer is prime, often providing a probabilistic guarantee about the reliability of its result.
Purpose
To test large integers for primality efficiently when exhaustive deterministic methods would be too expensive.
Importance
Primality testing is important in computational number theory and cryptography. Randomized tests such as Miller–Rabin make it practical to examine very large candidate integers while controlling the probability of an incorrect primality conclusion.
Key Concepts
Primality testing
Prime numbers
Composite numbers
Randomized algorithm
Fermat's little theorem
Miller–Rabin test
Modular exponentiation
Witness
Strong probable prime
False positive
Error probability
Repeated independent rounds
Characteristics
Uses modular arithmetic and number-theoretic properties.
Can test integers that are too large for simple trial division to be practical.
May use randomly selected bases.
Can identify composite numbers with certainty when a suitable witness is found.
A probable-prime result is not always a proof of primality.
Repeated independent Miller–Rabin rounds reduce the probability of accepting a composite number.
Some primality tests are probabilistic, while others are deterministic.
Types
| Name | Description |
|---|---|
Fermat primality test | Uses Fermat's little theorem to check whether a candidate integer satisfies a necessary condition for primality. |
Miller–Rabin primality test | Uses modular exponentiation and the factorization of n − 1 to test whether a number is a strong probable prime to selected bases. |
Solovay–Strassen test | A randomized primality test based on Euler's criterion and the Jacobi symbol. |
Deterministic primality tests | Algorithms that guarantee a correct prime-or-composite classification within their stated mathematical and computational assumptions. |
Components
| Name | Description |
|---|---|
Candidate integer | The integer whose primality is being investigated. |
Test base | A selected integer used in modular calculations. |
Modular exponentiation | The calculation of powers modulo the candidate integer. |
Witness | A value demonstrating that a candidate integer is composite. |
Test rounds | Repeated independent or appropriately selected trials that improve confidence in a probabilistic result. |
Result | A classification such as composite or probable prime. |
Properties
Every prime number greater than two is odd.
Fermat's little theorem gives a necessary condition for primality but not a sufficient condition.
A suitable witness can demonstrate that a candidate is composite.
Some composite numbers can pass the Fermat test for particular bases.
Miller–Rabin provides a stronger probabilistic test than the basic Fermat test.
For an odd composite candidate, at most one quarter of suitable bases are strong liars in a standard Miller–Rabin round.
Repeated independent rounds reduce the probability of a false probable-prime result.
A probable-prime result should not be described as an unconditional proof of primality.
Examples
| Problem | Solution | Result |
|---|---|---|
Use Fermat's little theorem to explain why 7 satisfies the condition with base 2. | Since 7 is prime and gcd(2, 7) = 1, Fermat's little theorem gives 2^6 ≡ 1 (mod 7). Indeed, 64 leaves a remainder of 1 when divided by 7. | 2^6 ≡ 1 (mod 7). |
Show that 9 is composite using a Fermat-test base of 2. | 2^8 = 256, and 256 leaves a remainder of 4 when divided by 9. Since the result is not 1, the candidate fails the Fermat condition for this base. | 9 is composite. |
Applications
Generating candidate primes for cryptographic systems
Computational number theory
Cryptographic software
Large-integer analysis
Randomized algorithms
Mathematical experimentation
Testing candidate integers in prime-related computations
Prerequisites
Prime and composite numbers
Divisibility
Modular arithmetic
Modular exponentiation
Fermat's little theorem
Basic probability
Greatest common divisors
Learning Objectives
Explain the purpose of primality testing.
State Fermat's little theorem.
Understand why the Fermat test can produce misleading results for some composite numbers.
Explain the basic mathematical idea behind the Miller–Rabin test.
Distinguish a composite result from a probable-prime result.
Understand how repeated rounds reduce the probability of error.
Recognize the importance of randomized primality testing in cryptography.
Common Mistakes
Assuming that passing one Fermat test proves primality.
Confusing a probable prime with a proven prime.
Ignoring the possibility of composite numbers that pass certain modular tests.
Assuming that all randomized primality tests have the same error bounds.
Using unsuitable or predictable bases without considering the algorithm's assumptions.
Confusing a witness for compositeness with a proof of primality.
Practice Questions
What is a primality test?
State Fermat's little theorem.
Why does the Fermat test not prove primality in every case?
What is a witness to compositeness?
What is the main idea behind the Miller–Rabin test?
Why are multiple rounds of Miller–Rabin useful?
What is the difference between a probable prime and a proven prime?
Explain one application of randomized primality testing.
Key Takeaway
Randomized primality tests use modular arithmetic and carefully selected bases to identify composite numbers efficiently and provide strong probabilistic evidence of primality.
Related Topics
Prime Numbers
Modular Arithmetic in Computer Science
Pseudorandom Numbers and Modular Methods
Elementary Probability in Number Theory
Number Theory in Cryptography
Prime Factorization Algorithms
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory