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...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2019
|
| Онлайн доступ: | http://mcm-math.kpnu.edu.ua/article/view/174208 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Репозитарії
Mathematical and computer modelling. Series: Physical and mathematical sciences| id |
mcm-mathkpnueduua-article-174208 |
|---|---|
| record_format |
ojs |
| spelling |
mcm-mathkpnueduua-article-1742082020-01-20T08:43:22Z 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 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 Розв’язання систем рівнянь над бітовими полями є актуальною задачею для галузей криптографії, теорії завадостійкого кодування інформації, роботехніки, астрофізики та інших областей. У даній статті запропоновано метод розв’язування бітових рівнянь, що базується на методології гілок та границь (branch-and-bound). Запропонована методологія вже буда використана авторами для розв’язання систем нелінійних алгебраїчних рівнянь. Метод може бути використаний не тільки для систем бітових рівнянь, а також і для розв’язання систем бітових рівнянь над довільними скінченними полями Галуа GF(n). Важливою особливістю запропонованого методу є те, що він дозволяє знайти усі розв’язки системи бітових рівнянь при будь-якому співвідношенні кількості змінних та кількості рівнянь. У статті наведено алгоритм, що реалізує послідовність дій, необхідну для реалізації запропонованого методу розв’язування систем бітових рівнянь. Алгоритм виконує послідовне зниження порядку системи (кількості змінних). Запропонована методика є спорідненою до методики Constrained Propagation, що використовується у задачах розв’язання систем нелінійних алгебраїчних рівнянь та задач глобальної мінімізації функцій. Також у статті наведено чисельні приклади, що демонструють роботу метода при розв’язанні систем бітових рівнянь у випадку квадратичних нелінійностей. При цьому також досліджені різні комбінації кількості рівнянь та кількості невідомих, а також окремо розглянуто випадок розрідженої системи рівнянь. Показано, що метод має перевагу в кількості операцій перед методом прямого перебору можливих розв’язків системи рівнянь Кам'янець-Подільський національний університет імені Івана Огієнка 2019-01-14 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/174208 10.32626/2308-5878.2019-19.137-141 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2019: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 19; 137-141 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2019: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 19; 137-141 2308-5878 10.32626/2308-5878.2019-19 uk http://mcm-math.kpnu.edu.ua/article/view/174208/174156 Авторське право (c) 2021 Василь Юрійович Семенов, Євгенія Вікторівна Семенова |
| institution |
Mathematical and computer modelling. Series: Physical and mathematical sciences |
| collection |
OJS |
| language |
Ukrainian |
| format |
Article |
| author |
Семенов, Василь Юрійович Семенова, Євгенія Вікторівна |
| spellingShingle |
Семенов, Василь Юрійович Семенова, Євгенія Вікторівна Method for the Solution of Systems of Bit Equations Based on Branch-and-Bound Principle |
| author_facet |
Семенов, Василь Юрійович Семенова, Євгенія Вікторівна |
| author_sort |
Семенов, Василь Юрійович |
| title |
Method for the Solution of Systems of Bit Equations Based on Branch-and-Bound Principle |
| title_short |
Method for the Solution of Systems of Bit Equations Based on Branch-and-Bound Principle |
| title_full |
Method for the Solution of Systems of Bit Equations Based on Branch-and-Bound Principle |
| title_fullStr |
Method for the Solution of Systems of Bit Equations Based on Branch-and-Bound Principle |
| title_full_unstemmed |
Method for the Solution of Systems of Bit Equations Based on Branch-and-Bound Principle |
| title_sort |
method for the solution of systems of bit equations based on branch-and-bound principle |
| title_alt |
Метод розв’язання систем бітових рівнянь на основі принципу гілок та границь |
| description |
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 |
| publisher |
Кам'янець-Подільський національний університет імені Івана Огієнка |
| publishDate |
2019 |
| url |
http://mcm-math.kpnu.edu.ua/article/view/174208 |
| work_keys_str_mv |
AT semenovvasilʹûríjovič methodforthesolutionofsystemsofbitequationsbasedonbranchandboundprinciple AT semenovaêvgeníâvíktorívna methodforthesolutionofsystemsofbitequationsbasedonbranchandboundprinciple AT semenovvasilʹûríjovič metodrozvâzannâsistembítovihrívnânʹnaosnovíprincipugíloktagranicʹ AT semenovaêvgeníâvíktorívna metodrozvâzannâsistembítovihrívnânʹnaosnovíprincipugíloktagranicʹ |
| first_indexed |
2024-04-21T19:24:35Z |
| last_indexed |
2024-04-21T19:24:35Z |
| _version_ |
1796973501973790720 |