Tekst źródłowy strony GNFS

'''Ogólne sito ciała liczbowego''' ('''GNFS''', [[Język angielski|ang.]] G''eneral Number Field Sieve'') jest najszybszym obecnie znanym [[algorytm]]em [[faktoryzacja|faktoryzacji]] dużych (ponad 100-cyfrowych) liczb. Używając tego algorytmu, zespół z [[Uniwersytet w Bonn|Uniwersytetu w Bonn]] (wspólnie z kilkoma innymi instytutami) [[3 grudnia]] [[2003]] rozłożył na czynniki pierwsze liczbę [[RSA-576]] (mającą 576 bitów, czyli 174 cyfry dziesiętne), a [[2 listopada]] [[2005]] rozłożył liczbę [[RSA-640]] (mającą 193 cyfry dziesiętne). Pierwsze obliczenie wymagało około 3 miesięcy pracy, a drugie około 5 miesięcy.

== Działanie algorytmu ==

[[Złożoność obliczeniowa]] algorytmu dla wejściowego ''n'' można opisać wzorem:

:<math>e^{ (c+o(1)) \,\cdot\, (\log n)^{\frac{1}{3}} \,\cdot\, (\log \log n)^{\frac{2}{3}} }</math>

dla pewnej stałej ''c'', zależącej od konkretnej implementacji. Zasada działania jest rozszerzeniem prostszego algorytmu [[sito liczbowe|sita liczbowego]]. Aby [[faktoryzacja|rozłożyć na czynniki pierwsze]] dużą liczbę ''n'' metodą sita liczbowego, szuka się [[Liczby gładkie|gładkich liczb]] (czyli mających wyłącznie małe dzielniki pierwsze) rzędu ''n''. Rzadkość występowania tych liczb sprawia jednak, że ta metoda nie jest zbyt efektywna. GNFS polega na szukaniu liczb gładkich rzędu ''n''<sup>1/''d''</sup>, gdzie ''d'' jest pewną stałą większą od 1. Wymaga to dodatkowych obliczeń i faktoryzacji w [[ciało liczbowe|ciele liczbowym]], co sprawia, że ten algorytm jest znacznie bardziej skomplikowany niż zwykłe sito liczbowe.

== Zobacz też ==
* [[RSA Factoring Challenge]]

{{Teoria liczb}}

[[Kategoria:Algorytmy faktoryzacji|GNFS]]