Algorithms in Zn

Let n be a positive integer. As before, the elements of Zn will be represented by the integers {0,1,2,... ,n-l}.

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 Zn 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 square-and- 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 square-and-multiply algorithm for exponentiation in Zn

INPUT: a e Z„, and integer 0 < к < n whose binary representation is к = k,2l. OUTPUT: ak mod n.

  • 1. Set b<-1. If к = 0 then retum(b).
  • 2. Set a.
  • 3. If k0 = 1 then set b<—a.
  • 4. For i from 1 to t do the following:
  • 4.1 Set A'f— A2 mod n.
  • 4.2 If к, = 1 then set b-t—A ■ b mod n.
  • 5. Retum(6).
  • 2.144 Example (modular exponentiation') Table 2.4 shows the steps involved in the computation

of 5596 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 5596 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 ak mod n, к < n

O(lgn)

O(lgn)

  • 0((lgn)2)
  • 0((lg?r)2)
  • 0((lgn)3)

Table 2.5: Bit complexity of basic operations in Zn.

 
Source
< Prev   CONTENTS   Source   Next >