 Probable prime

A probable prime is an integer that passes a specified necessary test for primality without thereby receiving a proof of primality. The qualification must identify the test and bases. For example, an odd $n$ passing a Fermat test to base $a$ satisfies $a^{n-1}\equiv 1(\mathrm{mod}n)$, but a composite can satisfy that congruence.

The Miller-Rabin primality test imposes a stronger condition on a chain of modular squares. Yet $2047=23\cdot 89$ passes even that test to base 2: writing $2046=2\cdot 1023$, one has $2^{1023}=(2^{11}{)}^{93}\equiv 1(\mathrm{mod}2047)$. A pass therefore means “not disproved by this test”, whereas a failing witness proves compositeness. With independent uniformly sampled bases, the standard worst-case error bound decreases exponentially with the number of rounds; it is a conditional test-error bound, not automatically the posterior probability that the particular input is prime.^[ref]