Incorrect solution for Discrete Log Problem when using the Index Calculus algorithm

Question

The index calculus algorithm can be used for computing discrete logarithms. The basic idea is that you search for a set of linear independent vectors. When you solve the corresponding matrix, you find the solutions for the discrete log problem of all the prime factors in your factor base. These can be used to solve the original discrete log problem.

I decided to make an implementation of it just for fun. However, when solving the corresponding matrix, I sometimes run into solutions for the factors that are incorrect. Let me show an example. Assume we have generator $g = 5$ and $h=543$ with $p = 2003$. Using the factor base $\mathcal{F} = \{2,3,5,7,11,13\}$, we want to find a solution for $$g^x \equiv h \mod(p)$$

Lets say we find the following relations which are $\mathcal{F}$-smooth: \begin{align*} 5^{790} &= 3^2 \cdot 11^2 \\ 5^{729} &= 2^5 \cdot 5 \cdot 11 \\ 5^{1162} &= 3^3 \cdot 5 \cdot 7 \\ 5^{919} &= 2^2 \cdot 5 \cdot 7^2 \\ 5^{150} &= 2 \cdot 3^2 \cdot 7 \\ 5^{953} &= 2 \cdot 5 \cdot 7 \cdot 13 \end{align*}

This leaves us with the following matrix: $M = $ \begin{pmatrix} 0 & 2 & 0 & 0 & 2 & 0 & 790\\ 5 & 0 & 1 & 0 & 1 & 0 & 729\\ 0 & 3 & 1 & 1 & 0 & 0 & 1162\\ 2 & 0 & 1 & 2 & 0 & 0 & 919\\ 1 & 2 & 0 & 1 & 0 & 0 & 150\\ 1 & 0 & 1 & 1 & 0 & 1 & 953 \end{pmatrix}

Using Gauss-Jordan Eliminiation, we get the following solutions: \begin{align} \log_5(2) &= -93 \equiv 1909 \mod(2002)\\ \log_5(3) &= 60 \\ \log_5(5) &= 859 \\ \log_5(7) &= 123 \\ \log_5(11) &= 335 \\ \log_5(13) &= 64 \end{align} We can check the only the $\log_5(7)$ is correct. My question is: how is it possible that the solutions for the factors in the factor base are (mostly) incorrect, although the relations we found are linear independent?

Answer 1

Did it a quick sanity check, and indeed your relations hold in $\mathbb{F}_p$. I cannot judge where you went wrong of course, but my guess is that you are dividing at points where you can't. The Gaussian elimination is done $\bmod{2002}$, hence dividing with any positive integer which has $\gcd$ unequal to 1 with 2002 is off-limits. Below I show how you can get some solutions from your system of equations.

Note that you can trivially cancel out 5's on the right side of your equation, to get the system of equations \begin{align*} 5^{790} &= 3^2\cdot11^2\\ 5^{728} &= 2^5\cdot 11\\ 5^{1161} &= 3^3\cdot7\\ 5^{918} &= 2^2\cdot 7^2\\ 5^{150} &= 2\cdot 3^2\cdot7\\ 5^{952} &= 2\cdot7\cdot13\\ \end{align*} This does not affect the solutions of course. Instead we get the matrix $$\begin{pmatrix} 0 & 2 & 0 & 2 & 0 & 790\\ 5 & 0 & 0 & 1 & 0 & 728\\ 0 & 3 & 1 & 0 & 0 & 1161\\ 2 & 0 & 2 & 0 & 0 & 918\\ 1 & 2 & 1 & 0 & 0 & 150\\ 1 & 0 & 1 & 0 & 1 & 952 \end{pmatrix}$$ Using Gaussian elimination (for the full computation check below) we obtain the relations \begin{align*} 2^{20} &= 5^{714} \\ 3^4 &= 5^{1384} \\ 3^{60} &= 5^{740} \\ 7^{20} &= 5^{458} \\ 11^4 &= 5^{196} \\ 13^2 &= 5^{986} \end{align*} Of course $3^4=5^{1384}\implies3^{60}=5^{740}$, hence we get solutions \begin{align*} 2^{20} &= 5^{714} \\ 3^4 &= 5^{1384} \\ 7^{20} &= 5^{458} \\ 11^4 &= 5^{196} \\ 13^2 &= 5^{986} \end{align*} Now note that $801\equiv5^{-1}\bmod{2002}$, hence $$2^{20} = 5^{714}\implies (2^{20})^{801} = (5^{714})^{801}\implies 2^4=5^{1344}.$$ Similarly $7^4=5^{492}$, and we have \begin{align*} 2^4 &= 5^{1344} \\ 3^4 &= 5^{1384} \\ 7^4 &= 5^{492} \\ 11^4 &= 5^{196} \\ 13^2 &= 5^{968} \end{align*} Now we get into some trouble, since $\gcd(2,2002)=2$, hence we cannot simply eliminate 2. However we can conclude that $\pm 13\equiv5^{493}\bmod{p}$. Simply trying both gives that $\log_5(-13)=493$. Moreover $\mathbb{F}_p^*$ is cyclic of order 2002, and since 2002 is not divisible by 4, it does not contain any element of order 4. So the only elements $x\in\mathbb{F}_p^*$ that satisfy $x^4=1$ are $\pm1$. Hence \begin{align*} \pm2 &= 5^{336} \\ \pm3 &= 5^{346} \\ \pm7 &= 5^{123} \\ \pm11 &= 5^{49} \\ -13 &= 5^{493} \end{align*} Simply trying the two options leads to the solutions \begin{align*} -2 &= 5^{336} \\ 3 &= 5^{346} \\ 7 &= 5^{123} \\ 11 &= 5^{49} \\ -13 &= 5^{493} \end{align*}

