Pollards p-1-Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Pollards p-1 - Algorithmus
Sei [mm] n$\geq$ [/mm] 2 eine zusammengesetze ganze Zahl, für die wir einen Teiler finden wollen.
1. Wähle eine Zahl k die ein Produkt von kleinen Primzahlen mit niedrigen Exponenten ist. Nimm zum Beispiel
$$k=kgV(1, 2, 3, [mm] \ldots [/mm] K)$$ für eine ganze Zahl K
2.Wähle eine beliebige ganze Zahl a mit 1 < a < n.
3. Berechne ggT(a,n). Ist dieser echt größer als 1, dann ist a ein nicht trivialer Teiler von n und wir sind fertig. Anderenfalls gehe zu Schritt 4.
4. Berechne $D= [mm] ggT(a^k-1,n)$. [/mm] Ist 1 < D < n, so ist D ein nicht trivialer Teiler von n und wir sind fertig. Ist D = 1, dann geh zurück zu Schritt 1 und wähle ein größeres k. Ist D=n, dann geh zurück zu Schritt 2 und wähle ein anderes a.
|
Hallo,
kann mir jemand das Prinzip von Pollards p-1-Algorithmus erklären. Warum führt dieser zu einer Faktorisierung in Primfaktoren?
Vielen Dank
mariposa
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Do 21.06.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
