Str091

178    5, Liczby pierwsze i rozkład na czynniki

dIn której istnieje taka liczba / < /»;. że x_K == x_f (niod r), tzn. pierwszą wartość A:, dla której nic wszystkie .v₀,    ..., x_k są różne modliło r. Przypuść

my, że jako A₀ wybraliśmy generator grupy (Z/rZ)*. Niech r - 1 = 2% gdzie liczba t jest nieparzysta.

(a)    Napisz kongrucncję modulo r - I równoważną x_k = x_t (równość oznacza tu kongrucncję modulo r).

(b)    Znajdź najmniejsze wartości Ar i /, dla których zachodzi warunek podany w (a), wyrażając je za pomocą s i rozwinięcia dwójkowego ułamka l/l.

(c)    Jak duża jest liczba k w porównaniu z /*? Dlaczego wybór/(x) w metodzie p był zły?

Bibliografia

1.    Blair WD., Lacampagnc C.B., Selfridgc J.L.: Factoring large numbers on a pockct calculalor. American Math. Monthly, 1986,93, s. 802-808.

2.    Brenl R.P.: An improved Monte Cario faclorizalion algorilhm. BIT, 1980, 20, s. 176-184.

3.    Brent R.P., Pollard J.M.: Faclorization of the cight Fermat number. Math. Comp., 1981,36, 1627-630.

4.    Guy R.K.: How lo faclor a number. Proc. Sth Manitoba Conference on Numerical Mathema-tics, 1975, s. 49-89.

5.    Pollard J.M.: A Monte Carlo method for faclorization. BIT, 1975, 15, s. 331-334.

5.3. Metoda faktoryzacji Fermata i bazy rozkładu

Metoda faktoryzacji Fermata. Jak już widzieliśmy wcześniej (por. ćwiczenie 3 w podrozdziale 1.2 i ćwiczenie 4 w podrozdziale 4.2), istnieje efektywna metoda rozkładu na czynniki pierwsze liczb złożonych będących iloczynem dwóch bliskich siebie liczb pierwszych. Ta metoda, zwana „metodą Fermata”, jest oparta na tym, że liczba n jest wtedy różnicą dwóch kwadratów, z których jeden jest bardzo mały.

Twierdzenie 5.3.1. Niech n będzie dodatnią liczbą nieparzystą. Istnieje wtedy wzajemnie jednoznaczna odpowiedniość między rozkładami liczby n na iloczyn postaci n = ab, gdzie a > b > 0, a rozkładami n na różnicę kwadratów postaci t² — s², gdzie tissą liczbami całkowityminieujemnymi. Tę odpowiedniość określają równości:

t =

a + b 2

a — b 2

a -1 + s,

b — t —

Dowód. Jeśli dany jest taki rozkład liczby n na czynniki, to możemy liczbę n zapisać w postaci n = ab — ((a + 6)/2)² — ((a — b)/2)², czyli w postaci różnicy dwóch kwadratów. Na odwrót, jeśli n = t² — s², to prawą stronę możemy

rozłożyć na czynniki postaci (/ + .»)(/ — s). Równości w tezie twierdzenia dokładnie opisują tę wzajemnie jednoznaczna od po wi ed ni ość między rozkładami obu rodzajów.

Jeśli n — aś i liczby a i b są bliskie siebie, to liczba 5 = (a — b)j2 jest mała, a więc liczba / jest tylko niewiele większa od Jn . W takim przypadku możemy znaleźć liczby a i b, próbując kolejnych wartości /, począwszy od [>/n ] 4- 1, aż znajdziemy taką wartość, dla której liczba t² — n = s^x jest pełnym kwadratem.

W dalszym ciągu będziemy zakładać, że liczba n nie jest pełnym kwadratem, by nie zajmować się trywialnymi wyjątkami w opisywanych procedurach i stwierdzeniach.

Przykład 1. Rozłóżmy na czynniki liczbę 200819.

Rozwiązanie. Mamy [>/200819 ] -t- I =449. Wtedy liczba 449² — 200819 = = 782 nie jest pełnym kwadratem. Próbujemy więc t = 450: 450² — 200819 = = 1681 = 41². Zatem 200819 = 450² - 41² = (450 + 41)(450 - 41) = 491-409.

Zauważmy, że jeśli dla żadnego rozkładu n = ab liczby a i b nie są bliskie siebie, to wprawdzie metoda faktoryzacji Fermata da w wyniku liczby a i b, ale będzie wymagała sprawdzenia dużej liczby wartości t = [yjn ] 4 1, [yjn ] + 2, ... Pewne uogólnienie metody faktoryzacji Fermata często działa lepiej w takich sytuacjach. Wybieramy małą liczbę k i kolejno badamy / = [y/krt ] 4- 1, [y/kn ] 4- 2 itd., tak długo, aż znajdziemy taką liczbę /, dla której liczba t² — kn = s^z jest pełnym kwadratem. Wtedy (/ 4 s)(t — 5) = kn, więc liczba t 4- s ma nietrywialny wspólny dzielnik z n i możemy go znaleźć, obliczając NWD(t 4- s, ń).

Przykład 2. Rozłóżmy na czynniki liczbę 141467.

Rozwiązanie. Jeśli spróbujemy metody Fermata, to szybko znudzimy się bada-niem kolejnych liczb t = 377, 378, ... Jednakże, jeśli przyjmiemy t = [>/3n ] -t-4 1 = 652, ..., to szybko przekonamy się, że 655² — 3 • 141467 = 68². Wtedy obliczymy NWD{655 4- 68,    141467) = 241 i stwierdzimy, że 141467 =

= 241 • 587. Powodem, dla którego działała uogólniona metoda Fermata dla k = 3, jest to, że istnieje rozkład n = ab, w którym liczba b jest bliska 3a. Dla k — 3 musieliśmy próbować tylko czterech różnych wartości t, podczas gdy zwykła metoda Fermata (tzn. dla k = 1) wymagałaby aż trzydziestu ośmiu wartości /.

Bazy rozkładu. Pewne uogólnienie pomysłu, na którym oparta jest metoda faktoryzacji Fermata, prowadzi do znacznie bardziej efektywnej metody