Advertisement
Published in:
2024 | OriginalPaper | Chapter
12. Wie man effektiver faktorisiert
Author : Duncan Buell
Published in: Grundlagen der Kryptographie
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.