Fermat Faktorisierung: Unterschied zwischen den Versionen
Aus RMG-Wiki
Zeile 1: | Zeile 1: | ||
+ | <div style="text-align:right;">[[Bild:Buch.PNG]][[Benutzer:Deininger_Matthias/Facharbeit/Fachwortverzeichnis| Fachwortverzeichnis]]</div> | ||
===Fermat’sche Faktorisierung=== | ===Fermat’sche Faktorisierung=== | ||
<br> | <br> | ||
Zeile 5: | Zeile 6: | ||
Die Idee des Algorithmus besteht darin, nach Zahlen a und b zu suchen, die die obige Gleichung erfüllen. Meist beginnt man mit <math>a = [\sqrt{n} + 1]</math> und erhöht darauf die Zahl a schrittweise um 1 bis <math>a^2-n</math> 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.<br> | Die Idee des Algorithmus besteht darin, nach Zahlen a und b zu suchen, die die obige Gleichung erfüllen. Meist beginnt man mit <math>a = [\sqrt{n} + 1]</math> und erhöht darauf die Zahl a schrittweise um 1 bis <math>a^2-n</math> 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.<br> | ||
<br> | <br> | ||
+ | [[Benutzer:Deininger_Matthias/Facharbeit/Faktorisierungsproblem| '''zurück zum Lernpfad''']] | ||
<br> | <br> | ||
---- | ---- | ||
vgl. [5, S.328] | vgl. [5, S.328] |
Version vom 13. Dezember 2010, 21:14 Uhr
Fermat’sche Faktorisierung
Die Idee des Algorithmus besteht darin, nach Zahlen a und b zu suchen, die die obige Gleichung erfüllen. Meist beginnt man mit und erhöht darauf die Zahl a schrittweise um 1 bis
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]