Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze

11.11.2022

Twierdzenie Fermata

Twierdzenie K1 (Pierre de Fermat, 1640)
Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math]. Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą

to liczba [math]\displaystyle{ a^p - a }[/math] jest podzielna przez [math]\displaystyle{ p }[/math], czyli [math]\displaystyle{ a^p \equiv a \pmod p }[/math]
i jeśli dodatkowo [math]\displaystyle{ p \nmid a }[/math], to liczba [math]\displaystyle{ a^{p - 1} - 1 }[/math] jest podzielna przez [math]\displaystyle{ p }[/math], czyli [math]\displaystyle{ a^{p - 1} \equiv 1 \pmod p }[/math]

Dowód

Punkt 1.

Zauważmy, że
a) twierdzenie jest prawdziwe dla [math]\displaystyle{ a = 0 }[/math]
b) w przypadku, gdy [math]\displaystyle{ p = 2 }[/math] wyrażenie [math]\displaystyle{ a^p - a = a^2 - a = a (a - 1) }[/math] jest podzielne przez [math]\displaystyle{ 2 }[/math], bo jedna z liczb [math]\displaystyle{ a - 1 }[/math] i [math]\displaystyle{ a }[/math] jest liczbą parzystą
c) w przypadku, gdy [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i twierdzenie jest prawdziwe dla [math]\displaystyle{ a \geqslant 1 }[/math], to jest też prawdziwe dla [math]\displaystyle{ - a }[/math], bo

[math]\displaystyle{ (- a)^p - (- a) = (- 1)^p a^p + a = - a^p + a = - (a^p - a) }[/math]

Zatem wystarczy pokazać, że dla ustalonej liczby pierwszej nieparzystej [math]\displaystyle{ p }[/math] twierdzenie jest prawdziwe dla każdego [math]\displaystyle{ a \in \mathbb{Z}_+ }[/math].

Indukcja matematyczna. Dla [math]\displaystyle{ a = 1 }[/math] mamy [math]\displaystyle{ 1^p - 1 = 0 }[/math] zatem liczba pierwsza [math]\displaystyle{ p }[/math] jest dzielnikiem rozważanego wyrażenia. Zakładając, że twierdzenie jest prawdziwe dla [math]\displaystyle{ a }[/math], czyli [math]\displaystyle{ p|a^p - a }[/math], otrzymujmy dla [math]\displaystyle{ a + 1 }[/math]

[math]\displaystyle{ (a + 1)^p - (a + 1) = \sum_{k = 0}^{p} \binom{p}{k} \cdot a^k - a - 1 }[/math]

[math]\displaystyle{ \;\;\,\, = 1 + \sum_{k = 1}^{p - 1} \binom{p}{k} \cdot a^k + a^p - a - 1 }[/math]

[math]\displaystyle{ \;\;\,\, = a^p - a + \sum^{p - 1}_{k = 1} \binom{p}{k} \cdot a^k }[/math]

Z założenia indukcyjnego [math]\displaystyle{ p|a^p - a }[/math], zaś [math]\displaystyle{ \binom{p}{k} = {\small\frac{p!}{k! \cdot (p - k) !}} }[/math] dla [math]\displaystyle{ k = 1, 2, \ldots, p - 1 }[/math] jest podzielne przez [math]\displaystyle{ p }[/math] (ponieważ [math]\displaystyle{ p }[/math] dzieli licznik, ale nie dzieli mianownika). Zatem [math]\displaystyle{ (a + 1)^p - (a + 1) }[/math] jest podzielne przez liczbę pierwszą [math]\displaystyle{ p }[/math].

Punkt 2.

Z punktu 1. wiemy, że liczba pierwsza [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ a^p - a = a (a^{p - 1} - 1) }[/math]. Jeżeli [math]\displaystyle{ p \nmid a }[/math], to z lematu Euklidesa (zobacz twierdzenie C70) wynika natychmiast, że [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ a^{p - 1} - 1 }[/math].
□

Uwaga K2
Z twierdzenia Fermata wynika, że jeżeli liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ m }[/math] są względnie pierwsze oraz [math]\displaystyle{ m }[/math] nie dzieli liczby [math]\displaystyle{ a^{m - 1} - 1 }[/math], to [math]\displaystyle{ m }[/math] jest liczbą złożoną. Każde twierdzenie pozwalające wykryć złożoność liczby może być wykorzystane do badania pierwszości liczb. Twierdzenia takie nie dają całkowitej pewności, że badana liczba jest pierwsza. Mamy na przykład [math]\displaystyle{ 341 = 11 \cdot 31 }[/math], ale [math]\displaystyle{ 341 | (2^{340} - 1) }[/math], bo

[math]\displaystyle{ 2^{340} - 1 = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115775 }[/math]

[math]\displaystyle{ \;\;\:\, = 341 \cdot 6568166399348399444449977362370804334667582103327417990909058947107894050381703652143335757394742275 }[/math]

Widzimy, że nawet dla niewielkiej liczby [math]\displaystyle{ 341 }[/math], potęga [math]\displaystyle{ 2^{340} - 1 }[/math] jest liczbą ogromną. Jeśli ta metoda ma mieć jakiekolwiek zastosowanie, to musimy znaleźć inny sposób obliczania reszty z dzielenia [math]\displaystyle{ a^n }[/math] przez [math]\displaystyle{ m }[/math], czyli potęgowania modulo [math]\displaystyle{ m }[/math].

Potęgowanie modulo

Uwaga K3
Wykorzystując wzór rekurencyjny

