HEURISTIC GENETIC ALGORITHM FOR DIOPHANTINE EQUATIONS SOLVING
Abstract
The problem of diophantine equations solving is considered in this article. This problem can
be applied in cryptography and cryptanalysis. The description of the genetic algorithm solving
diophantine equations is stated briefly in the article. The rule of calculation the value of fitness
function of chromosome is determined, the coding system in the genetic algorithm is described.
The genetic operators used in the algorithm are mentioned and the conditions for their execution
are determined. The criterion for stopping the genetic algorithm is described. One of the shortcomings
of the genetic algorithm is analyzed. The shortcoming of the algorithm lies in its attempts
to solve any diophantine equation, including one that has no solutions. A method eliminating this
shortcoming in some cases is proposed. This method is based on number theory. An explanation is
given in which cases this method will be used. The definition of residue and nonresidue of fixed
power for fixed modulus is given before describing this method. After describing this method the
implementation of the algorithm for solving diophantine equations and systems of them is described
in detail. Then the results of experimental studies of the time and quality of the genetic
algorithm are presented. Then the result of the algorithm is presented for an equation that has no
solutions and for a system of equations that also has no solutions, but in which the total number of
unknowns is too large for the proposed method to work. The algorithm running time is compared
when solving an equation and when solving a system of equations. The conclusion is made about
the usefulness of the proposed method in solving diophantine equations and systems of diophantine
equations.
References
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).
