ANNOUNCEMENT: The first assessment will be a full-period in-class test on Module 2 and portions of Module 1, on Friday September 16th, 2022. As we finish up information I am updating the Goals page with checkmarks. Checkmarks indicate material that will be covered. It will involve demonstrating the ability to reason about material covered, to implement algorithms by hand, and to do small mathematical proofs (some proofs, like that of Euler’s theorem, should be studied so you can reproduce them).

Compare your solutions for daily posts due Sept 2, Sept 7 and Sept 9. Look these over carefully (this is a great learning opportunity!) and ask if you have questions.

Use exhaustive search or any method to compute $L_2(3)$ modulo $13$. You can use Sage’s modular arithmetic functions such as the tables on this page.

It is a fact that $p=101$ is prime, and $2$ is a primitive root modulo $p$. It is a fact that $L_2(3)=69$ and $L_2(5)=24$ modulo $p$. It is also a fact that the integer factorization of $24$ is $24 = 2^3 \cdot 3$. Using these facts, evaluate $L_2(24)$ modulo $p$ with minimal work (just combine the facts above).

We finished class Friday before I could do an example of the Baby-Step-Giant-Step algorithm. Please check the notes (which have an example) or watch this video of the example (3:22), and review the method. I’ve now added it to the latex course notes. Your text also has a discussion (Chapter 7, Section 7.2.2 in 2nd ed).

Use the Baby-Step-Giant-Step algorithm (and show all steps) to solve the discrete logarithm problem $34 = 3^x \pmod{113}$. You may use Sage’s functionality to compute the lists, including the tools on the BabyStepGiantStep page if you want to (ask for help on discord if you need some explanation of the page), so it shouldn’t involve much work by hand. But please present the solutions tidily and in a well-explained and well-labelled way (indicate where each term in each list comes from, not just the value you get), so the algorithm is evident.

Analyse the runtime of the Baby-Step-Giant-Step algorithm. That is, clearly answer the following. This is similar to what we did for modular exponentiation in class (see the notes from class).

What is the input?

What is the size of the input?

What is the runtime?

What is the runtime as a function of the input size?