Str086

168    3. Liczby picrwM i rozkład ni czynnik

Wtedy wystarczyłoby przeprowadzić test (3) tylko dla pierwszych B podstaw, by być całkowicie pewnym, że liczba n jest pierwsza.

Taki fakt jest znany, ale zależy to od pewnej nie udowodnionej hipotezy, zwanej „uogólnioną hipotezą Ricmanna". Zwyczajna hipoteza Ricmannn jest stwierdzeniem, że wszystkie zespolone miejsca zerowe tak zwanej „funkcji zeta Ricmanna” ((s) (która jest określona jako suma odwrotności 5-tych potęg liczb naturalnych dodatnich, gdy s > )), które leżą w „pasku krytycznym" (gdzie część rzeczywista liczby .r jest zawarta między 0 i 1) muszą leżeć na „prostej krytycznej" (gdzie część rzeczywista liczby .v jest równa 1/2). Uogólniona hipoteza Ricmanna jest takim samym stwierdzeniem, ale dotyczącym pewnych uogólnień funkcji ((5), zwanych „L--szeregami Dirichleta". Z następującego faktu, którego dowód wykracza poza zakres tej książki, wynika, że test Millcra-Rabina (3) jest testem deterministycznym działającym w czasie wielomianowym (względem log w), przy założeniu, że jesteśmy gotowi uznać prawdziwość uogólnionej hipotezy Ricmanna (GRH).

Jeśli GRH jest prawdziwa i n jest złożoną liczbą nieparzystą, to n nie przechodzi pomyślnie przez test (3) dla co najmniej jednej podstawy b mniejszej od 2 log^an.

3. W latach osiemdziesiątych znaleziono efektywny deterministyczny test pier-wszości, który - mówiąc dokładnie - nie jest wielomianowy względem logn, ale w praktyce pozwala dowieść pierwszości liczb mających ponad sto cyfr dziesiętnych w czasie kilku sekund (na współczesnych dużych komputerach). Ta metoda Adlemana-Pomerance’a-Rumely’ego i Cohena-Lenstry jest oparta na tych samych pomysłach co test opisany wyżej, poza tym, że używa twierdzenia analogicznego do małego twierdzenia Fermata w rozszerzeniach ciała liczb wymiernych. Podstawową rolę odgrywają sumy Gaussa (których pewne typy zostały wprowadzone w podrozdziale 2.2 po to, by dowieść prawa wzajemności dla reszt kwadratowych) i blisko z nimi związane „sumy Jacobiego". Szczegółowa dyskusja tej metody zaprowadziłaby nas jednak zbyt głęboko w tę teorię. Obszerny i czytelny opis tej metody jest podany w artykule Cohena i Lenstry w Mathematics of Computation.

Ćwiczenia

1. (a) Znajdź wszystkie podstawy 6, przy których 15 jest liczbą pseudopierw-szą. (Nie bierz pod uwagę podstaw trywialnych ±1.)

(b)    Znajdź wszystkie podstawy, przy których 21 jest liczbą pseudopierwszą.

(c)    Udowodnij, że istnieje 36 podstaw 6e(Z/91Z)* (tzn. 50% wszystkich możliwych podstaw), przy których 91 jest liczbą pseudopierwszą.

(d)    Uogólnij punkt (c) pokazując, że jeśli zarówno /?, jak i 2/7 - 1 są liczbami pierwszymi i n - p(2p - 1), to liczba n jest pseudopierwszą dla 50% możliwych podstaw, mianowicie dla wszystkich b, które są resztami kwadratowymi modulo 2/7—1.

2 Miech n będzie dodatnią, nieparzystą liczbą złożona i niech SWDib, n) =

' g 1.

(a)    Wykaż, że jeśli p jest dzielnikiem pierwszym liczby n oraz ii' = nip, to liczba n jest pseudopierwszą przy podstawie b wtedy i tylko wtedy, gdy b«'T¹ fi 1 (mod p).

(b)    Udowodnij, że żadna liczba całkowita postaci n-hp (gdzie p > 3 je*t liczbą pierwszą) nie jest pseudopierwszą przy podstawach 2,5 i 7.

(c)    Udowodnij, że żadna liczba całkowita postaci n-ip (gdzie p > 5 jest liczbą pierwszą) nie jest pseudopierwszą przy podstawach % 3 i 7.

(d)    Udowodnij, że liczba 91 jest najmniejszą liczbą pseudopierwszą przy podstawie 3.

3.    Udowodnij, że liczba p¹ (gdzie p jest liczbą pierwszą) jest pseudopierwszą przy podstawie b wtedy i tylko wtedy, gdy b'~^l = \ (mod p¹).

4.    (a) Znajdź najmniejszą liczbę pseudopierwszą przy podstawie 5.

(b) Znajdź najmniejszą liczbę pseudopierwszą przy podstawie 2.

5.    Niech n - pq będzie iloczynem dwóch różnych liczb pierwszych.

(a)    Niech d - NWD(p - 1, q - 1). Udowodnij, że liczba n jest pseudo-pierwsza przy podstawie b wtedy i tylko wtedy, gdy b* = 1 (mod n). Wyraź, w zależności od d, liczbę podstaw, przy których liczba n jest pseudopierwszą.

(b)    Ile jest podstaw, przy których liczba n jest pseudopierwszą, jeśli q = 2p + 1? Wypisz je wszystkie (w zależności od p).

(c)    Niech n — 341. Jakie jest prawdopodobieństwo tego, że losowo wybrana liczba b, względnie pierwsza z n, jest podstawą, przy której liczba n jest pseudopierwszą?

6.    Pokaż, że jeśli liczba n jest pseudopierwszą przy podstawie óe(Z/nZ)*, to n jest również pseudopierwszą przy podstawach -b i b~^l.

7.    (a) Udowodnij, że jeśli liczba n jest pseudopierwszą przy podstawie 2, to

liczba N — 2" - 1 też jest pseudopierwszą przy tej podstawie.

(b)    Udowodnij, że jeśli liczba n jest pseudopierwszą przy podstawie b oraz NWD(b - 1, n) = 1, to liczba N = (b* - l)l(b -1) też jest pseudo-pierwsza przy podstawie b.

(c)    Udowodnij, że istnieje nieskończenie wiele liczb pseudopierwszych przy podstawie b dla b = 2,3,5.

(d)    Pokaż na przykładzie, że punkt (b) może nie być prawdziwy, jeśli pominiemy założenie NWD(b - 1, n) = 1.

8.    Niech b będzie liczbą całkowitą większą niż 1 i niech p będzie nieparzystą liczbą pierwszą nie będącą dzielnikiem żadnej z liczb h, b - 1, b + 1. Niech /i = (ó²'-l)/(ó²-l).

(a)    Wykaż, że liczba n jest złożona.

(b)    Wykaż, że 2p\n - 1.

(c)    Wykaż, że liczba n jest pseudopierwszą przy podstawie b\ wyprowadź stąd wniosek, że dla każdej podstawy b istnieje nieskończenie wiele liczb pseudopierwszych przy tej podstawie.