22446 Str095

!8f>    5. I irrby pierw*/* i ro/.lclml na crynniki

Dokonamy tera/ następnego istotnego uproszczenia, zastępując liczbę niewiadomych n(v) przez r. Na pierwszy rzut oka mogłoby się to wydawać zbyt daleko idącą modyfikacją naszego problemu. Rzeczywiście, zastąpienie n{y) przez v powoduje wprowadzenie nietrywialnych składników do naszej sumy; jednakże okazuje się, że te wyrazy skracają się i ostateczny rezultat jest taki sam. jaki otrzymalibyśmy przy bardziej starannej aproksymacji ¥(*, y), A więc możemy założyć, że liczba H'(*, y) jest w przybliżeniu równa liczbie

y

rozwiązań w liczbach całkowitych nierówności £ ot, < u,

i* i

Ale z faktu 2 (dla A’ = y) wynika, że liczba ¥(*, y) jest w przybliżeniu

równa

M + >

. Oszacujemy teraz log

czyli logarytm prawdopo

dobieństwa tego, że losowa liczba całkowita zawarta między 1 i x jest iloczynem liczb pierwszych nie większych niż y. Zauważmy, że log* - ulogy, z definicji u. Skorzystamy z uzyskanego przybliżenia ¥(*, y) i z faktu 1:

log

/*(*,?)

^cl08l,twr^l~"^l0E>'

a ([«] + y) log ([u] + >>)- ([«] + y)~

- (MlogM - M) - 0'log)' ~y)~ ulogy.

Dokonamy teraz następnych przybliżeń. Po pierwsze, zastąpimy [ii\ przez u. Następnie, ponieważ założyliśmy, że liczba u jest znacznie mniejsza niż y, możemy zastąpić log(w + y) przez logy. Po wszystkich redukcjach otrzymamy « — u log u, tzn.

yfe y)

X

Oznacza to na przykład, że jeśli tak jak wyżej przyjmiemy * « 10⁴⁸ i y « 10⁶, to prawdopodobieństwo tego, że losowa liczba całkowita zawarta między 1 i * jest iloczynem liczb pierwszych nie większych niż y, wynosi około 1/8⁸.

Możemy teraz oszacować liczbę operacji na bitach potrzebnych do wykonania opisanego wyżej algorytmu baz rozkładu, gdzie dla uproszczenia założymy, że nasza baza rozkładu B składa się z początkowych h = 7i(y) liczb pierwszych, tzn. wszystkich liczb pierwszych nie większych niż y. Aby ułatwić sobie tę analizę założymy, że baza B nie zawiera liczby — 1 i że zamiast bezwzględnie najmniejszych reszt rozpatrujemy reszty z dzielenia bf przez n.

Zatem szacujemy liczbę operacji na bitach potrzebnych do wykonania następujących kroków: (1) wybieramy losowe liczby całkowite b_{ zawarte między 1 i n i przedstawiamy bezwzględnie najmniejsze reszty kwadratów bf modliło n w postaci iloczynu liczb pierwszych nie większych niż y, o ile jest to możliwe; kontynuujemy to postępowanie tak długo, aż zbierzemy n(y) -f 1 różnych liczb b,_t dla których bf mod n daje się wyrazić przez taki iloczyn; (2) znajdujemy zbiór liniowo zależnych wierszy odpowiedniej macierzy złożonej % zer i jedynek, wymiaru (7t(y) + 1) x n(y), by otrzymać kongruencję postaci b² s c² (mod n); (3) jeśli b = ±c (mod «), to tak długo powtarzamy (1) i (2), znajdując nowe aż otrzymamy b² & c¹ (mod n) oraz b$ ±c (mod n); wtedy znajdujemy nietrywialny dzielnik n, obliczając NWD(b + c, n).

Zakładając, że reszty z dzielenia bf przez n są rozłożone równomiernie w przedziale od 1 do n, z powyższego rozumowania wynika, że potrzebujemy około u" prób, by znaleźć liczbę 6, taką, że bf mod n jest iloczynem liczb pierwszych nie większych niż y, gdzie u = logn/Iogy. Później zastanowimy się nad tym, jaką liczbę y należy wybrać, by zminimalizować łączny czas obliczeń. Rzecz w tym, że jeśli wybierzemy dużą liczbę y, to liczba u" będzie mała i częściej będziemy znajdować liczby b_t takie, że bf mod n jest iloczynem liczb pierwszych mniejszych lub równych y. Jednak w takim przypadku rozkład liczby bf mod n na iloczyn takich liczb pierwszych - a będziemy to musieli zrobić 7t(y) + 1 razy - a następnie eliminacja wierszy otrzymanej macierzy będą trwały bardzo długo. Na odwrót, jeśli wybierzemy względnie małą liczbę y, to te ostatnie czynności będą trwały krócej, ale znacznie więcej czasu pochłonie znalezienie liczb b_u dla których liczba bf mod n rozkłada się na iloczyn liczb pierwszych nie większych niż y, gdyż liczba u“ jest wtedy bardzo duża. A więc liczbę y trzeba dobrać tak, by uzyskać pewien kompromis między tymi dwiema skrajnościami.

Aby stwierdzić, jaką liczbę y należy wybrać, najpierw dokonamy bardzo „zgrubnego” szacowania liczby operacji na bitach, w zależności ody (i oczywiście od n). Następnie dobierzemy liczbę y tak, by zminimalizować otrzymany wynik (skorzystamy tu z elementarnego rachunku różniczkowego i pewnych upraszczających przybliżeń) i wreszcie dokonamy oszacowania czasu obliczeń dla tak dobranej liczby y.

Przypuśćmy, że liczba n ma r cyfr dwójkowych, a liczba y ma s cyfr dwójkowych; wtedy liczba u jest bardzo bliska rjs. Przede wszystkim, iłu operacji na bitach wymaga przetestowanie każdej losowo wybranej liczby b{! Twierdzimy, że ta liczba operacji wyraża się pewnym wielomianem zmiennych r i y, tzn. jest rzędu O (r^le**) dla pewnych (dość małych) liczb całkowitych k i /. Wygenerowanie jednej cyfry losowej wymaga stałej ilości czasu, więc wygenerowanie jednej liczby losowej ó_r, z przedziału między 1 i n, wymaga 0(r) operacji na bitach. Następnie obliczenie bf mod n wymaga 0(r²) operacji na bitach. Musimy teraz dzielić liczbę bf mod n kolejno przez wszystkie liczby pierwsze <y (i ich potęgi), w nadziei, że po tych wszystkich dzieleniach otrzymamy iloraz równy 1. Najprościej (chociaż nie najbardziej efektywnie) można to zrobić, dzieląc przez 2 i przez kolejne liczby nieparzyste p od 3 do y, zapamiętując w trakcie obliczeń, jaka potęga p dzieli bf mod n bez reszty. Zauważmy, że jeśli