Use of the Maple system in mathematical problems of cryptography. Part 1. Elementary theory of numbers
Volodymyr Mykhalevych, Leonid MaidanevychOn the basis of the analysis of literary sources, a conclusion was made about the relevance of using the environment of the Maple computer mathematics system for the purpose of creating software for conducting scientific research and creating educational and methodological materials for solving typical mathematical problems of cryptography. It is noted that the most famous and widespread cryptographic algorithm with a public key RSA is based on a number of problems of elementary number theory that can be solved using standard tools of the Maple system. This work examines the specified standard commands with a demonstration of their application techniques on specially developed examples. The commands for solving problems in such sections as divisibility of whole numbers, prime numbers are considered; the most important functions in number theory: functions for selection of integer and fractional parts of a number and multiplicative functions; congruences and systems of congruences of the first order, quadratic remainders. A simple and effective algorithm and program for determining prime Mersenne numbers based on standard Maple commands is given. This algorithm is based on the necessary condition of simplicity of Mersenne numbers. The work of the author's educational Maple calculation simulators is demonstrated: according to the extended Euclid algorithm; Euler functions; symbol of Legendre; Jacobi symbol. The operation of the Euler function training simulator is demonstrated when calculating the corresponding value for a prime number, a composite number that is the product of two primes, a composite number that is a natural power of a prime number, as well as composite natural numbers of arbitrary structure. With the help of fragments of the program code, which can be used as a basis for the development of training simulators, the determination of the complete system of the smallest integral residues is demonstrated; of the complete system of the absolute smallest and the reduced system of remainders by simple and composite modules
References
[1] Khoroshko, V.O., Azarov, O.D., Shelest, M.E., Andreev, V.I., Mukhachyov, V.A., Shcherbina, V.P., & Yaremchuk, Yu.E. (2003). Computer cryptography. Laboratory practice. Kyiv: NAU.
[2] Hulak, H.M., Mukhachov, V.A., Khoroshko, V.O., & Yaremchuk, Yu.E. (2011). Fundamentals of cryptographic protection of information. Vinnytsia: VNTU.
[3] Kvyetny, R.N., Tytarchuk, E.O., & Gurzhii, A.A. (2016). Method and algorithm of key exchange among groups of users based on asymmetric ECC and RSA ciphers. Information Technologies and Computer Engineering, 3, 38-43.
[4] Luzhetsky, V.A., Voytovych, O.P., & Dudatiev, A.V. (2009). Information security: A study guide. Vinnytsia: UNIVERSUM-Vinnytsia.
[5] Luzhetsky, V.A., & Baryshev, Yu.V. (2011). Methods of multi-channel controlled hashing for computer cryptography. Information Technologies and Computer Engineering, 1, 66-72.
[6] Mikhalevich, V.M., Tyutyunnyk, O.I., & Korinny, O. (2022). Educational Maple simulator for calculations based on Euclid’s extended algorithm. In Proceedings of the All-Ukrainian scientific and methodological conference “Modern scientific and methodological problems of mathematics in of higher education (pp. 80-83). Kyiv: NUHT.
[7] Luzhetsky, V.A., Myhalevich, V.M., Myhalevich, O.V., & Kaplun, V.A. (2010). The density of filling a series of natural numbers with terms of a separate inverse sequence of the second order. Information Technologies and Computers Computer Engineering, 1, 46-51.
[8] Dobranyuk, Yu.V., Mikhalevich, V.M., Kolomiets, A.A., & Kozak, O.M. (2022). Application of Maple SCM for construction of 3D graphs in problems of calculating the volume of figures. Information Technologies and Computer Engineering, 2, 115-123.
[9] Mikhalevich, V.M., & Abramchuk, I.V. (2021). Maximum accumulated strain for linear two-link triangle-like deformation trajectories. International Applied Mechanics, 57(6), 720-736. doi: 10.1007/s10778-022-01121-w.
[10] Cheung, Y.L. (1996). Learning number theory with a computer algebra system. International Journal of Mathematical Education in Science and Technology, 3(27), 379-385. doi: 10.1080/0020739960270308.
[11] Klima, R., Sigmon, N., & Stitzinger, T. (2000). Applications of abstract algebra with Maple. Boca Raton: CRC Press.
[12] Baligaand, A., & Boztas, S. (2001). Cryptography in the classroom using Maple. In W. Yang, S. Chu, Z. Karian & G. Fitz-Gerald (Eds.), Proceedings of the sixth Asian technology conference in mathematics (pp.343-350). Melbourne: RMIT.
[13] Mikhalevich, V.M. (2005). Excel-VBA-Maple problem generation program for mathematical disciplines. Information Technologies and Computer Engineering, 2, 74-83.
[14] Mikhalevich, V.M., Dymnich, I.V., & Mykhalevich, O.V. (2007). Protection of Maple procedures. Information Technologies and Computer Engineering, 3(10), 159-165.
[15] Bedratyuk, L.P., & Bedratyuk, G.I. (2013). Using the Maple computer algebra system in elementary number theory. Eastern European Journal of Advanced Technologies, 6(4), 10-13.
[16] Bedratyuk, L.P., & Bedratyuk, G.I. (2015). The use of the Maple computer algebra system in classical cryptosystems. Bulletin of the Khmelnytskyi National University, 231(6), 148-153.
[17] Mikhalevich, V.M., Tyutyunnyk, O.I., Dremlyuga, E.S., & Medvedeva, K.V. (2021). Mathematical models and software tools for generating pseudorandom sequences for cryptographic applications. In L scientific and technical conference of the faculty of information sciencesof technology and computer engineering. Vinnytsia: VNTU.
[18] Mikhalevich, V.M., Rogachevskii, D.B., Zhelnytskyi, D.Yu., & Balukh B.A. (2022). Educational Maple simulator for calculating the Euler function. In LI scientific and technical conference of the faculty of information technologies and computer engineering. Vinnytsia: VNTU.
[19] Stasiuk, M. (2021). Elements of the mathematical foundations of cryptography. Lviv: LSU BZD.
[20] Ogloblina, O.I., Sushko, T.S., & Shramko, Yu.V. (2015). Elements of number theory. Sumy: Sumy State University.
[21] Kozhukhivskyi, A.D., Horbenko, I.D., Haydur, G.I., Kozhuhivska, O.A., & Marchenko, V.V. (2021). Mathematical methods of cryptology. Kyiv: SUT.