[math]\displaystyle{ a^n = \left\{ \begin{array}{cll} a & & \text{gdy } n = 1\\ (a^2)^{{\large\frac{n}{2}}} & & \text{gdy } n \text{ jest parzyste}\\ a \cdot (a^2)^{{\large\frac{n - 1}{2}}} & & \text{gdy } n \text{ jest nieparzyste} \end{array} \right. }[/math]

możemy napisać w PARI/GP prosty program do potęgowania modulo:

modPower(a, n, m) = 
\\ a - podstawa, n - wykładnik, m - moduł
{
local(w);
if( m == 1, return(0) );
a = a % m;
w = 1;
while( n > 0,
       if( n % 2 == 1, w = (w * a) % m; n = n - 1); \\ gdy n jest nieparzyste, wyłączamy a i zmniejszamy n o jeden
       a = (a*a) % m; \\ wyliczamy nową podstawę modulo m
       n = n/2; \\ dla nowej podstawy wykładnik jest dwa razy mniejszy
     );
return(w);
}

Zauważmy, że w funkcji modPower() nie występują wyrażenia o wartości większej od [math]\displaystyle{ m^2 }[/math].

Liczby pseudopierwsze Fermata

Liczby złożone nieparzyste spełniające równanie Fermata, otrzymały własną nazwę.

Definicja K4
Jeżeli [math]\displaystyle{ m }[/math] jest liczbą złożoną nieparzystą i dla pewnego [math]\displaystyle{ a \in \mathbb{Z} }[/math] prawdziwa jest kongruencja

[math]\displaystyle{ a^{m - 1} \equiv 1 \pmod m }[/math]

to powiemy, że [math]\displaystyle{ m }[/math] jest liczbą pseudopierwszą Fermata przy podstawie [math]\displaystyle{ a }[/math] lub krótko: [math]\displaystyle{ m }[/math] jest FPSP([math]\displaystyle{ a }[/math]).

Uwaga K5
Zauważmy, że w definicji liczb pseudopierwszych Fermata nie musimy dodatkowo dołączać warunku [math]\displaystyle{ \gcd (a, m) = 1 }[/math], bo wynika on z przyjętej definicji. Mamy

[math]\displaystyle{ \gcd (a^{m - 1}, m) = \gcd (1, m) = 1 }[/math]

Zatem [math]\displaystyle{ \gcd (a, m) = 1 }[/math].

Możemy też łatwo pokazać, że jeżeli [math]\displaystyle{ \gcd (a, m) = d \gt 1 }[/math], to liczba [math]\displaystyle{ m }[/math] nie może być liczbą pseudopierwszą Fermata przy podstawie [math]\displaystyle{ a }[/math]. Istotnie, gdyby tak było, to mielibyśmy

[math]\displaystyle{ a^{m - 1} \equiv 1 \pmod{m} }[/math]

Ponieważ [math]\displaystyle{ d|m }[/math], to jest również

[math]\displaystyle{ a^{m - 1} \equiv 1 \pmod{d} }[/math]

Ale modulo [math]\displaystyle{ d }[/math] otrzymujemy natychmiast

[math]\displaystyle{ 0 \equiv 1 \pmod{d} }[/math]

Co jest niemożliwe, czyli [math]\displaystyle{ m }[/math] nie jest FPSP([math]\displaystyle{ a }[/math]).

Twierdzenie K6
Dla każdej podstawy [math]\displaystyle{ a \geqslant 2 }[/math] istnieje nieskończenie wiele liczb pseudopierwszych Fermata.

Dowód

Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math] i [math]\displaystyle{ a \geqslant 2 }[/math]. Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą, to

[math]\displaystyle{ a^p - 1 = (a - 1) (a^{p - 1} + a^{p - 2} + \ldots + a^2 + a + 1) }[/math]

oraz

[math]\displaystyle{ a^p + 1 = (a + 1) (a^{p - 1} - a^{p - 2} + \ldots + a^2 - a + 1) }[/math]

Czyli [math]\displaystyle{ a - 1 | a^p - 1 }[/math] oraz [math]\displaystyle{ a + 1 | a^p + 1 }[/math].

Jeżeli przez [math]\displaystyle{ R_2 (a) }[/math] oznaczymy resztę z dzielenia liczby [math]\displaystyle{ a }[/math] przez [math]\displaystyle{ 2 }[/math] równą [math]\displaystyle{ 0 }[/math] lub [math]\displaystyle{ 1 }[/math], to prawdziwe są kongruencje

[math]\displaystyle{ a \equiv R_2 (a) \pmod 2 }[/math]

oraz

[math]\displaystyle{ a^n \equiv R_2 (a) \pmod 2 }[/math]

dla dowolnej liczby całkowitej dodatniej [math]\displaystyle{ n }[/math]. Zatem modulo [math]\displaystyle{ 2 }[/math] jest

[math]\displaystyle{ {\small\frac{a^p - 1}{a - 1}} \equiv R_2 (a) \cdot (p - 1) + 1 \equiv 1 \pmod 2 }[/math]

[math]\displaystyle{ {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2 }[/math]

Co oznacza, że

[math]\displaystyle{ m = {\small\frac{a^p - 1}{a - 1}} \cdot {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2 }[/math]

Czyli [math]\displaystyle{ m }[/math] jest złożoną liczbą nieparzystą. Pozostaje pokazać, że [math]\displaystyle{ a^{m - 1} \equiv 1 \pmod m }[/math].

Z twierdzenia Fermata wiemy, że

[math]\displaystyle{ a^p - 1 \equiv a - 1 \pmod p }[/math]

Ponieważ [math]\displaystyle{ (a - 1) | (a^p - 1) }[/math], to możemy napisać

[math]\displaystyle{ (a - 1) \cdot \left( {\small\frac{a^p - 1}{a - 1}} - 1 \right) \equiv 0 \pmod p }[/math]

Z założenia [math]\displaystyle{ p \nmid (a - 1) }[/math], zatem liczba pierwsza [math]\displaystyle{ p }[/math] musi dzielić [math]\displaystyle{ {\small\frac{a^p - 1}{a - 1}} - 1 }[/math] i otrzymujemy

[math]\displaystyle{ {\small\frac{a^p - 1}{a - 1}} \equiv 1 \pmod p }[/math]

Postępując analogicznie jak wyżej, dostajemy

[math]\displaystyle{ a^p + 1 \equiv a + 1 \pmod p }[/math]

[math]\displaystyle{ (a + 1) \cdot \left( {\small\frac{a^p + 1}{a + 1}} - 1 \right) \equiv 0 \pmod p }[/math]

[math]\displaystyle{ {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod p }[/math]

Wynika stąd, że [math]\displaystyle{ m \equiv 1 \pmod p }[/math].

Zbierając mamy [math]\displaystyle{ 2| (m - 1) }[/math] i [math]\displaystyle{ p| (m - 1) }[/math], zatem [math]\displaystyle{ 2 p| (m - 1) }[/math], czyli

[math]\displaystyle{ m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} \equiv 1 \pmod{2 p} }[/math]

Oznacza to, że [math]\displaystyle{ m = 1 + 2 k p }[/math] dla pewnej liczby całkowitej [math]\displaystyle{ k \gt 0 }[/math].

Zauważmy teraz, że z definicji liczby [math]\displaystyle{ m }[/math] mamy [math]\displaystyle{ (a^2 - 1) m = a^{2 p} - 1 }[/math]. Rozpatrując to równanie modulo [math]\displaystyle{ m }[/math], otrzymujemy

[math]\displaystyle{ a^{2 p} \equiv 1 \pmod m }[/math]

Zatem modulo [math]\displaystyle{ m }[/math] jest

[math]\displaystyle{ a^{m - 1} = a^{2 k p} = (a^{2 p})^k \equiv 1^k \equiv 1 \pmod m }[/math]

Ponieważ dowolna liczba pierwsza [math]\displaystyle{ p \gt a^2 - 1 }[/math] nie dzieli [math]\displaystyle{ a^2 - 1 }[/math], to dla każdego [math]\displaystyle{ a \geqslant 2 }[/math] istnieje nieskończenie wiele liczb, które są FPSP([math]\displaystyle{ a }[/math]). Co należało pokazać.
□

Przykład K7
Z dowodu twierdzenia K6 wynika, że jeżeli liczba [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ p \nmid (a^2 - 1) }[/math], to liczba [math]\displaystyle{ m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} }[/math] jest FPSP([math]\displaystyle{ a }[/math]). Poniżej przedstawiamy przykłady takich liczb, dla kolejnych liczb pierwszych nieparzystych [math]\displaystyle{ p }[/math] takich, że [math]\displaystyle{ p \nmid (a^2 - 1) }[/math].

for(a=2, 5, s=1; d=a^2-1; forprime(p=3, 50, if( d%p == 0, next() ); m=(a^(2*p)-1)/d; print("a= ", a, "   m= ", m); s++; if( s>6, break() ) ))

[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]
[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 17895697 }[/math]	[math]\displaystyle{ 406901 }[/math]
[math]\displaystyle{ 5461 }[/math]	[math]\displaystyle{ 7381 }[/math]	[math]\displaystyle{ 1172812402961 }[/math]	[math]\displaystyle{ 254313151 }[/math]
[math]\displaystyle{ 1398101 }[/math]	[math]\displaystyle{ 597871 }[/math]	[math]\displaystyle{ 300239975158033 }[/math]	[math]\displaystyle{ 99341074625651 }[/math]
[math]\displaystyle{ 22369621 }[/math]	[math]\displaystyle{ 3922632451 }[/math]	[math]\displaystyle{ 19676527011956855057 }[/math]	[math]\displaystyle{ 62088171641031901 }[/math]
[math]\displaystyle{ 5726623061 }[/math]	[math]\displaystyle{ 317733228541 }[/math]	[math]\displaystyle{ 5037190915060954894609 }[/math]	[math]\displaystyle{ 24253192047278086344401 }[/math]
[math]\displaystyle{ 91625968981 }[/math]	[math]\displaystyle{ 2084647712458321 }[/math]	[math]\displaystyle{ 330117343809434739973099793 }[/math]	[math]\displaystyle{ 15158245029548803965250651 }[/math]

Uwaga K8
Wykorzystując funkcję potęgowania modulo, możemy napisać prosty program do testowania pierwszości liczb w oparciu o twierdzenie Fermata.

isPrimeOrFPSP(m, a) = 
{
if( modPower(a, m-1, m) == 1, return(1), return(0) );
}

Przykład K9
Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Fermata dla podstaw [math]\displaystyle{ a }[/math] od [math]\displaystyle{ 2 }[/math] do [math]\displaystyle{ 15 }[/math]

for(a=2, 15, s=1; forstep(m=1, 2000, 2, if( isPrimeOrFPSP(m, a)  &&  !isprime(m), print("a=", a, "  m=", m); s++ ); if( s>5, break() ) ))

[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]	[math]\displaystyle{ \boldsymbol{11} }[/math]	[math]\displaystyle{ \boldsymbol{12} }[/math]	[math]\displaystyle{ \boldsymbol{13} }[/math]	[math]\displaystyle{ \boldsymbol{14} }[/math]	[math]\displaystyle{ \boldsymbol{15} }[/math]
[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 65 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 341 }[/math]
[math]\displaystyle{ 561 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 561 }[/math]	[math]\displaystyle{ 185 }[/math]	[math]\displaystyle{ 325 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 133 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 39 }[/math]	[math]\displaystyle{ 1477 }[/math]
[math]\displaystyle{ 645 }[/math]	[math]\displaystyle{ 671 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 781 }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 561 }[/math]	[math]\displaystyle{ 45 }[/math]	[math]\displaystyle{ 205 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 259 }[/math]	[math]\displaystyle{ 133 }[/math]	[math]\displaystyle{ 105 }[/math]	[math]\displaystyle{ 65 }[/math]	[math]\displaystyle{ 1541 }[/math]
[math]\displaystyle{ 1105 }[/math]	[math]\displaystyle{ 703 }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 1541 }[/math]	[math]\displaystyle{ 301 }[/math]	[math]\displaystyle{ 703 }[/math]	[math]\displaystyle{ 63 }[/math]	[math]\displaystyle{ 511 }[/math]	[math]\displaystyle{ 99 }[/math]	[math]\displaystyle{ 305 }[/math]	[math]\displaystyle{ 143 }[/math]	[math]\displaystyle{ 231 }[/math]	[math]\displaystyle{ 195 }[/math]	[math]\displaystyle{ 1687 }[/math]
[math]\displaystyle{ 1387 }[/math]	[math]\displaystyle{ 949 }[/math]	[math]\displaystyle{ 435 }[/math]	[math]\displaystyle{ 1729 }[/math]	[math]\displaystyle{ 481 }[/math]	[math]\displaystyle{ 817 }[/math]	[math]\displaystyle{ 65 }[/math]	[math]\displaystyle{ 671 }[/math]	[math]\displaystyle{ 259 }[/math]	[math]\displaystyle{ 481 }[/math]	[math]\displaystyle{ 145 }[/math]	[math]\displaystyle{ 357 }[/math]	[math]\displaystyle{ 481 }[/math]	[math]\displaystyle{ 1729 }[/math]

Przykład K10
Tabela pokazuje ilość liczb pseudopierwszych Fermata dla podstaw [math]\displaystyle{ a }[/math] od [math]\displaystyle{ 2 }[/math] do [math]\displaystyle{ 15 }[/math]

for(a=2, 15, s=0; forstep(k=1, 10^6, 2, if( isPrimeOrFPSP(k, a)  &&  !isprime(k), s++ )); print("a= ", a, "   ", s))

