Tekst źródłowy strony Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze

<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">11.11.2022</div>

__FORCETOC__



== Potęgowanie modulo ==

<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&nbsp;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>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&nbsp;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&nbsp;funkcji <code>modPower()</code> nie występują wyrażenia o&nbsp;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/>
Wykorzystując wzór rekurencyjny

::<math>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:

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


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

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





== Liczby pseudopierwsze Fermata ==

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 M4</span><br/>
Jeżeli <math>m</math> jest liczbą złożoną nieparzystą i&nbsp;dla pewnego <math>a \in \mathbb{Z}</math> prawdziwa jest kongruencja

::<math>a^{m - 1} \equiv 1 \pmod m</math>

to powiemy, że <math>m</math> jest liczbą pseudopierwszą Fermata przy podstawie <math>a</math> lub krótko: <math>m</math> jest PSP(<math>a</math>).



<span style="font-size: 110%; font-weight: bold;">Uwaga M5</span><br/>
Zauważmy, że w&nbsp;definicji liczb pseudopierwszych Fermata nie musimy dodatkowo dołączać warunku <math>\gcd (a, m) = 1</math>, bo wynika on z&nbsp;przyjętej definicji. Mamy

::<math>\gcd (a^{m - 1}, m) = \gcd (1, 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>

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.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>a \in \mathbb{Z}</math> i <math>a \geqslant 2</math>. Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to

::<math>a^p - 1 = (a - 1) (a^{p - 1} + a^{p - 2} + \ldots + a^2 + a + 1)</math>

oraz 

::<math>a^p + 1 = (a + 1) (a^{p - 1} - a^{p - 2} + \ldots + a^2 - a + 1)</math>

Czyli <math>a - 1 \mid a^p - 1</math> oraz <math>a + 1 \mid a^p + 1</math>.


Jeżeli przez <math>R_2 (a)</math> oznaczymy resztę z&nbsp;dzielenia liczby <math>a</math> przez <math>2</math> równą <math>0</math> lub <math>1</math>, to prawdziwe są kongruencje

::<math>a \equiv R_2 (a) \pmod 2</math>

oraz

::<math>a^n \equiv R_2 (a) \pmod 2</math>

dla dowolnej liczby całkowitej dodatniej <math>n</math>. Zatem modulo <math>2</math> jest

::<math>{\small\frac{a^p - 1}{a - 1}} \equiv R_2 (a) \cdot (p - 1) + 1 \equiv 1 \pmod 2</math>

::<math>{\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2</math>

Co oznacza, że

::<math>m = {\small\frac{a^p - 1}{a - 1}} \cdot {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2</math>

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


Z twierdzenia Fermata wiemy, że

::<math>a^p - 1 \equiv a - 1 \pmod p</math>

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>

Z założenia <math>p \nmid (a - 1)</math>, zatem liczba pierwsza <math>p</math> musi dzielić <math>{\small\frac{a^p - 1}{a - 1}} - 1</math> i&nbsp;otrzymujemy

::<math>{\small\frac{a^p - 1}{a - 1}} \equiv 1 \pmod p</math>

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

::<math>a^p + 1 \equiv a + 1 \pmod p</math>

::<math>(a + 1) \cdot \left( {\small\frac{a^p + 1}{a + 1}} - 1 \right) \equiv 0 \pmod p</math>

::<math>{\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod p</math>

Wynika stąd, że <math>m \equiv 1 \pmod p</math>.

Zbierając mamy <math>2 \mid (m - 1)</math> i <math>p \mid (m - 1)</math>, zatem <math>2 p \mid (m - 1)</math>, czyli

::<math>m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} \equiv 1 \pmod{2 p}</math>

Oznacza to, że <math>m = 1 + 2 k p</math> dla pewnej liczby całkowitej <math>k > 0</math>.


Zauważmy teraz, że z&nbsp;definicji liczby <math>m</math> mamy <math>(a^2 - 1) m = a^{2 p} - 1</math>. Rozpatrując to równanie modulo <math>m</math>, otrzymujemy

::<math>a^{2 p} \equiv 1 \pmod m</math>

Zatem modulo <math>m</math> jest

::<math>a^{m - 1} = a^{2 k p} = (a^{2 p})^k \equiv 1^k \equiv 1 \pmod m</math>

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/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Przykład M7</span><br/>
Z dowodu twierdzenia M6 wynika, że jeżeli liczba <math>p</math> jest liczbą pierwszą nieparzystą i <math>p \nmid (a^2 - 1)</math>, to liczba <math>m = {\small\frac{a^{2 p} - 1}{a^2 - 1}}</math> jest PSP(<math>a</math>). Poniżej przedstawiamy przykłady takich liczb, dla kolejnych liczb pierwszych nieparzystych <math>p</math> takich, że <math>p \nmid (a^2 - 1)</math>.

 <span style="font-size: 90%; color:black;">'''for'''(a=2, 5, s=1; d=a^2-1; '''forprime'''(p=3, 50, '''if'''( d%p == 0, '''next'''() ); m=(a^(2*p)-1)/d; '''print'''("a= ", a, "   m= ", m); s++; '''if'''( s>6, '''break'''() ) )) </span>

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math>
|-
|   || <math>341</math> || <math>91</math> || <math>17895697</math> || <math>406901</math>
|-
|   || <math>5461</math> || <math>7381</math> || <math>1172812402961</math> || <math>254313151</math>
|-
|   || <math>1398101</math> || <math>597871</math> || <math>300239975158033</math> || <math>99341074625651</math>
|-
|   || <math>22369621</math> || <math>3922632451</math> || <math>19676527011956855057</math> || <math>62088171641031901</math>
|-
|   || <math>5726623061</math> || <math>317733228541</math> || <math>5037190915060954894609</math> || <math>24253192047278086344401</math>
|-
|   || <math>91625968981</math> || <math>2084647712458321</math> || <math>330117343809434739973099793</math> || <math>15158245029548803965250651</math>
|}



<span style="font-size: 110%; font-weight: bold;">Uwaga M8</span><br/>
Wykorzystując funkcję potęgowania modulo, możemy napisać prosty program do testowania pierwszości liczb w&nbsp;oparciu o&nbsp;twierdzenie Fermata.

 <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">PSP</span>(m, a) = 
 {
 '''if'''( modPower(a, m-1, m) == 1, '''return'''(1), '''return'''(0) );
 }</span>



<span style="font-size: 110%; font-weight: bold;">Przykład M9</span><br/>
Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Fermata dla podstaw <math>a</math> od <math>2</math> do <math>15</math>

 <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;"
! &nbsp;&nbsp;<math>\boldsymbol{a}</math>&nbsp;&nbsp; !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math>
|-
|   || <math>341</math> || <math>91</math> || <math>15</math> || <math>217</math> || <math>35</math> || <math>25</math> || <math>9</math> || <math>91</math> || <math>9</math> || <math>15</math> || <math>65</math> || <math>21</math> || <math>15</math> || <math>341</math>
|-
|   || <math>561</math> || <math>121</math> || <math>85</math> || <math>561</math> || <math>185</math> || <math>325</math> || <math>21</math> || <math>121</math> || <math>33</math> || <math>133</math> || <math>91</math> || <math>85</math> || <math>39</math> || <math>1477</math>
|-
|   || <math>645</math> || <math>671</math> || <math>91</math> || <math>781</math> || <math>217</math> || <math>561</math> || <math>45</math> || <math>205</math> || <math>91</math> || <math>259</math> || <math>133</math> || <math>105</math> || <math>65</math> || <math>1541</math>
|-
|   || <math>1105</math> || <math>703</math> || <math>341</math> || <math>1541</math> || <math>301</math> || <math>703</math> || <math>63</math> || <math>511</math> || <math>99</math> || <math>305</math> || <math>143</math> || <math>231</math> || <math>195</math> || <math>1687</math>
|-
|   || <math>1387</math> || <math>949</math> || <math>435</math> || <math>1729</math> || <math>481</math> || <math>817</math> || <math>65</math> || <math>671</math> || <math>259</math> || <math>481</math> || <math>145</math> || <math>357</math> || <math>481</math> || <math>1729</math>
|}



<span style="font-size: 110%; font-weight: bold;">Przykład M10</span><br/>
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'''( 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;"
! <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 M11</span><br/>
Można pokazać, że jeżeli <math>m</math> jest liczbą nieparzystą złożoną i&nbsp;istnieje przynajmniej jedna liczba <math>w</math> względnie pierwsza z <math>m</math>, taka że

::<math>w^{m - 1} \not\equiv 1 \pmod m</math>

to dla co najmniej połowy liczb <math>a \in [1, m - 1]</math> względnie pierwszych z <math>m</math> jest

::<math>a^{m - 1} \not\equiv 1 \pmod m</math>

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

Niestety, istnieją liczby złożone <math>m</math> takie, że

::<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 (zobacz L74 i nn.) i&nbsp;jest ich nieskończenie wiele. Pokazano, że dla dostatecznie dużych <math>x</math> ilość liczb Carmichaela mniejszych od <math>x</math> przekracza <math>x^{1/3}</math>. 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

:*&nbsp;&nbsp;&nbsp;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)

:*&nbsp;&nbsp;&nbsp;elementy zbioru <math>S_w</math> są względnie pierwsze z <math>m</math> (zobacz H6)

:*&nbsp;&nbsp;&nbsp;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>

:*&nbsp;&nbsp;&nbsp;<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>

:*&nbsp;&nbsp;&nbsp;<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/>
&#9633;
{{\Spoiler}}





== Test Millera-Rabina ==

Rozpoczniemy od udowodnienia prostego twierdzenia

<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>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia

::<math>x^2 \equiv 1 \pmod m</math>

Zatem <math>m \mid (x^2 - 1)</math>, czyli <math>m \mid (x - 1) (x + 1)</math>. Ponieważ z&nbsp;założenia <math>m</math> jest liczbą pierwszą nieparzystą, to <math>m</math> dzieli dokładnie jedną z&nbsp;liczb <math>x - 1</math> i <math>x + 1</math>. Istotnie, gdyby <math>m \mid (x - 1)</math> <math>\text{i} \;\, m \mid (x + 1)</math>, to <math>m</math> dzieliłaby również ich różnicę równą <math>2</math>, co jest niemożliwe w&nbsp;przypadku gdy <math>m</math> jest liczbą pierwszą nieparzystą.<br/>
&#9633;
{{\Spoiler}}



Prace Gary'ego Millera<ref name="Miller1"/> i&nbsp;Michaela Rabina<ref name="Rabin1"/> pozwoliły sformułować znacznie silniejszy test. Podstawą tego testu jest następujące twierdzenie

<span style="font-size: 110%; font-weight: bold;">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

::<math>a^d \equiv 1 \pmod m</math>

albo

::<math>a^{2^k d} \equiv - 1 \pmod m</math>

dla pewnego <math>k \in [0, r - 1]</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Rozważmy ciąg <math>r + 1</math> liczb zdefiniowanych następująco

::<math>\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>(u_i)</math> są dane wzorem ogólnym

::<math>u_i = a^{2^i d}</math>

gdzie <math>i = 0, 1, \ldots, r</math>

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

:a) żaden z&nbsp;wyrazów ciągu <math>(u_i)</math> nie przystaje do <math>1</math> modulo <math>m</math>

:b) wszystkie wyrazy ciągu <math>(u_i)</math> przystają do <math>1</math> modulo <math>m</math>

:c) <math>u_k</math> jest pierwszym wyrazem ciągu <math>(u_i)</math>, który przystaje do <math>1</math> modulo <math>m</math>


Co możemy zapisać jako

:a) <math>u_i \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math>

:b) <math>u_i \equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math>

:c) <math>u_k \equiv 1 \pmod m \quad</math> dla pewnego <math>k \in [0, r]</math>


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

:a) <math>u_i \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math>

:b) <math>u_0 \equiv 1 \pmod m</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>


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

Przypadek b) jest możliwy (np. dla <math>m = 41</math> i <math>a = 10</math>), ale nie pozwala powiedzieć nic więcej ani o&nbsp;liczbie <math>m</math>, ani o&nbsp;wyrazach ciągu <math>(u_i)</math>, które wszystkie przystają do <math>1</math> modulo <math>m</math>.<br/>

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

Co kończy dowód twierdzenia.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Definicja M15</span><br/>
Złożoną liczbę nieparzystą <math>m</math>, która spełnia twierdzenie M14 dla pewnej liczby <math>a \in \mathbb{Z}</math>, będziemy nazywali liczbą silnie pseudopierwszą przy podstawie <math>a</math> (w skrócie: SPSP(<math>a</math>)).



<span style="font-size: 110%; font-weight: bold;">Uwaga M16</span><br/>
Niech <math>a</math> będzie liczbą całkowitą względnie pierwszą z <math>m</math> i <math>a \in [1, m - 1]</math>. Można pokazać, że jeżeli <math>m \neq 9</math> jest liczbą nieparzystą złożoną, to co najwyżej <math>\tfrac{1}{4}</math> liczb <math>a</math> stanowią liczby silnie pseudopierwsze. Zatem w&nbsp;przypadku liczb silnie pseudopierwszych nie istnieje odpowiednik liczb Carmichaela. Czyli nie istnieją liczby złożone nieparzyste <math>m</math>, dla których twierdzenie M14 byłoby prawdziwe dla wszystkich podstaw <math>a</math>.

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 M17</span><br/>
Wykorzystując twierdzenie M14, możemy napisać w&nbsp;PARI/GP program wykonujący test Millera-Rabina dla ustalonej podstawy.

 <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">SPSP</span>(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);
 }</span>


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 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}}
Z założenia <math>m</math> jest SPSP(<math>a</math>), zatem spełniony jest dokładnie jeden z&nbsp;warunków

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

gdzie <math>m - 1 = 2^r \cdot d</math>, przy czym <math>d</math> jest liczbą nieparzystą.

Jeżeli spełniony jest pierwszy warunek, to

::<math>(a^d)^{2^r} \equiv 1 \pmod m</math>

::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math>

Czyli <math>m</math> jest PSP(<math>a</math>).

Jeżeli spełniony jest drugi warunek, to

::<math>(a^{2^k \cdot d})^{2^{r - k}} \equiv (- 1)^{2^{r - k}} \pmod m</math>

::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math>

Czyli <math>m</math> jest PSP(<math>a</math>).<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Przykład M19</span><br/>
Pokażemy, że jeżeli <math>m</math> jest PSP(<math>2</math>), to <math>2^m - 1</math> jest SPSP(<math>2</math>).

Z założenia <math>m</math> jest złożoną liczbą nieparzystą, zatem <math>N = 2^m - 1</math> jest złożoną liczbą nieparzystą. Ponieważ <math>m</math> jest FPSP(<math>2</math>), to

::<math>2^{m - 1} \equiv 1 \pmod m</math>

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

::<math>N - 1 = 2^m - 2 = 2 (2^{m - 1} - 1) = 2 k m</math>

Widzimy, że liczba <math>2</math> występuje w&nbsp;pierwszej potędze w&nbsp;rozwinięciu liczby <math>N - 1</math> na czynniki pierwsze i&nbsp;łatwo otrzymujemy, że

::<math>2^{(N - 1) / 2} = 2^{k m} = (2^m)^k = (2^m - 1 + 1)^k = (N + 1)^k \equiv 1 \pmod N</math>

Czyli <math>N = 2^m - 1</math> jest SPSP(<math>2</math>).



<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>

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



<span style="font-size: 110%; font-weight: bold;">Przykład M21</span><br/>
Tabela pokazuje ilość liczb silnie pseudopierwszych dla podstaw <math>a</math> od <math>2</math> do <math>15</math>

 <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=0; '''forstep'''(k=3, 10^6, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(k, a)  &&  !'''isprime'''(k), s++ )); '''print'''("a= ", a, "   ", s))</span>

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math>
|-
| #SPSP(<math>a</math>) <math> < 10^6</math> || <math>46</math> || <math>73</math> || <math>97</math> || <math>64</math> || <math>73</math> || <math>66</math> || <math>127</math> || <math>161</math> || <math>62</math> || <math>58</math> || <math>90</math> || <math>71</math> || <math>74</math> || <math>45</math>
|-
| #SPSP(<math>a</math>) <math> < 10^7</math> || <math>162</math> || <math>207</math> || <math>305</math> || <math>199</math> || <math>203</math> || <math>177</math> || <math>377</math> || <math>459</math> || <math>158</math> || <math>157</math> || <math>251</math> || <math>193</math> || <math>190</math> || <math>148</math>
|-
| #SPSP(<math>a</math>) <math> < 10^8</math> || <math>488</math> || <math>582</math> || <math>833</math> || <math>475</math> || <math>486</math> || <math>446</math> || <math>1023</math> || <math>1241</math> || <math>437</math> || <math>430</math> || <math>666</math> || <math>472</math> || <math>440</math> || <math>398</math>
|-
| #SPSP(<math>a</math>) <math> < 10^9</math> || <math>1282</math> || <math>1514</math> || <math>2162</math> || <math>1268</math> || <math>1232</math> || <math>1163</math> || <math>2599</math> || <math>3210</math> || <math>1113</math> || <math>1125</math> || <math>1655</math> || <math>1142</math> || <math>1151</math> || <math>1041</math>
|}

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



<span style="font-size: 110%; font-weight: bold;">Uwaga M22</span><br/>
Interesujące i&nbsp;pożyteczne będzie zbadanie najmniejszych liczb silnie pseudopierwszych dla wielu podstaw. Niech badanymi podstawami będą kolejne liczby pierwsze. Najmniejszą liczbę SPSP(<math>2</math>) już znamy: <math>2047</math>. Najmniejszą liczbę, która jest jednocześnie SPSP(<math>2</math>) i&nbsp;SPSP(<math>3</math>) musimy poszukać. Prostym poleceniem

 <span style="font-size: 90%; color:black;">'''forstep'''(m=3, 10^7, 2, '''if'''( '''isprime'''(m), '''next'''() ); '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 3), '''print'''("m=", m) ))</span>

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, 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>.


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: 90%; text-align: right; margin-right: auto;"
! <math>\boldsymbol{n}</math> !! <math>\boldsymbol{m}</math>
|-
|  <math>1</math> || <math>2047</math>
|-
|  <math>2</math> || <math>1373653</math>
|-
|  <math>3</math> || <math>25326001</math>
|-
|  <math>4</math> || <math>3215031751</math>
|-
|  <math>5</math> || <math>2152302898747</math>
|-
|  <math>6</math> || <math>3474749660383</math>
|-
|  <math>7</math> || <math>341550071728321</math>
|}

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



<span style="font-size: 110%; font-weight: bold;">Uwaga M23</span><br/>
Pomysł przedstawiony w uwadze M22 ma proste uogólnienie. Niech <math>A_r = \{ a_1, \ldots, a_r \}</math> będzie zbiorem liczb naturalnych większych od <math>1</math>. Możemy teraz szukać takiego zbioru <math>A_r</math>, dla którego najmniejsza liczba silnie pseudopierwsza jednocześnie względem podstaw <math>a_1, \ldots, a_r</math> będzie największa ze wszystkich rozpatrywanych przypadków.

Dla przykładu przyjmijmy, że

:*&nbsp;&nbsp;&nbsp;<math>r = 3</math>
:*&nbsp;&nbsp;&nbsp;<math>a_k < 100</math>
:*&nbsp;&nbsp;&nbsp;<math>a_k</math> są liczbami pierwszymi

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

::<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).

:*&nbsp;Jeżeli podstawa <math>a</math> jest liczbą pierwszą, to wystarczy zbadać, czy <math>R_a (m) = 0</math>. Jeśli tak, to tylko w przypadku, gdy <math>m = a</math> liczba <math>m</math> jest liczbą pierwszą.

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

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>





== Uzupełnienie ==

<span style="font-size: 110%; font-weight: bold;">Uwaga M24</span><br/>
W funkcji <code>isPrimeOr<span style="background-color: #fee481;">SPSP</span>()</code> wykorzystaliśmy zaimplementowane w&nbsp;PARI/GP funkcje:

* <code>gcd(a, b)</code> – znajduje największy wspólny dzielnik liczb a i b 
* <code>valuation(a, b)</code> – znajduje największą wartość liczby <math>r</math> taką, że <math>b^r \mid a</math>

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

 <span style="font-size: 90%; color:black;">gcd2(a, b) =
 {
 '''local'''(r);
 '''if'''( b == 0, '''return'''('''abs'''(a)) );
 r = a % b;
 '''while'''( r > 0, a = b; b = r; r = a % b );
 '''return'''('''abs'''(b));
 }</span>


 <span style="font-size: 90%; color:black;">valuation2(a, b) =
 {
 '''local'''(s);
 s = 0;
 '''while'''(a % b == 0, s++; a = a / b);
 '''return'''(s);
 }</span>















== Przypisy ==

<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="Rabin1">Michael O. Rabin, ''Probabilistic Algorithm for Testing Primality'', Journal of Number Theory '''12''', 128-138 (1980)</ref>

<ref name="SPSPtoNbases">Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., ''The Pseudoprimes to 25*10^9'', Mathematics of Computation, Vol. 35, No. 151 (1980), 1003-1026</ref>

<ref name="Jaeschke1">Gerhard Jaeschke, ''On Strong Pseudoprimes to Several Bases'', Mathematics of Computation, Vol. 61, No. 204 (Oct., 1993), 915-926</ref>

<ref name="A014233">On-Line Encyclopedia of Integer Sequences, ''Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness'', ([https://oeis.org/A014233 A014233])</ref>

<ref name="MillerRabin1">Wikipedia, ''Test Millera-Rabina'', ([https://pl.wikipedia.org/wiki/Test_Millera-Rabina#Dok%C5%82adno%C5%9B%C4%87_testu_i_wersje_deterministyczne Wiki-pl]), ([https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases Wiki-en])</ref>

</references>





&nbsp;