Faktorisierung ohne Probedivisionen

Etliche Verfahren der Kryptographie stützen sich darauf, dass ein Produkt von zwei Primzahlen einfach berechnet werden kann (selbst bei Faktoren mit 100 Dezimalstellen ist das ohne Computer möglich). Jedoch ist bislang kein Verfahren bekannt, mit dem man aus einer solchen Zahl die Primfaktoren systematisch in praktisch brauchbarer Zeit berechnen kann, sofern die Zahl mehrere hundert Dezimalstellen umfasst.

Auf einem von Fermat angegebenen Verfahren, dass die fragliche Zahl als Differenz von Quadratzahlen darstellt, basieren die meisten heute bekannten Verfahren mit der größten Effizienz. Um den Rechenaufwand gering zu halten, wird ein Großteil der Rechnungen in einem Restklassenring, also modulo einer Zahl, durchgeführt. Ein wesentlicher Teil dieser Verfahren ist eine Methode, um Kandidaten für Teiler anders als durch lineares Ausprobieren zu finden, also durch Einsatz von mathematischen Methoden den Rechenaufwand zu vermindern.

Sowohl das Fermat'sche Verfahren der Quadratzahlen als auch ein zweites (von mir als Verfahren der absteigenden Basen bezeichnet, da ich es in der Literatur bislang nicht finden konnte) lassen sich so gestalten, dass sie eine lineare Suche verwenden, dafür aber ohne Multiplikationen und Divisionen auskommen. Sie wären damit für eine Hardware-Lösung geeignet, da sie zudem leicht parallelisierbar sind.

Beide stellen keine Bedrohung für kryptographische Verfahren dar, weil der Aufwand ungefähr proportional zur Wurzel der Ausgangszahl ist, also exponentiell mit Anzahl der Stellen zunimmt.

Mit der Methode der absteigenden Basen und acht parallelen Prozessen konnte ich auf einem einfachen Desktop-PC mit vier Kernen den kleineren Faktor 1073075395319 der 80-Bit Zahl 1179132915127157710180471 in 3sec bestimmen, während dies mit der Quadratmethode wegen des viermal so großen Rechenbereichs nicht ohne weiteres möglich war. Die Programmierung erfolgte in der semi-interpretierten Sprache TUF-PL, so dass das GNU-Programm factor mit 0.3sec um eine Größenordnung schneller ist. Ob dies auch für eine direkte C-Implementation gilt, wurde nicht erprobt.

Der vollständige Text ist derzeit nur als PDF zugänglich.