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

Анотація

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