Elliptic Curves with trace t = 1 [Theory]

In this post, i will show the proof that one could efficiently compute the discrete logarithm on a curve $E[\mathbb{F}_p]$ if the number of points on that curve is equal to $p$. Such a curve is called anomalous. Since $$\#E[\mathbb{F}_p] = p+1-t$$ this is again equal to the statement that the trace $t$ of the curve is equal to $1$. The proof was given by Nigel Smart [1], Satoh and Araki [2], or Semaev [3] independently roughly at the same time ($\sim$ 1999).

Remark: The attack is somehow similar to the described lift in that post, which executes the lift $\mathbb{Z}/p\mathbb{Z} \rightarrow \mathbb{Z}/p^2\mathbb{Z}$, and that solves the dlp in the subgroup of order $p$ in $\mathbb{Z}/p^2\mathbb{Z}$.


A lot of papers, that mention this result, prove this by defining the subgroups $E_1$
\begin{equation}
E_1 = \{(x,y)\in E[\mathbb{Q}_p]| v_p(x) \leq -2\}
\end{equation} as well as $E_2$
\begin{equation}
E_2 = \{(x,y)\in E[\mathbb{Q}_p]| v_p(x) \leq -4\}
\end{equation} (with $v_p$ being the normal $p$-adic valuation function). Then they prove that
\begin{equation}
E[\mathbb{F}_p] \simeq E[\mathbb{Q}_p]/E_1
\end{equation}
and
\begin{equation}
E_1 / E_2 \simeq \mathbb{F}^+_p
\end{equation}

# p-adic integers #

But here, i want to show at least a little bit better what is actually going on. Therefore, i used [4] as a good reading source. To understand the proof better, one has to understand how the group operation on $E[\mathbb{Q}_p]$ looks like.
Assume we start with an elliptic curve in Weierstrass notation $$y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$$ over the field $\mathbb{F}_p$. We then apply the transformation $$(x,y) \rightarrow (-x/y,-1/y) = (z, w)$$ If we rewrite the Weierstrass equation with $z$ and $w$, we get $$w = z^3 + (a_1z + a_2z^2)w + (a_3 + a_4z)w^2 + a_6w^3$$ We substitute each $w$ on the RHS recursively with the whole term on the RHS, since it is equal to $w$ itself. The outcome is of the form $$w = z^3+a_1z^4+(a_1^2+a_2)z^5+...$$ The conversion from this representation back to $x$ and $y$, i.e., $x = z/w$ and $y = -1/w$ yields the series representation of these terms (now called $x(z)$ and $y(z)$)
\begin{align*}
x(z) = z/w & = \frac{1}{z^2}-\frac{a_1}{z}-a_2-a_3z-(a_4+a_1a_3)z^2-...\\
y(z) = -1/w & = -\frac{1}{z^3}+\frac{a_1}{z^2}+\frac{a_2}{z}+a_3+(a_4+a_1a_3)z+...
\end{align*}
However, these series representation are only valid if these infinite series converge in $\mathbb{Q}_p$. Since we can assume that all the coefficients $a_i$ are from $\mathbb{F}_p$, the series converge if $p|z$, which is equal to $v_p(z) \geq 1$, which means $z \in p\mathbb{Z}_p$, i.e.:
\begin{equation}
-x(z)/y(z) = z = c_0p + c_1p^2 + c_2p^3 + ....
\end{equation} If we set such a $z$ into the equations for $x(z)$ and $y(z)$ we get (for simplicity we assume $z = p$)
\begin{align*}
x(p) & =  \frac{1}{p^2}-\frac{a_1}{p}-a_2-a_3p-(a_4+a_1a_3)p^2-...\\
y(p) & = -\frac{1}{p^3}+\frac{a_1}{p^2}+\frac{a_2}{p}+a_3+(a_4+a_1a_3)p+...
\end{align*} hence a coordinate is equivalent to
\begin{align*}
(x(p):y(p):1) &\sim (x(p):y(p):1)(-p^3)\\
&\sim (-p+\frac{a_1}p^2+a_2p^3+a_3p^4-...:1-a_1p-a_2p^2-...:p^3)\\
&\sim (0:1:0)\pmod{p}
\end{align*} That means, whenever $z \in p\mathbb{Z}_p$ we get points that reduce to the point of infinity modulo $p$. And for those integers we could use the series representation to calculate. This mapping we define as the $\theta$-function.
\begin{align*}
\theta: E[p\mathbb{Z}_p] &\rightarrow E_1[\mathbb{Q}_p]\\
z &\mapsto \left(z/w,-1/w \right)
\end{align*}
 The addition for two points $z_1$ and $z_2$ is well defined for those series representation and denoted as $F(z_1,z_2)$ It is not surprisingly, that this only makes sense, if the logarithm in this case is easy. The logarithm function in this case is
