Algorithms in Zn
Let n be a positive integer. As before, the elements of Z_{n} will be represented by the integers {0,1,2,... ,nl}.
Observe that if a, b € Z„, then
Hence modular addition (and subtraction) can be performed without the need of a long division. Modular multiplication of a and b may be accomplished by simply multiplying a and b as integers, and then taking the remainder of the result after division by n. Inverses in Z_{n} can be computed using the extended Euclidean algorithm as next described.
2.142 Algorithm Computing multiplicative inverses in Z„
INPUT: a € Z„.
OUTPUT: a^{1} mod ?г, provided that it exists.
 1. Use the extended Euclidean algorithm (Algorithm 2.107) to find integers x and у such that ax + ny = d, where d = gcd(a, ?г).
 2. If d > 1, then a^{1} mod n does not exist. Otherwise, retum(x).
Modular exponentiation can be performed efficiently with the repeated squareand multiply algorithm (Algorithm 2.143), which is crucial for many cryptographic protocols. One version of this algorithm is based on the following observation. Let the binary representation of k be X^=o k'2^{!}> where each /г, e {0,1}. Then
2.143 Algorithm Repeated squareandmultiply algorithm for exponentiation in Z_{n}
INPUT: a e Z„, and integer 0 < к < n whose binary representation is к = k,2^{l}. OUTPUT: a^{k} mod n.
 1. Set b<1. If к = 0 then retum(b).
 2. Set a.
 3. If k_{0} = 1 then set b<—a.
 4. For i from 1 to t do the following:
 4.1 Set A'f— A^{2} mod n.
 4.2 If к, = 1 then set bt—A ■ b mod n.
 5. Retum(6).
 2.144 Example (modular exponentiation') Table 2.4 shows the steps involved in the computation
of 5^{596} mod 1234 = 1013. □
The number of bit operations for the basic operations in Z„ is summarized in Table 2.5. Efficient algorithms for performing modular multiplication and exponentiation are further examined in §14.3 and §14.6.
г 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
la 
0 
0 
1 
0 
1 
0 
1 
0 
0 
1 
A 
5 
25 
G25 
681 
1011 
369 
421 
779 
947 
925 
b 
1 
1 
625 
625 
67 
67 
1059 
1059 
1059 
1013 
Table 2.4: Computation of 5^{596} mod 1234.
Operation 
Bit complexity 
Modular addition (a + b) mod n Modular subtraction (a  b) mod n Modular multiplication (a • b) mod n Modular inversion a~^{l} mod n Modular exponentiation a^{k} mod n, к < n 
O(lgn) O(lgn)

Table 2.5: Bit complexity of basic operations in Z_{n}.