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.

Filter by
Sorted by
Tagged with
0
votes
0answers
35 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 ...
5
votes
0answers
79 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 ...
2
votes
1answer
81 views

Pollard's Kangaroo— What is the failure probability (assuming random functions)?

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 ...
0
votes
1answer
61 views

How many iterations for Pollard's $p-1$ with $p = r^k + 1$ for prime $r$?

$p$ and $q$ are large primes. What is the lowest upper bound for the number of iterations for Pollard's $p-1$ algorithm for factoring $N = pq$, provided that $p = r^k + 1$, for a prime $r$, and $r^k + ...
6
votes
2answers
830 views

Elliptic curve and “vanity” public keys

I want to find an algorithm to get a private/public key pair where one coordinate of the public key has some specific prefix (for example: 20 leading zeroes). In the secp256k1 case (the Bitcoin curve),...
1
vote
1answer
93 views

Williams' $p+1$ in tandem with Pollard's $p-1$?

Since the success of the $p - 1$ algorithm depends on $p - 1$ having "small" prime factors, or at least smaller than a reasonable smoothness bound, and Williams' $p + 1$ method has the same constraint ...
3
votes
0answers
139 views

Cryptographically Secure Elliptic Curve

What are the properties a cryptographically secure Elliptic Curve must have? I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far: A curve ...
0
votes
1answer
437 views

Can you help me understand Pollard's rho example?

I'm studying the Pollard's rho algorithm to solve discrete logaritms on the Handbook of applied cryptografy but I didn't understand one part of the theory and looking at the example gets me more ...
2
votes
2answers
847 views

How to apply Pollard's Rho Method on elliptic curves to solve discrete logarithm problem in finite field?

I have ElGamal signature scheme implemented in finite field $\mathbb{F}_p$. The thing is that I need to apply Pollard's Rho Method on elliptic curve $E(\mathbb{F}_p)$ to this scheme, solve discrete ...
2
votes
1answer
666 views

Pollard's Lambda algorithm ecdlp with Pohlig Hellman

I'm trying to solve the ECDLP problem given an elliptic curve defined over a prime field. This prime is large (about 256 bits). I managed to factor the order of the curve, and most of the prime ...
4
votes
2answers
1k views

Issue implementing Pollard's Rho for discrete logarithms

I've been trying to implement Pollard's Rho recently. The original idea was to implement the code in several languages and put it up for everyone to see for educational purposes. I first took to ...
0
votes
1answer
49 views

Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space?

Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space? It the reason why this is not generally done because of a meet-in-the-middle attack?
0
votes
2answers
221 views

Is the complexity of Pollard rho for discrete logartihm really the modulus?

so I'm reading everywhere that the Pollard Rho for Dlog's complexity of $g^a \pmod{n}$ is $\mathcal O(\sqrt{n})$. Shouldn't it be $\mathcal{O}(\sqrt{q})$ with $q$ the order of $g$?