Tekst źródłowy strony Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju

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

__FORCETOC__



== Podzielność wyrazów <math>V_n (P, Q)</math> przez liczbę pierwszą nieparzystą ==

<span style="font-size: 110%; font-weight: bold;">Twierdzenie P1</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą.

::{| border="0" 
|-style=height:1.9em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli <math>\; p \mid P \;</math> <math>\text{i} \;\; p \mid Q , \; </math> to <math>\; p \mid V_n \;</math> dla <math>n \geqslant 1</math>
|-style=height:1.9em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli <math>\; p \mid P \;</math> <math>\text{i} \;\; p \nmid Q , \;</math> to <math>\; p \mid V_{2 n + 1} \;</math> i <math>\; p \nmid V_{2 n}</math>
|-style=height:1.9em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli <math>\; p \nmid P \;</math> <math>\text{i} \;\; p \mid Q , \;</math> to <math>\; p \nmid V_n \;</math> dla <math>n \geqslant 0</math>
|-style=height:1.9em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli <math>\; p \mid Q , \;</math> to <math>\; p \mid V_n ,</math> gdzie <math>n \geqslant 1</math>, wtedy i&nbsp;tylko wtedy, gdy <math>\; p \mid P</math>
|-style=height:1.9em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli <math>\; p \nmid P \;</math> <math>\text{i} \;\; p \mid D , \;</math> to <math>\; p \nmid V_n \;</math> dla <math>n \geqslant 0</math>
|}

Założenie, że <math>p \nmid P</math> w&nbsp;ostatnim punkcie jest istotne. Gdy <math>\; p \mid P \;</math> i <math>\; p \mid D , \;</math> to <math>\; p \mid Q \;</math> i&nbsp;otrzymujemy punkt pierwszy.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
'''Punkt 1.'''

Ponieważ <math>V_1 = P</math>, zatem <math>p \mid V_1</math>. Dla <math>n \geqslant 2</math> wyrażenie <math>V_n = P V_{n - 1} - Q V_{n - 2}</math> jest podzielne przez <math>p</math>.

'''Punkt 2.'''

Indeksy nieparzyste. Indukcja matematyczna. Mamy <math>V_0 = 2</math>, <math>V_1 = P</math>, <math>V_2 = P^2 - 2 Q</math> i <math>V_3 = P^3 - 3 P Q</math>, zatem <math>p \mid V_1</math> i <math>p \mid V_3</math>. Zakładając, że <math>p \mid V_{2 n - 1}</math>, z&nbsp;definicji ciągu <math>(V_k)</math> otrzymujemy dla <math>V_{2 n + 1}</math>

::<math>V_{2 n + 1} = P V_{2 n} - Q V_{2 n - 1}</math>

Z założenia indukcyjnego wynika, że <math>p \mid V_{2 n + 1}</math>, zatem na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla wszystkich <math>n \geqslant 0</math>.

Indeksy parzyste. Indukcja matematyczna. Mamy <math>V_0 = 2</math>, <math>V_1 = P</math> i <math>V_2 = P^2 - 2 Q</math>, zatem <math>p \nmid V_0</math> i <math>p \nmid V_2</math>. Zakładając, że <math>p \nmid V_{2 n}</math>, z&nbsp;definicji ciągu <math>(V_k)</math> otrzymujemy dla <math>V_{2 n + 2}</math>

::<math>V_{2 n + 2} = P V_{2 n + 1} - Q V_{2 n}</math>

Z założenia indukcyjnego wynika, że <math>p \nmid V_{2 n + 2}</math>. Zatem na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla wszystkich liczb <math>n \geqslant 0</math>.

'''Punkt 3.'''

Indukcja matematyczna. Mamy <math>V_0 = 2</math> i <math>V_1 = P</math>, zatem <math>p \nmid V_0</math> i <math>p \nmid V_1</math>. Zakładając, że <math>p \nmid V_n</math>, z&nbsp;definicji ciągu <math>(V_k)</math> otrzymujemy dla <math>V_{n + 1}</math>

::<math>V_{n + 1} = P V_n - Q V_{n - 1}</math>

Z założenia indukcyjnego wynika, że <math>p \nmid V_{n + 1}</math>, zatem na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla wszystkich liczb <math>n \geqslant 0</math>.

'''Punkt 4.'''

Wynika z&nbsp;punktów pierwszego i&nbsp;trzeciego.

'''Punkt 5.'''

Z twierdzenia N7 wiemy, że

::<math>2^{n - 1} V_n = \sum_{k = 0}^{\lfloor n / 2 \rfloor} \binom{n}{2 k} P^{n - 2 k} D^k</math>

::::<math>\;\, = P^n + \binom{n}{2} P^{n - 2} D + \binom{n}{4} P^{n - 4} D^2 + \ldots </math>

Z założenia <math>p \mid D</math>, zatem modulo <math>p</math> dostajemy

::<math>2^{n - 1} V_n \equiv P^n \pmod{p}</math>

Ponieważ <math>p \nmid P</math>, zatem <math>p \nmid V_n</math>.
Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie P2</span><br/>
Jeżeli <math>d</math> jest nieparzystym dzielnikiem <math>Q</math>, to dla <math>n \geqslant 1</math> jest

::<math>V_n \equiv P^n \pmod{d}</math>

W szczególności, gdy liczba pierwsza nieparzysta <math>p</math> jest dzielnikiem <math>Q</math>, to

::<math>V_p \equiv P \pmod{p}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Oznaczmy <math>\delta = \sqrt{D}</math>, zatem <math>2 \alpha = P + \delta</math> i <math>2 \beta = P - \delta</math>. Ze wzoru dwumianowego, mamy

::<math>2^n \alpha^n = (P + \delta)^n = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} \delta^j</math>

::<math>2^n \beta^n = (P - \delta)^n = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (- \delta)^j</math>

Obliczając sumę powyższych wzorów, otrzymujemy

::<math>2^n (\alpha^n + \beta^n) = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (\delta^j + (- \delta)^j)</math>

:::::<math>\quad \: = \underset{j \; \text{parzyste}}{\sum_{j = 0}^{n}} \binom{n}{j} P^{n - j} \cdot 2 \delta^j</math>

:::::<math>\quad \: = 2 \underset{j \; \text{parzyste}}{\sum_{j = 0}^{n}} \binom{n}{j} P^{n - j} \cdot D^{j / 2}</math>

Rozpatrując powyższą równość modulo <math>Q</math>, dostajemy (zobacz N46)

::<math>2^{n - 1} V_n \equiv \underset{j \; \text{parzyste}}{\sum_{j = 0}^{n}} \binom{n}{j} P^{n - j} \cdot (P^2)^{j / 2}</math>

::::<math>\:\, \equiv P^n \underset{j \; \text{parzyste}}{\sum_{j = 0}^{n}} \binom{n}{j}</math>

::::<math>\:\, \equiv 2^{n - 1} P^n \pmod{Q}</math>

Czyli

::<math>2^{n - 1} (V_n - P^n) \equiv 0 \pmod{Q}</math>

Ponieważ <math>Q</math> dzieli <math>2^{n - 1} (V_n - P^n)</math>, to tym bardziej <math>d</math> dzieli <math>2^{n - 1} (V_n - P^n)</math>. Z&nbsp;założenia <math>\gcd (d, 2^{n - 1}) = 1</math>, zatem <math>d</math> dzieli <math>V_n - P^n</math> (zobacz C75). Co należało pokazać.


W przypadku szczególnym, gdy <math>d = n = p</math>, gdzie <math>p</math> jest nieparzystą liczbą pierwszą, otrzymujemy natychmiast (zobacz J22).

::<math>V_p \equiv P^p \equiv P \pmod{p}</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie P3</span><br/>
Niech <math>D = P^2 - 4 Q \neq 0</math>, a <math>(D \mid p)</math> oznacza symbol Legendre'a, gdzie <math>p</math> jest liczbą pierwszą nieparzystą i <math>p \nmid Q</math>. Mamy

::{| border="0" 
|-style=height:2em 
| &#9679;&nbsp;&nbsp;&nbsp; <math>V_p \equiv P \pmod{p}</math>
|-style=height:2em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli <math>(D \mid p) = - 1 , \;</math> to <math>V_{p + 1} \equiv 2 Q \pmod{p}</math>
|-style=height:2em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli <math>(D \mid p) = 1 , \;</math> to <math>V_{p - 1} \equiv 2 \pmod{p}</math>
|}

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
'''Punkt 1.'''

Zauważmy, że przypadek gdy <math>p \mid Q</math>, omówiliśmy w&nbsp;twierdzeniu poprzednim. Z&nbsp;założenia <math>p</math> jest liczbą pierwszą nieparzystą. Z&nbsp;twierdzenia N7, w&nbsp;przypadku nieparzystego <math>n = p</math>, otrzymujemy

::<math>2^{p - 1} V_p = P^p + \binom{p}{2} P^{p - 2} D + \binom{p}{4} P^{p - 4} D^2 + \ldots + p P D^{(p - 1) / 2}</math>

Ponieważ dla <math>k \in [1, p - 1]</math> jest (zobacz N43)

::<math>\binom{p}{k} \equiv 0 \pmod{p}</math>

to modulo <math>p</math> dostajemy

::<math>2^{p - 1} V_p \equiv V_p \equiv P^p \equiv P \pmod{p}</math>

'''Punkt 2.'''

Zauważmy, że warunek <math>(D \mid p) = - 1</math> nie może być spełniony, gdy <math>p \mid Q</math>. Istotnie, gdy <math>p \mid Q</math>, to <math>D = P^2 - 4 Q \equiv P^2 \pmod{p}</math>, czyli

::<math>(D \mid p) = (P^2 \mid p) = (P \mid p)^2 = 0 , \;</math> gdy <math>p \mid P</math>

lub

::<math>(D \mid p) = (P^2 \mid p) = (P \mid p)^2 = 1 , \;</math> gdy <math>p \nmid P</math>

i nie może być <math>(D \mid p) = - 1</math>.


Dla parzystego <math>n = p + 1</math> otrzymujemy z&nbsp;twierdzenia N7

::<math>2^p V_{p + 1} = P^{p + 1} + \binom{p + 1}{2} P^{p - 1} D + \binom{p + 1}{4} P^{p - 3} D^2 + \ldots + \binom{p + 1}{p - 1} P^2 D^{(p - 1) / 2} + D^{(p + 1) / 2}</math>

Ponieważ dla <math>k \in [2, p - 1]</math> jest (zobacz N44)

::<math>\binom{p + 1}{k} \equiv 0 \pmod{p}</math>

to modulo <math>p</math> dostajemy

::<math>2 V_{p + 1} \equiv P^2 + D \cdot D^{(p - 1) / 2} \pmod{p}</math>


