GNFS: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
int. |
→Działanie algorytmu: int. |
||
Linia 7:
:<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ż==
| |||