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.