77320 Str096

18K    5. i Jofhy plerwm i roukład na czynniki

liczba p nic jest pierwsza, to dzielenie przez p nie da reszty 0, gdyż wcześniej usunęliśmy z. bf mod n wszystkie dzielniki pierwsze takiej liczby p. Ponieważ dzielenie liczby mającej nie więcej niż r cyfr przez liczbę mającą nic więcej niż x cyfr wymaga czasu rzędu 0(r.v). to widzimy, że przetestowanie każdej losowo wybranej liczby wymaga 0(rsy) operacji na bitach.

Wykonanie kroku (I) wymaga przetestowania około u^u(n(y) + 1) liczb />,. by znaleźć n(y) + 1 takich, dla których hf modn jest iloczynem liczb pierwszych mniejszych lub równych y. Ponieważ n(y) « yftogy = 0(y/s), więc krok (1) wymaga 0(n"?t²) operacji na bitach.

Wykonanie kroku (2) wymaga przeprowadzenia operacji, których czas wyraża się wielomianem zmiennych y i r (są to operacje takie jak eliminacja wierszy macierzy czy dzielenie b lub c przez n). Zatem wykonanie kroku (2) wymaga 0(yV) operacji na bitach dla pewnych liczb całkowitych j i h. Za każdym razem, gdy wykonujemy kroki (l)-(2), mamy szansę 50% na osiągnięcie sukcesu, tzn. na znalezienie b i c takich, że b ^ +c (mod ń). Dokładniej, szansa sukcesu wynosi 50%, jeśli liczba n jest podzielna tylko przez dwie liczby pierwsze, i jest większa, jeśli n dzieli się przez więcej liczb pierwszych. Jeśli zatem zadowala nas, na przykład, prawdopodobieństwo 1 — 2“⁵⁰ znalezienia nietrywialnego dzielnika liczby n, to wystarczy wykonać ten krok 50 razy. Ponieważ wystarczy to do praktycznych celów, więc ostatecznie dostajemy oszacowanie

0(5O(iiV²/ + yV)) = 0(r^hu^uy^J) = 0(rVe^to) = 0(r^ł(r/j)^^łe^fc,)_f

dla odpowiednio dobranych liczb całkowitych h i k.

Wyznaczymy teraz wartość y - lub równoważnie s - dla której to oszacowanie czasu jest najmniejsze. Ponieważ r, liczba cyfr liczby n, jest ustalona, to znaczy, że musimy znaleźć wartość s, dla której liczba (rlś)^T,,ejest najmniejsza. Równoważnie, musimy zminimalizować logarytm tej liczby, tzn.

-log - + ks. Niech zatem s s

°1B6i^:;H- -t fiS+ O+^k “ - ^^1ib?|11

Musimy więc wybrać liczbę s tak, by ks było w przybliżeniu równe - log-.

S s

Inaczej mówiąc, musimy wybrać s tak, by oba czynniki iloczynu WĘMm były w przybliżeniu równe. Ponieważ k jest stalą, to z powyższego szacowania wynika, że s² ma taki sam rząd wielkości jak rlog(r/j) = rflogr - logs), a więc s ma rząd wielkości między Jr i y/r logr . Ale to oznacza, że log s jest w przybliżeniu równy -logr i po podstawieniu log* « ^logr, otrzymamy

C

logr.

0 « — logr + k, czyli

Teraz, po wyznaczeniu tej wartości s, możemy dokończyć szacowanie czasu obliczeń. Ponieważ oba czynniki (rl$)^,,s i e** są w przybliżeniu równe przy naszym optymalnym wyborze .1, to oszacowanie czasu upraszcza się do 0{e^lkl) =    ). Oznaczając stałą -Jlk przez C, otrzymujemy osta

tecznie następujące oszacowanie liczby operacji na bitach potrzebnych do rozłożenia r-bitowej liczby n na czynniki:

0(e^c^^Ci').

Powyższe rozumowanie było bardzo powierzchowne. Nie próbowaliśmy usprawiedliwić naszych uproszczeń ani oszacować błędów. Do tego, zarówno nasz algorytm, jak i oszacowanie czasu jego wykonania są probabilistyczne.

Do chwili wynalezienia bardzo niedawno temu metody sita ciał liczbowych (por. uwagę na końcu podrozdziału 5.5), wszystkie analizy czasu działania najbardziej efektywnych algorytmów faktoryzacji prowadziły do oszacowań postaci    w niektórych przypadkach te oszacowania zostały

ściśle udowodnione, w innych zaś zależą od bardzo prawdopodobnych, ale nie udowodnionych jeszcze hipotez. Główna różnica między oszacowaniami czasu działania różnych algorytmów polega na doborze stałej C w wykładniku. Pod tym względem historia problemu faktoryzacji jest istotnie różna od problemu badania pierwszości liczb, omawianego w podrozdziale 5.1, gdzie postęp w osiąganiu coraz to lepszych czasów działania algorytmów (zwłaszcza testów deterministycznych) był w ostatnich latach zdumiewający. Dokładny przegląd zawierający porównanie algorytmów faktoryzacji znanych w początku lat osiemdziesiątych znajduje się w artykule C. Pomerance’a z 1982 roku, cytowanym w bibliografii na końcu tego podrozdziału^.

Uwaga. Ponieważ r = 0(logn), to powyższe oszacowanie czasu może być zapisane w postaci    ' *    ~

Czas (rozkład ń) = 0(e^c'^Jio,*^}ot}ot").

Przypuszcza się, że z wyjątkiem metody sita ciał liczbowych najszybsze asymptotycznie ze znanych algorytmów faktoryzacji mają czas działania wyrażony powyższym wzorem ze stałą C = 1 + e, przy czym liczba sjest dowolnie mała.

Konsekwencje dla systemu RSA. Przypomnijmy, że bezpieczeństwo systemu kryptograficznego RSA (por. podrozdział 4.2) jest oparte na tym, że rozłożenie na czynniki bardzo dużej liczby całkowitej postaci n - pq jest znacznie bardziej czasochłonne niż inne czynności, które musi wykonać uprawniony użytkownik systemu i które mają czas działania wielomianowy lub prawie wielomianowy (testowanie pierwszości) w zależności od liczby cyfr r liczby rt.

^,ł Najnowszy przegląd testów pierwszości i metod faktoryzacji znajduje się w książce: Cohen H.: Computer Methods in Algebraic Number Theory, Springer-Ycrlag 1994 (pmp. tłum.).