Reminder: Test 1 (Module 1) is in class on Wednesday, September 16th.

Relevant Textbook Sections:

2.10.3 (Index Calculus), 2.10.4 (Runtime), and for review, 2.10.1 (The Baby-Step Giant-Step Algorithm) and 2.12 (ElGamal Encryption)

To Do:

1. Reminder: the first test is in class on Wednesday, September 16th, 2026 (Module 1). See the Tests page for the syllabus and review problems.
2. Solutions to the last daily post (the parity of the discrete log, baby-step giant-step for $51 = 2^x \pmod{83}$, the tower $2^{(3^{2026})} \pmod{33}$, and the runtime analysis) are now posted: Solutions to Daily Due Sep 11. All daily post solutions are collected on the Archive page.
3. To Know: If you’re interested in the runtime of the Index Calculus, I have more detail in the textbook (Section 2.10.4). Additionally, here are some course notes that cover it in more detail (from Andrew Sutherland’s MIT course on elliptic curves). This may be an interesting topic for a graduate student project: runtime for index calculus and/or index calculus improvements mod $p$ and/or in other finite fields.
4. Solve the discrete logarithm problem for $p=131$, $g=2$, $h=17$, using the Index Calculus method. You may use the Index Calculus Tools and Sage’s modular arithmetic and plain arithmetic computations to avoid by-hand computations, but please solve the linear system by hand (i.e. choosing which equations to subtract from which etc.). Note: this is a randomized algorithm, so you will get different relations than someone else, or next time you run the tool. If you are not finding a very nice linear system, just try to get some more relations and pick simple manageable ones.
5. An awkward linear system. Keep $p = 131$ and $g = 2$, and write $L(a)$ for the discrete log of $a$ base $2$ (so $L(a)$ is only defined modulo $p - 1 = 130$). One relation the tool can hand you is $2^{14} \equiv 9 = 3^2 \pmod{131}$, which says $14 \equiv 2L(3) \pmod{130}$.
   1. Suppose you “divide by two” to conclude $L(3) = 7$. Check this by computing $2^7 \pmod{131}$. Is it $3$?
   2. Explain what went wrong. How many solutions $y$ does $2y \equiv 14 \pmod{130}$ have, and what are they? Which one is $L(3)$?
   3. Find the parity of $L(3)$ using the test from the last daily post (raise $3$ to the $65$th power modulo $131$). Explain how this picks out the right solution in part (2) without any further checking.
   4. Here are three more relations: $2^{8} \equiv 5^3$, $2^{12} \equiv 5 \cdot 7$, and $2^{38} \equiv 3 \cdot 7 \pmod{131}$. Use them to find $L(5)$, $L(7)$ and $L(3)$ without ever dividing by an even number (you will need an inverse modulo $130$), and check that your $L(3)$ agrees with part (3).
   5. In general, which integers are safe to divide by (i.e. multiply by an inverse) when solving relations modulo $p-1$?
6. Runtime comparison. The (heuristic) runtime of the Index Calculus modulo $p$, with a well-chosen factor base, is about $e^{\sqrt{\ln p \cdot \ln \ln p}}$ operations (Section 2.10.4), while Baby-Step Giant-Step takes about $\sqrt{p}$ operations.
   1. Compute both quantities (to two significant figures, in scientific notation) for a $20$-digit prime, a $40$-digit prime, and a $100$-digit prime.
   2. Suppose $10^{20}$ operations is the most an attacker can afford. About how many digits must $p$ have to be safe against Baby-Step Giant-Step? Against the Index Calculus? (Treat the two formulas as exact; the real constants are different, but the moral is the same.)
   3. Explain in a sentence why the Index Calculus is called subexponential: compare $e^{\sqrt{\ln p \cdot \ln \ln p}}$ with $p^{\varepsilon} = e^{\varepsilon \ln p}$ for a fixed $\varepsilon > 0$ as $p \to \infty$.
7. Remember to upload to canvas!

Added Sept 25: solutions to this daily post (the Index Calculus for $2^x \equiv 17 \pmod{131}$, the awkward linear system, and the runtime comparison) are now posted: Solutions to Daily Due Sep 14.