В настоящей статье рассматриваются алгоритмы построения базиса множества решений систем линейных диофантовых уравнений в кольце Zm вычетов по модулю составного числа т. Данная статья является продолжением работ [1, 2]. В основе предлагаемых алгоритмов лежит TSS-метод построения минимального порождающего множества решений систем линейных однородных диофантовых уравнений в множестве натуральных чисел Af [3 ]. К такого рода системам и методам их решений сводятся задачи математических игр [4], распознавания изображений [5], криптографии [6 ], распараллеливания циклов [7 ] и многие другие задачи. Описываемые алгоритмы имеют полиномиальную оценку сложности при условии, что известно разложение модуля кольца на простые множители.
展开▼
