Timeline for Incorrect solution for Discrete Log Problem when using the Index Calculus algorithm
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 27, 2016 at 12:11 | vote | accept | Tomirio | ||
| Nov 27, 2016 at 6:39 | history | edited | CurveEnthusiast | CC BY-SA 3.0 |
added 10 characters in body
|
| Nov 27, 2016 at 6:39 | comment | added | CurveEnthusiast | Oh and I see, I indeed made a typo. The "dividing with any number which has gcd non-zero" should of course be gcd not equal to one. | |
| Nov 27, 2016 at 6:31 | history | edited | CurveEnthusiast | CC BY-SA 3.0 |
added 4 characters in body
|
| Nov 26, 2016 at 19:45 | comment | added | CurveEnthusiast | Yes, every step you take is done in the ring $\mathbb{Z}/2002\mathbb{Z}$. So we can add and subtract rows, and multiply a specific rows with any integer. We can only divide a row by integers which are relatively prime to 2002. | |
| Nov 26, 2016 at 19:42 | comment | added | Tomirio | Hmm, you're right. So at every indeterminate step, you will need to perform the $\mod(2002)$? | |
| Nov 26, 2016 at 19:40 | comment | added | CurveEnthusiast | 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. | |
| Nov 26, 2016 at 19:38 | comment | added | Tomirio | 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)$ | |
| Nov 26, 2016 at 19:37 | comment | added | CurveEnthusiast | 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}$. | |
| Nov 26, 2016 at 19:26 | comment | added | Tomirio | 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. | |
| Nov 26, 2016 at 11:35 | history | answered | CurveEnthusiast | CC BY-SA 3.0 |