Math 480, Spring 2015, Assignment 6

Carefully describe the following algorithms:

1. Trial and error (algorithm for calculating discrete logs).
2. Babystep-giantstep algorithm.

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

1. Time and memory complexity of the trial-and-error discrete log algorithm.
2. Time and memory complexity of the babystep-giantstep algorithm.

Solve the following problems:

1. Exercise 2.17(a).

Coding projects:

1. Implement the trial-and-error algorithm. What is the largest modulus for which you can successfully compute discrete logs with this algorithm?
2. Implement the babystep-giantstep algorithm. What is the largest modulus for which you can successfully compute discrete logs with this algorithm?

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