\begin{equation}
\log_F(z_1,z_2) = \log z_1 + \log z_2,\;\text{for}\; z_1,z_2 \in p\mathbb{Z}_p
\end{equation} as it is usual for a logarithm function and indeed it holds $$\log_F: E[p^i\mathbb{Z}_p] \rightarrow p^i\mathbb{Z}_p$$ This efficiently computable functions $F$ and $\log_F$ are actually responsible to make the whole algorithm work. For those who are more interested in the addition function $F$ and how to compute the logarithm $\log_F$ in these cases, can google the string formal group of elliptic curves.

Let the discrete logarithm be the $P = [n]Q$ on the original curve $E[\mathbb{F}_p]$, and we want to know $n$. We lift these two points to $E[\mathbb{Q}_p]$, which can easily be done using Hensel-lifting. The lifting goes successively to curves mod $p^2$,$p^3$ and so on, theoretically to infinity. But practically, $1$ lift is enough. Let $\overline{P}$ and $\overline{Q}$ be those points: \begin{align*}
\overline{P} = (x_P+\sum_{i=1}k^{P,x}_ip^i, y_P+\sum_{i=1}k^{P,y}_ip^i) \\
\overline{Q} = (x_Q+\sum_{i=1}k^{Q,x}_ip^i, y_Q+\sum_{i=1}k^{Q,y}_ip^i) \\
\end{align*} Since $\overline{P} = [n]\overline{Q}$ it is $$\overline{P} - [n]\overline{Q} = \overline{R} \in E_1[\mathbb{Q}_p]$$ and $\overline{R} \sim (0:1:0)\pmod{p}$. We don't know $\overline{R}$ since we don't know $n$. But we know the integer $p$, so we multiply everything with $p$:
\begin{equation}
[p]\overline{P} - [n][p]\overline{Q} = [p]\overline{R}
\end{equation} Since $P$ and $Q$ are $p$-torsion points, i.e., $[p]P = [p]Q = \mathcal{O}$, it is
\begin{align*}
[p]\overline{P} = \overline{\overline{P}}&\in E_1[\mathbb{Q}_p] \\
[p]\overline{Q} = \overline{\overline{Q}} &\in E_1[\mathbb{Q}_p]
\end{align*} thus $$\overline{\overline{P}} - [n]\overline{\overline{Q}} = [p]\overline{R}$$ First, we have to see what happens to $[p]\overline{R}$. Those are elements whose $x(z)$ and $y(z)$ series are of the form
\begin{align*}
x(z) &= z/w = \frac{1}{z^4} + ... \\
y(z) &= -1/w = \frac{1}{z^6} + ...
\end{align*} and $\theta^{-1}([p]\overline{R})$ yields an expression of the form $$-x(z)/y(z) = z^2 + ...$$ which is, for $p|z$, from $p^2\mathbb{Z}_p$. Since all elements are from $E_1$, we first can apply $\theta^{-1}$
\begin{equation}
\theta^{-1}(\overline{\overline{P}}) - [n]\theta^{-1}(\overline{\overline{Q}}) = \theta^{-1}([p]\overline{R}) \end{equation} and then we apply $\log_F$
\begin{equation}
\log_F(\theta^{-1}(\overline{\overline{P}})) - [n]\log_F(\theta^{-1}(\overline{\overline{Q}})) = \log_F(\theta^{-1}([p]\overline{R})) \end{equation} The right hand side is an integer from $p^2\mathbb{Z}_p$ and the terms on the left are integers from $p\mathbb{Z}_p$ (due to the log-function, we have no elliptic curve anymore), so this can be written as
\begin{equation}
c_1p+c_2p^2+c_3p^3+... - n(d_1p+d_2p^2+d_3p^3) = e_2p^2+e_3p^3 + e_4p^4
\end{equation} The reduction modulo $p^2$ yields zero on the RHS and thus
\begin{equation}
c_1p+c_2p^2+c_3p^3+... = n(d_1p+d_2p^2+d_3p^3+...)\pmod{p^2}
\end{equation} and finally
\begin{equation}
\frac{p(c_1+c_2p^1+c_3p^2+...)}{p(d_1+d_2p^1+d_3p^2+...)} = n\pmod{p^2}
\end{equation}
\begin{equation}
\frac{c_1}{d_1} = n\pmod{p}
\end{equation}

Since i am not totally fine with this post, i will update it from time to time and i will write a follow up post about the practial aspects of this algorithm as well as some SAGE examples.

Here is the practice post.

[1] Smart: The discrete logarithm problem on elliptic curves of trace one, Journal of Cryptology, Bd. 12, 1999, S. 193
[2] Satoh T. and Araki K.,Fermat quotients and the polynomial time discrete log algorithm for anamolous elliptic curves.Comm. Math. Univ. Sancti. Pauli., 47:81-92, 1998.
[3] Semaev, I.A. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p , Mathematics of Computation, 67:353-356,1998
[4] infoscience.epfl.ch/record/52470/files/IC_TECH_REPORT_200249.pdf