2020, issue 4, p. 15-38
Received 06.11.2020; Revised 12.12.2020; Accepted 17.12.2020
Published 31.12.2020; First Online 22.01.2021
https://doi.org/10.34229/2707-451X.20.4.2
Previous | Full text (in Ukrainian) | Next
The Mathematical Safe Problem and Its Solution (Part 1)
S.
Kryvyi * 
,
H. Hoherchak
Taras Shevchenko National University of Kyiv, Ukraine
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The problem of the mathematical safe arises in the theory of computer games and cryptographic applications. The article considers the formulation of the mathematical safe problem and the approach to its solution using systems of linear equations in finite rings and fields.
The purpose of the article is to formulate a mathematical model of the mathematical safe problem and its reduction to systems of linear equations in different domains; to consider solving the corresponding systems in finite rings and fields; to consider the principles of constructing extensions of residue fields and solving systems in the relevant areas.
Results. The formulation of the mathematical safe problem is given and the way of its reduction to systems of linear equations is considered. Methods and algorithms for solving this type of systems are considered, where exist methods and algorithms for constructing the basis of a set of solutions of linear equations and derivative methods and algorithms for constructing the basis of a set of solutions of systems of linear equations for residue fields, ghost rings, finite rings and finite fields. Examples are given to illustrate their work. The principles of construction of extensions of residue fields by the module of an irreducible polynomial, and examples of operations tables for them are considered. The peculiarities of solving systems of linear equations in such fields are considered separately. All the above algorithms are accompanied by proofs and estimates of their time complexity.
Conclusions. The considered methods and algorithms for solving linear equations and systems of linear equations in finite rings and fields allow to solve the problem of a mathematical safe in many variations of its formulation. The second part of the paper will consider the application of these methods and algorithms to solve the problem of mathematical safe in its various variations.
Keywords: mathematical safe, finite rings, finite fields, method, algorithm, solution.
Cite as: Kryvyi S., Hoherchak H. The Mathematical Safe Problem and Its Solution (Part 1). Cybernetics and Computer Technologies. 2020. 4. P. 15–38. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.4.2
References
1. Donets G.A. Solution of the Safe Problem on (0,1)-Matrices. Cybernetics and Systems Analysis. 2002. 38 (1). P. 83–88. https://doi.org/10.1023/A:1015596100010
2. Kaluzhnin L.A. Introduction to general algebra. M.: Nauka, 1973. 447 p. (in Russian)
3. Kryvyi S.L. Solution Algorithms for Systems of Linear Equations Over Residue Rings. Cybernetics and Systems Analysis. 2016. 52 (5). P. 791–801. https://doi.org/10.1007/s10559-016-9880-8
4. Kryvyi S.L. Algorithms for solution of systems of linear diophantine equations in residue fields. Cybernetics and Systems Analysis. 2007. 43 (2). P. 171–178. https://doi.org/10.1007/s10559-007-0036-8
5. Kryvyi S.L. Linear diophantine constraints and their application. Chernivtsi-Kyiv: Bookrek, 2015. 224 p. (in Ukrainian)
6. Koblitz N. Course in number theory and cryptography. M: Publishing house of TVP, 2001. 260 p. (in Russian)
7. Cheryomushkin A.V. Lectures on arithmetic algorithms in cryptography. M: MTsNMO, 2002. 103 p. (in Russian)
8. Kryvyi S.L., Hoherchak H.I. Algorithms for Solving Systems of Linear Equations in the Field Fpk. Journal of Automation and Information Sciences. 2019. 51 (10). P. 1–22. https://doi.org/10.1615/JAutomatInfScien.v51.i10.10
9. Lidl R., Niederreiter H. Finite fields. Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading MA, 1982. 20. P. 273–280.
10. Menezes A.J., Van Oorschot P.C., Vanstons S.A. Handbook of Applied Cryptography. CRC Press, 1996. 661 p.
11. Gavrilkevich M.V., Solodovnikov V.I. Efficient algorithms for solving linear algebra problems over a field of two elements. Review of Applied Industrial Mathematics. 1995. 2 (3). P. 400-437. (in Russian)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Ukrainian) | Next