Metoda sita liczbowego

Metoda sita liczbowego (ang. Rational Sieve) – 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}}\;(\operatorname {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}\;(\operatorname {mod} n),$ które można przekształcić na faktoryzację:

$n=\operatorname {NWD} \,(a-b,n)\cdot \operatorname {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):

2⁰3⁰11⁰13⁰19⁰ =  1 ≡ 36 = 2²3²11⁰13⁰19⁰.............(1)

2⁰3¹11⁰13⁰19⁰ =  3 ≡ 38 = 2¹3⁰11⁰13⁰19¹.............(2)

2²3⁰11⁰13⁰19⁰ =  4 ≡ 39 = 2⁰3¹11⁰13¹19⁰.............(3)

2⁰3²11⁰13⁰19⁰ =  9 ≡ 44 = 2²3⁰11¹13⁰19⁰.............(4)

2⁰3⁰11⁰13¹19⁰ = 13 ≡ 48 = 2⁴3¹11⁰13⁰19⁰.............(5)

2⁰3⁰11⁰13⁰19¹ = 19 ≡ 54 = 2¹3³11⁰13⁰19⁰.............(6)

2¹3⁰11¹13⁰19⁰ = 22 ≡ 57 = 2⁰3¹11⁰13⁰19¹.............(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=\operatorname {NWD} \,(38-3,35)\cdot \operatorname {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=\operatorname {NWD} \,(6-1,35)\cdot \operatorname {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.