Z założenia <math>D</math> jest liczbą niekwadratową modulo <math>p</math>, zatem <math>D^{(p - 1) / 2} \equiv - 1 \pmod{p}</math>. Skąd wynika natychmiast, że

::<math>2 V_{p + 1} \equiv P^2 - D \equiv 4 Q \pmod{p}</math>

Zatem

::<math>V_{p + 1} \equiv 2 Q \pmod{p}</math>

'''Punkt 3.'''

Dla parzystego <math>n = p - 1</math> otrzymujemy z&nbsp;twierdzenia N7

::<math>2^{p - 2} V_{p - 1} = P^{p - 1} + \binom{p - 1}{2} P^{p - 3} D + \binom{p - 1}{4} P^{p - 5} D^2 + \ldots + \binom{p - 1}{p - 3} P^2 D^{(p - 3) / 2} + D^{(p - 1) / 2}</math>

Ponieważ dla <math>k \in [0, p - 1]</math> jest (zobacz N45)

::<math>\binom{p - 1}{k} \equiv (- 1)^k \pmod{p}</math>

to modulo <math>p</math> mamy

::<math>2^{p - 2} V_{p - 1} \equiv P^{p - 1} + P^{p - 3} D + P^{p - 5} D^2 + \ldots + P^2 D^{(p - 3) / 2} + D^{(p - 1) / 2} \pmod{p}</math>


Z założenia <math>D</math> jest liczbą kwadratową modulo <math>p</math>, zatem istnieje taka liczba <math>R</math>, że

::<math>D \equiv R^2 \pmod{p}</math>

Ponieważ

:* <math>(D \mid p) = 1</math>, to <math>p \nmid D</math>, zatem <math>p \nmid R</math>
:* z&nbsp;założenia <math>p \nmid Q</math>, to <math>P^2 - R^2 \equiv P^2 - D \equiv 4 Q \not\equiv 0 \pmod{p}</math>


Czyli

::<math>2^{p - 2} V_{p - 1} \equiv P^{p - 1} + P^{p - 3} R^2 + P^{p - 5} R^4 + \ldots + P^2 R^{p - 3} + R^{p - 1} \pmod{p}</math>


Uwzględniając, że <math>P^2 - R^2 \not\equiv 0 \pmod{p}</math>, możemy napisać

::<math>2^{p - 2} (P^2 - R^2) V_{p - 1} \equiv (P^2 - R^2) (P^{p - 1} + P^{p - 3} R^2 + P^{p - 5} R^4 + \ldots + P^2 R^{p - 3} + R^{p - 1}) \pmod{p}</math>

::::::::<math>\equiv P^{p + 1} - R^{p + 1} \pmod{p}</math>

::::::::<math>\equiv P^2 - R^2 \pmod{p}</math>

Zatem

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

Skąd wynika

::<math>V_{p - 1} \equiv 2 \pmod{p}</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



Aby zapisać punkty 2. i 3. twierdzenia P3 (i tylko te punkty) w&nbsp;zwartej formie, musimy założyć, że <math>\gcd (p, D) = 1</math>. Otrzymujemy<br/>
<span style="font-size: 110%; font-weight: bold;">Twierdzenie P4</span><br/>
Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą i <math>\gcd (p, Q D) = 1</math>, to

::<math>V_{p - (D \mid p)} \equiv 2 Q^{(1 - (D \mid p)) / 2} \pmod{p}</math>





== Liczby pseudopierwsze Dicksona drugiego rodzaju ==

<span style="font-size: 110%; font-weight: bold;">Uwaga P5</span><br/>
Z twierdzenia P4 wiemy, że dla liczb pierwszych nieparzystych takich, że <math>p \nmid Q D</math> jest

::<math>V_{p - (D \mid p)} \equiv 2 Q^{(1 - (D \mid p)) / 2} \pmod{p}</math>

gdzie <math>(D \mid p)</math> oznacza symbol Legendre'a. Jeśli zastąpimy symbol Legendre'a symbolem Jacobiego, to będziemy mogli badać prawdziwość tego twierdzenia dla liczb złożonych i&nbsp;łatwo przekonamy się, że dla pewnych liczb złożonych <math>m</math> kongruencja

::<math>V_{m - (D \mid m)} \equiv 2 Q^{(1 - (D \mid m)) / 2} \pmod{m}</math>

również jest prawdziwa. Prowadzi to definicji liczb pseudopierwszych Dicksona drugiego rodzaju<ref name="D2PSP1"/><ref name="D2PSP2"/>.



<span style="font-size: 110%; font-weight: bold;">Definicja P6</span><br/>
Powiemy, że liczba złożona nieparzysta <math>m</math> jest liczbą pseudopierwszą Dicksona drugiego rodzaju dla parametrów <math>P</math> i <math>Q</math><ref name="D2PSP3"/> (D2PSP(<math>P, Q</math>)), jeżeli <math>\gcd (m, Q D) = 1</math> i

::<math>V_{m - (D \mid m)} \equiv 2 Q^{(1 - (D \mid m)) / 2} \pmod{m}</math>

gdzie <math>(D \mid m)</math> oznacza symbol Jacobiego.



<span style="font-size: 110%; font-weight: bold;">Uwaga P7</span><br/>
Wykorzystując funkcje <code>jacobi(a, n)</code> i <code>modLucas(n, P, Q, m)</code> (zobacz J48, N15) możemy napisać prosty program do testowania pierwszości liczb na podstawie twierdzenia P4.

 <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">D2PSP</span>(m, P, Q) = 
 {
 '''local'''(D, js);
 D = P^2 - 4*Q;
 '''if'''( '''gcd'''(m, 2*Q*D) > 1, '''return'''(0) );
 js = jacobi(D, m);
 '''if'''( modLucas(m - js, P, Q, m)[2] == ( 2*Q^((1 - js)/2) ) % m, '''return'''(1), '''return'''(0) );
 }</span>



<span style="font-size: 110%; font-weight: bold;">Przykład P8</span><br/>
Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Dicksona drugiego rodzaju dla różnych parametrów <math>P</math> i <math>Q</math>.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
! &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\boldsymbol{P}</math><br/><math>\boldsymbol{Q}</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
! <math>\boldsymbol{1}</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{- 5}</math>
| style="background-color: yellow" | <math>1121</math> || <math>1541</math> || <math>13333</math> || <math>217</math> || <math>4081</math> || style="background-color: yellow" | <math>519</math> || <math>3913</math> || <math>5461</math> || <math>201</math> || <math>1729</math>
|-
! <math>\boldsymbol{- 4}</math>
| <math>7345</math> || <math>1891</math> || <math>91</math> || <math>1585</math> || style="background-color: yellow" | <math>1055</math> || <math>147</math> || <math>129</math> || <math>129</math> || <math>385</math> || <math>91</math>
|-
! <math>\boldsymbol{- 3}</math>
| <math>121</math> || <math>91</math> || <math>121</math> || <math>121</math> || <math>121</math> || <math>121</math> || <math>121</math> || <math>121</math> || <math>121</math> || <math>121</math>
|-
! <math>\boldsymbol{- 2}</math>
| <math>341</math> || style="background-color: yellow" | <math>245</math> || <math>33</math> || style="background-color: yellow" | <math>1957</math> || style="background-color: yellow" | <math>1339</math> || <math>265</math> || <math>8321</math> || <math>6601</math> || <math>249</math> || <math>1105</math>
|-
! <math>\boldsymbol{- 1}</math>
| <math>9</math> || <math>9</math> || <math>9</math> || <math>9</math> || <math>9</math> || <math>9</math> || <math>9</math> || <math>9</math> || <math>9</math> || <math>9</math>
|-
! <math>\boldsymbol{1}</math>
| <math>25</math> || style="background-color: red" | <math></math> || <math>9</math> || <math>25</math> || <math>25</math> || <math>9</math> || <math>49</math> || <math>49</math> || <math>9</math> || <math>25</math>
|-
! <math>\boldsymbol{2}</math>
| <math>1003</math> || <math>561</math> || <math>341</math> || <math>33</math> || <math>33</math> || <math>3781</math> || <math>33</math> || <math>2419</math> || <math>84561</math> || <math>177</math>
|-
! <math>\boldsymbol{3}</math>
| <math>1541</math> || <math>121</math> || <math>121</math> || <math>91</math> || <math>121</math> || <math>121</math> || <math>121</math> || <math>121</math> || <math>121</math> || <math>24727</math>
|-
! <math>\boldsymbol{4}</math>
| <math>1891</math> || style="background-color: yellow" | <math>341</math> || <math>19951</math> || style="background-color: red" | <math></math> || <math>85</math> || <math>451</math> || <math>6601</math> || <math>385</math> || <math>129</math> || <math>4033</math>
|-
! <math>\boldsymbol{5}</math>
| <math>5597</math> || style="background-color: yellow" | <math>979</math> || <math>15753</math> || style="background-color: yellow" | <math>979</math> || style="background-color: yellow" | <math>913</math> || <math>217</math> || <math>1541</math> || <math>7787</math> || <math>1417</math> || <math>201</math>
|}

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
 <span style="font-size: 90%; color:black;">FirstD2PSP(Stop) = 
 \\ najmniejsze D2PSP(P,Q) < Stop;  dla 1<=P<=10 i -5<=Q<=5
 {
 '''local'''(D, m, P, Q);
 Q = -6;
 '''while'''( Q++ <= 5,
        '''if'''( Q == 0, '''next'''() );
        P = 0;
        '''while'''( P++ <= 10,
               D = P^2 - 4*Q;
               '''if'''( D == 0, 
                   '''print'''("Q= ", Q, "   P= ", P, "   ------------------");
                   '''next'''();
                 );
               m = 3;
               '''while'''( m < Stop,
                      '''if'''( isPrimeOr<span style="background-color: #fee481;">D2PSP</span>(m, P, Q)  &&  !'''isprime'''(m),
                          '''print'''("Q= ", Q, "   P= ", P, "   m= ", m, "   (D|m)= ", jacobi(D, m));
                          '''break'''();
                        );
                      m = m + 2;
                    );
             );
      );
 }</span>
<br/>
{{\Spoiler}}

Żółtym tłem oznaczyliśmy te najmniejsze liczby pseudopierwsze Lucasa, dla których <math>(D \mid m) = - 1</math>.



