83091 Str094

184    9. Ucshy pierwstc i ro/khul ni iwnnlkl

się losowy wybór liczb /»,. Wybieramy liczbę całkowitą y, średniej wielkości; jeśli na przykład liczba n ma 50 cyfr dziesiętnych, to y może mieć 5 lub 6 cyfr dziesiętnych. Niech R składa się z liczby - I i wszystkich liczb pierwszych Wybieramy dużą liczbę losowych liczb b_{ i próbujemy rozłożyć bezwzględnie najmniejszą resztę bf mod n na iloczyn liczb pierwszych należących do R. Z chwilą gdy otrzymamy wiele R-liczb b, (wystarczy n(y) + 2, gdzie Ti(_r) oznacza liczbę liczb pierwszych <y), wyznaczamy odpowiadające im wektory w przestrzeni F* (gdzie h = rr(y) + 1) i za pomocą metody eliminacji znajdujemy podzbiór wszystkich b_{ taki, że suma odpowiednich wektorów c, jest wekLorem zerowym. Następnie tworzymy iloczyny b = \]b_t mod n oraz c - | ] py mod rt w sposób opisany powyżej. Wtedy b¹ s c^l (mod «). Jeśli b = ±c (mod ń)_% to od nowa wybieramy inny zbiór losowych B-liczb (lub bardziej efektywnie, szukamy innego zbioru wierszy w macierzy wektorów śj, których suma jest wektorem zerowym; w razie potrzeby szukając nowych R-liczb i odpowiadających im wektorów). Kiedy wreszcie otrzymamy b¹ s c² (mod ń) oraz 6 # +c (mod n). obliczamy NWD(b + c, n), będący nietrywialnym dzielnikiem n.

Heurystyczne oszacowanie czasu. Przedstawimy teraz bardzo pobieżnie obliczenia prowadzące do oszacowania liczby operacji na bitach, potrzebnych do rozłożenia bardzo dużej liczby n na czynniki za pomocą opisanego wyżej algorytmu. Przyjmiemy szereg upraszczających założeń i przybliżeń, a ostateczny wynik i tak będzie tylko oszacowaniem probabilistycznym. Jeśli nie będziemy mieli szczęścia przy wyborze naszych losowych liczb b_lt to wykonanie algorytmu może się znacznie wydłużyć.

Będziemy potrzebować następujących pomocniczych faktów:

Fakt 1. (Wzór Stirlinga) log(n!) jest w przybliżeniu równy n log n — n.

Zwrot „w przybliżeniu” oznacza, że różnica rośnie wolniej niż n, gdy n -*■ oo. Tego faktu można dowieść, zauważając, że log(n!) jest sumą Riemanna (przy wyborze prawych końców 2,3,... z każdego przedziału) całki oznaczonej

M

J log xdx = /ilpgn — Ti + 1.

i

Fakt 2. Dla danej liczby naturalnej N i liczby dodatniej u liczba wszystkich

N

ciągów nieujemnych liczb całkowitych długości N, takich że £ ajśu, wy-

J=i

Zapis [u] oznacza tu część całkowitą liczby u. Fakt 2 może być udowodniony w taki sposób, że każdemu ciągowi N liczb et] przyporządkowujemy następujący ciąg N liczb fłj wybranych spośród liczb 1, 2, .... [w] + N. Niech + 1 oraz dla j ^ 1 niech es u_J+l + 1, tzn. wybieramy liczby

. _t8j_(t by między //y_, i /;_y było r/y liczb. To określa wzajemnie jednoznaczne '^porządkowanie między rozważanymi ciągami liczb «y i sposobami wyboru y |jc7,b ze zbioru [u] f iV liczb.

Kluczowym krokiem w oszacowaniu czasu działania naszego algorytmu iest teraz oszacowanie prawdopodobieństwa tego, źe liczba losowa mniejsza od \ jest iloczynem liczb pierwszych mniejszych od y (prą czym y jest liczba

zacznie mniejszą od x). Aby to zrobić, przyjmujemy najpierw stosunek ^/m    log;

jako u. Zatem, jeśli x jest liczbą r-bitową i y jest liczbą .r-bitową, to liczba u jest _w przybliżeniu równa stosunkowi liczby cyfr rjs.

W trakcie obliczeń będziemy stosować pewne uproszczenia, polegające _na zaniedbywaniu małych liczb. Będziemy to robić przy założeniu, że liczba _u jest znacznie mniejsza od y. Jak zwykle, n(y) oznacza liczbę liczb pierwszych mniejszych lub równych y. Ponieważ z twierdzenia o liczbach pierwszych wynika, że liczba k(y) jest w przybliżeniu równa y/logy, to przyjmujemy również, że mamy do czynienia z liczbą u znacznie mniejszą od *(y). W typowym zastosowaniu tego algorytmu w praktyce moglibyśmy przyjąć następujące przybliżone wartości liczb y, u i x:

y « 10⁶ (a więc n(y)« 7 • 10* i Iogy «14); u « 8; x « 10⁴⁸.

Zwykle przez ¥(x, y) oznacza się liczbę takich liczb całkowitych nie większych niż x, które nie dzielą się przez żadną liczbę pierwszą większą od y, tzn. liczbę takich liczb całkowitych, które można zapisać w postaci iloczynu \\fi^J < x_} przy czym liczby oty są nieujemne i iloczyn jest rozciągnięty na wszystkie liczby pierwsze nie większe niż y. Istnieje oczywiście wzajemnie jednoznaczna odpowiedniość między ciągami liczb całkowitych nieujemnych długości 7i(y\ dla których f] p^aj^J < x_y a liczbami całkowitymi mniejszymi lub rów-

nymi x, które nie są podzielne przez żadną liczbę pierwszą większą od y. Zatem liczba Y(x, y) jest równa liczbie rozwiązań w liczbach całkowitych a, nierów-*(y)

ności £    < logjc, powstałej w wyniku zlogarytmowania obu stron po-

i=i

przedniej nierówności. Zauważmy teraz, że logarytmy większości liczb p_} są niewiele mniejsze od log.y. Jest tak dlatego, że większość liczb pierwszych mniejszych od y ma prawie taką samą liczbę cyfr co y\ tylko niewiele z nich, w porównaniu z ich liczbą, ma znacznie mniej cyfr, a więc znacznie mniejszy logarytm. Możemy zatem pozwolić sobie na zastąpienie logp_} w ostatniej nierówności przez log}'. Po podzieleniu obu stron powstałej nierówności przez logy i po zastąpieniu log jc/logy przez u, stwierdzimy, że liczba H^,(x, y) jest

* w

w przybliżeniu równa liczbie rozwiązań nierówności £ oij < u.