University of Hawaii

ICS141:
Discrete Mathematics for
Computer Science I
Dept. Information & Computer Sci., University of Hawaii

Jan Stelovsky
based on slides by Dr. Baek and Dr. Still
Originals by Dr. M. P. Frank and Dr. J.L. Gross
Provided by McGraw-Hill

ICS 141: Discrete Mathematics I – Fall 2011 13-1

 University of Hawaii

Lecture 18a
Chapter 3. The Fundamentals
3.6 Applications of Integers Algorithms

ICS 141: Discrete Mathematics I – Fall 2011 13-2

 Quiz
University of Hawaii

1.  What is the decimal expansion (1AF)16?

2.  What is the hexadecimal expansion of (287)10?
3.  What is the two’s complement of -7?
4.  Multiply (100)2 and (101)2 in binary system.

n  Hints
n  162 = 256

ICS 141: Discrete Mathematics I – Fall 2011 13-3

 Applications
University of Hawaii

n  Miscelaneous useful results

n  Linear congruences
n  Chinese Remainder Theorem
n  Pseudoprimes
n  Fermat’s Little Theorem

n  Public Key Cryptography

n  The Rivest-Shamir-Adleman (RSA)

cryptosystem

ICS 141: Discrete Mathematics I – Fall 2011 13-4

 Miscelaneous Results
University of Hawaii

n  Theorem 1:
n  ∀a,b ∈ Z : ∃s,t ∈Z: gcd(a,b) = sa + tb
+

n  Lemma 1:
n  ∀a,b,c ∈ Z : gcd(a,b)=1 ∧ a | bc → a|c
+

n  Lemma 2:
n  If p is prime and p|a1a2…an (integers ai)
then ∃i: p|ai.
n  Theorem 2:
n  If ac ≡ bc (mod m) and gcd(c,m)=1, then
a ≡ b (mod m). (m∈Z+, a,b,c∈Z)

ICS 141: Discrete Mathematics I – Fall 2011 13-5

 Theorem 1
University of Hawaii

n  Theorem 1:
∀a,b∈Z+: ∃s,t ∈Z such that gcd(a,b) = sa + tb
n  Proof: By induction over the value of the
larger argument a.

n  Example:
n  Express gcd(252, 198) = 18 as a linear

combination of 252 and 198.

ICS 141: Discrete Mathematics I – Fall 2011 13-6

 Proof of Theorem 1
University of Hawaii

Theorem 1: ∀b,a∈Z+: ∃s,t ∈Z : gcd(a,b) = sa + tb

Proof: (By induction over the value of the larger
argument a.)
n  ByTheorem 0 gcd(a,b) = gcd(b,c) if c = a mod b, i.e.,
a = kb + c for some integer k, and thus c = a − kb.
n  Now, since b<a and c<b, by inductive hypothesis,
we can assume that ∃u,v: gcd(b,c) = ub + vc.
n  Substituting for c, this is ub+v(a−kb), which we can
regroup to get va + (u−vk)b.
n  So now let s = v, and let t = u−vk, and we’re finished.
n  The base case: s = 1 and t = 0.
This works for gcd(a,0), or if a=b originally. ■
ICS 141: Discrete Mathematics I – Fall 2011 13-7
 Theorem 1: Example
University of Hawaii

n  Express gcd(252, 198) = 18 as a linear combination of

252 and 198.
n  252 = 1 ⋅ 198 + 54

198 = 3 ⋅ 54 + 36
Euclidean algorithm
54 = 1 ⋅ 36 + 18
36 = 2 ⋅ 18

n  18 = 54 – 1 ⋅ 36 = 54 – 1 ⋅ (198 – 3 ⋅ 54)

= 4 ⋅ 54 – 1 ⋅ 198
= 4 ⋅ (252 – 1 ⋅ 198) – 1 ⋅ 198
= 4 ⋅ 252 – 5 ⋅ 198

n  Therefore, gcd(252, 198) = 18 = 4 ⋅ 252 – 5 ⋅ 198

ICS 141: Discrete Mathematics I – Fall 2011 13-8
 Proof of Lemma 1
University of Hawaii

n  Lemma 1:
∀a,b,c ∈ Z+: gcd(a,b)=1 ∧ a|bc → a|c
Proof:
n  Applying theorem 1, ∃s, t: sa + tb = 1.

n  Multiplying through by c, we have that

sac + tbc = c.
n  Since a|bc is given, we know that a|tbc,
and obviously a|sac.
n  Thus (using the theorem on pp.202), it
follows that a|(sac+tbc); in other words,
that a|c. ■
ICS 141: Discrete Mathematics I – Fall 2011 13-9
 Proof of Lemma 2
University of Hawaii

