Różnica pomiędzy stronami "Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze" i "Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju"

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

12.07.2023

Podzielność wyrazów [math]\displaystyle{ V_n (P, Q) }[/math] przez liczbę pierwszą nieparzystą

Twierdzenie P1
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą.

● jeżeli [math]\displaystyle{ \; p \mid P \; }[/math] [math]\displaystyle{ \text{i} \;\; p \mid Q , \; }[/math] to [math]\displaystyle{ \; p \mid V_n \; }[/math] dla [math]\displaystyle{ n \geqslant 1 }[/math]

● jeżeli [math]\displaystyle{ \; p \mid P \; }[/math] [math]\displaystyle{ \text{i} \;\; p \nmid Q , \; }[/math] to [math]\displaystyle{ \; p \mid V_{2 n + 1} \; }[/math] i [math]\displaystyle{ \; p \nmid V_{2 n} }[/math]

● jeżeli [math]\displaystyle{ \; p \nmid P \; }[/math] [math]\displaystyle{ \text{i} \;\; p \mid Q , \; }[/math] to [math]\displaystyle{ \; p \nmid V_n \; }[/math] dla [math]\displaystyle{ n \geqslant 0 }[/math]

● jeżeli [math]\displaystyle{ \; p \mid Q , \; }[/math] to [math]\displaystyle{ \; p \mid V_n , }[/math] gdzie [math]\displaystyle{ n \geqslant 1 }[/math], wtedy i tylko wtedy, gdy [math]\displaystyle{ \; p \mid P }[/math]

● jeżeli [math]\displaystyle{ \; p \nmid P \; }[/math] [math]\displaystyle{ \text{i} \;\; p \mid D , \; }[/math] to [math]\displaystyle{ \; p \nmid V_n \; }[/math] dla [math]\displaystyle{ n \geqslant 0 }[/math]

Założenie, że [math]\displaystyle{ p \nmid P }[/math] w ostatnim punkcie jest istotne. Gdy [math]\displaystyle{ \; p \mid P \; }[/math] i [math]\displaystyle{ \; p \mid D , \; }[/math] to [math]\displaystyle{ \; p \mid Q \; }[/math] i otrzymujemy punkt pierwszy.

Dowód

Punkt 1.

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

Punkt 2.

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

[math]\displaystyle{ V_{2 n + 1} = P V_{2 n} - Q V_{2 n - 1} }[/math]

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

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

[math]\displaystyle{ V_{2 n + 2} = P V_{2 n + 1} - Q V_{2 n} }[/math]

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

Punkt 3.

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

[math]\displaystyle{ V_{n + 1} = P V_n - Q V_{n - 1} }[/math]

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

Punkt 4.

Wynika z punktów pierwszego i trzeciego.

Punkt 5.

Z twierdzenia N7 wiemy, że

[math]\displaystyle{ 2^{n - 1} V_n = \sum_{k = 0}^{\lfloor n / 2 \rfloor} \binom{n}{2 k} P^{n - 2 k} D^k }[/math]

[math]\displaystyle{ \;\, = P^n + \binom{n}{2} P^{n - 2} D + \binom{n}{4} P^{n - 4} D^2 + \ldots }[/math]

Z założenia [math]\displaystyle{ p \mid D }[/math], zatem modulo [math]\displaystyle{ p }[/math] dostajemy

[math]\displaystyle{ 2^{n - 1} V_n \equiv P^n \pmod{p} }[/math]

Ponieważ [math]\displaystyle{ p \nmid P }[/math], zatem [math]\displaystyle{ p \nmid V_n }[/math]. Co należało pokazać.
□

Twierdzenie P2
Jeżeli [math]\displaystyle{ d }[/math] jest nieparzystym dzielnikiem [math]\displaystyle{ Q }[/math], to dla [math]\displaystyle{ n \geqslant 1 }[/math] jest

[math]\displaystyle{ V_n \equiv P^n \pmod{d} }[/math]

W szczególności, gdy liczba pierwsza nieparzysta [math]\displaystyle{ p }[/math] jest dzielnikiem [math]\displaystyle{ Q }[/math], to

[math]\displaystyle{ V_p \equiv P \pmod{p} }[/math]

Dowód

Oznaczmy [math]\displaystyle{ \delta = \sqrt{D} }[/math], zatem [math]\displaystyle{ 2 \alpha = P + \delta }[/math] i [math]\displaystyle{ 2 \beta = P - \delta }[/math]. Ze wzoru dwumianowego, mamy

[math]\displaystyle{ 2^n \alpha^n = (P + \delta)^n = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} \delta^j }[/math]

[math]\displaystyle{ 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]\displaystyle{ 2^n (\alpha^n + \beta^n) = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (\delta^j + (- \delta)^j) }[/math]

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

[math]\displaystyle{ \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]\displaystyle{ Q }[/math], dostajemy (zobacz N46)

[math]\displaystyle{ 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]\displaystyle{ \:\, \equiv P^n \underset{j \; \text{parzyste}}{\sum_{j = 0}^{n}} \binom{n}{j} }[/math]

[math]\displaystyle{ \:\, \equiv 2^{n - 1} P^n \pmod{Q} }[/math]

Czyli

[math]\displaystyle{ 2^{n - 1} (V_n - P^n) \equiv 0 \pmod{Q} }[/math]

Ponieważ [math]\displaystyle{ Q }[/math] dzieli [math]\displaystyle{ 2^{n - 1} (V_n - P^n) }[/math], to tym bardziej [math]\displaystyle{ d }[/math] dzieli [math]\displaystyle{ 2^{n - 1} (V_n - P^n) }[/math]. Z założenia [math]\displaystyle{ \gcd (d, 2^{n - 1}) = 1 }[/math], zatem [math]\displaystyle{ d }[/math] dzieli [math]\displaystyle{ V_n - P^n }[/math] (zobacz C74). Co należało pokazać.

W przypadku szczególnym, gdy [math]\displaystyle{ d = n = p }[/math], gdzie [math]\displaystyle{ p }[/math] jest nieparzystą liczbą pierwszą, otrzymujemy natychmiast (zobacz J22).

[math]\displaystyle{ V_p \equiv P^p \equiv P \pmod{p} }[/math]

Co należało pokazać.
□

Twierdzenie P3
Niech [math]\displaystyle{ D = P^2 - 4 Q \neq 0 }[/math], a [math]\displaystyle{ (D \mid p) }[/math] oznacza symbol Legendre'a, gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ p \nmid Q }[/math]. Mamy

● [math]\displaystyle{ V_p \equiv P \pmod{p} }[/math]

● jeżeli [math]\displaystyle{ (D \mid p) = - 1 , \; }[/math] to [math]\displaystyle{ V_{p + 1} \equiv 2 Q \pmod{p} }[/math]

● jeżeli [math]\displaystyle{ (D \mid p) = 1 , \; }[/math] to [math]\displaystyle{ V_{p - 1} \equiv 2 \pmod{p} }[/math]

Dowód

Punkt 1.

Zauważmy, że przypadek gdy [math]\displaystyle{ p \mid Q }[/math], omówiliśmy w twierdzeniu poprzednim. Z założenia [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą. Z twierdzenia N7, w przypadku nieparzystego [math]\displaystyle{ n = p }[/math], otrzymujemy

[math]\displaystyle{ 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]\displaystyle{ k \in [1, p - 1] }[/math] jest (zobacz N43)

[math]\displaystyle{ \binom{p}{k} \equiv 0 \pmod{p} }[/math]

to modulo [math]\displaystyle{ p }[/math] dostajemy

[math]\displaystyle{ 2^{p - 1} V_p \equiv V_p \equiv P^p \equiv P \pmod{p} }[/math]

Punkt 2.

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

[math]\displaystyle{ (D \mid p) = (P^2 \mid p) = (P \mid p)^2 = 0 , \; }[/math] gdy [math]\displaystyle{ p \mid P }[/math]

lub

[math]\displaystyle{ (D \mid p) = (P^2 \mid p) = (P \mid p)^2 = 1 , \; }[/math] gdy [math]\displaystyle{ p \nmid P }[/math]

i nie może być [math]\displaystyle{ (D \mid p) = - 1 }[/math].

Dla parzystego [math]\displaystyle{ n = p + 1 }[/math] otrzymujemy z twierdzenia N7

[math]\displaystyle{ 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]\displaystyle{ k \in [2, p - 1] }[/math] jest (zobacz N44)

[math]\displaystyle{ \binom{p + 1}{k} \equiv 0 \pmod{p} }[/math]

to modulo [math]\displaystyle{ p }[/math] dostajemy

[math]\displaystyle{ 2 V_{p + 1} \equiv P^2 + D \cdot D^{(p - 1) / 2} \pmod{p} }[/math]

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

[math]\displaystyle{ 2 V_{p + 1} \equiv P^2 - D \equiv 4 Q \pmod{p} }[/math]

Zatem

[math]\displaystyle{ V_{p + 1} \equiv 2 Q \pmod{p} }[/math]

Punkt 3.

Dla parzystego [math]\displaystyle{ n = p - 1 }[/math] otrzymujemy z twierdzenia N7

[math]\displaystyle{ 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]\displaystyle{ k \in [0, p - 1] }[/math] jest (zobacz N45)

[math]\displaystyle{ \binom{p - 1}{k} \equiv (- 1)^k \pmod{p} }[/math]

to modulo [math]\displaystyle{ p }[/math] mamy

[math]\displaystyle{ 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]\displaystyle{ D }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math], zatem istnieje taka liczba [math]\displaystyle{ R }[/math], że

[math]\displaystyle{ D \equiv R^2 \pmod{p} }[/math]

Ponieważ

[math]\displaystyle{ (D \mid p) = 1 }[/math], to [math]\displaystyle{ p \nmid D }[/math], zatem [math]\displaystyle{ p \nmid R }[/math]
z założenia [math]\displaystyle{ p \nmid Q }[/math], to [math]\displaystyle{ P^2 - R^2 \equiv P^2 - D \equiv 4 Q \not\equiv 0 \pmod{p} }[/math]

Czyli

[math]\displaystyle{ 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]\displaystyle{ P^2 - R^2 \not\equiv 0 \pmod{p} }[/math], możemy napisać

[math]\displaystyle{ 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]\displaystyle{ \equiv P^{p + 1} - R^{p + 1} \pmod{p} }[/math]

[math]\displaystyle{ \equiv P^2 - R^2 \pmod{p} }[/math]

Zatem

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

Skąd wynika

[math]\displaystyle{ V_{p - 1} \equiv 2 \pmod{p} }[/math]

Co należało pokazać.
□

Aby zapisać punkty 2. i 3. twierdzenia P3 (i tylko te punkty) w zwartej formie, musimy założyć, że [math]\displaystyle{ \gcd (p, D) = 1 }[/math]. Otrzymujemy
Twierdzenie P4
Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ \gcd (p, Q D) = 1 }[/math], to

