Sito kwadratowe

Ten artykuł od 2021-11 wymaga zweryfikowania podanych informacji. Należy podać wiarygodne źródła w formie przypisów bibliograficznych. 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 ${\displaystyle n.}$

1. Szukamy par ${\displaystyle (a_{i},b_{i}),}$ takich, że:
   • ${\displaystyle a_{i}^{2}\equiv b_{i}\,(\operatorname {mod} n),}$
   • ${\displaystyle b_{i}}$ rozkłada się w „bazie czynników” (inaczej „bazie rozkładu”).
2. Znajdujemy pary ${\displaystyle (a_{i_{1}},b_{i_{1}}),(a_{i_{2}},b_{i_{2}}),...(a_{i_{k}},b_{i_{k}}),}$ takie, że:
   • ${\displaystyle a=\prod _{j=1...k}a_{i_{j}},}$
   • ${\displaystyle b=\prod _{j=1...k}b_{i_{j}}=c^{2}}$ dla pewnego ${\displaystyle c.}$
3. Wtedy ${\displaystyle a^{2}\equiv c^{2},}$ więc jeśli ${\displaystyle a\not \equiv \pm c,}$ to ${\displaystyle \operatorname {NWD} \,(a+c,n)}$ jest nowym dzielnikiem liczby ${\displaystyle n.}$

Szukanie par

Niech

${\displaystyle m=\lfloor {\sqrt {n}}\rfloor }$

i

${\displaystyle W(x)=(x+m)^{2}-n.}$

Dla ${\displaystyle x=0,\pm 1,\pm 2,...}$ liczymy:

${\displaystyle a_{i}=x+m,}$

${\displaystyle b_{i}=W(x)=(x+m)^{2}-n,}$

wtedy

${\displaystyle b_{i}\equiv a_{i}^{2}.}$

Z wygenerowanych w ten sposób par należy brać te, dla których ${\displaystyle b_{i}}$ rozkłada się w bazie rozkładu.

Można też zauważyć, że jeśli

${\displaystyle p\mid b_{i},}$

to

${\displaystyle (x+m)^{2}\equiv n\,(\operatorname {mod} p),}$

więc ${\displaystyle n}$ musi być resztą kwadratową modulo ${\displaystyle p}$ (wystarczy do bazy czynników brać tylko takie ${\displaystyle p}$).

Inne wersje

Istnieją dwie szybsze wersje tego algorytmu występujące pod nazwami:

1. Wielokrotnie wielomianowe sito kwadratowe (ang. Multiple Polynomial Quadratic Sieve).
2. 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