Reminder! We have a course textbook on Overleaf with examples of the algorithms we cover. The table of contents should help you find anything, and I have been adding in solutions to some daily post problems there.
Here are solutions to the last daily post (link to appear shortly).
Reminder! You should be filling out your own daily post tracking sheet. Please attach a copy of that to the daily post submission today so we can take stock.
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.
Suppose I write the standard trial division algorithm for factoring an integer $n$. That is, I loop through all integers $k$ less than $n$, and try dividing $n$ by $k$ to see if it divides evenly. What is the runtime of this algorithm? As a function of the size of the input to the algorithm (the input is the number $n$ written in binary notation), is this an exponential or polynomial algorithm, or something in between?
Explain why for trial division, to factor $n$, you actually only need to loop through integers $k$ less than or equal to the square root of $n$. How does this change your runtime analysis?
Consider the discrete log problem $h = g^a$ modulo $p$. Suppose you make two lists: $g^x$ for random $x$ and $hg^{-y}$ for random $y$.
Explain how, if you get a collision, it results in a solution to the discrete log problem. This algorithm is called the “Birthday attack” on discrete log.
The Baby-Step-Giant-Step algorithm is a sort of “organized” birthday algorithm. Explain why I say this.
How long should you make these lists to expect a decent probability of a collision?
With reference to the last part, what is the runtime of the birthday attack on discrete log?
If you are so inclined, try to break one of the ciphertexts on discord from our Diffie-Hellman Key Exchange.