Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju: Różnice pomiędzy wersjami
| Linia 272: | Linia 272: | ||
<span style="font-size: 110%; font-weight: bold;">Uwaga N7</span><br/> | <span style="font-size: 110%; font-weight: bold;">Uwaga N7</span><br/> | ||
| − | Wykorzystując funkcje <code>jacobi(a, n)</code> i <code>modLucas(n, P, Q, m)</code> (zobacz | + | Wykorzystując funkcje <code>jacobi(a, n)</code> i <code>modLucas(n, P, Q, m)</code> (zobacz J45, M15) możemy napisać prosty program do testowania pierwszości liczb na podstawie twierdzenia N4. |
<span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">D2PSP</span>(m, P, Q) = | <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">D2PSP</span>(m, P, Q) = | ||
Wersja z 16:40, 13 lis 2023
Podzielność wyrazów [math]\displaystyle{ V_n (P, Q) }[/math] przez liczbę pierwszą nieparzystą
Twierdzenie N1
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.
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 M7 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 N2
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]
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 M46)
- [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 J19).
- [math]\displaystyle{ V_p \equiv P^p \equiv P \pmod{p} }[/math]
Co należało pokazać.
□
Twierdzenie N3
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]
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 M7, 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 M43)
- [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 M7
- [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 M44)
- [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 M7
- [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 M45)
- [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 N3 (i tylko te punkty) w zwartej formie, musimy założyć, że [math]\displaystyle{ \gcd (p, D) = 1 }[/math]. Otrzymujemy
Twierdzenie N4
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 N5
Z twierdzenia N4 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 N6
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 N7
Wykorzystując funkcje jacobi(a, n) i modLucas(n, P, Q, m) (zobacz J45, M15) możemy napisać prosty program do testowania pierwszości liczb na podstawie twierdzenia N4.
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 N8
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]
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 N9
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]
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 N10
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 N11
Przykłady N9 i N10 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 N18 i N19), 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 N12
Pokazać, że dla dowolnej niekwadratowej liczby nieparzystej [math]\displaystyle{ m }[/math] jest: MethodA(m, 9) = MethodA(m, -11).
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 N13
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 N14
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 N12), 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 N15
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 N12), 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 N16
Przyglądając się wierszom drugiej tabeli z przykładu N15, ł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 N17
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 N14). Ż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ń N18 i N19 zostały oparte na pomyśle przedstawionym przez Bailliego, Fioriego i Wagstaffa[5].
Twierdzenie N18
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]).
W zadaniu M12 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 N19
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]).
W zadaniu M12 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 N20
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)