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
/*N* 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 . }*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*^{ . }*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 *x* < *N*. Now let *z* = *xb*.
From the above identity we get *az* = *db* in
/*N*. 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
/*N*, 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}^{ ... }*m*_{r} with
*m*_{i} mutually coprime, then a computationally effective form of the
Chinese Remainder theorem allows us to make *all* arithmetic
operations faster.

(*m*_{1}^{ ... }*m*_{j - 1})*y*_{j} = *x*_{j} - (*m*_{1}^{ ... }*m*_{i - 1})*y*_{i}(mod *m*_{j})