Решение линейных диофантовых уравнений от двух переменных

Актуальность

На современном этапе в эпоху тотальной цифровизации всех областей жизнедеятельности более важной проблемой становится защита информации, а значит, криптография и ее математические основы требуют к себе особого внимания и дальнейшего развития. Задача о решении линейных диофантовых уравнений от двух переменных является, с одной стороны, объектом математического изучения, а с другой – тесно связана с криптографической защитой информации, а именно с функцией шифрования системы RSA.

Цель

Программно реализовать поиск решения любого линейного диофантового уравнения от двух переменных.

Задачи

1. Выделить существующие теоретические основы в математике, с помощью которых решаются линейные диофантовые уравнения от двух переменных.
2. Выбрать наиболее универсальный метод решения линейный диофантовых алгоритмов от двух переменных.
3. Построить математическую модель выбранного метода.
4. Разбить выбранный математический метод на части, которые необходимо запрограммировать как отдельные задачи.
5. Для каждой выделенной задачи подобрать или разработать эффективный алгоритм на языке программирования.
6. Для выбранного метода осуществить общую сборку алгоритмов для реализации решения линейного диофантового уравнения с двумя неизвестными.

Оснащение и оборудование, использованное при создании работы

• Компьютер
• Язык программирования Python

Описание

В данной работе рассматривались линейные диофантовые уравнения вида

ax + by = c, где a, b, c — целые числа.

В математике выделены следующие методы решения диофантовых линейных уравнений от двух переменных:

• метод полного перебора всех возможных значений переменных, входящих в уравнение;
•  метод, основанный на выражении одной переменной через другую и выделении целой части дроби;
• метод, основанный на алгоритме Евклида;
• метод, основанный на теории цепных дробей;
• метод, основанный на теории сравнений;
• метод бесконечного спуска;
• с помощью функции Эйлера.

Авторы работы осуществили программную реализацию методов, исходя из следующих критериев:

• по легкости написания программы (без универсальных методов): Математический метод №1 – метод полного перебора всех возможных значений переменных, входящих в уравнение;
• по составлению универсальных алгоритмов: Математический метод № 3 – метод, основанный на алгоритме Евклида.

Результаты работы/выводы

В результате проделанной работы получился скрипт, который проверяет разрешимость любого линейного диофантового уравнения и при положительном ответе дает параметрическое решение.

Перспективы использования результатов работы

В перспективах модернизировать решения при помощи применения других методов поиска НОД, например: Бинарный алгоритм вычисления НОД, -арный алгоритм Евклида, Аппроксимирующий -арный алгоритм поиска НОД и другие.

Также в планах осуществить программную реализацию с помощью других методов решения: метод, основанный на выражении одной переменной через другую и выделении целой части дроби; метод, основанный на теории цепных дробей; метод, основанный на теории сравнений; метод бесконечного спуска; с помощью функции Эйлера. Продолжить работать дальше над диафантовыми уравнениями второй степени для решения проблемы квадратичного вычета, которая лежит в основе системы шифрования Гольдвассер—Микали, на ней базируется семантическая секретность систем Накаша—Штерна и Бекалоха.