Method for the Solution of Systems of Bit Equations Based on Branch-and-Bound Principle
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 propo...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2019
|
| Online Zugang: | http://mcm-math.kpnu.edu.ua/article/view/174208 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| Zusammenfassung: | 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 |
|---|