n  Lemma 2: If p is prime and p|a1a2…an (integers

ai) then p|ai for some i.
Proof (by induction):
n  If n=1, this is immediate since p|a0 → p|a0.
Suppose the lemma is true for all n<k and p|a1…ak.
n  If p|m where m=a1…ak-1 then we have it inductively.
n  Otherwise, we have p|mak but ¬(p|m).
Since m is not a multiple of p, and p has no factors,
m has no common factors with p, thus gcd(m,p)=1.
So by applying Lemma 1, p|ak. ■

ICS 141: Discrete Mathematics I – Fall 2011 13-10

 Theorem 2
University of Hawaii

n  Theorem 2: Let m∈Z+ and a,b,c∈Z.

If ac ≡ bc (mod m) and gcd(c,m)=1, then a ≡ b (mod m).
Proof:
n  Since ac ≡ bc (mod m), this means m | ac−bc.

n  Factoring the right side, we get m | c(a − b).

Since gcd(c,m)=1, lemma 1 implies that m | a−b,

in other words, that a ≡ b (mod m). ■
n  Examples
n  20 ≡ 8 (mod 3) i.e. 5 ⋅ 4 ≡ 2 ⋅ 4 (mod 3)

Since gcd(4, 3) = 1, 5 ≡ 2 (mod 3)

n  14 ≡ 8 (mod 6) but 7 ≡ 4 (mod 6) (as gcd(2,6) ≠ 1)

ICS 141: Discrete Mathematics I – Fall 2011 13-11

 Linear Congruences, Inverses
University of Hawaii

n  A congruence of the form ax ≡ b (mod m) is

called a linear congruence. (m∈Z+, a,b∈Z,
and x: variable)
n  To solve the congruence is to find the x’s that
satisfy it.
n  An inverse of a, modulo m is any integer
a-1 such that a-1a ≡ 1 (mod m).
n  If we can find such an a-1, notice that we can
then solve ax ≡ b (mod m) by multiplying through
by it, giving a-1ax ≡ a-1b (mod m), thus
1·x ≡ a-1b (mod m), thus x ≡ a-1b (mod m).

ICS 141: Discrete Mathematics I – Fall 2011 13-12

 Theorem 3
University of Hawaii

n  Theorem 3: If gcd(a,m)=1 (i.e. a and m are relatively

prime) and m > 1,
then a has a inverse a-1 unique modulo m.
Proof:
n  By theorem 1, ∃s,t: sa + tm = 1, so sa + tm ≡ 1 (mod m).
n  Since tm ≡ 0 (mod m), sa ≡ 1 (mod m).
Thus s is an inverse of a (mod m).
n  Theorem 2 guarantees that if ra ≡ sa ≡ 1 then r ≡ s,
thus this inverse is unique modulo m.
(All inverses of a are in the same congruence class as s.)
■
ICS 141: Discrete Mathematics I – Fall 2011 13-13
 Example
University of Hawaii

n  Find an inverse of 3 modulo 7

n  Since gcd(3, 7) = 1, by Theorem 3 there exists
an inverse of 3 modulo 7.
n  7 = 2·3 + 1
n  From the above equation, –2·3 + 1·7 = 1
n  Therefore, –2 is an inverse of 3 modulo 7

n  Note that every integer congruent to –2 modulo

7 is also an inverse of 3, such as 5, –9, 12, and
so on.)

ICS 141: Discrete Mathematics I – Fall 2011 13-14

 Example
University of Hawaii

n  What are the solutions of the linear

congruence 3x ≡ 4 (mod 7)?
n  –2 is an inverse of 3 modulo 7 (previous slide)
n  Multiply both side by –2: –2·3x ≡ –2·4 (mod 7)
n  –6·x ≡ x ≡ –8 ≡ 6 (mod 7)
n  Therefore, the solutions to the congruence are
the integers x such that x ≡ 6 (mod 7), i.e. 6, 13,
20, 27,… and –1, –8, –15,…

n  e.g. 3·13 = 39 ≡ 4 (mod 7)

ICS 141: Discrete Mathematics I – Fall 2011 13-15

 University of Hawaii

An Application of Primes!
n  When you visit a secure web site (https:… address,
indicated by padlock icon in IE, key icon in
Netscape), the browser and web site may be using
a technology called RSA encryption.
n  This public-key cryptography scheme involves
exchanging public keys containing the product pq
of two random large primes p and q (a private key)
which must be kept secret by a given party.
n  So, the security of your day-to-day web
transactions depends critically on the fact that all
known factoring algorithms are intractable!
ICS 141: Discrete Mathematics I – Fall 2011 13-16
 University of Hawaii

Public Key Cryptography

n  In private key cryptosystems, the same secret “key” string is used to both
encode and decode messages.
n  This raises the problem of how to securely communicate the key strings.

