Str088

172 S. liczby pierwsrc i rozkład ni czynniki

na czynniki. Może to błędnic sugerować, że testy pierwszości mogłyby być w ten sposób wykorzystane do faktoryzacji. Tak jednak nie jest. Jeśli mamy daną dużą liczbę złożoną n (np. iloczyn dwóch dużych losowych liczb pierwszych). to jest niezwykle mało prawdopodobne, byśmy natrafili na taką podstawę h, przy której liczba n jest pscudopierwsza (por. ćwiczenie 5(a), by zorientować się, jakie jest prawdopodobieństwo natrafienia na taką podstawę b). Zatem różne wyrafinowane testy pscudopicrwszości służą tylko temu, by przekonać się. że dana liczba pierwsza rzeczywiście jest pierwsza; w praktyce, jeśli chcemy rozłożyć na czynniki liczbę złożoną, to okaże się, że nic przejdzie ona pomyślnie przez żaden test pierwszości, jakiemu ją poddamy. Te testy pierw-szości nic pomogą nam zatem w rozłożeniu tej liczby na czynniki.

Bibliografia

1.    Adlcman L.M., Pomcrancc G, Rumely R.S.: On distinguishing primc numbers from com-posite numbers. Annab of Maih., 1983,117, s. 173-206.

2.    Cohen H., Lenstra H.W., Jr.: Primalily testing and Jacobi sums. Maih. Comp., 1984, 42, s. 297-330.

3.    Dixon J.D.: Factorization and primality tests. American Maih. Monthly, 1984, 91, s. 333-352.

4.    Kranakis E.: Primalily and Cryptography. John Wiley & Sons 1986.

5.    Lenstra A.: Primality testing. Cryptology and Computational Number Theory, Proc. Symp. Appl. Maih., 1990,42, s. 13-25.

6.    Miller G.L.: Riemann's hypolhesis and tests for primalily. Proc. 7th Annual ACM Symposium on ihe Theory of Compuling, s. 234-239.

7.    Pomcrancc C.: Rccent developments in primality testing. The Maih. Intelligencer, 1981, 3, 197-105.

8.    Pomerancc C: The search for prime numbers. Scientific American, 1982, 247, s. 136-147.

9.    Rabin M.O.: Probabilislic algorithms for testing primalily. J. Number Theory, 1980, 12, s. 128-138.

10.    Solovay R., Strassen V.: A fast Monte Carlo test for primality. SI AM J. Compuling, 1977,6, s. 84-85 oraz errata 1978, 7, s. 118.

11.    Wagon S.: Primality testing. The Maih. Intelligencer, 1986, 8, No. 3, s. 58-61.

5.2. Metoda p

Przypuśćmy, że wiemy, iż pewna duża liczba nieparzysta n jest złożona; na przykład stwierdziliśmy, że nie przeszła pomyślnie przez któryś z opisanych w podrozdziale 5.1 testów pierwszości. Jak już wspomnieliśmy wcześniej, nie oznacza to, że mamy jakiekolwiek pojęcie o tym, jakie liczby mogą być dzielnikami n. Spośród opisanych metod badania pierwszości liczb tylko najwolniejsza - polegająca na dzieleniu przez kolejne liczby pierwsze mniejsze niż Jn - dawała w wyniku dzielnik pierwszy razem z informacją o tym, że liczba n jest złożona. Żaden szybszy algorytm do testowania pierwszości liczb nie był tak bezpośredni: wiadomo było, że liczba musi mieć dzielniki, ale nie wiadomo, jakie to dzielniki.

Metoda dzielenia przez kolejne liczby pierwsze mniejwe niż fn wyma-ga więcej niż 0{\fn) operacji na bitach. Najprostszym algorytmem, istotnie szybszym od tej metody, jest „metoda p" i. M. Pollarda (zwana również metodą „Monte Carlo”).

Pierwszy krok w metodzie p polega na wyborze łatwo obliczalnej funkcji przekształcającej zbiór Z/nZ w siebie, mianowicie względnie prostego wielomianu o współczynnikach całkowitych, takiego jak f(x) = x² + 1. Następnie wybieramy jakąś początkową wartość x = x₀ (np. =1 lub x₀ = 2, lub też wybieramy liczbę wygenerowaną losowo) i obliczamy kolejne iteracje funkcji f. jcj =/(*o)» *2 =/(/W)» *3 =/(/(/(*o))) »td. Zatem definiujemy

Wtedy porównujemy różne liczby Xj między sobą, mając nadzieję na to, że pewne dwie z nich będą dawały różne reszty przy dzieleniu przez n i takie same reszty przy dzieleniu przez pewien dzielnik n. Jeśli znajdziemy takie liczby x_i i x_k, to NWD(xj - x_k, n) będzie właściwym dzielnikiem n i nasze zadanie zostanie rozwiązane.

Przykład 1. Rozłóżmy liczbę 91 na czynniki, wybierając wielomian f{x) = x² + 1 i wartość początkową x₀ = 1. Wtedy mamy kolejno x₁ = 2_J x₂ = 5, x₃ = 26 itd. Stwierdzimy, że NWD(x₃ - x₂, n) = AW7)(21, 91) = 7, a więc 7 jest dzielnikiem. Oczywiście ten przykład jest trywialny: dzielnik 7 mogliśmy łatwiej znaleźć metodą kolejnego dzielenia przez liczby nieparzyste.

W metodzie p ważne jest, by wybrany wielomian f(x) przekształcał zbiór Z/nZ w siebie, w sposób „losowy”. Zobaczymy na przykład, że wielomian f(x) nie może być liniowy, a nawet nie powinien być przekształceniem wzajemnie jednoznacznym.

Przypuśćmy, że f(x) jest „losowym” przekształceniem Z/nZ w siebie i obliczmy, jak długich obliczeń możemy się spodziewać, zanim natrafimy na dwie wartości x_} i x_k takie, że różnica x_i - x_k ma nietrywialny wspólny dzielnik z liczbą n. Zrobimy to, znajdując dla ustalonego dzielnika r liczby n (którego w praktyce nie będziemy znali) średnią wielkość (ze względu na wszystkie funkcje Z/nZ w siebie i wszystkie wartości początkowe x₀) pierwszego indeksu k, dla którego istnieje indeks j < k taki, żc Xj = x, (mod r). Inaczej mówiąc, patrzymy na funkcję f(x) jak na funkcję z Z/rZ w siebie i pytamy

0    to, ile potrzeba iteracji, by natrafić na pierwsze powtórzenie wartości x, = x_k w Z/rZ.

Twierdzenie 5.2.1. Niech S będzie zbiorem mającym r elementów. Dla danej funkcji f ze zbioru S >v siebie i danego elementu x₀eS, niech x_J4., = f(xj) dla j:~= 0, 1,2,.... Niech X będzie dodatnią liczbą rzeczywistą i niech

1    - 1 + [>/2 Ar]. Wtedy stosunek liczby par (/, x₀), dla których wszystkie Jf₀, x_{,