
\documentstyle[12pt,titlepage]{article}
\title{Elliptic Curves Over Finite Fields}
\author{Eric Von York\thanks{Under the direction of Professor Philippe
Loustaunau.}\\George Mason University}
\date{May 07, 1992}
\begin{document}
\maketitle
\begin{abstract}
In this paper I will explain the implementation and improvements of three
algorithms which are designed to determine the number of points on an
elliptic curve $E$ over a finite field.  The points on an elliptic curve form
an Abelian group under the chord tangent law of composition.  Using a 
theorem proven by Hasse, one can determine the interval which contains the
group order. The first algorithm \cite{Shanks} determines the group
order by examining the orders of points on $E$. The second algorithm
\cite{Schoof} examines the properties of the torsion groups and the group
of endomorphisms on E to determine the number of points on $E$. The third algorithm
\cite{Muller} is a combination of the first two. The algorithms were
implemented using the computer algebra system {\em Maple}. The fields
considered will be of the form $\bf{Z}_{p}$, where p is a prime
and  $p \approx 10^{20}$.
\end{abstract}

\section{Background}

\subsection{Introduction}

In 1976 W. Diffie and M. Kellman proposed the idea of Public Key
Cryptography. Before these systems were invented, if a person knew how
to encode a message, this implied that they knew how to decode the
message. However, with public key systems, knowledge of the encoding
algorithm provides no information concerning the deciphering algorithms.
With this feature, public key systems could allow for secure
communication between two totally unaquainted parties. This type of
cryptosystem is better suited for large companies where trying to keep a
particular key secret would be impractical.

Since the discovery of public key cryptography in 1976, their popularity
has grown rapidly.  Traditionally these systems were embedded in fields
of the form $\bf{Z}_{p}$, where $p$ is a prime and $p$ may be as large as
$10^{40}$. However it was proposed by Koblitz in \cite{KoblitzI}, that
public key systems can be embedded in the group of points on an elliptic
curve over a finite field.  So far, the elliptic curve cryptosystems
have been harder to ``crack'' than their $\bf{Z}_{p}$ counterparts.

Essential to the implementation of a cryptosystem on an elliptic curve
is a knowledge of the number of points on this curve.  In this paper
\footnote{For more details on section 1 see \cite{CRD}}  I
will discuss three methods that are currently used to determine this
group order as well as their implementation in {\em Maple}, and some
improvements to them.


\subsection{Elliptic Curves}
Consider $f$ in $k[x,y]$, where $k$ is a field and $f$ is a cubic
in generalized Weierstrass form given by
\begin{displaymath}
 f = y^{2}+a_{1}xy+a_{2}y-x^{3}-a_{3}x^{2}-a_{4}x-a_{6}.
\end{displaymath}

If $k$ is a field, then we will denote its algebraic closure by
$\overline{k}$. If the characteristic of $k$ is not 2 or 3, we transform
$f$ into the following function $E$ which we define as follows:
\newtheorem{df}{Definition}
\begin{df}
A curve $E$ in $k[x,y]$ is called an elliptic curve if it is given by
\begin{equation}
E = y^{2} - x^3 - Ax - B                          \label{e-curve}
\end{equation}
where the characteristic\footnote{Throughout
these notes we will assume the characteristic of $k$ is not 2 or 3.} of $k$ is not 2 or 3.\end{df}

     We will also require $E$ to be non-singular. That is, we require that
the partial derivatives do not vanish simultaneously for any point $(a,b)$
on $E$. It is easy to show that this is equivalent to requiring that the
equation $x^{3}+Ax+B=0$ has no multiple roots. Using resultants we can
express this as the following:
\newtheorem{lem}{Lemma}
\begin{lem}
 E is non singular if and only if $4A^{3} + 27B^{2}$ is not equal to
\mbox{zero in $k$.}
\end{lem}

\subsubsection{The Chord Tangent Law of Composition}

By examining the locus of the equation $E=0$  in $\bf R^{2}$, one can see
that its graph will be symmetric about the $x$ axis \footnote{In what
follows we will use the fields $\bf Q$ and $\bf R$ since they allow us to
visualize many of the concepts; however, our arguments can be extended to
arbitrary fields.}.  In fact, it will be one of the two graphs shown
in figure 1 (provided it is non-singular).

\begin{figure}[hbt]
   \vspace{3in}
   \caption{The two types of non-singular elliptic curves over \bf $R^{2}$}
\end{figure}

Let's consider the line in $\bf R^{2}$ given by the equation $y=mx+b$ where
$m,b \in \bf Q$.

\begin{lem}
If $y \neq 0$ and $y=mx+b$ intersects equation (\ref{e-curve}) at $P_{1}$ and
$P_{2}$, and $P_{1}, P_{2} \in \bf Q^{2}$,  then $y=mx+b$ will
intersect equation (\ref{e-curve}) in a third point $P_{3} \in \bf Q^{2}$.
\end{lem}

In words, we are saying that given two rational points on E, that can be
connected by a non-verticle line, then there is a third point of intersection
on this line and E, and it too will be rational. The proof of this lemma
follows from simple linear algebra and the fact that all coefficients
are in $\bf Q$. We can see that we have a way to associate two given points
in $\bf Q^{2}$ to another point in $\bf Q^{2}$ for all cases except when the
two points lie on the line $ x = c, c \in \bf Q$.

To remedy this we view E over the projective plane $\bf P^{2}$.  With this
convention we now obtain the system of equations, $x = wc$,
$wy^{2} = x^{3} + Aw^{2}x + Bw^{3}$.  This system has the two solutions
corresponding to the points in $\bf Q^{2}$ plus the point at infinity given
by $ 0:1:0 $. When viewed in this manner, each verticle line intersects
the graph of $E$ in three points. In light of this, let us make the
following:

\begin{df}
Let $k$ be a field and define $E(k) = \{(a,b) \in k^{2} \mid E(a,b) = 0\}
\cup \{ \cal O \}$ where $ \cal O$ denotes the point at infinity, which is
on every line of the form $x=c, c \in k$.
\end{df}

Given any two points in $E(k)$ we have a way to associate to these two
points a third one. This is given in the following:
\begin{df}
Let $P,Q \in E(k)$. We define $PQ$ to be the third point of intersection
of the line determined by $P$ and $Q$ , with the elliptic curve $E(k)$. We
also make the convention that $\cal O \cal O$ = $\cal O$.
\end{df}

We are now ready to define the chord tangent law of composition on our
elliptic curve.
\begin{df}
Let $P,Q \in E(k)$ where $k$ is a field. Then we define
\begin{displaymath}
P+Q = {\cal O}(PQ)
\end{displaymath}
\end{df}

>From this point on, when we speak of adding two points in $E(k)$, we mean
adding in the sense of Definition 4. This process is depicted in figure 2.

\begin{figure}[hbt]
   \vspace{3in}
   \caption{The chord tangent law of composition in \bf $R^{2}$}
