Miller–Rabin Witness Density & Convergence: Exploring Prime…

What the Miller–Rabin Test Is

The Miller-Rabin primality test is a probabilistic algorithm used to determine whether a given number is prime. It works by checking if a randomly chosen base (witness) satisfies certain conditions that are true for all primes but may also be satisfied by some composite numbers, known as pseudoprimes.

The test involves several rounds of testing with different bases. If the number passes all these tests, it is considered probably prime; otherwise, it is definitely composite.

Why It Happens

The Miller-Rabin test relies on properties of modular arithmetic and Fermat's little theorem. For a given odd number n, if there exists at least one base a such that the conditions are not satisfied, then n is composite. If no such base is found after several rounds, the probability that n is prime increases exponentially with each additional round.

The density of witnesses (bases for which the test fails) varies depending on whether the number is actually prime or composite. Carmichael numbers, a special class of composite numbers, are particularly interesting as they can fool the Fermat primality test but not the Miller-Rabin test.

live demo · related simulation● LIVE

Witness Density and Convergence

The 2D visualization in this simulation helps illustrate how the density of witnesses (bases that show n is composite) changes as you scan through a range of odd numbers. For prime numbers, the witness density should be close to zero, while for composite numbers, especially Carmichael numbers, it can be much higher.

The convergence refers to how quickly the test converges on a correct answer as more rounds are performed. The simulation demonstrates that with enough rounds (k), the probability of a false positive becomes extremely small.

Practical Applications

In cryptography, the Miller-Rabin test is crucial for generating large prime numbers used in public key systems like RSA. The ability to quickly and accurately determine primality ensures the security of these cryptographic protocols.

The simulation also helps in understanding the trade-off between computational resources (number of rounds) and the confidence level in the result.

Frequently asked questions

What is a Carmichael number?

A Carmichael number is a composite number that passes the Fermat primality test for all bases, making it a pseudoprime. These numbers can fool simple primality tests but are caught by more sophisticated methods like Miller-Rabin.

How does the Monte Carlo simulation work?

The Monte Carlo simulation runs multiple rounds of the Miller-Rabin test with random bases and measures the false-positive rate. It compares this empirical result against the theoretical bound of 4^-k, showing how well the test performs in practice.

Why is witness density important?

Witness density indicates how often a given number fails the Miller-Rabin test as a composite number. A higher density suggests that the number might be composite and helps in assessing the reliability of the primality test results.

What does convergence mean in this context?

Convergence refers to how quickly the probability of a false positive decreases with each additional round of the Miller-Rabin test. More rounds lead to higher confidence that a number is prime, as the chance of it being composite becomes negligible.

Try it live

Everything above runs in your browser — open Miller–Rabin Witness Density & Convergence (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Miller–Rabin Witness Density & Convergence (2D) simulation

Miller–Rabin Witness Density & Convergence: Exploring Prime Number Testing