ЭВРИСТИЧЕСКИЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ДИОФАНТОВЫХ УРАВНЕНИЙ
Аннотация
Рассматривается задача решения диофантовых уравнений, которая может приме-
няться в криптографии и криптоанализе. Кратко излагается описание генетического ал-
горитма решения диофантовых уравнений. Определяется правило вычисления значения
целевой функции для хромосомы, описывается система кодирования в генетическом алго-
ритме. Упоминаются генетические операторы, используемые в алгоритме, определяются
условия их выполнения. Описывается критерий останова генетического алгоритма. Анали-
зируется один из недостатков генетического алгоритма – попытки решения любого дио-
фантова уравнения, в том числе и такого, которое заведомо не имеет решений. Предлага-
ется способ, позволяющий устранить этот недостаток в некоторых случаях, и, основан-
ный на теории чисел. Даётся пояснение, в каких случаях этот способ будет работать.
Перед описанием этого способа даётся определение вычета и невычета заданной степени
по заданному модулю. После описания этого способа подробно описывается программная
реализация алгоритма решения диофантовых уравнений и их систем. Затем приводятся
результаты экспериментальных исследований времени и качества работы генетического
алгоритма. Затем представляется результат работы алгоритма для уравнения, которое
заведомо не имеет решений, и для системы уравнений, которая также заведомо не имеет
решений, но в которой общее число неизвестных слишком велико для работы предлагаемо-
го метода. Сравнивается время работы алгоритма при решении уравнения и при решении
системы уравнений. Делается вывод о полезности применения предложенного способа при
решении диофантовых уравнений и систем диофантовых уравнений.
Литература
raspisaniya akademicheskikh kursov [An evolutionary algorithm for solving academic courses timetable
scheduling problem]. Available at: https://bsj.uobaghdad.edu.iq/index.php/BSJ/ article/
view/5309/3677 (accessed 29 October 2021).
2. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms].
2nd ed. Moscow: Fizmatlit, 2006, 320 p.
3. Goldberg D.E. Geneticheskie algoritmy poiska, optimizatsii i mashinnogo obucheniya [Goldberg
Genetic algorithms in search, optimization, and machine learning]. Izd. kompaniya
«Eddison-Uesli», 1989.
4. Delikatash D., Ozkan E., Ustun O., Torkul' O. Evolyutsionnye algoritmy dlya mnogotselevogo
gibkogo planirovaniya yacheek rabochikh mest [Evolutionary algorithms for multi-objective
flexible job shop cell scheduling]. Available at: https://reader.elsevier.com/reader/sd/pii/
S1568494621008127?token=B450EEE1CF1DDA0740952A46F8D57C861AD0F25F848BC3
9EAAFC2CD99565128625281A46285BAEAF57055ED57155F17D&originRegion=eu-west-
1&originCreation=20211029073249 (accessed 29 October 2021).
5. Devenport Kh. O probleme Uoringa dlya kubov [On Waring’s problem for cubes], Acta
Mathematica, 1939, Vol. 71.
6. Kavamura S., Komano Yu., Simidzu Kh., Yonemura T. Algoritmy Montgomeri s
ispol'zovaniem kvadratichnoy ostatochnosti [Montgomery algorithms using quadratic residuals].
Available at: https://link.springer.com/content/pdf/10.1007/s13389-018-0195-8.pdf (accessed
29 October 2021).
7. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: a textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 446 p.
8. Kreytsberg P., Serang O. O reshenii veroyatnostnykh lineynykh diofantovykh uravneniy [On solving
probabilistic linear diophantine equations]. Available at: https://jmlr.org/papers/volume 22/17-
474/17-474.pdf (accessed 29 October 2021).
9. Man Yu.K. Perspektivnyy podkhod k resheniyu lineynogo diofantova uravneniya [A forward
approach for solving linear Diophantine equation]. Available at: https://www.tandfonline.com/
doi/pdf/10.1080/0020739X.2020.1745915 (accessed 28 October 2021).
10. Manin Yu.I. Vychislimoe i nevychislimoe [Computable and non-computable]. Moscow:
Sovetskoe radio, 1980, 128 p.
11. Saymon D. Algoritmy evolyutsionnoy optimizatsii [Evolutionary optimization algorithms].
Moscow: Izd-vo «DMK Press», 2020, 1002 p.
12. Matiyasevich Yu.V. Desyataya problema Gil'berta [Hilbert's tenth problem]. Moscow:
Fizmatlit, 1993, 224 p.
13. Mitchell M. Vvedenie v geneticheskie algoritmy [An introduction to genetic algorithms]. London:
Pervoe izdanie izdatel'stva Massachusetskogo tekhnologicheskogo instituta v myagkoy
oblozhke, 1998, 158 p.
14. Osipov N.N., Kytmanov A.A. Algoritm resheniya semeystva diofantovykh uravneniy
chetvertoy stepeni, udovletvoryayushchikh usloviyu Runge [An algorithm for solving a family
of fourth-degree diophantine equations that satisfy Runge’s condition]. Available at:
https://events.rudn.ru/event/20/papers/178/files/445-Osipov-Kytmanov-CA-2019.pdf (accessed
28 October 2021).
15. Osipyan V.O. Razrabotka matematicheskoy modeli disimmetrichnoy bigrammnoy
kriptosistemy na osnove parametricheskogo resheniya mnogostepennoy sistemy diofantovykh
uravneniy [Development of a mathematical model of a disymmetric bigram cryptosystem
based on a parametric solution of a multistep system of diophantine equations], Inzhenernyy
vestnik Dona [Engineering Bulletin of the Don], 2020, No. 6.
16. Forouzan B.A. Kriptografiya i bezopasnost' setey: ucheb. posobie [Cryptography and network
security: a textbook]: transl. from Engl., ed. by A.N. Berlin. Moscow: Internet-Universitet
Informatsionnykh Tekhnologiy: BINOM. Laboratoriya znaniy, 2010, 784 p.
17. Kholland D.Kh. Geneticheskie algoritmy [Genetic algorithms]. Available at: https://www2.
econ.iastate.edu/tesfatsi/holland.GAIntro.htm (accessed 30 October 2021).
18. Chang K.-S., Li K.-T., Chen K. Sokhranenie konfidentsial'nosti i obratimoe sokrytie informatsii na
osnove arifmetiki kvadratichnykh vychetov [Privacy-preserving reversible information hiding based
on arithmetic of quadratic residues]. Available at: https://ieeexplore.ieee.org/stamp/
stamp.jsp?tp=&arnumber=8679991 (accessed 29 October 2021).
19. Chen' yu.-G., Yan Kh.-Kh. Gipoteza Sharkozi o kvadratichnykh vychetakh [A conjecture of
Sárközy on quadratic residues]. Available at: https://reader.elsevier.com/reader/sd/pii/
S0022314X21001402?token=B17EF4980D92E71F5CA05919D590CE859BA43F68FD937D6
6C630F36D032BCDB1A6541630B232868DE20F772B14520015&originRegion=eu-west-
1&originCreation=20211029110553 (accessed 29 October 2021).
20. Sharifi M.R., Akbarifard S., Kaderi K., Madadi M.R. Sravnitel'nyy analiz nekotorykh
evolyutsionnykh modeley v optimizatsii raboty vodokhranilishch plotiny [Comparative analysis
of some evolutionary-based models in optimization of dam reservoirs operation]. Available
at: https://www.nature.com/articles/s41598-021-95159-4.pdf (accessed 29 October 2021).