\end{figure}


\subsubsection{General Equations for Addition of Points on $E(k)$}
\label{generaladd}

When adding two points $P=(x_{1},y_{1})$ and $Q=(x_{2},y_{2})$ in $E(k)$
we must consider the following three cases:

\begin{enumerate}
   \item If $x_{1} = x_{2}$ and $y_{1} \neq y_{2}$
   \item If $x_{1} = x_{2}$ and $y_{1} = y_{2}$
   \item If $x_{1} \neq x_{2}$
\end{enumerate}

Case 1 corresponds to two points on a line of the form $x=c$, and in
this case $P+Q = \cal O$. Examination of this case also shows that if
$P=(a,b)$, then $-P = (a,-b)$.

Case 2 and 3 both result from intersecting the line $y = mx + b$
with $E=0$.  In case 2 the line is tangent to $E$ and the slope is found
by implicitly differentiating $E=0$ and is given by
\begin{equation}                      \label{tanslope}
m = (3x_{1}^{2}+A)/2y_{1}.
\end{equation}
In case 3 the slope is determined using $P$ and $Q$ and is given by
\begin{equation}                      \label{regslope}
m = (y_{2}-y_{1})/(x_{2}-x_{1}).
\end{equation}
If we substitute $mx+b$ for $y$ in $E=0$ we obtain the following:
\begin{displaymath}
x^{3}-m^{2}x^{2}+(2mB+A)x+B^{2}+b=0
\end{displaymath}

We know that $x_{1}$ and $x_{2}$ are both roots of this equation, and
from this it follows that the third root $x_{3}$ is given by
\begin{equation}               \label{addx}
x_{3}=-x_{1}-x_{2} + m^2
\end{equation}
We can rewrite $y=mx+b$ using $P$ as follows:
\begin{displaymath}
y-y_{1}=m(x-x_{1})
\end{displaymath}

Using this equation and the chord tangent law of composition we derive
the following equation for $y_{3}$:
\begin{equation}                \label{addy}
y_{3}=-y_{1}+m(x_{1}-x_{3})
\end{equation}

Hence, the addition of two points in $E(k)$ can be given by equations
(\ref{addx}) and (\ref{addy}). And the slope will be equation
(\ref{tanslope}) if in case 2 and equation (\ref{regslope})
if in case 3.

>From the previous definitions it follows that:
\begin{itemize}
\item If $P,Q \in E(k)$ then $PQ \in E(k)$
\item $\cal O + \cal O = \cal O$
\item $P+Q = Q+P$
\item $P+ {\cal O} = P$
\item For $P=(a,b) \in E(k), -P$ will be the point of intersection of
the line $x=a$ and $E=0$ which is not $\cal O$.
\end{itemize}

What doesn't follow so easily from the definitions is the fact that this
operation is associative.  There are several ways to prove associativity;
one of these ways is to establish a bijection between a subgroup of the
free Abelian group generated by $E(k)$ and the actual points on $E(k)$.
The proof of associativity in $E(k)$ is quite long and can be found
in sections 4 and 5 of \cite{CRD}.

\newtheorem{thm}{Theorem}       \label{Eisgroup}
\begin{thm}
E(k) forms an Abelian group under the chord tangent law of composition.
$\cal O$ is the identity.
\end{thm}
The proof of this follows from the comments made above.


\subsection{Rational Functions and the Group $E(k)$}

In this section we  will look at several definitions and theorems
concerning elliptic curves and their group structure. These will be needed
for the algorithms presented in later sections of these notes.

\subsubsection{Rational functions}

Note that since $E=0$ holds for points in $E(k)$, and since we will only
be viewing polynomials over $E(k)$, we can view the polynomials as
elements in
\begin{equation}
k[x,y]/<E>.
\end{equation}

\begin{df}
If f is an element of $k[x,y]/<E>$, we call $f$ a polynomial on $E$. We will
sometimes denote $k[x,y]/<E>$ as $k[E]$.
\end{df}

There are several extensions of notions that pertain to polynomials in
$\bf{R}[x]$ (ie:degree, differentiation, multiplicity of roots and poles)
that have analogs for polynomials in $k[E]$; however, all of these notions
must take into account the fact that $E=0$ for points in $E(k)$.

Using the notion of a norm function (similar to the norm for $C$), we
can show that $k[E]$ is an integral domain.  Thus, we are able to construct
the field of fractions, which we will denote as $k(E)$.

\begin{df}
If $r \in k(E)$ and $P$ is a finite point of $E(k)$, ie, $P \neq \cal O$,
then we say that $r$ is finite at $P$ if there exists an $f,g \in k[E]$,
such that $f/g = r$ and $g(P) \neq 0$.
Furthermore, the rational functions that are finite at P form a ring.
\end{df}

\begin{df}
Let $r \in k(E)$, we say that $r$ has a zero at $P \in E(k)$ if $r(P)=0$,
and we say that $r$ has a pole at P if $r(P) = \infty$.
\end{df}

Next, we would like to extend the idea of a rational function on E(k) to
that of a rational map on E(k).

\begin{df}
A rational map $M$ on $E(k)$ is a pair $(u,v)$ where $u,v \in k(E)$ and
\begin{displaymath}
v^{2} = u^{3} + Au + B.
\end{displaymath}
\end{df}

By the above relation for $u$ and $v$ we can see that if $u(P) = \infty$,
then $v(P) = \infty$.  Hence, if we define $(\infty,\infty)=\cal O$, then
$M$ actually does define a map from $E(k)$ to $E(k)$. When we add two
rational maps using the equations presented in section \ref{generaladd}
the result is also a rational map.

As stated previously, we can define the notion of multiplicity of a
rational function $r \in k(E)$ at a given $P \in E(k)$.  In order to do
this we state the following:
\begin{thm}                             \label{unif}
For each point $P \in E(k)$ there is a rational function $u \in k(E)$,
such that $u(P)=0$ and $u$ possesses the following property; if $r \in k(E)$,
$r(P) = 0$, and $r$ is not the zero function, then $$ r = u^{d}s$$ for some
integer $d$, and some rational function s that is finite and nonzero at
$P$. The integer $d$ is unique.
\end{thm}
Using this theorem, we can define the multiplicities of zeros and poles of
functions in $k(E)$ by the following:

\begin{df}
A function $u$ that satisfies theorem \ref{unif} is called a uniformizer
at $P$. If $r \in k(E)$ and $u$ is a uniformizer at $P$, and
$r=u^{d}s$,where $s(P) \neq 0$, we say that the order of $r$ at $P$ is d.
Furthermore, we define the multiplicity of a zero of $r$ at $P$ to be
the order of $r$ at $P$. We define the multiplicity of a pole at $P$ to be
the negative of the order of $1/r$ at $P$.
\end{df}

