4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ what is $P$? is it a specific point on $E$? $\endgroup$ – Ferra Oct 31 '16 at 15:02
  • $\begingroup$ Sorry, yes! $P$ is a generator point. I'll add it. Thanks for the remark! $\endgroup$ – Luca Oct 31 '16 at 15:17
  • 1
    $\begingroup$ how can $\zeta_3$ be a primitive cube root of $1$ in $\Bbb F_p$ when $p \neq 1 \pmod 6$ ? $\endgroup$ – mercio Nov 9 '16 at 15:16
  • $\begingroup$ thank you! that's another typo. $\endgroup$ – Luca Nov 10 '16 at 13:10
3
+100
$\begingroup$

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]$.

$\endgroup$
  • $\begingroup$ I'm sorry if this is an obvious question, but what is the "quick computation" to see that $\phi^2 - \phi + 1 = 0$ is the minimal polynomial? Could you maybe amplify this? Why is it that this $\lambda$ as the root of this minimal polynomial fulfills the property $\phi(P) = \lambda P$ $\endgroup$ – Luca Feb 20 '17 at 15:27
  • 2
    $\begingroup$ @Luca Take an arbitrary $P=(x,y)$. Then $\phi(P)=(\zeta_3x,-y)$ and $\phi^2(P)=(\zeta_3^2x,y)$. Now compute $(\zeta_3^2x,y)+(x,y)$, using the standard addition law. You will see that this equals $\phi(P)$. Note that $P$ is a generator, so any point in the group is a multiple of $P$, and therefore in particular $\phi(P)$. Thus there exist some $\lambda$ such that $\phi(P)=\lambda P$. Then $\mathcal{O}=\phi^2(P)-\phi(P)+P=\lambda^2 P-\lambda P+P=(\lambda^2-\lambda+1)P$. Therefore $\lambda^2-\lambda+1$ is a multiple of the order of $P$, which is $n$, i.e. $\lambda^2-\lambda+1\equiv0\pmod{n}$. $\endgroup$ – CurveEnthusiast Feb 20 '17 at 15:55
  • $\begingroup$ In the book "Handbook of elliptic and hyperelliptic cryptography" there is a formula for the characteristic polynomial. Is there an easy way to see the relation between $\phi^2 - \phi + 1$ and $x^2 + tx + n$, where $t$ is the trace and $n$ the norm of $\phi$? $\endgroup$ – Luca Feb 21 '17 at 13:22
  • $\begingroup$ how do I calculate the norm and trace of this automorphism? $\endgroup$ – Luca Feb 21 '17 at 13:23
  • $\begingroup$ Well $\phi$ has minimal polynomial $x^2-x+1$, so $t=-1$ and $n=1$. $\endgroup$ – CurveEnthusiast Feb 21 '17 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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