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.