3.1 Faster arithmetic

Given a and b in reduced form in $\mathbb {Z}$/N$\mathbb {Z}$, 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². 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 $\mathbb {Z}$/N$\mathbb {Z}$ 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², 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 $\mathbb {Z}$/N$\mathbb {Z}$. 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 $\mathbb {Z}$/N$\mathbb {Z}$, 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₁ ^... 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.

Lemma 5   Let q_i denote the inverse of the product (m₁ ^... m_{i - 1}) in the ring $\mathbb {Z}$/m_i$\mathbb {Z}$. Given x_i in the ring $\mathbb {Z}$/m_i$\mathbb {Z}$, we inductively define y_i as y₁ = x₁ and

y_j = q_j$$\left(\vphantom{ x_j - \sum_{i<j} (m_1\cdots m_{i-1})y_i }\right.$$x_j - $$\sum_{i<j}^{}$$(m₁ ^... m_{i - 1})y_i$$\left.\vphantom{ x_j - \sum_{i<j} (m_1\cdots m_{i-1})y_i }\right)$$(mod m_j)

Then x = $\sum_{i}^{}$(m₁ ^... m_{i - 1})y_i is the unique number between 0 and N - 1 such that x = x_i(mod m_i).

Now that we can compute q_i once and for all independent of the x_i; secondly, q_j. 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

(m₁ ^... m_{j - 1})y_j = $$\left(\vphantom{ x_j - \sum_{i<j} (m_1\cdots m_{i-1})y_i }\right.$$x_j - $$\sum_{i<j}^{}$$(m₁ ^... m_{i - 1})y_i$$\left.\vphantom{ x_j - \sum_{i<j} (m_1\cdots m_{i-1})y_i }\right)$$(mod m_j)

$\qedsymbol$