[math]\displaystyle{ \boldsymbol{a} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]	[math]\displaystyle{ \boldsymbol{11} }[/math]	[math]\displaystyle{ \boldsymbol{12} }[/math]	[math]\displaystyle{ \boldsymbol{13} }[/math]	[math]\displaystyle{ \boldsymbol{14} }[/math]	[math]\displaystyle{ \boldsymbol{15} }[/math]
#FPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^6 }[/math]	[math]\displaystyle{ 245 }[/math]	[math]\displaystyle{ 243 }[/math]	[math]\displaystyle{ 464 }[/math]	[math]\displaystyle{ 238 }[/math]	[math]\displaystyle{ 301 }[/math]	[math]\displaystyle{ 229 }[/math]	[math]\displaystyle{ 678 }[/math]	[math]\displaystyle{ 362 }[/math]	[math]\displaystyle{ 271 }[/math]	[math]\displaystyle{ 236 }[/math]	[math]\displaystyle{ 378 }[/math]	[math]\displaystyle{ 257 }[/math]	[math]\displaystyle{ 283 }[/math]	[math]\displaystyle{ 203 }[/math]
#FPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^7 }[/math]	[math]\displaystyle{ 750 }[/math]	[math]\displaystyle{ 749 }[/math]	[math]\displaystyle{ 1347 }[/math]	[math]\displaystyle{ 726 }[/math]	[math]\displaystyle{ 895 }[/math]	[math]\displaystyle{ 651 }[/math]	[math]\displaystyle{ 1993 }[/math]	[math]\displaystyle{ 1150 }[/math]	[math]\displaystyle{ 766 }[/math]	[math]\displaystyle{ 672 }[/math]	[math]\displaystyle{ 1091 }[/math]	[math]\displaystyle{ 719 }[/math]	[math]\displaystyle{ 817 }[/math]	[math]\displaystyle{ 614 }[/math]
#FPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^8 }[/math]	[math]\displaystyle{ 2057 }[/math]	[math]\displaystyle{ 2131 }[/math]	[math]\displaystyle{ 3805 }[/math]	[math]\displaystyle{ 1910 }[/math]	[math]\displaystyle{ 2314 }[/math]	[math]\displaystyle{ 1782 }[/math]	[math]\displaystyle{ 5407 }[/math]	[math]\displaystyle{ 3214 }[/math]	[math]\displaystyle{ 2091 }[/math]	[math]\displaystyle{ 1891 }[/math]	[math]\displaystyle{ 2933 }[/math]	[math]\displaystyle{ 1929 }[/math]	[math]\displaystyle{ 2155 }[/math]	[math]\displaystyle{ 1718 }[/math]
#FPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^9 }[/math]	[math]\displaystyle{ 5597 }[/math]	[math]\displaystyle{ 5767 }[/math]	[math]\displaystyle{ 10173 }[/math]	[math]\displaystyle{ 5146 }[/math]	[math]\displaystyle{ 6204 }[/math]	[math]\displaystyle{ 4923 }[/math]	[math]\displaystyle{ 14629 }[/math]	[math]\displaystyle{ 8670 }[/math]	[math]\displaystyle{ 5599 }[/math]	[math]\displaystyle{ 5020 }[/math]	[math]\displaystyle{ 7781 }[/math]	[math]\displaystyle{ 5082 }[/math]	[math]\displaystyle{ 5848 }[/math]	[math]\displaystyle{ 4665 }[/math]

Uwaga K11
Można pokazać, że jeżeli [math]\displaystyle{ m }[/math] jest liczbą nieparzystą złożoną i istnieje przynajmniej jedna liczba [math]\displaystyle{ a }[/math] względnie pierwsza z [math]\displaystyle{ m }[/math], taka że

[math]\displaystyle{ a^{m - 1} \not\equiv 1 \pmod m }[/math]

to dla co najmniej połowy liczb [math]\displaystyle{ b \in [1, m - 1] }[/math] względnie pierwszych z [math]\displaystyle{ m }[/math] jest

[math]\displaystyle{ b^{m - 1} \not\equiv 1 \pmod m }[/math]

Zatem przeprowadzając test Fermata, możemy z prawdopodobieństwem nie mniejszym niż [math]\displaystyle{ \tfrac{1}{2} }[/math] twierdzić, że liczba, która przeszła test, jest liczbą pierwszą. Wykonując test [math]\displaystyle{ k }[/math] razy dla [math]\displaystyle{ k }[/math] różnych podstaw z przedziału [math]\displaystyle{ [1, m - 1] }[/math] możemy z prawdopodobieństwem większym niż [math]\displaystyle{ 1 - \left( \tfrac{1}{2} \right)^k }[/math] twierdzić, że badana liczba [math]\displaystyle{ m }[/math] jest pierwsza.

Niestety, istnieją liczby złożone [math]\displaystyle{ m }[/math] takie, że

[math]\displaystyle{ a^{m - 1} \equiv 1 \pmod m }[/math]

dla każdego [math]\displaystyle{ a }[/math] względnie pierwszego z [math]\displaystyle{ m }[/math]. Liczby te nazywamy liczbami Carmichaela i jest ich nieskończenie wiele. Pokazano, że dla dostatecznie dużych [math]\displaystyle{ x }[/math] ilość liczb Carmichaela mniejszych od [math]\displaystyle{ x }[/math] przekracza [math]\displaystyle{ x^{1/3} }[/math]^[1]^[2]^[3]. Test Fermata jest zatem zbyt zawodny, aby można było go stosować.

Przykład K12
Oto wszystkie liczby Carmichaela mniejsze od [math]\displaystyle{ 100 000 }[/math]

[math]\displaystyle{ 561=3⋅11⋅17 }[/math]	[math]\displaystyle{ 1105=5⋅13⋅17 }[/math]	[math]\displaystyle{ 1729=7⋅13⋅19 }[/math]	[math]\displaystyle{ 2465=5⋅17⋅29 }[/math]
[math]\displaystyle{ 2821=7⋅13⋅31 }[/math]	[math]\displaystyle{ 6601=7⋅23⋅41 }[/math]	[math]\displaystyle{ 8911=7⋅19⋅67 }[/math]	[math]\displaystyle{ 10585=5⋅29⋅73 }[/math]
[math]\displaystyle{ 15841=7⋅31⋅73 }[/math]	[math]\displaystyle{ 29341=13⋅37⋅61 }[/math]	[math]\displaystyle{ 41041=7⋅11⋅13⋅41 }[/math]	[math]\displaystyle{ 46657=13⋅37⋅97 }[/math]
[math]\displaystyle{ 52633=7⋅73⋅103 }[/math]	[math]\displaystyle{ 62745=3⋅5⋅47⋅89 }[/math]	[math]\displaystyle{ 63973=7⋅13⋅19⋅37 }[/math]	[math]\displaystyle{ 75361=11⋅13⋅17⋅31 }[/math]

