ON SOLVING LINEAR DIOPHANTINE SYSTEMS USING GENERALIZED ROSSER’S ALGORITHM

Abstract. A difficulty in solving linear Diophantine systems is therapid growth of intermediate results. Rosser’s algorithm for solvinga single linear Diophatine equation is an efficient algorithm thateffectively controls the growth of intermediate results. Here, wepropose an approach to generalize Rosser’s algorithm and presenttwo algorithms for solving systems of linear Diophantine equations.Then, we show that the generalized approach provides us with anew formulation of the LDSSBR of Chou and Collins and a moreefficient implementation of Rosser’s approach. The new formulationalso enables us to propose an efficient algorithm for solving rankone perturbed linear Diophantine systems based on the LDSSBR,and to improve and extend the class of integer ABS algorithms forsolving linear Diophantine systems.