DOI: https://doi.org/10.32626/2308-5878.2019-19.137-141

Метод розв’язання систем бітових рівнянь на основі принципу гілок та границь

Василь Юрійович Семенов, Євгенія Вікторівна Семенова

Анотація


Розв’язання систем рівнянь над бітовими полями є актуальною задачею для галузей криптографії, теорії завадостійкого кодування інформації, роботехніки, астрофізики та інших областей. У даній статті запропоновано метод розв’язування бітових рівнянь, що базується на методології гілок та границь (branch-and-bound). Запропонована методологія вже буда використана авторами для розв’язання систем нелінійних алгебраїчних рівнянь. Метод може бути використаний не тільки для систем бітових рівнянь, а також і для розв’язання систем бітових рівнянь над довільними скінченними полями Галуа GF(n). Важливою особливістю запропонованого методу є те, що він дозволяє знайти усі розв’язки системи бітових рівнянь при будь-якому співвідношенні кількості змінних та кількості рівнянь. У статті наведено алгоритм, що реалізує послідовність дій, необхідну для реалізації запропонованого методу розв’язування систем бітових рівнянь. Алгоритм виконує послідовне зниження порядку системи (кількості змінних). Запропонована методика є спорідненою до методики Constrained Propagation, що використовується у задачах розв’я­за­н­ня систем нелінійних алгебраїчних рівнянь та задач глобальної мінімізації функцій. Також у статті наведено чисельні приклади, що демонструють роботу метода при розв’язанні систем бітових рівнянь у випадку квадратичних нелінійностей. При цьому також досліджені різні комбінації кількості рівнянь та кількості невідомих, а також окремо розглянуто випадок розрідженої системи рів­нянь. Показано, що метод має перевагу в кількості операцій перед методом прямого перебору можливих розв’язків системи рівнянь

Повний текст:

PDF

Посилання


Лидл Р., Нидеррайтер Г. Конечные поля: Т. 1. Пер. с англ. М.: Мир, 1988. 430 с.

Faugère J.-C. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). Proc. Int. Symp. Symbolic and Algebraic Computation. N.-Y., 2002. P. 75–83.

Neumaier A. Complete Search in Continuous Global Optimization and Constraint Satisfaction. Acta Numerica. 2004. P. 383–408.

Семенов В. Метод нахождения всех корней системы нелинейных алгебраических уравнений, основанный на операторе Кравчика. Кибернетика и системный анализ. 2015. Вып. 51, № 5. C. 169–175.