Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju

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

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

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] (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 J47, 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 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, "*")	[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, "*")	[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, "*")	[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.
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) );
}