Use of the Maple System in Mathematical Problems of Cryptography. Part 1. Elementary Theory of Numbers

On 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.