24.16. Tétel
A Miller-Rabin-nemtanúk fedőcsoportja
Legyen n\gt 1 tetszőleges páratlan egész szám, és képezzük a 23.9. Definíció szerinti e\geq 1 kitevőt és k\geq 1 páratlan egész számot. Tekintsük azokat a j kitevőket a 0, 1, 2, ..., e-1 egész számok között, amelyekhez található olyan x egész szám, hogy teljesül az alábbi kongruencia:
x^{2^j}\equiv -1\pmod n
E kitevők között mindig létezik legnagyobb, amelyet az n-hez tartozó kritikus négyzetreemelési szintnek nevezzük, és j_{\text{max}}-szal jelöljük.
Jelöljük továbbá H_n-nel azon [a]_n modulo n maradékosztályok halmazát, amelyek esetén teljesül az alábbi kongruencia:
a^{2^{j_{\text{max}}}k}\equiv \pm 1\pmod n
Ekkor H_n részcsoport (\Z/n\Z)^{\times}-ben, azaz:
H_n\leq (\Z/n\Z)^{\times}
Ezt a részcsoportot az n-hez tartozó Miller-Rabin-nemtanúk fedőcsoportjának nevezzük.
♣