Metoda sita liczbowego


Metoda sita liczbowego w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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.

Spis treści

Metoda | edytuj kod

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

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

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

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

Przykład | edytuj kod

Szukany jest rozkład na czynniki pierwsze n = 35. {\displaystyle n=35.} Ustalona została baza czynników P = { 2 , 3 , 11 , 13 , 17 , 19 } {\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 P {\displaystyle P} nie ma czynników liczby n , {\displaystyle n,} to następuje losowanie wartości z , {\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):

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 4 7 : {\displaystyle 2\cdot 4\cdot 7{:}} ten iloczyn upraszcza się do 3 2 2 2   19 2 , {\displaystyle 3^{2}\equiv 2^{2}\ 19^{2},} lub 3 2 38 2 . {\displaystyle 3^{2}\equiv 38^{2}.} Wynikową faktoryzacją jest

35 = NWD ( 38 3 , 35 ) NWD ( 38 + 3 , 35 ) = 35 1. {\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.

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

35 = NWD ( 6 1 , 35 ) NWD ( 6 + 1 , 35 ) = 5 7. {\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. 3 5 {\displaystyle 3\cdot 5} i 2 6. {\displaystyle 2\cdot 6.}

Ograniczenia algorytmu | edytuj kod

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

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

Bibliografia | edytuj kod

  • 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.
Na podstawie artykułu: "Metoda sita liczbowego" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy