Омский государственный университет имени Ф.М. Достоевского,
Омский государственный технический университет

Аннотация:
Одной из наиболее интересных задач дискретной математики является задача поиска решающего набора в задаче ВЫПОЛНИМОСТЬ. Перспективным направлением в построении методов решения представляется сведение задачи к непрерывному поиску точек глобального минимума, ассоциированного с конъюнктивной нормальной формой (КНФ) функционала. В данной работе обосновывается выбор функционала специального вида и предлагается применить к решению системы нелинейных алгебраических уравнений, определяющих стационарные точки функционала, модифицированный метод последовательных приближений. В работе показано, что метод поддается распараллеливанию. Рассматривается  схема применения метода к важным задачам криптографического анализа несимметричных шифров, в том числе для определения некоторых бит двоичного представления неизвестных сомножителей в задачах факторизации больших размерностей.

Ключевые слова:
КНФ, ВЫПОЛНИМОСТЬ, резолюция, минимизация, криптографический анализ, факторизация.

Литература:

1. Дулькейт, В.И. Минимизация функционалов, ассоциированных с задачами криптографического анализа / В.И. Дулькейт, Р.Т. Файзуллин, И.Г. Хныкин // Дифференциальные уравнения. Функциональные пространства. Теория приближений. тез. докл. Международной конференции, посвященной 100-летию со дня рождения С.Л. Соболева. - Новосибирск: Ин-т математики СО РАН, 2008. - C.484-485.
2. Дулькейт, В.И. Сведение задач криптоанализа асимметричных шифров к решению ассоциированных задач ВЫПОЛНИМОСТЬ / В.И. Дулькейт, Р.Т. Файзуллин, И.Г. Хныкин // Сборник докладов XIII Всероссийской конференции «Математические методы распознавания образов». - М.: МАКС Пресс, 2007. - С.249-251.
3. Крейнович, В.Я. Семантика итеративного метода С.Ю. Маслова / В.Я. Крейнович //Вопросы кибернетики. Проблемы сокращения перебора.- М.: АН. СССР, 1987. -С. 30-62.
4. Маслов, С. Ю. Итеративные методы в переборной модели, как модель интуитивных / С. Ю. Маслов // Тезисы IX Всесоюзной конференции по кибернетике. - Сухуми, 1981. - С. 26 - 28.
5. Матиясевич, В.Ю. Возможные нетрадиционные методы установления выполнимости пропозицональных формул / В.Ю. Матиясевич // Вопросы кибернетики. Проблемы сокращения перебора.- М.: АН СССР. -1987. - С. 87-90.
6. Опарин, Г.А. Непрерывные модели решения систем булевых уравнений / Г.А. Опарин, А.П. Новопашин // Вестник Томского государственного университета. -2004.-№9 (1) - C. 20-25.
7. Хныкин И.Г. Модификации КНФ, эквивалентным задачам криптоанализа асимметричных шифров методом резолюции / И.Г. Хныкин // Информационные технологии моделирования и управления. - 2007. №2. - С.328-337.
8. Cook, S.A. Finding hard instances for the satisfiability problem: / S.A. Cook, D.G. Mitchel //A survey. DIMACS series in discrete mathematics and theoretical computer science. V.5. -1997.
9. Cook, S.A. The complexity of theorem proving procedures / S.A. Cook // Proceedings of the Third Annual ACM Symposium on Theory of Computing. - 1971. - P.151-158.
10. Gu, J. Algorithms for the satisfiability (sat) problem / J. Gu [and other] / J. Gu //Eds. Ding-Zhu Du Jun Gu and Panos Pardalos. - Satisfiability Problem. Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science.- AMS, 1997. -P. 19-152.
11. Koblitz, N. The state of elliptic curve cryptography. / N. Koblitz, A. Menezes, S. Vanstone //Designs Codes and Cryptography, 19, 2000. -P.173-193
12. Lenstra, A. The Development of the Number Field Sieve./ A. Lenstra, H. Lenstra -Springer-Verlag, -1993.
13. SAT 2005 Competition results [Электронный ресурс]. – Режим доступа: http://www.lri.fr/~simon/contest05/results/, свободный.
14. SAT Live! [Электронный ресурс]. – Режим доступа: www.satlive.org, свободный.

    ---

© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20