GNFS
Z Wikipedii
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. Kolejną liczbą za rozłożenie, której wyznaczono nagrodę jest RSA-704.
[edytuj] Działanie algorytmu
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 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 n1/d, gdzie d jest pewną stałą większą od 1. Wymaga jednak dodatkowych obliczeń i faktoryzacji w ciele liczbowym, co sprawia że ten algorytm jest znacznie bardziej skomplikowany niż zwykłe sito liczbowe.