Test Millera-Rabina

Rozpoczniemy od udowodnienia prostego twierdzenia

Twierdzenie K13
Jeśli [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ x^2 \equiv 1 \pmod m }[/math], to albo [math]\displaystyle{ x \equiv - 1 \pmod m }[/math], albo [math]\displaystyle{ x \equiv 1 \pmod m }[/math].

Dowód

Z założenia

[math]\displaystyle{ x^2 \equiv 1 \pmod m }[/math]

Zatem [math]\displaystyle{ m | (x^2 - 1) }[/math], czyli [math]\displaystyle{ m | (x - 1) (x + 1) }[/math]. Ponieważ z założenia [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą, to [math]\displaystyle{ m }[/math] dzieli dokładnie jedną z liczb [math]\displaystyle{ x - 1 }[/math] i [math]\displaystyle{ x + 1 }[/math]. Istotnie, gdyby [math]\displaystyle{ m | (x - 1) }[/math] [math]\displaystyle{ \text{i} \;\, m | (x + 1) }[/math], to [math]\displaystyle{ m }[/math] dzieliłaby również ich różnicę równą [math]\displaystyle{ 2 }[/math], co jest niemożliwe w przypadku gdy [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą.
□

Prace Gary'ego Millera^[4] i Michaela Rabina^[5] pozwoliły sformułować znacznie silniejszy test. Podstawą tego testu jest następujące twierdzenie

Twierdzenie K14
Jeżeli [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ m - 1 = 2^r d }[/math], gdzie [math]\displaystyle{ d }[/math] jest liczbą nieparzystą, to dla dowolnego [math]\displaystyle{ a \in [1, m - 1] }[/math] jest albo

[math]\displaystyle{ a^d \equiv 1 \pmod m }[/math]

albo

[math]\displaystyle{ a^{2^k d} \equiv - 1 \pmod m }[/math]

dla pewnego [math]\displaystyle{ k \in [0, r - 1] }[/math].

Dowód

Rozważmy ciąg [math]\displaystyle{ r + 1 }[/math] liczb zdefiniowanych następująco

[math]\displaystyle{ \begin{array}{l} u_0 = a^d\\ u_1 = a^{2 d} = (a^d)^2\\ u_2 = a^{2^2 d} = (a^{2 d})^2\\ \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots\\ u_{r - 1} = a^{2^{r - 1} d} = (a^{2^{r - 2}})^2\\ u_r = a^{2^r d} = (a^{2^{r - 1} d})^2 = a^{m - 1} \end{array} }[/math]

Wyrazy ciągu [math]\displaystyle{ (u_i) }[/math] są dane wzorem ogólnym

[math]\displaystyle{ u_i = a^{2^i d} }[/math]

gdzie [math]\displaystyle{ i = 0, 1, \ldots, r }[/math]

Zauważmy, że mogą zdarzyć się następujące sytuacje

a) żaden z wyrazów ciągu [math]\displaystyle{ (u_i) }[/math] nie przystaje do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math]

b) wszystkie wyrazy ciągu [math]\displaystyle{ (u_i) }[/math] przystają do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math]

c) [math]\displaystyle{ u_k }[/math] jest pierwszym wyrazem ciągu [math]\displaystyle{ (u_i) }[/math], który przystaje do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math]

Co możemy zapisać jako

a) [math]\displaystyle{ u_i \not\equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, r] }[/math]

b) [math]\displaystyle{ u_i \equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, r] }[/math]

c) [math]\displaystyle{ u_k \equiv 1 \pmod m \quad }[/math] dla pewnego [math]\displaystyle{ k \in [0, r] }[/math]

Z definicji każdy wyraz ciągu [math]\displaystyle{ (u_i) }[/math] jest kwadratem poprzedniego. W szczególności oznacza to, że jeżeli dla pewnego [math]\displaystyle{ k \in [0, r] }[/math] jest [math]\displaystyle{ u_k \equiv 1 \pmod m }[/math], to [math]\displaystyle{ u_i \equiv 1 \pmod m }[/math] dla wszystkich [math]\displaystyle{ i \geqslant k }[/math]. Ten fakt pozwala doprecyzować zapis poszczególnych przypadków.

a) [math]\displaystyle{ u_i \not\equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, r] }[/math]

b) [math]\displaystyle{ u_0 \equiv 1 \pmod m }[/math]

c) [math]\displaystyle{ u_0 \not\equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, k - 1] \quad }[/math] oraz [math]\displaystyle{ \quad u_k \equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [k, r] , \quad }[/math] gdzie [math]\displaystyle{ k \geqslant 1 }[/math]

W przypadku a) mamy [math]\displaystyle{ u_r = a^{m - 1} \not\equiv 1 \pmod m }[/math], zatem liczba [math]\displaystyle{ m }[/math] byłaby liczbą złożoną, wbrew założeniu, że jest liczbą pierwszą.

Przypadek b) jest możliwy (np. dla [math]\displaystyle{ m = 41 }[/math] i [math]\displaystyle{ a = 10 }[/math]), ale nie pozwala powiedzieć nic więcej ani o liczbie [math]\displaystyle{ m }[/math], ani o wyrazach ciągu [math]\displaystyle{ (u_i) }[/math], które wszystkie przystają do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math].

W przypadku c) mamy [math]\displaystyle{ u_k \equiv 1 \pmod m }[/math], czyli [math]\displaystyle{ (u_{k - 1})^2 \equiv 1 \pmod m }[/math]. Z twierdzenia K13 wiemy, że musi być albo [math]\displaystyle{ u_{k - 1} \equiv - 1 \pmod m }[/math], albo [math]\displaystyle{ u_{k - 1} \equiv 1 \pmod m }[/math]. Ale drugi przypadek nie może zachodzić, bo założyliśmy, że [math]\displaystyle{ u_k }[/math] jest pierwszym wyrazem ciągu [math]\displaystyle{ (u_i) }[/math], który przystaje do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math]. Zatem musi być [math]\displaystyle{ u_{k - 1} \equiv - 1 \pmod m }[/math].