<span style="font-size: 110%; font-weight: bold;">Przykład P9</span><br/>
Tabela przedstawia ilość liczb D2PSP(<math>P, Q</math>) mniejszych od <math>10^9</math>.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
! &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\boldsymbol{P}</math><br/><math>\boldsymbol{Q}</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
! <math>\boldsymbol{1}</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{- 5}</math>
| <math>145</math> || <math>143</math> || <math>91</math> || <math>4981</math> || <math>356</math> || <math>129</math> || <math>101</math> || <math>172</math> || <math>152</math> || <math>129</math> 
|-
! <math>\boldsymbol{- 4}</math>
| <math>192</math> || <math>380</math> || <math>9272</math> || <math>318</math> || <math>249</math> || <math>208</math> || <math>192</math> || <math>555</math> || <math>233</math> || <math>183</math> 
|-
! <math>\boldsymbol{- 3}</math>
| <math>179</math> || <math>5767</math> || <math>184</math> || <math>184</math> || <math>153</math> || <math>372</math> || <math>145</math> || <math>164</math> || <math>147</math> || <math>192</math> 
|-
! <math>\boldsymbol{- 2}</math>
| <math>5361</math> || <math>521</math> || <math>128</math> || <math>217</math> || <math>120</math> || <math>163</math> || <math>132</math> || <math>343</math> || <math>111</math> || <math>467</math> 
|-
! <math>\boldsymbol{- 1}</math>
| <math>6428</math> || <math>8365</math> || <math>6318</math> || <math>10695</math> || <math>6004</math> || <math>8541</math> || <math>7104</math> || <math>6423</math> || <math>6496</math> || <math>6762</math> 
|-
! <math>\boldsymbol{1}</math>
| <math>282485800</math> || style="background-color: red" | <math></math> || <math>9811</math> || <math>10627</math> || <math>10081</math> || <math>13073</math> || <math>12756</math> || <math>11841</math> || <math>11373</math> || <math>12365</math> 
|-
! <math>\boldsymbol{2}</math>
| <math>221</math> || <math>2939</math> || <math>5597</math> || <math>418</math> || <math>147</math> || <math>157</math> || <math>141</math> || <math>168</math> || <math>116</math> || <math>174</math> 
|-
! <math>\boldsymbol{3}</math>
| <math>176</math> || <math>264</math> || <math>3095</math> || <math>5767</math> || <math>158</math> || <math>239</math> || <math>135</math> || <math>179</math> || <math>159</math> || <math>151</math> 
|-
! <math>\boldsymbol{4}</math>
| <math>407</math> || <math>5361</math> || <math>473</math> || style="background-color: red" | <math></math> || <math>9735</math> || <math>515</math> || <math>330</math> || <math>959</math> || <math>213</math> || <math>247</math> 
|-
! <math>\boldsymbol{5}</math>
| <math>108</math> || <math>421</math> || <math>137</math> || <math>421</math> || <math>480</math> || <math>5146</math> || <math>92</math> || <math>124</math> || <math>123</math> || <math>702</math> 
|}

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
 <span style="font-size: 90%; color:black;">NumOfD2PSP(Stop) = 
 \\ ilość liczb pseudopierwszych Dicksona drugiego rodzaju D2PSP(P,Q) < Stop;  dla 1<=P<=10 i -5<=Q<=5
 {
 '''local'''(D, m, P, Q);
 Q = -6;
 '''while'''( Q++ <= 5,
        '''if'''( Q == 0, '''next'''() );
        P = 0;
        '''while'''( P++ <= 10,
               D = P^2 - 4*Q;
               '''if'''( D == 0, '''print'''("Q= ", Q, "   P= ", P, "   ------------------"); '''next'''() );
               s = 0;
               m = 3;
               '''while'''( m < Stop,
                      '''if'''( isPrimeOr<span style="background-color: #fee481;">D2PSP</span>(m, P, Q)  &&  !'''isprime'''(m), s++ );
                      m = m + 2;
                    );
               '''print'''("Q= ", Q, "   P= ", P, "   s= ", s);
             );
      );
 }</span>
<br/>
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Przykład P10</span><br/>
Tabele przedstawiają ilość liczb D2PSP( <math>1, Q</math> ) mniejszych od <math>10^9</math> dla <math>| Q | \leqslant 20</math>.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
! <math>\boldsymbol{Q}</math> !! <math>\boldsymbol{1}</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{16}</math> !! <math>\boldsymbol{17}</math> !! <math>\boldsymbol{18}</math> !! <math>\boldsymbol{19}</math> !! <math>\boldsymbol{20}</math>
|-
| #D2PSP(<math>1,Q</math>) <math>< 10^9</math> || <math>282485800</math> || <math>221</math> || <math>176</math> || <math>407</math> || <math>108</math> || <math>113</math> || <math>550</math> || <math>194</math> || <math>165</math> || <math>119</math> || <math>135</math> || <math>171</math> || <math>99</math> || <math>105</math> || <math>85</math> || <math>767</math> || <math>113</math> || <math>195</math> || <math>578</math> || <math>127</math>
|}

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
! <math>\boldsymbol{Q}</math> !! <math>\boldsymbol{-1}</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{-16}</math> !! <math>\boldsymbol{-17}</math> !! <math>\boldsymbol{-18}</math> !! <math>\boldsymbol{-19}</math> !! <math>\boldsymbol{-20}</math>
|-
| #D2PSP(<math>1,Q</math>) <math>< 10^9</math> || <math>6428</math> || <math>5361</math> || <math>179</math> || <math>192</math> || <math>145</math> || <math>1281</math> || <math>123</math> || <math>196</math> || <math>198</math> || <math>162</math> || <math>246</math> || <math>1748</math> || <math>106</math> || <math>103</math> || <math>110</math> || <math>205</math> || <math>113</math> || <math>157</math> || <math>157</math> || <math>1536</math>
|}


Zauważmy, że otrzymane wartości dla <math>Q = \pm 1</math> i <math>Q = - 2</math> są wyraźnie większe od pozostałych.





== Zmodyfikowana metoda Selfridge'a wyboru parametrów <math>P</math> i <math>Q</math> ==

<span style="font-size: 110%; font-weight: bold;">Uwaga P11</span><br/>
Przykłady P9 i&nbsp;P10 pokazują, że w&nbsp;przypadku liczb pseudopierwszych Dicksona drugiego rodzaju dla parametrów <math>P, Q</math> należy unikać wyboru <math>Q = \pm 1</math> i <math>Q = - 2</math>. Niestety, metoda Selfridge'a dopuszcza wartość <math>Q = - 1</math>. Baillie i&nbsp;Wagstaff<ref name="BaillieWagstaff1"/> dostrzegają ten problem (zobacz tabelę nr 4 na stronie 1407) i&nbsp;„naprawiają” metodę Selfridge'a wprowadzając następującą poprawkę: jeśli otrzymamy parę <math>(P, Q) = (1, -1)</math>, to należy zamienić ją na parę <math>(P, Q) = (5, 5)</math>. Ponieważ liczba nieparzysta <math>m</math> jest LPSP(<math>1, - 1</math>) / SLPSP(<math>1, - 1</math>) wtedy i&nbsp;tylko wtedy, gdy <math>m</math> jest LPSP(<math>5, 5</math>) / SLPSP(<math>5, 5</math>) (zobacz P18 i&nbsp;P19), to taka poprawka nie zmienia wyników wcześniejszych obliczeń wykorzystujących funkcje LucasTest(m) i&nbsp;StrongLucasTest(m).

Innym sposobem usunięcia przypadku <math>Q = - 1</math> jest wyszukiwanie liczby <math>a_k</math>, dla której <math>(a_k \mid m) = - 1</math> od <math>a_k > 5</math>. To oznacza zmianę metody i&nbsp;oczywiście zmieni wyniki wcześniejszych obliczeń funkcji LucasTest(m) i&nbsp;StrongLucasTest(m).

Dlatego konieczne było napisanie nowej funkcji <code>MethodA(m)</code>. Działa ona teraz w&nbsp;ten sposób, że domyślnie (bez podania drugiego parametru lub wpisując jako drugi parametr wartość "*") działa ona jak „poprawiona” metoda Selfridge'a (następuje zamiana pary <math>(P, Q) = (1, - 1)</math> na <math>(P, Q) = (5, 5)</math>). Jeżeli wpiszemy drugi parametr, to będzie on interpretowany, jako wyraz ciągu <math>a_k = (- 1)^k (2 k + 1)</math>, od którego należy rozpocząć przeszukiwanie. Parametr musi być elementem ciągu <math>(a_k)</math> dla <math>k \geqslant 2</math>. Przykładowo <code>MethodA(m, 5)</code>, to stara (niepoprawiona) wersja funkcji, <code>MethodA(m, -7)</code> rozpocznie poszukiwanie liczby <math>a_k</math> takiej, że <math>(a_k \mid m) = - 1</math> od <math>a_k = - 7</math>.

 <span style="font-size: 90%; color:black;">MethodA(m, start = "*") = 
 {
 \\ parametr start (poza "*") musi być wyrazem ciągu a_k = (-1)^k * (2*k+1) dla k >= 2
 '''local'''(a, js, Q);
 '''if'''( m%2 == 0, '''return'''("Error") );
 '''if'''( m == 1, '''return'''([0, 0]) ); \\ 1 nie jest liczbą pierwszą
 a = '''if'''( start == "*", 5, start );
 '''if'''( a%4 <> 1, '''return'''("Error") );
 a = -a + 2*'''sign'''(a); \\ poprzedni wyraz ciągu (a_k)
 '''while'''( 1,
        a = -a - 2*'''sign'''(a); \\ następny wyraz ciągu (a_k)
        js = jacobi(a, m);
        '''if'''( js == 1, '''next'''() );
        '''if'''( js == 0, '''if'''( (a % m) <> 0, '''return'''([0, 0]), '''next'''() ) );
        '''if'''( js == -1, Q = (1 - a)/4 );
        '''if'''( start == "*" && Q == -1, '''return'''([5, 5]) );
        '''if'''( '''gcd'''(Q, m) == 1, '''return'''([1, Q]) );
        '''if'''( Q % m <> 0, '''return'''([0, 0]) ); \\ gcd(Q, m) > 1
      );
 }</span>

Jeżeli <math>\gcd (a, m) > 0</math> lub <math>\gcd (Q, m) > 0</math>, to następuje sprawdzenie złożoności liczby <math>m</math> (linia czwarta i&nbsp;ósma pętli <code>while</code>). Jeśli nie została wykryta złożoność liczby <math>m</math>, to funkcja <code>MethodA()</code> zwraca parę <math>(P, Q)</math> taką, że <math>\gcd (m, Q D) = 1</math>, gdzie <math>D = P^2 - 4 Q</math>.



<span style="font-size: 110%; font-weight: bold;">Zadanie P12</span><br/>
Pokazać, że dla dowolnej niekwadratowej liczby nieparzystej <math>m</math> jest: <code>MethodA(m, 9) = MethodA(m, -11)</code>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Mówiąc o&nbsp;liniach kodu, mamy na myśli linie w&nbsp;pętli <code>while</code>. Linia nr 1 w&nbsp;pętli <code>while</code>, to linia <code>a = -a - 2*sign(a);</code>.

Możemy znacznie ułatwić sobie analizę problemu, sprawdzając, że równość <code>MethodA(m, 9) = MethodA(m, -11)</code> jest prawdziwa dla niekwadratowych liczb nieparzystych mniejszych od <math>100</math>. Wystarczy wykonać prosty test:

 forstep(m=1, 10^2, 2, if( issquare(m), next() ); if( MethodA(m, 9) <> MethodA(m, -11), print(m) ))


