Miller-Rabin-tanúk száma – bizonyítás

1. eset: $n$ valamilyen prímhatvány

Ekkor tehát $n=p^c$ , ahol $p$ valamilyen páratlan prímszám, továbbá $c\geq 2$ , máskülönben $n=p$ nem lenne összetett. A 24.18. Tétel 2. és 3. pontjai alapján a nem Miller-Rabin-tanúk $G_n$ -nel jelölt halmaza egy valódi részcsoportot alkot a $(\Z/n\Z)^{\times}$ multiplikatív csoportban. A Lagrange-tétel (24.8. Tétel) alapján a $G_n$ részcsoport rendje osztója a $(\Z/n\Z)^{\times}$ csoport rendjének. Minthogy $G_n$ valódi részcsoport, ezért ez alapján az elemeinek a száma legfeljebb feleannyi, mint a $(\Z/n\Z)^{\times}$ csoport elemeinek a száma. A redukált maradékosztályoknak tehát legfeljebb a fele lehet nem Miller-Rabin-tanú. Másként fogalmazva legalább a felük Miller-Rabin-tanú kell legyen.

2. eset: $n$ nem prímhatvány, azaz legalább két prímtényezője van.

Ekkor a nem Miller-Rabin-tanúk ugyan nem alkotnak részcsoportot $(\Z/n\Z)^{\times}$ -ben, azonban a 24.19. Tétel alapján létezik olyan $H_n$ -nel jelölt valódi részcsoport, amely viszont minden nem Miller-Rabin-tanút tartalmaz. Azaz a következő a helyzet:

A Hn részcsoport elhelyezkedése — A $H_n$ részcsoport elhelyezkedése

Ismét a Lagrange-tétel (24.8. Tétel) miatt a redukált maradékosztályoknak legfeljebb a fele – köztük az összes nem Miller-Rabin-tanú – tartozhat $H_n$ -be. Következésképp ebben az esetben is legalább a felük Miller-Rabin-tanú.

Episode I

Alice és Bob

. rész: Miller-Rabin-tanúk száma – bizonyítás