Różnica pomiędzy stronami "Protokół Diffiego-Hellmana. Szyfrowanie RSA. Podpis cyfrowy" i "Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze"

Aktualna wersja na dzień 18:49, 17 mar 2024

11.11.2022

Potęgowanie modulo

Uwaga M1
Z twierdzenia Fermata (zobacz J22) 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 \mid (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].

Uwaga M2
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);
}

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

Zauważmy jeszcze, że PARI/GP umożliwia szybkie potęgowanie modulo i nie musimy korzystać z funkcji modPower(). Wystarczy napisać

lift( Mod(a, m)^d )

Co ważniejsze, powyższe polecenie jest wykonywane znacznie szybciej niż nasza funkcja modPower(). Podaliśmy kod funkcji dlatego, że jest ona bardzo ważna i Czytelnik powinien wiedzieć, jak jest w praktyce realizowana.

Uwaga M3
Wykorzystując wzór rekurencyjny

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

możemy napisać w PARI/GP prosty program do mnożenia modulo:

modMult(a, b, m) = 
\\ a, b - czynniki, m - moduł
{
local(w);
if( m == 1, return(0) );
a = a % m;
b = b % m;
w = 0;
while( b > 0,
       if( b % 2 == 1, w = (w + a) % m; b = b - 1 );  \\ gdy b jest nieparzysty, wydzielamy a i zmniejszamy b o jeden
       a = (2 * a) % m;  \\ wyliczamy nowy czynnik a modulo m
       b = b / 2;  \\ dla nowego czynnika a czynnik b jest dwa razy mniejszy
     );
return(w);
}

Czytelnik może zapytać, po co nam program do obliczania iloczynu modulo. Istotnie, jeśli piszemy programy w PARI/GP, to liczby całkowite mogą być ogromne i nie mamy powodu do zmartwienia (między innymi dlatego podajemy przykłady programów w PARI/GP). Jeżeli jednak będziemy potrzebowali napisać program w innym języku – powiedzmy w C – to ten problem stanie się nagle bardzo ważny. W C możemy przeprowadzać obliczenia dla bardzo dużych liczb całkowitych. Zmienne całkowite zadeklarowane jako uint32_t mogą przyjmować wartości z przedziału [math]\displaystyle{ [0, 2^{32} - 1] }[/math], a zmienne całkowite zadeklarowane jako uint64_t mogą przyjmować wartości z przedziału [math]\displaystyle{ [0, 2^{64} - 1] }[/math]. Liczba [math]\displaystyle{ 2^{64} \approx 1.84 \cdot 10^{19} }[/math] jest na tyle duża, że możemy wiele problemów liczyć, pisząc programy w C, co zapewnia większą szybkość obliczeń. W takich przypadkach funkcja modMult() może być bardzo użyteczna.

Zauważmy, że wykonując potęgowanie modulo, obliczamy iloczyny (w * a) % m i (a * a) % m. Jeżeli [math]\displaystyle{ m \lt 2^{32} }[/math], to nie napotkamy problemu: obydwa iloczyny są mniejsze od [math]\displaystyle{ 2^{64} }[/math] i będziemy mogli je wyliczyć. Ale w przypadku większych modułów już tak nie będzie i jeżeli chcemy zwiększyć zakres obliczeń, to musimy mnożenie wykonywać przy użyciu funkcji modMult(). Wystarczy założenie, że moduł [math]\displaystyle{ m \lt 2^{63} }[/math], aby suma (w + a) % m i iloczyn (2 * a) % m mogły zostać wyliczone.

Liczby pseudopierwsze Fermata

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

Definicja M4
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 PSP([math]\displaystyle{ a }[/math]).

Uwaga M5
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 \mid 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 PSP([math]\displaystyle{ a }[/math]).