Dalszą analizę możemy przeprowadzić dla liczb <math>m</math> postaci <math>6 k + 1</math>, <math>6 k + 3</math>, <math>6 k + 5</math>, gdzie <math>k \geqslant 10</math>. Rozważmy działanie funkcji <code>MethodA(m, 9)</code>.


Jeżeli <math>m = 6 k + 1</math> lub <math>m = 6 k + 5</math>, to <math>(9 \mid m) = (3 \mid m)^2 = 1</math> i&nbsp;wykonywana jest linia nr 3, w&nbsp;wyniku czego następuje przejście do kolejnej wartości <code>a</code>, która jest równa <math>- 11</math>. Od tej chwili nie ma już różnic między <code>MethodA(m, 9)</code> i <code>MethodA(m, -11)</code>.

Jeżeli <math>m = 6 k + 3</math>, to <math>(9 \mid m) = 0</math> i&nbsp;wykonywana jest linia nr 4, w&nbsp;wyniku czego funkcja <code>MethodA(m, 9)</code> zwraca wektor <code>[0, 0]</code>.


Pozostaje pokazać, że funkcja <code>MethodA(m, -11)</code> dla <math>m = 6 k + 3</math>, gdzie <math>k \geqslant 10</math>, również zwraca wektor <code>[0, 0]</code>.


Jeżeli <math>(- 11 \mid 6 k + 3) = 0</math>, to wykonywana jest linia nr 4, w&nbsp;wyniku czego zwracany jest wektor <code>[0, 0]</code>.

Jeżeli <math>(- 11 \mid 6 k + 3) = - 1</math>, to wykonywana jest linia nr 5, w&nbsp;wyniku czego wyliczana jest wartość <code>Q</code> i&nbsp;otrzymujemy <math>Q = 3</math>. Ponieważ <math>\gcd (Q, m) = 3 > 1</math>, to po wykonaniu linii nr 8 (ostatnia linia) zwracany jest wektor <code>[0, 0]</code>.

Jeżeli <math>(- 11 \mid 6 k + 3) = 1</math>, to wykonywana jest linia nr 3, w&nbsp;wyniku czego następuje przejście do kolejnej wartości <code>a</code>, która jest równa <math>13</math>.


Jeżeli <math>(13 \mid 6 k + 3) = 0</math>, to wykonywana jest linia nr 4, w&nbsp;wyniku czego zwracany jest wektor <code>[0, 0]</code>.

Jeżeli <math>(13 \mid 6 k + 3) = - 1</math>, to wykonywana jest linia nr 5, w&nbsp;wyniku czego wyliczana jest wartość <code>Q</code> i&nbsp;otrzymujemy <math>Q = - 3</math>. Ponieważ <math>\gcd (Q, m) = 3 > 1</math>, to po wykonaniu linii nr 8 (ostatnia linia) zwracany jest wektor <code>[0, 0]</code>.

Jeżeli <math>(13 \mid 6 k + 3) = 1</math>, to wykonywana jest linia nr 3, w&nbsp;wyniku czego następuje przejście do kolejnej wartości <code>a</code>, która jest równa <math>- 15</math>.


Ponieważ <math>(- 15 \mid 6 k + 3) = 0</math>, to wykonywana jest linia nr 4, w&nbsp;wyniku czego zwracany jest wektor <code>[0, 0]</code>.


Pokazaliśmy, że funkcje <code>MethodA(m, 9)</code> i <code>MethodA(m, -11)</code> zwracają takie same wartości dla wszystkich niekwadratowych liczb nieparzystych <math>m</math>.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga P13</span><br/>
Podobnie, jak w&nbsp;przypadku liczb pseudopierwszych Lucasa LPSP(<math>P, Q</math>) i&nbsp;w&nbsp;przypadku liczb silnie pseudopierwszych Lucasa SLPSP(<math>P, Q</math>), tak i&nbsp;w&nbsp;przypadku liczb pseudopierwszych Dicksona drugiego rodzaju D2PSP(<math>P, Q</math>) możemy testować pierwszość liczby <math>m</math>, wybierając liczby <math>P, Q</math> losowo lub zastosować wybraną metodę postępowania. Przyjmując zmodyfikowaną postać funkcji <code>MethodA()</code>, możemy łatwo napisać program:

 <span style="font-size: 90%; color:black;">Dickson2Test(m) =
 {
 '''local'''(P, Q, X);
 '''if'''( m%2 == 0, '''return'''(m == 2) );
 '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy m nie jest liczbą kwadratową
 X = MethodA(m);
 P = X[1];
 Q = X[2];
 '''if'''( P == 0, '''return'''(0) ); \\ jeżeli P = 0, to m jest liczbą złożoną
 '''if'''( modLucas(m + 1, P, Q, m)[2] == (2*Q) % m, '''return'''(1), '''return'''(0) );
 }</span>



<span style="font-size: 110%; font-weight: bold;">Przykład P14</span><br/>
Poniżej przedstawiamy najmniejsze liczby D2PSP(<math>P, Q</math>) oraz ilości tych liczb w&nbsp;zależności od wartości parametru <code>start</code> w&nbsp;funkcji <code>MethodA(m, start)</code>. Ponieważ <code>MethodA(m, 9) = MethodA(m, -11)</code> (zobacz P12), to pominęliśmy przypadek <code>MethodA(m, -11)</code>. Dla porównania w&nbsp;następnym przykładzie przedstawimy analogiczne zestawienia dla liczb SLPSP(<math>P, Q</math>).


Ilość liczb pseudopierwszych Dicksona drugiego rodzaju mniejszych od <math>10^n</math> dla różnych parametrów <code>start</code> funkcji <code>MethodA()</code>.

{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
! <math>\boldsymbol{n}</math> 
| style="width: 20px;" | <math>2</math> || style="width: 20px;" | <math>3</math> || style="width: 20px;" | <math>4</math> || style="width: 20px;" | <math>5</math> || style="width: 20px;" | <math>6</math> || style="width: 20px;" | <math>7</math> || style="width: 20px;" | <math>8</math> || style="width: 20px;" | <math>9</math> || style="width: 20px;" | <math>10</math> || style="width: 20px;" | <math>11</math> || style="width: 20px;" | <math>12</math> || style="width: 20px;" | <math>13</math> || style="width: 20px;" | <math>14</math> || style="width: 20px;" | <math>15</math> 
|-
! style="text-align: left" | MethodA(m, "*")<ref name="BaillieFioriWagstaff1"/>
| <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>3</math> || <math>3</math> || <math>4</math> || <math>5</math> 
|-
! style="text-align: left" | MethodA(m, 5) 
| <math>0</math> || <math>0</math> || <math>2</math> || <math>4</math> || <math>18</math> || <math>55</math> || <math>145</math> || <math>383</math> || <math>914</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -7) 
| <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 9) 
| <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 13) 
| <math>0</math> || <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>2</math> || <math>3</math> || <math>3</math> || <math>3</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -15) 
| <math>0</math> || <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>2</math> || <math>3</math> || <math>4</math> || <math>4</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 17) 
| <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>1</math> || <math>3</math> || <math>4</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -19) 
| <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 21) 
| <math>0</math> || <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -23) 
| <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 25) 
| <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -27) 
| <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 29) 
| <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>2</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -31) 
| <math>1</math> || <math>1</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 33) 
| <math>0</math> || <math>0</math> || <math>0</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math>2</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|}


Najmniejsze liczby pseudopierwsze Dicksona drugiego rodzaju dla różnych parametrów <code>start</code> funkcji <code>MethodA()</code>. Pogrubioną czcionką zostały zaznaczone te liczby, które są jednocześnie silnie pseudopierwszymi liczbami Lucasa (dla tego samego parametru <code>start</code>).

{| class="wikitable plainlinks"  style="font-size: 90%; text-align: left; margin-right: auto;"
! style="text-align: left" | MethodA(m, "*")<ref name="BaillieFioriWagstaff1"/>
| <math>913, 150267335403, 430558874533, 14760229232131, 936916995253453</math>
|-
! style="text-align: left" | MethodA(m, 5) 
| <math>1127, \boldsymbol{5777}, \boldsymbol{10877}, \boldsymbol{75077}, \boldsymbol{100127}, \boldsymbol{113573}, 139127, 154697, \boldsymbol{161027}, \boldsymbol{162133}, \boldsymbol{231703}, \boldsymbol{430127}, 472453, 567643, 629693, \boldsymbol{635627}, \ldots</math>
|-
! style="text-align: left" | MethodA(m, -7) 
| <math>509140495, \dots, 14760229232131</math>
|-
! style="text-align: left" | MethodA(m, 9) 
| <math>8788015</math>
|-
! style="text-align: left" | MethodA(m, 13) 
| <math>2263, 8788015, 59839087</math>
|-
! style="text-align: left" | MethodA(m, -15) 
| <math>2263, 3086759, 59839087, 166044803</math>
|-
! style="text-align: left" | MethodA(m, 17) 
| <math>58982383, 166044803, 209562267, 2676099095</math>
|-
! style="text-align: left" | MethodA(m, -19) 
| <math>58982383, ..., 101378999149</math>
|-
! style="text-align: left" | MethodA(m, 21) 
| <math>1121, ..., 101378999149</math>
|-
! style="text-align: left" | MethodA(m, -23) 
| <math>155, 20709031, ..., 101378999149</math>
|-
! style="text-align: left" | MethodA(m, 25) 
| <math>..., 101378999149</math>
|-
! style="text-align: left" | MethodA(m, -27) 
| <math>..., 101378999149</math>
|-
! style="text-align: left" | MethodA(m, 29) 
| <math>2004987, 1084387931, ..., 101378999149</math>
|-
! style="text-align: left" | MethodA(m, -31) 
| <math>27, 4611, 4105612299, ..., 101378999149</math>
|-
! style="text-align: left" | MethodA(m, 33) 
| <math>94669, 2026655153, ..., 101378999149</math>
|}


Liczby w&nbsp;pierwszym wierszu są tak duże, że możemy co najwyżej zweryfikować, czy są D2PSP(<math>P, Q</math>)

 <span style="font-size: 90%; color:black;">X = [913, 150267335403, 430558874533, 14760229232131, 936916995253453]
 for(k = 1, length(X), print( Dickson2Test(X[k]) ))</span>

Równie łatwo sprawdzamy, że

 <span style="font-size: 90%; color:black;">Dickson2Test(14760229232131, 5) == 1
 Dickson2Test(14760229232131, -7) == 1</span>


Czytelnik zapewne zwrócił uwagę na liczbę <math>m = 101378999149 = 43 \cdot 73 \cdot 109 \cdot 296299</math>, która pojawia się aż w&nbsp;ośmiu kolejnych wierszach. Kiedy i&nbsp;dlaczego taka sytuacja ma miejsce?

