Quadratic Sieve
Das Quadratische Sieb findet x mit x^2≡y^2 (mod n), sodass ggT(x±y,n) einen Faktor offenlegen kann; es ist die schnellste Faktorisierungsmethode unter 100 Stellen.
Zweck
Ganzzahlen mittlerer Größe (~100 Stellen) so schnell wie möglich faktorisieren.
Mechanismus
Man sucht viele x_i, sodass x_i^2 mod n B-glatt ist, und kombiniert sie per linearer Algebra über GF(2), sodass das Produkt der Quadrate eine perfekte Quadratzahl wird. Die Kombination liefert X^2≡Y^2 (mod n), und ggT(X±Y,n) kann nichttrivial sein.
Anwendungsfälle
- Ganzzahlfaktorisierung
- Kryptoanalyse
- Zahlentheoretische Algorithmen