Numerická metoda Quadratic Sieve

Numerická metoda Quadratic Sieve (česky někdy překládáno jako kvadratické síto) je efektivní algoritmus pro faktorizaci přirozených čísel (tj. hledání rozkladu čísla na součin prvočísel). Jedná se o nejefektivnější algoritmus pro čísla cca do 110 dekadických cifer. Dříve se využíval při kryptoanalýze RSA šifry (dnes se pro tyto účely využívá také jako doprovodný algoritmus metody GNFS). Metoda vychází z Dixonovy metody náhodných čtverců, vylepšuje ji ve způsobu výběru čísel. Obě metody potom hledají čísla použitelná pro Fermatovu faktorizační metodu.

Fermatova faktorizační metoda

Předpokládejme dále, že chceme provést faktorizaci přirozeného čísla n. Metoda funguje na jednoduchém principu, předpokládejme, že se nám podaří nalézt čísla x, y taková, že:

x ≢ y (mod n), ale zároveň: x² ≡ y² (mod n)

Pak pro tato čísla existuje pravděpodobnost 2/3, že výraz NSD(x + y, n) či NSD(x - y, n), kde NSD značí nejvyššího společného dělitele, bude netriviální dělitel čísla n (tj. takový dělitel, který není roven číslu 1, nebo právě n).

Dixonova metoda náhodných čtverců

Anglicky Dixon's random squares method. Tato metoda pracuje s faktorovu základnou F, kterou tvoří r prvočísel (většinou prvních r prvočísel):

F = {p₁, p₂, ..., p_r}

Předpokládáme pro jednoduchost, že množina je uspořádaná právě v tomto pořadí. Následně se pracuje s číslem s, které je rovné odmocnině z r zaokrouhlené nahoru (tj. z tzv. horní celou částí odmocniny z r):

s = ⌈ √n ⌉

Nyní probíhá faktorizace v následujících krocích:

1. Generujeme náhodně čísla x_i v intervalu s až n taková, že pro ně hodnota y_i:

   y_i = x_i² mod n

   je hladká nad F (tj. všechny prvočísla rozkladu y_i jsou obsažena v F). Exponenty rozkladu na prvočísla v F uložíme do matice M tak, že sloupečky matice představují příslušná prvočísla v F, pro které ukládáme exponenty (v i-tém řádku jsou tedy uloženy příslušné exponenty rozkladu y_i). Pokud číslo y_i není hladké nad F zahazujeme jej a zkoušíme dál.

2. Takových prvočísel musíme nalézt alespoň (r + 1), na konci máme množinu dvojic:

   {(x_i, y_i), i = {1, 2, ..., r + 1} }

   a matice M má právě (r + 1) řádků.

3. Nyní vypočítáme matici P jako:

   P = (M mod 2)^T

   kde T značí transponování matice (tj. z řádků se stanou sloupečky). Dále spočteme nulový prostor této matice v Z₂. Nulový prostor se získá pomocí Gaussovy eliminace, v podstatě nám dává návod, které sloupcové vektory brát (pro ně je příslušná část vektoru 1) a které nikoli (zde je 0). Řekněme, že prvek nulového prostoru matice (vektor v) má následující tvar:

   v=(e₁, e₂, ..., e_r+1)

   kde e_i má hodnotu 0 nebo 1.

4. Naši kongruenci tvaru x² ≡ y² (mod n) získáme dosazením do:

   x² ≡ ∏_{i ∈ {1, 2, ..., r + 1}} (x_i^e_i)² ≡ ∏_{i ∈ {1, 2, ..., r + 1}} (y_i^e_i) ≡ y²

5. Spočteme výraz NSD(x + y, n) a NSD(x - y, n) a vyzkoušíme, zdali není roven hledaném děliteli n, pokud nikoli, vše se opakuje od počátku.

Quadratic Sieve

Vylepšení od Dixonovy metody náhodných čtverců je především v tom, že nebere všechna čísla v intervalu s až n, ale pouze čísla minimálně vzdálená od s.