Fermat Faktorisierung

Aus RMG-Wiki
Wechseln zu: Navigation, Suche
Buch.PNG Fachwortverzeichnis

Fermat’sche Faktorisierung


N = a^2 - b^2  =\underbrace {(a+b)}_{=p}\cdot \underbrace {(a-b)}_{= q} = p\cdot q

Die Idee des Algorithmus besteht darin, nach Zahlen a und b zu suchen, die die obige Gleichung erfüllen. Meist beginnt man mit a = [\sqrt{n} + 1] und erhöht darauf die Zahl a schrittweise um 1 bis a^2-n Quadratzahl ist. Ist diese Forderung erfüllt, so lässt sich zunächst b und dann auch p und q berechnen, womit die Faktorisierung geglückt wäre. In der Praxis gilt dies jedoch für große Moduli n immer noch als nicht effizient berechenbar. Diese und ähnliche Vorgehen werden von Wissenschaftlern und Hackern weltweit verwendet, um die Faktorisierung von n zu brechen oder ein noch effektiveres Verfahren zu entwickeln.

zurück zum Lernpfad


vgl. [5, S.328]