Using the addition formulas given by equation (\ref{addx}) and equation
(\ref{addy}) we can derive rational functions that represent the addition
of a point $P \in E(k)$ to itself. This idea gives us the following:

\begin{df}
We define $g_{n}(P) = {\bf x}(nP)$  and $h_{n}(P) = {\bf y}(nP)$,
where $g_{n}$ and $h_{n}$ are in $k(E)$, and the multiplication is done
using the formulas presented in section \ref{generaladd}.
\end{df}

For example, if $P=(x,y)$ then, using equation (\ref{addx}), $g_{2}$ is given as
\begin{displaymath}                      \label{duplicate}
g_{2} = {\bf x}(2P) = \frac{x^{4}-2Ax^{2}-8Bx+A^{2}}{4(x^{3}+Ax+B)}
\end{displaymath}

Using this formula for $g_{2}$ and equation (\ref{addy}), we can determine
$h_{2}$. As we will see later in these notes, the $g_{n}$'s and $h_{n}$'s
are related to subgroups of $E(k)$.

\subsubsection{The Torsion Groups on E(k)}

\begin{df}
Let $n \in  \bf Z $, define
$E[n] = \{P\in E(k) \mid nP = \cal O\}$
\end{df}

It is easy to see that $E[n] \neq \emptyset$, since $n{\cal O} = {\cal O}
\in E[n]$ for all n. These torsion groups also have the following important
properties:

\begin{thm}
$E[n]$ contains a finite number of points for all n.
\end{thm}

\begin{thm}                    \label{isom}
Let $k$ be algebraically closed. If $(n,p) = 1$ , then
$\mid E[n] \mid = n^{2}$ and $E[n] \cong {\bf Z_{n}} \times {\bf Z_{n}}$.
\end{thm}

These results indicate that the groups $E[n]$ will be very useful
in examining the order of $E(k)$, especially over finite fields. In these
notes we will see that there are polynomials in $k[E]$ that are
intimately related to these torsion groups. We present these polynomials
in the next section.

\subsubsection{The Division Polynomials}     \label{divpols}

In this section we relate specific polynomials to the
torsion groups of $E(k)$. First, we will provide an example before going
on to state the relevant theorems and definitions.

Recall that if $k$ is algebraically closed, then theorem \ref{isom} tells
us that the  two-torsion group $E[2]$ has order 4. Also note that the
non-singularity of $E$ requires that the equation $x^{3}+Ax+B=0$ has three
distinct roots, $\omega_{1}, \omega_{2}$, and $\omega_{3}$. We will denote
the corresponding points in $E(k)$ by $P_{1}=(\omega_{1},0),
P_{2}=(\omega_{2},0), and\, P_{3}=(\omega_{3},0)$ respectively.

Using the addition formulas presented in section \ref{generaladd}, let
us compute $2P_{1}$. Since we are adding $P_{1}$ to itself, the slope
$m$ used in this case is given by equation (\ref{tanslope}). Therefore,
this addition yields $2P_{1}=(\infty,\infty)$, and we have
$2P_{1} = \cal O$. In fact, this is the case for $P_{i}, i = 1,2,3$.
Since $x^{3}+Ax+B=0$ has only three roots, these are the only such points.
Therefore, we have the three points, $P_{1}, P_{2}, P_{3}$, plus $\cal O$
that are contained in $E[2]$, and according to theorem \ref{isom}, these are
all the points in $E[2]$.

Also note that for all finite points $P \in E[2]$ we have ${\bf y}(P)=0$. This
is no coincidence, and in fact for any n-torsion group $E[n]$ we have a
polynomial $\psi_{n}$ related to the n-torsion group $E[n]$.
Specifically:
\begin{df}
Let $\psi_{n} \in k[E]$, we will define $\psi_{n}$ to be the unique
polynomial such that $\psi_{n}(P) = 0$ for all $P$  in $E[n]$ where $P \neq \cal O$.
Also, these zeros have multiplicity one, and the degree of $\psi_{n}$ is
$n^{2}-1$ when considered in $k[E]$, where the degree of x is 2, and the
degree of y is 3.
\end{df}

It turns out that these polynomials can be computed recursively. This
fact is expressed in the following:
\begin{thm}                          \label{psirelate}
Let $P=(x,y)$. The polynomials $\psi_{n}$ satisfy the following conditions:
\begin{itemize}
  \item $\psi_{0} = 0$
  \item $\psi_{1} = 1$
  \item $\psi_{2}(P) = 2y$
  \item $\psi_{3}(P) = 3x^{4}$
  \item $\psi_{4}(P)=4y(x^{6}+Ax^{4}+20Bx^{3}-5A^{2}x^{2}-4ABx-8B^{2}-A^{3})$
  \item For $m>n>0, \  \psi_{n}^{2}\psi_{m+1}\psi_{m-1} -
                    \psi_{m}^{2}\psi_{n+1}\psi_{n-1}=\psi_{m+n}\psi_{m-n}$
  \item For $k > 2, \  \psi_{2k} = \frac{\psi_{k}}{2y}
                     (\psi_{k+2}\psi_{k-1}^{2}-\psi_{k-2}\psi_{k+1}^{2})$
  \item For $k \geq 2, \  \psi_{2k+1}=\psi_{k+2}\psi_{k}^{3}-
                        \psi_{k+1}^{3}\psi_{k-1}$
  \item For $n$ odd, the polynomial $\psi_{n}$ is a function of $x$
        alone.
\end{itemize}
\end{thm}
The $\psi_{n}$'s also satisfy the following relation that will allow us to
compute on the n-torsion points of $E(\overline{k})$.
\begin{lem}                      \label{addpsi}
Let $P \in E(\overline{k})$. Let n be an integer greater than one such
that $nP \neq \cal O$,and let $\psi_{n}$ represent $\psi_{n}(P)$; then
\begin{equation}
nP = (x - \frac{\psi_{n-1}\psi_{n+1}}{\psi_{n}^{2}},
\frac{\psi_{n+2}\psi_{n-1}^{2}-\psi_{n-2}\psi_{n+1}^{2}}{4y\psi_{n}^{3}}).
\end{equation}
\end{lem}

Using theorem \ref{psirelate}, lemma \ref{addpsi},and Hasse's theorem (presented in the next section)  we will be able
to compute the order of $E(k)$ modulo certain primes.

