1
$\begingroup$

I am trying to understand illustrative example of Pollard's Rho method to solve ECDLP from the book "Guide to Elliptic Curve Cryptography"

I am referring to Algorithm 4.3 and Example 4.4

There is this table on Pg. 160

Pollard's Rho Calculation

Could anyone explain me how right side of this table , c'' , d'' and x'' is computed. I am simply not able to understand this computation which corresponds to step 6.2 of algo.

Only pattern I observe is that every second row on left side of table appears on right side,too.But other than that I am struggling to understand.

Please elaborate this computation . Thank you in advance.

$\endgroup$

2 Answers 2

0
$\begingroup$

every second row on left side of table appears on right side, too

Yes. That's because the right side is obtained just as the left side is, only skipping odd-numbered iterations. This is what "For i from 1 to 2 do" in step 6.2 of the algorithm is about: keeping only even iterations.

The algorithm is Pollard's rho for logarithms with cycle finding using the simplest algorithm, Floyd's tortoise and hare.

The right side values for line #ℓ+1 are calculated from the right side values for line #ℓ, by making, independently, the calculation made (or that would be made) to go on the left side from line #2ℓ to line #2ℓ+1, then the calculation made (or that would be made) to go on the left side from line #2ℓ+1 to line #2ℓ+2.

For example, applying the above for ℓ=6, the right side values for line #7 are calculated from the right side values for line #6, by making twice the same calculation that's made on the left side to go from one line to the next. IF on the left side we calculated two more lines, the left side on line #13 (resp. #14) would be what is computed internally on the first (resp. second) of the two computations made on the right side to go from line #6 to #7.

A cycle of the kind depicted in figure 4.1 page 158 is already entered when at line #10 the right side reaches point (223,153) that was already reached on the left side at line #8 and (thus) on the right side at line #4. Noticing this would allow to stop earlier and conclude, but the algorithm can't, because it does not keep earlier results in memory. So it keeps on until X' = X". That's a time vs memory trade-off.

$\endgroup$
5
  • $\begingroup$ Then ,does that mean on left side actualy 24 iterations are performed in order to arrive at the matching pair ? $\endgroup$ Dec 21, 2023 at 16:16
  • $\begingroup$ @SudhanwaDeo: No. On the left side it is performed 12 iterations. On the right side it is performed 12 times (a dummy iteration, not shown or numbered; and another iteration, shown and numbered). The 12th iteration of the left side has a point (57,105) that matches the point of iteration numbered 12 on the right side (which would be iteration 24 on the left side, but we do not get this far on the left side). That stops the iterations. $\endgroup$
    – fgrieu
    Dec 21, 2023 at 17:06
  • $\begingroup$ ok , i could not understand 100% of what you said. Let us take an example of Iteration 7.On left side , we have 79,21,(81,168) and on right side we have 139,111,(185,227).Could you tell me how right side values are calculated in this case without calculating what would be Iteration 14 values on left side ? $\endgroup$ Dec 22, 2023 at 4:25
  • $\begingroup$ HI ,@fgrieu , thank you for your efforts and explanation. So my understanding now is that this algorithm is designed in a way such that left side values are calculated in single step while right side same calculations happen twice. It will terminate only when step on Left and Right match to a single point . In this way , algorithm may not necessarily detect a solution of matching pair even if it is already found. It will try to find it only in this methodical way to save on memory . Is this understanding of mine correct ? $\endgroup$ Dec 22, 2023 at 10:01
  • $\begingroup$ @Sudhanwa Deo: yes this is it! $\endgroup$
    – fgrieu
    Dec 22, 2023 at 10:08
0
$\begingroup$

Given a prime p, we let $x_0 = 1$, and $x_{i+1} = (x_i^2+1) \mod p$. Since there are only p possible values for $x_i$, so eventually these values must repeat. Assuming that $x_i$ behaves like being random, the smallest I is expected to be quite small.

What will happen when we calculate $x_i$? For a while we get all different values. Then a value gets repeated, that is $x_n = x_m$, and from then on the values repeat in a cycle of length m-n.

Now the algorithm calculates two sequences: One step at a time, and two steps at a time. After n steps the “slow” sequence enters the cycle. The “fast” sequence at this point is somewhere in the cycle and would need k steps to reach the start of the cycle. Since the fast sequence does two steps where the slow one does one, after each 1/2 steps the fast sequence comes one closer to the slow one, and after k 1/2 steps both meet. At that point $x_i = x_{2i}$.

Note that we have no idea what n, m and k are, but we still will find the point where both sequences meet.

And this is just Floyd’s cycle finding algorithm. Pollard-rho is much more clever. Given is N, and we want to find factors of N. Let p be a prime factor of N. Then we calculate $x_{n+1} = (x_n^2+1) \mod p$ and $y_{n+1} = (y_n^2+1) \mod N$ in parallel. At some point we find an i such that $x_i = x_{2i}$. At that point $y_i = y_{2i} \mod p$ and $gcd(y_i - y_{2i})$ is a multiple of p.

We don’t actually have any idea what p is, since finding p is what we try to achieve! So we never actually calculate $x_i$. Nevertheless, p is a divisor, so we will find i with $gcd(y_i - y_{2i}) = g > 1$, and that g is a divisor of N.

$\endgroup$
1
  • $\begingroup$ The question is about Pollard's Rho for the Discrete Logarithm Problem (in an elliptic curve group). This answer is about Pollard's Rho for factoring. $\endgroup$
    – fgrieu
    Dec 26, 2023 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.