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

Аннотация

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