Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze: Różnice pomiędzy wersjami
(Nie pokazano 28 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
Linia 5: | Linia 5: | ||
− | == | + | == Potęgowanie modulo == |
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span style="font-size: 110%; font-weight: bold;">Uwaga M1</span><br/> |
− | + | 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 | |
− | : | + | ::<math>2^{340} - 1 = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115775</math> |
− | : | ||
− | + | ::::<math>\;\;\; = 341 \cdot 6568166399348399444449977362370804334667582103327417990909058947107894050381703652143335757394742275</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 dzielenia <math>a^n</math> przez <math>m</math>, czyli potęgowania modulo <math>m</math>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | <span style="font-size: 110%; font-weight: bold;">Uwaga M2</span><br/> | |
+ | Wykorzystując wzór rekurencyjny | ||
− | ::<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> | ||
− | |||
− | + | możemy napisać w PARI/GP prosty program do potęgowania modulo: | |
+ | <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 funkcji <code>modPower()</code> nie występują wyrażenia o wartości większej od <math>m^2</math>. | |
− | |||
− | |||
− | |||
+ | Zauważmy jeszcze, że PARI/GP umożliwia szybkie potęgowanie modulo i nie musimy korzystać z funkcji <code>modPower()</code>. Wystarczy napisać | ||
+ | <span style="font-size: 90%; color:black;">'''lift'''( '''Mod'''(a, m)^d )</span> | ||
− | < | + | 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;">Uwaga M3</span><br/> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | ||
Wykorzystując wzór rekurencyjny | Wykorzystując wzór rekurencyjny | ||
− | ::<math>a | + | ::<math>a \cdot b = \left\{ \begin{array}{cll} |
− | a & & \text{gdy } | + | a & & \text{gdy } b = 1 \\ |
− | + | 2 a \cdot \frac{b}{2} & & \text{gdy } b \text{ jest parzyste} \\ | |
− | a \cdot | + | a + 2 a \cdot \frac{b - 1}{2} & & \text{gdy } b \text{ jest nieparzyste} \\ |
\end{array} \right.</math> | \end{array} \right.</math> | ||
− | możemy napisać w | + | możemy napisać w PARI/GP prosty program do mnożenia modulo: |
− | <span style="font-size: 90%; color:black;"> | + | <span style="font-size: 90%; color:black;">modMult(a, b, m) = |
− | \\ a | + | \\ a, b - czynniki, m - moduł |
{ | { | ||
'''local'''(w); | '''local'''(w); | ||
'''if'''( m == 1, '''return'''(0) ); | '''if'''( m == 1, '''return'''(0) ); | ||
a = a % m; | a = a % m; | ||
− | w = | + | b = b % m; |
− | '''while'''( | + | w = 0; |
− | '''if'''( | + | '''while'''( b > 0, |
− | a = ( | + | '''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); | '''return'''(w); | ||
Linia 88: | Linia 85: | ||
− | + | 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 <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. | ||
Linia 98: | Linia 97: | ||
Liczby złożone nieparzyste spełniające równanie Fermata, otrzymały własną nazwę. | Liczby złożone nieparzyste spełniające równanie Fermata, otrzymały własną nazwę. | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja | + | <span style="font-size: 110%; font-weight: bold;">Definicja M4</span><br/> |
Jeżeli <math>m</math> jest liczbą złożoną nieparzystą i dla pewnego <math>a \in \mathbb{Z}</math> prawdziwa jest kongruencja | Jeżeli <math>m</math> jest liczbą złożoną nieparzystą i dla pewnego <math>a \in \mathbb{Z}</math> prawdziwa jest kongruencja | ||
::<math>a^{m - 1} \equiv 1 \pmod m</math> | ::<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 | + | 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;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga M5</span><br/> |
Zauważmy, że w definicji liczb pseudopierwszych Fermata nie musimy dodatkowo dołączać warunku <math>\gcd (a, m) = 1</math>, bo wynika on z przyjętej definicji. Mamy | Zauważmy, że w definicji liczb pseudopierwszych Fermata nie musimy dodatkowo dołączać warunku <math>\gcd (a, m) = 1</math>, bo wynika on z przyjętej definicji. Mamy | ||
Linia 114: | Linia 113: | ||
Zatem <math>\gcd (a, m) = 1</math>. | Zatem <math>\gcd (a, m) = 1</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 | ||
+ | ::<math>a^{m - 1} \equiv 1 \pmod{m}</math> | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | Ponieważ <math>d \mid m</math>, to jest również |
+ | |||
+ | ::<math>a^{m - 1} \equiv 1 \pmod{d}</math> | ||
+ | |||
+ | Ale modulo <math>d</math> otrzymujemy natychmiast | ||
+ | |||
+ | ::<math>0 \equiv 1 \pmod{d}</math> | ||
+ | |||
+ | Co jest niemożliwe, czyli <math>m</math> nie jest PSP(<math>a</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. | Dla każdej podstawy <math>a \geqslant 2</math> istnieje nieskończenie wiele liczb pseudopierwszych Fermata. | ||
Linia 128: | Linia 141: | ||
::<math>a^p + 1 = (a + 1) (a^{p - 1} - a^{p - 2} + \ldots + a^2 - a + 1)</math> | ::<math>a^p + 1 = (a + 1) (a^{p - 1} - a^{p - 2} + \ldots + a^2 - a + 1)</math> | ||
− | Czyli <math>a - 1 | + | Czyli <math>a - 1 \mid a^p - 1</math> oraz <math>a + 1 \mid a^p + 1</math>. |
Linia 156: | Linia 169: | ||
::<math>a^p - 1 \equiv a - 1 \pmod p</math> | ::<math>a^p - 1 \equiv a - 1 \pmod p</math> | ||
− | Ponieważ <math>(a - 1) | + | Ponieważ <math>(a - 1) \mid (a^p - 1)</math>, to możemy napisać |
::<math>(a - 1) \cdot \left( {\small\frac{a^p - 1}{a - 1}} - 1 \right) \equiv 0 \pmod p</math> | ::<math>(a - 1) \cdot \left( {\small\frac{a^p - 1}{a - 1}} - 1 \right) \equiv 0 \pmod p</math> | ||
Linia 174: | Linia 187: | ||
Wynika stąd, że <math>m \equiv 1 \pmod p</math>. | Wynika stąd, że <math>m \equiv 1 \pmod p</math>. | ||
− | Zbierając mamy <math>2 | + | 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> | ::<math>m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} \equiv 1 \pmod{2 p}</math> | ||
Linia 189: | Linia 202: | ||
::<math>a^{m - 1} = a^{2 k p} = (a^{2 p})^k \equiv 1^k \equiv 1 \pmod m</math> | ::<math>a^{m - 1} = a^{2 k p} = (a^{2 p})^k \equiv 1^k \equiv 1 \pmod m</math> | ||
− | 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ą | + | 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/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 195: | Linia 208: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Przykład M7</span><br/> |
− | Z dowodu twierdzenia | + | 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>. |
<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> | <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: | + | ::{| 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>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> | ||
|- | |- | ||
Linia 218: | Linia 231: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <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 oparciu o twierdzenie Fermata. | Wykorzystując funkcję potęgowania modulo, możemy napisać prosty program do testowania pierwszości liczb w oparciu o twierdzenie Fermata. | ||
− | <span style="font-size: 90%; color:black;"> | + | <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) ); | '''if'''( modPower(a, m-1, m) == 1, '''return'''(1), '''return'''(0) ); | ||
}</span> | }</span> | ||
Linia 229: | Linia 241: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <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> | Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Fermata 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=1; '''forstep'''(m=1, 2000, 2, '''if'''( | + | <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> |
::{| class="wikitable plainlinks" style="font-size: 90%; text-align: right; margin-right: auto;" | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: right; margin-right: auto;" | ||
Linia 250: | Linia 262: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Przykład M10</span><br/> |
Tabela pokazuje ilość liczb pseudopierwszych Fermata dla podstaw <math>a</math> od <math>2</math> do <math>15</math> | Tabela pokazuje ilość liczb pseudopierwszych Fermata 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=1, 10^6, 2, '''if'''( | + | <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> |
::{| class="wikitable plainlinks" style="font-size: 90%; text-align: right; margin-right: auto;" | ::{| 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>\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>\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> |
|} | |} | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <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 istnieje przynajmniej jedna liczba <math> | + | Można pokazać, że jeżeli <math>m</math> jest liczbą nieparzystą złożoną i istnieje przynajmniej jedna liczba <math>w</math> względnie pierwsza z <math>m</math>, taka że |
− | ::<math> | + | ::<math>w^{m - 1} \not\equiv 1 \pmod m</math> |
− | to dla co najmniej połowy liczb <math> | + | to dla co najmniej połowy liczb <math>a \in [1, m - 1]</math> względnie pierwszych z <math>m</math> jest |
− | ::<math> | + | ::<math>a^{m - 1} \not\equiv 1 \pmod m</math> |
Zatem przeprowadzając test Fermata, możemy z 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 przedziału <math>[1, m - 1]</math> możemy z prawdopodobieństwem większym niż <math>1 - \left( \tfrac{1}{2} \right)^k</math> twierdzić, że badana liczba <math>m</math> jest pierwsza. | Zatem przeprowadzając test Fermata, możemy z 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 przedziału <math>[1, m - 1]</math> możemy z prawdopodobieństwem większym niż <math>1 - \left( \tfrac{1}{2} \right)^k</math> twierdzić, że badana liczba <math>m</math> jest pierwsza. | ||
Linia 284: | Linia 296: | ||
::<math>a^{m - 1} \equiv 1 \pmod m</math> | ::<math>a^{m - 1} \equiv 1 \pmod m</math> | ||
− | dla każdego <math>a</math> względnie pierwszego z <math>m</math>. Liczby te nazywamy liczbami Carmichaela i 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 | + | dla każdego <math>a</math> względnie pierwszego z <math>m</math>. Liczby te nazywamy liczbami Carmichaela (zobacz L74 i nn.) i 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>. Test Fermata jest zatem zbyt zawodny, aby można było go stosować. |
+ | |||
+ | <span style="font-size: 110%; font-weight: bold;">Zadanie M12</span><br/> | ||
+ | Pokazać, że jeżeli <math>m</math> jest liczbą złożoną nieparzystą i istnieje liczba <math>w</math> względnie pierwsza z <math>m</math> taka, że | ||
− | + | ::<math>w^{m - 1} \not\equiv 1 \!\! \pmod{m}</math> | |
− | |||
− | ::{| | + | to kongruencja |
− | + | ||
− | + | ::<math>a^{m - 1} \equiv 1 \!\! \pmod{m}</math> | |
− | + | ||
− | + | nie jest prawdziwa dla co najmniej połowy liczb <math>a</math> względnie pierwszych z <math>m</math>. | |
− | + | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | |
− | + | Niech <math>S_b</math> będzie zbiorem wszystkich liczb <math>b</math> względnie pierwszych z <math>m</math> i różnych modulo <math>m</math>, dla których kongruencja | |
− | + | ||
+ | ::<math>a^{m - 1} \equiv 1 \!\! \pmod{m} \qquad \qquad \qquad (1)</math> | ||
+ | |||
+ | jest prawdziwa. Zdefiniujmy zbiór <math>S_w</math> następująco <math>S_w = \{ w b : b \in S_b \}</math>. Zauważmy, że | ||
+ | |||
+ | :* elementy zbioru <math>S_w</math> są wszystkie różne modulo <math>m</math>, bo z założenia <math>w</math> jest liczbą względnie pierwszą z <math>m</math> (zobacz H21 p.1) | ||
+ | |||
+ | :* elementy zbioru <math>S_w</math> są względnie pierwsze z <math>m</math> (zobacz H6) | ||
+ | |||
+ | :* dla każdego elementu zbioru <math>S_w</math> kongruencja <math>(1)</math> nie jest prawdziwa, bo | ||
+ | |||
+ | ::::<math>\left( w b \right)^{m - 1} = w^{m - 1} \cdot b^{m - 1} \equiv w^{m - 1} \not\equiv 1 \!\! \pmod{m}</math> | ||
+ | |||
+ | :* <math>| S_b | + | S_w | \leqslant \varphi (m)</math>, bo elementy zbiorów <math>S_b</math> i <math>S_w</math> nie muszą być wszystkimi liczbami względnie pierwszymi z <math>m</math> | ||
+ | |||
+ | :* <math>| S_b | = | S_w |</math>, co wynika wprost z definicji zbioru <math>S_w</math> | ||
+ | |||
+ | Zatem <math>| S_b | \leqslant \frac{1}{2} \varphi (m)</math>, czyli dla co najmniej połowy liczb <math>a</math> względnie pierwszych z <math>m</math> kongruencja <math>(1)</math> nie jest prawdziwa. Co należało pokazać.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
Linia 309: | Linia 342: | ||
Rozpoczniemy od udowodnienia prostego twierdzenia | Rozpoczniemy od udowodnienia prostego twierdzenia | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie M13</span><br/> |
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>. | 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>. | ||
Linia 317: | Linia 350: | ||
::<math>x^2 \equiv 1 \pmod m</math> | ::<math>x^2 \equiv 1 \pmod m</math> | ||
− | Zatem <math>m | + | Zatem <math>m \mid (x^2 - 1)</math>, czyli <math>m \mid (x - 1) (x + 1)</math>. Ponieważ z założenia <math>m</math> jest liczbą pierwszą nieparzystą, to <math>m</math> dzieli dokładnie jedną z 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 przypadku gdy <math>m</math> jest liczbą pierwszą nieparzystą.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 325: | Linia 358: | ||
Prace Gary'ego Millera<ref name="Miller1"/> i Michaela Rabina<ref name="Rabin1"/> pozwoliły sformułować znacznie silniejszy test. Podstawą tego testu jest następujące twierdzenie | Prace Gary'ego Millera<ref name="Miller1"/> i 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;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie M14</span><br/> |
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 | 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 | ||
Linia 340: | Linia 373: | ||
::<math>\begin{array}{l} | ::<math>\begin{array}{l} | ||
− | u_0 = a^d\\ | + | u_0 = a^d \\ |
− | u_1 = a^{2 d} = (a^d)^2\\ | + | u_1 = a^{2 d} = (a^d)^2 \\ |
− | u_2 = a^{2^2 d} = (a^{2 d})^2\\ | + | u_2 = a^{2^2 d} = (a^{2 d})^2 \\ |
− | \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots\\ | + | \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 - 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} | + | u_r = a^{2^r d} = (a^{2^{r - 1} d})^2 = a^{m - 1} \\ |
\end{array}</math> | \end{array}</math> | ||
Linia 378: | Linia 411: | ||
:b) <math>u_0 \equiv 1 \pmod m</math> | :b) <math>u_0 \equiv 1 \pmod m</math> | ||
− | :c) <math> | + | :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> |
Linia 385: | Linia 418: | ||
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 liczbie <math>m</math>, ani o wyrazach ciągu <math>(u_i)</math>, które wszystkie przystają do <math>1</math> modulo <math>m</math>.<br/> | 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 liczbie <math>m</math>, ani o wyrazach ciągu <math>(u_i)</math>, które wszystkie przystają do <math>1</math> modulo <math>m</math>.<br/> | ||
− | W przypadku c) mamy <math>u_k \equiv 1 \pmod m</math>, czyli <math>(u_{k - 1})^2 \equiv 1 \pmod m</math>. Z twierdzenia | + | W przypadku c) mamy <math>u_k \equiv 1 \pmod m</math>, czyli <math>(u_{k - 1})^2 \equiv 1 \pmod m</math>. Z 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/> |
Co kończy dowód twierdzenia.<br/> | Co kończy dowód twierdzenia.<br/> | ||
Linia 393: | Linia 426: | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja | + | <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 | + | 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>)). |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <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 przypadku liczb silnie pseudopierwszych nie istnieje odpowiednik liczb Carmichaela. Czyli nie istnieją liczby złożone nieparzyste <math>m</math>, dla których twierdzenie | + | 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 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>. |
− | Wynika stąd, że jeżeli dla <math>k</math> różnych liczb <math>a</math> prawdziwe jest twierdzenie | + | 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>. |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga M17</span><br/> |
− | Wykorzystując twierdzenie | + | Wykorzystując twierdzenie M14, możemy napisać w PARI/GP program wykonujący test Millera-Rabina dla ustalonej podstawy. |
− | <span style="font-size: 90%; color:black;"> | + | <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, a) = |
{ | { | ||
− | '''local'''(d, | + | '''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 | |
− | r = '''valuation'''(m - 1, 2); \\ wykładnik, z | ||
d = (m - 1) / 2^r; | d = (m - 1) / 2^r; | ||
x = modPower(a, d, m); | x = modPower(a, d, m); | ||
− | '''if'''( x == 1, '''return'''(1) ); | + | '''if'''( x == 1 || x == m - 1, '''return'''(1) ); \\ x = m - 1 to przypadek k == 0 |
− | + | k = 0; | |
− | '''while'''( | + | '''while'''( k++ < r, |
+ | x = x^2 % m; | ||
'''if'''( x == m - 1, '''return'''(1) ); | '''if'''( x == m - 1, '''return'''(1) ); | ||
− | |||
); | ); | ||
'''return'''(0); | '''return'''(0); | ||
Linia 425: | Linia 457: | ||
+ | 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> | ||
+ | |||
+ | ::<math>a^{2^k d} \equiv - 1 \!\! \pmod{m}</math> | ||
+ | |||
+ | modulo <math>g</math>, otrzymujemy natychmiast | ||
+ | |||
+ | ::<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. | ||
+ | |||
+ | <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;">Zadanie | + | |
− | Pokazać, że jeżeli liczba <math>m</math> jest SPSP(<math>a</math>), to jest | + | |
+ | <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>). | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
Linia 443: | Linia 510: | ||
::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math> | ::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math> | ||
− | Czyli <math>m</math> jest | + | Czyli <math>m</math> jest PSP(<math>a</math>). |
Jeżeli spełniony jest drugi warunek, to | Jeżeli spełniony jest drugi warunek, to | ||
Linia 451: | Linia 518: | ||
::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math> | ::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math> | ||
− | Czyli <math>m</math> jest | + | Czyli <math>m</math> jest PSP(<math>a</math>).<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 457: | Linia 524: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Przykład M19</span><br/> |
− | Pokażemy, że jeżeli <math>m</math> jest | + | 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 | 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 | ||
Linia 476: | Linia 543: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <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> | Tabela zawiera najmniejsze liczby silnie pseudopierwsze 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=1; '''forstep'''(m=3, 20000, 2, '''if'''( | + | <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> |
::{| class="wikitable plainlinks" style="font-size: 90%; text-align: center; margin-right: auto;" | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: center; margin-right: auto;" | ||
Linia 497: | Linia 564: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <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> | 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'''( | + | <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;" | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: center; margin-right: auto;" | ||
Linia 518: | Linia 585: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga M22</span><br/> |
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>2</math>) już znamy: <math>2047</math>. Najmniejszą liczbę, która jest jednocześnie SPSP(<math>2</math>) i SPSP(<math>3</math>) musimy poszukać. Prostym poleceniem | 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>2</math>) już znamy: <math>2047</math>. Najmniejszą liczbę, która jest jednocześnie SPSP(<math>2</math>) i SPSP(<math>3</math>) musimy poszukać. Prostym poleceniem | ||
− | <span style="font-size: 90%; color:black;">'''forstep'''(m=3, | + | <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> |
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 | 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 | ||
− | <span style="font-size: 90%; color:black;">'''forstep'''(m=3, | + | <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> |
znajdujemy, że szukana liczba to <math>m = 25326001</math>. | znajdujemy, że szukana liczba to <math>m = 25326001</math>. | ||
Linia 532: | Linia 599: | ||
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 | 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 | ||
− | ::{| class="wikitable plainlinks" style="font-size: | + | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: right; margin-right: auto;" |
! <math>\boldsymbol{n}</math> !! <math>\boldsymbol{m}</math> | ! <math>\boldsymbol{n}</math> !! <math>\boldsymbol{m}</math> | ||
|- | |- | ||
Linia 551: | Linia 618: | ||
Podane w 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 jest liczbą mniejszą od <math>3.41 \cdot 10^{14}</math>, to jest z pewnością liczbą pierwszą. | Podane w 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 jest liczbą mniejszą od <math>3.41 \cdot 10^{14}</math>, to jest z pewnością liczbą pierwszą. | ||
+ | |||
+ | |||
+ | |||
+ | <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 | ||
+ | |||
+ | :* <math>r = 3</math> | ||
+ | :* <math>a_k < 100</math> | ||
+ | :* <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>: | ||
+ | |||
+ | ::<math>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>m < 1.12 \cdot 10^{10}</math> jest liczbą pierwszą. | ||
+ | |||
+ | 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). | ||
+ | |||
+ | :* 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ą. | ||
+ | |||
+ | :* 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ą. | ||
+ | |||
+ | 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> | ||
+ | |||
Linia 557: | Linia 658: | ||
== Uzupełnienie == | == Uzupełnienie == | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga M24</span><br/> |
− | W funkcji <code> | + | W funkcji <code>isPrimeOr<span style="background-color: #fee481;">SPSP</span>()</code> wykorzystaliśmy zaimplementowane w PARI/GP funkcje: |
* <code>gcd(a, b)</code> – znajduje największy wspólny dzielnik liczb a i b | * <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 | + | * <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ć: | Wprowadzenie tych funkcji pozwoliło zwiększyć czytelność kodu, ale bez trudu możemy sami je napisać: | ||
Linia 567: | Linia 668: | ||
<span style="font-size: 90%; color:black;">gcd2(a, b) = | <span style="font-size: 90%; color:black;">gcd2(a, b) = | ||
{ | { | ||
− | '''while'''( | + | '''local'''(r); |
− | '''return'''( | + | '''if'''( b == 0, '''return'''('''abs'''(a)) ); |
+ | r = a % b; | ||
+ | '''while'''( r > 0, a = b; b = r; r = a % b ); | ||
+ | '''return'''('''abs'''(b)); | ||
}</span> | }</span> | ||
Linia 597: | Linia 701: | ||
<references> | <references> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
<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="Miller1">Gary L. Miller, ''Riemann's Hypothesis and Tests for Primality'', Journal of Computer and System Sciences '''13''', 300-317 (1976)</ref> | ||
Linia 613: | Linia 711: | ||
<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="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> | </references> |
Aktualna wersja na dzień 17:11, 20 kwi 2024
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.
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{a} }[/math] [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{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] [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{ w }[/math] względnie pierwsza z [math]\displaystyle{ m }[/math], taka że
- [math]\displaystyle{ w^{m - 1} \not\equiv 1 \pmod m }[/math]
to dla co najmniej połowy liczb [math]\displaystyle{ a \in [1, m - 1] }[/math] względnie pierwszych z [math]\displaystyle{ m }[/math] jest
- [math]\displaystyle{ a^{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 (zobacz L74 i nn.) 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]. Test Fermata jest zatem zbyt zawodny, aby można było go stosować.
Zadanie M12
Pokazać, że jeżeli [math]\displaystyle{ m }[/math] jest liczbą złożoną nieparzystą i istnieje liczba [math]\displaystyle{ w }[/math] względnie pierwsza z [math]\displaystyle{ m }[/math] taka, że
- [math]\displaystyle{ w^{m - 1} \not\equiv 1 \!\! \pmod{m} }[/math]
to kongruencja
- [math]\displaystyle{ a^{m - 1} \equiv 1 \!\! \pmod{m} }[/math]
nie jest prawdziwa dla co najmniej połowy liczb [math]\displaystyle{ a }[/math] względnie pierwszych z [math]\displaystyle{ m }[/math].
Niech [math]\displaystyle{ S_b }[/math] będzie zbiorem wszystkich liczb [math]\displaystyle{ b }[/math] względnie pierwszych z [math]\displaystyle{ m }[/math] i różnych modulo [math]\displaystyle{ m }[/math], dla których kongruencja
- [math]\displaystyle{ a^{m - 1} \equiv 1 \!\! \pmod{m} \qquad \qquad \qquad (1) }[/math]
jest prawdziwa. Zdefiniujmy zbiór [math]\displaystyle{ S_w }[/math] następująco [math]\displaystyle{ S_w = \{ w b : b \in S_b \} }[/math]. Zauważmy, że
- elementy zbioru [math]\displaystyle{ S_w }[/math] są wszystkie różne modulo [math]\displaystyle{ m }[/math], bo z założenia [math]\displaystyle{ w }[/math] jest liczbą względnie pierwszą z [math]\displaystyle{ m }[/math] (zobacz H21 p.1)
- elementy zbioru [math]\displaystyle{ S_w }[/math] są względnie pierwsze z [math]\displaystyle{ m }[/math] (zobacz H6)
- dla każdego elementu zbioru [math]\displaystyle{ S_w }[/math] kongruencja [math]\displaystyle{ (1) }[/math] nie jest prawdziwa, bo
- [math]\displaystyle{ \left( w b \right)^{m - 1} = w^{m - 1} \cdot b^{m - 1} \equiv w^{m - 1} \not\equiv 1 \!\! \pmod{m} }[/math]
- [math]\displaystyle{ | S_b | + | S_w | \leqslant \varphi (m) }[/math], bo elementy zbiorów [math]\displaystyle{ S_b }[/math] i [math]\displaystyle{ S_w }[/math] nie muszą być wszystkimi liczbami względnie pierwszymi z [math]\displaystyle{ m }[/math]
- [math]\displaystyle{ | S_b | = | S_w | }[/math], co wynika wprost z definicji zbioru [math]\displaystyle{ S_w }[/math]
Zatem [math]\displaystyle{ | S_b | \leqslant \frac{1}{2} \varphi (m) }[/math], czyli dla co najmniej połowy liczb [math]\displaystyle{ a }[/math] względnie pierwszych z [math]\displaystyle{ m }[/math] kongruencja [math]\displaystyle{ (1) }[/math] nie jest prawdziwa. Co należało pokazać.
□
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].
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[1] i Michaela Rabina[2] 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].
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]).
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{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] [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[3][4] znaleziono wartości liczb silnie pseudopierwszych względem wielu podstaw, które są kolejnymi liczbami pierwszymi, dla większej ilości liczb pierwszych[5]. 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ę[4][6], ż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 bvaluation(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
- ↑ 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
- ↑ 4,0 4,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)