[math]\displaystyle{ V_{p - (D \mid p)} \equiv 2 Q^{(1 - (D \mid p)) / 2} \pmod{p} }[/math]

Liczby pseudopierwsze Dicksona drugiego rodzaju

Uwaga P5
Z twierdzenia P4 wiemy, że dla liczb pierwszych nieparzystych takich, że [math]\displaystyle{ p \nmid Q D }[/math] jest

[math]\displaystyle{ V_{p - (D \mid p)} \equiv 2 Q^{(1 - (D \mid p)) / 2} \pmod{p} }[/math]

gdzie [math]\displaystyle{ (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 łatwo przekonamy się, że dla pewnych liczb złożonych [math]\displaystyle{ m }[/math] kongruencja

[math]\displaystyle{ 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^[1]^[2].

Definicja P6
Powiemy, że liczba złożona nieparzysta [math]\displaystyle{ m }[/math] jest liczbą pseudopierwszą Dicksona drugiego rodzaju dla parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math]^[3] (D2PSP([math]\displaystyle{ P, Q }[/math])), jeżeli [math]\displaystyle{ \gcd (m, Q D) = 1 }[/math] i

[math]\displaystyle{ V_{m - (D \mid m)} \equiv 2 Q^{(1 - (D \mid m)) / 2} \pmod{m} }[/math]

gdzie [math]\displaystyle{ (D \mid m) }[/math] oznacza symbol Jacobiego.

Uwaga P7
Wykorzystując funkcje jacobi(a, n) i modLucas(n, P, Q, m) (zobacz J48, N15) możemy napisać prosty program do testowania pierwszości liczb na podstawie twierdzenia P4.

isPrimeOrD2PSP(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) );
}

Przykład P8
Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Dicksona drugiego rodzaju dla różnych parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math].

[math]\displaystyle{ \boldsymbol{P} }[/math] [math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]
[math]\displaystyle{ \boldsymbol{- 5} }[/math]	[math]\displaystyle{ 1121 }[/math]	[math]\displaystyle{ 1541 }[/math]	[math]\displaystyle{ 13333 }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 4081 }[/math]	[math]\displaystyle{ 519 }[/math]	[math]\displaystyle{ 3913 }[/math]	[math]\displaystyle{ 5461 }[/math]	[math]\displaystyle{ 201 }[/math]	[math]\displaystyle{ 1729 }[/math]
[math]\displaystyle{ \boldsymbol{- 4} }[/math]	[math]\displaystyle{ 7345 }[/math]	[math]\displaystyle{ 1891 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 1585 }[/math]	[math]\displaystyle{ 1055 }[/math]	[math]\displaystyle{ 147 }[/math]	[math]\displaystyle{ 129 }[/math]	[math]\displaystyle{ 129 }[/math]	[math]\displaystyle{ 385 }[/math]	[math]\displaystyle{ 91 }[/math]
[math]\displaystyle{ \boldsymbol{- 3} }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]
[math]\displaystyle{ \boldsymbol{- 2} }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 245 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 1957 }[/math]	[math]\displaystyle{ 1339 }[/math]	[math]\displaystyle{ 265 }[/math]	[math]\displaystyle{ 8321 }[/math]	[math]\displaystyle{ 6601 }[/math]	[math]\displaystyle{ 249 }[/math]	[math]\displaystyle{ 1105 }[/math]
[math]\displaystyle{ \boldsymbol{- 1} }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]
[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 25 }[/math]
[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ 1003 }[/math]	[math]\displaystyle{ 561 }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 3781 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 2419 }[/math]	[math]\displaystyle{ 84561 }[/math]	[math]\displaystyle{ 177 }[/math]
[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ 1541 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 24727 }[/math]
[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ 1891 }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 19951 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 451 }[/math]	[math]\displaystyle{ 6601 }[/math]	[math]\displaystyle{ 385 }[/math]	[math]\displaystyle{ 129 }[/math]	[math]\displaystyle{ 4033 }[/math]
[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ 5597 }[/math]	[math]\displaystyle{ 979 }[/math]	[math]\displaystyle{ 15753 }[/math]	[math]\displaystyle{ 979 }[/math]	[math]\displaystyle{ 913 }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 1541 }[/math]	[math]\displaystyle{ 7787 }[/math]	[math]\displaystyle{ 1417 }[/math]	[math]\displaystyle{ 201 }[/math]

Pokaż kod

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( isPrimeOrD2PSP(m, P, Q)  &&  !isprime(m),
                         print("Q= ", Q, "   P= ", P, "   m= ", m, "   (D|m)= ", jacobi(D, m));
                         break();
                       );
                     m = m + 2;
                   );
            );
     );
}

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

Przykład P9
Tabela przedstawia ilość liczb D2PSP([math]\displaystyle{ P, Q }[/math]) mniejszych od [math]\displaystyle{ 10^9 }[/math].

[math]\displaystyle{ \boldsymbol{P} }[/math] [math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]
[math]\displaystyle{ \boldsymbol{- 5} }[/math]	[math]\displaystyle{ 145 }[/math]	[math]\displaystyle{ 143 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 4981 }[/math]	[math]\displaystyle{ 356 }[/math]	[math]\displaystyle{ 129 }[/math]	[math]\displaystyle{ 101 }[/math]	[math]\displaystyle{ 172 }[/math]	[math]\displaystyle{ 152 }[/math]	[math]\displaystyle{ 129 }[/math]
[math]\displaystyle{ \boldsymbol{- 4} }[/math]	[math]\displaystyle{ 192 }[/math]	[math]\displaystyle{ 380 }[/math]	[math]\displaystyle{ 9272 }[/math]	[math]\displaystyle{ 318 }[/math]	[math]\displaystyle{ 249 }[/math]	[math]\displaystyle{ 208 }[/math]	[math]\displaystyle{ 192 }[/math]	[math]\displaystyle{ 555 }[/math]	[math]\displaystyle{ 233 }[/math]	[math]\displaystyle{ 183 }[/math]
[math]\displaystyle{ \boldsymbol{- 3} }[/math]	[math]\displaystyle{ 179 }[/math]	[math]\displaystyle{ 5767 }[/math]	[math]\displaystyle{ 184 }[/math]	[math]\displaystyle{ 184 }[/math]	[math]\displaystyle{ 153 }[/math]	[math]\displaystyle{ 372 }[/math]	[math]\displaystyle{ 145 }[/math]	[math]\displaystyle{ 164 }[/math]	[math]\displaystyle{ 147 }[/math]	[math]\displaystyle{ 192 }[/math]
[math]\displaystyle{ \boldsymbol{- 2} }[/math]	[math]\displaystyle{ 5361 }[/math]	[math]\displaystyle{ 521 }[/math]	[math]\displaystyle{ 128 }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 120 }[/math]	[math]\displaystyle{ 163 }[/math]	[math]\displaystyle{ 132 }[/math]	[math]\displaystyle{ 343 }[/math]	[math]\displaystyle{ 111 }[/math]	[math]\displaystyle{ 467 }[/math]
[math]\displaystyle{ \boldsymbol{- 1} }[/math]	[math]\displaystyle{ 6428 }[/math]	[math]\displaystyle{ 8365 }[/math]	[math]\displaystyle{ 6318 }[/math]	[math]\displaystyle{ 10695 }[/math]	[math]\displaystyle{ 6004 }[/math]	[math]\displaystyle{ 8541 }[/math]	[math]\displaystyle{ 7104 }[/math]	[math]\displaystyle{ 6423 }[/math]	[math]\displaystyle{ 6496 }[/math]	[math]\displaystyle{ 6762 }[/math]
[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ 282485800 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 9811 }[/math]	[math]\displaystyle{ 10627 }[/math]	[math]\displaystyle{ 10081 }[/math]	[math]\displaystyle{ 13073 }[/math]	[math]\displaystyle{ 12756 }[/math]	[math]\displaystyle{ 11841 }[/math]	[math]\displaystyle{ 11373 }[/math]	[math]\displaystyle{ 12365 }[/math]
[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ 221 }[/math]	[math]\displaystyle{ 2939 }[/math]	[math]\displaystyle{ 5597 }[/math]	[math]\displaystyle{ 418 }[/math]	[math]\displaystyle{ 147 }[/math]	[math]\displaystyle{ 157 }[/math]	[math]\displaystyle{ 141 }[/math]	[math]\displaystyle{ 168 }[/math]	[math]\displaystyle{ 116 }[/math]	[math]\displaystyle{ 174 }[/math]
[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ 176 }[/math]	[math]\displaystyle{ 264 }[/math]	[math]\displaystyle{ 3095 }[/math]	[math]\displaystyle{ 5767 }[/math]	[math]\displaystyle{ 158 }[/math]	[math]\displaystyle{ 239 }[/math]	[math]\displaystyle{ 135 }[/math]	[math]\displaystyle{ 179 }[/math]	[math]\displaystyle{ 159 }[/math]	[math]\displaystyle{ 151 }[/math]
[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ 407 }[/math]	[math]\displaystyle{ 5361 }[/math]	[math]\displaystyle{ 473 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 9735 }[/math]	[math]\displaystyle{ 515 }[/math]	[math]\displaystyle{ 330 }[/math]	[math]\displaystyle{ 959 }[/math]	[math]\displaystyle{ 213 }[/math]	[math]\displaystyle{ 247 }[/math]
[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ 108 }[/math]	[math]\displaystyle{ 421 }[/math]	[math]\displaystyle{ 137 }[/math]	[math]\displaystyle{ 421 }[/math]	[math]\displaystyle{ 480 }[/math]	[math]\displaystyle{ 5146 }[/math]	[math]\displaystyle{ 92 }[/math]	[math]\displaystyle{ 124 }[/math]	[math]\displaystyle{ 123 }[/math]	[math]\displaystyle{ 702 }[/math]

Pokaż kod

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( isPrimeOrD2PSP(m, P, Q)  &&  !isprime(m), s++ );
                     m = m + 2;
                   );
              print("Q= ", Q, "   P= ", P, "   s= ", s);
            );
     );
}

Przykład P10
Tabele przedstawiają ilość liczb D2PSP( [math]\displaystyle{ 1, Q }[/math] ) mniejszych od [math]\displaystyle{ 10^9 }[/math] dla [math]\displaystyle{ | Q | \leqslant 20 }[/math].

[math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]	[math]\displaystyle{ \boldsymbol{11} }[/math]	[math]\displaystyle{ \boldsymbol{12} }[/math]	[math]\displaystyle{ \boldsymbol{13} }[/math]	[math]\displaystyle{ \boldsymbol{14} }[/math]	[math]\displaystyle{ \boldsymbol{15} }[/math]	[math]\displaystyle{ \boldsymbol{16} }[/math]	[math]\displaystyle{ \boldsymbol{17} }[/math]	[math]\displaystyle{ \boldsymbol{18} }[/math]	[math]\displaystyle{ \boldsymbol{19} }[/math]	[math]\displaystyle{ \boldsymbol{20} }[/math]
#D2PSP([math]\displaystyle{ 1,Q }[/math]) [math]\displaystyle{ \lt 10^9 }[/math]	[math]\displaystyle{ 282485800 }[/math]	[math]\displaystyle{ 221 }[/math]	[math]\displaystyle{ 176 }[/math]	[math]\displaystyle{ 407 }[/math]	[math]\displaystyle{ 108 }[/math]	[math]\displaystyle{ 113 }[/math]	[math]\displaystyle{ 550 }[/math]	[math]\displaystyle{ 194 }[/math]	[math]\displaystyle{ 165 }[/math]	[math]\displaystyle{ 119 }[/math]	[math]\displaystyle{ 135 }[/math]	[math]\displaystyle{ 171 }[/math]	[math]\displaystyle{ 99 }[/math]	[math]\displaystyle{ 105 }[/math]	[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 767 }[/math]	[math]\displaystyle{ 113 }[/math]	[math]\displaystyle{ 195 }[/math]	[math]\displaystyle{ 578 }[/math]	[math]\displaystyle{ 127 }[/math]

[math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ \boldsymbol{-1} }[/math]	[math]\displaystyle{ \boldsymbol{-2} }[/math]	[math]\displaystyle{ \boldsymbol{-3} }[/math]	[math]\displaystyle{ \boldsymbol{-4} }[/math]	[math]\displaystyle{ \boldsymbol{-5} }[/math]	[math]\displaystyle{ \boldsymbol{-6} }[/math]	[math]\displaystyle{ \boldsymbol{-7} }[/math]	[math]\displaystyle{ \boldsymbol{-8} }[/math]	[math]\displaystyle{ \boldsymbol{-9} }[/math]	[math]\displaystyle{ \boldsymbol{-10} }[/math]	[math]\displaystyle{ \boldsymbol{-11} }[/math]	[math]\displaystyle{ \boldsymbol{-12} }[/math]	[math]\displaystyle{ \boldsymbol{-13} }[/math]	[math]\displaystyle{ \boldsymbol{-14} }[/math]	[math]\displaystyle{ \boldsymbol{-15} }[/math]	[math]\displaystyle{ \boldsymbol{-16} }[/math]	[math]\displaystyle{ \boldsymbol{-17} }[/math]	[math]\displaystyle{ \boldsymbol{-18} }[/math]	[math]\displaystyle{ \boldsymbol{-19} }[/math]	[math]\displaystyle{ \boldsymbol{-20} }[/math]
#D2PSP([math]\displaystyle{ 1,Q }[/math]) [math]\displaystyle{ \lt 10^9 }[/math]	[math]\displaystyle{ 6428 }[/math]	[math]\displaystyle{ 5361 }[/math]	[math]\displaystyle{ 179 }[/math]	[math]\displaystyle{ 192 }[/math]	[math]\displaystyle{ 145 }[/math]	[math]\displaystyle{ 1281 }[/math]	[math]\displaystyle{ 123 }[/math]	[math]\displaystyle{ 196 }[/math]	[math]\displaystyle{ 198 }[/math]	[math]\displaystyle{ 162 }[/math]	[math]\displaystyle{ 246 }[/math]	[math]\displaystyle{ 1748 }[/math]	[math]\displaystyle{ 106 }[/math]	[math]\displaystyle{ 103 }[/math]	[math]\displaystyle{ 110 }[/math]	[math]\displaystyle{ 205 }[/math]	[math]\displaystyle{ 113 }[/math]	[math]\displaystyle{ 157 }[/math]	[math]\displaystyle{ 157 }[/math]	[math]\displaystyle{ 1536 }[/math]

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

Zmodyfikowana metoda Selfridge'a wyboru parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math]

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

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

Dlatego konieczne było napisanie nowej funkcji MethodA(m). Działa ona teraz w 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]\displaystyle{ (P, Q) = (1, - 1) }[/math] na [math]\displaystyle{ (P, Q) = (5, 5) }[/math]). Jeżeli wpiszemy drugi parametr, to będzie on interpretowany, jako wyraz ciągu [math]\displaystyle{ a_k = (- 1)^k (2 k + 1) }[/math], od którego należy rozpocząć przeszukiwanie. Parametr musi być elementem ciągu [math]\displaystyle{ (a_k) }[/math] dla [math]\displaystyle{ k \geqslant 2 }[/math]. Przykładowo MethodA(m, 5), to stara (niepoprawiona) wersja funkcji, MethodA(m, -7) rozpocznie poszukiwanie liczby [math]\displaystyle{ a_k }[/math] takiej, że [math]\displaystyle{ (a_k \mid m) = - 1 }[/math] od [math]\displaystyle{ a_k = - 7 }[/math].

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

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

Zadanie P12
Pokazać, że dla dowolnej niekwadratowej liczby nieparzystej [math]\displaystyle{ m }[/math] jest: MethodA(m, 9) = MethodA(m, -11).

Rozwiązanie

Mówiąc o liniach kodu, mamy na myśli linie w pętli while. Linia nr 1 w pętli while, to linia a = -a - 2*sign(a);.

Możemy znacznie ułatwić sobie analizę problemu, sprawdzając, że równość MethodA(m, 9) = MethodA(m, -11) jest prawdziwa dla niekwadratowych liczb nieparzystych mniejszych od [math]\displaystyle{ 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]\displaystyle{ m }[/math] postaci [math]\displaystyle{ 6 k + 1 }[/math], [math]\displaystyle{ 6 k + 3 }[/math], [math]\displaystyle{ 6 k + 5 }[/math], gdzie [math]\displaystyle{ k \geqslant 10 }[/math]. Rozważmy działanie funkcji MethodA(m, 9).

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

Jeżeli [math]\displaystyle{ m = 6 k + 3 }[/math], to [math]\displaystyle{ (9 \mid m) = 0 }[/math] i wykonywana jest linia nr 4, w wyniku czego funkcja MethodA(m, 9) zwraca wektor [0, 0].

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

Jeżeli [math]\displaystyle{ (- 11 \mid 6 k + 3) = 0 }[/math], to wykonywana jest linia nr 4, w wyniku czego zwracany jest wektor [0, 0].

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

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

Jeżeli [math]\displaystyle{ (13 \mid 6 k + 3) = 0 }[/math], to wykonywana jest linia nr 4, w wyniku czego zwracany jest wektor [0, 0].

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

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

Ponieważ [math]\displaystyle{ (- 15 \mid 6 k + 3) = 0 }[/math], to wykonywana jest linia nr 4, w wyniku czego zwracany jest wektor [0, 0].

Pokazaliśmy, że funkcje MethodA(m, 9) i MethodA(m, -11) zwracają takie same wartości dla wszystkich niekwadratowych liczb nieparzystych [math]\displaystyle{ m }[/math].
□

Uwaga P13
Podobnie, jak w przypadku liczb pseudopierwszych Lucasa LPSP([math]\displaystyle{ P, Q }[/math]) i w przypadku liczb silnie pseudopierwszych Lucasa SLPSP([math]\displaystyle{ P, Q }[/math]), tak i w przypadku liczb pseudopierwszych Dicksona drugiego rodzaju D2PSP([math]\displaystyle{ P, Q }[/math]) możemy testować pierwszość liczby [math]\displaystyle{ m }[/math], wybierając liczby [math]\displaystyle{ P, Q }[/math] losowo lub zastosować wybraną metodę postępowania. Przyjmując zmodyfikowaną postać funkcji MethodA(), możemy łatwo napisać program:

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

Przykład P14
Poniżej przedstawiamy najmniejsze liczby D2PSP([math]\displaystyle{ P, Q }[/math]) oraz ilości tych liczb w zależności od wartości parametru start w funkcji MethodA(m, start). Ponieważ MethodA(m, 9) = MethodA(m, -11) (zobacz P12), to pominęliśmy przypadek MethodA(m, -11). Dla porównania w następnym przykładzie przedstawimy analogiczne zestawienia dla liczb SLPSP([math]\displaystyle{ P, Q }[/math]).

Ilość liczb pseudopierwszych Dicksona drugiego rodzaju mniejszych od [math]\displaystyle{ 10^n }[/math] dla różnych parametrów start funkcji MethodA().

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 14 }[/math]	[math]\displaystyle{ 15 }[/math]
MethodA(m, "*")^[5]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 5 }[/math]
MethodA(m, 5)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 18 }[/math]	[math]\displaystyle{ 55 }[/math]	[math]\displaystyle{ 145 }[/math]	[math]\displaystyle{ 383 }[/math]	[math]\displaystyle{ 914 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -7)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 9)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 13)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -15)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 17)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -19)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 21)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -23)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 25)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -27)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 29)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -31)	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 33)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]

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

MethodA(m, "*")^[5]	[math]\displaystyle{ 913, 150267335403, 430558874533, 14760229232131, 936916995253453 }[/math]
MethodA(m, 5)	[math]\displaystyle{ 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]
MethodA(m, -7)	[math]\displaystyle{ 509140495, \dots, 14760229232131 }[/math]
MethodA(m, 9)	[math]\displaystyle{ 8788015 }[/math]
MethodA(m, 13)	[math]\displaystyle{ 2263, 8788015, 59839087 }[/math]
MethodA(m, -15)	[math]\displaystyle{ 2263, 3086759, 59839087, 166044803 }[/math]
MethodA(m, 17)	[math]\displaystyle{ 58982383, 166044803, 209562267, 2676099095 }[/math]
MethodA(m, -19)	[math]\displaystyle{ 58982383, ..., 101378999149 }[/math]
MethodA(m, 21)	[math]\displaystyle{ 1121, ..., 101378999149 }[/math]
MethodA(m, -23)	[math]\displaystyle{ 155, 20709031, ..., 101378999149 }[/math]
MethodA(m, 25)	[math]\displaystyle{ ..., 101378999149 }[/math]
MethodA(m, -27)	[math]\displaystyle{ ..., 101378999149 }[/math]
MethodA(m, 29)	[math]\displaystyle{ 2004987, 1084387931, ..., 101378999149 }[/math]
MethodA(m, -31)	[math]\displaystyle{ 27, 4611, 4105612299, ..., 101378999149 }[/math]
MethodA(m, 33)	[math]\displaystyle{ 94669, 2026655153, ..., 101378999149 }[/math]

Liczby w pierwszym wierszu są tak duże, że możemy co najwyżej zweryfikować, czy są D2PSP([math]\displaystyle{ P, Q }[/math])

X = [913, 150267335403, 430558874533, 14760229232131, 936916995253453]
for(k = 1, length(X), print( Dickson2Test(X[k]) ))

Równie łatwo sprawdzamy, że

Dickson2Test(14760229232131, 5) == 1
Dickson2Test(14760229232131, -7) == 1

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

Jest tak wtedy, gdy dla [math]\displaystyle{ r }[/math] kolejnych liczb [math]\displaystyle{ a_k }[/math], gdzie [math]\displaystyle{ a_k = (- 1)^k (2 k + 1) }[/math] mamy

[math]\displaystyle{ (a_k \mid m) = (a_{k + 1} \mid m) = \ldots = (a_{k + r - 1} \mid m) = 1 }[/math]

oraz

[math]\displaystyle{ (a_{k + r} \mid m) = - 1 }[/math]

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

Ponieważ w pętli while funkcji MethodA() mamy następujące linie

a = -a - 2*sign(a); \\ następny wyraz ciągu (a_k)
js = jacobi(a, m);
if( js == 1, next() );

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

Silnie pseudopierwsze liczby Lucasa i zmodyfikowana metoda Selfridge'a

Przykład P15
Poniżej przedstawiamy najmniejsze liczby SLPSP([math]\displaystyle{ P, Q }[/math]) oraz ilości tych liczb w zależności od wartości parametru start w funkcji MethodA(m, start). Ponieważ MethodA(m, 9) = MethodA(m, -11) (zobacz P12), to pominęliśmy przypadek MethodA(m, -11).

Ilość silnie pseudopierwszych liczb Lucasa mniejszych od [math]\displaystyle{ 10^n }[/math] dla różnych parametrów start funkcji MethodA().

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 14 }[/math]	[math]\displaystyle{ 15 }[/math]
MethodA(m, "*")^[6]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 58 }[/math]	[math]\displaystyle{ 178 }[/math]	[math]\displaystyle{ 505 }[/math]	[math]\displaystyle{ 1415 }[/math]	[math]\displaystyle{ 3622 }[/math]	[math]\displaystyle{ 9714 }[/math]	[math]\displaystyle{ 25542 }[/math]	[math]\displaystyle{ 67045 }[/math]	[math]\displaystyle{ 178118 }[/math]	[math]\displaystyle{ 474971 }[/math]
MethodA(m, 5)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 58 }[/math]	[math]\displaystyle{ 178 }[/math]	[math]\displaystyle{ 505 }[/math]	[math]\displaystyle{ 1415 }[/math]	[math]\displaystyle{ 3622 }[/math]	[math]\displaystyle{ 9714 }[/math]	[math]\displaystyle{ 25542 }[/math]	[math]\displaystyle{ 67045 }[/math]	[math]\displaystyle{ 178118 }[/math]	[math]\displaystyle{ 474971 }[/math]
MethodA(m, -7)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 14 }[/math]	[math]\displaystyle{ 62 }[/math]	[math]\displaystyle{ 210 }[/math]	[math]\displaystyle{ 601 }[/math]	[math]\displaystyle{ 1625 }[/math]	[math]\displaystyle{ 4261 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 9)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 20 }[/math]	[math]\displaystyle{ 73 }[/math]	[math]\displaystyle{ 219 }[/math]	[math]\displaystyle{ 604 }[/math]	[math]\displaystyle{ 1575 }[/math]	[math]\displaystyle{ 4162 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 13)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 23 }[/math]	[math]\displaystyle{ 67 }[/math]	[math]\displaystyle{ 200 }[/math]	[math]\displaystyle{ 545 }[/math]	[math]\displaystyle{ 1443 }[/math]	[math]\displaystyle{ 3891 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -15)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 28 }[/math]	[math]\displaystyle{ 84 }[/math]	[math]\displaystyle{ 236 }[/math]	[math]\displaystyle{ 696 }[/math]	[math]\displaystyle{ 1953 }[/math]	[math]\displaystyle{ 5226 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 17)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 46 }[/math]	[math]\displaystyle{ 147 }[/math]	[math]\displaystyle{ 396 }[/math]	[math]\displaystyle{ 1091 }[/math]	[math]\displaystyle{ 2931 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -19)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 66 }[/math]	[math]\displaystyle{ 202 }[/math]	[math]\displaystyle{ 557 }[/math]	[math]\displaystyle{ 1493 }[/math]	[math]\displaystyle{ 3978 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 21)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 24 }[/math]	[math]\displaystyle{ 79 }[/math]	[math]\displaystyle{ 242 }[/math]	[math]\displaystyle{ 643 }[/math]	[math]\displaystyle{ 1723 }[/math]	[math]\displaystyle{ 4498 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -23)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ 24 }[/math]	[math]\displaystyle{ 88 }[/math]	[math]\displaystyle{ 236 }[/math]	[math]\displaystyle{ 639 }[/math]	[math]\displaystyle{ 1722 }[/math]	[math]\displaystyle{ 4597 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 25)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 37 }[/math]	[math]\displaystyle{ 105 }[/math]	[math]\displaystyle{ 295 }[/math]	[math]\displaystyle{ 812 }[/math]	[math]\displaystyle{ 2188 }[/math]	[math]\displaystyle{ 5879 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -27)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 38 }[/math]	[math]\displaystyle{ 108 }[/math]	[math]\displaystyle{ 299 }[/math]	[math]\displaystyle{ 827 }[/math]	[math]\displaystyle{ 2224 }[/math]	[math]\displaystyle{ 5972 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 29)	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 27 }[/math]	[math]\displaystyle{ 69 }[/math]	[math]\displaystyle{ 160 }[/math]	[math]\displaystyle{ 500 }[/math]	[math]\displaystyle{ 1364 }[/math]	[math]\displaystyle{ 3583 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, -31)	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 19 }[/math]	[math]\displaystyle{ 72 }[/math]	[math]\displaystyle{ 194 }[/math]	[math]\displaystyle{ 573 }[/math]	[math]\displaystyle{ 1551 }[/math]	[math]\displaystyle{ 3928 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]
MethodA(m, 33)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 19 }[/math]	[math]\displaystyle{ 73 }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 537 }[/math]	[math]\displaystyle{ 1460 }[/math]	[math]\displaystyle{ 3705 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ }[/math]

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

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

Uwaga P16
Przyglądając się wierszom drugiej tabeli z przykładu P15, łatwo zauważamy, że w 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 SLPSP(m, a), gdzie

[math]\displaystyle{ a \in \{ }[/math]"*"[math]\displaystyle{ , -7, 9, 13, -15, 17, -19, 21, -23, 25, -27, 29, -31, 33 \} }[/math]

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

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

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

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

[math]\displaystyle{ \boldsymbol{a} }[/math]	`"*"`	[math]\displaystyle{ \boldsymbol{-7} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{13} }[/math]	[math]\displaystyle{ \boldsymbol{-15} }[/math]	[math]\displaystyle{ \boldsymbol{17} }[/math]	[math]\displaystyle{ \boldsymbol{-19} }[/math]	[math]\displaystyle{ \boldsymbol{21} }[/math]	[math]\displaystyle{ \boldsymbol{-23} }[/math]	[math]\displaystyle{ \boldsymbol{25} }[/math]	[math]\displaystyle{ \boldsymbol{-27} }[/math]	[math]\displaystyle{ \boldsymbol{29} }[/math]	[math]\displaystyle{ \boldsymbol{-31} }[/math]	[math]\displaystyle{ \boldsymbol{33} }[/math]
`"*"`	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 2904 }[/math]	[math]\displaystyle{ 1203 }[/math]	[math]\displaystyle{ 711 }[/math]	[math]\displaystyle{ 655 }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 223 }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 236 }[/math]	[math]\displaystyle{ 236 }[/math]	[math]\displaystyle{ 180 }[/math]	[math]\displaystyle{ 179 }[/math]	[math]\displaystyle{ 173 }[/math]
[math]\displaystyle{ \boldsymbol{-7} }[/math]	[math]\displaystyle{ 2904 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 1760 }[/math]	[math]\displaystyle{ 855 }[/math]	[math]\displaystyle{ 743 }[/math]	[math]\displaystyle{ 256 }[/math]	[math]\displaystyle{ 288 }[/math]	[math]\displaystyle{ 290 }[/math]	[math]\displaystyle{ 216 }[/math]	[math]\displaystyle{ 260 }[/math]	[math]\displaystyle{ 261 }[/math]	[math]\displaystyle{ 213 }[/math]	[math]\displaystyle{ 221 }[/math]	[math]\displaystyle{ 198 }[/math]
[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ 1203 }[/math]	[math]\displaystyle{ 1760 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 1897 }[/math]	[math]\displaystyle{ 1483 }[/math]	[math]\displaystyle{ 448 }[/math]	[math]\displaystyle{ 421 }[/math]	[math]\displaystyle{ 417 }[/math]	[math]\displaystyle{ 343 }[/math]	[math]\displaystyle{ 436 }[/math]	[math]\displaystyle{ 436 }[/math]	[math]\displaystyle{ 196 }[/math]	[math]\displaystyle{ 181 }[/math]	[math]\displaystyle{ 228 }[/math]
[math]\displaystyle{ \boldsymbol{13} }[/math]	[math]\displaystyle{ 711 }[/math]	[math]\displaystyle{ 855 }[/math]	[math]\displaystyle{ 1897 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 2833 }[/math]	[math]\displaystyle{ 777 }[/math]	[math]\displaystyle{ 609 }[/math]	[math]\displaystyle{ 436 }[/math]	[math]\displaystyle{ 370 }[/math]	[math]\displaystyle{ 351 }[/math]	[math]\displaystyle{ 351 }[/math]	[math]\displaystyle{ 196 }[/math]	[math]\displaystyle{ 170 }[/math]	[math]\displaystyle{ 188 }[/math]
[math]\displaystyle{ \boldsymbol{-15} }[/math]	[math]\displaystyle{ 655 }[/math]	[math]\displaystyle{ 743 }[/math]	[math]\displaystyle{ 1483 }[/math]	[math]\displaystyle{ 2833 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 1313 }[/math]	[math]\displaystyle{ 1064 }[/math]	[math]\displaystyle{ 727 }[/math]	[math]\displaystyle{ 613 }[/math]	[math]\displaystyle{ 578 }[/math]	[math]\displaystyle{ 578 }[/math]	[math]\displaystyle{ 303 }[/math]	[math]\displaystyle{ 260 }[/math]	[math]\displaystyle{ 291 }[/math]
[math]\displaystyle{ \boldsymbol{17} }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 256 }[/math]	[math]\displaystyle{ 448 }[/math]	[math]\displaystyle{ 777 }[/math]	[math]\displaystyle{ 1313 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 2037 }[/math]	[math]\displaystyle{ 1146 }[/math]	[math]\displaystyle{ 862 }[/math]	[math]\displaystyle{ 654 }[/math]	[math]\displaystyle{ 654 }[/math]	[math]\displaystyle{ 171 }[/math]	[math]\displaystyle{ 129 }[/math]	[math]\displaystyle{ 137 }[/math]
[math]\displaystyle{ \boldsymbol{-19} }[/math]	[math]\displaystyle{ 223 }[/math]	[math]\displaystyle{ 288 }[/math]	[math]\displaystyle{ 421 }[/math]	[math]\displaystyle{ 609 }[/math]	[math]\displaystyle{ 1064 }[/math]	[math]\displaystyle{ 2037 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 2231 }[/math]	[math]\displaystyle{ 1668 }[/math]	[math]\displaystyle{ 1236 }[/math]	[math]\displaystyle{ 1236 }[/math]	[math]\displaystyle{ 241 }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 190 }[/math]
[math]\displaystyle{ \boldsymbol{21} }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 290 }[/math]	[math]\displaystyle{ 417 }[/math]	[math]\displaystyle{ 436 }[/math]	[math]\displaystyle{ 727 }[/math]	[math]\displaystyle{ 1146 }[/math]	[math]\displaystyle{ 2231 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 3251 }[/math]	[math]\displaystyle{ 2342 }[/math]	[math]\displaystyle{ 2342 }[/math]	[math]\displaystyle{ 336 }[/math]	[math]\displaystyle{ 278 }[/math]	[math]\displaystyle{ 270 }[/math]
[math]\displaystyle{ \boldsymbol{-23} }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 216 }[/math]	[math]\displaystyle{ 343 }[/math]	[math]\displaystyle{ 370 }[/math]	[math]\displaystyle{ 613 }[/math]	[math]\displaystyle{ 862 }[/math]	[math]\displaystyle{ 1668 }[/math]	[math]\displaystyle{ 3251 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 2937 }[/math]	[math]\displaystyle{ 2937 }[/math]	[math]\displaystyle{ 475 }[/math]	[math]\displaystyle{ 360 }[/math]	[math]\displaystyle{ 275 }[/math]
[math]\displaystyle{ \boldsymbol{25} }[/math]	[math]\displaystyle{ 236 }[/math]	[math]\displaystyle{ 260 }[/math]	[math]\displaystyle{ 436 }[/math]	[math]\displaystyle{ 351 }[/math]	[math]\displaystyle{ 578 }[/math]	[math]\displaystyle{ 654 }[/math]	[math]\displaystyle{ 1236 }[/math]	[math]\displaystyle{ 2342 }[/math]	[math]\displaystyle{ 2937 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 5879 }[/math]	[math]\displaystyle{ 855 }[/math]	[math]\displaystyle{ 657 }[/math]	[math]\displaystyle{ 480 }[/math]
[math]\displaystyle{ \boldsymbol{-27} }[/math]	[math]\displaystyle{ 236 }[/math]	[math]\displaystyle{ 261 }[/math]	[math]\displaystyle{ 436 }[/math]	[math]\displaystyle{ 351 }[/math]	[math]\displaystyle{ 578 }[/math]	[math]\displaystyle{ 654 }[/math]	[math]\displaystyle{ 1236 }[/math]	[math]\displaystyle{ 2342 }[/math]	[math]\displaystyle{ 2937 }[/math]	[math]\displaystyle{ 5879 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 857 }[/math]	[math]\displaystyle{ 659 }[/math]	[math]\displaystyle{ 480 }[/math]
[math]\displaystyle{ \boldsymbol{29} }[/math]	[math]\displaystyle{ 180 }[/math]	[math]\displaystyle{ 213 }[/math]	[math]\displaystyle{ 196 }[/math]	[math]\displaystyle{ 196 }[/math]	[math]\displaystyle{ 303 }[/math]	[math]\displaystyle{ 171 }[/math]	[math]\displaystyle{ 241 }[/math]	[math]\displaystyle{ 336 }[/math]	[math]\displaystyle{ 475 }[/math]	[math]\displaystyle{ 855 }[/math]	[math]\displaystyle{ 857 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 2079 }[/math]	[math]\displaystyle{ 1003 }[/math]
[math]\displaystyle{ \boldsymbol{-31} }[/math]	[math]\displaystyle{ 179 }[/math]	[math]\displaystyle{ 221 }[/math]	[math]\displaystyle{ 181 }[/math]	[math]\displaystyle{ 170 }[/math]	[math]\displaystyle{ 260 }[/math]	[math]\displaystyle{ 129 }[/math]	[math]\displaystyle{ 199 }[/math]	[math]\displaystyle{ 278 }[/math]	[math]\displaystyle{ 360 }[/math]	[math]\displaystyle{ 657 }[/math]	[math]\displaystyle{ 659 }[/math]	[math]\displaystyle{ 2079 }[/math]	[math]\displaystyle{ — }[/math]	[math]\displaystyle{ 1857 }[/math]
[math]\displaystyle{ \boldsymbol{33} }[/math]	[math]\displaystyle{ 173 }[/math]	[math]\displaystyle{ 198 }[/math]	[math]\displaystyle{ 228 }[/math]	[math]\displaystyle{ 188 }[/math]	[math]\displaystyle{ 291 }[/math]	[math]\displaystyle{ 137 }[/math]	[math]\displaystyle{ 190 }[/math]	[math]\displaystyle{ 270 }[/math]	[math]\displaystyle{ 275 }[/math]	[math]\displaystyle{ 480 }[/math]	[math]\displaystyle{ 480 }[/math]	[math]\displaystyle{ 1003 }[/math]	[math]\displaystyle{ 1857 }[/math]	[math]\displaystyle{ — }[/math]

