= 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}\equiv1\pmod 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\cdot89$ passes even that test to base 2: writing $2046=2\cdot1023$, one has $2^{1023}=(2^{11})^{93}\equiv1\pmod{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.<Probabilistic Algorithm for Testing Primality by Michael O. Rabin>[§§1–2, witness test and error bound]{ref}
Back to article page
