52048 Str081

158    5. I .terby pierwsze i rozkład na czynniki

Twierdzenie 5.1.1. Niech n będzie nieparzystą liczbą złożoną. Wtedy:

(a)    Ursba n jest liczbą pseudopierwszą przy podstawie b, gdzie NWD(b, n) = i wtedy i tylko wtedy, gdy rząd b w grupie (Z/nZ)* (czyli najmniejsza dodatnia potęga b, która przystaje do 1 modulo n) dzieli n — 1.

(b)    Jeśli n jest liczbą pseudopierwszą przy podstawach b_v i b_z (gdzie N)VD(b_l, n) = NWD(b_lt n) = 1), to n jest liczbą pseudopierwszą przy podstawie b j b₂ oraz przy podstawie b_xb₂^l (gdzie bi¹ jest liczbą odwrotną do b₂ modulo n).

(c)    Jeśli n nie spełnia testu (1) przy pewnej podstawie be(Z/nZ)*, to n nie spełnia testu (1) dla co najmniej połowy możliwych podstaw b e (Z/nZ)*.

Dowód. Punkty (a) i (b) są bardzo łatwe i pozostawiamy je czytelnikowi do udowodnienia. Aby dowieść (c), niech {ó_lt b₂,    b,} będzie zbiorem wszyst

kich podstaw, przy których liczba n jest pseudopierwszą, tzn. zbiorem wszystkich liczb naturalnych 0 < b_t < n, dla których zachodzi kongruencja (1). Niech b będzie ustaloną podstawą, przy której n nie jest liczbą pseudopierwszą. Gdyby n była pseudopierwszą przy którejkolwiek podstawie bb_t, to na mocy punktu (b) byłaby również liczbą pseudopierwszą przy podstawie b = (bbjjb^¹ (mod n), co jednakże nie jest prawdą. Zatem dla s różnych reszt {bb_v bb₂,..., bb,} liczba n nie spełnia testu (1). Istnieje więc co najmniej tyle podstaw w (Z/nZ)*, przy których n nie jest liczbą pseudopierwszą, co podstaw, przy których (1) zachodzi. To kończy dowód.

Zatem, jeśli tylko nie okaże się, że n przechodzi pomyślnie przez test (1) dla wszystkich możliwych b takich, że NWD(b, ń) = 1, to mamy co najmniej 50% szansę na to, że n nie przejdzie pomyślnie testu (1) dla losowo wybranej podstawy b. Przypuśćmy więc, że chcemy wiedzieć, czy pewna duża liczba naturalna n jest pierwsza. Możemy wybrać losowo liczbę b w przedziale 0 < b < n. Najpierw znajdujemy d = NWD(b, n), używając algorytmu Euklidesa. Jeśli d> 1, to wiemy, że n nie jest pierwsza, a nawet znaleźliśmy nie-trywialny dzielnik d\n. Jeśli d = 1, to podnosimy b do (n — l)-szej potęgi (używając algorytmu iterowanego podnoszenia do kwadratu, zob. podrozdział 1.3). Jeśli (1) nie zachodzi, to wiemy, że liczba n jest złożona. Jeśli (1) zachodzi, to mamy jakiś argument przemawiający za tym, że n może być pierwsza. Wtedy próbujemy innej podstawy b i powtarzamy cały proces. Jeśli (1) nie zachodzi dla pewnej podstawy ó, to możemy zakończyć postępowanie, mając pewność, że liczba n jest złożona. Przypuśćmy, że próbujemy k różnych podstaw b i stwierdzamy, że n jest pseudopierwszą dla wszystkich k podstaw. Na mocy twierdzenia 5.1.1, szansa na to, że n jest jednak złożona, pomimo iż przeszła pomyślnie przez k testów, jest jak 1 do 2\ chyba że n okaże się mieć bardzo specjalną własność, że (1) zachodzi dla wszystkich be(Z/nZ)*. Jeśli k jest duże, możemy być pewni „z dużym prawdopodobieństwem", że n jest pierwsza (chyba że n jest pseudopierwszą przy wszystkich podstawach). Taką

metodę znajdowania liczb pierwszych nazywamy metodą probabilistyczną. Różni się ona od metody deterministycznej: słowo „deterministyczna" oznacza, żc taka metoda albo wykaże, źe n jest liczba złożoną, albo stwierdzi ze 100% pewnością, że /z jest liczbą pierwszą.

Czy może się zdarzyć, że dla liczby złożonej n test (1) zachodzi dla każdego ó? W takim przypadku nasza metoda probabilistyczna zawiedzie i nie wykaże, żc liczba n jest złożona (chyba, źe mamy wyjątkowe szczęście i trafimy na liczbę b taką, że NWD(b, n) > 1). Odpowiedź jest twierdząca, a każdą taką liczbę nazywamy liczbą Carmichaela (czytaj: Karmajkla).

Definicja. Liczba Carmichaela fal to taka liczba złożona /z, źe kongruencja (1) zachodzi dla każdej liczby óe(Z/nZ)*.

Twierdzenie 5.1.2. Niech n będzie nieparzystą liczbą złożoną. Wtedy.

(a)    Jeśli n jest podzielna przez kwadrat liczby >1. to n nie jest liczbą Carmichaela.

(b)    Jeśli n jest bezkwadratowa, to n jest liczbą Carmichaela wtedy i tylko wtedy, gdy p — 1 |n — 1 dla każdego dzielnika pierwszego p liczby n.

Dowód:

(a)    Przypuśćmy, że p²\n. Niech g będzie generatorem modulo p², tzn. taką liczbą całkowitą, że g^plp~^l) jest najniższą potęgą g, która przystaje do 1 modulo p². Zgodnie z ćwiczeniem 2 w podrozdziale 2.1, taka liczba g zawsze istnieje. Niech n' będzie iloczynem wszystkich różnych od p dzielników pierwszych liczby n. Z chińskiego twierdzenia o resztach wynika, że istnieje liczba b spełniająca dwie kongruenqe: b = g (mod p²) oraz b = 1 (mod n'). Wtedy b jest, tak jak g, generatorem modulo p¹ i spełnia również NWD(b, n) = 1, ponieważ nie jest podzielna przez p ani przez żaden dzielnik pierwszy liczby n'. Twierdzimy, że n nie jest pseudopierwszą przy podstawie b. Aby się o tym przekonać, zauważmy, że jeśli (1) zachodzi, to ponieważ p²\n, natychmiast mamy bⁿ~^l = 1 (mod p²). Ale w takim przypadku p(p — l)|n - 1, ponieważ pip - 1) jest rzędem b modulo p². Jednakże n - 1 = -1 (mod p), ponieważ p\n, a to oznacza, że n - 1 nie jest podzielna przez p(p — 1). Ta sprzeczność dowodzi, że b jest podstawą, przy której n nie jest liczbą pseudopierwszą.

(b)    Przypuśćmy najpierw, że p- l|n-1 dla każdego dzielnika pierwszego p liczby n. Niech b będzie dowolną podstawą, dla której NWD(b, n) = 1. Wtedy dla każdego dzielnika pierwszego p liczby n mamy: Ó““¹ jest potęgą ó^p_1, więc ó"^-1 = 1 (mod p). Zatem ó"'¹ - 1 jest podzielna przez wszystkie dzielniki pierwsze p liczby n, a więc i przez ich iloczyn, który jest równy n. Zatem (1) zachodzi dla wszystkich podstaw b. Na odwrót, przypuśćmy, że istnieje taka liczba p, że p - 1 nie dzieli n— \. Niech g będzie liczbą całkowitą generującą grupę (Z/pZ)*. Tak jak w dowodzie części