Solution algorithms for systems of linear equations over residue rings
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.
- Algorithms for solving systems of linear Diophantine equations in residue rings
- scientific article; zbMATH DE number 1684382
- Algorithms for solving systems of linear Diophantine equations in integer domains
- An algorithm for constructing the basis of the solution set for systems of linear Diophantine equations over the ring of integers
- scientific article; zbMATH DE number 176134
- Complexity of solution of linear systems in rings of differential operators
- An error-free algorithm to solve a linear system of polynomial equations
- The complexity of solving low degree equations over ring of integers and residue rings
- An algorithm for constructing the basis of the solution set for systems of linear Diophantine equations over the ring of integers
- Algorithms for solving linear equations over associative rings with unit element
- scientific article; zbMATH DE number 1684382 (Why is no real title available?)
- scientific article; zbMATH DE number 3890617 (Why is no real title available?)
- scientific article; zbMATH DE number 4208276 (Why is no real title available?)
- scientific article; zbMATH DE number 4216963 (Why is no real title available?)
- Methods of solution of discrete equations systems over the ring of integers based on the construction of graphs of solutions
- scientific article; zbMATH DE number 3900852 (Why is no real title available?)
- Solution of a system of linear equations in an integral ring
- scientific article; zbMATH DE number 4045008 (Why is no real title available?)
- scientific article; zbMATH DE number 16652 (Why is no real title available?)
- Fast solution of linear systems with polynomial coefficients over the ring of integers
- scientific article; zbMATH DE number 2218936 (Why is no real title available?)
- STACS 2005
- Algorithms for solving linear constraints over the ring of integers
- Algorithms for solving systems of linear Diophantine equations in residue rings
This page was built for publication: Solution algorithms for systems of linear equations over residue rings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q341378)
