СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

Аннотация
Данная работа посвящена модификации непрерывного метода поиска решения задачи выполнимости булевых формул (SAT). Показан способ, по которому строится функционал, ассоциированный с SAT, и приведен общий    алгоритм его решения методом простой итерации. Приведены ссылки на предыдущие работы автора и пояснено, что не всегда удается найти точное решение из-за попадания траектории метода простой итерации в овраг. Вместо построения эвристик по преодолению овражной ситуации и продолжения поиска предлагается сконструировать способ, который позволит определять некоторые биты приближения с высокой вероятностью. Полученные результаты могут быть с успехом использованы в задачах криптоанализа асимметричных шифров, логистики, автоматическом тестировании, распознавании данных, авторизации, в различных задачах на графах и других проблемах, которые сводятся к задаче SAT полиномиальным алгоритмом. Особое внимание уделяется задаче факторизации целых чисел, на которой построен известный асимметричный алгоритм шифрования RSA. Известно, что часть выполняющего набора SAT является ключом шифрования RSA. Соответственно, достаточно уметь определять часть выполняющего набора с высокой вероятностью. В предыдущих работах автора были определены некоторые нулевые биты с высокой вероятностью, в этой же работе основной упор делается на верное распознавание единичных бит. Для повышения числа единичных бит произведено построение нетривиального проектирования вещественных переменных в булевы. Представлено четыре способа: проектирование по окончании всех итераций, проектирование между итерациями с фиксированным параметром, проектирование с различными параметрами, байесовский подход. Проведено тестирование представленных методов на экземплярах 3-КНФ, эквивалентных задаче факторизации целых чисел. Полученные результаты сравниваются между собой, при этом критерием оптимальности выступает число верно определенных бит (как нулевых, так и единичных).  Введены случайные величины  и , равные числу верно определенных нулевых и единичных бит соответственно. С помощью метода хи-квадрат Пирсона показано, что  и  имеют равномерное распределение, что позволяет выбирать произвольное стартовое приближение.

 

Список литературы
1. Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. – 1973. – Т. 9, вып. 3. – С. 115–116.

2. Sat Live! [Electronic resource]: website. – URL: www.satlive.org (accessed: 28.01.2015).

3. Gu J. Local search for satisfiability (SAT) problem // IEEE Transactions on Systems, Man, and Cybernetics. – 1993. – Vol. 23, iss. 4. – P. 1108–1129. – doi: 10.1109/21.247892.

4. Gu J. On optimizing a search problem // Artificial Intelligence Methods and Applications / N.G. Bourbakis, ed. – New Jersey: World Scientific Publishing, 1992. – Ch. 2. – P. 63–105. – (Advanced series on Artificial Intelligence; vol. 1).

5. Cook S.A. The complexity of theorem proving procedures // Proceedings of the Third Annual Symposium on Theory of Computing, STOC '71. – New York, USA: ACM Press, 1971. – P. 151–158. – doi: 10.1145/800157.805047.

6. Davis M., Logeman G., Loveland D. A machine program for theorem proving // Communication of the ACM. – 1962. – Vol. 5, N 7. – P. 394–397. – doi: 10.1145/368273.368557.

7. Batiti R., Protasi M. Approximate algorithms and heuristics for MAX-SAT // Handbook of Combinatorial Optimization. – Kluwer Academic Publishers, 1998. – Vol. 1. – P. 77–148. – doi: 10.1007/978-1-4613-0303-9_2.

8. Гуселетова О.Н. Математические модели и алгоритмы дискретной оптимизации для решения задач формирования сложных изделий: автореф. дис. … канд. техн. наук. – Омск, 2008. – 16 с.

9. Handbook of applied cryptography / A.J. Menezes, P.C. van Oorschot, S.A. Vanstone. – Boca Raton, Florida, USA: CRC Press, 2001. – 780 p.

10. Маслов С.Ю. Итеративные методы в переборной модели, как модель интуитивных // Тезисы IX Всесоюзного симпозиума по кибернетике, 10–15 ноября 1981 г. – Сухуми, 1981. –

С. 26–28.

11. Крейнович В.Я. Семантика итеративного метода С.Ю. Маслова // Вопросы кибер-нетики: сборник статей. – М.: [б. и.], 1987. – Вып. 131: Проблемы сокращения перебора. –

С. 30–62.

12. Опарин Г.А., Новопашин А.П. Непрерывные модели решения систем булевых уравнений // Вестник Томского государственного университета. Приложение: Материалы международных всесоюзных и региональных научных конференций, симпозиумов, школ, проходивших в ТГУ. – 2004. – № 9 (1). – С. 20–25.

13. Файзуллин Р.Т., Дулькейт В.И., Огородников Ю.Ю. Гибридный метод поиска приближенного решения задачи 3-выполнимость, ассоциированной с задачей факторизации // Труды Института математики и механики УрО РАН. – 2013. – Т. 19, № 2. – С. 285–294.

14. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Непрерывные аппроксимации решения задачи «выполнимость» применительно к криптографическому анализу асимметричных шифров // Компьютерная оптика. – 2009. – T. 33, № 1. – С. 68–73.

15. Огородников Ю.Ю., Файзуллин Р.Т. Определение нулевых бит задачи 3-выполни-мость, ассоциированной с задачей факторизации // Компьютерная оптика. – 2014. – Т. 38,

№ 3. – С. 521–528.

16. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. – 1978. – Vol. 21, iss. 2. – P. 120–126. – doi: 10.1145/359340.359342.

17. Patsakis C. RSA private key reconstruction from random bits using SAT solvers [Electronic resource]. – Received 18 Jan 2013, last revised 7 May 2013. – (Cryptology ePrint Archive: report 2013/026). – URL: https://eprint.iacr.org/2013/026 (accessed: 28.01.2015).

18. Березин И.С., Жидков Н.П. Методы вычислений: учебное пособие для вузов. Т. 2. – М.: Физматлит, 1959. – Гл. 7, § 5. Решение систем уравнений. – С. 150–162.

19. Местецкий Л.М. Математические методы распознавания образов: курс лекций [Электронный ресурс] / МГУ, [факультет] ВМиК, кафедра «Математические методы прогнозирования». – М., 2002. – Гл. 2, § 2.1. Классификация на основе Байесовской теории решений. –

С. 8–13. – URL: http://www.ccas.ru/frc/papers/mestetskii04course.pdf (дата обращения: 28.01.2015).

20. Теория вероятностей и математическая статистика. Базовый курс с примерами и задачами: учебное пособие / А.И. Кибзун, А.Р. Гориянова, А.В. Наумов, А.Н. Сиротин. – М.: Физматлит, 2002. – 224 с.