A disaggregation approach for solving linear Diophantine equations

摘要

Finding integer solutions to a set of linear equations has been achallenging problem with application in many areas, such as knapsackoptimization and cryptography. In this paper, we nd a new methodfrom the angle of disaggregation to solve a system of linear Diophantineequations. The disaggregation process, which employs the LLL proce-dure in the literature, keeps generating new valid linear equations untilthe system of equations becomes high-ranked and easy to solve.