\section{Arithmetic modulo $N$}
Now that we have studied the basic arithmetic operations we can
perform computations in the ring $\bbZ/N\bbZ$. The objects in this
ring are cosets of the form $a+N\bbZ$ for integers $b$. By the process
of division we can write $a=d\cdot N + r$ for $r$ between 0 and $N-1$.
Thus $b+N\bbZ=r+N\bbZ$ and so the objects of $\bbZ/N\bbZ$ can be
identified with integers between $0$ and $N=1$. Thus one way to perform
arithmetic operations in this ring is to perform them with integers
and then, by division, reduce to this canonical form. However, this is
uses more space and time than required.
\subsection{Faster arithmetic}
Given $a$ and $b$ in reduced form in $\bbZ/N\bbZ$, we note that $a+b$
is between $0$ and $2N-2$, while $a-b$ is between $-N+1$ and $N-1$.
Thus a simple subtraction (respectively addition) of $N$ can perform
the necessary reduction. Thus, for example, addition is performed by
comparing $c=a+b$ with $N$; if it is less than $N$ then we return $c$
otherwise we return $c-N$.
When we multiply $a$ and $b$ we can get a number of size comparable to
$N^2$. Thus it would appear that there is no way faster than to
perform division. However, there are alternatives that can be made
faster as we shall see. A similar operation is $a^b$. The following
procedure can be applied to additive and multiplicative structures in
$\bbZ/N\bbZ$ to speed up both operations in some cases.
Let $G$ be a group (or semi-group) and $g$ and element of $G$. Let $k$
be a natural number. We wish to compute $u=g^k$. We have the
recursive identity $g^k=(g^{[k/2]})^2\cdot g^{(k\%2)}$, where $[k/2]$ is
the integer part of $k/2$ and $k\%2$ is 0 or 1 according as $k$ is even
or odd.
If $G$ has an identity element $1$ (i.~e.\ $G$ is monad). We can
proceed as follows. Set $u=1$, $p=g$. We induct on $k$, outputting $u$
when $k$ becomes zero. When $k$ is greater than zero, if $k$ is odd,
we replace $u$ by $u\cdot p$. Then we cwreplace $k$ by $[k/2]$ and
replace $p$ by $p^2$, the square of $p$, before induction on $k$.
This is known as right-left powering.
We can use the recursion directly to define $g^k$ in terms of
$g^{[k/2]}$ and $g^{(k\%2)}$. Now, the latter is either $g$ or $1$,
thus we only need to take squares and multiply by a fixed number $g$.
In particular, when $g$ easy to multiply with there is a substantial
saving of time and space.
The main hurdle for arithmetic modulo $N$ is division (as usual). To
divide by $a$, we apply the extended GCD to $a$ and $N$ (by one of
the earlier algorithms) to get a solution of $xa+yN=d$, where $d$ is
the GCD of $a$ and $N$. Moreover, by appropriately choosing the
initialisation we can also ensure that $0\leq x< N$. Now let $z=xb$.
From the above identity we get $az=db$ in $\bbZ/N\bbZ$. In particular,
if $d=1$, we see that $z$ is the quotient $a/b$ in this ring.
If $k$ is the order of the group of units (invertible elements) in
$\bbZ/N\bbZ$, then $a^k=1$ for any $a$ which is coprime to $N$. Thus,
we see that $a^{k-1}=x$ and this could sometimes be a faster way of
computing $x$. One situation, when $k$ can be computed easily is when
we have a factorisation of $N$.
More generally, in case we have a factorisation $N=m_1\cdots m_r$ with
$m_i$ mutually coprime, then a computationally effective form of the
Chinese Remainder theorem allows us to make {\em all} arithmetic
operations faster.
\begin{lemma}
Let $q_i$ denote the inverse of the product $(m_1\cdots m_{i-1})$ in
the ring $\bbZ/m_i\bbZ$. Given $x_i$ in the ring $\bbZ/m_i\bbZ$, we
inductively define $y_i$ as $y_1=x_1$ and
\[
y_j = q_j\left(
x_j - \sum_{i