MillerRabintesten

MillerRabintesten is a term sometimes used to refer to the Miller–Rabin primality test, a probabilistic algorithm for determining whether a given integer n greater than 1 is prime. It blends ideas from the Miller test and Rabin’s probabilistic framework and is widely employed in number theory and cryptography because it can efficiently handle large numbers.

The method operates on odd integers n by expressing n − 1 as d · 2^s with d odd. For a chosen base a (with 2 ≤ a ≤ n − 2), compute x = a^d mod n. If x is 1 or n − 1, the current round passes. Otherwise, repeatedly square x modulo n up to s−1 times; if x becomes n − 1 at any step, the round passes. If none of these conditions occur, n is declared composite. Repeating the test with different bases reduces the probability that a composite number is mistaken for prime. For a single random base, a composite n has at most a 1/4 chance of passing; using k independent bases yields an error probability at most (1/4)^k.

Deterministic variants exist for numbers within specific ranges, where a fixed finite set of bases suffices to guarantee primality. For example, certain bases are known to determine primality for all n < 2^64. In practice, Miller–Rabin is often used to generate probable primes for cryptographic key generation, occasionally under additional primality checks to ensure robustness.

See also: Fermat primality test, probabilistic primality tests, primality testing, and primality proving.