I want to see if a technique like Dixon's method for integer factorization would work for discrete logs. If the base is 2 (which could be generalized), to find the log of $r$, set up equations like the following (in which the first 7 primes are the factor base):
$r^{A_{i1}}2^{A_{i2}}3^{A_{i3}}5^{A_{i4}}7^{A_{i5}}11^{A_{i6}}13^{A_{i7}}17^{A_{i8}}\equiv1$ mod p
Then use row operations on the rows of the matrix $A$ to find a linear combination of these rows with $0$s in every entry other than the first two. This gives an equation of the form $r^x2^y\equiv1$ mod p, from which it's easy to obtain the log of $r$ base $2$.
The question I have is, whether the row operations can be performed so $x$ and $y$ are non-zero mod $p-1$. I don't have much idea how to guarantee this, and there is a strong tendency to get $0$s. For example, I picked $p=4327$ and $r=1277$, and generated a matrix $A$ in which each row satisfies
$1277^{A_{i1}}2^{A_{i2}}3^{A_{i3}}5^{A_{i4}}7^{A_{i5}}11^{A_{i6}}13^{A_{i7}}17^{A_{i8}}\equiv1$ mod 4327
$$A = \begin{bmatrix}
1 & -1 & -1 & 1 & -3 & 0 & 0 & 0 \\
1 & -3 & -2 & 1 & 0 & -1 & 1 & 0 \\
1 & 1 & 1 & -1 & 0 & 0 & 1 & -1 \\
1 & -10 & -1 & 0 & 0 & 2 & 0 & 0 \\
1 & -1 & 5 & 0 & -1 & 0 & -1 & -1 \\
1 & 2 & 0 & 3 & 0 & -1 & -1 & -1 \\
1 & 3 & 2 & 0 & -1 & -1 & -1 & 1 \\
1 & 1 & -2 & -2 & 2 & 0 & -1 & 1 \\
\end{bmatrix}$$
Lo and behold, the determinant of $A$ is $0$ mod $p-1$ (-4326 to be exact). Had this not been the case, an absurd result would have ensued: We could have shown that $1277^x2^y\equiv1$ mod $p$ for any ratio $x/y$ of our choosing, by inverting $A$. So the determinant is bound to be $0$ mod $p-1$.
No comments:
Post a Comment