Arithmetic Modulo m Arithmetic Modulo m

Definitions: Let Zm be the set of nonnegative integers The operations +m and ∙m satisfy many of the same properties as
less than m: ordinary addition and multiplication.
{0,1, …., m−1} – Closure: If a and b belong to Zm , then a +m b and a ∙m b
belong to Zm .
The operation +m is defined as a +m b = (a + b) mod m.
This is addition modulo m. – Associativity: If a, b, and c belong to Zm , then
(a +m b) +m c = a +m (b +m c) and (a ∙m b) ∙m c = a ∙m (b ∙m c).
The operation ∙m is defined as a ∙m b = (a + b) mod m. This – Commutativity: If a and b belong to Zm , then
is multiplication modulo m. a +m b = b +m a and a ∙m b = b ∙m a.
Using these operations is said to be doing arithmetic – Identity elements: The elements 0 and 1 are identity
modulo m. elements for addition and multiplication modulo m,
respectively.
Example: Find 7 +11 9 and 7 ∙11 9.
• If a belongs to Zm , then a +m 0 = a and a ∙m 1 = a.
Solution: Using the definitions above:
– 7 +11 9 = (7 + 9) mod 11 = 16 mod 11 = 5
– 7 ∙11 9 = (7 ∙ 9) mod 11 = 63 mod 11 = 8

22 Sept 2015 CS 320 1 22 Sept 2015 CS 320 2

Representations of Integers
Arithmetic Modulo m Let b be a positive integer greater than 1.
– Additive inverses: If a≠ 0 belongs to Zm , then m− a is the Then if n is a positive integer, it can be expressed
additive inverse of a modulo m and 0 is its own additive inverse.
• a +m (m− a ) = 0 and 0 +m 0 = 0 uniquely in the form:
– Distributivity: If a, b, and c belong to Zm , then
• a ∙m (b +m c) = (a ∙m b) +m (a ∙m c) and n = akbk + ak-1bk-1 + … + a1b + a0,
(a +m b) ∙m c = (a ∙m c) +m (b ∙m c).
Exercises 42-44 ask for proofs of these properties.
Multiplicatative inverses have not been included since they do not always where k is a nonnegative integer,
exist. For example, there is no multiplicative inverse of 2 modulo 6. a0, a1, …, ak are nonnegative integers less than b,
But every non zero element of Zm will have a multiplicative inverse if
m is a prime. and ak ≠ 0.
(optional) Using the terminology of abstract algebra, Zm with +m is a
commutative group and Zm with +m and ∙m is a commutative ring. Example for b=10:
If m is prime then Zm is a field.
859 = 8⋅102 + 5⋅101 + 9⋅100
22 Sept 2015 CS 320 3 22 Sept 2015 CS 320 4

Representations of Integers Representations of Integers

How can we construct the base b expansion of an
integer n?
Example for b=2 (binary expansion):
First, divide n by b to obtain a quotient q0 and
(10110)2 = 1⋅24 + 1⋅22 + 1⋅21 = (22)10 remainder a0, that is,
n = bq0 + a0, where 0 ≤ a0 < b.
Example for b=16 (hexadecimal expansion):
The remainder a0 is the rightmost digit in the base b
(we use letters A to F to indicate numbers 10 to 15) expansion of n.
(3A0F)16 = 3⋅163 + 10⋅162 + 0⋅161 + 15⋅160 = (14863)10 Next, divide q0 by b to obtain:
q0 = bq1 + a1, where 0 ≤ a1 < b.
a1 is the second digit from the right in the base b
expansion of n. Continue this process until you obtain
a quotient equal to zero.
22 Sept 2015 CS 320 5 22 Sept 2015 CS 320 6

1
 Representations of Integers Representations of Integers
Example: procedure base_b_expansion(n, b: positive integers)
What is the base 8 expansion of (12345)10 ? q := n
k := 0
First, divide 12345 by 8: while q ≠ 0
12345 = 8⋅1543 + 1 begin
ak := q mod b
1543 = 8⋅192 + 7
q := q/b
192 = 8⋅24 + 0
k := k + 1
24 = 8⋅3 + 0
end
3 = 8⋅0 + 3
{the base b expansion of n is (ak-1 … a1a0)b }
The result is: (12345)10 = (30071)8.
22 Sept 2015 CS 320 7 22 Sept 2015 CS 320 8

Addition of Integers Addition of Integers

How do we (humans) add two integers? Let a = (an-1an-2…a1a0)2, b = (bn-1bn-2…b1b0)2.
How can we algorithmically add these two binary
1 11 carry
numbers?
Example: 7583
+ 4932 First, add their rightmost bits:
a0 + b0 = c0⋅2 + s0,
12515
where s0 is the rightmost bit in the binary expansion
1 1 carry of a + b, and c0 is the carry.
Binary expansions: (1011)2
Then, add the next pair of bits and the carry:
+ (1010)2
a1 + b1 + c0 = c1⋅2 + s1,
(101 01 )2 where s1 is the next bit in the binary expansion of a +
b, and c1 is the carry.
22 Sept 2015 CS 320 9 22 Sept 2015 CS 320 10

Addition of Integers Addition of Integers

Example:
Add a = (1110)2 and b = (1011)2.
Continue this process until you obtain cn-1.
a0 + b0 = 0 + 1 = 0⋅2 + 1, so that c0 = 0 and s0 = 1.
The leading bit of the sum is sn = cn-1.
a1 + b1 + c0 = 1 + 1 + 0 = 1⋅2 + 0, so c1 = 1 and s1 = 0.
The result is: a2 + b2 + c1 = 1 + 0 + 1 = 1⋅2 + 0, so c2 = 1 and s2 = 0.
a + b = (snsn-1…s1s0)2 a3 + b3 + c2 = 1 + 1 + 1 = 1⋅2 + 1, so c3 = 1 and s3 = 1.
s4 = c3 = 1.

Therefore, s = a + b = (11001)2.

22 Sept 2015 CS 320 11 22 Sept 2015 CS 320 12

2
 Addition of Integers Multiplication of Integers
procedure add(a, b: positive integers) procedure multiply(a, b: positive integers)
// ai, bi are the bits of a and b. // ai, bi are the bits of a and b.
c := 0 for j := 0 to n-1
for j := 0 to n-1 begin
begin
if bj = 1 then cj := a shifted left j places
else cj := 0 // cj are the partial products
d := (aj + bj + c)/2 // gives the high bit of sum end
sj := aj + bj + c – 2d // gives the low bit of sum p := 0
c := d for i := 0 to n-1
end p := p + cj
sn := c {p is the value of the product as an integer.
{the binary expansion of the sum is (snsn-1…s1s0)2} Note that we haven’t computed bits for p}

22 Sept 2015 CS 320 13 22 Sept 2015 CS 320 14

More Algorithms Section Summary

Take a look at Algorithms 4 and 5 on
pages 253, 254 and be sure you
understand them. It’s important to be
able to read the code and see what it Integer Representations
says. – Base b Expansions
Algorithm 4 gives a way of doing the – Binary Expansions
division algorithm using repeated – Octal Expansions
subtractions instead of division. – Hexadecimal Expansions
Algorithm 5 gives a way of computing bn Base Conversion Algorithm
using a binary representation of n
Algorithms for Integer Operations
16
22 Sept 2015 CS 320 15 22 Sept 2015

Representations of Integers Base b Representations