n  In public key cryptosystems, there are two complementary keys instead.
n  One key decrypts the messages that the other one encrypts.

n  This means that one key (the public key) can be made public, while the other
(the private key) can be kept secret from everyone.
n  Messages to the owner can be encrypted by anyone using the public

key, but can only be decrypted by the owner using the private key.
n  Like having a private lock-box with a slot for messages.

n  Or, the owner can encrypt a message with their private key, and then
anyone can decrypt it, and know that only the owner could have
encrypted it.
n  This is the basis of digital signature systems.

n  The most famous public-key cryptosystem is RSA.

n  It is based entirely on number theory!

ICS 141: Discrete Mathematics I – Fall 2011 13-17

 Rivest-Shamir-Adleman (RSA)
University of Hawaii

n  Choose a pair p, q of large random prime

numbers with about the same number of bits
n  Let n = pq
n  Choose exponent e that is relatively prime to
(p−1)(q−1) and 1 < e <(p−1)(q−1)
n  Compute d, the inverse of e modulo (p−1)(q−1).

n  The public key consists of: n, and e.

n  The private key consists of: n, and d.

ICS 141: Discrete Mathematics I – Fall 2011 13-18

 RSA Encryption
University of Hawaii

n  To encrypt a message encoded as an integer:

n  Translate each letter into an integer and group them

to form larger integers, each representing a block of

letters. Each block is encrypted using the mapping
C = Me mod n.
n  Example: RSA encryption of the message STOP
with p = 43, q = 59, and e = 13
n  n = 43 x 59 = 2537

n  gcd(e, (p–1)(q–1)) = gcd(13, 42·58) = 1

n  STOP -> 1819 1415

n  1819
13 mod 2537 = 2081; 141513 mod 2537 = 2182

n  Encrypted message: 2081 2182

ICS 141: Discrete Mathematics I – Fall 2011 13-19

 RSA Decryption
University of Hawaii

n  To decrypt the encoded message C,

n  Compute M = C mod n
d

n  Recall that d is an inverse of e modulo (p−1)(q−1).

n  Example: RSA decryption of the message 0981 0461

encrypted with p = 43, q = 59, and e = 13
n  n = 43 x 59 = 2537; d = 937

n  0981
937 mod 2537 = 0704

n  0461
937 mod 2537 = 1115

n  Decrypted message: 0704 1115

n  Translation back to English letters: HELP

ICS 141: Discrete Mathematics I – Fall 2011 13-20

 Why RSA Works
University of Hawaii

Theorem (Correctness of RSA): (Me)d ≡ M (mod n). Proof:

n  By the definition of d, we know that de ≡ 1 [mod (p−1)(q−1)].

n  Thus by the definition of modular congruence,

∃k: de = 1 + k(p−1)(q−1).
n  So, the result of decryption is
Cd ≡ (Me)d = Mde = M1+k(p−1)(q−1) (mod n)
n  Assuming that M is not divisible by either p or q,
n  Which is nearly always the case when p and q are very large,

n  Fermat’s Little Theorem tells us that M

p−1≡1 (mod p)
and Mq−1≡1 (mod q)
n  Thus, we have that the following two congruences hold:

n  First: Cd ≡ M·(Mp−1)k(q−1) ≡ M·1k(q−1) ≡ M (mod p)

n  Second: C ≡ M·(M
d q−1)k(p−1) ≡ M·1k(p−1) ≡ M (mod q)

n  And since gcd(p,q)=1, we can use the Chinese Remainder

Theorem to show that therefore Cd≡M (mod pq):
n  If C ≡M (mod pq) then ∃s: C =spq+M, so C ≡M (mod p) and
d d d
(mod q). Thus M is a solution to these two congruences, so
(by CRT) it’s the only solution.■
ICS 141: Discrete Mathematics I – Fall 2011 13-21
 Uniqueness of Prime
Factorizations
University of Hawaii

The “hard” part of proving the Fundamental Theorem of Arithmetic.

“The prime factorization of any positive integer n is unique.”
Proof: Suppose that the positive integer n can be written as
the product of two different ways, i.e. n = p1…ps = q1…qt
are equal products of two nondecreasing sequences of
primes.
Assume (without loss of generality) that all primes in
common have already been divided out, so that ∀ij: pi ≠
qj. But since p1…ps = q1…qt, we have that p1|q1…qt, since
p1·(p2…ps) = q1…qt. Then applying lemma 2, ∃j: p1|qj.
Since qj is prime, it has no divisors other than itself and 1,
so it must be that pi=qj. This contradicts the assumption
∀ij: pi ≠ qj.
Consequently, the two lists must have been identical to
begin with! ■
ICS 141: Discrete Mathematics I – Fall 2011 13-22
 Chinese Remainder Theorem
