11291 Str103

202    5. Uefby plcrwm i rozkład na czynniki

Wreszcie powtarzamy tc same kroki dla l₂ ~ 1112 zamiast f, = 1318, tym razem kończąc na skokach co 243.

Po wykonaniu tej procedury dla każdej z pozostałych sześciu liczb pierwszych z naszej bazy rozkładu, otrzymujemy tablicę wykładników, wymiaru 500 x 8, w której każdy wiersz odpowiada jednej wartości l między 1021 i 1520. Wyrzucamy teraz wszystkie wiersze odpowiadające tym liczbom /, dla których liczba t³ — n nie została zredukowana do jedności w wyniku kolejnych dzieleń przez potęgi liczb pierwszych p podczas tworzenia tablicy. Zatem pozostawiamy tylko te wiersze, dla których liczba t² — n jest /Miczbą. W tym przykładzie dla liczby n = 1042387 otrzymamy następującą tablicę (puste miejsca oznaczają wykładniki równe zeru):

/	t^2-n	2	3	11	17	19	23	43	47
1021	54	1	3	. -	-				-r.
1027	12342	1	1	2	1		m ^!
1030	18513	• gi	2	2	1	19		Ul
1061	83334	1	1	PHI	1	i	Sg	1	-
1112	194157		5		1	• --.r	-		1
1129	232254	1	3	i	1	ŚltP	i	--	-
1148	275517	—	2	3	rjŁSi	'	i	888	n
1175	338238	1	2	-		1	i	i	-
1217	438702	1	1	1	2		i
1390	889713	SpA	2	2	-	1	- •	l	-■
1520	1268013	■jj ■ ■■	I	-	1		2	39	1

Powtarzając postępowanie z przykładu 9 w podrozdziale 5.3, szukamy, począwszy od góry, zależności modulo 2 między wierszami tej tablicy. To znaczy, szukamy zbioru wierszy, które po zsumowaniu kolumnami dadzą w każdej kolumnie liczbę parzystą. Pierwszy taki zbiór składa się z trzech pierwszych wierszy, jego suma jest podwojonym wierszem 1321----. Stąd otrzymuje

my kongruencję

(1021 • 1027 • 1030)² = (2 • 3³ • ll² • 17)² (mod 1042387).

Jednak pomimo że udało się nam tak szybko znaleźć zbiór wierszy liniowo zależnych modulo 2, nie udało się nam do końca: oba kwadraty po dwóch stronach tej kongruencji przystają do tej samej liczby 111078 modulo 1042387, a więc otrzymujemy trywialny rozkład. Kiedy będziemy przeglądać dalej naszą tablicę, znajdziemy kilka innych zbiorów liniowo zależnych wierszy, które jednak też nie dadzą nam uietrywialnego rozkładu. Wreszcie, kiedy już jesteśmy prawie gotowi, by poddać się - i wybrać na nowo większy zbiór A - zauważamy, że ostatni wiersz - odpowiadający ostatniej spośród naszych liczb t - jest liniowo zależny od poprzednich wierszy. Dokładniej, jest on równy modulo 2 piątemu wierszowi. To daje nam kongruencję

(1112 • 1520)² = (3³ ' 17'23 47)² (mod 1042387),

czyli

647853 ² = 496179² (mod 1042387),

skąd otrzymujemy nietrywialny dzielnik

NWD(641?>5?, - 496179, 1042387) = 1487.

Opierając się na pewnych nie udowodnionych, ale bardzo prawdopodobnych hipotezach, można pokazać, źe oczekiwany czas działania metody sita kwadratowego rozkładu na czynniki wynosi asymptotycznie

dla dowolnego e > 0. Wymaga ona też dość dużo pamięci, również rzędu exp(C Vl°gⁿ loglog n ). Szczegółowe omówienie wymagań czasowych i pamięciowych metody sita kwadratowego (a także kilku innych metod) rozkładu na czynniki znajduje się w artykule Pomerance’a zawartym w tomie Computation Methods in Number Theory.

Sito ciał liczbowych. Do niedawna wszystkie konkurujące ze sobą najlepsze algorytmy rozkładu dowolnych liczb całkowitych na czynniki miały czas działania postaci

exp(0(Vlog/i loglog n )).

Niektórzy specjaliści uważali nawet, że ta funkcja zmiennej n może być naturalnym ograniczeniem dolnym tego czasu działania. Jednakże w ciągu ostatnich paru lat została opracowana nowa metoda - nazywana sitem ciał liczbowych — mająca znacznie lepszy (asymptotycznie) heurystyczny czas działania, mianowicie

exp (O ((log ń)^1/3 (log log ń) ^2/3)>.

W praktyce okazuje się ona najszybszą metodą rozkładu na czynniki liczb, które są na granicy lub poza granicą aktualnych (1994 r.) możliwości rozkładu, tzn. mających więcej niż 150 cyfr.

Pod pewnymi względami algorytm sita dał liczbowych rozkładu na czynniki jest podobny do wcześniejszych algorytmów, które próbowały tworzyć kongruencję postaci x² = y² (mod n). Jednakże ta metoda korzysta z „bazy rozkładu” w pierścieniu liczb całkowitych pewnego odpowiednio dobranego algebraicznego ciała liczbowego. Zatem obok podstawowego mechanizmu sita kwadratowego, ta metoda rozkładu korzysta z algebraicznej teorii liczb. Jest to przypuszczalnie najbardziej skomplikowany znany algorytm rozkładu. Podamy tylko ogólny zarys tego algorytmu.