Алгоритм построения базиса множества решений систем линейных диофантовых уравнений в кольце целых чисел

Abstract

Запропоновано поліноміальний алгоритм побудови мінімальної породжуючої множини (пред-базиса) і базиса множини всіх розв’язків системи лінійних діофантових рівнянь в кільці цілих чисел. Цей алгоритм грунтується на модифікованому TSS-методі.A polynomial algorithm is proposed to construct the minimal generating set of solutions and the basis of the solution set for systems of linear Diophantine equations over the ring of integer numbers. The algorithm is based on the modified TSS-method.