GNFS: Różnice pomiędzy wersjami

'''Ogólne sito ciała liczbowego''' ('''GNFS''', [[Język angielski|ang.]] '''general 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.

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

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ę [[liczba gładka|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''^1/''d'', gdzie ''d'' jest pewną stałą większą od 1. Wymaga jednakto dodatkowych obliczeń i faktoryzacji w [[ciało liczbowe|ciele liczbowym]], co sprawia że ten algorytm jest znacznie bardziej skomplikowany niż zwykłe sito liczbowe.