37945 Str080

5

Liczby pierwsze i rozkład na czynniki

W wielu sytuacjach chcemy wiedzieć, czy duża liczba n jest liczbą pierwszą. Na przykład w systemie kryptograficznym RSA z publicznym kluczem oraz w wielu innych systemach kryptograficznych opartych na problemie logarytmu dyskretnego w ciałach skończonych musimy znaleźć dużą „losową” liczbę pierwszą. Jednym ze sposobów interpretacji tego, co ten zwrot oznacza, jest wybranie dużej liczby nieparzystej n₀ za pomocą generatora cyfr losowych, a następnie testowanie, czy liczby n₀, n_Q + 2,... są pierwsze, tak długo aż otrzymamy najmniejszą liczbę pierwszą, która jest nie mniejsza niż n₀. Inną okazją do testowania, czy dana liczba jest pierwsza, jest sprawdzanie, czy liczba pewnej szczególnej postaci jest liczbą pierwszą. Dla pewnej liczby pierwszej f możemy na przykład chcieć wiedzieć, czy 2^f~^l jest liczbą pierwszą Mersenne’a. Jeśli zajmujemy się ciałem mającym 2¹ elementów, to wiemy już, że każdy element ^0,1 jest generatorem grupy FJ, wtedy (i tylko wtedy), gdy 2^f~^l jest liczbą pierwszą (zob. ćwiczenie 13(a) w podrozdziale 2.1).

Test pierwszości polega na sprawdzeniu, czy liczba n nie jest pierwsza. Jeśli liczba n „przechodzi” pomyślnie przez test pierwszości, to może być pierwsza. Jeśli przechodzi pomyślnie wiele testów pierwszości, to jest bardzo prawdopodobne, że jest liczbą pierwszą. Natomiast, jeśli n nie przechodzi pomyślnie choć przez jeden test pierwszości, to na pewno jest liczbą złożoną. Ale to stawia nas wobec bardzo trudnego problemu: znalezienia dzielników pierwszych liczby n. Ogólnie, znacznie bardziej czasochłonne jest rozłożenie na czynniki dużej liczby, gdy wiemy, że jest ona liczbą złożoną (bo nie spełniła pewnego testu pierwszości), niż znalezienie liczby pierwszej tego samego rzędu wielkości. (Jest to stwierdzenie o charakterze empirycznym, a nie twierdzenie; nic tego typu nie zostało dowiedzione). Bezpieczeństwo systemu kryptograficznego RSA jest oparte na założeniu, że znacznie łatwiej jest komuś znaleźć dwie niezwykle duże liczby pierwsze p i q, niż komuś innemu znaleźć oba czynniki pierwsze liczby n, jeśli zna on tylko liczbę n = pq, ale nie zna ani p, ani q. Po omówieniu testów pierwszości w podrozdziale 5.1, opiszemy dwie różne metody rozkładu na czynniki pierwsze w podrozdziałach 5.2-5.5.

5,1. Liczby pseudopierwsze

Czy zauważyliście, by ktoś kiedykolwiek szukał naprawdę dużych liczb, które nie jq pierwsze? To znaczy, czy chciałbyś kiedykolwiek przeczytać wiadomość, źe „dziś Wydział Informatyki Univcrsity of 7/aihington ogłosił, że liczba 2^{511,1 fi33031} + 8 jest parzysta. Jest to największa dotychczas znaleziona liczba złożona."

- napis w toalecie, 0'nr/eraty of Washington

Zjawisko, którego prawdopodobieństwo zajścia wynosi 10"^w, me będzie nigdy miało miejsca, a jeśli nawet, to nie zostanie nigdy zaobserwowane.

- Ćmilc Borei, Lu ProbabUltis et tanie

Niech n będzie dużą liczbą nieparzystą i przypuśćmy, że chcemy stwierdzić, czy n jest liczbą pierwszą. Najprostszym testem pierwszości jest „wyrywków e dzielenie”. Oznacza to, że bierzemy jakąś nieparzystą liczbę m i patrzymy, czy dzieli ona n. Jeśli m ± 1, n i m|n, to n jest złożona; w przeciwnym przypadku n przechodzi pomyślnie test „wyrywkowego dzielenia przez m". Gdy m przebiega liczby nieparzyste, począwszy od 3, i n przechodzi pomyślnie przez wszystkie przeprowadzane testy wyrywkowego dzielenia, wtedy coraz bardziej prawdopodobne staje się to, że n jest liczbą pierwszą. Wiemy z całą pewnością, że n jest pierwsza, gdy m osiągnie Jn. Oczywiście jest to bardzo czasochłonna metoda testowania, czy liczba n jest pierwsza. Inne testy opisane w tym podrozdziale są znacznie szybsze.

Większość znanych efektywnych testów pierwszości przypomina w ogólnym zarysie następujący test.

Wiemy, że zgodnie z małym twierdzeniem Fermata, jeśli liczba n jest pierwsza, to dla dowolnej liczby 6, takiej że NWD(b, n) = 1, mamy

ó*^-1 s 1 (mod n).    (1)

Jeśli liczba n nie jest pierwsza, to nadal jest możliwe (choć mało prawdopodobne), że (1) zachodzi.

Definicja. Jeśli n jest nieparzystą liczbą złożoną i b jest jakąkolwiek liczbą taką, że NWD(n, b) = 1 oraz zachodzi (1), to liczbę n nazywamy liczbą pseudopiem-szą przy podstawie b.

Inaczej mówiąc, liczba „pseudopierwsza” to taka liczba n, która „udaje” liczbę pierwszą w ten sposób, że przechodzi pomyślnie test (1),

Przykład 1. Liczba n = 91 jest liczbą pseudopierwszą przy podstawie b = 3, ponieważ 3⁹⁰ s 1 (mod 91). Jednakże 91 nie jest pseudopierwsza przy podstawie 2, ponieważ 2⁹⁰ = 64 (mod 91). Gdybyśmy nie wiedzieli jeszcze, żc 91 jest liczbą złożoną, to fakt, żc 2⁹⁰ # 1 (mod 91) przekonałby nas o tym.