Solution algorithms for systems of linear equations over residue rings (Q341378)

The author considers a system \(S\) of linear Diophantine equations in the ring \(\mathbb{Z}_m\). The first theorem says that if the modulus can be factored into prime numbers, \(m= p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}\), where \(p_1<p_2< \dots <p_r\), then the original system \(S\) can be rewritten as an equivalent system \(S'\) of \(r\cdot s\) equations that consists of \(r\) subsystems \(S_i\) of \(s\) equations, each subsystem \(S_i\) modulo \(p_i^{k_i}\). The solution of the equivalent system \(S'\) is reduced to the solution of subsystems \(S_i\) modulo \(p_i^{k_i}\), or in residue fields modulo a prime number (in the case when \(k_i=1\) for some \(i \in [1,r]\)), or to the solution of systems in primary rings (in the case when \(k_i>1\)). In the paper, there are three algorithms for solutions of Diophantine systems of equations. At first, the author considers systems of linear homogeneous Diophantine equations (LHDE) over primary rings. Under some special conditions he constructs a base of the solution set of this LHDE. Then he constructs the base of systems of linear homogeneous Diophantine equations represented in general form. Finally, there is an algorithm for solving systems of linear inhomogeneous Diophantine equations. The author says that all proposed algorithms are based on the truncated solution set method. The complexity of the proposed algorithms is determined by the complexity of the problem of factorization of the number \(m\) into its prime numbers. If such a factorization is possible, then the proposed algorithms have polynomial complexity.