23.9. Definíció
Miller-Rabin-tanú
Legyen n\gt 1 egy tetszőleges páratlan, a pedig tetszőleges n-hez relatív prím egész szám. Képezzük továbbá azt az e\geq 1 kitevőt és k\geq 1 páratlan számot, amelyekre teljesül az alábbi:
n-1=2^e\cdot k
Valamint tegyük fel, hogy az alábbi kongruenciák közül egyik sem teljesül:
\begin{aligned}a^k&\equiv +1\pmod n \\ a^k&\equiv -1\pmod n \\ a^{2k}&\equiv -1\pmod n \\ a^{4k}&\equiv
-1\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv -1\pmod n\end{aligned}
Ekkor az a egész szám által reprezentált [a]_n maradékosztályt az n egész szám Miller-Rabin-tanújának nevezzük. Amennyiben a-ra teljesül a fenti kongruenciák közül legalább az egyik, akkor az [a]_n maradékosztályt Miller-Rabin-nemtanúnak nevezzük. Ha n összetett, akkor az ő Miller-Rabin-nemtanúit Miller-Rabin-cinkosoknak nevezzük.
♣