67500 Str093

182    5. Lic*by plofwwe i roikład im czynniki

oraz p, - •- 0, ⁿ następnie badamy losowe b_t tak długo, aż uzbieramy sporo /Miczb. Inna metoda polega na tym, że najpierw wybieramy pewną liczbę liczb b_t takich, że bezwzględnie najmniejsza reszta bf mod n ma małą wartość bezwzględną (np. wybieramy bliskie yjktt dla małych wielokrotności kn\ inny sposób zostanie pokazany w podrozdziale 5.4). Wtedy jako B bierzemy zbiór składający się z niewielkiej liczby liczb pierwszych (oraz jak zwykle /?, = ~ I) taki, że wiele spośród wybranych bezwzględnie najmniejszych reszt bf mod n rozkłada się na iloczyn liczb ze zbioru B.

Przykład 6. W sytuacji z przykładów 4-5 wybraliśmy liczby 67 i 68 dlatego, że są one bliskie ^4633. Po stwierdzeniu, że 67² = —144 (mod 4633) oraz 68² s —9 (mod 4633), mogliśmy wybrać B = {-1, 2, 3}. Jak widzieliśmy już wcześniej, wektorami odpowiadającymi liczbom 67 i 68 są odpowiednio (1,0,0) i (1,0,0), których suma jest wektorem zerowym. Obliczamy 6 = 67 • 68 mod A633 = —77 i c = 2^Ył • 3^,ł (przy obliczaniu c możemy pominąć potęgę — 1), tzn. c = 36. Na szczęście -77 ^ ±36 (mod 4633), a więc możemy znaleźć szukany dzielnik, obliczając NWD(-11 + 36,4633) = 41.

Kiedy możemy być pewni, że mamy wystarczająco wiele liczb b_t, by wśród odpowiadających im wektorów c_; znaleźć takie, których suma jest wektorem zerowym? Inaczej mówiąc, jeśli mamy zbiór wektorów w przestrzeni Fj, to kiedy możemy być pewni, że sumą pewnego podzbioru tego zbioru jest wektor zerowy? Jest to pytanie o to, kiedy zbiór wektorów jest liniowo zależny nad ciałem F₂. Z elementarnych twierdzeń algebry liniowej (prawdziwych również w przypadku ciała F₂, a nie tylko ciała liczb rzeczywistych) wynika, że wystarczy mieć h + 1 wektorów. Zatem, w najgorszym przypadku, będziemy musieli wygenerować h 4- 1 różnych 5-liczb, by znaleźć pierwszy przykład kon-

gruencji    (mod ń). (W przykładzie 6 jest pokazane, że mo

żemy znaleźć wektory liniowo zależne wcześniej; w tym przypadku h = 3 i mogliśmy poprzestać na dwóch ^-wektorach.) Jeśli liczba h jest duża, to możemy mieć trudności z zauważeniem, które wektory dają w sumie wektor zerowy; w takim przypadku zapisujemy wektory jako wiersze pewnej macierzy i stosujemy znane z algebry liniowej metody eliminacji, by znaleźć liniowo zależny zbiór wierszy.

Przykład 7. Niech n == 4633. Znajdźmy najmniejszą bazę rozkładu B taką, że liczby 68, 69 i 96 są ZMiczbami, a następnie rozłóżmy liczbę 4633 na czynniki.

Rozwiązanie. Jak już widzieliśmy przedtem, liczby 68² mod n oraz 69² mod n są iloczynami liczb —1, 2 i 3; ponieważ 96² mod n — —50, to bezwzględnie najmniejsze reszty tych trzech kwadratów są iloczynami liczb z bazy rozkładu B = { — 1, 2, 3, 5}. Wyznaczyliśmy już wektory e_A = (1,0,0,0) i e₂ = (0,1,0,0),

odpowiadające liczbom 68 i 69. Ponieważ 96² •= — 50 (mod 4633), więc «₃ = (1,1,0,0). Suma tych trzech wektorów jest wektorem zerowym, a więc możemy przyjąć b = 68 69 • 96 == 1031 (mod 4633) i c = 2⁴ • 3 * 5 =* 240. Wreszcie otrzymamy NWD{240 4- 1031, 4633) = 41.

W przykładach 6 i 7 widzieliśmy, w jaki sposób możemy postępować, by znaleźć wiele b_t takich, że bezwzględnie najmniejsze reszty bf mod n są iloczynami małych liczb pierwszych. Prawdopodobieństwo tego, że bf mod n jest iloczynem małych liczb pierwszych, jest tym większe, im mniejsza jest wartość bezwzględna tej reszty. Zatem możemy kolejno próbować liczb b_t bliskich y/iTn dla małych liczb k. Możemy na przykład wybrać [^/śn] i [>/kn 1-4-1 dla k = 1, 2, ....

Przykład 8. Rozłóżmy na czynniki liczbę n — 1829, wybierając jako liczby b_t takie liczby całkowite postaci [-J1829A: ] i [_>/l829A: ] + 1 dla k = 1, 2, ..., że bf mod n jest iloczynem liczb pierwszych mniejszych od 20. Dla takiej liczby b_i piszemy bf mod n —    a następnie wykładniki a_tJ zapisujemy w tablicy.

i

wchodzi w rozkład bf mod n i bi -1	na czynniki pierwsze: 2 3 5 7				n	13
42 1	—	—	1	—	—	1
43	2	—	1	—	B	—
61	—	2		1	—	—
74 1	—	—	• —	—	i	—
85 1	— •	—	Ujlg	i	—	1
86	4	-	i	-	—	-
Szukamy teraz takiego zbioru	wierszy	tej tablicy, że sumy wyrazów

gólnych kolumnach są parzyste. Widać od razu, że wiersze drugi i szósty dają

w sumie — 6 — 2---. Prowadzi to do kongruencji (b₂ • b₆)² = (2^6/2 • S²*²)²

(mod n), czyli (43 * 86)² = 40² (mod 1829). Ale ponieważ 43 • 86 = 40 (mod 1829), otrzymana zależność jest trywialna. Musimy poszukać zatem innego zbioru wierszy, które w sumie dadzą wiersz złożony z liczb parzystych. Zauważamy, że suma pierwszych trzech wierszy i wiersza piątego wynosi 2 2 2 2 2 — 2, co daje kongruencję (42 -43-61 • 85)² = (2 - 3 • 5 • 7 - 13)² (mod «), czyli 1459² = 901² (mod 1829). Wynika stąd, że dzielnikiem liczby 1829 jest NW£)(1459 -+- 901, 1829) = 59.

Dla k = 1, 2, 3, 4 otrzymujemy następującą tablicę, w której liczba u góryy-tej kolumny to p_Jy a liczba w /-tym wierszu pod p_t jest wykładnikiem, z którym pj

Algorytm baz rozkładu. Jako podsumowanie opiszemy teraz metodę rozkładania bardzo dużych liczb n na czynniki pierwsze, w której wykorzystuje