youproof.orgDeep Math. Human Access.

23.9. Definíció

Miller-Rabin-tanú

Legyen n>1n\gt 1 egy tetszőleges páratlan, aa pedig tetszőleges nn-hez relatív prím egész szám. Képezzük továbbá azt az e≥1e\geq 1 kitevőt és k≥1k\geq 1 páratlan számot, amelyekre teljesül az alábbi:

n−1=2e⋅kn-1=2^e\cdot k

Valamint tegyük fel, hogy az alábbi kongruenciák közül egyik sem teljesül:

ak≡+1(modn)ak≡−1(modn)a2k≡−1(modn)a4k≡−1(modn)⋮a2e−1⋅k≡−1(modn)\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 aa egész szám által reprezentált [a]n[a]_n maradékosztályt az nn egész szám Miller-Rabin-tanújának nevezzük. Amennyiben aa-ra teljesül a fenti kongruenciák közül legalább az egyik, akkor az [a]n[a]_n maradékosztályt Miller-Rabin-nemtanúnak nevezzük. Ha nn összetett, akkor az ő Miller-Rabin-nemtanúit Miller-Rabin-cinkosoknak nevezzük.

♣