Ein allgemeines Faktorisierungsverfahren, das Kongruenzen von Quadraten modulo n sucht, indem es viele Werte sammelt, die vollständig über einer gewählten Faktorbasis faktorisiert werden können, und diese mittels linearer Algebra kombiniert, um ein Quadrat modulo n zu erzeugen.

Prinzip

Finde ganze Zahlen x, so dass x^2 mod n B-glatt ist (d. h. vollständig über einer Faktorbasis faktorisiert); speichere die Exponentenvektoren modulo 2 dieser Relationen und löse ein lineares System, um eine Teilmenge zu erhalten, deren Produkt eine quadratische Kongruenz ergibt, dann kann ein gcd zur Faktorgewinnung führen.

Demonstration

Für ein moderates n eine Faktorbasis kleiner Primzahlen wählen, Werte x in der Nähe von sqrt(n) sieben, um B-glatte Werte von x^2 - n zu finden, genügend Relationen sammeln, einen Kernvektor modulo 2 berechnen, die entsprechenden Relationen multiplizieren, so dass y^2 ≡ z^2 (mod n) gilt, und gcd(|y-z|, n) kann einen nichttrivialen Faktor liefern.

Fehlanwendung

Eine ungeeignete Faktorbasis wählen oder nicht genügend glatte Relationen sammeln, oder das quadratische Sieb auf Größen anwenden, bei denen das Zahlkörper-Sieb asymptotisch überlegen ist, ohne Begründung.

Konsequenz

Sehr effektiv für Zahlen mittlerer bis großer Größe: deutlich schneller als Probeteilung und Pollard Rho für große Semiprimes bis zu einer Grenze; erfordert erheblichen Speicher und lineare Algebra, ist jedoch praktisch und parallelisierbar.

Umkehrung

Anstatt ein quadratisches Polynom über den ganzen Zahlen zu sieben, verwendet man Zahlkörper, um glattere Normen und Relationen zu erzeugen (wie beim Zahlkörper-Sieb), um die praktische Grenze deutlich zu erhöhen.

Abgrenzung

Ein allgemeines Sieb, geeignet für mittelgroße bis große Eingaben, aber asymptotisch vom Zahlkörper-Sieb übertroffen für sehr große Werte; es setzt voraus, dass viele B-glatte Werte gefunden werden können und schließt speziell angepasste Algorithmen aus.

Semantische Spannung

Steht im Wettbewerb mit dem Zahlkörper-Sieb: Beide sammeln Relationen und lösen lineare Systeme, aber das quadratische Sieb arbeitet mit quadratischen Polynomen und integeren Faktorbases, während NFS algebraische Zahlkörper nutzt und asymptotisch besser skaliert.

Synthese

Das quadratische Sieb wandelt das Faktorisierungsproblem in die Suche nach vielen glatten quadratischen Resten um, nutzt Sieben und lineare Algebra, um Relationen zu kombinieren und eine Kongruenz von Quadraten zu bilden, die über gcd nichttriviale Faktoren liefert.