We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [pollard-rho]

Algorithm for integer factorization invented by John Pollard (1975). It is often used in cryptanalysis because it only requires a small amount of space and remains polynomial in time.

13 questions
Filter by
Sorted by
Tagged with
50 views

### Pollard's Kangaroo: How random does $f$ have to be?

I'm implementing Pollard's kangaroo algorithm as described here. Wikipedia's description of the protocol says that you should have "a pseudorandom map $f:G\rightarrow S$." Does anyone know what ...
90 views

### Variant of Pollard rho using small factors of p - 1

Given an integer $N$ to factor which is divisible by some prime $p$, suppose you know (or guess) that $p - 1$ has a few small factors, e.g. $3, 2^2, 5$. Define $B$ as a product of small prime powers ...
I'm reading Pollard's paper on solving the discrete log problem, i.e. to find $x$ given $y = g^x$, where $g$ is a generator of the group. He has a Kangaroo Algorithm (page 4) which allows you, if you ...