5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Thanks for you answer! When I solve the matrix of the relations using some online tool, it gives me the exact same set of solutions as I calculate. So does WolframAlpha. The fact that I'm not ending up with any fraction after we row-reduced the matrix makes me think something else must be going wrong. $\endgroup$ – Tomirio Nov 26 '16 at 19:26
  • $\begingroup$ This online tool solves your system of equations over the complex numbers. This is not what you want. You want to have solutions in $\mathbb{Z}/2002\mathbb{Z}$. $\endgroup$ – CurveEnthusiast Nov 26 '16 at 19:37
  • $\begingroup$ I do perform the the Gaussian Elimination $\mod(2002)$. I only perform the $\mod(2002)$ when the Gaussian Elimination is done. You say that "dividing with any number which has $\gcd$ non-zero with 2002 is off-limits''. You can actually divide if the $\gcd$ of the number and 2002 equals 1, which means that the number has an inverse $\mod(2002)$ $\endgroup$ – Tomirio Nov 26 '16 at 19:38
  • $\begingroup$ Consider for example the relation $\left(-5\right)^2=5^2$. If we follow your method, we obtain the matrix $M=\begin{pmatrix} 2 & 2\end{pmatrix}$. The tool will simplify this to the matrix $M=\begin{pmatrix} 1 & 1\end{pmatrix}$. But then the conclusion is that $-5=5$, which is incorrect. $\endgroup$ – CurveEnthusiast Nov 26 '16 at 19:40
  • $\begingroup$ Hmm, you're right. So at every indeterminate step, you will need to perform the $\mod(2002)$? $\endgroup$ – Tomirio Nov 26 '16 at 19:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm not sure if I understand your point. All your statements are correct, but how do they help to solve the problem? Could you clarify how to apply the CRT here? $\endgroup$ – CurveEnthusiast Nov 27 '16 at 20:35
  • $\begingroup$ @CurveEnthusiast The question was why something went wrong. It was my intention to keep some space for actual homework. $\endgroup$ – Vadym Fedyukovych Nov 27 '16 at 20:40
  • $\begingroup$ Let me repeat it: equation with powers of 2 and 11 should be considered modulo 286. Please note corresponding power of 5 can be divided by 7: $104 = \frac{728}{7}$. $\endgroup$ – Vadym Fedyukovych Nov 27 '16 at 20:52
  • $\begingroup$ I'm not trying to give the homework away here! Honestly just trying to understand (maybe should be doing my own homework better..). We have $5^{728}\not\equiv 2^5\cdot11\bmod{286}$. And if we divide the exponent of 5 by 7, what happens to the exponents of 2 and 11? $\endgroup$ – CurveEnthusiast Nov 27 '16 at 21:02
  • $\begingroup$ Both 2 and 11 are generators of a multiplicative subgroup modulo 2003. Subgroup of order $\frac{2002}{7}$. $\endgroup$ – Vadym Fedyukovych Nov 27 '16 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.