Co kończy dowód twierdzenia.
□

Definicja K15
Złożoną liczbę nieparzystą [math]\displaystyle{ m }[/math], która spełnia twierdzenie K14 dla pewnej liczby [math]\displaystyle{ a \in \mathbb{Z} }[/math], będziemy nazywali liczbą silnie pseudopierwszą przy podstawie [math]\displaystyle{ a }[/math] (w skrócie: SPSP([math]\displaystyle{ a }[/math])).

Uwaga K16
Niech [math]\displaystyle{ a }[/math] będzie liczbą całkowitą względnie pierwszą z [math]\displaystyle{ m }[/math] i [math]\displaystyle{ a \in [1, m - 1] }[/math]. Można pokazać, że jeżeli [math]\displaystyle{ m \neq 9 }[/math] jest liczbą nieparzystą złożoną, to co najwyżej [math]\displaystyle{ \tfrac{1}{4} }[/math] liczb [math]\displaystyle{ a }[/math] stanowią liczby silnie pseudopierwsze. Zatem w przypadku liczb silnie pseudopierwszych nie istnieje odpowiednik liczb Carmichaela. Czyli nie istnieją liczby złożone nieparzyste [math]\displaystyle{ m }[/math], dla których twierdzenie K14 byłoby prawdziwe dla wszystkich podstaw [math]\displaystyle{ a }[/math].

Wynika stąd, że jeżeli dla [math]\displaystyle{ k }[/math] różnych liczb [math]\displaystyle{ a }[/math] prawdziwe jest twierdzenie K14, to prawdopodobieństwo uznania liczby złożonej [math]\displaystyle{ m }[/math] za pierwszą wynosi [math]\displaystyle{ \left( \tfrac{1}{4} \right)^k }[/math].

Uwaga K17
Wykorzystując twierdzenie K14, możemy napisać w PARI/GP prosty program do testowania pierwszości liczb.

MillerRabinTest(m, a)=
{
local(d, k, r, x);
if( m % 2 == 0, return(m == 2) );
r = valuation(m - 1, 2); \\ wykładnik, z jakim liczba 2 występuje w rozwinięciu na czynniki pierwsze liczby m - 1
d = (m - 1) / 2^r;
x = modPower(a, d, m);
if( x == 1 || x == m - 1, return(1) ); \\ x = m - 1 to przypadek k == 0
k = 0;
while( k++ < r,
       x = x^2 % m;
       if( x == m - 1, return(1) );
     );
return(0);
}

Zadanie K18
Pokazać, że jeżeli liczba [math]\displaystyle{ m }[/math] jest SPSP([math]\displaystyle{ a }[/math]), to jest FPSP([math]\displaystyle{ a }[/math]).

Rozwiązanie

Z założenia [math]\displaystyle{ m }[/math] jest SPSP([math]\displaystyle{ a }[/math]), zatem spełniony jest dokładnie jeden z warunków

[math]\displaystyle{ a^d \equiv 1 \pmod m }[/math]
[math]\displaystyle{ a^{2^k \cdot d} \equiv - 1 \pmod m }[/math], dla pewnego [math]\displaystyle{ k \in [0, r - 1] }[/math]

gdzie [math]\displaystyle{ m - 1 = 2^r \cdot d }[/math], przy czym [math]\displaystyle{ d }[/math] jest liczbą nieparzystą.

Jeżeli spełniony jest pierwszy warunek, to

[math]\displaystyle{ (a^d)^{2^r} \equiv 1 \pmod m }[/math]

[math]\displaystyle{ a^{2^r \cdot d} \equiv 1 \pmod m }[/math]

Czyli [math]\displaystyle{ m }[/math] jest FPSP([math]\displaystyle{ a }[/math]).

Jeżeli spełniony jest drugi warunek, to

[math]\displaystyle{ (a^{2^k \cdot d})^{2^{r - k}} \equiv (- 1)^{2^{r - k}} \pmod m }[/math]

[math]\displaystyle{ a^{2^r \cdot d} \equiv 1 \pmod m }[/math]

Czyli [math]\displaystyle{ m }[/math] jest FPSP([math]\displaystyle{ a }[/math]).
□

Przykład K19
Pokażemy, że jeżeli [math]\displaystyle{ m }[/math] jest FPSP([math]\displaystyle{ 2 }[/math]), to [math]\displaystyle{ 2^m - 1 }[/math] jest SPSP([math]\displaystyle{ 2 }[/math]).

Z założenia [math]\displaystyle{ m }[/math] jest złożoną liczbą nieparzystą, zatem [math]\displaystyle{ N = 2^m - 1 }[/math] jest złożoną liczbą nieparzystą. Ponieważ [math]\displaystyle{ m }[/math] jest FPSP([math]\displaystyle{ 2 }[/math]), to

[math]\displaystyle{ 2^{m - 1} \equiv 1 \pmod m }[/math]

Wynika stąd natychmiast, że [math]\displaystyle{ 2^{m - 1} - 1 = k m }[/math], gdzie [math]\displaystyle{ k }[/math] jest liczbą nieparzystą. Zatem

[math]\displaystyle{ N - 1 = 2^m - 2 = 2 (2^{m - 1} - 1) = 2 k m }[/math]

Widzimy, że liczba [math]\displaystyle{ 2 }[/math] występuje w pierwszej potędze w rozwinięciu liczby [math]\displaystyle{ N - 1 }[/math] na czynniki pierwsze i łatwo otrzymujemy, że

[math]\displaystyle{ 2^{(N - 1) / 2} = 2^{k m} = (2^m)^k = (2^m - 1 + 1)^k = (N + 1)^k \equiv 1 \pmod N }[/math]

Czyli [math]\displaystyle{ N = 2^m - 1 }[/math] jest SPSP([math]\displaystyle{ 2 }[/math]).

Przykład K20
Tabela zawiera najmniejsze liczby silnie pseudopierwsze dla podstaw [math]\displaystyle{ a }[/math] od [math]\displaystyle{ 2 }[/math] do [math]\displaystyle{ 15 }[/math]

for(a=2, 15, s=1; forstep(m=3, 20000, 2, if( MillerRabinTest(m, a)  &&  !isprime(m), print("a=", a, "  m=", m); s++ ); if( s>5, break() ) ))

