L5 (Extended Euclid and Mod Division)

Question 1

How do we verify that a number ‘d’ is the GCD of ‘a’ and ‘b’?

Answer 1

We use the following property:

if d divides both a and b (with no remainder), and
d = ax + by

for some integers x and y, then

d = GCD(a, b)

note: x or y can be negative

Question 2

Write out the Extended Euclid algorithm.

Input should be two integers a and b

Output should be (x,y,d) such that:
d = GCD(a, b)
and
d = ax + by

Answer 2

Base case is b = 0
Recurse on Extended-Euclid of b and a mod b

Question 3

What is the condition for the extended-euclid algorithm to be correct?

Answer 3

For any positive integers a, and b, the extended-euclid algorithm is correct

Question 4

What are the 3 steps in mathematical induction?

We want to show that a statement S(k) holds for all integers k >= 0

Answer 4

Step 1 (base case): Show that S(0) holds

Step 2: Assume that S(k’) holds

Step 3 (inductive step):
Show that if S(k’) holds, then S(k’+1) must also hold

By going this, the S(k) statement must hold by induction

Question 5

Define what it means for an integer x to be multiplicative inverse of a modulo N?

Answer 5

x is the multiplicative inverse of a modulo N if:

a*x ≡ 1 (mod N)

Question 6

Integer a has a multiplicative inverse modulo N

What does this imply?

Answer 6

This implies that the greatest common denominator of a and N is 1:

GCD(N, a) = 1

Question 7

What does it mean for two numbers for be co-prime?

Answer 7

Two numbers are co-prime (or relatively prime) if their greatest common divisor is 1

gcd(a, b) = 1

They do not have any common factors other than 1

Question 8

What is the exponential property of modular exponentiation?

Answer 8

(a^b) mod N = (a mod N)^b

Question 9

What is the modular division theorem?

Answer 9

For any integer a in {0, 1, … N-1}, or (a < N). a has a multiplicative inverse mod N if an only if GCD(N, a) =1

Question 10

If a multiplicative inverse exists for N and a, how would it be found?

How long would it take?

Answer 10

To find the inverse, run the extended-euclid algorithm on N and a:

(x, y, d) = extended-euclid(N, a)

and then y mod N would be the multiplicative inverse of a and N

it would take O(n^3) time where n is the number of bits in a