We can use positive integer b greater than 1 as a base, because of
this theorem:
In the modern world, we use decimal, or base
10, notation to represent integers. For example Theorem 1: Let b be a positive integer greater than 1.
Then if n is a positive integer, it can be expressed
when we write 965, we mean 9∙102 + 6∙101 + uniquely in the form:
5∙100 . n = akbk + ak-1bk-1 + …. + a1b + a0
We can represent numbers using any base b, where k is a nonnegative integer, a0,a1,…. ak are
where b is a positive integer greater than 1. nonnegative integers less than b, and ak≠ 0. The aj, j
The bases b = 2 (binary), b = 8 (octal) , and b= = 0,…,k are called the base-b digits of the
16 (hexadecimal) are important for computing representation.
and communications
(We will prove this using mathematical induction in Section 5.1.)
The ancient Mayans used base 20 and the The representation of n given in Theorem 1 is called the base b
ancient Babylonians used base 60. expansion of n and is denoted by (akak-1….a1a0)b.
We usually omit the subscript 10 for base 10 expansions.
17 18
22 Sept 2015 22 Sept 2015

3
 Binary Expansions Binary Expansions
Most computers represent integers and do
arithmetic with binary (base 2) expansions of Example: What is the decimal
integers. In these expansions, the only digits expansion of the integer that has
used are 0 and 1.
Example: What is the decimal expansion of the (11011)2 as its binary expansion?
integer that has (1 0101 1111)2 as its binary Solution: (11011)2 = 1 ∙24 + 1∙23 +
expansion?
Solution: 0∙22 + 1∙21 + 1∙20 =27.
(1 0101 1111)2 = 1∙28 + 0∙27 + 1∙26 + 0∙25 +
1∙24 + 1∙23 + 1∙22 + 1∙21 + 1∙20 =351.

22 Sept 2015 19
22 Sept 2015 20

Octal Expansions Octal Expansions

The octal expansion (base 8) uses the
digits {0,1,2,3,4,5,6,7}.
Example: What is the decimal
Example: What is the decimal expansion of the number with octal
expansion of the number with octal expansion (111)8 ?
expansion (7016)8 ?
Solution: 7∙83 + 0∙82 + 1∙81 + 6∙80 Solution: 1∙82 + 1∙81 + 1∙80 = 64
=3598 + 8 + 1 = 73

22 Sept 2015 21 22 Sept 2015 22

Hexadecimal Expansions Base Conversion