[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]	[math]\displaystyle{ \boldsymbol{11} }[/math]	[math]\displaystyle{ \boldsymbol{12} }[/math]	[math]\displaystyle{ \boldsymbol{13} }[/math]	[math]\displaystyle{ \boldsymbol{14} }[/math]	[math]\displaystyle{ \boldsymbol{15} }[/math]
[math]\displaystyle{ 2047 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 781 }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 133 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 1687 }[/math]
[math]\displaystyle{ 3277 }[/math]	[math]\displaystyle{ 703 }[/math]	[math]\displaystyle{ 1387 }[/math]	[math]\displaystyle{ 1541 }[/math]	[math]\displaystyle{ 481 }[/math]	[math]\displaystyle{ 325 }[/math]	[math]\displaystyle{ 65 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 793 }[/math]	[math]\displaystyle{ 133 }[/math]	[math]\displaystyle{ 1099 }[/math]	[math]\displaystyle{ 841 }[/math]	[math]\displaystyle{ 3277 }[/math]
[math]\displaystyle{ 4033 }[/math]	[math]\displaystyle{ 1891 }[/math]	[math]\displaystyle{ 2047 }[/math]	[math]\displaystyle{ 5461 }[/math]	[math]\displaystyle{ 1111 }[/math]	[math]\displaystyle{ 703 }[/math]	[math]\displaystyle{ 481 }[/math]	[math]\displaystyle{ 671 }[/math]	[math]\displaystyle{ 1729 }[/math]	[math]\displaystyle{ 2047 }[/math]	[math]\displaystyle{ 145 }[/math]	[math]\displaystyle{ 5149 }[/math]	[math]\displaystyle{ 2743 }[/math]	[math]\displaystyle{ 6541 }[/math]
[math]\displaystyle{ 4681 }[/math]	[math]\displaystyle{ 3281 }[/math]	[math]\displaystyle{ 3277 }[/math]	[math]\displaystyle{ 5611 }[/math]	[math]\displaystyle{ 1261 }[/math]	[math]\displaystyle{ 2101 }[/math]	[math]\displaystyle{ 511 }[/math]	[math]\displaystyle{ 703 }[/math]	[math]\displaystyle{ 4187 }[/math]	[math]\displaystyle{ 4577 }[/math]	[math]\displaystyle{ 247 }[/math]	[math]\displaystyle{ 7107 }[/math]	[math]\displaystyle{ 3277 }[/math]	[math]\displaystyle{ 14041 }[/math]
[math]\displaystyle{ 8321 }[/math]	[math]\displaystyle{ 8401 }[/math]	[math]\displaystyle{ 4033 }[/math]	[math]\displaystyle{ 7813 }[/math]	[math]\displaystyle{ 2701 }[/math]	[math]\displaystyle{ 2353 }[/math]	[math]\displaystyle{ 1417 }[/math]	[math]\displaystyle{ 1541 }[/math]	[math]\displaystyle{ 6533 }[/math]	[math]\displaystyle{ 5041 }[/math]	[math]\displaystyle{ 1649 }[/math]	[math]\displaystyle{ 8911 }[/math]	[math]\displaystyle{ 5713 }[/math]	[math]\displaystyle{ 14701 }[/math]

Przykład K21
Tabela pokazuje ilość liczb silnie pseudopierwszych dla podstaw [math]\displaystyle{ a }[/math] od [math]\displaystyle{ 2 }[/math] do [math]\displaystyle{ 15 }[/math]

for(a=2, 15, s=0; forstep(k=3, 10^6, 2, if( MillerRabinTest(k, a)  &&  !isprime(k), s++ )); print("a= ", a, "   ", s))

[math]\displaystyle{ \boldsymbol{a} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]	[math]\displaystyle{ \boldsymbol{11} }[/math]	[math]\displaystyle{ \boldsymbol{12} }[/math]	[math]\displaystyle{ \boldsymbol{13} }[/math]	[math]\displaystyle{ \boldsymbol{14} }[/math]	[math]\displaystyle{ \boldsymbol{15} }[/math]
#SPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^6 }[/math]	[math]\displaystyle{ 46 }[/math]	[math]\displaystyle{ 73 }[/math]	[math]\displaystyle{ 97 }[/math]	[math]\displaystyle{ 64 }[/math]	[math]\displaystyle{ 73 }[/math]	[math]\displaystyle{ 66 }[/math]	[math]\displaystyle{ 127 }[/math]	[math]\displaystyle{ 161 }[/math]	[math]\displaystyle{ 62 }[/math]	[math]\displaystyle{ 58 }[/math]	[math]\displaystyle{ 90 }[/math]	[math]\displaystyle{ 71 }[/math]	[math]\displaystyle{ 74 }[/math]	[math]\displaystyle{ 45 }[/math]
#SPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^7 }[/math]	[math]\displaystyle{ 162 }[/math]	[math]\displaystyle{ 207 }[/math]	[math]\displaystyle{ 305 }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 203 }[/math]	[math]\displaystyle{ 177 }[/math]	[math]\displaystyle{ 377 }[/math]	[math]\displaystyle{ 459 }[/math]	[math]\displaystyle{ 158 }[/math]	[math]\displaystyle{ 157 }[/math]	[math]\displaystyle{ 251 }[/math]	[math]\displaystyle{ 193 }[/math]	[math]\displaystyle{ 190 }[/math]	[math]\displaystyle{ 148 }[/math]
#SPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^8 }[/math]	[math]\displaystyle{ 488 }[/math]	[math]\displaystyle{ 582 }[/math]	[math]\displaystyle{ 833 }[/math]	[math]\displaystyle{ 475 }[/math]	[math]\displaystyle{ 486 }[/math]	[math]\displaystyle{ 446 }[/math]	[math]\displaystyle{ 1023 }[/math]	[math]\displaystyle{ 1241 }[/math]	[math]\displaystyle{ 437 }[/math]	[math]\displaystyle{ 430 }[/math]	[math]\displaystyle{ 666 }[/math]	[math]\displaystyle{ 472 }[/math]	[math]\displaystyle{ 440 }[/math]	[math]\displaystyle{ 398 }[/math]
#SPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^9 }[/math]	[math]\displaystyle{ 1282 }[/math]	[math]\displaystyle{ 1514 }[/math]	[math]\displaystyle{ 2162 }[/math]	[math]\displaystyle{ 1268 }[/math]	[math]\displaystyle{ 1232 }[/math]	[math]\displaystyle{ 1163 }[/math]	[math]\displaystyle{ 2599 }[/math]	[math]\displaystyle{ 3210 }[/math]	[math]\displaystyle{ 1113 }[/math]	[math]\displaystyle{ 1125 }[/math]	[math]\displaystyle{ 1655 }[/math]	[math]\displaystyle{ 1142 }[/math]	[math]\displaystyle{ 1151 }[/math]	[math]\displaystyle{ 1041 }[/math]

