\section{Algebraic Schemes for Cryptosystems}
The above title is a kind of pun since we will discuss the geometric
objects called Algebraic Schemes which also give us algebraic schemes
(in the ``English'' sense) for cryptosystems. All the groups
discussed so far turn out to be special cases of certain groups that
are introduced in this section.
The fundamental problem studied in arithmetic algebraic geometry is
the solution of systems of algebraic equations. The notion of an
Algebraic Scheme is the essential geometric notion that incorporates
this question. We then introduce the notion of vector group schemes
and the $K$-group of such objects. With some additional constraints
these are the groups that seem to arise in many cryptographic
contexts.
While we cannot hope to introduce all the algebraic geometry and
commutative algebra that is necessary to study these $K$-groups here,
we give the fundamental definitions and some important examples. We
will also not give proofs as the subject is too vast to be covered
here. When we apply this theory to hyper-elliptic curves in the next
section we will be more precise.
\subsection{Finite rings}
We recall some basic facts about finite commutative rings with
identity (and $1\neq 0$). (The adventurous reader may like to explore
which parts of this entire section can be carried over to the
non-commutative case). The reader can prove these results from first
principles.
\begin{enumerate}
\item In any finite ring there are finitely many ideals and in
particular there are finitely many maximal ideals. In other words
such a ring is ``semi-local''.
\item Any prime ideal in a finite ring is maximal.
\item (Analogue of Chinese Remainder Theorem). Any finite ring is a
product of finite {\em local} rings; \ie finite rings which have
only one maximal ideal.
\item In a finite local ring every element is either a unit or
nilpotent. Moreover, a finite local ring has $p^n$ elements for some
prime $p$ and some integer $n$.
\item The {\em residue field} of a finite local ring is the quotient
of the ring by its maximal ideal. This is a finite field.
\item An element of a finite local ring is a unit if and only if its
image in the residue field is non-zero.
\end{enumerate}
\subsection{Functors of points}
Suppose that we are given a system $S$ of $p$ polynomial equations in
$q$ variables. To every finite ring $A$ we associate the set $S(A)$ of
all $q$-tuples $(a_1,\dots,a_q)$ of elements of $A$ that satisfy this
system of equations. This is an example of a {\em functor} $F$ from
finite rings to finite sets; \ie for every ring $A$ we associate a
finite set $F(A)$ such that if $A\to B$ is a ring homomorphism then we
have a natural map $F(A)\to F(B)$ so that composition of ring
homomorphisms goes to composition of set maps and the identity ring
homomorphism goes to the identity map.
Giving a system $T$ that is ``derived'' from the system $S$ by
substituting the variables by polynomial functions of another set of
$r$ variables is a natural operation on systems of equations. The
analogous notion is that of a morphism of functors (also called a {\em
natural transformation}) $F\to G$. This is a way of giving a map
$F(A)\to G(A)$ so that for any ring homomorphism $A\to B$ we get a
{\em commutative diagram} (any element in the top left corner has the
same image in the bottom right corner independent of the route
followed).
\[
\begin{array}{ccc}
F(A) & \to & G(A) \\
\downarrow & & \downarrow \\
F(B) & \to & G(B)
\end{array}
\]
Some simple examples of such functors are:
\begin{enumerate}
\item To every finite ring we associate the empty set.
\item To every finite ring we associate the singleton set.
\item To every finite ring we associate the underlying set
of the ring.
\item To every finite ring we associate the group of units in the
ring.
\item To every finite ring we associate the collection of $q$ tuples
of elements of the ring.
\end{enumerate}
Each of the above is a particular case of the following more general
construction. Let $R$ be any finitely generated ring (\ie $R$ is a the
quotient of the ring $\bbZ[X_1,\dots,X_q]$ of polynomials with integer
coefficients by some ideal $I$). We have a functor (usually denoted by
$\Spec(R)$) which associates to the finite ring $A$ the finite set of
(unital) ring homomorphisms $\Hom(R,A)$. This can be done by taking
the rings (1) $R=0$ (2) $R=\bbZ$ (3) $R=\bbZ[X]$ (4)
$R=\bbZ[X,Y]/(XY-1)$ and (5) $R=\bbZ[X_r\dots,X_q]$. The associated
geometric objects can conceptualised as (1) empty (2) point (3) line
(4) hyperbola (5) $q$-dimensional {\em affine space} $\bbA^q$ (since
that is what one will get when $A$ is a field). A functor of the form
$\Spec(R)$ for a finitely generated ring $R$ is called an {\em affine
scheme}. If $R$ is a quotient of the polynomial ring
$\bbZ[X_1,\dots,X_q]$ by the ideal generated by polynomials
$(f_1(X_1,\dots,X_q),\dots,f_p(X_1,\dots,X_q))$, then it is clear that
$\Spec(R)(A)$ is naturally identified with the subset of $q$-tuples of
elements of $A$ which satisfy the system of equations given by the
$f_i$.
For those who have studied affine schemes earlier in a slightly
different way we offer the following:
\begin{lemma} Let $R\to S$ be a homomorphism of finitely generated
rings so that for every finite ring $A$ the induced map
$\Hom(S,A)\to\Hom(R,A)$ is a bijection. Then this homomorphism is an
isomorphism.
\end{lemma}
A slightly different example (but one which is fundamental) is the
functor that associates with a ring $A$ the collection of all
$n+1$-tuples $(a_0,a_1,\dots,a_n)$ which generate the ring $A$ upto
multiplication by units. Equivalently, one can think of all surjective
$A$-module homomorphisms $A^{n+1}\to A$ modulo the equivalence induced
by multiplication by units. This functor is denoted $\bbP^n$ and is
conceptualised as the projective $n$-dimensional space. We use the
symbol $(a_0:a_1:\cdots:a_n)$ to denote the equivalence class under
unit multiples of the $n+1$-tuple $(a_0,d_1,\dots,a_n)$ which gives
rise to an element in $\bbP^n(A)$.
Now, if $a=(a_0:a_1:\cdots:a_p)$ and $b=(b_0:b_1:\cdots:b_q)$ are
elements in $\bbP^p(A)$ and $\bbP^q(A)$ respectively, then we can form
the $(p+1)\cdot(q+1)$-tuple consisting of $c_{ij}=a_j\cdot b_j$; this
tuple generates the ring $A$ as well. Clearly, when $a$ and $b$ are
replaced by unit multiples $ua$ and $vb$ for some units $u$ and $v$ in
$A$, the tuple $c=(c_{ij})_{i=0,j=0}^{p,q}$ is replaced by its unit
multiple $(uv)c$. Thus, we have a natural transformation
$\bbP^p\times\bbP^q \to \bbP^{pq+p+q}$. Moreover, one easily checks
that the resulting map on sets
\[ \bbP^p(A)\times\bbP^q(A)\to \bbP^{pq+p+q}(A) \]
is on-to-one for every finite ring $A$. This natural transformation is
called the Segre embedding.
For each positive integer $d$ we can associate to
$a=(a_0:a_1:\cdots:a_p)$ the $\binom{p+d}{d}$ tuple of all monomials
of degree exactly $d$ with the entries from $a$. For example, if $d=2$
then we take the $\binom{p+2}{2}$-tuple consisting of $b_{ij}=a_ia_j$.
As above this gives a natural transformation of functors \(
\bbP^p\to\bbP^{\binom{p+d}{d}-1} \). For each finite ring $A$ the
resulting map on sets
\[ \bbP^p(A)\to\bbP^{\binom{p+d}{d}-1}(A) \]
is one-to-one. This natural transformation is called the $d$-tuple
Veronese embedding.
The two examples above are special cases of projective subschemes
defined as follows. Let $F(X_0,\dots,X_p)$ be any {\em homogeneous}
polynomial in the variables $X_0$,\dots,$X_p$ (in other words all the
monomials in $F$ have the same degree). While the value of $F$ at a
$p+1$-tuple $(a_0,\dots,a_p)$ can change if we multiply the latter by
a unit, this multiplication does nothing if the value is 0. Thus, the
set
\[
V(F)(A) = \{ (a_0:a_1:\cdots:a_p) |
F(a_0,\dots,a_p) = 0 \}
\]
is well-defined. More generally, we can define, for any finite
collection $F_1,\dots,F_n$ of homogeneous polynomials in the same
$p+1$ variables
\[
V(F_1,\dots,F_n)(A) = \{ (a_0:a_1:\cdots:a_p) |
F_i(a_0,\dots,a_p) = 0; \forall i \}
\]
Such sub-functors of $\bbP^p(A)$ are called projective schemes. To
emphasise the point, a functor is a projective scheme if it is
naturally isomorphic to one of the functors of the form
$V(F_1,\dots,F_n)$ for some homogeneous polynomials $F_i$ in the set of
$p+1$ variables $X_i$. In particular, the Segre embedding is given by
the system of all equations of the form $Z_{ij}Z_{kl}=Z_{il}Z_{kj}$.
For any monomial of degree $2d$ and two ways of writing it as a
product of monomials of degree $d$, we obtain a quadratic equation
satisfied by the elements of the Veronese embedding; this system of
equations defines the Veronese embedding.
There is also a natural way of thinking of {\em affine} schemes in
terms of subfunctors of $\bbP^n$ for a suitable $n$. As we saw above
any affine scheme is a subscheme of $\bbA^q$, so it is enough to
exhibit $\bbA^q$ as a subfunctor of $\bbP^n$ for a suitable $n$. Now it
is clear that if $(a_1,\dots,a_q)$ is {\em any} $q$-tuple, then the
collection $(1,a_1,\dots,a_q)$ generates the ring $A$ so that this
defines an element $(1:a_1:\cdots:a_q)$ of $\bbP^q(A)$. Conversely, if
$(a_0:a_1:\cdots:a_q)$ is an element of $\bbP^q(A)$, such that $a_0$
is a unit then this is the same as $(1:a_1/a_0:\cdots:a_q/a_0)$, which
in turn corresponds to the point $(a_1/a_0,\dots,a_q/a_0)$ in
$\bbA^q$.
A generalisation of the above is the notion of a quasi-projective
scheme. In addition to the homogeneous polynomials $F_i$ considered
above let $G_1(X_0,\dots,X_p)$, \dots, $G_m(X_0,\dots,X_p)$ be
homogeneous polynomials {\em of the same degree}. We define a
quasi-projective scheme
\begin{multline*}
V(F_1,\dots,F_n;G_1,\dots,G_m)(A) =
\left\{ \strut (a_0:a_1:\cdots:a_p) \right| \\
F_i(a_0,\dots,a_p) = 0 ;\forall i \\
\text{~and~} \\
\left. \strut (G_1(a_0,\dots,a_p),\dots,G_m(a_0,\dots,a_p))
\text{~generate the ring~} A \right\}
\end{multline*}
Note that, we need to make sense of linear combinations of the $G_i$'s
and hence it is essential that they are all of the same degree. As
before we will be interested in the underlying functor rather than its
given representation as a subfunctor defined by the ``equations'' $F_i$
and the ``inequations'' $G_j$.
One can go further and define the notion of an {\em abstract}
algebraic scheme but for our purposes the notion defined above of a
quasi-projective scheme (of finite type over integers or of
``arithmetic'' type) will suffice.
Let $F_1$,\dots,$F_n$ be a collection of equations which define a
projective scheme and $d$ be no smaller than the maximum of their
degrees. It is clear that the same projective scheme is defined by the
larger collection of the form $F_j\cdot M$ where $j$ varies between 1
and $n$ and $M$ varies over {\em all} monomials of degree
$d-\deg(F_j)$. Thus we can always assume that a projective scheme is
defined by homogeneous equations of the same degree.
The complement of the subscheme of $V(F_1,\dots,F_n)$ is {\em
not} the functor that assigns to each $A$ the set-theoretic
complement $\bbP^p(A)\setminus V(F_1,\dots,F_n)(A)$, but in fact,
when $F_i$'s have the same degree it is the quasi-projective scheme
$V(0;F_1,\dots,F_n)(A)$. The reason for this choice becomes clear as
we study schemes more. For the moment it is enough to note that if
$A$ is the ring $\bbF_p[\epsilon]=\bbF_p[X]/(X^2)$, then the element
$(1:\epsilon:\cdots:\epsilon)$ is in the set-theoretic complement of
$(1:0:\cdots:0)$ in $\bbP^p(A)$ but is {\em not} in the scheme-theoretic
complement that we have defined above.
Finally, let $X\subset \bbP^p$ be a quasi-projective scheme, and let
$F_1$,\dots, $F_n$ be a bunch of homogeneous polynomials of the same
degree. The intersection $X\cap V(F_1,\dots,F_n;1)$ is clearly a
subscheme of $X$ and such subschemes are called {\em closed}
subschemes of $X$. The intersection $X\cap V(0;F_1,\dots,F_n)$ is also
a subscheme of $X$ and such subschemes are called open subschemes of
$X$. More generally, the intersection of
$V(D_1,\dots,D_m;E_1,\dots,E_n)$ and $V(F_1,\dots,F_k;G_1,\dots,G_l)$
is the scheme
\[ V(D_1,\dots,D_m,F_1,\dots,F_k;\{E_i\cdot G_j\}) \]
The ``Hilbert Basis theorem'' asserts that the intersection of {\em
any} (not necessarily finite) collection of closed subschemes is a
closed subscheme.
One very useful example of a closed subscheme is the subscheme
$\bbP^p\subset\bbP^p\times\bbP^p$, which is the diagonal; this is a
closed subscheme of the scheme $\bbP^p\times\bbP^p$ defined by the
conditions $X_iY_j=X_jY_i$ for $0\leq i,j\leq p$. For any $p