2
$\begingroup$

I have been playing with Pollard's rho algorithm for elliptic curves over finite fields. I have noticed after some experimenting, that the algorithm almost always 'fails' for supersingular elliptic curves over a finite field with characteristic equal to a Mersenne prime. I cannot seem to find any logical explanation for it, so I wonder whether anyone has an idea why this happens.

Let me elaborate on the meaning of 'fail'. So I use the standard Pollard rho method which you find in chapter 11 in 'The Arithmetic of Elliptic Curves' by Joseph Silverman. In the implementation I used a partition function, which basically looks at the sum of the coefficients of each point on the curve modulo 3 (so that the points on the curve are just about equally divided into three sets). I don't think actually this influences the result.

Using the notation in the book, I consider the algorithm to fail if $n \mid \delta_i - \beta_i$. In this case as Silverman says, we get no information on $m$ (where we want to find $m$ such that $m \cdot x = y$, for $x,y \in E(\mathbf{F}_p)$).

Apparently, this almost always happens when $p$ is a Mersenne prime and $E(\mathbf{F}_p)$ is supersingular (so the amount of rational points is exactly $p+1$). If anyone has any suggestions why this happens, I'm all ears!

Improve this question
$\endgroup$
2
  • $\begingroup$ If p is Mersenne prime then p+1 is power of 2 and the group order is 2-smooth. Why don't you try small subgroup algorithm and solve the DL in time log(p)? $\endgroup$
    – joro
    Commented Oct 22, 2023 at 8:32
  • $\begingroup$ As @joro suggests, you can solve DLPs faster on these particular curves using the Pohlig-Hellman algorithm. (For supersingular curves in general, you can use the Menezes-Okamoto-Vanstone reduction to map the problem to a finite field discrete log and solve faster there.) But if you're doing this to study Pollard rho, then this really looks like a subtle problem with your partition function (and/or your choice of "steps") rather than the rho algorithm itself. Try hashing a canonical representative for the point and then taking the result mod 3, to get a proper "random" division into 3 sets. $\endgroup$
    – Ben Smith
    Commented Oct 25, 2023 at 11:35

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .