Next: 3.2 Encrypting and Decrypting Up: 3 Arithmetic modulo N Previous: 3 Arithmetic modulo N

## 3.1 Faster arithmetic

Given a and b in reduced form in /N, 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 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.

Lemma 5   Let qi denote the inverse of the product (m1 ... mi - 1) in the ring /mi. Given xi in the ring /mi, we inductively define yi as y1 = x1 and

yj = qjxj - (m1 ... mi - 1)yi(mod mj)

Then x = (m1 ... mi - 1)yi is the unique number between 0 and N - 1 such that x = xi(mod mi).

Now that we can compute qi once and for all independent of the xi; secondly, qj. Thus we can do many conversions quickly. Secondly, the sums and products have a structure that permits easy inductive computation (exercise for the reader).

Proof. By construction, we have

(m1 ... mj - 1)yj = xj - (m1 ... mi - 1)yi(mod mj)

Next: 3.2 Encrypting and Decrypting Up: 3 Arithmetic modulo N Previous: 3 Arithmetic modulo N
Kapil Hari Paranjape 2002-10-20