ЭВРИСТИЧЕСКИЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ДИОФАНТОВЫХ УРАВНЕНИЙ

Аннотация

Рассматривается задача решения диофантовых уравнений, которая может приме-
няться в криптографии и криптоанализе. Кратко излагается описание генетического ал-
горитма решения диофантовых уравнений. Определяется правило вычисления значения
целевой функции для хромосомы, описывается система кодирования в генетическом алго-
ритме. Упоминаются генетические операторы, используемые в алгоритме, определяются
условия их выполнения. Описывается критерий останова генетического алгоритма. Анали-
зируется один из недостатков генетического алгоритма – попытки решения любого дио-
фантова уравнения, в том числе и такого, которое заведомо не имеет решений. Предлага-
ется способ, позволяющий устранить этот недостаток в некоторых случаях, и, основан-
ный на теории чисел. Даётся пояснение, в каких случаях этот способ будет работать.
Перед описанием этого способа даётся определение вычета и невычета заданной степени
по заданному модулю. После описания этого способа подробно описывается программная
реализация алгоритма решения диофантовых уравнений и их систем. Затем приводятся
результаты экспериментальных исследований времени и качества работы генетического
алгоритма. Затем представляется результат работы алгоритма для уравнения, которое
заведомо не имеет решений, и для системы уравнений, которая также заведомо не имеет
решений, но в которой общее число неизвестных слишком велико для работы предлагаемо-
го метода. Сравнивается время работы алгоритма при решении уравнения и при решении
системы уравнений. Делается вывод о полезности применения предложенного способа при
решении диофантовых уравнений и систем диофантовых уравнений.