A polynomial algorithm for solving systems of two linear diophantine equations

DOI10.1016/0304-3975(90)90082-SzbMath0701.68050MaRDI QIDQ914391

Jean-François Romeuf

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

polynomial algorithmlinear diophantine systemsminimal length solution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer solution of Diophantine equations (11Y50) Number-theoretic algorithms; complexity (11Y16) Linear Diophantine equations (11D04)

Related Items (6)

General solution of systems of linear diophantine equations and inequations ⋮ An algorithm for constructing the basis of the solution set for systems of linear Diophantine equations over the ring of integers ⋮ Finite-state automata in information technologies ⋮ Algorithms for solution of systems of linear Diophantine equations in residue fields ⋮ Combinatorial method for solving systems of linear constraints ⋮ Methods of solution and criteria of consistency of systems of linear Diophantine equations over the set of natural numbers

Uses Software

• ALGOL 60

Cites Work

• Efficient solution of linear diophantine equations
• An algorithm to generate the basis of solutions to homogeneous linear Diophantine equations
• Rational sets in commutative monoids
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Bounded Algol-Like Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial algorithm for solving systems of two linear diophantine equations