Wzmocnienie testu BPSW

Uwaga P17
Dla wszystkich rozpatrywanych tutaj parametrów start takich, że

start [math]\displaystyle{ \in \{ }[/math]"*"[math]\displaystyle{ , -7, 9, 13, -15, 17, -19, 21, -23, 25, -27, 29, -31, 33 \} }[/math]

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

Przypomnijmy, że nie znamy liczb nieparzystych [math]\displaystyle{ m }[/math], które byłyby jednocześnie liczbami silnie pseudopierwszymi (SPSP) i silnie pseudopierwszymi liczbami Lucasa (SLPSP) dla [math]\displaystyle{ m \lt 2^{64} }[/math]. Jest bardzo prawdopodobne, że równie rzadko występują liczby, które są jednocześnie silnie pseudopierwszymi liczbami Lucasa (SLPSP) i 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.

BPSW2test(m) =
{
local(p);
forprime(p = 2, 1000, if( m % p > 0, next() ); if( m == p, return(1), return(0) ));
if( !isPrimeOrSPSP(m, 2), return(0) );
if( !StrongLucasTest(m), return(0) );
if( !Dickson2Test(m), return(0), return(1) );
}

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

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

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

BPSW2test(m) =
{
local(p);
forprime(p = 2, 1000, if( m % p > 0, next() ); if( m == p, return(1), return(0) ));
if( !isPrimeOrSPSP(m, 2), return(0) );
if( !StrongLucasAndDickson2Test(m), return(0), return(1) );
}

Uzupełnienie

Dowody twierdzeń P18 i P19 zostały oparte na pomyśle przedstawionym przez Bailliego, Fioriego i Wagstaffa^[5].
Twierdzenie P18
Liczba nieparzysta [math]\displaystyle{ m }[/math] jest LPSP([math]\displaystyle{ 1, - 1 }[/math]) wtedy i tylko wtedy, gdy [math]\displaystyle{ m }[/math] jest LPSP([math]\displaystyle{ 5, 5 }[/math]).

Dowód

W zadaniu N12 połóżmy [math]\displaystyle{ Q = 1 }[/math] i konsekwentnie [math]\displaystyle{ P = 4 Q + 1 = 5 }[/math]. Pierwszy z wypisanych wzorów przyjmie postać

[math]\displaystyle{ U_{2 k} (5, 5) = 5^k U_{2 k} (1, - 1) }[/math]

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

[math]\displaystyle{ U_{m - \epsilon} (5, 5) = 5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1) }[/math]

Zauważmy, że

dla [math]\displaystyle{ (P, Q) = (1, - 1) \;\; \text{i} \;\; (P, Q) = (5, 5) }[/math] jest [math]\displaystyle{ D = P^2 - 4 Q = 5 }[/math]
[math]\displaystyle{ \gcd (m, - 5) = 1 }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ \gcd (m, 25) = 1 }[/math]
[math]\displaystyle{ U_{m - \epsilon} (5, 5) \equiv 5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1) \pmod{m} }[/math]

[math]\displaystyle{ \Large{\Longrightarrow} }[/math]

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

[math]\displaystyle{ \Large{\Longleftarrow} }[/math]

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

[math]\displaystyle{ 5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1) \equiv 0 \pmod{m} }[/math]

Ponieważ [math]\displaystyle{ \gcd (m, 5) = 1 }[/math], to z powyższej kongruencji wynika natychmiast, że (zobacz C74)

[math]\displaystyle{ U_{m - \epsilon} (1, - 1) \equiv 0 \pmod{m} }[/math]

Czyli [math]\displaystyle{ m }[/math] jest LPSP([math]\displaystyle{ 1, - 1 }[/math]). Co należało pokazać.
□

Twierdzenie P19
Liczba nieparzysta [math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ 1, - 1 }[/math]) wtedy i tylko wtedy, gdy [math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ 5, 5 }[/math]).

Dowód

W zadaniu N12 połóżmy [math]\displaystyle{ Q = 1 }[/math] i konsekwentnie [math]\displaystyle{ P = 4 Q + 1 = 5 }[/math]. Drugi, czwarty i trzeci z wypisanych wzorów przyjmą postać

[math]\displaystyle{ U_{2 k + 1} (5, 5) = 5^k V_{2 k + 1} (1, - 1) }[/math]

[math]\displaystyle{ V_{2 k + 1} (5, 5) = 5^{k + 1} U_{2 k + 1} (1, - 1) }[/math]

[math]\displaystyle{ V_{2 k} (5, 5) = 5^k V_{2 k} (1, - 1) }[/math]

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

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

Liczba [math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ 1, - 1 }[/math]) jeżeli [math]\displaystyle{ \gcd (m, - 5) = 1 }[/math] i zachodzi dokładnie jeden z warunków

A) [math]\displaystyle{ \; U_w (1, - 1) \equiv 0 \pmod{m} }[/math]

B) [math]\displaystyle{ \; V_w (1, - 1) \equiv 0 \pmod{m} }[/math]

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

Podobnie, liczba [math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ 5, 5 }[/math]) jeżeli [math]\displaystyle{ \gcd (m, 25) = 1 }[/math] i zachodzi dokładnie jeden z warunków

a) [math]\displaystyle{ \; U_w (5, 5) \equiv 0 \pmod{m} }[/math]

b) [math]\displaystyle{ \; V_w (5, 5) \equiv 0 \pmod{m} }[/math]

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

[math]\displaystyle{ \Large{\Longrightarrow} }[/math]

Jeżeli [math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ 1, - 1 }[/math]), to [math]\displaystyle{ \gcd (m, - 5) = 1 }[/math] i zachodzi dokładnie jeden z warunków A), B), C). Zatem [math]\displaystyle{ \gcd (m, 25) = 1 }[/math] i zachodzi dokładnie jeden z warunków a), b), c). Czyli [math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ 5, 5 }[/math]).

[math]\displaystyle{ \Large{\Longleftarrow} }[/math]

Jeżeli [math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ 5, 5 }[/math]), to [math]\displaystyle{ \gcd (m, 25) = 1 }[/math] i zachodzi dokładnie jeden z warunków a), b), c). Zatem [math]\displaystyle{ \gcd (m, - 5) = 1 }[/math] i zachodzi dokładnie jedna z kongruencji

