youproof.orgDeep Math. Human Access.

Megjegyzés

A Fermat-tanúkhoz hasonlóan ebben az esetben is teljes maradékosztályokról célszerű beszélni. Ha ugyanis egy bb egész szám aa-val azonos maradékosztályban van, akkor teljesül az a≡b(modn)a\equiv b\pmod n kongruencia, és így a 20.2. Tétel 6. pontja alapján teljesülnek az alábbi kongruenciák is:

ak≡bk(modn)a2k≡b2k(modn)a4k≡b4k(modn)⋮a2e−1⋅k≡b2e−1⋅k(modn)\begin{aligned}a^k&\equiv b^k\pmod n \\ a^{2k}&\equiv b^{2k}\pmod n \\ a^{4k}&\equiv b^{4k}\pmod n \\ &\vdots \\ a^{2^{e-1}\cdot k}&\equiv b^{2^{e-1}\cdot k}\pmod n\end{aligned}

Mármost e kongruenciák baloldalai pontosan akkor kongruensek a definícióban szereplő +1+1 és −1-1 számokkal, amikor a jobboldalaik is. Így tehát az [a]n[a]_n maradékosztálynak vagy minden eleme teljesíti a Miller-Rabin-tanúkkal szemben támasztott kritériumokat, vagy egyik sem.

Szintén a Fermat-tanúkhoz hasonlóan itt is önkényesen kikötöttük, hogy [a]n[a]_n egy redukált maradékosztály. Ennek terminológiai indoklása szóról szóra megegyezik a 23.3. Definíció utáni megjegyzésben leírtakkal.

Ugyanakkor megjegyezzük, hogy minden Miller-Rabin-nemtanú Fermat-nemtanú is egyben – és így a 23.3. Definíció utáni megjegyzés alapján szintén csak redukált maradékosztály lehetne az említett megszorítás nélkül is. Ilyenkor ugyanis a definícióban szereplő Miller-Rabin-kongruenciák közül teljesül legalább az egyik. Ez a 20.1. Tétel 3. pontja alapján azt jelenti, hogy nn osztója az alábbi kifejezések közül legalább az egyiknek:

ak−1ak+1a2k+1a4k+1⋮a2e−1⋅k+1\begin{aligned}&a^k-1 \\ &a^k+1 \\ &a^{2k}+1 \\ &a^{4k}+1 \\ &\vdots \\ &a^{2^{e-1}\cdot k}+1\end{aligned}

Ám e kifejezések szorzata a 23.8. Tétel alapján épp an−1−1a^{n-1}-1, aminek a 16.2. Tétel 7. pontja miatt nn szintén osztója. Ez ismét a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesül az an−1≡1(modn)a^{n-1}\equiv 1\pmod n kongruencia, és így [a]n[a]_n valóban Fermat-nemtanú. Másként fogalmazva ez azt jelenti, hogy minden Fermat-tanú egyúttal Miller-Rabin-tanú is, vagyis az új definíció valóban tágítani igyekszik az nn összetettségét igazoló tanúk körét.

A 23.5. ábrán a Miller-Rabin-nemtanúk és a Fermat-nemtanúk elhelyezkedése látható az összes nemnulla modulo nn maradékosztályok között. A Miller-Rabin-tanúk pontosan a kiszürkített részben helyezkednek el.

A Miller-Rabin-nemtanúk elhelyezkedése
23.5. ábra: A Miller-Rabin-nemtanúk elhelyezkedése

♣