Wikipedia

GNFS: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
DodekBot (dyskusja | edycje)
80 710 edycji
Uzupełnienia na podstawie angielskiej Wiki
Linia 1:
'''GNFSOgólne sito ciała liczbowego''' ('''GNFS''', [[Język angielski|ang.]] '''general number field sieve)''' -) jest najszybszym obecnie najszybszymznanym [[algorytm|algorytmem]] [[faktoryzacja|faktoryzacji]] dużych (ponad 100-cyfrowych) liczb. ZnanyUżywając jesttego teżalgorytmu, podzespół nazwąz ogólnego[[Uniwersytet sitaw ciałaBonn|Uniwersytetu liczbowego.w ZostałBonn]] wykorzystany(wspólnie doz faktoryzacjikilkoma innymi instytutami) [[liczba|liczby3 grudnia]] RSA-567[[2003]] (numerrozłożył oznaczana ilośćczynniki pierwsze liczbę [[bit|bitówRSA-576]] potrzebnych(mającą do576 zapisaniabitów, tejczyli liczby - 193174 cyfry dziesiętne), przeza zespół[[2 składającylistopada]] się[[2005]] międzyrozłożył innymiliczbę z[[RSA-640]] naukowców(mającą z193 Scientificcyfry Computingdziesiętne). InstitutePierwsze iobliczenie Purewymagało Mathematicsokoło Institute3 zmiesięcy [[Niemcy|Niemiec]]pracy, oraza Nationaldrugie Researchokoło Institute5 formiesięcy. MathematicsKolejną andliczbą Computerza Sciencerozłożenie zktórej [[Holandia|Holandii]].wyznaczono Zespółnagrodę złamałjest [[szyfrRSA-704]] używając około 100 maszyn w czasie nieco ponad 3 miesiące.
 
== Działanie algorytmu ==
{{Matematyka stub}}▼
 
[[Złożoność obliczeniowa|Złożoność]] algorytmu dla wejściowego ''n'' można opisać wzorem:
[[Kategoria:Algorytmy]]▼
 
:<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ę [[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''<sup>1/''d''</sup>, gdzie ''d'' jest pewną stałą większą od 1. Wymaga jednak 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ż==
* [[Sito kwadratowe]]
* [[RSA Factoring Challenge]]
▲{{Matematykainformatyka stub}}
 
▲[[Kategoria:Algorytmy teorioliczbowe]]
[[Kategoria:Kryptografia]]
 
[[de:Zahlkörpersieb]]
[[en:General number field sieve]]
[[fr:Algorithme de factorisation par crible sur les corps de nombres généralisé]]▼
[[fi:Yleinen lukukuntaseula]]
▲[[fr:Algorithme de factorisation par crible sur les corps de nombres généralisé]]
[[zh:普通数域筛选法]]
Źródło: „https://pl.wikipedia.org/wiki/GNFS”