Widzimy, że liczb silnie pseudopierwszych jest znacznie mniej niż liczb pseudopierwszych Fermata.

Uwaga K22
Interesujące i pożyteczne będzie zbadanie najmniejszych liczb silnie pseudopierwszych dla wielu podstaw. Niech badanymi podstawami będą kolejne liczby pierwsze. Najmniejszą liczbę SPSP([math]\displaystyle{ 2 }[/math]) już znamy: [math]\displaystyle{ 2047 }[/math]. Najmniejszą liczbę, która jest jednocześnie SPSP([math]\displaystyle{ 2 }[/math]) i SPSP([math]\displaystyle{ 3 }[/math]) musimy poszukać. Prostym poleceniem

forstep(m=3, 2*10^6, 2, if( MillerRabinTest(m, 2)  &&  MillerRabinTest(m, 3)  &&  !isprime(m), print("m=", m) ) )

znajdujemy, że [math]\displaystyle{ m = 1373653 }[/math]. Więcej czasu będzie wymagało znalezienie liczby jednocześnie silnie pseudopierwszej względem podstaw [math]\displaystyle{ 2, 3, 5 }[/math]. Poleceniem

forstep(m=3, 26*10^6, 2, if( MillerRabinTest(m, 2)  &&  MillerRabinTest(m, 3)  &&  MillerRabinTest(m, 5)  &&  !isprime(m), print("m=", m) ) )

znajdujemy, że szukana liczba to [math]\displaystyle{ m = 25326001 }[/math].

Stosując bardziej wyrafinowane metody^[6]^[7] znaleziono wartości liczb silnie pseudopierwszych względem wielu podstaw, które są kolejnymi liczbami pierwszymi, dla większej ilości liczb pierwszych^[8]. Dla przykładu

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ \boldsymbol{m} }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2047 }[/math]
[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 1373653 }[/math]
[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 25326001 }[/math]
[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 3215031751 }[/math]
[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 2152302898747 }[/math]
[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 3474749660383 }[/math]
[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 341550071728321 }[/math]

Podane w prawej kolumnie liczby [math]\displaystyle{ m }[/math] są najmniejszymi liczbami jednocześnie silnie pseudopierwszymi względem podstaw [math]\displaystyle{ p_1, \ldots, p_n }[/math]. Zauważmy, że wyniki te mają bardzo praktyczne zastosowanie. Przykładowo, jeśli [math]\displaystyle{ m }[/math] przechodzi test Millera-Rabina dla siedmiu podstaw [math]\displaystyle{ a = 2, 3, 5, 7, 11, 13, 17 }[/math] i jest liczbą mniejszą od [math]\displaystyle{ 3.41 \cdot 10^{14} }[/math], to jest z pewnością liczbą pierwszą.

Uzupełnienie

Uwaga K23
W funkcji MillerRabinTest() wykorzystaliśmy zaimplementowane w PARI/GP funkcje:

gcd(a, b) – znajduje największy wspólny dzielnik liczb a i b
valuation(a, b) – znajduje największą wartość liczby [math]\displaystyle{ r }[/math] taką, że [math]\displaystyle{ b^r | a }[/math]

Wprowadzenie tych funkcji pozwoliło zwiększyć czytelność kodu, ale bez trudu możemy sami je napisać:

gcd2(a, b) =
{
while( b <> 0, a = b; b = a % b );
return(a);
}

valuation2(a, b) =
{
local(s);
s = 0;
while(a % b == 0, s++; a = a / b);
return(s);
}

Przypisy

↑ W. R. Alford, Andrew Granville and Carl Pomerance, There are Infinitely Many Carmichael Numbers, Annals of Mathematics, 140, (1994), 703-722
↑ Glyn Harman, On the Number of Carmichael Numbers up to x, Bull. London Math. Soc. 37 (2005) 641–650
↑ Glyn Harman, Watt’s Mean Value Theorem and Carmichael Numbers, International Journal of Number Theory, Vol. 4, No. 2 (2008) 241–248
↑ Gary L. Miller, Riemann's Hypothesis and Tests for Primality, Journal of Computer and System Sciences 13, 300-317 (1976)
↑ Michael O. Rabin, Probabilistic Algorithm for Testing Primality, Journal of Number Theory 12, 128-138 (1980)
↑ Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., The Pseudoprimes to 25*10^9, Mathematics of Computation, Vol. 35, No. 151 (1980), 1003-1026
↑ Gerhard Jaeschke, On Strong Pseudoprimes to Several Bases, Mathematics of Computation, Vol. 61, No. 204 (Oct., 1993), 915-926
↑ On-Line Encyclopedia of Integer Sequences, Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness, (A014233)

[Carmichael1-1] W. R. Alford, Andrew Granville and Carl Pomerance, There are Infinitely Many Carmichael Numbers, Annals of Mathematics, 140, (1994), 703-722

[Carmichael2-2] Glyn Harman, On the Number of Carmichael Numbers up to x, Bull. London Math. Soc. 37 (2005) 641–650

[Carmichael3-3] Glyn Harman, Watt’s Mean Value Theorem and Carmichael Numbers, International Journal of Number Theory, Vol. 4, No. 2 (2008) 241–248

[Miller1-4] Gary L. Miller, Riemann's Hypothesis and Tests for Primality, Journal of Computer and System Sciences 13, 300-317 (1976)

[Rabin1-5] Michael O. Rabin, Probabilistic Algorithm for Testing Primality, Journal of Number Theory 12, 128-138 (1980)

[SPSPtoNbases-6] Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., The Pseudoprimes to 25*10^9, Mathematics of Computation, Vol. 35, No. 151 (1980), 1003-1026

[Jaeschke1-7] Gerhard Jaeschke, On Strong Pseudoprimes to Several Bases, Mathematics of Computation, Vol. 61, No. 204 (Oct., 1993), 915-926

[A014233-8] On-Line Encyclopedia of Integer Sequences, Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness, (A014233)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze

Spis treści

Twierdzenie Fermata

Potęgowanie modulo

Liczby pseudopierwsze Fermata

Test Millera-Rabina

Uzupełnienie

Przypisy

Menu nawigacyjne

Szukaj