Jest tak wtedy, gdy dla <math>r</math> kolejnych liczb <math>a_k</math>, gdzie <math>a_k = (- 1)^k (2 k + 1)</math> mamy

::<math>(a_k \mid m) = (a_{k + 1} \mid m) = \ldots = (a_{k + r - 1} \mid m) = 1</math>

oraz

::<math>(a_{k + r} \mid m) = - 1</math>

a ponadto liczba <math>m</math> jest liczbą pseudopierwszą Dicksona drugiego rodzaju dla parametrów <math>P, Q</math> wyliczonych przy pomocy funkcji <code>MethodA()</code> z&nbsp;liczby <math>a_{k + r}</math>, czyli <math>P = 1</math>, <math>Q = (1 - a_{k + r}) / 4</math>.

Ponieważ w&nbsp;pętli <code>while</code> funkcji <code>MethodA()</code> mamy następujące linie

 <span style="font-size: 90%; color:black;">a = -a - 2*'''sign'''(a); \\ następny wyraz ciągu (a_k)
 js = jacobi(a, m);
 '''if'''( js == 1, '''next'''() );</span>

to dla wszystkich liczb <math>a_j</math>, gdzie <math>k \leqslant j \leqslant k + r - 1</math> następuje przejście do liczby <math>a_{j + 1}</math>, aż do osiągnięcia wartości <math>a_{k + r}</math>.





== Silnie pseudopierwsze liczby Lucasa i&nbsp;zmodyfikowana metoda Selfridge'a ==

<span style="font-size: 110%; font-weight: bold;">Przykład P15</span><br/>
Poniżej przedstawiamy najmniejsze liczby SLPSP(<math>P, Q</math>) oraz ilości tych liczb w&nbsp;zależności od wartości parametru <code>start</code> w&nbsp;funkcji <code>MethodA(m, start)</code>. Ponieważ <code>MethodA(m, 9) = MethodA(m, -11)</code> (zobacz P12), to pominęliśmy przypadek <code>MethodA(m, -11)</code>.


Ilość silnie pseudopierwszych liczb Lucasa mniejszych od <math>10^n</math> dla różnych parametrów <code>start</code> funkcji <code>MethodA()</code>.

{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
! <math>\boldsymbol{n}</math> 
| style="width: 20px;" | <math>2</math> || style="width: 20px;" | <math>3</math> || style="width: 20px;" | <math>4</math> || style="width: 20px;" | <math>5</math> || style="width: 20px;" | <math>6</math> || style="width: 20px;" | <math>7</math> || style="width: 20px;" | <math>8</math> || style="width: 20px;" | <math>9</math> || style="width: 20px;" | <math>10</math> || style="width: 20px;" | <math>11</math> || style="width: 20px;" | <math>12</math> || style="width: 20px;" | <math>13</math> || style="width: 20px;" | <math>14</math> || style="width: 20px;" | <math>15</math> 
|-
! style="text-align: left" | MethodA(m, "*")<ref name="Jacobsen1"/>
| <math>0</math> || <math>0</math> || <math>2</math> || <math>12</math> || <math>58</math> || <math>178</math> || <math>505</math> || <math>1415</math> || <math>3622</math> || <math>9714</math> || <math>25542</math> || <math>67045</math> || <math>178118</math> || <math>474971</math>
|-
! style="text-align: left" | MethodA(m, 5) 
| <math>0</math> || <math>0</math> || <math>2</math> || <math>12</math> || <math>58</math> || <math>178</math> || <math>505</math> || <math>1415</math> || <math>3622</math> || <math>9714</math> || <math>25542</math> || <math>67045</math> || <math>178118</math> || <math>474971</math> 
|-
! style="text-align: left" | MethodA(m, -7) 
| <math>0</math> || <math>0</math> || <math>1</math> || <math>14</math> || <math>62</math> || <math>210</math> || <math>601</math> || <math>1625</math> || <math>4261</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 9) 
| <math>0</math> || <math>1</math> || <math>3</math> || <math>20</math> || <math>73</math> || <math>219</math> || <math>604</math> || <math>1575</math> || <math>4162</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 13) 
| <math>0</math> || <math>2</math> || <math>5</math> || <math>23</math> || <math>67</math> || <math>200</math> || <math>545</math> || <math>1443</math> || <math>3891</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -15) 
| <math>0</math> || <math>3</math> || <math>5</math> || <math>28</math> || <math>84</math> || <math>236</math> || <math>696</math> || <math>1953</math> || <math>5226</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 17) 
| <math>0</math> || <math>2</math> || <math>5</math> || <math>13</math> || <math>46</math> || <math>147</math> || <math>396</math> || <math>1091</math> || <math>2931</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -19) 
| <math>0</math> || <math>2</math> || <math>5</math> || <math>21</math> || <math>66</math> || <math>202</math> || <math>557</math> || <math>1493</math> || <math>3978</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 21) 
| <math>0</math> || <math>3</math> || <math>7</math> || <math>24</math> || <math>79</math> || <math>242</math> || <math>643</math> || <math>1723</math> || <math>4498</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -23) 
| <math>0</math> || <math>3</math> || <math>8</math> || <math>24</math> || <math>88</math> || <math>236</math> || <math>639</math> || <math>1722</math> || <math>4597</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 25) 
| <math>0</math> || <math>3</math> || <math>11</math> || <math>37</math> || <math>105</math> || <math>295</math> || <math>812</math> || <math>2188</math> || <math>5879</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -27) 
| <math>0</math> || <math>3</math> || <math>11</math> || <math>38</math> || <math>108</math> || <math>299</math> || <math>827</math> || <math>2224</math> || <math>5972</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 29) 
| <math>1</math> || <math>2</math> || <math>5</math> || <math>27</math> || <math>69</math> || <math>160</math> || <math>500</math> || <math>1364</math> || <math>3583</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, -31) 
| <math>1</math> || <math>1</math> || <math>5</math> || <math>19</math> || <math>72</math> || <math>194</math> || <math>573</math> || <math>1551</math> || <math>3928</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|-
! style="text-align: left" | MethodA(m, 33) 
| <math>0</math> || <math>0</math> || <math>5</math> || <math>19</math> || <math>73</math> || <math>199</math> || <math>537</math> || <math>1460</math> || <math>3705</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> 
|}


Najmniejsze silnie pseudopierwsze liczby Lucasa dla różnych parametrów <code>start</code> funkcji <code>MethodA()</code>. Pogrubioną czcionką zostały zaznaczone te liczby, które są jednocześnie pseudopierwszymi liczbami Dicksona drugiego rodzaju (dla tego samego parametru <code>start</code>).

{| class="wikitable plainlinks"  style="font-size: 90%; text-align: left; margin-right: auto;"
! style="text-align: left" | MethodA(m, "*") 
| <math>5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 58519, 75077, 97439, 100127, 113573, 115639, 130139, 155819, 158399, \ldots</math>
|-
! style="text-align: left" | MethodA(m, 5) 
| <math>5459, \boldsymbol{5777}, \boldsymbol{10877}, 16109, 18971, 22499, 24569, 25199, 40309, 58519, \boldsymbol{75077}, 97439, \boldsymbol{100127}, \boldsymbol{113573}, 115639, 130139, 155819, 158399, \ldots</math>
|-
! style="text-align: left" | MethodA(m, -7) 
| <math>5459, 10403, 16109, 18971, 22499, 24569, 25199, 40309, 40553, 51983, 58519, 70523, 81407, 97439, 113423, 115639, 130139, 155819, \ldots</math>
|-
! style="text-align: left" | MethodA(m, 9) 
| <math>899, 1127, 2407, 10403, 10877, 13817, 16109, 18971, 22499, 32399, 39203, 40553, 51983, 57599, 64979, 81407, 82109, 93023, 97289, \ldots</math>
|-
! style="text-align: left" | MethodA(m, 13) 
| <math>799, 989, 1127, 2407, 5429, 10793, 10877, 13529, 13817, 15539, 16109, 19109, 22499, 24119, 27403, 32399, 35459, 37399, 37949, 57599, \ldots</math>
|-
! style="text-align: left" | MethodA(m, -15) 
| <math>559, 899, 989, 1127, 3599, 10793, 10877, 11663, 13529, 15539, 19109, 22499, 23939, 24119, 27403, 32399, 41309, 46079, 49769, 57599, \ldots</math>
|-
! style="text-align: left" | MethodA(m, 17) 
| <math>559, 899, 1127, 1769, 3479, 10793, 10877, 11663, 34271, 60377, 62831, 70337, 96029, 103739, 112391, 114911, 126479, 159731, 186659, \ldots</math>
|-
! style="text-align: left" | MethodA(m, -19) 
| <math>559, 899, 1769, 5207, 8579, 10793, 11663, 12449, 32239, 34271, 58589, 60377, 62831, 70337, 72389, 72899, 79883, 84419, 93869, 96029, \ldots</math>
|-
! style="text-align: left" | MethodA(m, 21) 
| <math>143, 629, 899, 2881, 3791, 5183, 5207, 10793, 11663, 12449, 16279, 17621, 20473, 36863, 38869, 48707, 62831, 65207, 79523, 79883, 87047, \ldots</math>
|-
! style="text-align: left" | MethodA(m, -23) 
| <math>143, 629, 899, 2881, 5183, 5207, 5777, 6901, 10793, 12449, 16279, 22753, 29369, 36863, 37151, 51179, 51641, 62831, 72863, 79523, 79883, \ldots</math>
|-
! style="text-align: left" | MethodA(m, 25) 
| <math>143, 629, 899, 1763, 2881, 4619, 5183, 5207, 5777, 6439, 6901, 10793, 12449, 16279, 19043, 22753, 31877, 32399, 37151, 37949, 39203, 48827, \ldots</math>
|-
! style="text-align: left" | MethodA(m, -27) 
| <math>143, 629, 899, 1763, 2881, 4619, 5183, 5207, 5777, 6439, 6901, 10793, 12449, 16279, 19043, 20705, 22753, 31877, 32399, 37151, 37949, 39203, \ldots</math>
|-
! style="text-align: left" | MethodA(m, 29) 
| <math>989, 2881, 6439, 6901, 10403, 10877, 11327, 13199, 13529, 16279, 17249, 19109, 21299, 22753, 33947, 37127, 46031, 60587, 61913, 64523, \ldots</math>
|-
! style="text-align: left" | MethodA(m, -31) 
| <math>1007, 2743, 6439, 6901, 10403, 13199, 15503, 17249, 21299, 22577, 33947, 37127, 50399, 60587, 88409, 89389, 97663, 99007, 101567, 107879, \ldots</math>
|-
! style="text-align: left" | MethodA(m, 33) 
| <math>1829, 3007, 5777, 6901, 8909, 10403, 13529, 21299, 22577, 28673, 30743, 33947, 36893, 37127, 64523, 64619, 88409, 89389, 98789, 112949, \ldots</math>
|}



