Sito kwadratowe
Ten artykuł od 2021-11 wymaga zweryfikowania podanych informacji. |
Sito kwadratowe (ang. Quadratic Sieve) – najszybszy znany algorytm do faktoryzacji liczb, które są krótsze niż 110 cyfr dziesiętnych.[1]
Algorytm[edytuj | edytuj kod]
Algorytm ten jest ukonkretnieniem metody sita liczbowego. Załóżmy, że szukamy czynników liczby
- Szukamy par takich, że:
- rozkłada się w „bazie czynników” (inaczej „bazie rozkładu”).
- Znajdujemy pary takie, że:
- dla pewnego
- Wtedy więc jeśli to jest nowym dzielnikiem liczby
Szukanie par[edytuj | edytuj kod]
Niech
i
Dla liczymy:
wtedy
Z wygenerowanych w ten sposób par należy brać te, dla których rozkłada się w bazie rozkładu.
Można też zauważyć, że jeśli
to
więc musi być resztą kwadratową modulo (wystarczy do bazy czynników brać tylko takie ).
Inne wersje[edytuj | edytuj kod]
Istnieją dwie szybsze wersje tego algorytmu występujące pod nazwami:
- Wielokrotnie wielomianowe sito kwadratowe (ang. Multiple Polynomial Quadratic Sieve).
- Wielokrotnie wielomianowe sito kwadratowe dla podwójnie dużych liczb pierwszych (ang. Double Large Prime Variation of the Multiple Polynomial Quadratic Sieve).
Obecnie najszybszym algorytmem faktoryzacyjnym dla liczb o większych długościach jest algorytm GNFS (ang. General Number Field Sieve; ogólne sito ciała liczbowego)[2]. Inne algorytmy faktoryzacji zostały wyparte przez dwie wyżej wymienione modyfikacje.
Przypisy[edytuj | edytuj kod]
- ↑ The Quadratic Sieve Factoring Algorithm [online] [dostęp 2023-07-07] (ang.).
- ↑ Carl Pomerance , A Tale of Two Sieves [online] [dostęp 2023-07-07] (ang.).