When we multiply a and b we can get a number of size comparable to N2. 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 ab. 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 = gk. We have the recursive identity gk = (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 p2, the square of p, before induction on k. This is known as right-left powering.
We can use the recursion directly to define gk 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 ak = 1 for any a which is coprime to N. Thus, we see that ak - 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 = m1 ... mr with mi mutually coprime, then a computationally effective form of the Chinese Remainder theorem allows us to make all arithmetic operations faster.