Math 480, Spring 2015, Assignment 8

Carefully define the following terms:

1. Euler totient function.

Carefully state the following theorems (you do not need to prove them):

1. Euler's generalization of Fermat's little theorem.
2. Theorem concerning the invertibility of the power map $x\mapsto x^e$ on $\mathbb{Z}_n$, when $e$ is prime to $\phi(n)$.

Carefully describe the following algorithms:

1. Pohlig-Hellman algorithm (this is actually a method that potentially accelerates other discrete log algorithms; just state an algorithm that reduces a discrete log problem to several smaller discrete log problems).
2. Method to compute the Euler totient $\phi(n)$ once the prime factorization of $n$ is known.

Solve the following problems:

1. Problems 2.28(a) and 3.5.

Coding projects:

1. (Pohlig-Hellman) Implement the Pohlig-Hellman discrete log algorithm. Note that this will need to call at least two external routines: one to factor the modulus, and another to compute the resulting (smaller) discrete logarithms. For now you have no efficient factorization methods, so you may either implement an inefficient one or rely on an efficient one that you obtain from a third party. Try to make your code sufficiently modular that you can easily swap in your own efficient factorization algorithm once you have written it. For the small discrete log problems, call your babystep-giantstep implementation, but again, try to make the code modular so you can easily swap in other methods as they become available.
2. (Euler totient) Make a function that takes a positive integer $n$ as input and returns the Euler totient $\phi(n)$. As above, you will need to call an external factorization routine; try to plan ahead so it will be easy to swap in your own routine when it becomes available.

--------------------End of assignment--------------------