I am currently trying to implement the Pollard Rho Algorithm with the speed-up using this automorphism, and have a question about the automorphisms of an elliptic curve; more specific:
let $E/\mathbb{F}_p$ be an elliptic curve $E: y^2 = x^3 + 7$ with $p\equiv 1 (mod) 6$.
We define $\phi: E\to E$ with $(x,y)\mapsto (\zeta_3x, -y)$, with $\zeta_3$ the primitive 3rd root in $\mathbb{F}_p$. We have then
Then there exists an integer $\lambda$ s.t. $\lambda R = \phi(R)$ for all $R\in E/\mathbb{F}_p$.
In "Mathematics of Public Key Cryptography" by Steven Galbraith I read that $\lambda$ should be the root of the characteristic polynomial of $\phi (mod) n$, where $n = ord(P)$ prime and $P$ a generator point of $E/\mathbb{F}_p$.
I found that this works for the root of $f(x) = x^5+x^4+x^3+x^2+x+1$.
- here my first question: I am not sure why this is the characteristic polynomial. Plus it looks like the polynomial of the 6th-root of unity $\zeta_6\in \mathbb{F}_p$. Why is that? Where is the connection between $\phi$ and $\zeta_6$?
- my second question: In another source (Elliptic Curve Cryptography in Practice) I found that $\phi$ can also be defined as $\phi: E\to E$, with $(x,y)\mapsto (\zeta_6 x, -y)$. But a little test with SAGE gave me the error that $(\zeta_6x,-y)$ is not a point on $E/\mathbb{F}_p$.
- my third question: I now need to calculate $\lambda^i * R = \phi^i(R) $, $\forall i\in\{0,1,2,3,4,5\}$ $(*)$. ($\lambda^6 = 1 (mod) n$ and $\phi^6(R) = R$). Again I tested this with SAGE, but from the five different roots of $f$ there is only one of them that holds this property (the others give the same $\phi^i(R)$, but in a different order). Is there a trick how to pick $\lambda$ the root of $f$ where the property $(*)$ holds (for arbitrary primes $p$ and generator points $P$)?
I would be happy for any advice and hint! All the best,
Luca
Let $E/\mathbb{F}_p$ be the elliptic curve which you describe. I'm going to assume that $E(\mathbb{F}_p)=\langle P\rangle$, because you mention that $P$ is a generator. Therefore $\#E(\mathbb{F}_p)=n$, where in cryptographic context $n$ would probably be some prime.
First of all, for an elliptic curve $y^2=x^3+ax+b$ we can define the $j$-invariant $$j=1728\frac{4a^3}{4a^3+27b^2}.$$ It is clear that $j(E)=0$. As a result, we know that $\#\operatorname{Aut}(E)=6$. If we take $\zeta_6\in\mathbb{F}_p$ such that $\zeta_6^6=1$, and we write $\zeta_3=\zeta_6^2$, then we have the automorphisms $$(x,y)\mapsto(x,y),(x,-y),(\zeta_3x,y),(\zeta_3x,-y),(\zeta_3^2x,y),(\zeta_3^2x,-y).$$ In particular, we have the automorphism $\phi:(x,y)\mapsto(\zeta_3x,-y)$.
Now, since our curve is not supersingular and has non-trivial endomorphisms, we know that the endomorphism ring $\operatorname{End}(E)$ is isomorphic to an order in a quadratic imaginary number field, say $K/\mathbb{Q}$. Note that clearly $\phi^6=1$, which is seen by composing the map with itself a couple of times. That is, $\phi$ is a sixth root of unity in $K$. It is indeed a root of the polynomial $x^6-1=(x-1)f(x)$. But, a quick computation shows that actually $\phi^2-\phi+1=0$, so $\phi$ has minimal polynomial $x^2-x+1$. Note that this does not contradict the fact that $\phi^6=1$.
Now consider the action of $\phi$ on $\langle P\rangle$. The group is cyclic generated by $P$, so the whole action is determined by the image of $P$. As $\phi(P)\in\langle P\rangle$, there must exist some $\lambda$ such that $\phi(P)=\lambda P$. But certainly still $\phi^2-\phi+1=0$. Thus $(\lambda^2-\lambda+1)P=\mathcal{O}$, and therefore $\lambda^2-\lambda+1\equiv0\pmod{n}$.
Example. Take $p=13$, and think of $\mathbb{F}_p$ as $\mathbb{Z}/p\mathbb{Z}$. Then $\#E(\mathbb{F}_p)=7$. Take $\zeta_3=9$. The roots to $\lambda^2-\lambda+1\equiv0\pmod{7}$ are easily seen to be 3 and 5. A quick check shows that $\phi=[3]$.