Lab 13 : Modular Exponentiation

In this lab, we will implement modular exponentiation and experiment with the difficulty of finding roots modulo n.

0 Preliminaries

To run doctests, add the following to the bottom of your file:

if (__name__ == '__main__'):
  import doctest
  doctest.testmod(optionflags= doctest.NORMALIZE_WHITESPACE)

1 Slow exponentiation

Exercise 1 Write a function which computes exponentiation by repeated multiplication.

def slow_exp(x, e):
    """
    Assume e is a non-negative integer.

    >>> slow_exp(2, 10)
    1024

    """

Exercise 2 Run your function from Exercise 2 on inputs which take many seconds to a minute to compute. When you do this, assign the output to a variable (i.e. >>> out = slow_exp(..., ...), so that the slowness will not simply be due to printing a large number in the interaction buffer. (Include these tests as comments in your file for your instructor to see.)

2 Binary representation

Exercise 3 Write a function which takes a non-negative number and returns a string of 0s and 1s which represent that number in binary. Do not use bin or the like.

def bin_rep(n):
    """
    Assume that n is a non-negative integer.

    >>> bin_rep(12345)
    '11000000111001'

    """

3 Square and multiply

We can significantly reduce the number of steps computing exponentiation by using repeated squaring as opposed to repeated multiplication. The key insight is that if the exponent e is even then \(x^e = (x^2)^{\frac{e}{2}}\); and if the exponent e is odd then \(x^e = x(x^2)^{\frac{e-1}{2}}\).

If we further convert the exponent to binary, we can exponentiate using the following algorithm:

1. Initialize result = 1.
2. If there are no remaining bits in the exponent, return result.
3. Read the next bit b of the exponent (left-to-right).
4. If b is 1, result = x * result * result.
5. If b is 0, result = result * result.
6. Goto 2.

Exercise 4 Write a function which computes exponentiation by the square and multiply algorithm.

def sqr_and_mult(x, e):
    """
    Assume e is a non-negative integer.

    >>> sqr_and_mult(10, 3)
    1000
    >>> sqr_and_mult(2, 10)
    1024
    >>> sqr_and_mult(2, 12)
    4096

    """

4 Modular square and multiply

Exercise 5 Write a function which computes modular exponentiation by the modular square and multiply algorithm.

def sqr_and_mult_mod(x, e, n):
    """
    Assume e is a non-negative integer.

    >>> sqr_and_mult_mod(2, 5, 64)
    32
    >>> sqr_and_mult_mod(2, 6, 64)
    0

    """

5 Brute force modular root finding

Exercise 6 Write a function which given a number c, a modulus n and an exponent e, tries to find m such that \(m^e \equiv c \pmod{n}\).

def slow_root_mod(e, c, n):
    """
    >>> slow_root_mod(5, 32, 119)
    2
    >>> slow_root_mod(4, 81, 77)
    3

    """

Exercise 7 Run your function from Exercise 6 on inputs which take many seconds to minutes to compute. For added realism, try taking n to be the product of two primes, and choose e so that it’s somewhat less than n. (Include these tests as comments in your file for your instructor to see.)