Applying the idea of Dixon's method to discrete logs 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$.
 A: The way to get the discrete log of $r$ from a matrix like $A$ turns out to be straightforward.  (I used SymPy to do the calculations here as well as the determinant in the question itself).
Step 1: Form a matrix from columns 3 through 8 of $A$.  These are the columns we want to have $0$s when we do row operations on $A$ to get an expression for $1$ involving only $r$ and 2.
$$B = \begin{bmatrix}
 -1 &  1 & -3 &  0 &  0 &  0 \\
 -2 &  1 &  0 & -1 &  1 &  0 \\
  1 & -1 &  0 &  0 &  1 & -1 \\
 -1 &  0 &  0 &  2 &  0 &  0 \\
  5 &  0 & -1 &  0 & -1 & -1 \\
  0 &  3 &  0 & -1 & -1 & -1 \\
  2 &  0 & -1 & -1 & -1 &  1 \\
 -2 & -2 &  2 &  0 & -1 &  1 \\
\end{bmatrix}$$
Step 2: Take the null space of $B$ and pick an arbitrary member of it:
$$K = \begin{bmatrix}
-1/8 & -1/4 & 9/8 & 5/8 & -5/8 & 1/2 & 1 & 0
\end{bmatrix}$$
Step 3: $KA$ gives the discrete log of $r$, once you clear denominators.
$$KA = \begin{bmatrix}
9/4 & 3/8 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}$$
Sure enough, $1277^{18} 2^3\equiv1$ mod $4327$.
Notes:


*

*Though it was new to me, the idea behind my question probably goes back to at least 1992.  The paper linked below, from 1992, talks about using the number field sieve to solve the discrete log problem.  The number field sieves is a way of getting expressions like the ones in matrix $A$.  Link:  https://pdfs.semanticscholar.org/1020/f10f733cba8562db77fcceef47145118b8bc.pdf

*$p = 4327$ was a flawed example because I did not verify that $2$ is a primitive root of $4327$.  A possible consequence of this oversight is that the final equation $1277^{18}2^3\equiv1$ mod $4327$ involves only multiples of $3$: $18$, $3$ and $p-1=4326$.  Because of this common factor, it is not possible to solve $2^x\equiv1277$ mod $p$ from my final equation.  Once this is fixed, the technique suggested in the question might still fail due to divisors like 3 of $p-1$.  But it looks like it won't fail for the reason the original question asks about.  So this answer stands, as far as I'm concerned.