The hexadecimal expansion needs 16 digits, but our To construct the base b expansion of an integer
decimal system provides only 10. So letters are used for n:
the additional symbols. The hexadecimal system uses – Divide n by b to obtain a quotient and remainder.
the digits {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. The letters A n = bq0 + a0 0 ≤ a0 ≤ b
through F represent the decimal numbers 10 through – The remainder, a0 , is the rightmost digit in the base b
15. expansion of n. Next, divide q0 by b.
Example: What is the decimal expansion of the number q0 = bq1 + a1 0 ≤ a1 ≤ b
with hexadecimal expansion (2AE0B)16 ? – The remainder, a1, is the second digit from the right in
Solution: the base b expansion of n.
2∙164 + 10∙163 + 14∙162 + 0∙161 + 11∙160 =175627 – Continue by successively dividing the quotients by b,
Example: What is the decimal expansion of the number obtaining the additional base b digits as the remainder.
with hexadecimal expansion (E5)16 ? The process terminates when the quotient is 0.
Solution: 1∙162 + 14∙161 + 5∙160 = 256 + 224 + 5 = 485
22 Sept 2015 23 22 Sept 2015
continued → 24

4
 Algorithm: Constructing Base b Base Conversion
Expansions
Example: Find the octal expansion of
procedure base b expansion(n, b: positive integers with b > 1)
q := n
(12345)10
k := 0
while (q ≠ 0)
Solution: Successively dividing by 8 gives:
ak := q mod b
q := q div b
– 12345 = 8 ∙ 1543 + 1
k := k + 1
return(ak-1 ,…, a1,a0){(ak-1 … a1a0)b is base b expansion of n} – 1543 = 8 ∙ 192 + 7
– 192 = 8 ∙ 24 + 0
q represents the quotient obtained by successive
divisions by b, starting with q = n. – 24 = 8 ∙ 3 + 0
The digits in the base b expansion are the remainders of – 3 =8∙0+3
the division given by q mod b.
The algorithm terminates when q = 0 is reached. The remainders are the digits from right to left
26
yielding (30071)8.
22 Sept 2015 25 22 Sept 2015

Comparison of Hexadecimal, Octal, Conversion Between Binary, Octal, and

Hexadecimal Expansions
and Binary Representations
Example: Find the octal and hexadecimal
expansions of (11 1110 1011 1100)2.
Solution:
– To convert to octal, we group the digits into blocks
of three (011 111 010 111 100)2, adding initial 0s
as needed. The blocks from left to right
correspond to the digits 3,7,2,7, and 4. Hence, the
Initial 0s are not shown
solution is (37274)8.
– To convert to hexadecimal, we group the digits
Each octal digit corresponds to a block of 3 binary digits. into blocks of four (0011 1110 1011 1100)2, adding
Each hexadecimal digit corresponds to a block of 4 binary initial 0s as needed. The blocks from left to right
digits. correspond to the digits 3,E,B, and C. Hence, the
solution is (3EBC)16.
So, conversion between binary, octal, and hexadecimal is
easy.
22 Sept 2015 27 22 Sept 2015 28

Binary Addition of Integers Binary Addition of Integers

Algorithms for performing operations with integers procedure add(a, b: positive integers)
using their binary expansions are important as {the binary expansions of a and b are (an-1,an-2,…,a0)2 and
computer chips work with binary numbers. Each (bn-1,bn-2,…,b0)2, respectively}
digit is called a bit. c := 0
for j := 0 to n − 1
d := ⌊(aj + bj + c)/2⌋
sj := aj + bj + c − 2d
The number of additions of bits used by the algorithm to add c := d
two n-bit integers is O(n). sn := c
return(s0,s1,…, sn)
{the binary expansion of the sum is (sn,sn-1,…,s0)2}
22 Sept 2015 29 22 Sept 2015 30

5
 Binary Multiplication of Integers Binary Modular Exponentiation
Algorithm for computing the product of two n bit integers.

procedure multiply(a, b: positive integers) In cryptography, it is important to be able to find bn mod m

{the binary expansions of a and b are (an-1,an-2,…,a0)2 and (bn-1,bn-2,…,b0)2, efficiently, where b, n, and m are large integers.
respectively} Use the binary expansion of n, n = (ak-1,…,a1,ao)2 , to compute bn .
for j := 0 to n − 1 Note that:
if bj = 1 then cj = a shifted j places
else cj := 0
{co,c1,…, cn-1 are the partial products}
p := 0 Therefore, to compute bn, we need only compute the values of b,
for j := 0 to n − 1 b2, (b2)2 = b4, (b4)2 = b8 , …, and then multiply the terms
p := p + cj in this list, where aj = 1.
return p {p is the value of ab}

Example: Compute 311 using this method.

The number of additions of bits used by the algorithm to multiply two n-bit integers is
Solution: Note that 11 = (1011)2 so that 311 = 38 32 31 =
O(n2). ((32)2 )2 32 31 = (92 )2 ∙ 9 ∙3 = (81)2 ∙ 9 ∙3 =6561 ∙ 9 ∙3 =117,147.

continued →
22 Sept 2015 31 22 Sept 2015 32

Binary Modular Exponentiation

Algorithm
The algorithm successively finds b mod m, b2
mod m, b4 mod m, …, mod m,
and multiplies together the
terms where aj = 1.
procedure modular exponentiation(b: integer, n = (ak-1ak-2…a1a0)2 , m: positive
integers)
x := 1
power := b mod m
for i := 0 to k − 1
if ai= 1 then x := (x∙ power ) mod m
power := (power∙ power ) mod m
return x {x equals bn mod m }

– O((log m )2 log n) bit operations are used to find bn mod m.

33
22 Sept 2015