Solutions to Discrete Log Practice Session

Task 1. Here are the baby steps and giant steps to compute $L_5(11)$ modulo $p=197$.

By observing the above, we can see that the 13th baby step equals the 4th giant step. Thus, $5^{13+15\cdot4}=11$. This implies $L_5(11)=13+15*4=73$. To check this, we can compute

Task 2. We want to use Index Calculus to compute $L_5(10)$ modulo $p=197$. The first goal is simply to produce some examples of powers of $5$ that are smooth. If we look ahead, we see that $10=5 \cdot 2$, hence we can compute $L_5(10) = L_5(2) + L_5(5)$. It is immediate that $L_5(5)=1$. So we need only find enough smooth powers of $5$ to obtain $L_5(2)$.

To compute some smooth powers, there are various methods to employ. Let’s use a small factor base of $2,3,5,7$. Let’s try just factoring some powers of $5$, as a starting point:

Ok, that’s kind of too much information. We can restrict ourselves to factorizations that happen to smooth with a simple trick (this is not a formal part of the algorithm, just a trick). I’ll also increase the loop size:

Ok, now we’re getting somewhere. We can combine, for example, the relations $g^{73}=11$ and $g^{62}=2 \cdot 11$ to discover $2 = g^{62-73} = g^{-11} = g^{196-11} = g^{185}$. In other words, $L_5(2) = 185$. Let’s check:

Finally, we have $L_5(10) = L_5(5) + L_5(2) = 1 + 185 = 186$. Let’s check: