Example of CM field discriminant of elliptic curves

Question

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.

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.