%plain TeX
\normalbaselineskip=1.6\normalbaselineskip\normalbaselines
\magnification=1200
\def\max{\mathop{\rm max}}
\def\min{\mathop{\rm min}}
\def\rk{\mathop{\rm rk}}
\def\uple#1{(#1_1,\ldots,#1_n)}
\def\puple#1{(#1_1:\ldots:#1_n)}
\def\pmb#1{\setbox0=\hbox{#1}%
 \kern-.025em\copy0\kern-\wd0
 \kern.05em\copy0\kern-\wd0
 \kern-.025em\raise.0433em\box0 }
\def\w{\pmb{$\omega$}}
\def\Gm{{\bf G}_m}
\def\ra{\rightarrow}
\def\Z{{\bf Z}}
\def\topn{\buildrel{p^n}\over\to} 
\def\Q{{\bf Q}}
\def\C{{\bf C}}
\def\F{{\bf F}}
\def\zmp{\Z/p\Z}
\def\O{{\cal O}}
\def\isom{\cong}
\def\Ext{\mathop{\hbox{Ext}}}
\def\mod{\mathop{\rm mod}\nolimits}
\def\Qp{{\bf Q}_p}
\def\Qpb{\bar{\bf Q}_p}
\def\Cp{{\bf C}_p}
\def\P{{\bf P}}
\def\Hom{\mathop{\rm Hom}\nolimits}
\def \H{{\cal H}}
\def \X{{\cal X}}
\def\Spec{\mathop{\rm Spec}\nolimits}
\def \bs{\bigskip}
\def\Gal{\mathop{\rm Gal}\nolimits}
\def\End{\mathop{\rm End}\nolimits}
\def\limproj{\mathop{\oalign{\hfil$\rm lim$\hfil\cr
 $\longleftarrow$\cr}}}
\def \l{\lambda}
\def\bk{\bar{k}}
\def \ra{\rightarrow}
\def \op{\frac{1}{p}}
\def \st{\stackrel}
\def \da{\downarrow}
\def \R{{\bf Rings}}
\def \d{\delta}
\def \s{\sigma}
\def \a{\alpha}
\def \b{\beta}
\def \x{\chi}
\def \t{\tau}
\def \z{\zeta}
\def \con{\equiv }
\def \e{\epsilon}
\def \bC{\bar{C}}
\def \bX{\bar{X}}
\def \k{\kappa}
\def \bF{{\bar{\bf F}}_p}

{\bf Relating the Smart-Satoh-Araki and Semaev approaches
to the discrete logarithm problem on anomalous elliptic curves }
\medskip
\centerline{\bf Jos\'e Felipe Voloch}
\bs

Very recently it was announced that Semaev [Se], Smart [Sm] and Satoh and 
Araki [SA] gave a solution of the discrete logarithm problem on elliptic curves 
over $\F_p$ with $p$ points, $p$ a prime, the so-called anomalous curves.
The discrete logarithm problem is to find an procedure so that, given 
$P,Q$ points on the curve, one finds an integer $m$ with $Q=mP$ or shows
that $m$ does not exist. This brief note relates the Smart-Satoh-Araki and
Semaev approaches.

Let $E/\F_p$ be an elliptic curve with $p$ points. We need to provide
a map $\a: E(\F_p) \to \Z/p\Z$. Semaev (see also R\"uck [R]) proceeds
as follows. Fix $P \in E(\F_p), P \ne 0$ and let $\omega = df/f$, where
$(f)= p(P-0)$, so $\omega$ is a holomorphic differential. 
Given $Q \in E(\F_p), Q \ne 0$, find likewise $f_Q$ with
divisor $p(Q-0)$ and define $\a(Q) = df_Q/(f_Q\omega)$. The point of the
algorithm is that $f,f_Q$ can be computed quickly.

Smart and Satoh and Araki proceed differently. They take a lift ${\bf E}$
of $E$ to $\Z/p^2$ and points ${\bf P},{\bf Q}$ lifting $P,Q$. They define
$\a'(Q) = \l(p{\bf Q})/\l(p{\bf P})$, where $\l$ is the elliptic logarithm
$\l:{\bf E}_1=\ker({\bf E} \to E) \to p\Z/p^2$, provided the expression makes
sense (see below). The definition of $\l$ depends 
on a choice of holomorphic differential $\w$ on ${\bf E}$ and can be
computed quickly. According to 
Tate [T], $\w$ can be fixed so it lifts $\omega$ and so that $exp(\l):
{\bf E}_1 \to (1+p\Z)/p^2$ is an isomorphism. With this choice of $\w$,
Tate defines $q = exp(\l(p{\bf P}))$, which is the Serre-Tate parameter
([LST],[K]) in this special case. It follows that 
$q-1=\l(p{\bf P}) \in p\Z/p^2$ and that $\l(p{\bf Q}) = (q-1)n$ if
${\bf Q}=n{\bf P}$. Therefore, unless $q=1 \in \Z/p^2$,
$\a' = \a$. This relates the two maps and shows that the method
of Smart and Satoh and Araki fails precisely when $q=1 \in \Z/p^2$, that
is, when ${\bf E}$ is the canonical lift of $E$. In the unlikely event
this happens they can run their algorithm on another lift and still
solve this instance of the discrete logarithm problem.

{\bf Acknowledgements:}
The author would like to thank
the NSA (grant MDA904-97-1-0037) for financial support.

\bigskip
\centerline{\bf References.}
\bigskip
\noindent
[K] N. M. Katz, {\it Serre-Tate local moduli}, Springer LNM 868 (1981)
138-202.
\medskip
\noindent
[LST] J. Lubin, J-P. Serre and J. Tate, {\it Elliptic curves and formal
groups},
Proc. of the Woods Hole summer institute in algebraic geometry 1964.
Unpublished. Available at http://www.ma.utexas.edu/users/voloch/lst.html.
\medskip
\noindent
[R] H.-G. R\"uck, {\it On the discrete logarithm problem in the
divisor class group of curves}, preprint, 1997.
\medskip
\noindent
[Se]I. A. Semaev, {\it Evaluation of discrete logarithms on some
elliptic curves}, Math. Comp, to appear.
\medskip
\noindent
[Sm] N. Smart, {\it The discrete logarithm problem on elliptic curves of
trace one}, preprint HP-LABS Technical Report (Number HPL-97-128), 1997.
\medskip
\noindent
[SA] T. Satoh and K. Araki, {\it Fermat quotients and the polynomial
time discrete log algorithm for anomalous elliptic curves}, preprint, 1997.
\medskip
\noindent
[T] J. T. Tate, {\it Letter to B. Dwork}, November, 15th, 1968. 
\medskip
\noindent
Dept. of Mathematics, Univ. of Texas, Austin, TX 78712, USA
\smallskip
\noindent
e-mail: voloch@math.utexas.edu



\end