Method for the Solution of Systems of Bit Equations Based on Branch-and-Bound Principle

• Date: 2019
• Main Authors: Семенов, Василь Юрійович, Семенова, Євгенія Вікторівна
• Format: Article
• Language: Ukrainian
• Published: Кам'янець-Подільський національний університет імені Івана Огієнка 2019
• Online Access: http://mcm-math.kpnu.edu.ua/article/view/174208
• Journal Title: Mathematical and computer modelling. Series: Physical and mathematical sciences

Solution of systems of bit equations is an important task for the cryptography, theory of error-correction coding, information coding, robotechnics, astrophysics and other fields. In this paper we propose a method for the solution of bit equations based on the branch-and-bound methodology. The proposed methodology was already used by the authors for the solution of systems of nonlinear algebraic equations. The method can be applied not just for the systems of bit equations, but also for the equations over arbitrary finite Galois field GF(n). The important feature of proposed method is that it allows to find all solutions of system of bit equations for any combination of number of equations and number of variables. The algorithm for the implementation of the proposed method is given. The algorithm performs subsequent decreasing of the order of the system (i. e. number of variables). The proposed methodology is close to the method of Constrained Propagation which is used for the solution of the systems of nonlinear equations and global minimization tasks. Numerical examples demonstrating the application of the method to the solution of systems of quadratic bit equations is also shown. Different combinations of the number of variables and the number of equations are considered. It is shown that the method has advantage over the direct search approach for the solution of the system of bit equations