✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-118

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.

NameExpressionDescription

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

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.

Variables

SymbolMeaning

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

NameDescription

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

NameDescription

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

ProblemSolutionResult

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