Diophantine Linear System Solving

A simple randomized algorithm is given for finding an integer solution to a system of linear Diophantine equations. Given as input a system which admits an integer solution, the algorithm can be used to find such a solution with probability at least 1/2. The running time (number of bit operations) is essentially cubic in the dimension of the system. The analogous result is presented for linear systems over the ring of polynomials with coefficients from a field. 1 Introduction Solving a system of linear Diophantine equations is a classical mathematical problem: given an integer matrix A and vector b, the goal is to find an integer vector x that satisfies Ax = b. We present a simple randomized algorithm for solving this problem. We also show how to adapt the algorithm to solve linear systems over the ring of univariate polynomials with coefficients from a field. The algorithm is easy to implement, memory efficient, and faster than previous methods. The algorithm is probabilistic in th..