Control Systems and Computers, N6, 2017, Article 7
DOI: https://doi.org/10.15407/usim.2017.06.055
Upr. sist. maš., 2017, Issue 6 (272), pp. 55-64.
UDC 51.681.3
Sergii L. Kryvyi – Doctor of Physical and Mathematical Science, Professor, Professor of the Informational Systems Department of the Taras Shevchenko National University of Kyiv, E-mail: sl.krivoi@gmail.com
Vasyl T. Antoniuk – Student of the Informational Systems Department of the Taras Shevchenko National University of Kyiv, E-mail vasia.antoniuk@gmail.com
The Implementation of the Algorithm for Solving Systems of Linear Diophantine Equations Over Finite Residue Rings
Introduction. Finding the basis solutions set of the system of the linear Diophantine equations is one of the important and necessary problems of algebra, number theory, cryptography, the theory of mathematical games etc. When constructing a mathematical model of a large number of problems, it becomes clear that one of the methods of their solution is to find the basis of the set of all solutions of the system of the linear homogeneous or inhomogeneous Diophantine equations in a residue ring or a residue field modulo a composite or a prime number.
Purpose. The purpose of this work is to develop a programme that will be able to find a set of basis solutions of a system of linear Diophantine in a residue ring or a residue field modulo a composite or a prime number.
Methods. Achievement of the purpose is associated with solving the following problems: analysis of existing algorithms; detailed analysis and description of the chosen algorithm; its software implementation.
Results. Algorithms based on the TSS-method were chosen to solve the problem. The chosen algorithms were described in detail and the corresponding software solution was constructed.
Conclusion. As a result of the work, effective algorithms for solving the problem are described and implemented. The resulting application can be used in solving the relevant practical problems. Also, a detailed description of the algorithms will allow other researchers to build a wider system (for example, for greater constraints).
Keywords: residue ring, linear Diophantine constraints, set of basis solutions, software implementation.
- DONETS, G.A., AGHAEI, AGH GHAMISH YAGHOUB., 2013. “The mathematical safe problem on matrices”, In: Prepr. V.M. Glushkov Institute of Cybernetics of NANU, pp. 124–131. (In Russian).
- DONETS, G.A., SAMER, I.M. ALSHALAME, 2005. “Solution of the problem of construction of a linear mosaic”, Theory of Optimal Solutions, V.M. Glushkov Cybernetic Institute of NASU, Kiev, pp. 15–24. (In Russian).
- GANTMACHER, F.R., 1959. Matrix theory, Chelsea Publishing, New York, 258 p.
- VASILENKO, O.N., 2003. Number-Theoretic Algorithms in Cryptography, MTsNMO, Moscow. (In Russian).
- KRYVYI, S.L., 2015. Linear Diophantine Equations and Their Applications, Bukrek, Kiev. (In Ukrainian).
- KRYVYI, S.L., 2007. “Algorithms for solving systems of linear Diophantine equations in residue rings”, Cybernetics and Systems Analysis, 43, 6, pp. 787–798. (In Russian).
https://doi.org/10.1007/s10559-007-0103-1 - KRYVYI, S.L, 2007. “Algorithms for solution of systems of linear Diophantine equations in residue fields”, Cybernetics and Systems Analysis, 43, 2, pp. 171–178. (In Russian).
https://doi.org/10.1007/s10559-007-0036-8
Received 20.10.2017