Twierdzenie M6
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 \mid a^p - 1 }[/math] oraz [math]\displaystyle{ a + 1 \mid 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) \mid (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 \mid (m - 1) }[/math] i [math]\displaystyle{ p \mid (m - 1) }[/math], zatem [math]\displaystyle{ 2 p \mid (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ą PSP([math]\displaystyle{ a }[/math]). Co należało pokazać.
□

Przykład M7
Z dowodu twierdzenia M6 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 PSP([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 M8
Wykorzystując funkcję potęgowania modulo, możemy napisać prosty program do testowania pierwszości liczb w oparciu o twierdzenie Fermata.

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

Przykład M9
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( isPrimeOrPSP(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 M10
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( isPrimeOrPSP(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]
#PSP([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]
#PSP([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]
#PSP([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]
#PSP([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 M11
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 M12
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 M13
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 \mid (x^2 - 1) }[/math], czyli [math]\displaystyle{ m \mid (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 \mid (x - 1) }[/math] [math]\displaystyle{ \text{i} \;\, m \mid (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 M14
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_i \not\equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, k - 1] \quad }[/math] oraz [math]\displaystyle{ \quad u_i \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 M13 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 M15
Złożoną liczbę nieparzystą [math]\displaystyle{ m }[/math], która spełnia twierdzenie M14 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 M16
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 M14 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] względnie pierwszych z [math]\displaystyle{ m }[/math] prawdziwe jest twierdzenie M14, 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 M17
Wykorzystując twierdzenie M14, możemy napisać w PARI/GP program wykonujący test Millera-Rabina dla ustalonej podstawy.

isPrimeOrSPSP(m, a) =
{
local(d, k, r, x);
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);
}

Zauważmy, że nie musimy sprawdzać, czy [math]\displaystyle{ \gcd (a, m) = 1 }[/math], bo jeśli tak nie jest, to dla takiej podstawy powyższy test i tak wykryje złożoność liczby [math]\displaystyle{ m }[/math]. Istotnie, jeżeli [math]\displaystyle{ \gcd (a, m) = g \gt 1 }[/math], to rozważając kongruencje z twierdzenia M14

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

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

modulo [math]\displaystyle{ g }[/math], otrzymujemy natychmiast

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

[math]\displaystyle{ 0 \equiv - 1 \!\! \pmod{g} }[/math]

Co jest niemożliwe. Jednak sprawdzenie, czy [math]\displaystyle{ \gcd (a, m) = 1 }[/math] jest wskazane, bo operacja ta jest wykonywana bardzo szybko. A jeśli mieliśmy tyle szczęścia, że [math]\displaystyle{ \gcd (a, m) = g \gt 1 }[/math], to jednocześnie znaleźliśmy dzielnik testowanej liczby [math]\displaystyle{ m }[/math], co w przypadku dużych liczb nie jest rzeczą prostą. Zatem program wykonujący [math]\displaystyle{ k }[/math] testów Millera-Rabina dla przypadkowych podstaw [math]\displaystyle{ a }[/math], gdzie [math]\displaystyle{ a \in [2, m - 2] }[/math], powinien wyglądać tak

PrimeTest(m, k) = 
{
local(a, d, j);
if( m < 2, return(0) );
if( m % 2 == 0, return(m == 2) );  \\ testowana liczba jest liczbą parzystą
setrand(getwalltime());  \\ ustawiamy ziarno (ang. seed) generatora liczb losowych
j = 0;
while( j++ <= k,
       a = random([2, m - 2]);  \\ a jest liczbą losową z przedziału domkniętego [2, m-2]
       d = gcd(a, m);
       if( d > 1, return(0) );  \\ testowana liczba jest liczbą złożoną podzielną przez d
       if( !isPrimeOrSPSP(m, a), return(0) );  \\ testowana liczba jest liczbą złożoną
     );
return(1);  \\ testowana liczba jest prawdopodobnie liczbą pierwszą
}

Testując dla pięciu przypadkowych podstaw, trudno znaleźć liczbę, dla której wartość funkcji PrimeTest() byłaby różna od isprime(). Nam się to nie udało.

forstep(j = 10^6+1, 10^7, 2, if( PrimeTest(j, 5) != isprime(j), print(j) ))

Zadanie M18
Pokazać, że jeżeli liczba [math]\displaystyle{ m }[/math] jest SPSP([math]\displaystyle{ a }[/math]), to jest PSP([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 PSP([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 PSP([math]\displaystyle{ a }[/math]).
□

Przykład M19
Pokażemy, że jeżeli [math]\displaystyle{ m }[/math] jest PSP([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 M20
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( isPrimeOrSPSP(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 M21
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( isPrimeOrSPSP(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 M22
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, 10^7, 2, if( isprime(m), next() ); if( isPrimeOrSPSP(m, 2) && isPrimeOrSPSP(m, 3), 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, 10^8, 2, if( isprime(m), next() ); if( isPrimeOrSPSP(m, 2) && isPrimeOrSPSP(m, 3) && isPrimeOrSPSP(m, 5), 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ą.

Uwaga M23
Pomysł przedstawiony w uwadze M22 ma proste uogólnienie. Niech [math]\displaystyle{ A_r = \{ a_1, \ldots, a_r \} }[/math] będzie zbiorem liczb naturalnych większych od [math]\displaystyle{ 1 }[/math]. Możemy teraz szukać takiego zbioru [math]\displaystyle{ A_r }[/math], dla którego najmniejsza liczba silnie pseudopierwsza jednocześnie względem podstaw [math]\displaystyle{ a_1, \ldots, a_r }[/math] będzie największa ze wszystkich rozpatrywanych przypadków.

Dla przykładu przyjmijmy, że

[math]\displaystyle{ r = 3 }[/math]
[math]\displaystyle{ a_k \lt 100 }[/math]
[math]\displaystyle{ a_k }[/math] są liczbami pierwszymi

Okazuje się^[7]^[9], że przy takich założeniach szukanym zbiorem jest [math]\displaystyle{ A_3 = \{ 2, 7, 61 \} }[/math]. Najmniejszą liczbą silnie pseudopierwszą jednocześnie względem podstaw [math]\displaystyle{ 2, 7, 61 }[/math] jest liczba [math]\displaystyle{ 4759123141 }[/math]. Łatwo znajdujemy, że dla [math]\displaystyle{ m \lt 3 \cdot 10^{10} }[/math] istnieje osiem liczb silnie pseudopierwszych jednocześnie względem podstaw [math]\displaystyle{ 2, 7, 61 }[/math]:

[math]\displaystyle{ 4759123141, 8411807377, 11207066041, 11711154457, 12015212653, 18074903681, 19632812033, 27913980641 }[/math]

Korzystając z tego rezultatu możemy napisać prosty program, który rozstrzyga w sposób pewny, czy badana liczba [math]\displaystyle{ m \lt 1.12 \cdot 10^{10} }[/math] jest liczbą pierwszą.

Ponieważ teraz podstawy [math]\displaystyle{ a }[/math] są ustalone, a testowana liczba [math]\displaystyle{ m }[/math] może być dowolna, to musimy wykluczyć sytuacje, że [math]\displaystyle{ \gcd (a, m) \gt 1 }[/math]. Musimy tak zrobić, bo pierwszość liczby [math]\displaystyle{ m }[/math] nie zostanie wykryta, gdy [math]\displaystyle{ \gcd (a, m) = g \gt 1 }[/math] (zobacz M17).

Jeżeli podstawa [math]\displaystyle{ a }[/math] jest liczbą pierwszą, to wystarczy zbadać, czy [math]\displaystyle{ R_a (m) = 0 }[/math]. Jeśli tak, to tylko w przypadku, gdy [math]\displaystyle{ m = a }[/math] liczba [math]\displaystyle{ m }[/math] jest liczbą pierwszą.

Jeżeli podstawa [math]\displaystyle{ a }[/math] jest liczbą złożoną, powiedzmy [math]\displaystyle{ a = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math], to wystarczy zbadać, czy dla pewnego [math]\displaystyle{ i = 1, \ldots, s }[/math] jest [math]\displaystyle{ R_{p_i} (m) = 0 }[/math]. Jeśli tak, to tylko w przypadku, gdy [math]\displaystyle{ m = p_i }[/math] liczba [math]\displaystyle{ m }[/math] jest liczbą pierwszą.

Poniżej przedstawiamy odpowiedni kod w PARI/GP. Zauważmy, że wstępne sprawdzanie pierwszości nieprzypadkowo uwzględnia wszystkie liczby pierwsze [math]\displaystyle{ p \leqslant 61 }[/math]. Wybraliśmy taki zakres, aby zostały objęte podstawy [math]\displaystyle{ 2, 7, 61 }[/math].

MyIsPrime(m) = 
{
if( m < 2, return(0) );
forprime(p = 2, 61, if( m % p == 0, return(m == p) ));
if( m == 4759123141 || m == 8411807377, return(0) );
return( isPrimeOrSPSP(m, 2) && isPrimeOrSPSP(m, 7) && isPrimeOrSPSP(m, 61) );
}

Uzupełnienie

Uwaga M24
W funkcji isPrimeOrSPSP() 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 \mid a }[/math]

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

gcd2(a, b) =
{
local(r);
if( b == 0, return(abs(a)) );
r = a % b;
while( r > 0, a = b; b = r; r = a % b );
return(abs(b));
}

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
↑ ^7,0 ^7,1 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)
↑ Wikipedia, Test Millera-Rabina, (Wiki-pl), (Wiki-en)

[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] 7,0 ^7,1 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)

[MillerRabin1-9] Wikipedia, Test Millera-Rabina, (Wiki-pl), (Wiki-en)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Różnica pomiędzy stronami "Protokół Diffiego-Hellmana. Szyfrowanie RSA. Podpis cyfrowy" i "Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze"

Aktualna wersja na dzień 18:49, 17 mar 2024

Spis treści

Potęgowanie modulo

Liczby pseudopierwsze Fermata

Test Millera-Rabina

Uzupełnienie

Przypisy

Menu nawigacyjne

Szukaj

@@ Linia 1: / Linia 1: @@
-<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">22.11.2023</div>
+<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">11.11.2022</div>
 __FORCETOC__
@@ Linia 5: / Linia 5: @@
-== Protokół Diffiego-Hellmana ==
+== Potęgowanie modulo ==
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q1</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga M1</span><br/>
-Metoda ta została opracowana przez W. Diffiego i&nbsp;M. Hellmana<ref name="DiffieHellman1"/><ref name="DiffieHellman2"/> w 1976 roku. Opisana niżej procedura nie jest metodą szyfrowania i&nbsp;z&nbsp;założenia jej cel jest zupełnie inny. Umożliwia ona osobom mogącym kontaktować się ze sobą jedynie przez niezabezpieczone przed podsłuchem środki łączności ustalenie (tajnej) liczby, zwanej kluczem. Dysponując wspólną liczbą-kluczem osoby te mogą kodować i&nbsp;odczytywać wiadomości wybraną metodą szyfrowania. Przedstawimy w&nbsp;punktach procedurę postępowania wraz z&nbsp;przykładowymi danymi.
+Z twierdzenia Fermata (zobacz J22) wynika, że jeżeli liczby <math>a</math> i <math>m</math> są względnie pierwsze oraz <math>m</math> nie dzieli liczby <math>a^{m - 1} - 1</math>, to <math>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>341 = 11 \cdot 31</math>, ale <math>341 \mid (2^{340} - 1)</math>, bo
-::1. Agencja i&nbsp;Bolek wybierają (jawną) liczbę pierwszą <math>p = 541</math> i (jawną) liczbę <math>g = 2</math><ref name="generator1"/>
+::<math>2^{340} - 1 = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115775</math>
-::2. Agencja ustala (tajny, znany tylko sobie) wykładnik <math>a = 2718</math>
+::::<math>\;\;\; = 341 \cdot 6568166399348399444449977362370804334667582103327417990909058947107894050381703652143335757394742275</math>
-::3. Bolek ustala (tajny, znany tylko sobie) wykładnik <math>b = 3141</math>
+Widzimy, że nawet dla niewielkiej liczby <math>341</math>, potęga <math>2^{340} - 1</math> jest liczbą ogromną. Jeśli ta metoda ma mieć jakiekolwiek zastosowanie, to musimy znaleźć inny sposób obliczania reszty z&nbsp;dzielenia <math>a^n</math> przez <math>m</math>, czyli potęgowania modulo <math>m</math>.
-::4. Agencja oblicza (jawną) liczbę <math>X = R_p (g^a) = 300</math> i&nbsp;wysyła ją do Bolka
-::5. Bolek oblicza (jawną) liczbę <math>Y = R_p (g^b) = 191</math> i&nbsp;wysyła ją do Agencji
-::6. Agencja oblicza (tajną) liczbę <math>k_A = R_p (Y^a) = 493</math>
+<span style="font-size: 110%; font-weight: bold;">Uwaga M2</span><br/>
+Wykorzystując wzór rekurencyjny
-::7. Bolek oblicza (tajną) liczbę <math>k_B = R_p (X^b) = 493</math>
+::<math>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>
-::8. Modulo <math>p</math> mamy
-::::<math>k_A = R_p (Y^a) \equiv Y^a = [R_p (g^b)]^a \equiv (g^b)^a \equiv g^{a b} \equiv (g^a)^b \equiv [R_p (g^a)]^b = X^b \equiv R_p (X^b) = k_B \!\! \pmod{p}</math>
+możemy napisać w&nbsp;PARI/GP prosty program do potęgowania modulo:
-::9. Z&nbsp;definicji liczby <math>k_A, k_B \in [0, p - 1]</math>, zatem <math>0 \leqslant | k_A - k_B | \leqslant p - 1</math>. Ponieważ liczby <math>k_A, k_B</math> przystają do siebie modulo <math>p</math>, to muszą być sobie równe, czyli liczba <math>k = k_A = k_B</math> jest poszukiwanym kluczem.
+ <span style="font-size: 90%; color:black;">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);
+ }</span>
+Czytelnik łatwo sprawdzi, że w&nbsp;funkcji <code>modPower()</code> nie występują wyrażenia o&nbsp;wartości większej od <math>m^2</math>.
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q2</span><br/>
+Zauważmy jeszcze, że PARI/GP umożliwia szybkie potęgowanie modulo i nie musimy korzystać z funkcji <code>modPower()</code>. Wystarczy napisać
-Liczby <math>a</math> i <math>b</math> mogą być losowo wybranymi liczbami dodatnimi nie większymi od <math>p</math>. Istotnie, jeżeli <math>a = k \cdot (p - 1) + r</math>, to
-::<math>g^a \equiv (g^{p - 1})^k \cdot g^r \equiv g^r \!\! \pmod{p}</math>
+ <span style="font-size: 90%; color:black;">'''lift'''( '''Mod'''(a, m)^d )</span>
-W naszym przykładzie możemy użyć liczb <math>a = 18</math> oraz <math>b = 441</math> otrzymując te same rezultaty. W&nbsp;praktyce ten problem nie występuje, bo gdy liczba pierwsza <math>p</math> ma co najmniej sto cyfr, to trudno wybrać jeszcze większy wykładnik.
+Co ważniejsze, powyższe polecenie jest wykonywane znacznie szybciej niż nasza funkcja <code>modPower()</code>. Podaliśmy kod funkcji dlatego, że jest ona bardzo ważna i Czytelnik powinien wiedzieć, jak jest w praktyce realizowana.
-<span style="font-size: 110%; font-weight: bold;">Przykład Q3</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga M3</span><br/>
-Zobaczmy, jak wpłynie na protokół zmiana liczby <math>g</math>. Niech <math>p = 541</math> i <math>g = 15</math>.
+Wykorzystując wzór rekurencyjny
+::<math>a \cdot b = \left\{ \begin{array}{cll}
+  a &  & \text{gdy } b = 1 \\
+a \cdot \frac{b}{2} &  & \text{gdy } b \text{ jest parzyste} \\
+  a + 2 a \cdot \frac{b - 1}{2} &  & \text{gdy } b \text{ jest nieparzyste} \\
+\end{array} \right.</math>
+możemy napisać w PARI/GP prosty program do mnożenia modulo:
+ <span style="font-size: 90%; color:black;">modMult(a, b, m) =
+ \\ a, b - czynniki, m - moduł
+ {
+ '''local'''(w);
+ '''if'''( m == 1, '''return'''(0) );
+ a = a % m;
+ b = b % m;
+ w = 0;
+ '''while'''( b > 0,
+        '''if'''( b % 2 == 1, w = (w + a) % m; b = b - 1 );  \\ gdy b jest nieparzysty, wydzielamy a i zmniejszamy b o jeden
+        a = (2 * a) % m;  \\ wyliczamy nowy czynnik a modulo m
+        b = b / 2;  \\ dla nowego czynnika a czynnik b jest dwa razy mniejszy
+      );
+ '''return'''(w);
+ }</span>
+Czytelnik może zapytać, po co nam program do obliczania iloczynu modulo. Istotnie, jeśli piszemy programy w PARI/GP, to liczby całkowite mogą być ogromne i&nbsp;nie mamy powodu do zmartwienia (między innymi dlatego podajemy przykłady programów w PARI/GP). Jeżeli jednak będziemy potrzebowali napisać program w&nbsp;innym języku – powiedzmy w C – to ten problem stanie się nagle bardzo ważny. W C możemy przeprowadzać obliczenia dla bardzo dużych liczb całkowitych. Zmienne całkowite zadeklarowane jako <code>uint32_t</code> mogą przyjmować wartości z przedziału <math>[0, 2^{32} - 1]</math>, a zmienne całkowite zadeklarowane jako <code>uint64_t</code> mogą przyjmować wartości z przedziału <math>[0, 2^{64} - 1]</math>. Liczba <math>2^{64} \approx 1.84 \cdot 10^{19}</math> jest na tyle duża, że możemy wiele problemów liczyć, pisząc programy w C, co zapewnia większą szybkość obliczeń. W takich przypadkach funkcja <code>modMult()</code> może być bardzo użyteczna.
+Zauważmy, że wykonując potęgowanie modulo, obliczamy iloczyny <code>(w * a) % m</code> i <code>(a * a) % m</code>. Jeżeli <math>m < 2^{32}</math>, to nie napotkamy problemu: obydwa iloczyny są mniejsze od <math>2^{64}</math> i będziemy mogli je wyliczyć. Ale w przypadku większych modułów już tak nie będzie i jeżeli chcemy zwiększyć zakres obliczeń, to musimy mnożenie wykonywać przy użyciu funkcji <code>modMult()</code>. Wystarczy założenie, że moduł <math>m < 2^{63}</math>, aby suma <code>(w + a) % m</code> i iloczyn <code>(2 * a) % m</code> mogły zostać wyliczone.
-::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
-|-
-! <math>\boldsymbol{a}</math> || <math>\boldsymbol{b}</math> || <math>\boldsymbol{R_p(g^a)}</math> || <math>\boldsymbol{R_p(g^b)}</math> || <math>\boldsymbol{R_p(g^{a b})}</math>
-|-
-| <math>2985</math> || <math>4683</math> || <math>411</math> || <math>129</math> || <math>1</math>
-|-
-| <math>4270</math> || <math>8998</math> || <math>312</math> || <math>214</math> || <math>15</math>
-|-
-| <math>9749</math> || <math>3921</math> || <math>225</math> || <math>411</math> || <math>129</math>
-|-
-| <math>8993</math> || <math>6479</math> || <math>225</math> || <math>505</math> || <math>214</math>
-|-
-| <math>2146</math> || <math>8663</math> || <math>312</math> || <math>352</math> || <math>225</math>
-|-
-| <math>9941</math> || <math>6182</math> || <math>352</math> || <math>505</math> || <math>312</math>
-|-
-| <math>8944</math> || <math>8120</math> || <math>214</math> || <math>225</math> || <math>352</math>
-|-
-| <math>2928</math> || <math>9314</math> || <math>129</math> || <math>505</math> || <math>411</math>
-|-
-| <math>7436</math> || <math>3172</math> || <math>225</math> || <math>312</math> || <math>505</math>
-|}
-Czytelnik może wybierać dowolne inne wykładniki <math>a</math> i <math>b</math>, ale innych wartości <math>R_p (g^{a b})</math> już nie uzyska. Wybór liczby <math>g = 2</math> w&nbsp;zamieszczonym powyżej opisie metody, nie był przypadkowy. Liczba <math>2</math> jest generatorem modulo <math>541</math>. Generator modulo liczba pierwsza <math>p</math>, to taka liczba <math>g</math>, że zbiór potęg
-::<math>\{ g^1, g^2, g^3, \ldots, g^{p - 1} \}</math>
-rozpatrywany modulo <math>p</math> jest identyczny ze zbiorem
-::<math>\{ 1, 2, 3, \ldots, p - 1 \}</math>
+== Liczby pseudopierwsze Fermata ==
-Wybierając liczbę <math>g</math> tak, aby była generatorem modulo <math>p</math>, zapewniamy sobie, że w&nbsp;ostatniej kolumnie mogą pojawić się wszystkie liczby od <math>1</math> do <math>p - 1</math>. Taki wybór <math>g</math> zwiększa ilość możliwych wartości dla ustalanego klucza <math>k = R_p (g^{a b})</math>, a&nbsp;tym samym zwiększa bezpieczeństwo procedury. Zauważmy, że liczby <math>p</math> i <math>g</math> są jawne. Osoba próbująca poznać ustalony klucz <math>k</math> z&nbsp;pewnością ucieszy się, gdy sprawdzi, że niewłaściwy wybór liczby <math>g</math> zredukował ilość możliwych kluczy i&nbsp;ułatwił jej pracę.
+Liczby złożone nieparzyste spełniające równanie Fermata, otrzymały własną nazwę.
-Każda liczba pierwsza ma generator modulo, ale znalezienie go dla dużych liczb pierwszych nie jest proste i&nbsp;może trwać bardzo długo. Pomocne w&nbsp;tej sytuacji jest następujące twierdzenie.
+<span style="font-size: 110%; font-weight: bold;">Definicja M4</span><br/>
+Jeżeli <math>m</math> jest liczbą złożoną nieparzystą i&nbsp;dla pewnego <math>a \in \mathbb{Z}</math> prawdziwa jest kongruencja
+::<math>a^{m - 1} \equiv 1 \pmod m</math>
+to powiemy, że <math>m</math> jest liczbą pseudopierwszą Fermata przy podstawie <math>a</math> lub krótko: <math>m</math> jest PSP(<math>a</math>).
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie Q4</span><br/>
-Niech <math>p = 2 q + 1</math> będzie liczbą pierwszą, gdzie <math>q \geqslant 3</math> jest również liczbą pierwszą. Jeżeli <math>g</math> jest liczbą niekwadratową modulo <math>p</math> i <math>g \not\equiv - 1 \!\! \pmod{p}</math>, to <math>g</math> jest generatorem modulo <math>p</math>.
-{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
-Dowód jest na tyle prosty i&nbsp;elegancki, że postanowiliśmy go zamieścić, choć wykracza on poza omówiony wcześniej materiał. Czytelnik może ten dowód pominąć. Dowód poprzedzamy kilkoma prostymi, ale istotnymi komentarzami.
-'''Komentarz 1.'''
+<span style="font-size: 110%; font-weight: bold;">Uwaga M5</span><br/>
+Zauważmy, że w&nbsp;definicji liczb pseudopierwszych Fermata nie musimy dodatkowo dołączać warunku <math>\gcd (a, m) = 1</math>, bo wynika on z&nbsp;przyjętej definicji. Mamy
-'''Bez dowodu''' przyjmujemy fakt, że istnieje dokładnie <math>\varphi (p - 1)</math> różnych generatorów modulo <math>p</math>, gdzie <math>\varphi</math> jest funkcją Eulera<ref name="funkcjaphi1"/>. Funkcja Eulera <math>\varphi (n)</math> jest równa ilości liczb całkowitych dodatnich nie większych od <math>n</math> i&nbsp;względnie pierwszych z <math>n</math>.
+::<math>\gcd (a^{m - 1}, m) = \gcd (1, m) = 1</math>
-'''Komentarz 2.'''
+Zatem <math>\gcd (a, m) = 1</math>.
-Udowodnimy, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.
+Możemy też łatwo pokazać, że jeżeli <math>\gcd (a, m) = d > 1</math>, to liczba <math>m</math> nie może być liczbą pseudopierwszą Fermata przy podstawie <math>a</math>. Istotnie, gdyby tak było, to mielibyśmy
-Przypuśćmy, że <math>g</math> jest liczbą kwadratową modulo <math>p</math>, zatem (zobacz J31)
+::<math>a^{m - 1} \equiv 1 \pmod{m}</math>
-::<math>g^{(p - 1) / 2} \equiv 1 \!\! \pmod{p}</math>
+Ponieważ <math>d \mid m</math>, to jest również
-Wynika stąd, że zbiór
+::<math>a^{m - 1} \equiv 1 \pmod{d}</math>
-::<math>S = \{ g^1, g^2, g^3, \ldots, g^{p - 1} \}</math>
+Ale modulo <math>d</math> otrzymujemy natychmiast
-::<math>\;\;\,\, = \left\{ g^1, g^2, g^3, \ldots, g^{\tfrac{p - 1}{2} - 3}, g^{\tfrac{p - 1}{2} - 2}, g^{\tfrac{p - 1}{2} - 1}, g^{\tfrac{p - 1}{2}}, g^{\tfrac{p - 1}{2} + 1}, g^{\tfrac{p - 1}{2} + 2}, g^{\tfrac{p - 1}{2} + 3}, \ldots, g^{p - 3}, g^{p - 2}, g^{p - 1} \right\}</math>
+::<math>0 \equiv 1 \pmod{d}</math>
-jest identyczny modulo <math>p</math> ze zbiorem
+Co jest niemożliwe, czyli <math>m</math> nie jest PSP(<math>a</math>).
-::<math>S' = \left\{ g^1, g^2, g^3, \ldots, g^{\tfrac{p - 1}{2} - 3}, g^{\tfrac{p - 1}{2} - 2}, g^{\tfrac{p - 1}{2} - 1}, 1, g^1, g^2, g^3, \ldots, g^{\tfrac{p - 1}{2} - 3}, g^{\tfrac{p - 1}{2} - 2}, g^{\tfrac{p - 1}{2} - 1} \right\}</math>
-::<math>\quad \, = \left\{ 1, g^1, g^2, g^3, \ldots, g^{\tfrac{p - 1}{2} - 3}, g^{\tfrac{p - 1}{2} - 2}, g^{\tfrac{p - 1}{2} - 1} \right\}</math>
-i nie może być identyczny modulo <math>p</math> ze zbiorem <math>T = \{ 1, 2, 3, \ldots, p - 1 \}</math>, bo <math>S'</math> zawiera co najwyżej połowę elementów zbioru <math>T</math>. Uzyskana sprzeczność dowodzi, że generator musi być liczbą niekwadratową modulo <math>p</math>.
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie M6</span><br/>
+Dla każdej podstawy <math>a \geqslant 2</math> istnieje nieskończenie wiele liczb pseudopierwszych Fermata.
-'''Komentarz 3.'''
+{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+Niech <math>a \in \mathbb{Z}</math> i <math>a \geqslant 2</math>. Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to
-Ponieważ funkcja Eulera <math>\varphi (n)</math> jest równa ilości liczb całkowitych dodatnich nie większych od <math>n</math> i&nbsp;względnie pierwszych z <math>n</math>, to dla liczby pierwszej <math>p</math> mamy <math>\varphi (p) = p - 1</math>, bo wszystkie liczby <math>1, 2, 3, \ldots, p - 1</math> są względnie pierwsze z&nbsp;liczbą pierwszą <math>p</math>.
+::<math>a^p - 1 = (a - 1) (a^{p - 1} + a^{p - 2} + \ldots + a^2 + a + 1)</math>
-'''Komentarz 4.'''
+oraz
-Ponieważ funkcja Eulera <math>\varphi (n)</math> jest równa ilości liczb całkowitych dodatnich nie większych od <math>n</math> i&nbsp;względnie pierwszych z
+::<math>a^p + 1 = (a + 1) (a^{p - 1} - a^{p - 2} + \ldots + a^2 - a + 1)</math>
-<math>n</math>, to dla liczby pierwszej nieparzystej <math>p</math> mamy <math>\varphi (2 p) = p - 1</math>, bo
-:* wszystkie liczby parzyste <math>2, 4, 6, \ldots, 2 p - 2</math> mają z&nbsp;liczbą <math>2 p</math> wspólny dzielnik równy <math>2</math> i&nbsp;nie mogą być względnie pierwsze z&nbsp;liczbą <math>2 p</math>
+Czyli <math>a - 1 \mid a^p - 1</math> oraz <math>a + 1 \mid a^p + 1</math>.
-:* wszystkie liczby nieparzyste <math>1, 3, 5, \ldots, 2 p - 1</math> (których jest <math>p</math>) są względnie pierwsze z&nbsp;liczbą <math>2 p</math>, poza liczbą nieparzystą <math>p</math>, która nie jest względnie pierwsza z&nbsp;liczbą <math>2 p</math>
-Wracając do dowodu twierdzenia Q4, zauważmy, że liczba <math>- 1</math> jest liczbą niekwadratową modulo <math>p = 2 q + 1</math>. Istotnie, obliczając symbol Jacobiego, otrzymujemy
+Jeżeli przez <math>R_2 (a)</math> oznaczymy resztę z&nbsp;dzielenia liczby <math>a</math> przez <math>2</math> równą <math>0</math> lub <math>1</math>, to prawdziwe są kongruencje
-::<math>\left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} = (- 1)^{\tfrac{p - 1}{2}} = (- 1)^q = - 1</math>
+::<math>a \equiv R_2 (a) \pmod 2</math>
-Zauważmy też, że dla liczb pierwszych <math>p \geqslant 5</math> liczba <math>- 1</math> nie jest generatorem modulo <math>p</math>. Ponieważ <math>(- 1)^n = \pm 1</math>, to zbiór potęg
+oraz
-::<math>\{ g^1, g^2, g^3, \ldots, g^{p - 1} \}</math>
+::<math>a^n \equiv R_2 (a) \pmod 2</math>
-składa się tylko z&nbsp;dwóch elementów <math>\{ - 1, 1 \}</math> i&nbsp;dla liczb pierwszych <math>p \geqslant 5</math> nie może być identyczny modulo <math>p</math> ze zbiorem <math>\{ 1, 2, 3, \ldots, p - 1 \}</math>.
+dla dowolnej liczby całkowitej dodatniej <math>n</math>. Zatem modulo <math>2</math> jest
+::<math>{\small\frac{a^p - 1}{a - 1}} \equiv R_2 (a) \cdot (p - 1) + 1 \equiv 1 \pmod 2</math>
-Ilość generatorów modulo <math>p</math> dla liczby pierwszej <math>p = 2 q + 1</math> jest równa
+::<math>{\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2</math>
-::<math>\varphi (p - 1) = \varphi (2 q) = q - 1 = {\small\frac{p - 1}{2}} - 1</math>
+Co oznacza, że
-Ponieważ istnieje <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math> (zobacz J30), to liczb niekwadratowych modulo <math>p</math>, różnych od <math>- 1</math>, jest <math>{\small\frac{p - 1}{2}} - 1</math>, czyli tyle samo, co generatorów modulo <math>p</math>, a&nbsp;żadna z&nbsp;pozostałych liczb (kwadratowych modulo <math>p</math>) nie może być generatorem modulo <math>p</math>. Co kończy dowód.<br/>
+::<math>m = {\small\frac{a^p - 1}{a - 1}} \cdot {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2</math>
-&#9633;
-{{\Spoiler}}
+Czyli <math>m</math> jest '''złożoną liczbą nieparzystą'''. Pozostaje pokazać, że <math>a^{m - 1} \equiv 1 \pmod m</math>.
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q5</span><br/>
+Z twierdzenia Fermata wiemy, że
-Jeśli nie potrzebujemy wyliczyć najmniejszego generatora modulo <math>p = 2 q + 1</math>, to z&nbsp;twierdzenia Q4 można łatwo pokazać, że liczba <math>- 4</math> jest generatorem dla wszystkich liczb pierwszych <math>p = 2 q + 1 \geqslant 7</math>, a&nbsp;liczba <math>- 3</math> dla wszystkich liczb pierwszych <math>p = 2 q + 1 \geqslant 11</math>. Ponieważ <math>q = 2 k + 1</math>, to <math>p = 4 k + 3</math>.
-. Pokażemy, że <math>- 4</math> jest liczbą niekwadratową modulo <math>p</math>. Liczba <math>k</math> może być postaci <math>2 j</math> lub <math>2 j + 1</math>, co daje odpowiednio <math>p = 8 j + 3</math> lub <math>p = 8 j + 7</math>. Zatem
+::<math>a^p - 1 \equiv a - 1 \pmod p</math>
-::<math>\left( {\small\frac{- 4}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}}^{\! 2} = (- 1) \cdot (\pm 1)^2 = - 1</math>
+Ponieważ <math>(a - 1) \mid (a^p - 1)</math>, to możemy napisać
-Zobacz twierdzenie J42 p.6.
+::<math>(a - 1) \cdot \left( {\small\frac{a^p - 1}{a - 1}} - 1 \right) \equiv 0 \pmod p</math>
+Z założenia <math>p \nmid (a - 1)</math>, zatem liczba pierwsza <math>p</math> musi dzielić <math>{\small\frac{a^p - 1}{a - 1}} - 1</math> i&nbsp;otrzymujemy
-. Pokażemy, że <math>- 3</math> jest liczbą niekwadratową modulo <math>p</math>. Liczba <math>k</math> może być postaci <math>3 j, 3 j + 1, 3 j + 2</math>, co daje odpowiednio
+::<math>{\small\frac{a^p - 1}{a - 1}} \equiv 1 \pmod p</math>
-::<math>k = 3 j \qquad \qquad \;\!\!\! p = 12 j + 3 \qquad \;\; q = 6 j + 1</math>
+Postępując analogicznie jak wyżej, dostajemy
-::<math>k = 3 j + 1 \qquad p = 12 j + 7 \qquad \;\; q = 6 j + 3</math>
+::<math>a^p + 1 \equiv a + 1 \pmod p</math>
-::<math>k = 3 j + 2 \qquad p = 12 j + 11 \qquad q = 6 j + 5</math>
+::<math>(a + 1) \cdot \left( {\small\frac{a^p + 1}{a + 1}} - 1 \right) \equiv 0 \pmod p</math>
-Pierwsza i&nbsp;druga postać liczby <math>k</math> nie jest możliwa, bo albo liczba <math>p</math>, albo liczba <math>q</math> byłyby liczbami złożonymi. Zatem
+::<math>{\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod p</math>
-::<math>\left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = (- 1) \cdot (+ 1) = - 1</math>
+Wynika stąd, że <math>m \equiv 1 \pmod p</math>.
-Zobacz twierdzenie J42 p.6 i&nbsp;zadanie J47.
+Zbierając mamy <math>2 \mid (m - 1)</math> i <math>p \mid (m - 1)</math>, zatem <math>2 p \mid (m - 1)</math>, czyli
+::<math>m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} \equiv 1 \pmod{2 p}</math>
+Oznacza to, że <math>m = 1 + 2 k p</math> dla pewnej liczby całkowitej <math>k > 0</math>.
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q6</span><br/>
-O ile w&nbsp;ogólnym przypadku liczb pierwszych <math>p</math> liczących setki cyfr znalezienie najmniejszego generatora modulo <math>p</math> może trwać godzinami, to w&nbsp;przypadku liczb pierwszych <math>p = 2 q + 1</math>, gdzie <math>q</math> jest również liczbą pierwszą, wystarczy znaleźć liczbę niekwadratową modulo <math>p</math>, a&nbsp;obliczenie symbolu Jacobiego trwa bardzo krótko, zaś wyszukanie liczb pierwszych postaci <math>p = 2 q + 1</math> też jest zaskakująco szybkie. Dlatego napisaliśmy w&nbsp;PARI/GP prosty program, który wyszukuje w&nbsp;zadanym przedziale <math>[m, n]</math> liczbę pierwszą <math>p</math> taką, że <math>p = 2 q + 1</math> i&nbsp;zwraca <math>p</math> oraz najmniejszy generator modulo <math>p</math>.
-Należy zwrócić uwagę, że funkcje <code>ispseudoprime()</code> i <code>randomprime()</code> sprawdzają pierwszość liczby na tym samym poziomie – wykonywany jest test Millera-Rabina. Dlatego używamy ich łącznie, co przyspiesza wyszukanie odpowiedniej liczby pierwszej. Następnie, już silniejszym testem, potwierdzamy pierwszość obydwu liczb: <math>p</math> i <math>(p - 1) / 2</math>.
+Zauważmy teraz, że z&nbsp;definicji liczby <math>m</math> mamy <math>(a^2 - 1) m = a^{2 p} - 1</math>. Rozpatrując to równanie modulo <math>m</math>, otrzymujemy
-{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
+::<math>a^{2 p} \equiv 1 \pmod m</math>
- <span style="font-size: 90%; color:black;">SafePrime(m, n) =
- \\ zwraca wektor [p, g], gdzie p i (p-1)/2 są liczbami pierwszymi, a g jest generatorem modulo p
- {
- '''local'''(g, p);
- '''setrand'''('''getwalltime'''());  \\ ustawiamy ziarno (ang. seed) generatora liczb losowych
- '''while'''( 1,
-        p = 9;
-        '''while'''( !'''ispseudoprime'''( (p - 1)/2 ), p = '''randomprime'''([m, n]) );
-        '''if'''( '''isprime'''(p) && '''isprime'''( (p-1)/2 ), '''break'''() );
-      );
- g = 2;
- '''while'''( jacobi(g, p) > -1, g++ );
- '''return'''([p, g]);
- }</span>
-<br/>
-{{\Spoiler}}
+Zatem modulo <math>m</math> jest
+::<math>a^{m - 1} = a^{2 k p} = (a^{2 p})^k \equiv 1^k \equiv 1 \pmod m</math>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q7</span><br/>
+Ponieważ dowolna liczba pierwsza <math>p > a^2 - 1</math> nie dzieli <math>a^2 - 1</math>, to dla każdego <math>a \geqslant 2</math> istnieje nieskończenie wiele liczb, które są PSP(<math>a</math>). Co należało pokazać.<br/>
-Jak dalece bezpieczna jest opisana wyżej metoda? Aby znaleźć klucz trzeba oprócz (jawnych) liczb <math>p, g, X, Y</math> znać jedną z&nbsp;liczb <math>a</math> lub <math>b</math>. Liczba <math>a</math> spełnia kongruencję
+&#9633;
+{{\Spoiler}}
-::<math>g^a \equiv X \!\! \pmod{p}</math>
-ale nie istnieje żadna metoda szybkiego znalezienia wykładnika <math>a</math>. Oczywiście zawsze pozostaje możliwość kolejnego wyliczania <math>g^n</math> modulo <math>p</math> z&nbsp;nadzieją trafienia na <math>X</math> lub <math>Y</math>. Dla naszych danych mielibyśmy modulo <math>541</math>
-::<math>2^1 \equiv 2, \quad 2^2 \equiv 4, \; \ldots , \; 2^{17} \equiv 150, \quad 2^{18} \equiv 300</math>
+<span style="font-size: 110%; font-weight: bold;">Przykład M7</span><br/>
+Z dowodu twierdzenia M6 wynika, że jeżeli liczba <math>p</math> jest liczbą pierwszą nieparzystą i <math>p \nmid (a^2 - 1)</math>, to liczba <math>m = {\small\frac{a^{2 p} - 1}{a^2 - 1}}</math> jest PSP(<math>a</math>). Poniżej przedstawiamy przykłady takich liczb, dla kolejnych liczb pierwszych nieparzystych <math>p</math> takich, że <math>p \nmid (a^2 - 1)</math>.
-czyli wystarczyło jedynie 18 prób! Ale dla dwustucyfrowej liczby pierwszej <math>p</math> i&nbsp;trochę lepiej wybranych liczb <math>a</math> i <math>b</math> ilość prób będzie liczbą rzędu <math>10^{50}</math>. Nawet dla najszybszych komputerów stanowi to barierę nie do pokonania.
+ <span style="font-size: 90%; color:black;">'''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'''() ) )) </span>
+::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
+! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math>
+|-
+|   || <math>341</math> || <math>91</math> || <math>17895697</math> || <math>406901</math>
+|-
+|   || <math>5461</math> || <math>7381</math> || <math>1172812402961</math> || <math>254313151</math>
+|-
+|   || <math>1398101</math> || <math>597871</math> || <math>300239975158033</math> || <math>99341074625651</math>
+|-
+|   || <math>22369621</math> || <math>3922632451</math> || <math>19676527011956855057</math> || <math>62088171641031901</math>
+|-
+|   || <math>5726623061</math> || <math>317733228541</math> || <math>5037190915060954894609</math> || <math>24253192047278086344401</math>
+|-
+|   || <math>91625968981</math> || <math>2084647712458321</math> || <math>330117343809434739973099793</math> || <math>15158245029548803965250651</math>
+|}
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q8</span><br/>
-Realne zagrożenie pojawia się jedynie wtedy, gdy Agencja i&nbsp;Bolek nie sprawdzą autentyczności liczb <math>X</math> i <math>Y</math>. Przykładowo Agencja może zapytać o <math>7</math>, <math>23</math>, <math>101</math> itd. cyfrę liczby <math>X</math>, którą otrzymał Bolek. Dlaczego jest to ważne? Jeżeli korespondencja (maile, listy) Agencji i&nbsp;Bolka jest kontrolowana przez Wywiad, to Wywiad może przechwycić liczby <math>X = R_p (g^a)</math> oraz <math>Y = R_p (g^b)</math> i&nbsp;wysłać im swoją liczbę <math>Z = R_p (g^c)</math>. Od tej pory korespondencja Agencji będzie przechwytywana, odszyfrowywana przez Wywiad kluczem <math>k_1 = R_p (g^{a c})</math>, czytana, ewentualnie zmieniana, ponownie szyfrowana kluczem <math>k_2 = R_p (g^{b c})</math> i&nbsp;wysyłana do Bolka.
-Analogicznie będzie kontrolowana korespondencja Bolka wysyłana do Agencji.
+<span style="font-size: 110%; font-weight: bold;">Uwaga M8</span><br/>
+Wykorzystując funkcję potęgowania modulo, możemy napisać prosty program do testowania pierwszości liczb w&nbsp;oparciu o&nbsp;twierdzenie Fermata.
+ <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">PSP</span>(m, a) =
+ {
+ '''if'''( modPower(a, m-1, m) == 1, '''return'''(1), '''return'''(0) );
+ }</span>
+<span style="font-size: 110%; font-weight: bold;">Przykład M9</span><br/>
+Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Fermata dla podstaw <math>a</math> od <math>2</math> do <math>15</math>
-== Szyfrowanie RSA ==
+ <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=1; '''forstep'''(m=1, 2000, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">PSP</span>(m, a)  &&  !'''isprime'''(m), '''print'''("a=", a, "  m=", m); s++ ); '''if'''( s>5, '''break'''() ) ))</span>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q9</span><br/>
+::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
-Rozpoczniemy od dowodu kilku prostych twierdzeń. Łatwość ich sformułowania i&nbsp;dowodu zaskakuje, jeśli weźmiemy pod uwagę fakt, że stanowią one podstawę niezwykle ważnej metody szyfrowania.
+! &nbsp;&nbsp;<math>\boldsymbol{a}</math>&nbsp;&nbsp; !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math>
+|-
+|   || <math>341</math> || <math>91</math> || <math>15</math> || <math>217</math> || <math>35</math> || <math>25</math> || <math>9</math> || <math>91</math> || <math>9</math> || <math>15</math> || <math>65</math> || <math>21</math> || <math>15</math> || <math>341</math>
+|-
+|   || <math>561</math> || <math>121</math> || <math>85</math> || <math>561</math> || <math>185</math> || <math>325</math> || <math>21</math> || <math>121</math> || <math>33</math> || <math>133</math> || <math>91</math> || <math>85</math> || <math>39</math> || <math>1477</math>
+|-
+|   || <math>645</math> || <math>671</math> || <math>91</math> || <math>781</math> || <math>217</math> || <math>561</math> || <math>45</math> || <math>205</math> || <math>91</math> || <math>259</math> || <math>133</math> || <math>105</math> || <math>65</math> || <math>1541</math>
+|-
+|   || <math>1105</math> || <math>703</math> || <math>341</math> || <math>1541</math> || <math>301</math> || <math>703</math> || <math>63</math> || <math>511</math> || <math>99</math> || <math>305</math> || <math>143</math> || <math>231</math> || <math>195</math> || <math>1687</math>
+|-
+|   || <math>1387</math> || <math>949</math> || <math>435</math> || <math>1729</math> || <math>481</math> || <math>817</math> || <math>65</math> || <math>671</math> || <math>259</math> || <math>481</math> || <math>145</math> || <math>357</math> || <math>481</math> || <math>1729</math>
+|}
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie Q10</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Przykład M10</span><br/>
-Jeżeli <math>p</math> jest liczbą pierwszą, to dla dowolnego <math>a \in \mathbb{Z}</math> i&nbsp;każdego <math>k \geqslant 0</math> jest
+Tabela pokazuje ilość liczb pseudopierwszych Fermata dla podstaw <math>a</math> od <math>2</math> do <math>15</math>
-::<math>a^{(p - 1) k + 1} \equiv a \!\! \pmod{p}</math>
+ <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=0; '''forstep'''(k=1, 10^6, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">PSP</span>(k, a)  &&  !'''isprime'''(k), s++ )); '''print'''("a= ", a, "   ", s))</span>
-{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
-Jeżeli <math>p \mid a</math>, to dowodzona kongruencja jest prawdziwa. Jeżeli <math>p \nmid a</math>, to modulo <math>p</math> mamy
+! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math>
+|-
+| #PSP(<math>a</math>) <math> < 10^6</math> || <math>245</math> || <math>243</math> || <math>464</math> || <math>238</math> || <math>301</math> || <math>229</math> || <math>678</math> || <math>362</math> || <math>271</math> || <math>236</math> || <math>378</math> || <math>257</math> || <math>283</math> || <math>203</math>
+|-
+| #PSP(<math>a</math>) <math> < 10^7</math> || <math>750</math> || <math>749</math> || <math>1347</math> || <math>726</math> || <math>895</math> || <math>651</math> || <math>1993</math> || <math>1150</math> || <math>766</math> || <math>672</math> || <math>1091</math> || <math>719</math> || <math>817</math> || <math>614</math>
+|-
+| #PSP(<math>a</math>) <math> < 10^8</math> || <math>2057</math> || <math>2131</math> || <math>3805</math> || <math>1910</math> || <math>2314</math> || <math>1782</math> || <math>5407</math> || <math>3214</math> || <math>2091</math> || <math>1891</math> || <math>2933</math> || <math>1929</math> || <math>2155</math> || <math>1718</math>
+|-
+| #PSP(<math>a</math>) <math> < 10^9</math> || <math>5597</math> || <math>5767</math> || <math>10173</math> || <math>5146</math> || <math>6204</math> || <math>4923</math> || <math>14629</math> || <math>8670</math> || <math>5599</math> || <math>5020</math> || <math>7781</math> || <math>5082</math> || <math>5848</math> || <math>4665</math>
+|}
-::<math>a^{(p - 1) k + 1} = a \cdot (a^{p - 1})^k \equiv a \!\! \pmod{p}</math>
-gdzie skorzystaliśmy z&nbsp;twierdzenia Fermata (J22).<br/>
-&#9633;
-{{\Spoiler}}
+<span style="font-size: 110%; font-weight: bold;">Uwaga M11</span><br/>
+Można pokazać, że jeżeli <math>m</math> jest liczbą nieparzystą złożoną i&nbsp;istnieje przynajmniej jedna liczba <math>a</math> względnie pierwsza z <math>m</math>, taka że
+::<math>a^{m - 1} \not\equiv 1 \pmod m</math>
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie Q11</span><br/>
+to dla co najmniej połowy liczb <math>b \in [1, m - 1]</math> względnie pierwszych z <math>m</math> jest
-Jeżeli <math>p</math> i <math>q</math> są różnymi liczbami pierwszymi, to dla dowolnego <math>a \in \mathbb{Z}</math> i&nbsp;każdego <math>k \geqslant 0</math> jest
-::<math>a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p q}</math>
+::<math>b^{m - 1} \not\equiv 1 \pmod m</math>
-{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+Zatem przeprowadzając test Fermata, możemy z&nbsp;prawdopodobieństwem nie mniejszym niż <math>\tfrac{1}{2}</math> twierdzić, że liczba, która przeszła test, jest liczbą pierwszą. Wykonując test <math>k</math> razy dla <math>k</math> różnych podstaw z&nbsp;przedziału <math>[1, m - 1]</math> możemy z&nbsp;prawdopodobieństwem większym niż <math>1 - \left( \tfrac{1}{2} \right)^k</math> twierdzić, że badana liczba <math>m</math> jest pierwsza.
-Z twierdzenia Q10 wiemy, że dla dowolnych liczb <math>i, j \geqslant 0</math> prawdziwe są kongruencje
-::<math>a^{(p - 1) i + 1} \equiv a \!\! \pmod{p}</math>
+Niestety, istnieją liczby złożone <math>m</math> takie, że
-::<math>a^{(q - 1) j + 1} \equiv a \!\! \pmod{q}</math>
+::<math>a^{m - 1} \equiv 1 \pmod m</math>
-Dla dowolnego, ale ustalonego <math>k \geqslant 0</math> wybierzmy liczby <math>i, j</math> następująco: <math>i = k (q - 1)</math> oraz <math>j = k (p - 1)</math>. Otrzymujemy
+dla każdego <math>a</math> względnie pierwszego z <math>m</math>. Liczby te nazywamy liczbami Carmichaela i&nbsp;jest ich nieskończenie wiele. Pokazano, że dla dostatecznie dużych <math>x</math> ilość liczb Carmichaela mniejszych od <math>x</math> przekracza <math>x^{1/3}</math><ref name="Carmichael1"/><ref name="Carmichael2"/><ref name="Carmichael3"/>. Test Fermata jest zatem zbyt zawodny, aby można było go stosować.
-::<math>a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p}</math>
-::<math>a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{q}</math>
-Z twierdzenia J1 wiemy, że powyższy układ kongruencji może być zapisany w&nbsp;sposób równoważny
+<span style="font-size: 110%; font-weight: bold;">Przykład M12</span><br/>
+Oto wszystkie liczby Carmichaela mniejsze od <math>100 000</math>
-::<math>a^{k (p - 1) (q - 1) + 1} \equiv a \!\! \pmod{p q}</math>
+::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: left; margin-right: auto;"
+| <math>561=3⋅11⋅17</math> || <math>1105=5⋅13⋅17</math> || <math>1729=7⋅13⋅19</math> || <math>2465=5⋅17⋅29</math>
+|-
+|  <math>2821=7⋅13⋅31</math> || <math>6601=7⋅23⋅41</math> || <math>8911=7⋅19⋅67</math> || <math>10585=5⋅29⋅73</math>
+|-
+|  <math>15841=7⋅31⋅73</math> || <math>29341=13⋅37⋅61</math> || <math>41041=7⋅11⋅13⋅41</math> || <math>46657=13⋅37⋅97</math>
+|-
+|  <math>52633=7⋅73⋅103</math> || <math>62745=3⋅5⋅47⋅89</math> || <math>63973=7⋅13⋅19⋅37</math> || <math>75361=11⋅13⋅17⋅31</math>
+|}
-Co należało pokazać.<br/>
-&#9633;
-{{\Spoiler}}
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q12 (metoda szyfrowania RSA)</span><br/>
-RSA<ref name="RSA1"/><ref name="RSA2"/> to akronim od nazwisk twórców tej metody: Rona Rivesta, Adiego Shamira i&nbsp;Leonarda Adlemana. Rozpoczniemy od wypisania używanych oznaczeń, co znakomicie ułatwi zrozumienie opisu metody.
-:# <math>p, q</math> – dwie duże liczby pierwsze o&nbsp;zbliżonych wartościach
+== Test Millera-Rabina ==
-:#* często przyjmuje się, że <math>p < q < 2 p</math>; można też przyjąć, że <math>q \sim 2 p</math>
-:# <math>m = p q</math>
-:# <math>\Phi = (p - 1) (q - 1)</math>
-:#* oznaczenie nawiązuje do funkcji Eulera <math>\varphi</math>, bo <math>\varphi (m) = \varphi (p q) = (p - 1) (q - 1)</math>
-:# <math>e</math> (ang. ''encryption'') – wykładnik służący do szyfrowania (publiczny)
-:# <math>d</math> (ang. ''decryption'') – wykładnik służący do odszyfrowania (tajny)
-:# <math>B</math> (ang. ''block of digits'') – wiadomość w&nbsp;postaci liczby (ciągu cyfr) przeznaczona do zaszyfrowania
-:# <math>C</math> (ang. ''coded block of digits'') – zaszyfrowana wiadomość, czyli liczba powstała w&nbsp;wyniku szyfrowania liczby <math>B</math>
+Rozpoczniemy od udowodnienia prostego twierdzenia
-'''Opis metody'''
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie M13</span><br/>
-:# Wybierzmy liczbę <math>e</math> tak, aby spełniała warunki <math>\gcd (e, \Phi) = 1</math> i <math>2 < e < \Phi</math>
+Jeśli <math>m</math> jest liczbą pierwszą nieparzystą i <math>x^2 \equiv 1 \pmod m</math>, to albo <math>x \equiv - 1 \pmod m</math>, albo <math>x \equiv 1 \pmod m</math>.
-:#* zaleca się, aby <math>e \geqslant 65537</math>
-:# Z&nbsp;lematu Bézouta (zobacz C73) istnieją takie liczby całkowite <math>d</math> i <math>k</math>, że <math>d e + k \Phi = 1</math>. Liczbę <math>d</math> wyliczamy ze wzoru <math>d = d_0 + \Phi t</math>, gdzie <math>d_0</math> (oraz <math>k_0</math>) otrzymujemy, wykorzystując w&nbsp;PARI/GP funkcję <code>gcdext(e, Φ)</code> (zobacz C78)
-:#* <math>d</math> wybieramy tak, aby była liczbą dodatnią, wtedy <math>k</math> musi być liczbą ujemną
-:#* <math>d</math> nie może być zbyt małą liczbą; pokazano<ref name="BonehDurfee1"/>, że powinno być <math>d > m^{0.292}</math>
-:# Metoda szyfrowania RSA wymaga trzech liczb: <math>m</math>, <math>e</math>, <math>d</math>. Liczba <math>d</math> jest tajna. Podobnie tajne są liczby <math>p</math>, <math>q</math>, <math>\Phi</math>, ale te liczby można po prostu skasować po wyliczeniu <math>d</math>
-:# Szyfrowaną wiadomość przekształcamy w&nbsp;ciąg cyfr. W&nbsp;przypadku długich wiadomości może być konieczny podział ciągu cyfr na bloki. Tworzymy w&nbsp;ten sposób liczbę <math>B</math>. Zakładamy, że <math>B < m</math>
-:# Szyfrowanie. Zakodowany tekst jest wynikiem operacji: <math>C = R_m (B^e)</math>, gdzie <math>R_m (B^e)</math> oznacza resztę z&nbsp;dzielenia liczby <math>B^e</math> przez <math>m</math>
-:#* zauważmy, że: <math>C \equiv B^e \!\! \pmod{m}</math>
-:# Odszyfrowanie. Odkodowany tekst otrzymujemy, obliczając: <math>B = R_m (C^d)</math>
-:# Dowód poprawności metody wynika z&nbsp;twierdzenia Q12
-:#* <math>R_m (C^d) \equiv C^d \equiv (B^e)^d \equiv B^{e d} \equiv B^{- k \Phi + 1} \equiv B^{- k (p - 1) (q - 1) + 1} \equiv B \!\! \pmod{m}</math>
-:#* ponieważ <math>k < 0</math>, to <math>- k</math> jest liczbą dodatnią i&nbsp;możemy zastosować twierdzenie Q12
-:#* ponieważ <math>B < m</math>, to <math>R_m (C^d) = B</math>
-:# Para liczb <math>(m, e)</math> jest nazywana kluczem publicznym – służy do szyfrowania i&nbsp;może być dostępna dla każdego.
-:# Para liczb <math>(m, d)</math> jest nazywana kluczem prywatnym – służy do odszyfrowania. Liczba <math>d</math> jest tajna – osoba, która ją wykradnie, będzie mogła odczytywać wysyłane do nas wiadomości
+{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
+Z założenia
+::<math>x^2 \equiv 1 \pmod m</math>
-<span style="font-size: 110%; font-weight: bold;">Przykład Q13</span><br/>
+Zatem <math>m \mid (x^2 - 1)</math>, czyli <math>m \mid (x - 1) (x + 1)</math>. Ponieważ z&nbsp;założenia <math>m</math> jest liczbą pierwszą nieparzystą, to <math>m</math> dzieli dokładnie jedną z&nbsp;liczb <math>x - 1</math> i <math>x + 1</math>. Istotnie, gdyby <math>m \mid (x - 1)</math> <math>\text{i} \;\, m \mid (x + 1)</math>, to <math>m</math> dzieliłaby również ich różnicę równą <math>2</math>, co jest niemożliwe w&nbsp;przypadku gdy <math>m</math> jest liczbą pierwszą nieparzystą.<br/>
-Prosty przykład: niech wysyłaną wiadomością będzie słowo <math>\text{YES}</math>. Zamianę liter na ciąg cyfr dokonamy, przypisując każdej literze jej numer w&nbsp;alfabecie np.: <math>A \longrightarrow 01</math>, <math>B \longrightarrow 02</math>, ... , <math>Z \longrightarrow 26</math>, czyli <math>\text{YES}\longrightarrow 250519</math>, zatem musimy zaszyfrować liczbę <math>250519</math>.
+&#9633;
+{{\Spoiler}}
-Niech <math>p = 1009</math>, <math>q = 1013</math>, <math>e = 1019</math>. Znajdujemy <math>m = p q = 1022117</math>, <math>\Phi = (p - 1) (q - 1) = 1020096</math>, <math>d = 397427</math>. Klucz publiczny <math>(m, e)</math>, klucz prywatny <math>(m, d)</math>. Zaszyfrowana wiadomość to <math>R_m (250519^e) = 560222</math>. Odszyfrowując, otrzymujemy <math>R_m (560222^d) = 250519</math>. Tak, jak być powinno.
+Prace Gary'ego Millera<ref name="Miller1"/> i&nbsp;Michaela Rabina<ref name="Rabin1"/> pozwoliły sformułować znacznie silniejszy test. Podstawą tego testu jest następujące twierdzenie
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q14</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie M14</span><br/>
-Bezpieczeństwo metody polega na wyborze tak dużych liczb pierwszych <math>p</math> i <math>q</math>, aby faktoryzacja ich iloczynu <math>m</math> leżała poza możliwościami współczesnych komputerów i&nbsp;stosowanych algorytmów. Choć klucz publiczny <math>(m, e)</math> służący do szyfrowania nie jest tajny i&nbsp;może być udostępniany wszystkim, to poznanie klucza prywatnego, czyli liczby <math>d</math>, jest praktycznie niemożliwe.
+Jeżeli <math>m</math> jest liczbą pierwszą nieparzystą i <math>m - 1 = 2^r d</math>, gdzie <math>d</math> jest liczbą nieparzystą, to dla dowolnego <math>a \in [1, m - 1]</math> jest albo
-Liczba <math>d</math> wynika z&nbsp;rozwiązania równania <math>d e + k \Phi = 1</math>, ale aby obliczyć <math>\Phi = (p - 1) (q - 1)</math> musimy znać rozkład liczby <math>m</math> na czynniki pierwsze. Obecnie nie istnieją dostatecznie szybkie sposoby znajdowania rozkładu dużych liczb na czynniki pierwsze. Możemy łatwo sprawdzić, czy liczba <math>m = p q</math> jest liczbą złożoną, ale jeśli tak jest, to poznanie jej czynników jest dla dostatecznie dużych <math>m</math> niemożliwe.
+::<math>a^d \equiv 1 \pmod m</math>
+albo
+::<math>a^{2^k d} \equiv - 1 \pmod m</math>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q15 (generowanie liczb <math>m, e, d</math>)</span><br/>
+dla pewnego <math>k \in [0, r - 1]</math>.
-Przyjmując proste założenia co do liczb pierwszych <math>p, q</math> (przyjęliśmy, że <math>1.8 p < q < 2.2 p</math>) oraz zakładając, że <math>d > m^{2 / 3}</math> napisaliśmy prosty program do generowania klucza publicznego i&nbsp;prywatnego. Parametr <code>w</code> określa, ile cyfr w&nbsp;układzie dziesiętnym będą miały liczby <math>p, q</math>. Wybór <code>w > 500</code> gwarantuje wygenerowanie liczby <math>m</math>, której rozkład na czynniki pierwsze nie powinien być możliwy przez wiele lat. Ostatnie (znane) osiągnięcie faktoryzacji, to rozkład 250-cyfrowej liczby <math>m = p q</math> na czynniki pierwsze<ref name="RSA250"/>.
-{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
+{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
- <span style="font-size: 90%; color:black;">RSAkeys(w) =
+Rozważmy ciąg <math>r + 1</math> liczb zdefiniowanych następująco
- \\ parametr w > 1 określa, ile cyfr w&nbsp;układzie dziesiętnym będą miały liczby p, q
- {
- '''local'''(d, e, m, p, Phi, q);
- '''setrand'''('''getwalltime'''());  \\ ustawiamy ziarno (ang. seed) generatora liczb losowych
- p = 1;
- q = 0;
- '''while'''( !'''isprime'''(p)  ||  !'''isprime'''(q),
-        '''while'''( q < 1.8 * p  ||  q > 2.2 * p,
-               p = '''randomprime'''( [10^(w - 1), 10^w] );
-               q = '''randomprime'''( [10^(w - 1), 10^w] );
-             );
-      );
- m = p * q;
- Phi = (p - 1) * (q - 1);
- d = -1;
- '''while'''( d < m^(2/3),
-        e = '''randomprime'''( [10^10, 10^15] );
-        if( '''gcd'''(e, Phi) > 1, '''next'''() );
-        d = '''gcdext'''(e, Phi)[1];
-      );
- '''return'''([m, e, d]);
- }</span>
- <span style="font-size: 90%; color:black;">PrintRSAkeys(w) =
+::<math>\begin{array}{l}
- {
+  u_0 = a^d \\
- '''local'''(V);
+  u_1 = a^{2 d} = (a^d)^2 \\
- V = RSAkeys(w);
+  u_2 = a^{2^2 d} = (a^{2 d})^2 \\
- '''print'''("m = ", V[1]);
+  \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\
- '''print'''("e = ", V[2]);
+  u_{r - 1} = a^{2^{r - 1} d} = (a^{2^{r - 2}})^2 \\
- '''print'''("d = ", V[3]);
+  u_r = a^{2^r d} = (a^{2^{r - 1} d})^2 = a^{m - 1} \\
- }</span>
+\end{array}</math>
-{{\Spoiler}}
+Wyrazy ciągu <math>(u_i)</math> są dane wzorem ogólnym
+::<math>u_i = a^{2^i d}</math>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q16 (zamiana tekstu na liczbę i&nbsp;odwrotnie)</span><br/>
+gdzie <math>i = 0, 1, \ldots, r</math>
-W przypadku profesjonalnych programów szyfrujących wykorzystujących metodę RSA szyfrowany jest cały plik, który jest przecież ciągiem zer i&nbsp;jedynek. Oprogramowanie dzieli taki plik na odpowiednich rozmiarów bloki <math>B_j</math> i&nbsp;każdy jest szyfrowany kluczem publicznym <math>(m, e)</math>. Możemy w&nbsp;ten sposób szyfrować zdjęcia, filmy, tekst w&nbsp;dowolnym języku itd.
-Ponieważ napisanie takiego oprogramowania wykraczałoby poza potrzeby tego omówienia, ale z&nbsp;drugiej strony chcemy udostępnić Czytelnikowi przykłady bardziej skomplikowane niż szyfrowanie słowa <math>\text{YES}</math>, to postanowiliśmy ograniczyć się do szyfrowania tekstu, który zawiera jedynie znaki ASCII<ref name="ASCII"/>.
+Zauważmy, że mogą zdarzyć się następujące sytuacje
-Aby efektywnie korzystać z&nbsp;szyfrowania RSA potrzebne będą nam programy, które przetworzą taki tekst na liczbę i&nbsp;odwrotnie. Poniżej przedstawiamy dwie bardzo proste funkcje: pierwsza funkcja zamienia znaki ASCII od 32 do 126 na liczbę (każdemu znakowi przypisywane są dwie cyfry), a&nbsp;druga funkcja zamienia wygenerowaną przez pierwszą funkcję liczbę na odpowiadający tej liczbie tekst.
+:a) żaden z&nbsp;wyrazów ciągu <math>(u_i)</math> nie przystaje do <math>1</math> modulo <math>m</math>
-Założenie, że nasza wiadomość zawiera tylko znaki ASCII od 32 do 126, jest bardzo ważne. Oznacza to, że taki tekst przetworzony przez funkcję <code>TextToNumber()</code> na liczbę, zostanie odtworzony przez funkcję <code>NumberToText()</code> w&nbsp;niezmienionej postaci. Nie będzie tak, jeśli wystąpią inne znaki: każdy z&nbsp;takich znaków zostanie zamieniony na spacje (np. każda polska litera zostanie zamieniona na dwie spacje). Nie oznacza to, że nie można korzystać z&nbsp;tych funkcji, ale jeśli szyfrujemy '''podpisaną''' wiadomość, to zgodność tekstów ma zasadnicze znaczenie.
+:b) wszystkie wyrazy ciągu <math>(u_i)</math> przystają do <math>1</math> modulo <math>m</math>
-{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
+:c) <math>u_k</math> jest pierwszym wyrazem ciągu <math>(u_i)</math>, który przystaje do <math>1</math> modulo <math>m</math>
- <span style="font-size: 90%; color:black;">TextToNumber( s ) =
- \\ zamienia znaki ASCII od 32 do 126 na liczbę
- {
- '''local'''(a, b, k, len, txt, V);
- V = '''Vecsmall'''(s);
- len = '''length'''(V);
- txt = "";
- k = 0;
- '''while'''( k++ <= len,
-        a = V[k];
-        b = "01";  \\ spacja – wstawiamy jeżeli a jest poza zakresem
-        '''if'''( a >= 32  &&  a <= 40, b = '''Str'''("0", a - 31) );
-        '''if'''( a >= 41  &&  a <= 126, b = '''Str'''(a - 31) );
-        txt = '''Str'''(txt, b);
-      );
- '''return'''( '''eval'''(txt) );
- }</span>
- <span style="font-size: 90%; color:black;">NumberToText( n ) =
- {
- '''local'''(a, k, len, txt, V);
- len = '''length'''('''Str'''(n));
- '''if'''( len % 2 == 1, len++ ); \\ "zgubione" zero na początku
- len = len / 2;
- V = '''vector'''(len);
- k = len + 1;
- '''while'''( k-- >= 1,
-        a = n % 100;
-        n = '''floor'''(n / 100);
-        V[k] = a + 31;
-      );
- txt = '''strchr'''(V);
- '''return'''(txt);
- }</span>
-<br/>
-{{\Spoiler}}
+Co możemy zapisać jako
+:a) <math>u_i \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q17</span><br/>
+:b) <math>u_i \equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math>
-Jeżeli mamy już funkcje zamieniające tekst na liczbę i&nbsp;odwrotnie, to napisanie w&nbsp;PARI/GP programów do szyfrowania i&nbsp;deszyfrowania metodą RSA jest bardzo proste.
-{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
+:c) <math>u_k \equiv 1 \pmod m \quad</math> dla pewnego <math>k \in [0, r]</math>
- <span style="font-size: 90%; color:black;">RSAencode(m, e, s) =
- \\ szyfrujemy string s
- {
- '''local'''(B, C);
- B = TextToNumber(s);
- C = '''lift'''( '''Mod'''(B, m)^e );
- '''print'''(C);
- }</span>
- <span style="font-size: 90%; color:black;">RSAdecode(m, d, C) =
- \\ deszyfrujemy liczbę C
- {
- '''local'''(B, s);
- B = '''lift'''( '''Mod'''(C, m)^d );
- s = NumberToText(B);
- '''print'''(s);
- }</span>
-<br/>
-{{\Spoiler}}
+Z definicji każdy wyraz ciągu <math>(u_i)</math> jest kwadratem poprzedniego. W&nbsp;szczególności oznacza to, że jeżeli dla pewnego <math>k \in [0, r]</math> jest <math>u_k \equiv 1 \pmod m</math>, to <math>u_i \equiv 1 \pmod m</math> dla wszystkich <math>i \geqslant k</math>. Ten fakt pozwala doprecyzować zapis poszczególnych przypadków.
+:a) <math>u_i \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math>
-<span style="font-size: 110%; font-weight: bold;">Przykład Q18</span><br/>
+:b) <math>u_0 \equiv 1 \pmod m</math>
-Kładąc <code>w = 50</code> w&nbsp;funkcji <code>RSAkeys(w)</code> otrzymaliśmy
-m = 2173471545652309346779542101680852446325835148920429701148920590128959176663355134192839060494750117<br/>
+:c) <math>u_i \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, k - 1] \quad</math> oraz <math>\quad u_i \equiv 1 \pmod m \quad </math> dla każdego <math>i \in [k, r] , \quad</math> gdzie <math>k \geqslant 1</math>
-e = 3675359337253<br/>
-d = 308186586218659991253427464678921309369969889382350078327142348395702895999753492453847408362677933<br/>
-Liczba m&nbsp;ma 100 cyfr. Podamy teraz prosty przykład z&nbsp;polskimi literami. Zakodujemy i&nbsp;odkodujemy tekst (35 znaków)
-''Lepszy na wolności kęsek lada jaki.''
+W przypadku a) mamy <math>u_r = a^{m - 1} \not\equiv 1 \pmod m</math>, zatem liczba <math>m</math> byłaby liczbą złożoną, wbrew założeniu, że jest liczbą pierwszą.<br/>
-Zamieniając tekst na liczbę – funkcją <code>TextToNumber(s)</code> – otrzymujemy liczbę 74-cyfrową
+Przypadek b) jest możliwy (np. dla <math>m = 41</math> i <math>a = 10</math>), ale nie pozwala powiedzieć nic więcej ani o&nbsp;liczbie <math>m</math>, ani o&nbsp;wyrazach ciągu <math>(u_i)</math>, które wszystkie przystają do <math>1</math> modulo <math>m</math>.<br/>
-B = 45708184919001796601888077798001016874017601018470760177666966017566767415
+W przypadku c) mamy <math>u_k \equiv 1 \pmod m</math>, czyli <math>(u_{k - 1})^2 \equiv 1 \pmod m</math>. Z&nbsp;twierdzenia M13 wiemy, że musi być albo <math>u_{k - 1} \equiv - 1 \pmod m</math>, albo <math>u_{k - 1} \equiv 1 \pmod m</math>. Ale drugi przypadek nie może zachodzić, bo założyliśmy, że <math>u_k</math> jest pierwszym wyrazem ciągu <math>(u_i)</math>, który przystaje do <math>1</math> modulo <math>m</math>. Zatem musi być <math>u_{k - 1} \equiv - 1 \pmod m</math>.<br/>
-Jest tak, bo każdy znak tekstu został zamieniony na dwie cyfry, ale każda z&nbsp;polskich liter "ś" i "ę" została zamieniona na dwie spacje i&nbsp;każdej z&nbsp;tych liter odpowiadają cztery cyfry "0101". Zauważmy, że B&nbsp;<&nbsp;m tak, jak być powinno.
+Co kończy dowód twierdzenia.<br/>
+&#9633;
+{{\Spoiler}}
-Korzystając z&nbsp;funkcji <code>RSAencode(m, e, s)</code>, dostajemy od razu zakodowany tekst
-C = 1883258467778511884133977054466089742750188942420326552221154007622797635139655819975338109849673552
-Po odkodowaniu funkcją <code>RSAdecode(m, d, C)</code>, otrzymujemy
+<span style="font-size: 110%; font-weight: bold;">Definicja M15</span><br/>
+Złożoną liczbę nieparzystą <math>m</math>, która spełnia twierdzenie M14 dla pewnej liczby <math>a \in \mathbb{Z}</math>, będziemy nazywali liczbą silnie pseudopierwszą przy podstawie <math>a</math> (w skrócie: SPSP(<math>a</math>)).
-''Lepszy na wolno&nbsp;&nbsp;ci k&nbsp;&nbsp;sek lada jaki.''
-Polskie litery zostały zastąpione przez dwie spacje.
+<span style="font-size: 110%; font-weight: bold;">Uwaga M16</span><br/>
+Niech <math>a</math> będzie liczbą całkowitą względnie pierwszą z <math>m</math> i <math>a \in [1, m - 1]</math>. Można pokazać, że jeżeli <math>m \neq 9</math> jest liczbą nieparzystą złożoną, to co najwyżej <math>\tfrac{1}{4}</math> liczb <math>a</math> stanowią liczby silnie pseudopierwsze. Zatem w&nbsp;przypadku liczb silnie pseudopierwszych nie istnieje odpowiednik liczb Carmichaela. Czyli nie istnieją liczby złożone nieparzyste <math>m</math>, dla których twierdzenie M14 byłoby prawdziwe dla wszystkich podstaw <math>a</math>.
-Czytelnikowi pozostawiamy odszyfrowanie podanej niżej zakodowanej wiadomości. Ze względu na rozmiar musieliśmy podzielić tekst i&nbsp;otrzymaliśmy trzy zakodowane bloki.
+Wynika stąd, że jeżeli dla <math>k</math> różnych liczb <math>a</math> względnie pierwszych z <math>m</math> prawdziwe jest twierdzenie M14, to prawdopodobieństwo uznania liczby złożonej <math>m</math> za pierwszą wynosi <math>\left( \tfrac{1}{4} \right)^k</math>.
-C<sub>1</sub> = 1228411078235780067165277802337600665865387220034514894292654793454492777859429937501850347835450261<br/>
-C<sub>2</sub> = 1212270919532485597119464911345613794658433495925582794819870422454753698249874400827689168074862675<br/>
-C<sub>3</sub> = 1407997868763350498310642273976637553443290951270357250985396471705600151258961305510222246198960667<br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga M17</span><br/>
+Wykorzystując twierdzenie M14, możemy napisać w&nbsp;PARI/GP program wykonujący test Millera-Rabina dla ustalonej podstawy.
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q19</span><br/>
+ <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, a) =
-Omówiliśmy dokładnie metodę szyfrowania RSA i&nbsp;Czytelnik powinien mieć już jasność, że metodą tą możemy szyfrować tylko liczby. Jeśli chcemy zaszyfrować tekst, to musi najpierw zostać zapisany w&nbsp;postaci liczby (ciągu cyfr). Podaliśmy też dwie proste metody takiej zamiany (zobacz Q13 i&nbsp;Q16).
+ {
+ '''local'''(d, k, r, x);
+ 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);
+ }</span>
-W dalszej części artykułu pisząc o&nbsp;szyfrowaniu metodą RSA, będziemy mieli najczęściej na myśli dwie czynności wykonywanie łącznie: zamianę tekstu na liczbę (ustaloną wcześniej metodą) i&nbsp;właściwą operację szyfrowania. Podobnie pisząc o&nbsp;odszyfrowaniu, też zazwyczaj będziemy mieli myśli dwie czynności: właściwą operację odszyfrowywania i&nbsp;zamianę otrzymanej liczby na tekst.
+Zauważmy, że nie musimy sprawdzać, czy <math>\gcd (a, m) = 1</math>, bo jeśli tak nie jest, to dla takiej podstawy powyższy test i tak wykryje złożoność liczby <math>m</math>. Istotnie, jeżeli <math>\gcd (a, m) = g > 1</math>, to rozważając kongruencje z twierdzenia M14
+::<math>a^d \equiv 1 \!\! \pmod{m}</math>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q20</span><br/>
+::<math>a^{2^k d} \equiv - 1 \!\! \pmod{m}</math>
-Zwróćmy uwagę na to, że w&nbsp;przypadku pomyłki i&nbsp;zaszyfrowania wiadomości naszym kluczem prywatnym <math>(m, d)</math> możliwe będzie jej odczytanie przez każdą osobę, która zna nasz klucz publiczny <math>(m, e)</math>. Istotnie, niech <math>C = R_m (B^d)</math>. Łatwo pokażemy, że <math>B = R_m (C^e)</math>.
-::<math>R_m (C^e) \equiv C^e \equiv (B^d)^e \equiv B^{e d} \equiv B^{- k \Phi + 1} \equiv B^{- k (p - 1) (q - 1) + 1} \equiv B \!\! \pmod{m}</math>
+modulo <math>g</math>, otrzymujemy natychmiast
-Fakt ten wykorzystamy do stworzenia podpisu wiadomości.
+::<math>0 \equiv 1 \!\! \pmod{g}</math>
+::<math>0 \equiv - 1 \!\! \pmod{g}</math>
+Co jest niemożliwe. Jednak sprawdzenie, czy <math>\gcd (a, m) = 1</math> jest wskazane, bo operacja ta jest wykonywana bardzo szybko. A jeśli mieliśmy tyle szczęścia, że <math>\gcd (a, m) = g > 1</math>, to jednocześnie znaleźliśmy dzielnik testowanej liczby <math>m</math>, co w przypadku dużych liczb nie jest rzeczą prostą. Zatem program wykonujący <math>k</math> testów Millera-Rabina dla przypadkowych podstaw <math>a</math>, gdzie <math>a \in [2, m - 2]</math>, powinien wyglądać tak
+ <span style="font-size: 90%; color:black;">PrimeTest(m, k) =
+ {
+ '''local'''(a, d, j);
+ '''if'''( m < 2, '''return'''(0) );
+ '''if'''( m % 2 == 0, '''return'''(m == 2) );  \\ testowana liczba jest liczbą parzystą
+ '''setrand'''('''getwalltime'''());  \\ ustawiamy ziarno (ang. seed) generatora liczb losowych
+ j = 0;
+ '''while'''( j++ <= k,
+        a = '''random'''([2, m - 2]);  \\ a jest liczbą losową z przedziału domkniętego [2, m-2]
+        d = '''gcd'''(a, m);
+        '''if'''( d > 1, '''return'''(0) );  \\ testowana liczba jest liczbą złożoną podzielną przez d
+        '''if'''( !isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, a), '''return'''(0) );  \\ testowana liczba jest liczbą złożoną
+      );
+ '''return'''(1);  \\ testowana liczba jest prawdopodobnie liczbą pierwszą
+ }</span>
+Testując dla pięciu przypadkowych podstaw, trudno znaleźć liczbę, dla której wartość funkcji <code>PrimeTest()</code> byłaby różna od <code>isprime()</code>. Nam się to nie udało.
-== Kryptograficzne funkcje haszujące ==
+ <span style="font-size: 90%; color:black;">'''forstep'''(j = 10^6+1, 10^7, 2, '''if'''( PrimeTest(j, 5) != '''isprime'''(j), '''print'''(j) ))</span>
-<span style="font-size: 110%; font-weight: bold;">Definicja Q21</span><br/>
-Funkcja haszująca<ref name="hashfunction1"/> przypisuje każdemu ciągowi bitów o&nbsp;dowolnej (ale skończonej) długości ciąg bitów o&nbsp;stałej długości.
+<span style="font-size: 110%; font-weight: bold;">Zadanie M18</span><br/>
+Pokazać, że jeżeli liczba <math>m</math> jest SPSP(<math>a</math>), to jest PSP(<math>a</math>).
-<span style="font-size: 110%; font-weight: bold;">Przykład Q22</span><br/>
+{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
-Bardzo prosta funkcja haszująca przypisuje każdemu ciągowi osiem pierwszych bitów tego ciągu (w przypadku, gdy ciąg jest za krótki, wystarczy powtórzyć go odpowiednią liczbę razy). Tak określona funkcja nie jest dobrą funkcją haszującą i&nbsp;ze wszystkich wymagań (które wymienimy niżej) spełnia tylko jeden: możemy szybko obliczyć wynik.
+Z założenia <math>m</math> jest SPSP(<math>a</math>), zatem spełniony jest dokładnie jeden z&nbsp;warunków
-Innym przykładem funkcji haszującej może być funkcja, która oblicza sumę kodów ASCII kolejnych znaków modulo <math>256</math>. Ta funkcja, podobnie jak poprzednia, jedynie szybko oblicza wynik.
+:* <math>a^d \equiv 1 \pmod m</math>
+:* <math>a^{2^k \cdot d} \equiv - 1 \pmod m</math>, dla pewnego <math>k \in [0, r - 1]</math>
-Druga funkcja jest lepsza od pierwszej, bo każdy znak tekstu wpływa na uzyskany wynik. Co prawda ciągi znaków, których suma kodów ASCII wynosi 256 (np. "8dd") możemy dodawać bezkarnie, jednak uwzględniając, że wiadomość nie jest ciągiem przypadkowych znaków, modyfikacja wiadomości tak, aby hasz pozostał niezmieniony, będzie wymagała pewnego wysiłku.
+gdzie <math>m - 1 = 2^r \cdot d</math>, przy czym <math>d</math> jest liczbą nieparzystą.
+Jeżeli spełniony jest pierwszy warunek, to
+::<math>(a^d)^{2^r} \equiv 1 \pmod m</math>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q23</span><br/>
+::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math>
-Od dobrej funkcji haszującej oczekujemy, że będzie spełniała następujące warunki
-:* będzie szybko obliczać wynik
+Czyli <math>m</math> jest PSP(<math>a</math>).
-:* (jednokierunkowość) dla zadanej wartości hasza <math>h</math> znalezienie jakiegokolwiek ciągu bitów <math>m</math> takiego, że <math>h = \mathop{\text{hash}}(m)</math> powinno być bardzo trudne
-:* (słaba odporność na kolizje) dla zadanego ciągu bitów <math>m_1</math> znalezienie jakiegokolwiek ciągu bitów <math>m_2 \neq m_1</math> takiego, że <math>\mathop{\text{hash}}(m_2) = \mathop{\text{hash}}(m_1)</math> powinno być bardzo trudne
-:* (silna odporność na kolizje) znalezienie jakichkolwiek dwóch ciągów bitów <math>m_1</math> i <math>m_2</math> takich, że <math>\mathop{\text{hash}}(m_1) = \mathop{\text{hash}}(m_2)</math> powinno być bardzo trudne
-W praktyce oznacza to, że jeżeli dwa łańcuchy mają taki sam hasz, to są one identyczne. To właśnie ta własność decyduje o&nbsp;przydatności funkcji haszującej dla podpisu elektronicznego i&nbsp;innych zastosowań.
+Jeżeli spełniony jest drugi warunek, to
+::<math>(a^{2^k \cdot d})^{2^{r - k}} \equiv (- 1)^{2^{r - k}} \pmod m</math>
+::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math>
-<span style="font-size: 110%; font-weight: bold;">Przykład Q24 (zastosowanie funkcji haszujących)</span><br/>
+Czyli <math>m</math> jest PSP(<math>a</math>).<br/>
-Jeśli chcemy upewnić się, czy przesłana mailem wiadomość nie zastała zmieniona, to wystarczy, że telefonicznie podamy odbiorcy hasz wiadomości.
+&#9633;
+{{\Spoiler}}
-Hasło podawane przy logowaniu powinno być haszowane, a&nbsp;system powinien przechowywać jedynie hasz hasła tak, aby samo hasło pozostawało nikomu nieznane.
-Udostępniając do pobrania plik, możemy udostępnić również jego hasz. Umożliwi to łatwe sprawdzenie użytkownikowi, czy pobrany plik nie został uszkodzony.
+<span style="font-size: 110%; font-weight: bold;">Przykład M19</span><br/>
+Pokażemy, że jeżeli <math>m</math> jest PSP(<math>2</math>), to <math>2^m - 1</math> jest SPSP(<math>2</math>).
+Z założenia <math>m</math> jest złożoną liczbą nieparzystą, zatem <math>N = 2^m - 1</math> jest złożoną liczbą nieparzystą. Ponieważ <math>m</math> jest FPSP(<math>2</math>), to
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q25 (przykłady funkcji haszujących)</span><br/>
+::<math>2^{m - 1} \equiv 1 \pmod m</math>
-Istnieje wiele wykorzystywanych w&nbsp;praktyce funkcji haszujących. Najbardziej znane to: CRC<ref name="CRC"/>, MD5<ref name="MD5"/>, SHA-1<ref name="SHA1"/> oraz funkcje ze standardu SHA-2<ref name="SHA2"/>: SHA-224, SHA-256, SHA-384, SHA-512
-Linux udostępnia wypisane wyżej funkcje jako cksum (CRC), md5sum, sha1sum, sha224sum, sha256sum, sha384sum, sha512sum.
+Wynika stąd natychmiast, że <math>2^{m - 1} - 1 = k m</math>, gdzie <math>k</math> jest liczbą nieparzystą. Zatem
-Na stronie [https://emn178.github.io/online-tools/ GitHub – Online Tools] znajdziemy wiele funkcji haszujących. Możemy policzyć wartości wybranej funkcji dla dowolnego tekstu i&nbsp;dla plików. Zauważmy, że wiele edytorów tekstu automatycznie dodaje znak końca linii<ref name="konieclinii"/> (LF) o&nbsp;kodzie ASCII równym 10 (szesnastkowo 0a) na końcu pliku. Może to powodować różnice przy obliczaniu hasza dla tekstu i&nbsp;dla pliku tekstowego zawierającego ten sam tekst.
+::<math>N - 1 = 2^m - 2 = 2 (2^{m - 1} - 1) = 2 k m</math>
+Widzimy, że liczba <math>2</math> występuje w&nbsp;pierwszej potędze w&nbsp;rozwinięciu liczby <math>N - 1</math> na czynniki pierwsze i&nbsp;łatwo otrzymujemy, że
+::<math>2^{(N - 1) / 2} = 2^{k m} = (2^m)^k = (2^m - 1 + 1)^k = (N + 1)^k \equiv 1 \pmod N</math>
-<span style="font-size: 110%; font-weight: bold;">Przykład Q26</span><br/>
+Czyli <math>N = 2^m - 1</math> jest SPSP(<math>2</math>).
-Dla przykładu rozważmy, często używaną, funkcję haszującą SHA-256. Generuje ona 256-bitowy hasz, który zapisujemy, podając 64 cyfry w&nbsp;zapisie szesnastkowym. Każdą cyfrę w&nbsp;układzie szesnastkowym można zapisać w&nbsp;postaci 4 zer i&nbsp;jedynek w&nbsp;układzie dwójkowym (czterech bitów).
-::<math>0 = 0000, \ldots, 9 = 1001, a = 1010, \ldots, f = 1111</math>
-Dla tekstu
-''Polskie litery i cyfry: ąćęłńóśźżĄĆĘŁŃÓŚŹŻ 0123456789''
+<span style="font-size: 110%; font-weight: bold;">Przykład M20</span><br/>
+Tabela zawiera najmniejsze liczby silnie pseudopierwsze dla podstaw <math>a</math> od <math>2</math> do <math>15</math>
-otrzymujemy hasz
+ <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=1; '''forstep'''(m=3, 20000, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, a)  &&  !'''isprime'''(m), '''print'''("a=", a, "  m=", m); s++ ); '''if'''( s>5, '''break'''() ) ))</span>
-a86397d5e16611466e82376cc9f4d367ecbcd4af6d4418a5d3a130e8ad9d98d
+::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
+! &nbsp;&nbsp;<math>\boldsymbol{a}</math>&nbsp;&nbsp; !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math>
+|-
+|   || <math>2047</math> || <math>121</math> || <math>341</math> || <math>781</math> || <math>217</math> || <math>25</math> || <math>9</math> || <math>91</math> || <math>9</math> || <math>133</math> || <math>91</math> || <math>85</math> || <math>15</math> || <math>1687</math>
+|-
+|   || <math>3277</math> || <math>703</math> || <math>1387</math> || <math>1541</math> || <math>481</math> || <math>325</math> || <math>65</math> || <math>121</math> || <math>91</math> || <math>793</math> || <math>133</math> || <math>1099</math> || <math>841</math> || <math>3277</math>
+|-
+|   || <math>4033</math> || <math>1891</math> || <math>2047</math> || <math>5461</math> || <math>1111</math> || <math>703</math> || <math>481</math> || <math>671</math> || <math>1729</math> || <math>2047</math> || <math>145</math> || <math>5149</math> || <math>2743</math> || <math>6541</math>
+|-
+|   || <math>4681</math> || <math>3281</math> || <math>3277</math> || <math>5611</math> || <math>1261</math> || <math>2101</math> || <math>511</math> || <math>703</math> || <math>4187</math> || <math>4577</math> || <math>247</math> || <math>7107</math> || <math>3277</math> || <math>14041</math>
+|-
+|   || <math>8321</math> || <math>8401</math> || <math>4033</math> || <math>7813</math> || <math>2701</math> || <math>2353</math> || <math>1417</math> || <math>1541</math> || <math>6533</math> || <math>5041</math> || <math>1649</math> || <math>8911</math> || <math>5713</math> || <math>14701</math>
+|}
-Czytelnik powinien zwrócić uwagę, że nawet niewielka zmiana tekstu (np. zmiana lub dodanie jednego znaku) spowoduje wygenerowanie zupełnie innego hasza.
+<span style="font-size: 110%; font-weight: bold;">Przykład M21</span><br/>
+Tabela pokazuje ilość liczb silnie pseudopierwszych dla podstaw <math>a</math> od <math>2</math> do <math>15</math>
+ <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=0; '''forstep'''(k=3, 10^6, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(k, a)  &&  !'''isprime'''(k), s++ )); '''print'''("a= ", a, "   ", s))</span>
+::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
+! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math>
+|-
+| #SPSP(<math>a</math>) <math> < 10^6</math> || <math>46</math> || <math>73</math> || <math>97</math> || <math>64</math> || <math>73</math> || <math>66</math> || <math>127</math> || <math>161</math> || <math>62</math> || <math>58</math> || <math>90</math> || <math>71</math> || <math>74</math> || <math>45</math>
+|-
+| #SPSP(<math>a</math>) <math> < 10^7</math> || <math>162</math> || <math>207</math> || <math>305</math> || <math>199</math> || <math>203</math> || <math>177</math> || <math>377</math> || <math>459</math> || <math>158</math> || <math>157</math> || <math>251</math> || <math>193</math> || <math>190</math> || <math>148</math>
+|-
+| #SPSP(<math>a</math>) <math> < 10^8</math> || <math>488</math> || <math>582</math> || <math>833</math> || <math>475</math> || <math>486</math> || <math>446</math> || <math>1023</math> || <math>1241</math> || <math>437</math> || <math>430</math> || <math>666</math> || <math>472</math> || <math>440</math> || <math>398</math>
+|-
+| #SPSP(<math>a</math>) <math> < 10^9</math> || <math>1282</math> || <math>1514</math> || <math>2162</math> || <math>1268</math> || <math>1232</math> || <math>1163</math> || <math>2599</math> || <math>3210</math> || <math>1113</math> || <math>1125</math> || <math>1655</math> || <math>1142</math> || <math>1151</math> || <math>1041</math>
+|}
-== Podpisywanie dokumentów jawnych ==
+Widzimy, że liczb silnie pseudopierwszych jest znacznie mniej niż liczb pseudopierwszych Fermata.
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q27</span><br/>
-Zauważmy, że przekazywanie wiadomości (jawnych lub nie) wymaga wcześniejszego ustalenia sposobu komunikowania się. Może to być konto mailowe (jawne lub używane tylko do kontaktów tajnych), umówiona skrytka itd. Wynika stąd, że odbiorca zawsze zna nadawcę (wie, od kogo otrzymał przesyłkę).
-Ponieważ musimy liczyć się z&nbsp;tym, że ustalony kanał łączności może zostać przejęty, a&nbsp;przekaz zmieniony, to stosujemy różnego rodzaju zabezpieczenia, których celem jest ochrona integralności przekazu.
+<span style="font-size: 110%; font-weight: bold;">Uwaga M22</span><br/>
+Interesujące i&nbsp;pożyteczne będzie zbadanie najmniejszych liczb silnie pseudopierwszych dla wielu podstaw. Niech badanymi podstawami będą kolejne liczby pierwsze. Najmniejszą liczbę SPSP(<math>2</math>) już znamy: <math>2047</math>. Najmniejszą liczbę, która jest jednocześnie SPSP(<math>2</math>) i&nbsp;SPSP(<math>3</math>) musimy poszukać. Prostym poleceniem
+ <span style="font-size: 90%; color:black;">'''forstep'''(m=3, 10^7, 2, '''if'''( '''isprime'''(m), '''next'''() ); '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 3), '''print'''("m=", m) ))</span>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q28</span><br/>
+znajdujemy, że <math>m = 1373653</math>. Więcej czasu będzie wymagało znalezienie liczby jednocześnie silnie pseudopierwszej względem podstaw <math>2, 3, 5</math>. Poleceniem
-Powiedzmy, że Bolek chce przekazać ważny dokument do Urzędu. Jednak Urząd chce mieć pewność, że tak ważny dokument rzeczywiście sporządził Bolek, a&nbsp;nie ktoś inny, kto tylko pod Bolka się podszywa. Oczywiście można taki dokument przekazać osobiście, ale co zrobić w&nbsp;sytuacji, gdy jest to niemożliwe, a&nbsp;dostępny jest internet?
-Jeśli Bolek potrafi szyfrować wiadomości metodą RSA i&nbsp;udostępnił swój klucz publiczny <math>(m, e)</math> Urzędowi, to może postąpić następująco
+ <span style="font-size: 90%; color:black;">'''forstep'''(m=3, 10^8, 2, '''if'''( '''isprime'''(m), '''next'''() ); '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 3) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 5), '''print'''("m=", m) ))</span>
-:# sporządzić ów ważny dokument (powiedzmy DokB) w&nbsp;postaci pliku (ewentualnie papierowy dokument zeskanować)
+znajdujemy, że szukana liczba to <math>m = 25326001</math>.
-:# obliczyć hasz pliku DokB: <math>\; h_B = \mathop{\text{SHA256}}( \text{DokB} )</math>
-:# zaszyfrować hasz <math>h_B</math> swoim '''kluczem prywatnym''' <math>(m, d)</math> (zobacz Q20)
-:#* zaszyfrowany hasz <math>h_B</math> jest podpisem Bolka (co za chwilę stanie się jasne)
-:# tak zaszyfrowany hasz wpisać w&nbsp;treści maila i&nbsp;załączyć plik DokB
-Jak przebiega weryfikacja odebranej wiadomości?
+Stosując bardziej wyrafinowane metody<ref name="SPSPtoNbases"/><ref name="Jaeschke1"/> znaleziono wartości liczb silnie pseudopierwszych względem wielu podstaw, które są kolejnymi liczbami pierwszymi, dla większej ilości liczb pierwszych<ref name="A014233"/>. Dla przykładu
-:# Urząd odbiera mail od Bolka i&nbsp;pobiera załącznik (nazwijmy go DokU, bo nie wiemy, czy nie został zmieniony)
+::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
-:# Urząd oblicza hasz załączonego pliku DokU: <math>\; h_U = \mathop{\text{SHA256}}( \text{DokU} )</math>
+! <math>\boldsymbol{n}</math> !! <math>\boldsymbol{m}</math>
-:# '''kluczem publicznym''' Bolka Urząd odszyfrowuje otrzymany w&nbsp;mailu zaszyfrowany hasz <math>h_B</math> (zobacz Q20)
+|-
-:# z&nbsp;równości <math>h_B = h_U</math> wynika, że dokumenty DokB i&nbsp;DokU są identyczne (zobacz Q23)
+|  <math>1</math> || <math>2047</math>
+|-
+|  <math>2</math> || <math>1373653</math>
+|-
+|  <math>3</math> || <math>25326001</math>
+|-
+|  <math>4</math> || <math>3215031751</math>
+|-
+|  <math>5</math> || <math>2152302898747</math>
+|-
+|  <math>6</math> || <math>3474749660383</math>
+|-
+|  <math>7</math> || <math>341550071728321</math>
+|}
+Podane w&nbsp;prawej kolumnie liczby <math>m</math> są najmniejszymi liczbami jednocześnie silnie pseudopierwszymi względem podstaw <math>p_1, \ldots, p_n</math>. Zauważmy, że wyniki te mają bardzo praktyczne zastosowanie. Przykładowo, jeśli <math>m</math> przechodzi test Millera-Rabina dla siedmiu podstaw <math>a = 2, 3, 5, 7, 11, 13, 17</math> i&nbsp;jest liczbą mniejszą od <math>3.41 \cdot 10^{14}</math>, to jest z&nbsp;pewnością liczbą pierwszą.
-Jest tak, ponieważ z&nbsp;równości <math>h_B = h_U</math> wynika, że zaszyfrowany hasz <math>h_B</math> musiał pochodzić od Bolka, bo został zaszyfrowany jego kluczem '''prywatnym''', do którego nikt, poza nim, nie ma dostępu. Dlatego zaszyfrowany kluczem prywatnym Bolka hasz <math>h_B</math> jest tym samym, co jego podpis i&nbsp;potwierdza to, że plik DokB (którego hasz jest równy <math>h_B</math>) został sporządzony przez Bolka.
-Ujmując inaczej, każdy może przedstawić się w&nbsp;mailu jako Bolek, dołączyć spreparowany plik, policzyć hasz tego pliku, ale nie będzie w&nbsp;stanie zaszyfrować tego hasza kluczem '''prywatnym''' Bolka, bo klucz ten jest tajny i&nbsp;niedostępny dla nikogo poza Bolkiem.
+<span style="font-size: 110%; font-weight: bold;">Uwaga M23</span><br/>
+Pomysł przedstawiony w uwadze M22 ma proste uogólnienie. Niech <math>A_r = \{ a_1, \ldots, a_r \}</math> będzie zbiorem liczb naturalnych większych od <math>1</math>. Możemy teraz szukać takiego zbioru <math>A_r</math>, dla którego najmniejsza liczba silnie pseudopierwsza jednocześnie względem podstaw <math>a_1, \ldots, a_r</math> będzie największa ze wszystkich rozpatrywanych przypadków.
+Dla przykładu przyjmijmy, że
+:*&nbsp;&nbsp;&nbsp;<math>r = 3</math>
+:*&nbsp;&nbsp;&nbsp;<math>a_k < 100</math>
+:*&nbsp;&nbsp;&nbsp;<math>a_k</math> są liczbami pierwszymi
+Okazuje się<ref name="Jaeschke1"/><ref name="MillerRabin1"/>, że przy takich założeniach szukanym zbiorem jest <math>A_3 = \{ 2, 7, 61 \}</math>. Najmniejszą liczbą silnie pseudopierwszą jednocześnie względem podstaw <math>2, 7, 61</math> jest liczba <math>4759123141</math>. Łatwo znajdujemy, że dla <math>m < 3 \cdot 10^{10}</math> istnieje osiem liczb silnie pseudopierwszych jednocześnie względem podstaw <math>2, 7, 61</math>:
-== Podpisywanie dokumentów tajnych ==
+::<math>4759123141, 8411807377, 11207066041, 11711154457, 12015212653, 18074903681, 19632812033, 27913980641</math>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q29</span><br/>
+Korzystając z tego rezultatu możemy napisać prosty program, który rozstrzyga w sposób pewny, czy badana liczba <math>m < 1.12 \cdot 10^{10}</math> jest liczbą pierwszą.
-Powiedzmy, że Bolek ma ważną informację i&nbsp;chce ją przekazać do Agencji. Oczywiście informacji nie może przeczytać nikt inny, a&nbsp;Agencja musi mieć pewność, że źródłem tej ważnej informacji jest rzeczywiście Bolek, a&nbsp;nie ktoś inny, kto tylko pod Bolka się podszywa. Tym razem Bolek na pewno potrafi szyfrować wiadomości metodą RSA, a&nbsp;jego klucz publiczny <math>(m, e)</math> jest z&nbsp;pewnością znany Agencji. Co więcej, Bolek zna klucz publiczny Agencji <math>(M, E)</math>, którego ma używać do komunikowania się z&nbsp;Agencją. W&nbsp;tym przypadku Bolek postępuje następująco
-:# oblicza hasz wiadomości <math>h_B = \mathop{\text{SHA256}}( \text{tekst} )</math>
+Ponieważ teraz podstawy <math>a</math> są ustalone, a testowana liczba <math>m</math> może być dowolna, to musimy wykluczyć sytuacje, że <math>\gcd (a, m) > 1</math>. Musimy tak zrobić, bo '''pierwszość''' liczby <math>m</math> nie zostanie wykryta, gdy <math>\gcd (a, m) = g > 1</math> (zobacz M17).
-:# szyfruje hasz <math>h_B</math> swoim '''kluczem prywatnym''' <math>(m, d)</math>
-:# umieszcza zaszyfrowany hasz <math>h_B</math> jako ostatnią linię tekstu wiadomości
-:# szyfruje całość (tekst wiadomości + zaszyfrowany hasz <math>h_B</math>) kluczem publicznym Agencji <math>(M, E)</math>
-:# umieszcza cały zaszyfrowany tekst w&nbsp;pliku i&nbsp;wysyła jako załącznik maila do Agencji
-Agencja
+:*&nbsp;Jeżeli podstawa <math>a</math> jest liczbą pierwszą, to wystarczy zbadać, czy <math>R_a (m) = 0</math>. Jeśli tak, to tylko w przypadku, gdy <math>m = a</math> liczba <math>m</math> jest liczbą pierwszą.
-:# pobiera załącznik
+:*&nbsp;Jeżeli podstawa <math>a</math> jest liczbą złożoną, powiedzmy <math>a = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>, to wystarczy zbadać, czy dla pewnego <math>i = 1, \ldots, s</math> jest <math>R_{p_i} (m) = 0</math>. Jeśli tak, to tylko w przypadku, gdy <math>m = p_i</math> liczba <math>m</math> jest liczbą pierwszą.
-:# tekst z&nbsp;załącznika odszyfrowuje kluczem prywatnym Agencji <math>(M, D)</math>
-:# z&nbsp;ostatniej linii pliku odczytuje zaszyfrowany hasz <math>h_A</math> tekstu otrzymanej wiadomości
-:# deszyfruje hasz <math>h_A</math> wiadomości '''kluczem publicznym''' Bolka <math>(m, e)</math>
-:# oblicza hasz <math>h_B</math> wiadomości od Bolka
-:# równość <math>h_B = h_A</math> potwierdza, że wiadomość nie została zmieniona i&nbsp;przekazał ją do Agencji Bolek
-Zauważmy, że '''klucz publiczny''' Agencji może być wiedzą poufną, ale z&nbsp;pewnością nie jest tak dobrze strzeżony, jak '''klucze prywatne'''. Agencja nie może zakładać, że zaszyfrowany jej kluczem publicznym plik nie został spreparowany. Dopiero po odszyfrowaniu pliku, obliczeniu hasza wiadomości i&nbsp;potwierdzenia zgodności tego hasza z&nbsp;haszem zapisanym w&nbsp;ostatniej linii pliku (który został zaszyfrowany '''kluczem prywatnym''' Bolka) Agencja ma pewność, że plik stworzył i&nbsp;wysłał Bolek.
+Poniżej przedstawiamy odpowiedni kod w PARI/GP. Zauważmy, że wstępne sprawdzanie pierwszości nieprzypadkowo uwzględnia wszystkie liczby pierwsze <math>p \leqslant 61</math>. Wybraliśmy taki zakres, aby zostały objęte podstawy <math>2, 7, 61</math>.
+ <span style="font-size: 90%; color:black;">MyIsPrime(m) =
+ {
+ '''if'''( m < 2, return(0) );
+ '''forprime'''(p = 2, 61, '''if'''( m % p == 0, '''return'''(m == p) ));
+ '''if'''( m == 4759123141 || m == 8411807377, '''return'''(0) );
+ '''return'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 7) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 61) );
+ }</span>
-<span style="font-size: 110%; font-weight: bold;">Uwaga Q30</span><br/>
-Zwróćmy uwagę, że '''jeżeli korzystamy''' z&nbsp;funkcji <code>TextToNumber()</code> i <code>NumberToText()</code> (zobacz Q16), a&nbsp;jednocześnie chcemy podpisywać szyfrowane wiadomości, to wiadomości '''nie mogą''' zawierać znaków innych niż znaki ASCII od&nbsp;32 do&nbsp;126.
-Jest tak dlatego, że funkcja <code>TextToNumber()</code> zgubi informację o&nbsp;innych znakach w&nbsp;wiadomości, a&nbsp;funkcja <code>NumberToText()</code> już tej informacji nie odtworzy. Zatem hasz wysyłanej wiadomości i&nbsp;hasz otrzymanej wiadomości (po odszyfrowaniu) nigdy nie będą identyczne w&nbsp;przypadku użycia znaków innych niż znaki ASCII od&nbsp;32 do&nbsp;126.
+== Uzupełnienie ==
+<span style="font-size: 110%; font-weight: bold;">Uwaga M24</span><br/>
+W funkcji <code>isPrimeOr<span style="background-color: #fee481;">SPSP</span>()</code> wykorzystaliśmy zaimplementowane w&nbsp;PARI/GP funkcje:
+* <code>gcd(a, b)</code> – znajduje największy wspólny dzielnik liczb a i b
+* <code>valuation(a, b)</code> – znajduje największą wartość liczby <math>r</math> taką, że <math>b^r \mid a</math>
+Wprowadzenie tych funkcji pozwoliło zwiększyć czytelność kodu, ale bez trudu możemy sami je napisać:
+ <span style="font-size: 90%; color:black;">gcd2(a, b) =
+ {
+ '''local'''(r);
+ '''if'''( b == 0, '''return'''('''abs'''(a)) );
+ r = a % b;
+ '''while'''( r > 0, a = b; b = r; r = a % b );
+ '''return'''('''abs'''(b));
+ }</span>
+ <span style="font-size: 90%; color:black;">valuation2(a, b) =
+ {
+ '''local'''(s);
+ s = 0;
+ '''while'''(a % b == 0, s++; a = a / b);
+ '''return'''(s);
+ }</span>
@@ Linia 632: / Linia 668: @@
-== Przypisy ==
-<references>
-<ref name="DiffieHellman1">Whitfield Diffie and Martin E. Hellman, ''New Directions in Cryptography'', IEEE Transactions on Information Theory, Vol.&nbsp;22, No.&nbsp;6, 1976 ([https://ee.stanford.edu/~hellman/publications/24.pdf LINK])</ref>
-<ref name="DiffieHellman2">Wikipedia, ''Protokół Diffiego-Hellmana'', ([https://pl.wikipedia.org/wiki/Protok%C3%B3%C5%82_Diffiego-Hellmana Wiki-pl]), ([https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange Wiki-en])</ref>
-<ref name="generator1">Liczba <math>g</math> powinna (ale nie musi) być generatorem modulo <math>p</math>. Dlaczego tak jest, wyjaśnimy w&nbsp;dalszej części tekstu.</ref>
-<ref name="funkcjaphi1">Wikipedia, ''Funkcja φ'', ([https://pl.wikipedia.org/wiki/Funkcja_%CF%86 Wiki-pl]), ([https://en.wikipedia.org/wiki/Euler%27s_totient_function Wiki-en])</ref>
-<ref name="RSA1">R. Rivest, A. Shamir and L. Adleman, ''A Method for Obtaining Digital Signatures and Public-Key Cryptosystems'', Communications of the ACM, Volume 21, Issue 2, Feb. 1978, pp. 120-126</ref>
-<ref name="RSA2">Wikipedia, ''RSA (kryptografia)'', ([https://pl.wikipedia.org/wiki/RSA_(kryptografia) Wiki-pl]), ([https://en.wikipedia.org/wiki/RSA_(cryptosystem) Wiki-en])</ref>
-<ref name="BonehDurfee1">Dan Boneh and Glenn Durfee, ''Cryptanalysis of RSA with Private Key d Less Than N<sup>0.292</sup>'', IEEE Transactions on Information Theory, Vol.&nbsp;46, No.&nbsp;4, 2000</ref>
-<ref name="RSA250">Wikipedia, ''RSA numbers'', ([https://en.wikipedia.org/wiki/RSA_numbers#RSA-250 Wiki-en])</ref>
+== Przypisy ==
-<ref name="ASCII">Wikipedia, ''ASCII'', ([https://pl.wikipedia.org/wiki/ASCII Wiki-pl]), ([https://en.wikipedia.org/wiki/ASCII Wiki-en])</ref>
+<references>
-<ref name="hashfunction1">Wikipedia, ''Cryptographic hash function'', ([https://en.wikipedia.org/wiki/Cryptographic_hash_function Wiki-en]), ([https://pl.wikipedia.org/wiki/Funkcja_skr%C3%B3tu#Kryptograficzne_funkcje_skr%C3%B3tu Wiki-pl])</ref>
+<ref name="Carmichael1">W. R. Alford, Andrew Granville and Carl Pomerance, ''There are Infinitely Many Carmichael Numbers'', Annals of Mathematics, '''140''', (1994),  703-722</ref>
-<ref name="CRC">Wikipedia, ''Cykliczny kod nadmiarowy'', ([https://pl.wikipedia.org/wiki/Cykliczny_kod_nadmiarowy Wiki-pl]), ([https://en.wikipedia.org/wiki/Cyclic_redundancy_check Wiki-en])</ref>
+<ref name="Carmichael2">Glyn Harman, ''On the Number of Carmichael Numbers up to x'', Bull. London Math. Soc. 37 (2005) 641–650</ref>
-<ref name="MD5">Wikipedia, ''MD5'', ([https://pl.wikipedia.org/wiki/MD5 Wiki-pl]), ([https://en.wikipedia.org/wiki/MD5 Wiki-en])</ref>
+<ref name="Carmichael3">Glyn Harman, ''Watt’s Mean Value Theorem and Carmichael Numbers'', International Journal of Number Theory, Vol. 4, No. 2 (2008) 241–248</ref>
-<ref name="SHA1">Wikipedia, ''SHA-1'', ([https://pl.wikipedia.org/wiki/SHA-1 Wiki-pl]), ([https://en.wikipedia.org/wiki/SHA-1 Wiki-en])</ref>
+<ref name="Miller1">Gary L. Miller, ''Riemann's Hypothesis and Tests for Primality'', Journal of Computer and System Sciences '''13''', 300-317 (1976)</ref>
-<ref name="SHA2">Wikipedia, ''SHA-2'', ([https://pl.wikipedia.org/wiki/SHA-2 Wiki-pl]), ([https://en.wikipedia.org/wiki/SHA-2 Wiki-en])</ref>
+<ref name="Rabin1">Michael O. Rabin, ''Probabilistic Algorithm for Testing Primality'', Journal of Number Theory '''12''', 128-138 (1980)</ref>
-<ref name="konieclinii">Wikipedia, ''Koniec linii'', ([https://pl.wikipedia.org/wiki/Koniec_linii Wiki-pl]), ([https://en.wikipedia.org/wiki/Newline Wiki-en])</ref>
+<ref name="SPSPtoNbases">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</ref>
-</references>
+<ref name="Jaeschke1">Gerhard Jaeschke, ''On Strong Pseudoprimes to Several Bases'', Mathematics of Computation, Vol. 61, No. 204 (Oct., 1993), 915-926</ref>
+<ref name="A014233">On-Line Encyclopedia of Integer Sequences, ''Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness'', ([https://oeis.org/A014233 A014233])</ref>
+<ref name="MillerRabin1">Wikipedia, ''Test Millera-Rabina'', ([https://pl.wikipedia.org/wiki/Test_Millera-Rabina#Dok%C5%82adno%C5%9B%C4%87_testu_i_wersje_deterministyczne Wiki-pl]), ([https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases Wiki-en])</ref>
+</references>