University of Hawaii

n  Theorem: (Chinese remainder theorem.)

Let m1,…,mn > 0 be pairwise relatively prime
and ai ,…,an arbitrary integers.
Then the equations system x ≡ ai (mod mi) (for i=1,..,n)
has a unique solution modulo m = m1 m2···mn.
Proof:
n  Let Mi = m/mi. (Thus gcd(mi, Mi)=1.)
n  So by Theorem 3, ∃yi=Mi such that yiMi≡1 (mod mi).
n  Now let x = ∑i aiyiMi = a1y1M1 + a2y2M2 +···+ anynMn.
n  Since mi|Mk for k≠i, Mk≡0 (mod mi), so
x≡aiyiMi≡ai (mod mi). Thus, the congruences hold.
(Uniqueness is an exercise.) □
ICS 141: Discrete Mathematics I – Fall 2011 13-23
 Computer Arithmetic with
Large Integers
University of Hawaii

n  By Chinese Remainder Theorem, an integer a where

0≤a<m=∏mi, gcd(mi,mj≠i)=1, can be represented by
a’s residues mod mi:
(a mod m1, a mod m2, …, a mod mn)
n  To perform arithmetic with large integers represented in
this way,
n  Simply perform operations on the separate residues!

n  Each of these might be done in a single machine

operation.
n  The operations may be easily parallelized on a

vector machine.
n  Works so long as m > the desired result.

ICS 141: Discrete Mathematics I – Fall 2011 13-24

 Computer Arithmetic Example
University of Hawaii

n  For example, the following numbers are relatively prime:

m1 = 225−1 = 33,554,431 = 31 · 601 · 1,801
m2 = 227−1 = 134,217,727 = 7 · 73 · 262,657
m3 = 228−1 = 268,435,455 = 3 · 5 · 29 · 43 · 113 · 127
m4 = 229−1 = 536,870,911 = 233 · 1,103 · 2,089
m5 = 231−1 = 2,147,483,647 (prime)
n  Thus, we can uniquely represent all numbers up to
m = ∏mi ≈ 1.4×1042 ≈ 2139.5 by their residues ri modulo these five mi.
n  E.g., 10
30 = (r = 20,900,945; r2 = 18,304,504; r3 = 65,829,085;
1
r4 = 516,865,185; r5 = 1,234,980,730)
n  To add two such numbers in this representation,
n  Just add the residues using machine-native 32-bit integers.

n  Take the result mod 2 −1:

k

n  If result is ≥ the appropriate 2 −1 value, subtract out 2 −1

k k

n  or just take the low k bits and add 1.

n  Note: No carries are needed between the different pieces!

ICS 141: Discrete Mathematics I – Fall 2011 13-25

 Pseudoprimes
University of Hawaii

n  Ancient Chinese mathematicians noticed that whenever

n is prime, 2n−1≡1 (mod n).
n  Some also claimed that the converse was true.
n  However, it turns out that the converse is not true!
n  If 2n−1≡1 (mod n), it doesn’t follow that n is prime.
n  For example, 341=11·31, but 2340≡1 (mod 341).
n  Composites n with this property are called
pseudoprimes.
n  More generally, if bn−1≡1 (mod n) and n is composite,
then n is called a pseudoprime to the base b.

ICS 141: Discrete Mathematics I – Fall 2011 13-26

 Carmichael Numbers
University of Hawaii

n  These are sort of the “ultimate pseudoprimes.”

n  A Carmichael number is a composite n such that
bn−1≡1 (mod n) for all b relatively prime to n.
n  The smallest few are 561, 1105, 1729, 2465,
2821, 6601, 8911, 10585, 15841, 29341.
n  Well, so what? Who cares?
n  Exercise for the student: Do some research
and find me a useful & interesting application
of Carmichael numbers.

ICS 141: Discrete Mathematics I – Fall 2011 13-27

 Fermat’s Little Theorem
University of Hawaii

n  Fermat generalized the ancient observation that

2p−1≡1 (mod p) for primes p to the following more
general theorem:
n  Theorem: (Fermat’s Little Theorem.)
n  If p is prime and a is an integer not divisible by p,
then ap−1≡1 (mod p).
n  Furthermore, for every integer a we have
ap ≡ a (mod p).
n  Example (Exponentiation MOD a Prime)
n  Find 2
301 mod 5: By FLT, 24 ≡ 1 (mod 5). Hence,

2300 = (24)75 ≡ 1 (mod 5).

Therefore, 2301=(2300)·2 ≡ 1·2 (mod 5)≡2 (mod 5)
ICS 141: Discrete Mathematics I – Fall 2011 13-28