Algorithmic Algebra - A Classical Introduction to Cryptography: Applications for Communications Security - page 167

We can check that 18 mod 5 = 3 and 18 mod 7 = 4.

This theorem can be used to compute exponentiation in Z mn faster. Since Z mn
is isomorphic to the Z m ×

Z n product structure, instead of computing a e

mod mn ,

we can compute a e mod m and a e mod n which gives a e

Z n . Then we can
use the Chinese Remainder Theorem to recover a e mod mn . Since the complexity of
exponentiation is cubic in the size of the modulus, assuming that m and n are half of
the size of mn , exponentiation in Z m costs 1

in Z m ×

8 of the exponentiation price in Z mn ,
as well as exponentiation in Z n . Since applying the Chinese Remainder Theorem is
quadratic, we speed up the exponentiation by a factor of 4. This method needs however
to use the factorization of mn , which is not always available as we will see in the next
sections.

/

For instance, if we want to compute 2 23 mod 35, we first compute 2 23 mod 5 and
2 23 mod 7. For 2 23 mod 5, we notice that Z 5 has a cardinality of 4 since Z 5 is a field
(see Section 6.3). Hence the Lagrange theorem implies that 2 4

mod 5 = 1. We can

3, and obtain 2 23 2 3

reduce 23 modulo 4, by 23 = 4 × 5 + mod 5 = mod 5. It is

now easy to compute 2 3 mod 5 which gives 2 23 3. Similarly, 2 23

mod 5 = mod 7 =

2 5 4. Now we apply the Chinese Remainder Theorem for computing f − 1 (3 mod 7 = , 4)

and obtain that 2 23 18. If we apply the algorithm of Fig. 6.6, we ob-

tain the following sequence of x values in step 2 with the corresponding bits of
e

mod 35 =

= 23

e 1 0 1 1 1

x 1 4 16 9 9

=

and we terminate with x 18 as well.

We summarize all the above algorithms by the following complexities for compu-
tations in Z n . We assume that all operands are lesser than n .
Addition: linear in the size of n .
Multiplication, inversion, gcd: quadratic in the size of n .
Exponentiation: cubic in the size of n .

6.3 The Finite Field Z p

6.3.1 Basic Properties of Z p

We recall that a field is a ring K in which the multiplicative group K ∗ consists of
all nonzero ring elements. This means that all elements but zero are invertible for the
multiplication.