\section{Primes and Composites}
We have seen that it is necessary to find large primes quickly in
order to generate cryptosystems. The cryptanalyst's job is to factor
numbers into prime factors (or at least find many prime factors of a
number). We examine these problems in this section.
\subsection{Eratosthenes' sieve}
The most traditional way of finding prime numbers is the sieve of
Eratosthenes. Suppose we are given a list $l$ of all primes less than
the integer $n$. Then $n$ is prime if it is not a multiple of any of
these. Thus, if we have also a list $m$, so that $m_i$ is the least
multiple of the prime $l_i$ that is not less than $n$, we can compare
$n$ with elements of this list to decide if it is a prime. The
incremental step can then be carried out as follows. We run through
the list $m_i$ look for $n$. Whenever we find $n$ we note that $n$ is
composite and replace $m_i$ by $m_i+l_i$. If we come to the end of the
list without find such an $i$, then $n$ is a prime so we append it to
the end of $l$; we also append $2*n$ to the end of $m$. In this way we
can iteratively generate the list of all primes!
Clearly as the list grows larger this is taking up more and more space
and time. Moreover, it gives us no way of checking if a given number
is prime except by running through all primes before it.
\subsection{Trial division}
If $N=a\cdot b$ is a factoring of a number $N$, then at least one of
the numbers $a$, $b$ is such that its square is not more than $N$.
Thus to check, whether $N$ is a prime, it is enough to test whether it
is a multiple of prime number $p$ so that $p^2$ is not more than $N$.
This leads to the first test that does not require a list of all
primes less than $N$. Given the increasing sequence $l$ of all primes
less than some number $x$ so that $x^2>N$, we check for the primality
of $N$ as follows. We run through the sequence $l$, dividing $N$ by
the primes $l_i$ to obtain $N=q_il_i+r_i$. If $r_i$ is zero then $N$
is not a prime and we stop. If $q_iN$ so have
checked enough prime factors to show that $N$ is a prime and we stop.
\subsection{Combinations of the methods}
When we compare the trial division method with Eratosthenes' sieve, we
see that we are only checking for divisors upto $\sqrt{N}$, {\em but}
we are performing divisions rather than the (much simpler) additions.
Thus there should be a way of improving the Eratosthenes' method.
First of all, when we find a new prime $m$ we should append the {\em
square} $m^2$ to the list of multiples rather than $2*m$; all
smaller multiples of $m$ are also multiples of smaller primes! This is
not enough to speed up the sieve computation since we will still be
comparing our trial prime $m$ with all the elements in the multiple
list instead of only the ``relevant'' ones; the list of multiples
grows as fast as the list of primes, whereas the multiples we need to
check against are only multiples of primes less than the square root.
Thus we keep a pointer $s$ into the list $m$ that keeps track of where
the list of squares in this list start. We do not check for multiples
beyond this point. This extension of the sieve using the idea from
trial division is a good way to generate lists of primes.
Trial division is then only a method to check for primality for a
small set of numbers and not a method for building lists. Its one
big limitation is its dependence on a list of all primes upto
$\sqrt{N}$. We do not want to keep extending our list of primes
(otherwise we may as well be generating using the sieve as
above). So we can ask if we can improve trial division using ideas
from the sieve.
It is possible to append a ``sieve'' at the end of the given list
of primes $l$ as follows. Let $M$ the product of a the first few prime
numbers (say 6 or 30 or 210). Let $S$ be the (naturally ordered)
collection of representatives between 0 and $M-1$ of the units in
$\bbZ/M\bbZ$.
After we exhaust the given list $l$ without obtaining $q_ik_1$ (or vice versa) then we see that the
second term is no more than $1/2^r$ so we have the result in this
case as well. Thus we may assume that $k_1=k_2=l$. Now, if
$\gcd(q,q_1)0} [n/p^i]$. In particular, if $p$
is odd then the latter term goes to infinity with $n$.
\end{enumerate}
\end{lemma}
\begin{proof} Exercise.
\end{proof}
It follows that only finitely many terms of the power series
\[ \log(1-x)=-\sum_{i\geq 0} \frac{x^i}{i+1}\]
survive in $\bbZ/p^e\bbZ$ when we
substitute $x$ by a multiple of $p$. Thus we obtain a map
\[ \log : U_1 \to \bbZ/p^e\bbZ \]
which in fact takes values in the ideal $p\bbZ/p^e\bbZ$, which
isomorphic to the additive group $\bbZ/p^{e-1}\bbZ$. Elementary
manipulations of the power series combined with the binomial theorem
and the fact that all but finitely many terms are zero can be used to
show that $\log(1+x\cdot y + x + y)=\log(1+x)+\log(1+y)$. Similarly,
for $p$ odd we obtain a map
\[ \exp: p\bbZ/p^e\bbZ \to U_1 \]
by means of the usual power series
\[ \exp(x) = \sum_{i\geq 0} \frac{x^i}{i!} \]
which satisfies $\exp(x+y)=\exp(x)\cdot\exp(y)$. We also check by
direct substitution that $\log(\exp(x))=x$ and vice versa. It follows
that the group $U_1$ is isomorphic to the group $p\bbZ/p^e\bbZ$ which
is in turn isomorphic to $\bbZ/p^{e-1}\bbZ$. We note in passing that
a generator $g$ of $U_1$ of order $p^{e-1}$ corresponds to the generator
$p$ in $p\bbZ/p^e\bbZ$ via the expression $g=\exp(p)$!
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End: