L4 (Modular Exponentiation and GCD)

Question 1

The modular exponentiation problem is trying to compute the value of x ^ y mod N.

What is the most efficient algorithm for this?
What is the runtime of this algorithm?

Answer 1

Uses properties of modular arithmetic. It branches and recurses on if y is even or odd. Base case is y = 0.

func modexp(x, y, N):
if y == 0: return 1
z = modexp(x, floor(y/2), N)
if y is even: return z^2 mod N
if y is odd: return x*z^2 mod N

runtime is O(n^3)

Question 2

What is the GCD (greatest common divisor) of two numbers?

Answer 2

The GCD (Greatest common divisor) of two numbers is the largest integer that divides both of them

Question 3

What is euclid’s rule for GCD of two numbers?

Answer 3

If a and b are positive integers with a >= b, then

gcd(a, b) = gcd(b, a mod b)

Question 4

Write an algorithm to compute the GCD of two numbers a, and b using euclid’s rule.

Answer 4

func euclid_gcd(a, b):
if b == 0: return a
return euclid_gcd(b, a mod b)