Der asymptotisch schnellste bekannte klassische Algorithmus zur Faktorisierung sehr großer ganzer Zahlen, der algebraische Zahlkörper, Polynomauswahl, Normsieben und großskalige lineare Algebra nutzt, um Relationen zu erzeugen, die Kongruenzen von Quadraten modulo n liefern.

Prinzip

Wähle Polynome, die Zahlkörper definieren, und Abbildungen nach Z/nZ, sieve über zwei Domänen, um Relationen zu sammeln, bei denen algebraische Normen über gewählten Faktorbases glatt sind, setze zahlreiche Relationen in eine spärliche Matrix zusammen und löse modulo 2, um in Quadratskongruenzen zu kombinieren, deren gcds mit n nichttriviale Faktoren liefern.

Demonstration

Für ein großes Semiprime n eine Polynom-Paarung und eine Faktorbasis wählen, über algebraische und rationale Seiten Normen sieben, glatte Normen sammeln, genügend Relationen erlangen, eine spärliche lineare Algebra-Routine laufen lassen, Abhängigkeiten finden und schließlich Quadratskongruenzen bilden und gcds berechnen, um Faktoren zu extrahieren.

Fehlanwendung

NFS auf kleine Zahlen anwenden, bei denen der Aufwand für Polynomauswahl und lineare Algebra den Algorithmus langsamer macht als einfachere Methoden, oder schlechte Polynomauswahl, die die praktische Leistung zunichtemacht.

Konsequenz

Bietet die beste bekannte praktische Leistung zum Faktorisieren sehr großer Zahlen (Hunderte von Dezimalstellen) auf klassischer Hardware; verlangt aber erhebliche Rechenressourcen, anspruchsvolle Implementierung und sorgfältiges Tuning.

Umkehrung

Im Gegensatz zu elementaren oder quadratischen Sieben, die bei kleineren Größen praktikabel bleiben; oder zu Quantenalgorithmen (Shor), die asymptotisch alle klassischen Siebe übertreffen würden, falls großskalige, fehlertolerante Quantencomputer verfügbar wären.

Abgrenzung

Asymptotisch optimal unter den bekannten klassischen Algorithmen für sehr große Zahlen, aber aufgrund der Einrichtungskosten für kleine Eingaben unpraktisch; schließt Quantenfaktorisierungsverfahren und spezialisierte algebraische Methoden für spezielle Formen aus, sofern sie nicht angepasst sind.

Semantische Spannung

Im Wettbewerb mit dem quadratischen Sieb in praktischen Bereichen und mit spezialisierten Methoden für bestimmte Zahlenformen; konzeptionell unterscheidet es sich, indem es Zahlkörper und Norm-Sieving verwendet anstelle nur ganzzahliger quadratischer Reste.

Synthese

Das Zahlkörper-Sieb reduziert die Faktorisierung auf die Suche nach vielen glatten algebraischen Normen in Zahlkörpern, kombiniert Sieben und großskalige lineare Algebra, um diese Relationen in Quadratskongruenzen umzuwandeln, die Faktoren liefern, und erreicht so die beste bekannte klassische asymptotische Laufzeit für sehr große Zahlen.