Gaussian elimination:

Multiply the bottom row by 2 (the 6th row, starting the count at 1), and then subtract the 4th row from the bottom row. This leaves $$\begin{pmatrix} 0 & 2 & 0 & 2 & 0 & 790\\ 5 & 0 & 0 & 1 & 0 & 728\\ 0 & 3 & 1 & 0 & 0 & 1161\\ 2 & 0 & 2 & 0 & 0 & 918\\ 1 & 2 & 1 & 0 & 0 & 150\\ 0 & 0 & 0 & 0 & 2 & 986 \end{pmatrix}$$ Multiplying the 5th column by 2, and subtracting the fourth gives $$\begin{pmatrix} 0 & 2 & 0 & 2 & 0 & 790\\ 5 & 0 & 0 & 1 & 0 & 728\\ 0 & 3 & 1 & 0 & 0 & 1161\\ 2 & 0 & 2 & 0 & 0 & 918\\ 0 & 4 & 0 & 0 & 0 & 1384\\ 0 & 0 & 0 & 0 & 2 & 986 \end{pmatrix}$$ Multiplying the first row by 2 and subtracting the 5th leaves $$\begin{pmatrix} 0 & 0 & 0 & 4 & 0 & 196\\ 5 & 0 & 0 & 1 & 0 & 728\\ 0 & 3 & 1 & 0 & 0 & 1161\\ 2 & 0 & 2 & 0 & 0 & 918\\ 0 & 4 & 0 & 0 & 0 & 1384\\ 0 & 0 & 0 & 0 & 2 & 986 \end{pmatrix}$$ Multiply the second row by 4 and subtract the first to get $$\begin{pmatrix} 0 & 0 & 0 & 4 & 0 & 196\\ 20 & 0 & 0 & 0 & 0 & 714\\ 0 & 3 & 1 & 0 & 0 & 1161\\ 2 & 0 & 2 & 0 & 0 & 918\\ 0 & 4 & 0 & 0 & 0 & 1384\\ 0 & 0 & 0 & 0 & 2 & 986 \end{pmatrix}$$ Multiply the 4th row by 10 and subtract the 2nd to get $$\begin{pmatrix} 0 & 0 & 0 & 4 & 0 & 196\\ 20 & 0 & 0 & 0 & 0 & 714\\ 0 & 3 & 1 & 0 & 0 & 1161\\ 0 & 0 & 20 & 0 & 0 & 458\\ 0 & 4 & 0 & 0 & 0 & 1384\\ 0 & 0 & 0 & 0 & 2 & 986 \end{pmatrix}$$ Finally multiply the 3rd by 20 and subtract the 4th to obtain $$\begin{pmatrix} 0 & 0 & 0 & 4 & 0 & 196\\ 20 & 0 & 0 & 0 & 0 & 714\\ 0 & 60 & 0 & 0 & 0 & 740\\ 0 & 0 & 20 & 0 & 0 & 458\\ 0 & 4 & 0 & 0 & 0 & 1384\\ 0 & 0 & 0 & 0 & 2 & 986 \end{pmatrix}$$

Answer 2

A quick example to let you see the rest in one line: it does not follow from $4 \equiv 1 \pmod{3}$ that $4 \equiv 1 \pmod{6}$.

2003 is prime; $2002 = 2*7*11*13$, which means that multiplicative subgroups of orders 2,7,11,13 are there.

Let's see the order of 5: $5^{2002/2} = 2002 \pmod{2003}$ (that is, not 1); $5^{2002/7} = 874 \pmod{2003}$; $5^{2002/11} = 886 \pmod{2003}$; $5^{2002/13} = 633 \pmod{2003}$. It follows, order of 5 is 2002. Perfect.

Now take a look at the first generator from the "factor base", in particular $2^{2002/7} = 1 \pmod{2003}$. It follows, 2 generates a subgroup of order 286 only, not 2002. That is, first equation in the system should not be considered modulo 2002.

Constructive part of the answer would be to use Chinese Reminder Theorem.