My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are all integers, and solving for $x_i$. The algorithm I am using is based off of the following journal article:
http://www.jstor.org/stable/3620787 .
The algorithm I derived from the article is roughly as follow:
- Find a minimum coefficient (there could be many, just pick the any of them).
- Take every coefficient that is not the one you picked in the modulus of coefficient you picked.
Check if any coefficients are 1, if so, go to 5.
Go to 1.
Back-substitute to find solution.
Currently, I have an incomplete argument that the algorithm is indeed polynomial time. My argument is as follows:
Suppose we choose the $a_j$ that such that it minimizes the number of bits all of the coefficients are reduced by, thereby maximizing the number of iterations. Then, after we compute ${a^{'}_{{i} \neq {j}} = a_{{i} \neq {j}}} \mod {a_j}$ we know that $a^{'}_{{i} \neq {j}} < {{a_{{i} \neq {j}}} \over {2}}$, because if it were not, then $a_j$ could go into $a_{{i} \neq {j}}$ another time. On the next iteration, the previous minimum $a_j$ cannot be the new minimum, since every other coefficient is less. Thus, the previous minimum will necessarily be reduced by one bit. Hence, all of the coefficients are reduced by at least 1 bit every 2 iterations. Thus, the maximum number of iterations is twice the maximum number of bits for a coefficient $2\log_2(\max {a_i})$, the back-substitution takes exactly the same number of steps, thus I estimate the algorithm is $O(\log(\max {a_i}))$, which is polynomial time with respect to the number of bits in the coefficient representation.
Am I missing something or is this correct? Please let me know if there is anything I need to clarify.