[math]\displaystyle{ 5^{(w - 1) / 2} V_w (1, - 1) \equiv 0 \pmod{m} }[/math]

[math]\displaystyle{ 5^{(w + 1) / 2} U_w (1, - 1) \equiv 0 \pmod{m} }[/math]

[math]\displaystyle{ 5^{2^{j - 1} w} V_{2^j w} (1, - 1) \equiv 0 \pmod{m} }[/math]

Ponieważ [math]\displaystyle{ \gcd (m, 5) = 1 }[/math], to z powyższych wzorów wynika natychmiast, że zachodzi dokładnie jedna z kongruencji (zobacz C74)

[math]\displaystyle{ V_w (1, - 1) \equiv 0 \pmod{m} }[/math]

[math]\displaystyle{ U_w (1, - 1) \equiv 0 \pmod{m} }[/math]

[math]\displaystyle{ V_{2^j w} (1, - 1) \equiv 0 \pmod{m} }[/math]

Co oznacza, że zachodzi dokładnie jeden z warunków A), B), C). Czyli [math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ 1, - 1 }[/math]). Co należało pokazać.
□

Zestawienie funkcji

Uwaga P20
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ę MethodA() tak, aby możliwe było pełne wykorzystanie tej funkcji po zmodyfikowaniu i związane z tym poprawki.

\\ 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 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);
}

\\ test Millera-Rabina
isPrimeOrSPSP(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);
}

\\ 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 ≡ 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 ≡ 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 ≡ n ≡ 3 (mod 4)
       a = a % n;
     );
if( n == 1, return(w), return(0) ); \\ n jest teraz równe gcd(a, n)
}

\\ 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]);
}

\\ 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
     );
}

\\ 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) );
}

\\ 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);
}

\\ test BPSW
BPSWtest(m, start = "*") =
{
forprime(p = 2, 1000, if( m % p > 0, next() ); if( m == p, return(1), return(0) ));
if( !isPrimeOrSPSP(m, 2), return(0) );
if( !StrongLucasTest(m, start), return(0), return(1) );
}

\\ 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) );
}

\\ 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) );
}

\\ test BPSW2
BPSW2test(m, start = "*") =
{
forprime(p = 2, 1000, if( m % p > 0, next() ); if( m == p, return(1), return(0) ));
if( !isPrimeOrSPSP(m, 2), return(0) );
if( !StrongLucasAndDickson2Test(m, start), return(0), return(1) );
}

Przypisy

↑ Zobacz prace: Andrzej Rotkiewicz, Lucas pseudoprimes, (2000) oraz Lucas and Frobenius pseudoprimes, (2003) i Lawrence Somer, Lucas sequences [math]\displaystyle{ \{U_k\} }[/math] for which [math]\displaystyle{ U_{2 p} }[/math] and [math]\displaystyle{ U_{p} }[/math] are pseudoprimes for almost all primes [math]\displaystyle{ p }[/math], (2006)
↑ Baillie, Fiori i Wagstaff w pracy Strengthening the Baillie-PSW primality test nazywają te liczby liczbami pseudopierwszymi Lucasa-V (w skrócie: vpsp([math]\displaystyle{ P, Q }[/math])) (ang. Lucas-V pseudoprime).
↑ ang. Dickson pseudoprime of the second kind with parameters [math]\displaystyle{ P }[/math] and [math]\displaystyle{ Q }[/math]
↑ Robert Baillie and Samuel S. Wagstaff Jr., Lucas Pseudoprimes, Mathematics of Computation Vol. 35, No. 152 (1980), (LINK)
↑ ^5,0 ^5,1 ^5,2 Robert Baillie, Andrew Fiori and Samuel S. Wagstaff, Jr., Strengthening the Baillie-PSW primality test, Mathematics of Computation, 90 (2021)
↑ Dana Jacobsen, Pseudoprime Statistics, Tables, and Data, (LINK)

[D2PSP1-1] Zobacz prace: Andrzej Rotkiewicz, Lucas pseudoprimes, (2000) oraz Lucas and Frobenius pseudoprimes, (2003) i Lawrence Somer, Lucas sequences [math]\displaystyle{ \{U_k\} }[/math] for which [math]\displaystyle{ U_{2 p} }[/math] and [math]\displaystyle{ U_{p} }[/math] are pseudoprimes for almost all primes [math]\displaystyle{ p }[/math], (2006)

[D2PSP2-2] Baillie, Fiori i Wagstaff w pracy Strengthening the Baillie-PSW primality test nazywają te liczby liczbami pseudopierwszymi Lucasa-V (w skrócie: vpsp([math]\displaystyle{ P, Q }[/math])) (ang. Lucas-V pseudoprime).

[D2PSP3-3] . Dickson pseudoprime of the second kind with parameters [math]\displaystyle{ P }[/math] and [math]\displaystyle{ Q }[/math]

[BaillieWagstaff1-4] Robert Baillie and Samuel S. Wagstaff Jr., Lucas Pseudoprimes, Mathematics of Computation Vol. 35, No. 152 (1980), (LINK)

[BaillieFioriWagstaff1-5] 5,0 ^5,1 ^5,2 Robert Baillie, Andrew Fiori and Samuel S. Wagstaff, Jr., Strengthening the Baillie-PSW primality test, Mathematics of Computation, 90 (2021)

[Jacobsen1-6] Dana Jacobsen, Pseudoprime Statistics, Tables, and Data, (LINK)

[1]

[2]

[3]

[4]

[5]

[6]

Różnica pomiędzy stronami "Testy pierwszości. Liczby pseudopierwsze Fermata i liczby silnie pseudopierwsze" i "Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju"

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

Spis treści

Podzielność wyrazów [math]\displaystyle{ V_n (P, Q) }[/math] przez liczbę pierwszą nieparzystą

Liczby pseudopierwsze Dicksona drugiego rodzaju

Zmodyfikowana metoda Selfridge'a wyboru parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math]

Silnie pseudopierwsze liczby Lucasa i zmodyfikowana metoda Selfridge'a

Wzmocnienie testu BPSW

Uzupełnienie

Zestawienie funkcji

Przypisy

Menu nawigacyjne

Szukaj

@@ Linia 1: / Linia 1: @@
-<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">11.11.2022</div>
+<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">12.07.2023</div>
 __FORCETOC__