<span style="font-size: 110%; font-weight: bold;">Uwaga P16</span><br/>
Przyglądając się wierszom drugiej tabeli z&nbsp;przykładu P15, łatwo zauważamy, że w&nbsp;wierszach położonych blisko siebie często występują te same liczby. Zbadamy teraz, ile jest wspólnych liczb między poszczególnymi wierszami.

Pokazana niżej tabela powstała po znalezienia wszystkich liczb <code>SLPSP(m, a)</code>, gdzie

::<math>a \in \{</math><big><tt>"*"</tt></big><math>, -7, 9, 13, -15, 17, -19, 21, -23, 25, -27, 29, -31, 33 \}</math>

i <math>m < 10^{10}</math>. Następnie policzyliśmy ilość liczb SLPSP wspólnych dla różnych parametrów <math>a</math>.

Zauważamy, że im bardziej odległe są parametry <code>a</code>, to tym mniej pojawia się wspólnych liczb SLPSP.

Ten sam efekt występuje w&nbsp;przypadku liczb D2PSP. Choć dysponujemy w&nbsp;tym przypadku zaledwie 25 różnymi liczbami (nie uwzględniamy liczb wypisanych w&nbsp;drugim wierszu), to zdarza się, że powtarzają się one w&nbsp;sąsiadujących wierszach.

Wynika stąd praktyczny wniosek: jeśli chcemy przeprowadzić dwa testy <code>SLPSP(m, a)</code> dla różnych parametrów <code>a</code>, to powinny to być raczej <code>SLPSP(m, "*")</code> i <code>SLPSP(m, 33)</code>, a&nbsp;nie np. <code>SLPSP(m, "*")</code> i <code>SLPSP(m, -7)</code>.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{a}</math> || <big><tt>"*"</tt></big> || <math>\boldsymbol{-7}</math> || <math>\boldsymbol{9}</math> || <math>\boldsymbol{13}</math> || <math>\boldsymbol{-15}</math> || <math>\boldsymbol{17}</math> || <math>\boldsymbol{-19}</math> || <math>\boldsymbol{21}</math> || <math>\boldsymbol{-23}</math> || <math>\boldsymbol{25}</math> || <math>\boldsymbol{-27}</math> || <math>\boldsymbol{29}</math> || <math>\boldsymbol{-31}</math> || <math>\boldsymbol{33}</math>
|-
! <big><tt>"*"</tt></big> 
| <math>—</math> || <math>2904</math> || <math>1203</math> || <math>711</math> || <math>655</math> || <math>199</math> || <math>223</math> || <math>199</math> || <math>199</math> || <math>236</math> || <math>236</math> || <math>180</math> || <math>179</math> || <math>173</math>
|-
! <math>\boldsymbol{-7}</math> 
| <math>2904</math> || <math>—</math> || <math>1760</math> || <math>855</math> || <math>743</math> || <math>256</math> || <math>288</math> || <math>290</math> || <math>216</math> || <math>260</math> || <math>261</math> || <math>213</math> || <math>221</math> || <math>198</math>
|-
! <math>\boldsymbol{9}</math> 
| <math>1203</math> || <math>1760</math> || <math>—</math> || <math>1897</math> || <math>1483</math> || <math>448</math> || <math>421</math> || <math>417</math> || <math>343</math> || <math>436</math> || <math>436</math> || <math>196</math> || <math>181</math> || <math>228</math>
|-
! <math>\boldsymbol{13}</math> 
| <math>711</math> || <math>855</math> || <math>1897</math> || <math>—</math> || <math>2833</math> || <math>777</math> || <math>609</math> || <math>436</math> || <math>370</math> || <math>351</math> || <math>351</math> || <math>196</math> || <math>170</math> || <math>188</math>
|-
! <math>\boldsymbol{-15}</math> 
| <math>655</math> || <math>743</math> || <math>1483</math> || <math>2833</math> || <math>—</math> || <math>1313</math> || <math>1064</math> || <math>727</math> || <math>613</math> || <math>578</math> || <math>578</math> || <math>303</math> || <math>260</math> || <math>291</math>
|-
! <math>\boldsymbol{17}</math> 
| <math>199</math> || <math>256</math> || <math>448</math> || <math>777</math> || <math>1313</math> || <math>—</math> || <math>2037</math> || <math>1146</math> || <math>862</math> || <math>654</math> || <math>654</math> || <math>171</math> || <math>129</math> || <math>137</math>
|-
! <math>\boldsymbol{-19}</math> 
| <math>223</math> || <math>288</math> || <math>421</math> || <math>609</math> || <math>1064</math> || <math>2037</math> || <math>—</math> || <math>2231</math> || <math>1668</math> || <math>1236</math> || <math>1236</math> || <math>241</math> || <math>199</math> || <math>190</math>
|-
! <math>\boldsymbol{21}</math> 
| <math>199</math> || <math>290</math> || <math>417</math> || <math>436</math> || <math>727</math> || <math>1146</math> || <math>2231</math> || <math>—</math> || <math>3251</math> || <math>2342</math> || <math>2342</math> || <math>336</math> || <math>278</math> || <math>270</math>
|-
! <math>\boldsymbol{-23}</math> 
| <math>199</math> || <math>216</math> || <math>343</math> || <math>370</math> || <math>613</math> || <math>862</math> || <math>1668</math> || <math>3251</math> || <math>—</math> || <math>2937</math> || <math>2937</math> || <math>475</math> || <math>360</math> || <math>275</math>
|-
! <math>\boldsymbol{25}</math> 
| <math>236</math> || <math>260</math> || <math>436</math> || <math>351</math> || <math>578</math> || <math>654</math> || <math>1236</math> || <math>2342</math> || <math>2937</math> || <math>—</math> || <math>5879</math> || <math>855</math> || <math>657</math> || <math>480</math>
|-
! <math>\boldsymbol{-27}</math> 
| <math>236</math> || <math>261</math> || <math>436</math> || <math>351</math> || <math>578</math> || <math>654</math> || <math>1236</math> || <math>2342</math> || <math>2937</math> || <math>5879</math> || <math>—</math> || <math>857</math> || <math>659</math> || <math>480</math>
|-
! <math>\boldsymbol{29}</math> 
| <math>180</math> || <math>213</math> || <math>196</math> || <math>196</math> || <math>303</math> || <math>171</math> || <math>241</math> || <math>336</math> || <math>475</math> || <math>855</math> || <math>857</math> || <math>—</math> || <math>2079</math> || <math>1003</math>
|-
! <math>\boldsymbol{-31}</math> 
| <math>179</math> || <math>221</math> || <math>181</math> || <math>170</math> || <math>260</math> || <math>129</math> || <math>199</math> || <math>278</math> || <math>360</math> || <math>657</math> || <math>659</math> || <math>2079</math> || <math>—</math> || <math>1857</math>
|-
! <math>\boldsymbol{33}</math> 
| <math>173</math> || <math>198</math> || <math>228</math> || <math>188</math> || <math>291</math> || <math>137</math> || <math>190</math> || <math>270</math> || <math>275</math> || <math>480</math> || <math>480</math> || <math>1003</math> || <math>1857</math> || <math>—</math>
|}





== Wzmocnienie testu BPSW ==

<span style="font-size: 110%; font-weight: bold;">Uwaga P17</span><br/>
Dla wszystkich rozpatrywanych tutaj parametrów <code>start</code> takich, że

::<tt>start</tt> <math>\in \{</math><tt>"*"</tt><math>, -7, 9, 13, -15, 17, -19, 21, -23, 25, -27, 29, -31, 33 \}</math>

(czyli poza przypadkiem niezmodyfikowanej metody Selfridge'a – funkcja <code>MethodA(m, 5)</code>) znaleźliśmy <math>25</math> liczb pseudopierwszych Dicksona drugiego rodzaju. Większość z&nbsp;nich to liczby mniejsze od <math>10^{10}</math> (zobacz P14). Żadna z&nbsp;tych liczb nie jest silnie pseudopierwszą liczbą Lucasa (SLPSP) i&nbsp;nie zależy to od wyboru wartości parametru <code>start</code> w&nbsp;funkcji <code>StrongLucasTest(m, start)</code> (również dla <code>start = 5</code>).

Przypomnijmy, że nie znamy liczb nieparzystych <math>m</math>, które byłyby jednocześnie liczbami silnie pseudopierwszymi (SPSP) i&nbsp;silnie pseudopierwszymi liczbami Lucasa (SLPSP) dla <math>m < 2^{64}</math>. Jest bardzo prawdopodobne, że równie rzadko występują liczby, które są jednocześnie silnie pseudopierwszymi liczbami Lucasa (SLPSP) i&nbsp;pseudopierwszymi liczbami Dicksona drugiego rodzaju (D2PSP). Stanowi to dobrą przesłankę do wzmocnienia testu BPSW.


Zatem wykorzystując funkcję Dickson2Test(m), możemy otrzymać test znacznie silniejszy od testu BPSW.

 <span style="font-size: 90%; color:black;">BPSW2test(m) =
 {
 '''local'''(p);
 '''forprime'''(p = 2, 1000, '''if'''( m % p > 0, next() ); '''if'''( m == p, '''return'''(1), '''return'''(0) ));
 '''if'''( !isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2), '''return'''(0) );
 '''if'''( !StrongLucasTest(m), '''return'''(0) );
 '''if'''( !Dickson2Test(m), '''return'''(0), '''return'''(1) );
 }</span>


Oczywiście możemy (a nawet powinniśmy), napisać program, w&nbsp;którym połączymy testy StrongLucasTest(m) i&nbsp;Dickson2Test(m).

 <span style="font-size: 90%; color:black;">StrongLucasAndDickson2Test(m) =
 {
 '''local'''(a, b, c, k, P, Q, r, SLT, w, X);
 '''if'''( m%2 == 0, '''return'''(m == 2) );
 '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy liczba m nie jest kwadratowa
 X = MethodA(m);
 P = X[1];
 Q = X[2];
 '''if'''( P == 0, '''return'''(0) ); \\ jeżeli P = 0, to m jest liczbą złożoną
 r = '''valuation'''(m + 1, 2); \\ znajdujemy wykładnik, z jakim liczba 2 występuje w m + 1
 w = (m + 1) / 2^r;
 X =  modLucas(w, P, Q, m);
 a = X[1]; \\ U_w(P, Q) % m
 b = X[2]; \\ V_w(P, Q) % m
 SLT = 0;
 '''if'''( a == 0 || b == 0, SLT = 1 ); \\ b == 0 to przypadek k == 0
 c = modPower(Q, w, m); \\ Q^w % m
 k = 0;
 \\ sprawdzamy warunek V_(2^k * w) %m = 0; korzystamy ze wzoru V_(2*w) = (V_w)^2 - 2*Q^w
 '''while'''( k++ < r,
        b = (b^2 - 2*c) % m;
        '''if'''( SLT == 0  &&  b == 0, SLT = 1 );
        c = c^2 % m;
      );
 '''if'''( SLT == 0, '''return'''(0) ); \\ liczba m nie przeszła silnego testu Lucasa
 b = (b^2 - 2*c) % m; \\ V_(m+1)(P, Q) % m
 '''if'''( b == (2*Q) % m, '''return'''(1), '''return'''(0) );
 }</span>


Zauważmy, że po takim połączeniu czas obliczeń w&nbsp;przypadku testu BPSW2(m) nie ulega praktycznie wydłużeniu w&nbsp;stosunku do testu BPSW(m), bo funkcja modLucas() wylicza jednocześnie liczby <math>U_m (P, Q)</math> i <math>V_m (P, Q)</math> modulo <math>n</math>. Uzyskaliśmy w&nbsp;ten sposób bardzo silne narzędzie do badania pierwszości liczb:

 <span style="font-size: 90%; color:black;">BPSW2test(m) =
 {
 '''local'''(p);
 '''forprime'''(p = 2, 1000, '''if'''( m % p > 0, '''next'''() ); '''if'''( m == p, '''return'''(1), '''return'''(0) ));
 '''if'''( !isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2), '''return'''(0) );
 '''if'''( !StrongLucasAndDickson2Test(m), '''return'''(0), '''return'''(1) );
 }</span>





== Uzupełnienie ==

Dowody twierdzeń P18 i&nbsp;P19 zostały oparte na pomyśle przedstawionym przez Bailliego, Fioriego i&nbsp;Wagstaffa<ref name="BaillieFioriWagstaff1"/>.<br/>
<span style="font-size: 110%; font-weight: bold;">Twierdzenie P18</span><br/>
Liczba nieparzysta <math>m</math> jest LPSP(<math>1, - 1</math>) wtedy i&nbsp;tylko wtedy, gdy <math>m</math> jest LPSP(<math>5, 5</math>).

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
W zadaniu N12 połóżmy <math>Q = 1</math> i&nbsp;konsekwentnie <math>P = 4 Q + 1 = 5</math>. Pierwszy z&nbsp;wypisanych wzorów przyjmie postać

::<math>U_{2 k} (5, 5) = 5^k U_{2 k} (1, - 1)</math>

Z założenia <math>m</math> jest liczbą nieparzystą, zatem dla parzystej liczby <math>m - \epsilon</math>, gdzie <math>\epsilon = (D \mid m) = \pm 1</math> jest

::<math>U_{m - \epsilon} (5, 5) = 5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1)</math>

Zauważmy, że

:* dla <math>(P, Q) = (1, - 1) \;\; \text{i} \;\; (P, Q) = (5, 5)</math> jest <math>D = P^2 - 4 Q = 5</math>
:* <math>\gcd (m, - 5) = 1</math> wtedy i&nbsp;tylko wtedy, gdy <math>\gcd (m, 25) = 1</math>
:* <math>U_{m - \epsilon} (5, 5) \equiv 5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1) \pmod{m}</math>

<math>\Large{\Longrightarrow}</math>

Jeżeli <math>m</math> jest LPSP(<math>1, - 1</math>), to <math>\gcd (m, - 5) = 1</math> i <math>U_{m - \epsilon} (1, - 1) \equiv 0 \pmod{m}</math>, zatem <math>\gcd (m, 25) = 1</math> i <math>U_{m - \epsilon} (5, 5) \equiv 0 \pmod{m}</math>. Czyli <math>m</math> jest LPSP(<math>5, 5</math>).

<math>\Large{\Longleftarrow}</math>

Jeżeli <math>m</math> jest LPSP(<math>5, 5</math>), to <math>\gcd (m, 25) = 1</math> i <math>U_{m - \epsilon} (5, 5) \equiv 0 \pmod{m}</math>, zatem <math>\gcd (m, - 5) = 1</math> i

::<math>5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1) \equiv 0 \pmod{m}</math>

Ponieważ <math>\gcd (m, 5) = 1</math>, to z&nbsp;powyższej kongruencji wynika natychmiast, że (zobacz C75)

::<math>U_{m - \epsilon} (1, - 1) \equiv 0 \pmod{m}</math>

Czyli <math>m</math> jest LPSP(<math>1, - 1</math>). Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie P19</span><br/>
Liczba nieparzysta <math>m</math> jest SLPSP(<math>1, - 1</math>) wtedy i&nbsp;tylko wtedy, gdy <math>m</math> jest SLPSP(<math>5, 5</math>).

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
W zadaniu N12 połóżmy <math>Q = 1</math> i&nbsp;konsekwentnie <math>P = 4 Q + 1 = 5</math>. Drugi, czwarty i&nbsp;trzeci z&nbsp;wypisanych wzorów przyjmą postać

::<math>U_{2 k + 1} (5, 5) = 5^k V_{2 k + 1} (1, - 1)</math>

::<math>V_{2 k + 1} (5, 5) = 5^{k + 1} U_{2 k + 1} (1, - 1)</math>

::<math>V_{2 k} (5, 5) = 5^k V_{2 k} (1, - 1)</math>


Niech <math>m - (D \mid m) = 2^r w</math>, gdzie <math>w</math> jest liczbą nieparzystą. Uwzględniając wypisane wyżej wzory, zauważmy, że

:* dla <math>(P, Q) = (1, - 1) \;\; \text{i} \;\; (P, Q) = (5, 5)</math> jest <math>D = P^2 - 4 Q = 5</math>
:* <math>\gcd (m, - 5) = 1</math> wtedy i&nbsp;tylko wtedy, gdy <math>\gcd (m, 25) = 1</math>
:* <math>U_w (5, 5) \equiv 5^{(w - 1) / 2} V_w (1, - 1) \pmod{m}</math>
:* <math>V_w (5, 5) \equiv 5^{(w + 1) / 2} U_w (1, - 1) \pmod{m}</math>
:* <math>V_{2^j w} (5, 5) \equiv 5^{2^{j - 1} w} V_{2^j w} (1, - 1) \pmod{m} \qquad</math> gdzie <math>j \geqslant 1</math>


Liczba <math>m</math> jest SLPSP(<math>1, - 1</math>) jeżeli <math>\gcd (m, - 5) = 1</math> i&nbsp;zachodzi dokładnie jeden z&nbsp;warunków

::A) <math>\; U_w (1, - 1) \equiv 0 \pmod{m}</math>

::B) <math>\; V_w (1, - 1) \equiv 0 \pmod{m}</math>

::C) <math>\; V_{2^j w} (1, - 1) \equiv 0 \pmod{m} \qquad</math> dla pewnego <math>j \in [1, r - 1]</math> (w przypadku, gdy <math>r \geqslant 2</math>)


Podobnie, liczba <math>m</math> jest SLPSP(<math>5, 5</math>) jeżeli <math>\gcd (m, 25) = 1</math> i&nbsp;zachodzi dokładnie jeden z&nbsp;warunków

::a) <math>\; U_w (5, 5) \equiv 0 \pmod{m}</math>

::b) <math>\; V_w (5, 5) \equiv 0 \pmod{m}</math>

::c) <math>\; V_{2^j w} (5, 5) \equiv 0 \pmod{m} \qquad</math> dla pewnego <math>j \in [1, r - 1] </math> (w przypadku, gdy <math>r \geqslant 2</math>)

<math>\Large{\Longrightarrow}</math>

Jeżeli <math>m</math> jest SLPSP(<math>1, - 1</math>), to <math>\gcd (m, - 5) = 1</math> i&nbsp;zachodzi dokładnie jeden z&nbsp;warunków A), B), C). Zatem <math>\gcd (m, 25) = 1</math> i&nbsp;zachodzi dokładnie jeden z&nbsp;warunków a), b), c). Czyli <math>m</math> jest SLPSP(<math>5, 5</math>).

<math>\Large{\Longleftarrow}</math>

Jeżeli <math>m</math> jest SLPSP(<math>5, 5</math>), to <math>\gcd (m, 25) = 1</math> i&nbsp;zachodzi dokładnie jeden z&nbsp;warunków a), b), c). Zatem <math>\gcd (m, - 5) = 1</math> i&nbsp;zachodzi dokładnie jedna z&nbsp;kongruencji

::<math>5^{(w - 1) / 2} V_w (1, - 1) \equiv 0 \pmod{m}</math>

::<math>5^{(w + 1) / 2} U_w (1, - 1) \equiv 0 \pmod{m}</math>

::<math>5^{2^{j - 1} w} V_{2^j w} (1, - 1) \equiv 0 \pmod{m}</math>

Ponieważ <math>\gcd (m, 5) = 1</math>, to z&nbsp;powyższych wzorów wynika natychmiast, że zachodzi dokładnie jedna z&nbsp;kongruencji (zobacz C75)

::<math>V_w (1, - 1) \equiv 0 \pmod{m}</math>

::<math>U_w (1, - 1) \equiv 0 \pmod{m}</math>

::<math>V_{2^j w} (1, - 1) \equiv 0 \pmod{m}</math>

Co oznacza, że zachodzi dokładnie jeden z&nbsp;warunków A), B), C). Czyli <math>m</math> jest SLPSP(<math>1, - 1</math>). Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}





== Zestawienie funkcji ==

