Використання системи Maple в математичних задачах криптографії. Повідомлення 1. Елементарна теорія чисел

Abstract

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.

На основі аналізу літературних джерел зроблено висновок про актуальність використання середовища системи комп`ютерної математики Maple з метою створення програмного забезпечення для проведення наукових досліджень та створення навчально-методичнх матеріалів з розв`язання типових математичних задач криптографії. Зазначено, що найбільш відомий та поширений криптографічний алгоритм з відкритим ключем RSA базується на низці задач елементарної теорії чисел, що можуть бути розв`язані за допомогою стандартних засобів системи Maple. В цій роботі розглянуто вказані стандартні команди з демонстрацією прийомів їх застосування на спеціально розробленх прикладах. Розглянуто команди для розв`язання задач за такими розділами, як подільність цілих чисел, прості числа; найважливіші функції в теорії чисел: функції виділення цілої та дробової частин числа та мультиплікативні функції; конгруенції та системи конгруенцій першого порядку, квадратичні лишки. Наведено простий та ефективний алгоритм і програма визначення за домогою стандартних команд Maple простих чисел Мерсенна. Вказаний алгоритм базується на необхіднійумові простоти чисел Мерсенна. Продемонстровано роботу авторських навчальних Maple-тренажерів обчислення: за розширеним алгоритмом Евкліда; функції Ейлера; символу Лежандра; символу Якобі. Роботу навчального тренажера з обчисення функції Ейлера продемонстровано під час обчислення відповідного значення для простого числа, складеного числа, що є добутком двох простих, складеного числа, що є натуральним степенем простого числа, а також складених натуральних чисел довільної структури. За допомогою фрагментів програмного коду, що можуть бути покладені в основу розробки навчальних тренажерів продемонстровано визначення повної системи найменших невід&39;ємних лишків; повної системи абсолютно найменших та зведеної системи лишків за простим та складеним модулями