80370 Str122

240    6. K i żywe diptycmr

przez który będziemy mnożyć punkt P. Jeśli B będzie duża, to prawdopodobieństwo tego, że nas/a para P) ma własność A P mod p - O mod p dla pewnej liczby p\n, będzie większe; z drugiej strony, im większa jest liczba B, tym dłużej trwa obliczenie A /¹ mod p. Zatem liczba A? musi być wybrana jakoś tak. by zminimalizować czas działania algorytmu. Liczba C, mówiąc nieprecyzyjnie. jest ograniczeniem tych dzielników pierwszych p\n, dla których mamy szansę otrzymać równość AT mod p — O mod p. Wtedy bierzemy liczbę k daną wzorem (2); liczba k jest zatem iloczynem wszystkich nic większych od C potęg liczb pierwszych nic większych od B. Twierdzenie Hassego mówi nam, że jeśli p jest liczbą taką. że p + 1 + 2yjp < C oraz rząd grupy E mod p nic jest podziclny przez żadną liczbę pierwszą większą od B, to liczba A jest wielokrotnością tego rzędu, a więc kP mod p = O mod p.

Przykład 3. Przypuśćmy, że wybraliśmy B = 20 i chcemy rozłożyć na czynniki 10-cyfrową liczbę n, która może być iloczynem dwóch 5-cyfrowych liczb pierwszych (tzn. nie jest podzielna przez żadną liczbę pierwszą mającą mniej niż 5 cyfr). Wtedy wybieramy C = 100700 i A = 2¹⁶•3¹⁰•5⁷•7⁵•11⁴•13⁴•17⁴•19³.

Powracamy teraz do opisu algorytmu. Wykonując działania modulo rt, próbujemy obliczyć kP w następujący sposób. Korzystając z metody ite-rowanego podwajania, obliczamy najpierw 2P, 2(2P), 2(4P), ...» 2^aiP, potem 3(2*^łP), 3(3 * 2“^JP), ..., 3“^s2^a*P itd., aż wreszcie otrzymamy /^8,P. (Mno-

kb

żymy przez kolejne dzielniki pierwsze / liczby A, od najmniejszego do największego). W tych obliczeniach, jeśli tylko musimy wykonać dzielenie modulo n, korzystamy z algorytmu Euklidesa, by znaleźć element odwrotny modulo n. Jeśli któreś użycie algorytmu Euklidesa nie da nam w wyniku elementu odwrotnego modulo 7i, to albo znajdziemy nietrywialny dzielnik n, albo stwierdzimy, że sama liczba n jest największym wspólnym dzielnikiem n i pewnego mianownika. W pierwszym przypadku algorytm zakończył się sukcesem. W drugim musimy powrócić do punktu wyjścia i wybrać inną parę (E, P). Jeśli algorytm Euklidesa za każdym razem umożliwił znalezienie elementu odwrotnego - i w ten sposób obliczyliśmy AP modulo n - to również musimy powrócić do punktu wyjścia i wybrać inną parę (2s, P). To kończy opis algorytmu.

Przykład 4. Wybierzmy rodzinę krzywych eliptycznych y² = x³ + ax — a, a — 1, 2, ...» z których każda zawiera punkt P = (1, 1). Zanim wybierzemy liczbę a dla danej liczby n, musimy sprawdzić, że wyróżnik 4a³ + 27a² jest względnie pierwszy z n. Spróbujmy rozłożyć na czynniki liczbę n = 5429, gdy B — 3 i C = 92. (W tym przykładzie i w poniższych ćwiczeniach ilustrujemy metodę dla małych wartości n. Oczywiście w praktyce ta metoda nabiera wartości dopiero dla dużo większych ń). Nasz wybór C jest tu motywowany tym, że chcemy znaleźć dzielnik pierwszy p nie większy niż *Jn « 73; dla p = 73

ograniczeniem liczby F^-punktów na krzywej eliptycznej jest 74 -ł- 7~Jl3 < 92. Zgodnie ze wzorem (2) wybieramy k = 2* ■ 3*. Dla każdej wartości a mnożymy punkt /* kolejno sześć razy przez 2, a potem cztery razy przez 3 na krzywej o równaniu y² — x³ -f-    — a, za każdym razem wykonując działania modu

lo n. Dla a — 1 stwierdzimy, źe wszystkie mnożenia dają się wykonać bez przeszkód i punkt 3*2⁶ P mod p jest skończonym punktem krzywej ĆT mod p dla dowolnej liczby p takiej, że p\n. Próbujemy zatem a = 2. Wtedy stwierdzimy, że przy próbie obliczenia 3²2⁶P otrzymamy mianownik, którego największy wspólny dzielnik z liczbą /z jest właściwym dzielnikiem liczby /i równym 61. Zatem rząd punktu P — (1, 1) na krzywej y² = x* + 2x — 2 modulo 61 jest dzielnikiem liczby 3 ²2⁶. (Por. ćwiczenie 5 poniżej). A więc już druga próba zakończyła się sukcesem. Przy okazji warto wspomnieć, że gdybyśmy spróbowali a = 3, to ta metoda dałaby drugi dzielnik pierwszy 89 przy próbie obliczenia 3*2⁶P. (Zazwyczaj, choć nie zawsze, ta metoda daje najmniejszy dzielnik pierwszy.)

Czas działania. Najważniejszym problemem przy szacowaniu czasu działania algorytmu jest wyznaczenie dla ustalonej liczby p i ustalonego wyboru ograniczenia B (dokonanego w pewien optymalny sposób) prawdopodobieństwa tego, że losowo wybrana krzywa eliptyczna modulo p ma rząd N niepodzielny przez żadną liczbę pierwszą większą niż B. Wiadomo, że rzędy N wszystkich krzywych eliptycznych modulo p są rozłożone prawie równomiernie w przedziale p + 1 — 2y/p < N < p + 1    2yjp , w którym muszą się znajdować na mocy

twierdzenia Hassego (gęstość występowania tych rzędów N nieco zmniejsza się blisko końców tego przedziału). Zatem to prawdopodobieństwo jest w przybliżeniu równe prawdopodobieństwu tego, że losowo wybrana liczba wielkości rzędu p nie jest podzielna przez żadną liczbę pierwszą większą niż B. Widzieliśmy już, gdy szacowaliśmy czas obliczeń w podrozdziale 5.3, że to prawdopodobieństwo jest w przybliżeniu równe u~^u, gdzie u = iogp/logB. To prowadzi do oszacowania postaci 0(e^CyJrlogr ), gdzie r jest liczbą cyfr dwójkowych liczby n. Dokładne oszacowanie czasu obliczeń znajduje się w artykule Lenstry.

Dokładniej, załóżmy, że n jest dodatnią liczbą całkowitą, nie będącą potęgą liczby pierwszej i niepodzielną przez 2 i 3. Zakładając bardzo prawdopodobną hipotezę dotyczącą rozkładu liczb niepodzielnych przez żadną liczbę pierwszą większą niż B w małym przedziale wokół p, Lenstra udowodnił następujące probabilistyczne oszacowanie liczby operacji na bitach potrzebnych do znalezienia nietrywialnego dzielnika liczby n:

_e4 £2 + «) lo* p tagtogF^    £3)

gdzie p jest najmniejszym dzielnikiem pierwszym n i e zbiega do zera dla dużych p. Ponieważ zawsze p < yjn , więc z (3) wynika, że mamy również następujące oszacowanie:

(l + *) logu logiogil