GNFS

Ogólne sito ciała liczbowego (GNFS, ang. General Number Field Sieve) jest najszybszym obecnie znanym algorytmem faktoryzacji dużych (ponad 100-cyfrowych) liczb. Używając tego algorytmu, zespół z 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:

$e^{(c+o(1))\,\cdot \,(\log n)^{\frac {1}{3}}\,\cdot \,(\log \log n)^{\frac {2}{3}}}$

dla pewnej stałej c, zależącej od konkretnej implementacji. Zasada działania jest rozszerzeniem prostszego algorytmu sita liczbowego. Aby rozłożyć na czynniki pierwsze dużą liczbę n metodą sita liczbowego, szuka się 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 to dodatkowych obliczeń i faktoryzacji w ciele liczbowym, co sprawia, że ten algorytm jest znacznie bardziej skomplikowany niż zwykłe sito liczbowe.

Zobacz też

• RSA Factoring Challenge