@@ Linia 5: / Linia 5: @@
-== Potęgowanie modulo ==
+== Podzielność wyrazów <math>V_n (P, Q)</math> przez liczbę pierwszą nieparzystą ==
-<span style="font-size: 110%; font-weight: bold;">Uwaga M1</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie P1</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
+Niech <math>p</math> będzie liczbą pierwszą nieparzystą.
-::<math>2^{340} - 1 = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115775</math>
+::{| 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.'''
-::::<math>\;\;\; = 341 \cdot 6568166399348399444449977362370804334667582103327417990909058947107894050381703652143335757394742275</math>
+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>.
-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>.
+'''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>
-<span style="font-size: 110%; font-weight: bold;">Uwaga M2</span><br/>
+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>.
-Wykorzystując wzór rekurencyjny
-::<math>a^n = \left\{ \begin{array}{cll}
+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>
-  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>
+::<math>V_{2 n + 2} = P V_{2 n + 1} - Q V_{2 n}</math>
-możemy napisać w&nbsp;PARI/GP prosty program do potęgowania modulo:
+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>.
- <span style="font-size: 90%; color:black;">modPower(a, n, m) =
+'''Punkt 3.'''
- \\ a - podstawa, n - wykładnik, m - moduł
- {
+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>
- '''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>
+::<math>V_{n + 1} = P V_n - Q V_{n - 1}</math>
-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>.
+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>.
-Zauważmy jeszcze, że PARI/GP umożliwia szybkie potęgowanie modulo i nie musimy korzystać z funkcji <code>modPower()</code>. Wystarczy napisać
+'''Punkt 4.'''
- <span style="font-size: 90%; color:black;">'''lift'''( '''Mod'''(a, m)^d )</span>
+Wynika z&nbsp;punktów pierwszego i&nbsp;trzeciego.
-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.
+'''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>
-<span style="font-size: 110%; font-weight: bold;">Uwaga M3</span><br/>
+::::<math>\;\, = P^n + \binom{n}{2} P^{n - 2} D + \binom{n}{4} P^{n - 4} D^2 + \ldots </math>
-Wykorzystując wzór rekurencyjny
-::<math>a \cdot b = \left\{ \begin{array}{cll}
+Z założenia <math>p \mid D</math>, zatem modulo <math>p</math> dostajemy
-  a &  & \text{gdy } b = 1 \\
-a \cdot \frac{b}{2} &  & \text{gdy } b \text{ jest parzyste} \\
-  a + 2 a \cdot \frac{b - 1}{2} &  & \text{gdy } b \text{ jest nieparzyste} \\
-\end{array} \right.</math>
+::<math>2^{n - 1} V_n \equiv P^n \pmod{p}</math>
-możemy napisać w PARI/GP prosty program do mnożenia modulo:
+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: 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.
+<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
-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.
+::<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>
-== Liczby pseudopierwsze Fermata ==
+::<math>2^n \beta^n = (P - \delta)^n = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (- \delta)^j</math>
-Liczby złożone nieparzyste spełniające równanie Fermata, otrzymały własną nazwę.
+Obliczając sumę powyższych wzorów, otrzymujemy
-<span style="font-size: 110%; font-weight: bold;">Definicja M4</span><br/>
+::<math>2^n (\alpha^n + \beta^n) = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (\delta^j + (- \delta)^j)</math>
-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>
+:::::<math>\quad \: = \underset{j \; \text{parzyste}}{\sum_{j = 0}^{n}} \binom{n}{j} P^{n - j} \cdot 2 \delta^j</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>).
+:::::<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>
-<span style="font-size: 110%; font-weight: bold;">Uwaga M5</span><br/>
+::::<math>\:\, \equiv P^n \underset{j \; \text{parzyste}}{\sum_{j = 0}^{n}} \binom{n}{j}</math>
-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>
+::::<math>\:\, \equiv 2^{n - 1} P^n \pmod{Q}</math>
-Zatem <math>\gcd (a, m) = 1</math>.
+Czyli
-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>2^{n - 1} (V_n - P^n) \equiv 0 \pmod{Q}</math>
-::<math>a^{m - 1} \equiv 1 \pmod{m}</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 C74). Co należało pokazać.
-Ponieważ <math>d \mid m</math>, to jest również
-::<math>a^{m - 1} \equiv 1 \pmod{d}</math>
+W przypadku szczególnym, gdy <math>d = n = p</math>, gdzie <math>p</math> jest nieparzystą liczbą pierwszą, otrzymujemy natychmiast (zobacz J22).
-Ale modulo <math>d</math> otrzymujemy natychmiast
+::<math>V_p \equiv P^p \equiv P \pmod{p}</math>
-::<math>0 \equiv 1 \pmod{d}</math>
+Co należało pokazać.<br/>
+&#9633;
+{{\Spoiler}}
-Co jest niemożliwe, czyli <math>m</math> nie jest PSP(<math>a</math>).
+<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
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie M6</span><br/>
+::{| border="0"
-Dla każdej podstawy <math>a \geqslant 2</math> istnieje nieskończenie wiele liczb pseudopierwszych Fermata.
+|-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}}
-Niech <math>a \in \mathbb{Z}</math> i <math>a \geqslant 2</math>. Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to
+'''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>.
-::<math>a^p - 1 = (a - 1) (a^{p - 1} + a^{p - 2} + \ldots + a^2 + a + 1)</math>
-oraz
+Dla parzystego <math>n = p + 1</math> otrzymujemy z&nbsp;twierdzenia N7
-::<math>a^p + 1 = (a + 1) (a^{p - 1} - a^{p - 2} + \ldots + a^2 - a + 1)</math>
+::<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>
-Czyli <math>a - 1 \mid a^p - 1</math> oraz <math>a + 1 \mid a^p + 1</math>.
+Ponieważ dla <math>k \in [2, p - 1]</math> jest (zobacz N44)
+::<math>\binom{p + 1}{k} \equiv 0 \pmod{p}</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
+to modulo <math>p</math> dostajemy
-::<math>a \equiv R_2 (a) \pmod 2</math>
+::<math>2 V_{p + 1} \equiv P^2 + D \cdot D^{(p - 1) / 2} \pmod{p}</math>
-oraz
-::<math>a^n \equiv R_2 (a) \pmod 2</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>
-dla dowolnej liczby całkowitej dodatniej <math>n</math>. Zatem modulo <math>2</math> jest
+Zatem
-::<math>{\small\frac{a^p - 1}{a - 1}} \equiv R_2 (a) \cdot (p - 1) + 1 \equiv 1 \pmod 2</math>
+::<math>V_{p + 1} \equiv 2 Q \pmod{p}</math>
-::<math>{\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2</math>
+'''Punkt 3.'''
-Co oznacza, że
+Dla parzystego <math>n = p - 1</math> otrzymujemy z&nbsp;twierdzenia N7
-::<math>m = {\small\frac{a^p - 1}{a - 1}} \cdot {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2</math>
+::<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>
-Czyli <math>m</math> jest '''złożoną liczbą nieparzystą'''. Pozostaje pokazać, że <math>a^{m - 1} \equiv 1 \pmod m</math>.
+Ponieważ dla <math>k \in [0, p - 1]</math> jest (zobacz N45)
+::<math>\binom{p - 1}{k} \equiv (- 1)^k \pmod{p}</math>
-Z twierdzenia Fermata wiemy, że
+to modulo <math>p</math> mamy
-::<math>a^p - 1 \equiv a - 1 \pmod p</math>
+::<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>
-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>D</math> jest liczbą kwadratową modulo <math>p</math>, zatem istnieje taka liczba <math>R</math>, że
-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>D \equiv R^2 \pmod{p}</math>
-::<math>{\small\frac{a^p - 1}{a - 1}} \equiv 1 \pmod p</math>
+Ponieważ
-Postępując analogicznie jak wyżej, dostajemy
+:* <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>
-::<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>
+Czyli
-::<math>{\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod p</math>
+::<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>
-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
+Uwzględniając, że <math>P^2 - R^2 \not\equiv 0 \pmod{p}</math>, możemy napisać
-::<math>m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} \equiv 1 \pmod{2 p}</math>
+::<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>
-Oznacza to, że <math>m = 1 + 2 k p</math> dla pewnej liczby całkowitej <math>k > 0</math>.
+::::::::<math>\equiv P^{p + 1} - R^{p + 1} \pmod{p}</math>
+::::::::<math>\equiv P^2 - R^2 \pmod{p}</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
+Zatem
-::<math>a^{2 p} \equiv 1 \pmod m</math>
+::<math>2^{p - 2} V_{p - 1} \equiv 1 \pmod{p}</math>
-Zatem modulo <math>m</math> jest
+Skąd wynika
-::<math>a^{m - 1} = a^{2 k p} = (a^{2 p})^k \equiv 1^k \equiv 1 \pmod m</math>
+::<math>V_{p - 1} \equiv 2 \pmod{p}</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/>
+Co należało pokazać.<br/>
 &#9633;
 {{\Spoiler}}
@@ Linia 208: / Linia 237: @@
-<span style="font-size: 110%; font-weight: bold;">Przykład M7</span><br/>
+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/>
-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: 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>
-  <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>
+== 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;"
-! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math>
+! &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>341</math> || <math>91</math> || <math>17895697</math> || <math>406901</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>5461</math> || <math>7381</math> || <math>1172812402961</math> || <math>254313151</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>1398101</math> || <math>597871</math> || <math>300239975158033</math> || <math>99341074625651</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>22369621</math> || <math>3922632451</math> || <math>19676527011956855057</math> || <math>62088171641031901</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>5726623061</math> || <math>317733228541</math> || <math>5037190915060954894609</math> || <math>24253192047278086344401</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>91625968981</math> || <math>2084647712458321</math> || <math>330117343809434739973099793</math> || <math>15158245029548803965250651</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) =
-<span style="font-size: 110%; font-weight: bold;">Uwaga M8</span><br/>
+ \\ najmniejsze D2PSP(P,Q) < Stop;  dla 1<=P<=10 i -5<=Q<=5
-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) );
+  '''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 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>
+<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;<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>
+! &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>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>\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>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>\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>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>\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>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>\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>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>
+! <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 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>
+<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: right; margin-right: auto;"
+::{| 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>
+! <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>
 |-
-| #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>
+| #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>
 |-
-| #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>
+| #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>
-|-
-| #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>
 |}
+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.
-<span style="font-size: 110%; font-weight: bold;">Uwaga M11</span><br/>
-Można pokazać, że jeżeli <math>m</math> jest liczbą nieparzystą złożoną i&nbsp;istnieje przynajmniej jedna liczba <math>a</math> względnie pierwsza z <math>m</math>, taka że
-::<math>a^{m - 1} \not\equiv 1 \pmod m</math>
-to dla co najmniej połowy liczb <math>b \in [1, m - 1]</math> względnie pierwszych z <math>m</math> jest
-::<math>b^{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.
+== Zmodyfikowana metoda Selfridge'a wyboru parametrów <math>P</math> i <math>Q</math> ==
-Niestety, istnieją liczby złożone <math>m</math> takie, że
+<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).
-::<math>a^{m - 1} \equiv 1 \pmod m</math>
+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>.
-dla każdego <math>a</math> względnie pierwszego z <math>m</math>. Liczby te nazywamy liczbami Carmichaela i&nbsp;jest ich nieskończenie wiele. Pokazano, że dla dostatecznie dużych <math>x</math> ilość liczb Carmichaela mniejszych od <math>x</math> przekracza <math>x^{1/3}</math><ref name="Carmichael1"/><ref name="Carmichael2"/><ref name="Carmichael3"/>. Test Fermata jest zatem zbyt zawodny, aby można było go stosować.
+<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>.
-<span style="font-size: 110%; font-weight: bold;">Przykład M12</span><br/>
+{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
-Oto wszystkie liczby Carmichaela mniejsze od <math>100 000</math>
+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>.
-::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: left; margin-right: auto;"
+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:
-| <math>561=3⋅11⋅17</math> || <math>1105=5⋅13⋅17</math> || <math>1729=7⋅13⋅19</math> || <math>2465=5⋅17⋅29</math>
+ 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></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></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>
 |-
-|  <math>2821=7⋅13⋅31</math> || <math>6601=7⋅23⋅41</math> || <math>8911=7⋅19⋅67</math> || <math>10585=5⋅29⋅73</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>
 |-
-|  <math>15841=7⋅31⋅73</math> || <math>29341=13⋅37⋅61</math> || <math>41041=7⋅11⋅13⋅41</math> || <math>46657=13⋅37⋅97</math>
+! 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>
 |-
-|  <math>52633=7⋅73⋅103</math> || <math>62745=3⋅5⋅47⋅89</math> || <math>63973=7⋅13⋅19⋅37</math> || <math>75361=11⋅13⋅17⋅31</math>
+! 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>
-== Test Millera-Rabina ==
+Równie łatwo sprawdzamy, że
-Rozpoczniemy od udowodnienia prostego twierdzenia
+ <span style="font-size: 90%; color:black;">Dickson2Test(14760229232131, 5) == 1
+ Dickson2Test(14760229232131, -7) == 1</span>
-<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}}
+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?
-Z założenia
-::<math>x^2 \equiv 1 \pmod m</math>
+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
-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/>
+::<math>(a_k \mid m) = (a_{k + 1} \mid m) = \ldots = (a_{k + r - 1} \mid m) = 1</math>
-&#9633;
-{{\Spoiler}}
+oraz
+::<math>(a_{k + r} \mid m) = - 1</math>
-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
+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>.
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie M14</span><br/>
+Ponieważ w&nbsp;pętli <code>while</code> funkcji <code>MethodA()</code> mamy następujące linie
-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>
+ <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>
-albo
+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>.
-::<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
+== Silnie pseudopierwsze liczby Lucasa i&nbsp;zmodyfikowana metoda Selfridge'a ==
-::<math>u_i = a^{2^i d}</math>
+<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>.
-gdzie <math>i = 0, 1, \ldots, r</math>
-Zauważmy, że mogą zdarzyć się następujące sytuacje
+Ilość silnie pseudopierwszych liczb Lucasa mniejszych od <math>10^n</math> dla różnych parametrów <code>start</code> funkcji <code>MethodA()</code>.
-:a) żaden z&nbsp;wyrazów ciągu <math>(u_i)</math> nie przystaje do <math>1</math> modulo <math>m</math>
+{| 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>
+|}
-: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>
+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>
+|}
-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>
+<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.
-:c) <math>u_k \equiv 1 \pmod m \quad</math> dla pewnego <math>k \in [0, r]</math>
+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>
-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.
+i <math>m < 10^{10}</math>. Następnie policzyliśmy ilość liczb SLPSP wspólnych dla różnych parametrów <math>a</math>.
-:a) <math>u_i \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math>
+Zauważamy, że im bardziej odległe są parametry <code>a</code>, to tym mniej pojawia się wspólnych liczb SLPSP.
-:b) <math>u_0 \equiv 1 \pmod m</math>
+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.
-: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>
+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>
+|}
-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}}
+== 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
-<span style="font-size: 110%; font-weight: bold;">Definicja M15</span><br/>
+::<tt>start</tt> <math>\in \{</math><tt>"*"</tt><math>, -7, 9, 13, -15, 17, -19, 21, -23, 25, -27, 29, -31, 33 \}</math>
-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>)).
+(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.
-<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>.
+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>
-<span style="font-size: 110%; font-weight: bold;">Uwaga M17</span><br/>
+Oczywiście możemy (a nawet powinniśmy), napisać program, w&nbsp;którym połączymy testy StrongLucasTest(m) i&nbsp;Dickson2Test(m).
-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) =
+  <span style="font-size: 90%; color:black;">StrongLucasAndDickson2Test(m) =
   {
-  '''local'''(d, k, r, x);
+  '''local'''(a, b, c, k, P, Q, r, SLT, w, X);
-  r = '''valuation'''(m - 1, 2); \\ wykładnik, z jakim liczba 2 występuje w rozwinięciu na czynniki pierwsze liczby m - 1
+ '''if'''( m%2 == 0, '''return'''(m == 2) );
-  d = (m - 1) / 2^r;
+ '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy liczba m nie jest kwadratowa
-  x = modPower(a, d, m);
+ X = MethodA(m);
-  '''if'''( x == 1 || x == m - 1, '''return'''(1) ); \\ x = m - 1 to przypadek k == 0
+ 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,
-         x = x^2 % m;
+         b = (b^2 - 2*c) % m;
-         '''if'''( x == m - 1, '''return'''(1) );
+         '''if'''( SLT == 0  &&  b == 0, SLT = 1 );
+        c = c^2 % m;
        );