\subsection{Hasse's Theorem}

In this section we will present the results that lead to the proof of
Hasse's Theorem. This theorem places a bound on the order of the
group of points $E(k)$, where the characteristic of k is nonzero. This notion
is of fundamental importance in the algorithms presented in the final
section of these notes.  We will also present some theorems and definitions
that will allow us to compute the group order mod $p_{i}$, where $p_{i}$
is prime and less than $p$.

\subsubsection{Endomorphisms and the Ramification Index}

\begin{df}
A rational mapping $E(k) \mapsto E(k)$ that is also a group homomorphism
is called an endomorphism.  These mappings form a group denoted $End(E(k))$.
\end{df}

One particular endomorphism on $E(k)$ that concerns us is the
Frobenius mapping given by $$\varphi(a,b) \mapsto (a^{p},b^{p})$$ where
$(a,b) \in E(k)$. Now that we have defined an endomorphism on $E(k)$, let
us give some definitions and theorems that will emphasize the importance
of $\varphi$. First we need to define the ramification index and degree of
an endomorphism:

\begin{df}
Let $F$ be a rational map on $E(k)$ and let $P \in E(k)$. Then the
ramification index of $F$ at $P$ is defined by $$e_{F}(P) =
ord_{P}(u \circ F)$$ where $u$ is a uniformizer at $F(P)$, and $ord_{P}(r)$
stands for the order of $r$ at $P$.
\end{df}

\begin{df}
Let $\alpha \in End(E)$. The degree of $\alpha$ is given by $$deg\alpha
= \mid ker\alpha \mid \cdot e_{\alpha}$$
\end{df}

The Frobenius endomorphism has the following important properties:
\begin{itemize}
   \item If $(a,b) \in E(k)$ then $(a^{p},b^{p}) \in E(k)$
   \item $(a,b)$ is k-rational if and only if $\varphi(a,b)=(a,b)$
   \item If $k= \bf{Z}_{p}$ then $e_{ \varphi } = 1$
   \item $deg(1- \varphi ) = \mid E(\bf{Z}_{p}) \mid$
\end{itemize}

>From the above list we can see that the Frobenius endomorphism, when
viewed in the proper setting , can give us the information we seek.

\subsubsection{Determinants of Endomorphisms}

According to theorem \ref{isom}, $E[n] \cong {\bf Z_{n}} \times {\bf Z_{n}}$.
If we view $E[n]$ as a $\bf Z_{n}$ module, then we see that it is free; hence,
we can do linear algebra there.  It is easy to show that if $\alpha \in
End(E)$, then $\alpha$ is a linear transformation. Also, since $\alpha$
is a group homomorphism, we can show that $\alpha(E[n]) \subseteq E[n]$.
Using these facts we see that there is a matrix representation of
$\alpha$ when viewed over $E[n]$, and hence a determinant.

Using the Weil paring \footnote{See \cite{Muller}.} we get the following:
\begin{thm}                             \label{detdeg}
Let $\alpha \in End(E(k))$, then the determinant of $\alpha$ on $E[m]$
satisfies $$ det( \alpha ) = deg( \alpha ) \ mod \ m.$$
\end{thm}

Theorem \ref{detdeg} allows us to use results from linear algebra to
ascertain $\mid E(k) \mid$ modulo $m$.  Specifically, we can
use the following two theorems, both of which are derived from their
linear algebra analogues:

\begin{thm}                   \label{det1}
Let $\alpha$ and $\beta$ be members of $End(E(k))$, then $$ deg(a_{1}
\alpha + a_{2} \beta) = a_{1}^{2} deg( \alpha ) + a_{2}^{2} deg( \beta )
+ a_{1} a{2} (deg( \alpha + \beta )-deg( \alpha ) - deg( \beta ))$$
\end{thm}

\begin{thm}                    \label{det2}
If $\alpha$ is any endomorphism, then $$ \beta = \alpha \circ \alpha -
(1 + deg( \alpha ) - deg(1- \alpha)) \circ \alpha - (deg( \alpha )) =
\cal O _{M}$$ (the identity endomorphism).
\end{thm}

\subsubsection{Main Theorem}

\begin{thm}                          \label{mainthm}
Let $t=p+1- \mid E(\bf{Z}_{p}) \mid$ and $\varphi$ be the Frobenius endomorphism. Then
\begin{enumerate}
  \item $\varphi \circ \varphi - t \circ \varphi + p = \cal O _{M}$
  \item $\mid t \mid \leq 2 \sqrt{p}$
\end{enumerate}
\end{thm}

The first part of the theorem follows from theorem \ref{det2} and the
facts presented concerning $\varphi$  and $1 - \varphi$.  The second
part of the theorem follows from theorem \ref{det1} using $ \alpha = 1$
and $\beta = \varphi$.

\section{The Algorithms}

In this section we will examine the three algorithms used to determine
the order of $E(k)$. The first algorithm is one which is based on an
idea of Daniel Shanks presented in \cite{Shanks}. The second is
presented in Rene Schoof's paper \cite{Schoof}.  The third algorithm is a
combination of the preceding two and was presented in \cite{Muller} by
V. M\"{u}ller and J. Buchmann.

Shanks' algorithm uses part 2 of theorem \ref{mainthm} and the baby-step
giant-step strategy to determine the
order of $E(k)$. This method is very efficient for primes p
approximately $10^{17}$. However, after this the algorithm starts to slow
down considerably. The reason for this is that in this algorithm, one needs
to generate and search a set which has size $\approx \sqrt[4]{p}$.
Therefore, for large p this becomes more and more difficult.

Schoof's algorithm uses both parts of theorem \ref{mainthm}.  In his
algorithm, Schoof uses the $\psi_{n}$'s and part 1 of theorem \ref{mainthm}
to compute on the $p_{i}$ torsion groups and determine the group order
mod $p_{i}$  (where $p_{i}$ is a relatively small prime). The
biggest draw back of this algorithm is that the $\psi_{n}$'s have degree
approximately equal to $n^{2}/2$. For example, to compute on $E[17]$ we must
work with polynomials with degree $\approx$ 140. In some parts of
the algorithm we raise these polynomials to the $p^{2}$ power and
then must compute the GCD with another polynomial. Computationally, this algorithm can
get complicated very quickly.

In the algorithm presented in \cite{Muller}, M\"{u}ller and Buchmann combine
the above ideas using Schoof's idea to improve Shanks' algorithm.  What
they do is compute $\mid E(k) \mid \ mod \ p_{i}$ for a few small primes
$p_{1} \ldots p_{n}$  (ie: 2,3,5,7) and use the Chinese remainder theorem
to find $\mid E(k) \mid  mod \ p_{1} \ldots p_{n}$.  Using this they reduce
the size of the set needed to be searched in Shanks' algorithm by a factor
proportional to $p_{1} \ldots p_{n}$. 
  
\subsection{Shanks' Algorithm}               \label{shnkalg}

Let $I=[{\cal L},{\cal H}] \cap \bf Z$, where ${\cal L} = \lfloor p -
2 \sqrt{p} + 1 \rfloor$ and ${\cal H} = \lceil p + 2 \sqrt{p} + 1 \rceil $.
$I$ is the interval given in part 2 of theorem \ref{mainthm}, and hence
$ \mid E(k) \mid \in I$.

Consider a point $P \in E(k)$. It follows from Lagrange's theorem that
for at least one $ a \in I, aP = \cal O$. What Shanks' algorithm does is
use a portion of the cyclic group generated by $P$ $(the \ baby \ step)$ to
search $I$ for this value $(the \ giant \ step)$. If only one value $ a
\in I$ is found, such that $ aP = \cal O$ holds, then this is the group
order. If more then one is found then the point order of $P$ is determined
and a second procedure is invoked.
This second procedure finds the order of a point $R$ in $E(k)/<P>$ 
and uses this to determine the order of $E(k)$. We examine the algorithm
\footnote{As presented in \cite{Muller}} below and follow it with a
discussion of the implementation and validity of each step.

\begin{description}
\item[step1] Randomly choose a point $P \in E(k)$.
\item[step 2] Set $d = \lceil \sqrt{ \cal H - \cal L} \rceil$. Compute $ P, 2P, \ldots, (d-1)P$.
      If $iP = \cal O$ for any $i \leq d$ then go to step 1. Else set
      $BS = \{{\cal O}, P, 2P, \ldots,iP, \ldots (d-1)P \}$.
\item[step 3] Let $Q = dP$. Compute $H_{j} = \cal L$ $P + jQ$ for $j=1,2, \ldots d.$
      Determine if $H_{j} \in BS$. If so, then store the corresponding $i$'s and $j$'s.
\item[step 4] If there is only one pair $(i,j)$ found in step 3, then $$\mid E(k) \mid = {\cal L} +
      jd - i$$ Else find a consecutive pair $(i_{1},j_{1}),
      (i_{2},j_{2})$ and set $\mid P \mid$ equal to $$ (j_{2} - j_{1})d
      + (i_{2} - i_{1})$$ If $\mid P \mid\,< \sqrt{p}-1$ then go back to step 1.
\item[step 5] Choose a random point $R \in E(k)$.
\item[step 6] Repeat steps 2 to 4 for $R$. If this yields the group
             order, then stop. Else go to step 7.
\item[step 7] Using a method similar to the one given in steps 1 to 4, determine
      the least divisor $s$ of $\mid R \mid$, such that $sR \in <P>$.  If
      $s \cdot \mid P \mid < 4 \sqrt{p}$ then go back to step 5. Else
\item[step 8] Determine the unique $n$ such that $ns \cdot \mid P \mid \in I$.
              Next, set $\mid E(k) \mid = ns \cdot \mid P \mid$. End.
\end{description}

For step one we choose a random $w \in \bf{Z}_{p}$ and compute $w^{3} + Aw +B$
until $$ ( \frac{w^3+Aw+B}{p}) = 1$$ where $(\frac{u}{v})$ denotes the
Legendre symbol. This is a probabilistic method for finding points in
$E(k)$. One can expect about half the $w$'s in $\bf Z_{p}$ to be quadratic
residues. Once a $w$ is found, we then solve $y^{2}-w^{3}-Aw-B=0$ mod $p$
and we have a point $(w,y) \in E(k)$. This method works efficiently
in practice. \footnote{ In {\em Maple}, using primes $\approx 10^{30}$,
it takes an average of 4 seconds cpu time before a point is found.}

In step 2 we are generating a set of size $d$. We do this by adding
the point $P$ to itself $d$ times. Each time we add $P$ to itself to
obtain $nP$ we must search the existing values \makebox{$iP$, i = 1,2,
$\ldots$,n-1}  already calculated, and if we find this point in this set
we choose another point and begin again; if not, then place this point
in the set and proceed until the set has $d$ points.  In step 3 we are
doing a similar procedure.  The main difference between these two steps
is that the size of the set to be searched in step 3 stays constant,
while the size of the set in step 2 grows linearly as we go along. We
are able to use the {\em member} function already in {\em Maple} to search
the set in steps 2 and 3.

Notice that in step 2 the size of the set
needed to be searched will be smaller (on the average it will be half as
big) then the size of the set searched in step 3. However, in step 2 we
must search the set to see if it contains $iP$; if it does not, then we
place $iP$ in this set. Therefore, even though the set to be searched in
step 2 is half as big as the one in step 3, because of the additional
step required in step 2, we will consider the individual operations in each
to require an equal amount of cpu time.  That is, we will consider one
search \& placing into the set of step 2 to be time equivalent to
one search of the bigger set in step 3.

With this in mind, let $s$ represent the order of $BS$ in step 2, let
{\cal S} be the total number of operations in steps 2 and 3,and
set ${\cal A} = {\cal H - L}$.  Then in order to minimize the total
amount of operations preformed in steps 2 and 3, we must minimize;
$$ {\cal S} = \frac{{\cal A}}{s} + s $$
The minimum of this function occurs when $s = 2\sqrt[4]{p}$, hence the
choice of $d$ in step 2.

We can also expect to find a point meeting the criterion for step 2
rather easily. Since by part 2 of theorem \ref{mainthm}, we have $\mid E(k) \mid
\geq ({\sqrt{p}-1})^{2}$. Also, by theorem \ref{isom} it follows that $E(k) \cong
{\bf Z_{s}} \times {\bf Z_{t}}$. From these two facts we see that $s > \sqrt{p}-1$
or $t > \sqrt{p}-1$, and it follows that a large number of points on $E(k)$ will
have order greater than $\sqrt{p}-1 > d$. It also follows that if $s \ or \ t
\geq 4\sqrt{p}$, then a large number of points on $E(k)$ will have order bigger
than $4\sqrt{p}$ = $\cal H - L$.

If in step 1 we find a point with order greater than $\mid \cal{H}-
\cal{L} \mid$ the algorithm will terminate in step 4. In practice the
algorithm terminates at this point for most elliptic curves.
However, there are curves which always seem to require the additional
steps. For example, $$ y^{2} = x^{3} + x$$ where $p$ has the form
$k^{2} + 1$.

In order for the algorithm to get past step 6, we must find a point
\makebox{$R \in E(k)/<P>$} with order greater than or equal to 5, when
viewed in \makebox{$E(k)/<P>$}.  In this case, if \makebox{$s \ or \ t \leq
4\sqrt{p}$}, then it is very likely that a $R$ will be found in the second
part of the algorithm.

In section 3.2 of \cite{Muller}, M\"{u}ller and Buchmann propose the following
modification to step 2 of the algorithm: instead of computing the first
$d$ points of $BS$, only compute the first $\lceil d/2 \rceil + 1$ points
in $BS$. In other words, set $BS = \{{\cal O}, P, 2P, \ldots \lceil
d/2 \rceil P \}$, thus reducing the size of $BS$ by one half.

We can do this because of the structure of $E(k)$. If we have $P$ computed,
then by case 1 from section \ref{generaladd}, we also have the
$x$-value of $-P$. Therefore, instead of checking for $H_{j}$ to be in $BS$,
we only need to check if the $x$-value of $H_{j}$ matches an $x$-value in
$BS$. There are some modifications that need to be made to the algorithm.
These all concern finding the corresponding $i$ that goes with the $j$ from
$H_{j}$. We must also modify the checks at the end points of the
interval $I$. Still, this is an improvement over the previous method.
Running times for this algorithm can be found in table 1.


\subsubsection{An Adjustment to Shanks' Algorithm}

Let us propose the following adjustment to Shanks' algorithm.

\begin{description}
\item[steps 1 to 4] Implement the corresponding steps of Shanks'
     algorithm as presented in section \ref{shnkalg}.
\item[step 5] Choose a point $R \in E(k)$ where $R \neq P$.
\item[step 6] Set $$I' = [\frac{{\cal H - L}}{\mid P \mid}] \cap
              {\bf Z} = \{a_{1} \ldots a_{s}\}$$
     where $s \leq 4$.
\item[step 7] Using a {\em baby-step giant-step} method, check if
     $a_{i}R \in <P>$. If more then one $a_{i}$ is found then goto
     step 5. If only one such $a_{i}$ is found, then set
     $$ \mid E(k) \mid = a_{i}\mid P \mid$$ and stop.
\end{description}

In step 4 of Shanks' algorithm, if the group order was not found, then
the order of the point P had to be greater than or equal to $\sqrt{p} -
1$.  This implies that $\mid I' \mid \leq 4$, as well as implying that
\begin{equation}                \label{maxord}
\mid R \ + <P> \mid \leq \sqrt{p} + 4, \forall R \in E(k).
\end{equation}
Also, in step 2 of Shanks' algorithm $BS$ is computed for the
point P.  We can use this set when checking to see if $a_{i}P \in <P>$.
Recall that in step 2 we require $\mid BS \mid = \lceil 2\sqrt[4]{p} \rceil$.
Hence, by equation ( \ref{maxord} ) we can check to see $a_{i}R \in <P>$
in approximately $\frac{1}{2} \sqrt[4]{p}$ operations for each $a_{i}R$. Since
there are at most four of them, we can complete this process in
approximately $2\sqrt[4]{p}$ operations.  This is equivalent to the
number of operations needed to compute a new $BS$ for the point $R$,
found in step 6 of the algorithm in section \ref{shnkalg}.
The adjusted algorithm will terminate if $\mid R \ + <P> \mid$ is greater
than 4, which is exactly the same terminating condition for the second
half of Shanks' algorithm presented in section \ref{shnkalg}. Hence, when dealing with curves that require the second half of Shanks' algorithm, this method of implementation is more efficient. Next we will give a general description of Schoofs' 
algorithm as presented in \cite{Schoof}.

\subsection{Schoof's Algorithm}  \label{schalg}

Recall from theorem \ref{mainthm} that the Frobenius endomorphism
$\varphi$ satisfies the relation on $E({\bf Z}_{p})$ given by
\begin{equation}                \label{endeq}
\varphi^{2} + p - t \varphi = \cal{O}_{M}
\end{equation}
where $$ t = p + 1 - \mid E({\bf Z}_{p}) \mid.$$

We can restrict our view of equation $(\ref{endeq})$ to points in $E[p_{i}]$
and consider the following equation instead of $(\ref{endeq})$:
\begin{equation}                 \label{newendeq}
\varphi_{p_{i}}^{2} + m = \tau \varphi_{p_{i}}
\end{equation}
where $\varphi_{p_{i}}$ represents the Frobenius endomorphism restricted
to $E[p_{i}]$, $ m \equiv p$ mod $p_{i}$, and $\tau \equiv t$ mod $p_{i}$. What
Schoof does in his algorithm is use the equations presented in section
\ref{divpols} to determine $\tau$ for the primes $\{p_{1}, p_{2}, \ldots
p_{n} \}$ where $ \prod _{1}^{n} p_{i} > 4 \sqrt{p}$. Then using the
Chinese remainder theorem, he determines $E(k)$ mod $p_{1}p_{2} \ldots
p_{n}$ and then finds the unique $a \in I$ such that $a \equiv E(k) \
mod \ p_{1}, \ldots p_{n}$.

Specifically, if $P \in E[p_{i}]$ and $p_{i} \neq 2 \, or \, p$, then using
the following relation we check for which $\tau$ the following equation
holds, mod $p_{i}$:
\begin{equation}                      \label{schoofeq}
(x^{p^{2}}, y^{p^{2}}) + ( x - \frac{\psi_{m-1}\psi_{m+1}}{\psi_{m}^{2}},
\frac{\psi_{m+2}\psi_{m-1}^{2}-\psi_{m-2}\psi_{m+1}^{2}}{4y\psi_{m}^{3}})
\end{equation}

$$ =  \cases{ 0  &  \mbox{if $\tau = 0$ mod $p_{i}$}; \cr
     (x^{p}-(\frac{\psi_{\tau-1}\psi_{\tau+1}}{\psi_{\tau}^{2}})^{p},
   (\frac{\psi_{\tau+2}\psi_{\tau-1}^{2}-\psi_{\tau-2}\psi_{\tau+1}^{2}}
   {4y\psi_{\tau}^{3}})^{p})  & \mbox{otherwise}.\cr }$$

Using the relation given in $(\ref{e-curve})$, theorem \ref{psirelate},
and the addition formulas given in section \ref{generaladd} one can
transform the coordinates of equation $(\ref{schoofeq})$ into the system
of polynomials
\begin{equation}                      \label{polsys}
H_{x}(x) = 0,  H_{y}(x) = 0.
\end{equation}
After determining the polynomials given in equation $(\ref{polsys})$,
one must check for which $\tau = 0,1,2,\ldots, p_{i}-1$,the system in
$(\ref{polsys})$ hold mod $\psi_{p_{i}}$.

As stated previously, we will be using the addition formulas given in
section \ref{generaladd} to simplify the left hand side of equation
$(\ref{schoofeq})$. In order to use the addition formulas one must
first determine which form of the slope will be needed for the right
hand side of equation $(\ref{newendeq})$. For example, are there points
in $E[p_{i}]$ that are equal, inverses of each other, etc..?  Once this
is ascertained, we proceed to find the proper $\tau$ and hence the value
of $\mid E(k) \mid$ modulo a given $p_{i}$.

Next let's look at an outline of Schoofs' algorithm \footnote{For a more
detailed description see \cite{Schoof}}, and follow this with a brief
discussion of the validity of the steps, as well as their implementation
using {\em Maple}.

\begin{description}
      \item[step 1] Calculate the product of sucessive primes, starting
      with 2, and stopping for the first prime $p_{n}$ such that
      $p_{1}p_{2}p_{3} \ldots p_{n} \geq 4 \sqrt{p}$. Set j equal to this
      product.
      \item[step 2] Determine if $x^{3} + Ax + B = 0$ has any solutions in
            $\bf Z_{p}$. If yes then set $\mid E(k) \mid \equiv 0 \ mod
             \ 2 $, else set $\mid E(k) \mid \equiv 1 \ mod \ 2$
      \item[step 3] For i from 1 to n do steps 4 to 7.
      \item[step 4] Determine if there are any points $P \in E(\overline{k})$
            such that $\varphi_{p_{i}}^{2}(P) = \pm mP$.
            \begin{itemize}
                 \item If there exists a $P$ with
                       $\varphi_{p_{i}}^{2}(P) = mP$ then goto to step 5.
                  \item If there exists a $P$ such that
                        $\varphi_{p_{i}}^{2}(P) = -mP$ then set $\tau = 0$
                        and stop.
                   \item If no such $P$ exists then $\tau \neq 0$;
                         goto step 7.
            \end{itemize}
      \item[step 5] Calculate $(\frac{p}{p_{i}})$. If this equals $-1$, then set
            $\tau = 0$ and stop; otherwise set \makebox{$w = \sqrt{p}$
            mod $p_{i}$.}
      \item[step 6] Determine if $\pm w$ is an eigenvalue of $\varphi$. If
            neither is an eigenvalue of $\varphi$ then set $\tau = 0$
            and stop, else set $\tau = \pm 2w$ accordingly and stop.
      \item[step 7] Check $(\ref{polsys})$ mod $\psi_{p_{i}}$ for the unique
            $\tau = 1,2, \ldots p_{i}-1$. Stop.
      \item[step 8] Using the Chinese remainder theorem, determine
           $${\cal E} \equiv \mid E(k) \mid \ mod \ p_{1} \ldots p_{n}.$$
      \item[step 9] Set $\mid E(k) \mid = B$ where $$B \equiv {\cal E}
                    \ mod \ p_{1} \ldots p_{n},$$ and $B \in I$.
\end{description}

In step 2 one determines the group order mod 2. Note that if
$x^{3}+Ax+B=0$ has a solution in $\bf Z_{p}$, then the group order must
be even, hence 0 mod 2; if not, then it is 1 mod 2.

In step 4, we can use $(\ref{e-curve})$ to transform the appropriate equations
in the $\psi_{n}$'s into polynomials in $x$ alone. Once this is done we
check the $GCD$ of this polynomial and $\psi_{p_{i}}$. If this $GCD$ is
one, then this implies that there are no points $P$ on $E(\overline{k})$
such that $P$ satisfies
\begin{equation}                \label{eigenck}
\varphi_{p_{i}}^{2}(x(P)) = \pm m(x(P))
\end{equation}
Hence, since  $\varphi$ is an endomorphism, $\tau$ cannot be zero. At
this point the algorithm goes to step 7.  For step 7 we will need
at most $\lfloor \frac{p_{i}}{2} \rfloor$ steps to find the appropriate
$\tau$.

If in step 4 there are points $P$ that satisfy equation $(\ref{eigenck})$,
then one must determine if the map $\varphi_{p_{i}}^{2}$ is equivalent to
the map $m$ or the map $-m$ when viewed over $E[p_{i}]$. If we find the
latter, then $\tau$ must be zero.  If we find the former, then using
this fact, we can derive the relationship:
\begin{equation}                        \label{eigenval}
\varphi(P) = \frac{2p}{t}(P)
\end{equation}
Since the mappings in the above equation are endomorphisms, we can derive the
following: $$ t^{2} \equiv 4p \ mod \ p_{i}.$$
Using this relation and equation \ref{eigenval} we can show that either
$w$ or $-w$ is an eigenvalue of $\varphi$, where $w \equiv \sqrt{p} \ mod \
p_{i}$. With this in mind we check to see if $$ \varphi(P) = wP, \ \forall
P \in E[p_{i}]$$  This can be accomplished by converting the above
relation in $\psi_{n}$'s to one in polynomials in ${\bf Z}[x]$, and
checking whether this polynomial is equal to \makebox{zero mod $\psi_{p_{i}}$.}

In all steps of Schoofs algorithm, we used the {\em Maple modp1}
representation for all polynomials\footnote{ A special thanks goes out to Mike Monagan of the Symbolic Computation Group for providing me with some valuable advice concerning the use  of { \em Maple}}. What {\em modp1} does is represent
the polynomials as strings of integers, and uses these integers to
preform computations more efficiently.

\subsection{The Combined Algorithm}    \label{combo1}

We now present the combined Schoof-Shanks algorithm \footnote{As
presented in \cite{Muller}}:
\begin{description}
     \item[step 1] Compute $\mid E(k) \mid$ for the primes 2,3,5,7 as
           described in section \ref{schalg}.
     \item[step 2] Set $d = min\{\overline{d} \mid \overline{d} \geq 2
            \sqrt[4]{p} \, and \, d \equiv 0 \, mod \, 210 \}.$
     \item[step 3] Implement Shanks' algorithm as presented in section
           \ref{shnkalg} using the $d$ computed in step 2 and
           the following adjustment to step 2.
      \begin{itemize}
            \item Store only those $iP$ in $BS$ with $i \equiv ( {\cal L}
                  - \mid E(k) \mid)$ mod 210.
       \end{itemize}
            Stop.
\end{description}

Some running times for this algorithm are presented in table 1.  Recall
from step 4 of Shanks' algorithm that if there is only one
pair (i, \ j) found in step 3 of the algorithm, then the group order can be
found from the following computation: $$ \mid E(k) \mid = {\cal L} + jd -
i.$$  From this we obtain the relationship:
\begin{equation}             \label{newi}
i \equiv {\cal L} - \mid E(k) \mid mod \ p_{1}p_{2} \cdots p_{n}.
\end{equation}
For this reason we only need to store the $i$'s in step 3 above that
satisfy this criterion.

This modification has several advantages. The first one is that it reduces
the size of the set $BS$ that must be stored in step 2 of Shanks'
algorithm. For example; consider the curve $y^2 = x^{3} + x + 1$ over $\bf
Z_{p}$, where $p = 100000000000031$, then $d = 6325$. Also, lets
say we use 2,3,5, and 7 as our primes in step 1.  Then, we can show that
$E({\bf Z_{p}}) \ mod \ 210 \equiv \ 76$.  According to
our previous statements, the modified $BS$ will be equal to the set \{ \cal{O},
76P, 286P, 496P, \ldots, 6510P \}.  Hence, BS is reduced by a factor of 210.
This will improve the time spent searching this set in step 3.

The second advantage to knowing $E(k) \ mod \ p_{1} \ldots p_{n}$ is
that it places an added restriction on obtaining only the point order from
the first part of the algorithm. Not only must the point $P$ ( chosen in
step 1 of Shanks' algorithm )  have order less than $4 \sqrt{p}$, this
order must also be congruent to zero modulo $p_{1} \ldots p_{n}$ if no
intersection points are equal to $\cal O$; or congruent to $ \pm E(k) \
mod \ p_{1} \ldots p_{n}$ if one intersection point is equal to $\cal O$.
Therefore, when using Shanks' algorithm in tandem with Schoof's
algorithm, it is not likely that Shanks' algorithm will make it
past step 4.

\subsubsection{Optimizing the Running Time}      \label{optimize}

In section 7 of \cite{Muller}, the authors state that they are working
on improving the algorithm by allowing more primes in the Schoof part.
We have done some investigation into this question and we will make 
some suggestions for improvements.

Recall that in the combined algorithm, we only need to store those $iP$
calculated in step 2 of Shanks' algorithm that satisfy equation
(\ref{newi}). Hence, we no longer need to calculate each and every $P$
in $BS$. Because of this, we can use a {\em baby-step  giant-step}
method to compute the modified $BS$ in this algorithm.

In my implementation, I only calculate $iP$ for $i$ from 1 to $m =
\prod^{n}_{1}p_{i}$. Then this is used in a modified {\em baby-step
giant-step} method to calculate the points needed to store in step 2 of
Shanks' algorithm. Therefore, we can look at the Shanks' part of the
algorithm as occuring in three phases.  First, calculate the set $$BBS =
\{ {\cal O}, P, 2P,3P,\ldots mP \}$$  Second, use this set to calculate
the points needed to store in $BS$, using $BBS$ the way $BS$ is used in
step 3 of the algorithm in section \ref{shnkalg}. Finally, we use $BS$
to hunt the interval $I$ for the group order.

In light of these last comments, we would like to determine which
choices of $p_{1} \ldots p_{n}$ and $d$ will give us a more efficient running
time for the combined algorithm.  We make the same assumptions
concerning the time needed to perform each operation in the three
different phases of the combined algorithm, as were made in steps
2 and 3 of the original Shanks' algorithm. With this, minimizing the
number of operations performed in our implementation can be determined
by finding the minimum value of the following function  in $R(x,y)$:
$$ M = x + \frac{y}{x} + \frac{{\cal A}}{y}$$ where ${\cal A} = \cal H -
\cal L$ and,  $x$, $y/x$, and ${\cal A}/y$ are equivalent to the number
of operations in first, second and third part respectively. The minimum
of this function occurs at (${\cal A}^{1/3},{\cal A}^{2/3}$).

The size of $\cal A$ depends on the order of the field. Based on our
assumptions, the choice of $d$ in step 1 of the Shanks' part should be
$2 \sqrt[3]{2p}$ and the number of primes chosen in step 1 of the combined
algorithm should be adjusted according to the size of the field. We
present some running times for the combined algorithm with
the previous adjustments  in the last column of table 1.

We note here that our analysis of the combined algorithm is not
complete.  In the above argument, we never mentioned how increasing the
number of primes used to calculate $E(k) \ mod \ p_{1}p_{2} \cdots p_{n}$
effects the running time of the algorithm.  It is my preliminary belief
that the time saved in minimizing the number of operations in the
Shanks' part of the algorithm far outweighs the extra time spent in
calculating the group order modulo one extra prime, for small primes.
However, as numbers increase, the primes become more sparse. Hence, the
number of steps needed to compute $E(k) \ mod \ p_{i}$  will increase
proportionaly. There may be a cut off point where optimizing in the
above manner is no longer effective.  

\section{Running Times}

In this section we present some running times for the three algorithms
described in this paper.  The algorithms were executed on the GMU VAX 6000 - 420  running VAX/VMS 5.4 -1. The results in the following table
represent an averaged time for several curves\footnote{Three curves were 
used in most cases, more in some others.} over fields of the form $ {\bf Z}_{p}$, where $p$ is given in column one. In column two we present running times for Shanks' algorithm as
presented in section \ref{shnkalg}, in column three we present times for
the combined algorithm implemented without the results discussed in
section \ref{optimize}, and in column four we present the combined
algorithm implemented with the results discussed in section \ref{optimize}. 

\vspace{.75 in}


\begin{center}

\begin{tabular}{|c|c|c|c|}                   \hline
\multicolumn{4}{|c|}{Table 1}  \\ \hline  &
\multicolumn{3}{|c|}{times}
\\ \cline{2-4}  \multicolumn{1}{|c|}{ size of prime} &
\multicolumn{1}{|c|}{Shanks'} & \multicolumn{1}{|c|}{Combined I}
& \multicolumn{1}{|c|}{Combined II} \\ \hline
$ \approx 10^{12}$ & 1 min 24 sec  &   2 min 58 sec & 2 min 38 sec \\ \hline
$ \approx 10^{15}$ & 9 min 10 sec  &   5 min 47 sec & 2 min 22 sec \\ \hline
$ \approx 10^{16}$ & 1  hr  2 min  &   9 min 17 sec & 2 min 50 sec \\ \hline
$ \approx 10^{17}$ &57 min  2 sec  &  15 min 19 sec & 4 min 51 sec \\ \hline
$ \approx 10^{18}$ & out of memory&  28 min 23 sec &15 min 18 sec \\ \hline
$ \approx 10^{19}$ &  out of memory&   1 hr   3 min &25 min 12 sec \\ \hline
$ \approx 10^{20}$ &  out of memory&  51 min 10 sec &21 min  7 sec \\ \hline
\end{tabular}

\end{center}

\newpage
\begin{thebibliography}{99}
\bibitem{Brassard} G. Brassard: {\em Modern Cryptology - A Tutorial,}
Lecture Notes in Computer Science \#325. Springer - Verlag, N.Y., 1988.
\bibitem{CRD} L. S. Charlap and D. P. Robbins: {\em An Elementary
Introduction to Elliptic Curves,} CDR Expository Report No. 31,
Institute for Defense Analysis, Princeton, December 1988.
\bibitem{Husemoller} D. Husem\"{o}ller: {\em Elliptic Curves,} Springer -
Verlag, N.Y., 1987.
\bibitem{KoblitzII} N. Koblitz: {\em A Course in Number Theory and
Cryptography,} Springer - Verlag, N.Y., 1987.
\bibitem{KoblitzI} N. Koblitz: {\em Elliptic Curve Cryptosystems,}
Mathematics of Computation, {\em 48}, 1987, 203-209.
\bibitem{Muller} V. M\"{u}ller and J. Buchmann: {\em Computing the number
of points of elliptic curves over finite fields,} Proceeding of
ISSAC'91, S.M. Watt editor, ACM Press 1991, pp179-182.
\bibitem{Schoof} R. Schoof: { \em Elliptic curves over finite fields and the
computation of square roots mod p,} Mathematics of Computation, {\em
44}, 1985, 483-494.
\bibitem{Sedgewick} R. Sedgewick: {\em Algorithms,} Addison - Wesley, N.Y.,
1988.
\bibitem{Shanks} D. Shanks: { \em Class number, a theory of factorization
and genera,}  Proc. Symposium of Pure Math. {\em 20} , Amer. Math. Soc.
1970, pp 415-440.
\end{thebibliography}

\newpage
\pagestyle{empty}
\tableofcontents

\end{document}             % End of document.



