Pollard's Rho-Algorithmus ( Primzahltest, Arbeit f

25/09/2014 - 14:51 von Weltmarktf | Report spam
(Pollard’s Rho–Algorithmus)

Sei n eine Zahl von der ein Teiler gefunden werden soll.1
1. Wàhle a ∈ {0, . . . , n − 1} mit a ̸= 0, −2 und ein x0 ∈ N.
2. Setze k := 0.
3. Berechne xi+1 := x
2
i + a mod n für i = 2k − 1, . . . , 2
k+1 − 1.
4. Berechne dj
:= ggT(x2
k−1 − xj
, n) für j = 2k+1 − 2
k−1
, . . . , 2
k+1 − 1.
2
Gibt es ein j mit dj ̸= 1, n, so breche den Algorithmus ab, man hat
einen Teiler d von n gefunden.
5. Setze k := k + 1 und gehe zu 3.
 

Lesen sie die antworten

#1 Izur Kockenhan
25/09/2014 - 15:13 | Warnen spam
Wir Ingenieure haben es da schon einfacher:
isprime(m);
nextprime(n);
numlib::proveprime(o);

Die Funktion numlib::proveprime(o); stellt einen Primzahlentest zur
Verfügung, der stets eine korrekte Antwort liefert, aber im Allgemeinen viel
langsamer als isprime(m); ist.
Wir nutzen MuPAD!

Izur Kockenhan

Ähnliche fragen