3
$\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$
4
  • 1
    $\begingroup$ what is $P$? is it a specific point on $E$? $\endgroup$
    – Ferra
    Oct 31, 2016 at 15:02
  • $\begingroup$ Sorry, yes! $P$ is a generator point. I'll add it. Thanks for the remark! $\endgroup$
    – Luca
    Oct 31, 2016 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, 2016 at 15:16
  • $\begingroup$ thank you! that's another typo. $\endgroup$
    – Luca
    Nov 10, 2016 at 13:10

1 Answer 1

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$
5
  • $\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, 2017 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$ Feb 20, 2017 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, 2017 at 13:22
  • $\begingroup$ how do I calculate the norm and trace of this automorphism? $\endgroup$
    – Luca
    Feb 21, 2017 at 13:23
  • $\begingroup$ Well $\phi$ has minimal polynomial $x^2-x+1$, so $t=-1$ and $n=1$. $\endgroup$ Feb 21, 2017 at 13:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .