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 b egész szám a-val azonos maradékosztályban van, akkor teljesül az 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:

\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 és -1 számokkal, amikor a jobboldalaik is. Így tehát az [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 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 n osztója az alábbi kifejezések közül legalább az egyiknek:

\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 a^{n-1}-1, aminek a 16.2. Tétel 7. pontja miatt n szintén osztója. Ez ismét a 20.1. Tétel 3. pontja alapján azt jelenti, hogy teljesül az a^{n-1}\equiv 1\pmod n kongruencia, és így [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 n ö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 n 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

♣