Sito kwadratowe

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

AlgorytmEdytuj

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

  1. Szukamy par   takich że:
    •  
    •   rozkłada się w „bazie czynników” (inaczej „bazie rozkładu”).
  2. Znajdujemy pary   takie że:
    •  
    •   dla pewnego  
  3. Wtedy   więc jeśli   to   jest nowym dzielnikiem liczby  

Szukanie parEdytuj

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 wersjeEdytuj

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). Inne algorytmy faktoryzacyjne zostały wyparte przez dwie wyżej wymienione modyfikacje.