From this answer I am able to understand that if CM field discriminant for a particular curve is small then it provide us a fast endomorphism which in turn allow rho method to speed up by $\sqrt{\frac{1}{3}}$.

What I cannot understand is:

  1. How one calculate this CM discriminant? Is this same as $\Delta = 4a^3 + 27b^2$ (I do not think so)

  2. What kind of operation this endomorphism is? For example $[-1]$ endomorphism in answer is point negation. What operation I need to do with CM discriminant $\beta$ to acheive this: $$ (x,y) \mapsto (\beta x, y) \mapsto (\beta^2 x, y) \mapsto (\beta^3 x, y) = (x,y), $$ Do I need to multiply the $x$ coordinate with cm discriminant (highly unlikely) or perform scalar multiplication or something else?

  3. Please demonstrate (2) using example over real elliptic curve over finite field.


1 Answer 1


The speed up is not for all curves with small CM discriminant, but specifically for those with CM by $\sqrt{-3}$ (hence allowing us to define a cube root of unity $\beta=(1+\sqrt{-3})/2$.

  1. For a given curve over a prime field we can compute its CM discriminant by first counting the number of points and then computing $t=p+1-\#E(\mathbb F_p)$. The CM discriminant is then the square free part of $t^2-4p$.

For example, consider the curve $E:y^2=x^3+7$ over $\mathbb F_{19}$. This has 12 points and so $t=19+1-12=8$ and the CM discriminant is the square free part of $8^2-4\times 19=-12$ so we have discriminant $-3$ (as is required for the endomorphism used in the Pollard rho speed up).

2 and 3. The endomorphism requires an element $\beta$ which is a cube root of 1 in our field and for $\mathbb F_{19}$, we see that $\beta=7$ is a permissible choice. The computation of the endomorphism is simply multiplication of the $x$-coordinate by $\beta$, hence if we start with the point (8,5) on the curve in our example it maps to (18,5) under the endomorphism (because $7\times 8=18\mod 19)$. Iterating the map gives $$(8,5)\mapsto (18,5)\mapsto (12,5)\mapsto (8,5)$$ as desired.

ETA: To show how this speeds up Pollard rho, its convenient to work over a curve with a prime number of points, so let's switch to the curve $y^2=x^3+3$ over $GF(31)$ which has 43 points (hence $t=-11$ and we have complex multiplication by $\sqrt{-3}$). We take $\beta=5$ and again we can form triples of points such as $(1,2)\mapsto (5,2)\mapsto (25,2)$. By the magic of complex multiplication the discrete logs of these are related by $\gamma$ where $\gamma$ is a cube root of 1 in $GF(43)$, in this case $\gamma=6$ as we see $$6(1,2)=(5,2),36(1,2)=(25,2).$$ Thus the "private key" of $(5,2)$ is 6 times the private key of $(1,2)$ mod 43.


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.