-  '''return'''(0);
+  '''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>
-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
+== 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>0 \equiv 1 \!\! \pmod{g}</math>
+::<math>U_{2 k} (5, 5) = 5^k U_{2 k} (1, - 1)</math>
-::<math>0 \equiv - 1 \!\! \pmod{g}</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
-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
+::<math>U_{m - \epsilon} (5, 5) = 5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1)</math>
- <span style="font-size: 90%; color:black;">PrimeTest(m, k) =
+Zauważmy, że
- {
- '''local'''(a, d, j);
+:* dla <math>(P, Q) = (1, - 1) \;\; \text{i} \;\; (P, Q) = (5, 5)</math> jest <math>D = P^2 - 4 Q = 5</math>
- '''if'''( m < 2, '''return'''(0) );
+:* <math>\gcd (m, - 5) = 1</math> wtedy i&nbsp;tylko wtedy, gdy <math>\gcd (m, 25) = 1</math>
- '''if'''( m % 2 == 0, '''return'''(m == 2) );  \\ testowana liczba jest liczbą parzystą
+:* <math>U_{m - \epsilon} (5, 5) \equiv 5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1) \pmod{m}</math>
- '''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.
+<math>\Large{\Longrightarrow}</math>
- <span style="font-size: 90%; color:black;">'''forstep'''(j = 10^6+1, 10^7, 2, '''if'''( PrimeTest(j, 5) != '''isprime'''(j), '''print'''(j) ))</span>
+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
-<span style="font-size: 110%; font-weight: bold;">Zadanie M18</span><br/>
+::<math>5^{(m - \epsilon) / 2} U_{m - \epsilon} (1, - 1) \equiv 0 \pmod{m}</math>
-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}}
+Ponieważ <math>\gcd (m, 5) = 1</math>, to z&nbsp;powyższej kongruencji wynika natychmiast, że (zobacz C74)
-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>U_{m - \epsilon} (1, - 1) \equiv 0 \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ą.
+Czyli <math>m</math> jest LPSP(<math>1, - 1</math>). Co należało pokazać.<br/>
+&#9633;
+{{\Spoiler}}
-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>
+<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>).
-Czyli <math>m</math> jest PSP(<math>a</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ć
-Jeżeli spełniony jest drugi warunek, to
+::<math>U_{2 k + 1} (5, 5) = 5^k V_{2 k + 1} (1, - 1)</math>
-::<math>(a^{2^k \cdot d})^{2^{r - k}} \equiv (- 1)^{2^{r - k}} \pmod m</math>
+::<math>V_{2 k + 1} (5, 5) = 5^{k + 1} U_{2 k + 1} (1, - 1)</math>
-::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math>
+::<math>V_{2 k} (5, 5) = 5^k V_{2 k} (1, - 1)</math>
-Czyli <math>m</math> jest PSP(<math>a</math>).<br/>
-&#9633;
-{{\Spoiler}}
+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>
-<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
+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
-::<math>2^{m - 1} \equiv 1 \pmod m</math>
+::A) <math>\; U_w (1, - 1) \equiv 0 \pmod{m}</math>
-Wynika stąd natychmiast, że <math>2^{m - 1} - 1 = k m</math>, gdzie <math>k</math> jest liczbą nieparzystą. Zatem
+::B) <math>\; V_w (1, - 1) \equiv 0 \pmod{m}</math>
-::<math>N - 1 = 2^m - 2 = 2 (2^{m - 1} - 1) = 2 k 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>)
-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>
+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
-Czyli <math>N = 2^m - 1</math> jest SPSP(<math>2</math>).
+::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>)
-<span style="font-size: 110%; font-weight: bold;">Przykład M20</span><br/>
+<math>\Large{\Longrightarrow}</math>
-Tabela zawiera najmniejsze liczby silnie pseudopierwsze dla podstaw <math>a</math> od <math>2</math> do <math>15</math>
- <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=1; '''forstep'''(m=3, 20000, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, a)  &&  !'''isprime'''(m), '''print'''("a=", a, "  m=", m); s++ ); '''if'''( s>5, '''break'''() ) ))</span>
+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>).
-::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
+<math>\Large{\Longleftarrow}</math>
-! &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>
-|}
+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>
-<span style="font-size: 110%; font-weight: bold;">Przykład M21</span><br/>
+::<math>5^{(w + 1) / 2} U_w (1, - 1) \equiv 0 \pmod{m}</math>
-Tabela pokazuje ilość liczb silnie pseudopierwszych dla podstaw <math>a</math> od <math>2</math> do <math>15</math>
- <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=0; '''forstep'''(k=3, 10^6, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(k, a)  &&  !'''isprime'''(k), s++ )); '''print'''("a= ", a, "   ", s))</span>
+::<math>5^{2^{j - 1} w} V_{2^j w} (1, - 1) \equiv 0 \pmod{m}</math>
-::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
+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 C74)
-! <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.
+::<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>
-<span style="font-size: 110%; font-weight: bold;">Uwaga M22</span><br/>
+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/>
-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
+&#9633;
+{{\Spoiler}}
- <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>.
+== Zestawienie funkcji ==
-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
+<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.
-::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: right; margin-right: auto;"
+  <span style="font-size: 90%; color:black;">\\ potęgowanie modulo
-! <math>\boldsymbol{n}</math> !! <math>\boldsymbol{m}</math>
+ modPower(a, n, m) =
-|-
+ \\ a - podstawa, n - wykładnik, m - moduł
-|  <math>1</math> || <math>2047</math>
+  {
-|-
+ '''local'''(w);
-|  <math>2</math> || <math>1373653</math>
+  '''if'''( m == 1, '''return'''(0) );
-|-
+ a = a % m;
-|  <math>3</math> || <math>25326001</math>
+  w = 1;
-|-
+  '''while'''( n > 0,
-|  <math>4</math> || <math>3215031751</math>
+        '''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
-|  <math>5</math> || <math>2152302898747</math>
+        n = n/2; \\ dla nowej podstawy wykładnik jest dwa razy mniejszy
-|-
+      );
-|  <math>6</math> || <math>3474749660383</math>
+  '''return'''(w);
-|-
+  }</span>
-|  <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: 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: 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
+ <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>
-:*&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>
+ <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>
-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ą.
+ <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>
-:*&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) =
+  <span style="font-size: 90%; color:black;">\\ test Lucasa
+ LucasTest(m, start = "*") =
   {
-  '''if'''( m < 2, return(0) );
+ '''local'''(P, Q, X);
-  '''forprime'''(p = 2, 61, '''if'''( m % p == 0, '''return'''(m == p) ));
+  '''if'''( m % 2 == 0, '''return'''(m == 2) );
-  '''if'''( m == 4759123141 || m == 8411807377, '''return'''(0) );
+  '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy m nie jest liczbą kwadratową
-  '''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) );
+ 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>
-== Uzupełnienie ==
-<span style="font-size: 110%; font-weight: bold;">Uwaga M24</span><br/>
+ <span style="font-size: 90%; color:black;">\\ test BPSW
-W funkcji <code>isPrimeOr<span style="background-color: #fee481;">SPSP</span>()</code> wykorzystaliśmy zaimplementowane w&nbsp;PARI/GP funkcje:
+ 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>
-* <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) =
+  <span style="font-size: 90%; color:black;">\\ test Dicksona2
+ Dickson2Test(m, start = "*") =
   {
-  '''local'''(r);
+  '''local'''(P, Q, X);
-  '''if'''( b == 0, '''return'''('''abs'''(a)) );
+  '''if'''( m%2 == 0, '''return'''(m == 2) );
-  r = a % b;
+ '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy m nie jest liczbą kwadratową
-  '''while'''( r > 0, a = b; b = r; r = a % b );
+  X = MethodA(m, start);
- '''return'''('''abs'''(b));
+ 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;">valuation2(a, b) =
+  <span style="font-size: 90%; color:black;">\\ silny test Lucasa i test Dicksona2
+ StrongLucasAndDickson2Test(m, start = "*") =
   {
-  '''local'''(s);
+  '''local'''(a, b, c, k, P, Q, r, SLT, w, X);
-  s = 0;
+ '''if'''( m%2 == 0, '''return'''(m == 2) );
-  '''while'''(a % b == 0, s++; a = a / b);
+ '''if'''( '''issquare'''(m), '''return'''(0) ); \\ sprawdzamy, czy liczba m nie jest kwadratowa
-  '''return'''(s);
+ 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>
@@ Linia 681: / Linia 1276: @@
 <references>
-<ref name="Carmichael1">W. R. Alford, Andrew Granville and Carl Pomerance, ''There are Infinitely Many Carmichael Numbers'', Annals of Mathematics, '''140''', (1994),  703-722</ref>
+<ref name="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="Carmichael2">Glyn Harman, ''On the Number of Carmichael Numbers up to x'', Bull. London Math. Soc. 37 (2005) 641–650</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="Carmichael3">Glyn Harman, ''Watt’s Mean Value Theorem and Carmichael Numbers'', International Journal of Number Theory, Vol. 4, No. 2 (2008) 241–248</ref>
+<ref name="D2PSP3">ang. ''Dickson pseudoprime of the second kind with parameters <math>P</math> and <math>Q</math>''</ref>
-<ref name="Miller1">Gary L. Miller, ''Riemann's Hypothesis and Tests for Primality'', Journal of Computer and System Sciences '''13''', 300-317 (1976)</ref>
+<ref name="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="Rabin1">Michael O. Rabin, ''Probabilistic Algorithm for Testing Primality'', Journal of Number Theory '''12''', 128-138 (1980)</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="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="Jacobsen1">Dana Jacobsen, ''Pseudoprime Statistics, Tables, and Data'', ([http://ntheory.org/pseudoprimes.html LINK])</ref>
-<ref name="Jaeschke1">Gerhard Jaeschke, ''On Strong Pseudoprimes to Several Bases'', Mathematics of Computation, Vol. 61, No. 204 (Oct., 1993), 915-926</ref>
+</references>
-<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>