no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
— | algo:factoradd [2020-02-04 17:22] (aktuell) – angelegt rainer | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== 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, | ||
+ | |||
+ | Sowohl das Fermat' | ||
+ | |||
+ | 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 {{: |