Str123

242    6. Krzywe (Iłplycnw

Oszacowanie (4) ma dokładnie taką samą postać, jak (przypuszczalne) oszacowanie czasu najlepszego znanego algorytmu faktoryzacji^. Jednak metoda Lcnstry ma pewne zalety w stosunku do metod konkurencyjnych:

1.    Jest to jodyna metoda istotnie szybsza dla rt podziclnych przez liczbę pierwszą znacznie mniejszą tdi y/n .

2.    Z tego powodu ta metoda może być używana w połączeniu z innymi metodami faktoryzacji, gdy chcemy rozłożyć na czynniki pewne pomocnicze liczby. (Na przykład w metodzie korzystającej z ułamków łańcuchowych w podrozdziale 5.4 musieliśmy rozkładać na czynniki pierwsze liczby b{ mod «, jeśli były one iloczynami względnie małych liczb pierwszych.)

3.    W odróżnieniu od innych metod, wymaga ona stosunkowo małej pamięci.

Ale chyba najbardziej ekscytującą cechą algorytmu faktoryzacji Lcnstry jest użycie po raz pierwszy krzywych eliptycznych; są to jedne z najintensywniej badanych obiektów nowoczesnej teorii liczb i geometrii algebraicznej, mające wyjątkowo bogatą strukturę. Pokazuje to, że - być może - będzie można znaleźć nowe metody faktoryzacji, korzystając z nieoczekiwanych konstrukcji pochodzących z działów matematyki dotychczas odległych od tych zagadnień.

Ćwiczenia

1.    Użyj metody Pollarda z parametrami k = 840 i a — 2 do rozkładu liczby n = 53467 na czynniki. Następnie wypróbuj a = 3.

2.    Przypuśćmy, że tylko jeden dzielnik pierwszy p liczby n ma tę własność, że liczba p — 1 nie ma dużych dzielników pierwszych. Załóżmy, że w algorytmie Pollarda bierzemy wartość k nie będącą wielokrotnością p — l i sprawdzamy różne wartości a. Oszacuj za pomocą k i p — 1 prawdopodobieństwo tego, że otrzymasz dzielnik d — p w kroku 4 algorytmu.

3.    Dla następujących wartości p i B znajdź (z pomocą komputera, jeśli to będzie konieczne) stosunek liczby tych liczb całkowitych z przedziału między p+\ —2yjp i p + 1 + 2-Jp , które nie mają dzielników pierwszych większych niż 2?, do liczby wszystkich liczb z tego przedziału: (a) p = 109, B = 3; (b)p = 109, B = 19; (c) p = 1009, B m 19; (d) p = 1009, B = 97; (e) p = 9973, B = 97.

4.    Każda liczba n w ćwiczeniu 5 z podrozdziału 5.4 ma dzielnik pierwszy p < 100. W każdym z przypadków (a)-(k) znajdź ten dzielnik za pomocą metody Lenstry, korzystającej z krzywych eliptycznych, wybierając B = 5, C = 120, P = (1,1) i E: y² = x³ + ax — a dla a = 1, 2,... (biorąc tylko te a, dla których wyróżnik jest względnie pierwszy z ń). Jaka jest w każdym przypadku najmniejsza wartość a, dla której znajdziesz dzielnik, i jaka jest

^ł) Por. uwagi dotyczące czasu działania metody sita ciał liczbowych na końcu podrozdziału 5.5 (przyp. tłum.).

wartość k_}, dla której ten dzielnik okaże się być największym wspólnym dzielnikiem mianownika i n podczas obliczania k_tP1

5.    Przypuśćmy, że dla liczby k danej wzorem (2) znaleźliśmy dzielnik n podczas obliczania k_lP modulo n, gdzie k, jest częściowym iloczynem w (2). (Przypomnijmy, że obliczamy kP, kolejno mnożąc przez liczby /, począwszy od najmniejszej). Udowodnij, źe k_{P mod p- O raod p dla pewnej liczby p\n, tzn. wyklucz tę możliwość, źe otrzymasz mianownik nie będący liczbą względnie pierwszą z n przy obliczaniu / * (kJl)P, w którymś kroku metody iterowanego podwajania, przed ostatnim krokiem.

6.    (a) Przypuśćmy, że dla dowolnej liczby neZ mamy efektywną metodę ge

nerowania punktów P = (x, y) takich, żey² s x³ -f ox (mod n). Wyjaśnij, dlaczego użycie do rozkładu liczby n na czynniki krzywych eliptycznych y² =*x³ + ax, dla różnych o, nie byłoby dobrym pomysłem, (b) Odpowiedz na takie samo pytanie dla rodziny krzywych o równaniach y² = x³ + b dla różnych b.

7.    Przypuśćmy, że chcemy zwiększyć trochę prawdopodobieństwo tego, że rząd punktu E mod p dla pewnej liczby p\N jest iloczynem małych dzielników pierwszych, dbając na początku o to, by ten rząd był podzielny przez 4. Opisz, w jaki sposób można to zrobić.

Bibliografia

1.    Lenstra H.W., Jr.: Factoring inlegers with elliptie curves. Annals of Maik {1\ 1987, 126, s. 649-673.

2.    Montgomery P.: Speeding the Pollard and elliptie cum methods of factorizalion. Maik. Comp., 1987, 48, s. 243-264.

3.    Pollard J.M.: Theorems on faclorization and primality testing. Proc. Cambridge Philas. Soc., 1974,76, s. 521-528.