Sito kwadratowe
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
Sito kwadratowe (ang. Quadratic Sieve) – najszybszy znany algorytm do faktoryzacji liczb, które są krótsze niż 110 cyfr dziesiętnych.[1]
Algorytm
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
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
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
- p
- d
- e
ogólne typy liczb |
| ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
relacje |
| ||||||||||
działania | |||||||||||
liczby pierwsze |
| ||||||||||
równania diofantyczne |
| ||||||||||
twierdzenia arytmetyki modularnej |
| ||||||||||
inne zagadnienia | |||||||||||
twierdzenia limitacyjne |