General solving linear Diophantine equations based on a modular transformation for risk assessment in information security

Abstract

Strictly formalized algorithms for solving linear Diophantine equations (LDE) of arbitrary order based on the use of modular transformations to determine quantitative values of information security risks. At every step of algorithms offered instead of one primary LDE formed two, the first of which is used on the reverse course of the algorithm, and the second - to further reduce the coefficients of the variables, to obtain one of the coefficients equal to unity. In the second equation, the coefficients of the unknowns are the remnants of the division of the primary coefficients of the equation for a minimum coefficient of this LDE. Due to this, there is a simultaneous decrease in the values of the coefficients of all the variables, instead of one of them, as it is implemented in the methods of change of variables. This provides a reduction the computational complexity of the algorithms and the values of the coefficients in the general solution of equations. Determine their time complexity T(n), where n - the number of unknowns in the equation. For algorithm A1 shown, that T₁(n)= O(n*m*log₂M) , where M – the maximum coefficient in equation, and m –the average labor input of a division operation with the remainder. For algorithm A2 asymptotic limit rating M it is of the order O(n*log_nM*m).