Sito kwadratowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Sito kwadratowe (ang. Quadratic Sieve) to najszybszy znany algorytm do faktoryzacji liczb, które są krótsze niż 150 cyfr dziesiętnych.


Algorytm[edytuj | edytuj kod]

Algorytm ten jest ukonkretnieniem metody sita liczbowego. Załóżmy, że szukamy czynników liczby n.

  1. Szukamy par ({a_i}, {b_i}) , takich że:
    •  {a_i}^2 \equiv {b_i} (\text{mod } n)
    • bi rozkłada się w "bazie czynników" (inaczej "bazie rozkładu")
  2. Znajdujemy pary  ({a_{i_1}}, {b_{i_1}}), ({a_{i_2}}, {b_{i_2}}), ... ({a_{i_k}}, {b_{i_k}}) , takie że:
    •  a = \prod_{j = 1..k} {a_{i_j}}
    •  b = \prod_{j = 1..k} {b_{i_j}} = c^2 dla pewnego c
  3. Wtedy  a^2 \equiv c^2 więc jeśli  a \not\equiv \pm c to NWD(a+c, n) jest nowym dzielnikiem liczby n.

Szukanie par[edytuj | edytuj kod]

Niech

 m = \lfloor\sqrt{n}\rfloor

i

 W(x) = (x + m)^2 - n

Dla  x = 0, \pm 1, \pm 2, ... liczymy:

{a_i} = x + m
{b_i} = W(x) = (x+m)^2 -n

wtedy

{b_i} \equiv {a_i}^2

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

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

 p \mid {b_i}

to

 (x+m)^2 \equiv n (\text{mod } p)

więc n musi być resztą kwadratową modulo p (wystarczy do bazy czynników brać tylko takie p)

Inne wersje[edytuj | edytuj kod]

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 NFS (ang. Number Field Sieve; Sito ciała liczbowego). Inne algorytmy faktoryzacyjne zostały wyparte przez dwa wyżej wymienione algorytmy.