Page 274 - Discrete Mathematics and Its Applications

4.2 Integer Representations and Algorithms 253

ALGORITHM FOR div AND mod Given integers a and d, d> 0, we can find q =
a div d and r = a mod d using Algorithm 4. In this brute-force algorithm, when a is pos-
itive we subtract d from a as many times as necessary until what is left is less than d. The
number of times we perform this subtraction is the quotient and what is left over after all these
subtractions is the remainder. Algorithm 4 also covers the case where a is negative. This algo-
rithm finds the quotient q and remainder r when |a| is divided by d. Then, when a< 0 and
r> 0, it uses these to find the quotient −(q + 1) and remainder d − r when a is divided by d.
We leave it to the reader (Exercise 59) to show that, assuming that a> d, this algorithm uses
O(q log a) bit operations.

ALGORITHM 4 Computing div and mod.

procedure division algorithm(a: integer, d: positive integer)
q := 0
r := |a|
while r ≥ d
r := r − d
q := q + 1
if a< 0 and r> 0 then
r := d − r
q := −(q + 1)
return (q, r) {q = a div d is the quotient, r = a mod d is the remainder}

There are more efficient algorithms than Algorithm 4 for determining the quotient q =
a div d and the remainder r = a mod d when a positive integer a is divided by a positive
integer d (see [Kn98] for details). These algorithms require O(log a · log d) bit operations. If
both of the binary expansions of a and d contain n or fewer bits, then we can replace log a · log d
2
2
by n . This means that we need O(n ) bit operations to find the quotient and remainder when
a is divided by d.

Modular Exponentiation

n
In cryptography it is important to be able to find b mod m efficiently, where b, n, and m are
n
large integers. It is impractical to first compute b and then find its remainder when divided
n
by m because b will be a huge number. Instead, we can use an algorithm that employs the
binary expansion of the exponent n.
Before we present this algorithm, we illustrate its basic idea. We will explain how to use
n
the binary expansion of n, say n = (a k−1 ...a 1 a 0 ) 2 , to compute b . First, note that

n
a 0
b = b a k−1 ·2 k−1 +···+a 1 ·2+a 0 = b a k−1 ·2 k−1 ··· b a 1 ·2 · b .
n 2 2 2 4 4 2
This shows that to compute b , we need only compute the values of b, b , (b ) = b , (b ) =
j
k
2
2
8
b ,...,b . Once we have these values, we multiply the terms b in this list, where a j = 1. (For
n
efficiency, after multiplying by each term, we reduce the result modulo m.) This gives us b .For
8 2 1
example, to compute 3 11 we first note that 11 = (1011) 2 , so that 3 11 = 3 3 3 . By successively
2
2
4
2
8
squaring, we find that 3 = 9, 3 = 9 = 81, and 3 = (81) = 6561. Consequently, 3 11 =
8 2 1
3 3 3 = 6561 · 9 · 3 = 177,147.