CoreSource checked

Miller-Rabin Primality Test

Tests whether an integer is probably prime by looking for modular witnesses of compositeness.

Explore relationships Open constellationBrowse atlas

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: 1
Relationships: 8
Code example: Ready
Visualization: Ready

Overview

Miller-Rabin writes n - 1 as 2^s d and checks whether chosen bases behave like they should modulo a prime. A failing base proves compositeness; enough independent bases make a probable-prime result reliable for practical prime generation.

Core Concepts

probabilistic primality testingprimality testingrandom samplingcryptography

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 when a fast probable-prime test is acceptable or deterministic base sets are known for the integer range.
Use after eliminating small divisors so modular exponentiation is spent on plausible candidates.

When Not to Use

Avoid when a formal primality proof is required.
Avoid with too few bases or with random-base generation that cannot be trusted.

What It Does

Decomposes n - 1 into an odd factor and powers of two
Raises random or fixed bases modulo n
Rejects n when a base becomes a witness for compositeness

Use Cases

Screening candidate primes for cryptographic key generation
Fast probable-prime checks in number-theory code
Combining trial division with stronger randomized primality testing

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

Key Formulas (1)

Witness test

check a^d mod n and a^{(2^r·d)} mod n for r = 0…s−1

check a^d mod n and a^(2^r*d) mod n for r = 0..s-1

Looks for modular powers that prove compositeness.

Pseudocode

1.Reject n < 2 and handle n = 2, n = 3, and even n
2.Write n - 1 as 2^s * d with d odd
3.For each chosen base a, compute x = a^d mod n
4.Accept this base if x is 1 or n - 1
5.Repeatedly square x up to s - 1 times, accepting if x becomes n - 1
6.If no square reaches n - 1, return composite
7.Return probably prime after all bases pass

Canonical Example

Input: n = 561, base = 2
Output: composite
Explanation: The modular-power sequence exposes behavior impossible for a prime, so 561 is rejected even though it fools simple Fermat testing.

Implementation Notes

Handle n < 2, n = 2, n = 3, and even n before the witness loop.
Use modular exponentiation and multiplication routines appropriate for the word size.
Choose deterministic bases for bounded machine integers or enough independent random bases for large integers.

Common Pitfalls

Testing n <= 3, even n, or small divisors incorrectly creates boundary bugs.
Using too few bases can leave strong pseudoprimes undetected.
Modular exponentiation must avoid overflow for the integer size being tested.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show checking whether random bases witness compositeness on a small probabilistic primality testing example.

Step 1 of 7: Reject n < 2 and handle n = 2, n = 3, and even n

cryptography-mechanism

Notes

A composite result is certain; a probable-prime result depends on the base policy.

Sources (2)

What each reference supports for this entry.

Handbook of Applied Cryptography

Book

Cryptographic reference for Miller-Rabin Primality Test's number-theoretic primitive, modular arithmetic, primality, or factorization context.

Open source

Modern Computer Arithmetic

Book

Reference for Miller-Rabin Primality Test's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.

Open source