Anzeige
Erschienen in:
2024 | OriginalPaper | Buchkapitel
12. Wie man effektiver faktorisiert
verfasst von : Duncan Buell
Erschienen in: Grundlagen der Kryptographie
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Zusammenfassung
In Kap. 11 haben wir mehrere Faktorisierungsmethoden beschrieben. Jede davon wird bei einigen Ganzzahlen erfolgreich sein, aber keine davon ist eine hochmoderne Methode, von der wir erwarten würden, dass sie bei einer gut gewählten RSA N = pq erfolgreich ist. Selbst die beste davon, CFRAC, leidet unter der Notwendigkeit, eine Probedivision durchzuführen, die die meiste Zeit keinen Fortschritt in Richtung Faktorisierung von N erbringt. In diesem Kapitel diskutieren wir Siebmethoden zur Faktorisierung. Der primäre rechnerische Vorteil einer Siebmethode besteht darin, dass alle ausgeführten Rechenschritte tatsächlich zur Findung von Faktoren beitragen und dass ein Sieb, das mit konstantem Schritt durch ein Array im Speicher geht, auf den niedrigsten Ebenen eines Rechenprozesses äußerst effizient ist. Wir diskutieren das Quadratische Sieb und das Mehrpolige Quadratische Sieb und schließen dann mit einem Hinweis auf die derzeit beste Methode zur Faktorisierung großer „schwerer“ Ganzzahlen, das Zahlkörpersieb.