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

${\displaystyle \prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}\;(\operatorname {mod} n)}$

(gdzie ${\displaystyle a_{i}}$ i ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a^{2}\equiv b^{2}\;(\operatorname {mod} n),}$ które można przekształcić na faktoryzację:

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

Otrzymana faktoryzacja może być trywialna np. ${\displaystyle 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 ${\displaystyle n=35.}$ Ustalona została baza czynników ${\displaystyle 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 ${\displaystyle P}$ nie ma czynników liczby ${\displaystyle n,}$ to następuje losowanie wartości ${\displaystyle 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:

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

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

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

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

${\displaystyle 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. ${\displaystyle 3\cdot 5}$ i ${\displaystyle 2\cdot 6.}$

Ograniczenia algorytmu

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

Większym problemem jest znalezienie wystarczającej liczby potrzebnych wartości ${\displaystyle z.}$ Dla danego ${\displaystyle B,}$ liczby ${\displaystyle B}$-gładkie stają się bardzo rzadkie wraz ze wzrostem ${\displaystyle n.}$ Jeśli zaczyna się od ${\displaystyle 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 ${\displaystyle n,}$ ale rzędu ${\displaystyle n^{1/d}}$ dla pewnej liczby ${\displaystyle 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.