gibt es ein faktorisierungsverfahren zur primfaktorzerlegung?

...komplette Frage anzeigen

4 Antworten

Grundsätzlich gibt es kein Verfahren, das bei einer allgemein gegebenen Zahl n die Faktorzerlegung vornimmt, welches wesentlich effizienter ist als das triviale Verrfahren, nämlich alle Primzahlen bis Wurzel(n) durchzuprobieren. Die bekannten sehr hohen Primzahlen beruhen auf speziellen Verfahren, die nur bei speziellen Darstellungen möglich sind.

Auf dieser Tatsache beruhen kryptograhische Verfahren (RSA-Algorithmus). Der RSA-Algorithmus wäre nicht anwendbar, wenn es einen effizienten Algorithmus zur Faktorisierung gäbe. Hat man also z.B. eine natürliche Zahl mit 400 Stellen gegeben, die das Produkt zweier 200-stelligen Primzahlen ist (die aber nicht bekannt sind), so kann man diese beiden Faktoren nicht herausfinden, da der Rechenaufwand zu groß wäre.

Zum Verständnis ist dazu zu sagen, dass bei einer willkürlich gegebenen 400-stelligen Zahl die Faktorisierung sehr wahrscheinlich gelingt, da es in den meisten Fällen sehr kleine Primfaktoren gibt. Die Schwierigkeit der praktischen Faktorisierung besteht eben nur dann, wenn die Zahl selbst eine Primzahl ist oder der kleinste Primfaktor sehr groß ist (z.B. eben 200 Stellen hat).

Da musst du bis morgen warten, bis Sheldon, Leonard und Raj wieder on sind...

Na klar

sogar hier in Deutschland. Wende dich dazu an einen deutschstämmigen Matheprofessor.

notizhelge 24.03.2012, 13:13

"Bis heute ist kein Faktorisierungsverfahren bekannt, das nichttriviale Teiler und damit die Primfaktorzerlegung einer Zahl effizient berechnet." (http://de.wikipedia.org/wiki/Faktorisierungsverfahren)

Darauf, dass es kein solches Verfahren gibt, basieren Verschlüsselungsverfahren.

0

Was möchtest Du wissen?