<span style="font-size: 110%; font-weight: bold;">Uwaga P20</span><br/>
Poniżej przedstawiamy zestawienie najważniejszych funkcji, które wykorzystywaliśmy do testowania pierwszości liczb. Zauważmy, że wprowadziliśmy drugi parametr do funkcji, które wywołują funkcję <code>MethodA()</code> tak, aby możliwe było pełne wykorzystanie tej funkcji po zmodyfikowaniu i&nbsp;związane z&nbsp;tym poprawki.

 <span style="font-size: 90%; color:black;">\\ potęgowanie 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&nbsp;jest nieparzyste, wyłączamy a&nbsp;i&nbsp;zmniejszamy n&nbsp;o&nbsp;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>



 <span style="font-size: 90%; color:black;">\\ test Millera-Rabina
 isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, a) =
 {
 '''local'''(d, k, r, x);
 '''if'''( m % 2 == 0, '''return'''(m == 2) );
 r = '''valuation'''(m - 1, 2); \\ wykładnik, z jakim liczba 2 występuje w rozwinięciu na czynniki pierwsze liczby m - 1
 d = (m - 1) / 2^r;
 x = modPower(a, d, m);
 '''if'''( x == 1 || x == m - 1, '''return'''(1) ); \\ x = m - 1 to przypadek k == 0
 k = 0;
 '''while'''( k++ < r,
        x = x^2 % m;
        '''if'''( x == m - 1, '''return'''(1) );
      );
 '''return'''(0);
 }</span>



 <span style="font-size: 90%; color:black;">\\ obliczanie symbolu Jacobiego
 jacobi(a, n) = 
 {
 '''local'''(r, w);
 '''if'''( n <= 0 || n % 2 == 0, '''return'''("Error") );
 a = a % n; \\ korzystamy ze wzoru (a|n) = (b|n), gdy a &equiv; b (mod n)
 w = 1;
 '''while'''( a <> 0,
        '''while'''( a % 2 == 0, a = a/2; r = n % 8; '''if'''( r == 3 || r == 5, w = -w ) );
        \\ usunęliśmy czynnik 2 ze zmiennej a, uwzględniając, że (2|n) = -1, gdy n &equiv; 3,5 (mod 8)
        \\ teraz zmienne a oraz n są nieparzyste
        r = a; \\ zmienna r tylko przechowuje wartość a
        a = n;
        n = r;
        '''if'''( a % 4 == 3 && n % 4 == 3, w = -w );
        \\ zamieniliśmy zmienne, uwzględniając, że (a|n) = - (n|a), gdy a &equiv; n &equiv; 3 (mod 4)
        a = a % n;
      );
 '''if'''( n == 1, '''return'''(w), '''return'''(0) ); \\ n jest teraz równe gcd(a, n)
 }</span>



 <span style="font-size: 90%; color:black;">\\ obliczanie wyrazów ciągu Lucasa modulo m
 modLucas(n, P, Q, m) =
 {
 '''local'''(A, i, s, U, U2, V, W, W2);
 '''if'''( m == 1, '''return'''([0, 0]) );
 '''if'''( n == 0, '''return'''([0, 2 % m]) );
 A = '''digits'''(n, 2); \\ otrzymujemy wektor cyfr liczby n w układzie dwójkowym
 s = '''length'''(A); \\ długość wektora A
 U = 1;
 W = P;
 i = 1;
 '''while'''( i++ <= s,
        '''if'''( A[i] == 0,  U2 = 2*U*W - P*U^2;  W2 = W^2 - Q*U^2 );
        '''if'''( A[i] == 1,  U2 = W^2 - Q*U^2;  W2 = P*W^2 - 2*Q*U*W );
        U = U2 % m;
        W = W2 % m;
      );
 V = (2*W - P*U) % m;
 '''return'''([U, V]);
 }</span>



 <span style="font-size: 90%; color:black;">\\ zmodyfikowana metoda Selfridge'a wyboru parametrów P i Q
 MethodA(m, start = "*") = 
 {
 \\ parametr start (poza "*") musi być wyrazem ciągu a_k = (-1)^k * (2*k+1) dla k >= 2
 '''local'''(a, js, Q);
 '''if'''( m%2 == 0, '''return'''("Error") );
 '''if'''( m == 1, '''return'''([0, 0]) ); \\ 1 nie jest liczbą pierwszą
 a = '''if'''( start == "*", 5, start );
 '''if'''( a%4 <> 1, '''return'''("Error") );
 a = -a + 2*'''sign'''(a); \\ poprzedni wyraz ciągu (a_k)
 '''while'''( 1,
        a = -a - 2*'''sign'''(a); \\ następny wyraz ciągu (a_k)
        js = jacobi(a, m);
        '''if'''( js == 1, '''next'''() );
        '''if'''( js == 0, '''if'''( (a % m) <> 0, '''return'''([0, 0]), '''next'''() ) );
        '''if'''( js == -1, Q = (1 - a)/4 );
        '''if'''( start == "*" && Q == -1, '''return'''([5, 5]) );
        '''if'''( '''gcd'''(Q, m) == 1, '''return'''([1, Q]) );
        '''if'''( Q % m <> 0, '''return'''([0, 0]) ); \\ gcd(Q, m) > 1
      );
 }</span>



 <span style="font-size: 90%; color:black;">\\ test Lucasa
 LucasTest(m, start = "*") =
 {
 '''local'''(P, Q, X);
 '''if'''( m % 2 == 0, '''return'''(m == 2) );
 '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy m nie jest liczbą kwadratową
 X = MethodA(m, start);
 P = X[1];
 Q = X[2];
 '''if'''( P == 0, '''return'''(0) ); \\ jeżeli P = 0, to m jest liczbą złożoną
 '''if'''( modLucas(m + 1, P, Q, m)[1] == 0, '''return'''(1), '''return'''(0) );
 }</span>



 <span style="font-size: 90%; color:black;">\\ silny test Lucasa
 StrongLucasTest(m, start = "*") =
 {
 '''local'''(a, b, c, k, P, Q, r, w, X);
 '''if'''( m%2 == 0, '''return'''(m == 2) );
 '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy liczba m nie jest kwadratowa
 X = MethodA(m, start);
 P = X[1];
 Q = X[2];
 '''if'''( P == 0, '''return'''(0) ); \\ jeżeli P = 0, to m jest liczbą złożoną
 r = '''valuation'''(m + 1, 2); \\ znajdujemy wykładnik, z jakim liczba 2 występuje w m + 1
 w = (m + 1) / 2^r;
 X =  modLucas(w, P, Q, m);
 a = X[1]; \\ U_w(P, Q) % m
 b = X[2]; \\ V_w(P, Q) % m
 '''if'''( a == 0 || b == 0, '''return'''(1) ); \\ b == 0 to przypadek k == 0
 '''if'''( r == 1, '''return'''(0) ); \\ nie ma dalszych przypadków
 c = modPower(Q, w, m); \\ Q^w % m
 k = 0;
 \\ sprawdzamy warunek V_(2^k * w) %m = 0; korzystamy ze wzoru V_(2*w) = (V_w)^2 - 2*Q^w
 '''while'''( k++ < r,
        b = (b^2 - 2*c) % m;
        '''if'''( b == 0, '''return'''(1) );
        c = c^2 % m;
      );
 '''return'''(0);
 }</span>



 <span style="font-size: 90%; color:black;">\\ test BPSW
 BPSWtest(m, start = "*") =
 {
 '''forprime'''(p = 2, 1000, '''if'''( m % p > 0, '''next'''() ); '''if'''( m == p, '''return'''(1), '''return'''(0) ));
 '''if'''( !isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2), '''return'''(0) );
 '''if'''( !StrongLucasTest(m, start), '''return'''(0), '''return'''(1) );
 }</span>



 <span style="font-size: 90%; color:black;">\\ test Dicksona2
 Dickson2Test(m, start = "*") =
 {
 '''local'''(P, Q, X);
 '''if'''( m%2 == 0, '''return'''(m == 2) );
 '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy m nie jest liczbą kwadratową
 X = MethodA(m, start);
 P = X[1];
 Q = X[2];
 '''if'''( P == 0, '''return'''(0) ); \\ jeżeli P = 0, to m jest liczbą złożoną
 '''if'''( modLucas(m + 1, P, Q, m)[2] == (2*Q) % m, '''return'''(1), '''return'''(0) );
 }</span>



 <span style="font-size: 90%; color:black;">\\ silny test Lucasa i test Dicksona2
 StrongLucasAndDickson2Test(m, start = "*") =
 {
 '''local'''(a, b, c, k, P, Q, r, SLT, w, X);
 '''if'''( m%2 == 0, '''return'''(m == 2) );
 '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy liczba m nie jest kwadratowa
 X = MethodA(m, start);
 P = X[1];
 Q = X[2];
 '''if'''( P == 0, '''return'''(0) ); \\ jeżeli P = 0, to m jest liczbą złożoną
 r = '''valuation'''(m + 1, 2); \\ znajdujemy wykładnik, z jakim liczba 2 występuje w m + 1
 w = (m + 1) / 2^r;
 X =  modLucas(w, P, Q, m);
 a = X[1]; \\ U_w(P, Q) % m
 b = X[2]; \\ V_w(P, Q) % m
 SLT = 0;
 '''if'''( a == 0 || b == 0, SLT = 1 ); \\ b == 0 to przypadek k == 0
 c = modPower(Q, w, m); \\ Q^w % m
 k = 0;
 \\ sprawdzamy warunek V_(2^k * w) %m = 0; korzystamy ze wzoru V_(2*w) = (V_w)^2 - 2*Q^w
 '''while'''( k++ < r,
        b = (b^2 - 2*c) % m;
        '''if'''( SLT == 0  &&  b == 0, SLT = 1 );
        c = c^2 % m;
      );
 '''if'''( SLT == 0, '''return'''(0) ); \\ liczba m nie przeszła silnego testu Lucasa
 b = (b^2 - 2*c) % m; \\ V_(m+1)(P, Q) % m
 '''if'''( b == (2*Q) % m, '''return'''(1), '''return'''(0) );
 }</span>



 <span style="font-size: 90%; color:black;">\\ test BPSW2
 BPSW2test(m, start = "*") =
 {
 '''forprime'''(p = 2, 1000, '''if'''( m % p > 0, '''next'''() ); '''if'''( m == p, '''return'''(1), '''return'''(0) ));
 '''if'''( !isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2), '''return'''(0) );
 '''if'''( !StrongLucasAndDickson2Test(m, start), '''return'''(0), '''return'''(1) );
 }</span>














== Przypisy ==

<references>

<ref name="D2PSP1">Zobacz prace: Andrzej Rotkiewicz, ''Lucas pseudoprimes'', (2000) oraz ''Lucas and Frobenius pseudoprimes'', (2003) i&nbsp;Lawrence Somer, ''Lucas sequences <math>\{U_k\}</math> for which <math>U_{2 p}</math> and <math>U_{p}</math> are pseudoprimes for almost all primes <math>p</math>'', (2006)</ref>

<ref name="D2PSP2">Baillie, Fiori i&nbsp;Wagstaff w&nbsp;pracy ''Strengthening the Baillie-PSW primality test'' nazywają te liczby liczbami pseudopierwszymi Lucasa-V (w skrócie: vpsp(<math>P, Q</math>)) (ang. ''Lucas-V pseudoprime'').</ref>

<ref name="D2PSP3">ang. ''Dickson pseudoprime of the second kind with parameters <math>P</math> and <math>Q</math>''</ref>

<ref name="BaillieWagstaff1">Robert Baillie and Samuel S. Wagstaff Jr., ''Lucas Pseudoprimes'', Mathematics of Computation Vol. 35, No. 152 (1980), ([http://mpqs.free.fr/LucasPseudoprimes.pdf LINK])</ref>

<ref name="BaillieFioriWagstaff1">Robert Baillie, Andrew Fiori and Samuel S. Wagstaff, Jr., ''Strengthening the Baillie-PSW primality test'', Mathematics of Computation, 90 (2021)</ref>

<ref name="Jacobsen1">Dana Jacobsen, ''Pseudoprime Statistics, Tables, and Data'', ([http://ntheory.org/pseudoprimes.html LINK])</ref>

</references>








&nbsp;