50082 Str104

204 S Uc/by |iierw»« i rncfcfaid ni czynniki

Pcxlstawowe kroki algorytmu można krótko opisać w następujący sposób. Dla danej liczby całkowitej ??. którą mamy rozłożyć na czynniki, wybieramy stopień d i próbujemy przedstawić n jako wartość w punkcie w pewnego nierozkładalncgo wielomianu unormowanego o współczynnikach całkowitych, stopnia d:

n sa f(m) = m^ś +    w^-**¹ + a_d. ₂m^rf~“ + ... + a_lm + a₀,

przy czym rząd wielkości liczb całkowitych m i a_k nic przekracza 0(n^l,i). Jeden ze sposobów znalezienia takiego wielomianu polega na przedstawieniu liczby tt w postaci rozwinięcia w systemie pozycyjnym o podstawie m, gdzie liczba m jest częścią całkowitą pierwiastka stopnia d z liczby n. Analiza algorytmu wskazuje, że dla liczb 125-cyfrowych powinno się przyjąć d— 5, tak by zarówno /«, jak i współczynniki miały po około 25 cyfr.

Metoda sita ciał liczbowych polega teraz na wyszukaniu (za pomocą przesiewania podobnego do tego z jakim mieliśmy do czynienia w przypadku sita kwadratowego) możliwie wielu takich par (o, 6), dla których liczby a + bm oraz bⁱf(-alb) = {-a)^d + a_t__l(-a)^l~^lb + a_t^₁(~a)ⁱ~²b¹ + — — a_labⁱ~^l + 0^* są Mczbami względem danej bazy rozkładu B. Szczegółowy opis tego, jak to zrobić i jak następnie otrzymuje się rozkład na czynniki liczby n, znajduje się w cytowanej w bibliografii książce The Deuelopment of the Number Field Sieve. Aby ta procedura zadziałała, stosunek liczby iMiczb do liczby wszystkich wartości wielomianu / musi być w przybliżeniu równy stosunkowi liczby iMiczb do liczby wszystkich liczb tej samej wielkości. Chociaż prawdopodobnie jest to prawdziwe, oraz było prawdziwe we wszystkich sprawdzonych przypadkach, nie wydaje się, by można było łatwo tego dowieść. Ponieważ oszacowanie czasu działania algorytmu zależy od tej nie udowodnionej hipotezy, jest to oszacowanie heurystyczne. Pomimo że prawdopodobnie nie ma to wielkiego wpływu na praktyczne zastosowania do rozkładania liczb, jest to jednak poważny otwarty problem w analizie teoretycznej asymptotycznej złożoności obliczeniowej problemu faktoryzagi.

Autor chce tu złożyć podziękowania Joe Buhlerowi za dostarczenie do tej książki tego krótkiego streszczenia metody sita ciał liczbowych.

ćwiczenia

1.    Znajdź wszystkie relacje liniowej zależności modulo 2 między wierszami macierzy podanej w przykładzie w tekście książki, a następnie pokaż, że jeśli P = 50 i A < 499, to nie można tą metodą otrzymać nietry wialnego rozkładu liczby 1042387.

2.    Niech n dąży do nieskończoności i przypuśćmy, że liczby Pi Asą wybierane zawsze tak, by miały ten sam rząd wielkości (np. załóżmy, że istnieją

stale dodatnie e, i c_z takie, że c_x <■ log Al log /•* < e₂>. Który krok spośród 1 -7 zabiera asymtotycznie najwięcej czasu w podanej wyżej wersji metody sita kwadratowego? Podaj oszacowanie za pomocą notacji O liczby operacji wykonywanych w tym kroku.

3. Wykorzystaj metodę opisaną w tym podrozdziale z parametrami P = 50, A — 500 do rozkładu na czynniki następujących liczb: (a) 1046603, (b) 1059691, (c) 998771.

Bibliografia

1. Caron T._f SiWerman R.: Parallel impłementation of the quadralic steve. J. Super computinję. 1988, 1, s. 273-290.

2.    Gcrver J.L.: Factoring large numbers with a ąuadratic «eve. Math. Camp.. 1983. 41,    1X1 -

-294.

3.    Len sir a A., Lenslra H.W., Jr. (red.): The deoełopment of the Number Field Sieoe. Springer--Verlag 1993.

4.    Lenslra H.W., Jr., Pomerance C.: A rigorous time botmd for factoring mtegers. J. Arrter. Math. Soe., 1992, 5, s. 483-516.

5.    Pomerance C.: Analysis and comparison of some inieger factoring algoritłrms. W: Computat io-nal Methods in Number Theory, wyd. przez: H. W. Lenslra, Jr. i R. Tijdeman. Mathemaiisch Centrum, Amsterdam, 1982, s. 89-139.

6.    Pomerance C.: Factoring. Cryptology and Computational Number Theory. Proc. Symp. Appl. Math., 1990, 42, s. 27-47.