**Lecture Outline**

• **What we’ve covered so far:**

– symmetric encryption

– hash functions

• **Where we are heading:**

– number theory

– public-key encryption

– digital signatures

**• Introduction to number theory**

– divisibility

– GCD and Euclidean algorithm

– prime and composite numbers

– Chinese remainder theorem

– Euler Ø function

– Fermat’s theorem

**Divisibility**

**• Divisibility**

– given integers a and b, we say that b divides a (denoted by b|a) if b/a

is a whole number (or b = ac for an integer c)

– b is called a divisor of a

**• Transitivity theorem**

– we are given integers a, b, and c, where all of them > 1

– if a|b and b|c, then a|c

– proof

**• Linear combination theorem**

– let a, b, c, x, and y be integers > 1

– if a|b and a|c, then a|(bx+cy)

**• Proof**

– a|b=>

– a|c =>

–

–

**• Division algorithm (theorem)**

– let a > 0 and b be two integers

– then there exist two **unique** integers q and r such that 0 ≤ r < a and

b = aq +r

–** to show existence:**

– **uniqueness can be shown by contradiction:**

• as sume there are integers q' and r' such that b = aq' +r' and

0 ≤ r' < a

**• Notation**

– the integer q is called the **quotient**

– the integer r is called the **remainder**

– [x] is the** floor** of x (largest integer ≤ x)

– [x] is the** ceiling **of x (smallest integer ≥ x)

– then q = [b/a] and r = b mod a

** Greatest Greatest Divisor**

**• Greatest common divisor (GCD)**

– suppose we are given integers a and b which are not both 0

– their greatest common divisor gcd(a, b) = c is the greatest number

that divides both a and b

– example: gcd(128, 100) = 4

– it is clear that gcd(a, b) = gcd(b, a)

**• GCD and multiplication **

– we are given integers a, b, and m > 1

– if gcd(a,m) = gcd(b,m) = 1, then gcd(ab,m) = 1

– example: gcd(25, 7) = gcd(3, 7) = 1 => gcd(75, 7) = 1

**• GCD and division**

**– Theorem 1**

• we are given integers a and b

• if g = gcd(a, b), then

• example:

**– Theorem 2**

• if a is a positive integer and b, q, and r are integers with

b = aq +r, then gcd(b, a) = gcd(a, r)

• we can use this theorem to find GCD

**Euclidean Algorithm**

• Fact: given integers a > 0, b, q, and r such that b = aq
+r,

gcd(a, b) = gcd(a, r)

**• Euclidean algorithm for finding gcd(a, b)**

– apply the division algorithm iteratively to compute the remainder

– the last non- zero remainder is the answer

– while a ≠ 0 do

r b mod a

b a

a r

return b

**• Example:**

– compute GCD of 165 and 285

– steps of Euclidean algorithm:

– the answer is gcd(165, 285) =

**Towards Extended Towards Extended Euclidean Algorithm**

**• Theorem:**

– if integers a and b are not both 0, then there are integers x and y so

that ax +by = gcd(a, b)

– we can find x and y using the extended Euclidean algorithm

**• Example:**

– find x and y such that 285x +165y = gcd(285, 165) = 15

– we start with the next to last equation in our example and work

backwards