satoh.tex

\section{Satoh's algorithm} \label{satoh}
This algorithm is divided into two parts. First we do what is called a \emph{lifting} to desired
precision, then we recover the trace of the Frobenius from the lifted data.

\subsection{Lifting the j-invariants}
We begin by establishing some notation, so let $\mathbb{F}_q$ be our finite field with $q=p^n$ as before,
$\mathbb{Z}_p$ the $p$-adic integers and $\mathbb{Q}_q$ the $q$-adic rationals as defined in Section \ref{p-adic}.
For this section we let $\sigma$ be the $p^{th}$ Frobenius, and $\phi_q$ be the $q^{th}$ Frobenius.
As for previous sections we denote the curves over our finite fields as $E/\mathbb{F}_q$,
for the lifted curves we write $\mathscr{E}/\mathbb{Q}_q$.

\begin{mydef}
 The \emph{canonical lift $\mathscr{E}$} of an elliptic curve $E$ over $\mathbb{F}_q$ is
an elliptic curve over $\mathbb{Q}_q$ such that $End(\mathscr{E}) \simeq End(E)$.
\end{mydef}

The existence of such a canonical lift is vital because of the isomorphic endomorphism rings. This
enables us to lift the endomorphisms, especially the Frobenius which we are interested in.

\begin{thm}
 \textbf{(Lubin-Serre-Tate)} Let $E/\mathbb{F}_q$ be an elliptic curve with $j$-invariant $j(E)$ and
$\sigma$ the $p^{th}$ Frobenius on $\mathbb{Q}_q$ then the system of equations
$$ \Phi_p(x, \sigma(x)) = 0 \quad x \equiv j(E) \, (mod\, p)$$
where $\Phi_p$ is the $p$-th modular polynomial has a unique solution $J \in \mathbb{Z}_q$ 
which is the $j$-invariant of the canonical lift $\mathscr{E}$ of $E$.
\end{thm}
The latter theorem gives an efficient way of calculating the $j$-invariants, in addition it has
been shown \cite{Deuring} that the canonical lift always exists and is unique (up to isomorphism).

Knowing $j(\mathscr{E})$ we can explicitly write out the Weierstrass equation for $\mathscr{E}$, but
instead of lifting $E$ to $\mathscr{E}$ directly we can consider all its conjugates
$$E, E^\sigma, E^{\sigma^2}, \ldots, E^{\sigma^{n-2}}, E^{\sigma^{n-1}}. $$
Letting $E^{\sigma^i} = E^i $ we get a sequence of maps
$$ E \overset{\sigma}{\rightarrow} E^1 \overset{\sigma}{\rightarrow} E^2 \overset{\sigma}{\rightarrow}
\ldots \overset{\sigma}{\rightarrow} E^{n-1}. $$
Where the composition is the $q^{th}$ Frobenius $\phi_q = \sigma \sigma \ldots \sigma: E \rightarrow E$.
Recall that the $\deg \sigma = p$.

Since the endomorphism rings are isomorphic we can lift every Frobenius on $E$ to a
Frobenius on $\mathscr{E}$. We thus obtain a commutative diagram

$$
\xymatrix {
  \mathscr{E} \ar[d]^\pi \ar[r]^\sigma & \mathscr{E}^1 \ar[d]^\pi \ar[r]^\sigma & \ldots \ar[r]^\sigma & \mathscr{E}^{n-1} \ar[d]^\pi \ar[r]^\sigma & \mathscr{E} \ar[d]^\pi \\
  E \ar[r]^\sigma & E^1 \ar[r]^\sigma &\ldots \ar[r]^\sigma & E^{n-1} \ar[r]^\sigma & E \\
}
$$

Since the lifted Frobenius also has degree $p$ we have that
$$\Phi_p(j(\mathscr{E}^{i+1}), j(\mathscr{E}^{i})) = 0 \quad j(\mathscr{E}^i) \equiv j(E^i) \, (mod\, p). $$
We thus define a function $\Theta: \mathbb{Z}_q^n \rightarrow \mathbb{Z}_q^n$ by
$$\Theta(x_0, x_1, \ldots, x_{n-1}) = (\Phi_p(x_0, x_1), \Phi_p(x_1, x_2), \ldots, \Phi_p(x_{n-1}, x_0)).$$
Note that the roots of $\Theta$ are the $j$-invariants of our lifted curves
$$\Theta(j(\mathscr{E}^{n-1}), j(\mathscr{E}^{n-2}), \ldots, j(\mathscr{E}^0)) = (0, 0, \ldots, 0) $$
so by solving $\Theta(\bar{x}) = 0$ using a multivariate Newton-Raphson iteration, we can
recover the $j$-invariants to desired precision. Setting up the Jacobian matrix $J_\Theta$
of $\Theta$, the iteration is given by
$$ \bar{x}_{n+1} = \bar{x}_n - J_\Theta^{-1} \Theta(\bar{x}_n) $$
where the matrix $J_\Theta(x_0, x_1, \ldots, x_{n-1})$ is given as 

$$
\begin{pmatrix}
  {\partial \over \partial x_0} \Phi_p(x_0, x_1) & {\partial \over \partial x_1} \Phi_p(x_0, x_1) & 0 & \ldots & 0 & 0 \\
  0 & {\partial \over \partial x_1} \Phi_p(x_1, x_2) & {\partial \over \partial x_2} \Phi_p(x_1, x_2) & 0 & \ldots & 0 \\
  0 \\
  \vdots & & \ddots & & & \vdots \\
  0 \\
  {\partial \over \partial x_0} \Phi_p(x_{n-1}, x_0) & 0 & \ldots & 0 & 0 & {\partial \over \partial x_{n-1}} \Phi_p(x_{n-1}, x_0) \\
\end{pmatrix}
$$

The elements on the diagonal of this matrix are given by
$$ \frac{\partial}{\partial x_i} \Phi_p(x_i, x_{i+1}) \quad i =  0, 1, \ldots, n-1$$
recalling the congruence relation from Theorem \ref{kroenecker} we calculate

\begin{eqnarray}
 \frac{\partial}{\partial x_i} \Phi_p(x_i, x_{i+1}) &=& \frac{\partial}{\partial x_i}(x_i^p-x_{i+1})(x_i-x_{i+1}^p)\nonumber \\
						    &=& p x_i^{p-1}(x_i-x_{i+1}^p)+(x_i^p-x_{i+1})\nonumber \\
						    &\equiv& x_i^p-x_{i+1}\, (mod\, p) \nonumber
\end{eqnarray}
A similar calculation for the elements on the semi-diagonal shows that
$$ \frac{\partial}{\partial x_{i+1}} \Phi_p(x_i, x_{i+1}) \equiv x_{i+1}^p - x_i \, (mod\,p). $$
The Jacobian matrix modulo $p$ thus has non-zero diagonal elements
\begin{eqnarray}
 \frac{\partial}{\partial x_i} \Phi_p(j(\mathscr{E}^{i+1}), j(\mathscr{E}^i)) &\equiv& j(\mathscr{E}^{i+1})^p-j(\mathscr{E}^i) \nonumber \\
									      &\equiv& j(\mathscr{E}^i)^{p^2}-j(\mathscr{E}^i) \nonumber \\
									      &\not\equiv& 0 \quad (mod\, p) \nonumber
\end{eqnarray}
while the elements on the semi-diagonal are all zero
\begin{eqnarray}
 \frac{\partial}{\partial x_{i+1}} \Phi_p(j(\mathscr{E}^{i+1}), j(\mathscr{E}^i)) &\equiv& j(\mathscr{E}^i)^p-j(\mathscr{E}^{i+1}) \nonumber \\
										  &\equiv& j(\mathscr{E}^i)^p-j(\mathscr{E}^i)^p \nonumber \\
										  &\equiv& 0 \quad (mod\, p) \nonumber
\end{eqnarray}
By similar means we can show that the bottom left element is also $0$ modulo $p$, so in fact the Jacobian matrix
$J_\Theta$ is a diagonal matrix modulo $p$.
It is therefore certainly invertible and the Newton-Raphson iteration can be performed.

Because of the Hasse bound we only need to calculate the lifting to a desired precision. Letting $\tau$
be the Frobenius trace
$$\mid \tau \mid \leq 2\sqrt{q} = 2p^{\frac{n}{2}} \leq p^{\frac{n}{2}+1} $$
we have that the $j$-invariant must be lifted with precision $\frac{n}{2}+1$ in order to accurately recover
the Frobenius trace.

\subsection{Recovering the trace}
Let $\phi$ be the $q^{th}$ Frobenius and $\phi^*$ be the induced Frobenius on differentials, 
we have that $c = tr(\phi) = \phi + \widehat{\phi}$ so investigating the
action of the Frobenius on the invariant differential $\omega$ we see that
\begin{eqnarray}
 [tr(\phi)]^*(\omega)&=& [tr(\phi)](\omega) \nonumber \\
		     &=& (\phi + \widehat{\phi})^*(\omega) \nonumber \\
		     &=& \phi^*(\omega) + \widehat{\phi}^*(\omega) \nonumber \\
		     &=& \widehat{\phi}^*(\omega) \nonumber
\end{eqnarray}
Where the last equality is using the fact that $\phi^* = 0$ since $\phi$ is inseparable, we thus
get that $\widehat{\phi}^*(\omega) = c\omega$.
Recall from Chapter \ref{invariant} that $\frac{dx}{y}$ is also holomorphic and invariant under translation,
so for the rest of this section we define our invariant differential as such
$$ \omega = \frac{dx}{y}. $$
Instead of working with $\phi$ we work with its dual $\widehat{\phi}$ and the dual
of the $p^{th}$ Frobenius $\widehat{\sigma}$. This is because we will later
be lifting the kernel of $\sigma$ which is trivial. But the dual of the Frobenius is separable
and its kernel can be lifted. In addition the trace of $\widehat{\sigma}$ is equal to the trace of $\sigma$.
Our diagrams will be turned around so we get commutative
squares
$$
\xymatrix {
  \mathscr{E}^{i+1} \ar[r]^{\widehat{\sigma}_{i+1}} \ar[d]^\pi & \mathscr{E}^i \ar[d]^\pi \\
  E^{i+1} \ar[r]^{\widehat{\sigma}_{i+1}} & E^i 
}
$$

Letting $\widehat{\mathscr{F}_q}$ be the lifted of the dual $q^{th}$ Frobenius we have that
$\widehat{\mathscr{F}_q} = \widehat{\sigma} \widehat{\sigma} \ldots \widehat{\sigma}$.
So if $\omega_i = \omega^{\sigma^i}$ we have that $\widehat{\sigma}_i^*(\omega_i) = c_i \omega_{i+1}$.
A calculation then yields, using that $\sigma_i^* = c_i$
\begin{eqnarray}
  \widehat{\mathscr{F}}_q(\omega) &=& (\widehat{\sigma}_1 \circ \widehat{\sigma}_2 \circ \ldots \circ \widehat{\sigma}_{n-1})(\omega) \nonumber \\
			      &=& ([c_1] \circ \ldots \circ [c_{n-1}](\omega) \nonumber \\
			      &=& [c_1\ldots c_{n-1}](\omega) \nonumber
\end{eqnarray}
Since $\widehat{\mathscr{F}}_q(\omega) = c \omega$ we have that
$$ c = \prod_{i=1}^{n-1} c_i \quad (mod\, q). $$
It then remains for us to calculate each $c_i$ for every lifted $p^{th}$ Frobenius
endomorphism $\widehat{\sigma}_i$.

From \cite{AEC} we have that there exists a commutative triangle
$$
\xymatrix{
  \mathscr{E}^{i+1} \ar[rr]^{\widehat{\sigma}_{i+1}} \ar[dr]^{v_{i}} && \mathscr{E}^i \\
  & \mathscr{E}^{i+1}/\ker(\widehat{\sigma}_{i+1}) \ar[ur]^{\lambda_i} & 
}
$$

From formulas due to V\'{e}lu (see \cite{Velu} or \cite{Sato}) we can calculate the map
$v_i$ and the Weierstrass equation for the curve $\mathscr{E}^{i+1}/\ker(\widehat{\sigma}_{i+1})$.
This means that in order to investigate the action of
$\widehat{\sigma}_{i+1}$ on the invariant differential for all $i$ amount to investigating
how the composition $\lambda_i v_i$ acts. In addition, if we let $v_i^*$ be the map induced 
on differentials then by the formulas of V\'{e}lu it has trivial action on the invariant differential $\omega$.
It is then enough to calculate how the isomorphism $\lambda_i$ acts on the invariant differential. 
Given the Weierstrass equations for our curves
$$ \mathscr{E}^{i+1}/\ker(\widehat{\sigma}_{i+1}): y^2 = x^3 + \alpha_{i+1}x + \beta_{i+1}$$
$$ \mathscr{E}^i: y^2 = x^3 + a_i x + b_i $$
$$ \lambda_i: \mathscr{E}^{i+1}/\ker(\widehat{\sigma}_{i+1}) \rightarrow \mathscr{E}_i. $$
Here the coefficients $\alpha_{i+1}$ and $\beta_{i+1}$ are given by
$$\alpha_{i+1} = (6-5p)a_{i+1}-30(h_{i,1}^2-2h_{i,2})$$
$$\beta_{i+1}  = (15-14p)b_{i+1}-70(3h_{i,1}h_{i,2}-h_{i,1}^3-3h_{i,3})+42a_{i+1}h_{i,1}$$
where $h_{i,k}$ is the coefficient of $x^{d-k}$ in the polynomial $H_i(x)$ from \ref{satohdiv}.

The function which preserves the coefficients of the curves is given by
$$(x,y) \mapsto (u_i^2 x, u_i^3 y). $$
Calculating how this acts on the curve we get the curve
$$ y^2 = x^3 + u_i^{-4} a_i x + u_i^{-6} b_i$$
comparing coefficients we get the two equalities
$$ u_i^{-4} a_i = \alpha_{i+1} \text{ and } u_i^{-6} b_i = \beta_{i+1}. $$
Solving for $u_i^2$ we get
$$ u_i^2 = \frac{\alpha_{i+1} b_i}{\beta_{i+1} a_i} $$
and we have our isomorphism. Now for calculating how $\lambda_i$ acts on the holomorphic
differential $\omega=\frac{dx}{y}$ we recall from Chapter \ref{diff} and calculate
\begin{eqnarray}
 \lambda_i^*(\frac{1}{y} dx) &=& \lambda_i^*(\frac{1}{y}) d(\lambda_i^*(x)) \nonumber \\
			     &=& \frac{1}{u_i^3 y} d(u_i^2 x) \nonumber \\
			     &=& \frac{u_i^2 dx}{u_i^3 y} \nonumber \\
			     &=& u_i^{-1} \omega \nonumber
\end{eqnarray}
From our commutative triangle we thus have that
$$ \widehat{\sigma_i}^*(\omega_i) = c_i = (\lambda_i v_i)^*(\omega_i) = \lambda_i^*(\omega_i) = u_i^{-1}\omega_{i+1}$$
so we have found $c_i$ for all $i$, its square is given by
$$ c_i^2 = \frac{\beta_{i+1} a_i}{\alpha_{i+1} b_i}. $$
By our product formula for $c$ we have the square of $c$ given as
$$ c^2 = \prod_{i=1}^{n-1} c_i = \prod_{i=1}^{n-1} \frac{\beta_{i+1} a_i}{\alpha_{i+1} b_i}. $$
Taking the square root we obtain the trace $c$ up to sign.

\subsection{Factor of the division polynomial} \label{satohdiv}
Recall that in order to calculate the curve equation for $\mathscr{E}_{i+1}/\ker(\widehat{\sigma}_{n+1})$
we needed coefficients of the factor
$$H_i(x) = \prod_{(x',y')\in \ker(\widehat{\sigma}_{i+1})} (x-x')$$
of the $p^{th}$ division polynomial $\Psi_{i+1}$. Here the product is taken over all points in
the kernel excluding the identity $O$ and up to sign. Since $\#\ker(\widehat{\sigma}_{i+1}) = p$ we have
that $\deg(H_i(x)) = \frac{p-1}{2}$.

The following result is due to Satoh and serves as a modified Hensel lifting \cite{Robert}, it can be found
in \cite{Satoh} and \cite{Handbook}.
\begin{prop}
 Let $p\geq 3$ be a prime and $\Psi(x) \in \mathbb{Z}_p[x]$ such that $\Psi'(x) \equiv 0\, (mod\, p)$ and
$\Psi'(x) \not\equiv 0\, (mod\, p^2)$. Let $h(x) \in \mathbb{Z}_p[x]$ be a monic polynomial such that
\begin{enumerate}
  \item $h(x) \,(mod\,p)$ is square-free and relative prime to $\frac{\Psi'(x)}{p}\,(mod\,p)$.
  \item $\Psi(x) \equiv f(x)h(x)\,(mod\,p^{n+1})$
\end{enumerate}
Then the polynomial
$$H(x) = h(x) + \left(\left(\frac{\Psi(x)}{\Psi'(x)} h'(x)\right)\,(mod\, h(x))\right)$$
satisfies $H(x) \equiv h(x) (mod\, p^n)$ and $\Psi(x) \equiv F(x)H(x) (mod \, p^{2n+1})$ for some $F(x)$.
\end{prop}
This gives us the following algorithm, as seen in \cite{Handbook}. So let the function
$liftkernel(\Psi_p, N)$ be given as
\begin{algorithmic}
\REQUIRE $p$-division polynomial $\Psi_p(x)$ of $\mathscr{E}$ and precision $N$
\IF {$N=1$} 
        \STATE $H(x)\gets h(x)$ such that $\Psi_p(x) \equiv \delta h(x)^p (mod\, p)$
\ELSE
        \STATE $N'\gets \lceil\frac{N-1}{2}\rceil$
	\STATE $H(x)\gets liftkernel(\Psi_p(x), N')$
	\STATE $H(x)\gets H(x) + \left(\frac{H'(x)\Psi_p(x)}{\Psi_p'(x)} \, mod\, H(x) \right)\, mod\, p^N$
\ENDIF
\RETURN $H(x)$
\end{algorithmic}
This ends the algorithm of Satoh and we give a short summary: starting out with
an elliptic curve $E$ of the form $$y^2 = x^3 + ax + b$$ we calculate the $j$-invariants of
all its conjugates $E^i$. We then calculate the $j$-invariants of all the canonical lift $\mathscr{E}^i$,
this is the $q$-adic integer obtained from the Newton-Raphson iteration. By properties of the
invariant differential $\omega$ it is sufficient to calculate how the isomorphism $\lambda_i$ acts on
$\omega$
$$\lambda_i^*(\omega) = c\omega.$$
Then $c$ is given by a product of the curve coefficients of
$\mathscr{E}^{i+1}/\ker(\widehat{\sigma}_{i+1})$ and $\mathscr{E}^i$.
The time complexity of this algorithm is $O(n^5)$ where $n$ is such that $q = p^n$.