Metoda sita liczbowego

Metoda sita liczbowego (Szablon:Ang.) – algorytm rozkładu liczb na czynniki pierwsze. Jest uproszczoną wersją algorytmu GNFS, znacznie mniej efektywną od pełnej wersji. Mimo niepraktyczności jest jednak znacznie prostszy od ogólnej wersji i jego zrozumienie jest przydatne przed opanowaniem zasady działania GNFS.

Metoda

Chcąc znaleźć czynniki liczby złożonej $n,$ należy wybrać granicę $B$ i określić bazę czynników $(P),$ zawierającą wszystkie liczby pierwsze mniejsze niż $B.$ Następnie trzeba wyszukać liczby naturalne $z,$ takie że zarówno $z,$ jak i $z+n$ są B-gładkie (ich czynniki pierwsze są nie większe niż $B$). Każda taka liczba definiuje pewną relację modulo $n,$ pomiędzy elementami $P,$ w postaci:

$\prod _{p_i\in P}{p}_i^{a_i}\equiv \prod _{p_i\in P}{p}_i^{b_i}(\mathrm{mod}n)$

(gdzie $a_i$ i $b_i$ są pewnymi nieujemnymi liczbami całkowitymi).

Kiedy zostanie wyszukanych wystarczająco wiele takich relacji (zwykle oznacza to, że trzeba znaleźć ich więcej niż jest elementów w $P$), można znaleźć wśród nich podzbiór, którego pomnożenie da parzyste wykładniki po obu stronach równości. Pozwala to otrzymać relację postaci $a^2\equiv b^2(\mathrm{mod}n),$ które można przekształcić na faktoryzację:

$n=\mathrm{NWD}(a-b,n)\cdot \mathrm{NWD}(a+b,n).$

Otrzymana faktoryzacja może być trywialna np. $n=n\cdot 1$ – w takim wypadku szukamy innej kombinacji relacji. Po znalezieniu pierwszej nietrywialnej kombinacji algorytm kończy działanie.

Przykład

Szukany jest rozkład na czynniki pierwsze $n=35.$ Ustalona została baza czynników $P=\{2,3,11,13,17,19\}$ – nie może ona zawierać liczb 5 ani 7, gdyż są one dzielnikami 35. Gdyby się na takie natrafiło, reszta algorytmu nie byłaby potrzebna. Jeśli w zbiorze $P$ nie ma czynników liczby $n,$ to następuje losowanie wartości $z,$ aż zbierze się wystarczającą ich ilość. W tym przypadku wylosowano liczby 1, 3, 4, 9, 13, 19 i 22. W rezultacie otrzymuje się następujące relacje (mod 35):

2030110130190 =  1 ≡ 36 = 2232110130190.............(1)

2031110130190 =  3 ≡ 38 = 2130110130191.............(2)

2230110130190 =  4 ≡ 39 = 2031110131190.............(3)

2032110130190 =  9 ≡ 44 = 2230111130190.............(4)

2030110131190 = 13 ≡ 48 = 2431110130190.............(5)

2030110130191 = 19 ≡ 54 = 2133110130190.............(6)

2130111130190 = 22 ≡ 57 = 2031110130191.............(7)

Można teraz na różne sposoby połączyć je, tak aby uzyskać parzyste wykładniki:

$2\cdot 4\cdot 7:$ ten iloczyn upraszcza się do $3^2\equiv 2^{2}19^2,$ lub $3^2\equiv 38^2.$ Wynikową faktoryzacją jest

$35=\mathrm{NWD}(38-3,35)\cdot \mathrm{NWD}(38+3,35)=35\cdot 1.$

Jest ona trywialna, więc należy szukać dalej.

$1:$ to sprowadza się do $6^2\equiv 1^2,$ co daje faktoryzację

$35=\mathrm{NWD}(6-1,35)\cdot \mathrm{NWD}(6+1,35)=5\cdot 7.$

Czynniki zostały znalezione!

Należy zauważyć, że nie zostały użyte inne potencjalne kombinacje, jak np. $3\cdot 5$ i $2\cdot 6.$

Ograniczenia algorytmu

Algorytm ten, podobnie jak GNFS, nie może znaleźć czynników dla liczb postaci $p^m,$ gdzie $p$ jest liczbą pierwszą, a $m$ jest całkowite. Nie jest to jednak duży problem, ponieważ można szybko sprawdzić czy $n$ jest tej postaci.

Większym problemem jest znalezienie wystarczającej liczby potrzebnych wartości $z.$ Dla danego $B,$ liczby $B$-gładkie stają się bardzo rzadkie wraz ze wzrostem $n.$ Jeśli zaczyna się od $n$ mającego ponad 100 cyfr, znalezienie choć jednej takiej liczby jest praktycznie niemożliwe. Przewaga GNFS tkwi w tym, że szuka on liczb gładkich nie rzędu $n,$ ale rzędu $n^{1/d}$ dla pewnej liczby $d$ (zwykle 3 albo 5).

Bibliografia

• A.K. Lenstra, H.W. Lenstra, Jr., M.S. Manasse, J.M. Pollard, The Factorization of the Ninth Fermat Number, „Math. Comp.” 61 (1993), s. 319–349. A draft is available at www.std.org/~msm/common/f9paper.ps.
• A.K. Lenstra, H.W. Lenstra, Jr. (eds.) The Development of the Number Field Sieve, „Lecture Notes in Mathematics” 1554, Springer-Verlag, New York 1993.