Testy pierwszości. Liczby pseudopierwsze Dicksona drugiego rodzaju: Różnice pomiędzy wersjami

Z Henryk Dąbrowski
Przejdź do nawigacji Przejdź do wyszukiwania
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 J44, M15) możemy napisać prosty program do testowania pierwszości liczb na podstawie twierdzenia N4.
+
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 17:40, 13 lis 2023

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

Dowód


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]
Dowód


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]
Dowód


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

Pokaż kod

Żół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].

Pokaż kod


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


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

Rozwiązanie


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


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


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


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


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



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

Dowód


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

Dowód



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

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