Metoda sita liczbowego

(Przekierowano z Sito liczbowe)

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.

MetodaEdytuj

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

 

(gdzie   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  ), 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   które można przekształcić na faktoryzację:

 

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

PrzykładEdytuj

Szukany jest rozkład na czynniki pierwsze   Ustalona została baza czynników   – 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   nie ma czynników liczby   to następuje losowanie wartości   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:

  ten iloczyn upraszcza się do   lub   Wynikową faktoryzacją jest

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

  to sprowadza się do   co daje faktoryzację

 
Czynniki zostały znalezione!

Należy zauważyć, że nie zostały użyte inne potencjalne kombinacje, jak np.   i  

Ograniczenia algorytmuEdytuj

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

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

BibliografiaEdytuj

  • 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.