C&SA | Contents

Volume 62 >>> № 2 MARCH — APRIL 2026

-->

UDC 61.681.3

S. Kryvyi
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine,
sl.krivoi@gmail.com

O. Chugaenko
Samsung R&D Institute Ukraine (SR Ukraine), Kyiv, Ukraine, firestreami13@yahoo.com

ON ALGORITHMS FOR SOLVING LINEAR EQUATIONS IN RESIDUE RINGS

Abstract. Two algorithms for solving systems of linear congruences in residue rings are analyzed. One of the algorithms is based on the factorization of the module and solution of the subsystems into which the initial system is decomposed, in the primary rings or the fields. The second algorithm relies on the introduction of certain redundancies during calculations. Both algorithms find the generators of the set of all solutions of the initial system of linear congruences. The dependencies of both algorithms on the value of the module, the number of congruences, and the number of variables in the systems are given in the tables and in the charts obtained during the experiments.

Keywords: linear equations, residue ring, algorithms, complexity.

full text

REFERENCES

1. Menezes A., van Oorschot P., Vanstons S. Handbook of applied cryptography. Boca Raton: CRC Press, 1996. 661 p.
2. Lenstra A.K., Lenstra M.S., Menasse M.S., Pollard J.M. The number field sieve. Proc. of the 22nd ACM Symposium on the Theory of Computing (13–17 May 1990, Baltimore, USA). Baltimore, 1990. P. 564–572.
3. Kaluzhnyn L.A. Introduction to general algebra [in Russian]. Moscow: Nauka, 1973. 447 p.
4. Shoup V. A computational introduction to number theory and algebra. Cambridge: Cambridge University Press, 2008. 580 p.
5. Kryvyi S.L. Algorithms for solution of systems of linear Diophantine equations in residue fields. Cybernetics and Systems Analysis. 2007. Vol. 43, N 2. P. 171–178. https://doi.org/10.1007/s10559-007-0036-8.
6. Kryvyi S.L. Algorithms for solution of linear constraints over residue ring. Cybernetics and Systems Analysis. 2024. Vol. 60, N 6. P. 862–871. https://doi.org/10.1007/s10559-024-00723-1.
7. Kryvyi S.L., Antonyuk V.T. Implementation of an algorithm for solving systems of linear Diophantine equations in a residue ring. Control Systems and Machines. 2017. No. 6. P. 55–64.