| 05.12.2013, 14:41 |
Highlander214 |
Auf diesen Beitrag antworten » |
Laufzeit Pollard-Rho
Hallo,
ich soll die Laufzeit des Pollard-Rho-Algorithmus begründen (gegeben ist der folgende Fact):
| Zitat: |
| 3.11 Fact Assuming that the function f(x) = x2 + 1 mod p behaves like a random function, the expected time for Pollard’s rho algorithm to find a factor p of n is O(√p) modular mul- tiplications. This implies that the expected time to find a non-trivial factor of n is O(n1/4) modular multiplications. |
Der Anfang des Facts und die Funktionsweise des Algorithmus ist mir klar, was ich jedoch nicht verstehe ist: Wieso ist der Erwartungswert für die Länge eines Zyklus , Wobei p der Modulo ist. |
