Информационная технология минимизации функционалов, ассоциированных с задачей выполнимость тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Хныкин, Иван Геннадьевич

• Хныкин, Иван Геннадьевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Хныкин, Иван Геннадьевич

Введение.

Глава 1. Задача ВЫПОЛНИМОСТЬ и методы ее решения.

1.1. Постановка задач.

1.2. Математические модели задачи ВЬШОЛНИМОСТЬ.

1.3. Алгоритмы поиска решения задачи ВЫПОЛНИМОСТЬ.

1.3.1. Алгоритм DP (Davis-Putnam).

1.3.2. Алгоритм DPLL (Davis-Putnam-Logemann-Loveland).

1.3.3. Методы локального поиска.

1.3.4. Методы преодоления локальных экстремумов.

1.3.5. Семейство алгоритмов локального поиска с обходом локальных минимумов.

1.3.6. Семейство градиентных алгоритмов локального поиска.

1.3.7. Методы глобальной оптимизации.

1.3.8. Непрерывный метод Лагранжа.

Глава 2. Описание гибридного метода последовательных приближений с «инерцией» в применении к задаче ВЫПОЛНИМОСТЬ.

2.1. Переход от задачи ВЬШОЛНИМОСТЬ к задаче поиска глобального минимума.

2.2. Построение метода последовательных приближений с «инерцией».

2.3. Модификации и гибридизации метода последовательных приближений с «инерцией».

2.3.1. Переход к задаче 3-ВЬШОЛНИМОСТЬ.

2.3.2. Стратегия применения правил резолюции.

2.3.3. Выбор начального приближения.

2.3.4. Добавление весовых множителей.•.

2.3.5. Сдвиг по антиградиенту.

2.3.6. Туннелирование.

2.3.7. Метод смены траектории.

2.3.8. Рестарт.

2.3.9. Выбор метода проектирования.

2.3.10. Увеличение разрядности.

2.3.11. Гибридный метод последовательных приближений с «инерцией».

2.3.12. Способы распараллеливания метода.

Глава 3. Результаты численных экспериментов применения модифицированного метода последовательных приближений с «инерцией» к различным типам задач ВЬШОЛНИМОСТЬ.

3.1. Задачи для тестирования метода последовательных приближений с инерцией» и его модификаций.

3.1.1. Тестовые примеры открытой библиотеки SATLib.

3.1.2. Задачи криптографического анализа несимметричных шифров.

3.2. Результаты численных экспериментов гибридного метода последовательных приближений с «инерцией».

3.2.1. Стратегия применения правил резолюции.

3.2.2. Переход к задаче 3-ВЫПОЛНИМОСТЬ.

3.2.3. Добавление весовых множителей.

3.2.4. Сдвиг по антиградиенту.

3.2.5. Метод смены траектории и туннелирование.

3.2.6. Увеличение разрядности.

3.2.7. Гибридный метод последовательных приближений с «инерцией».

3.2.8. Способы распараллеливания метода.

3.3. Исследование применимости метода последовательных приближений с «инерцией» к задаче факторизации.

3.3.1. Определение наиболее вероятных значений бит сомножителей.

3.3.2. Выбор начального приближения.

Введение диссертации (часть автореферата) на тему «Информационная технология минимизации функционалов, ассоциированных с задачей выполнимость»

Задача ВЫПОЛНИМОСТЬ — одна из наиболее интересных задач информатики.

В 1936 году Эмиль Пост (Emil Leon Post), а в 1937 году - Алан Тьюринг (Alan Turing) независимо друг от друга разработали теоретическую модель вычислительной машины, которая легла в основу теории алгоритмов. Она представляет собой бесконечную в одну сторону ленту, по которой передвигается одна — единственная головка. Каждая ячейка ленты может находиться в одном из состояний: ноль, единица, а также в неопределенном состоянии. На каждом шаге выполнения алгоритма головка может сдвинуться влево, сдвинуться вправо либо записать в ячейку, над которой она находится, ноль или единицу. Программа для такой машины — это сколь угодно большой, но конечный набор состояний, каждому из которых соответствует некоторое действие, а также следующее состояние. Есть два выделенных состояния — исходное, в котором начинается работа программы, и специальное состояние СТОП, которое соответствует выходу из программы.

Эта модель вычислений, получившая название детерминированной машины Тьюринга, стала общепринятой (хотя Пост придумал свою модель на год раньше). В информатике широко известно нестрогое утверждение (так называемый тезис Чёрча), которое гласит, что любой объект, отвечающий нашему интуитивному понятию алгоритма, можно реализовать в виде программы на машине Тьюринга. Контрпримеров к этому утверждению пока не обнаружено, и оно считается верным — хотя доказать его невозможно.

Класс задач, которые решаются за полиномиальное время на детерминированной машине Тьюринга, называют классом Р.

Другой класс задач — которые решаются за полиномиальное время на, так называемых, недетерминированных машинах Тьюринга, называют классом NP. Для наглядности приведем следующее описание: задача входит в класс NP, если существует детерминированная машина Тьюринга «с подсказкой», которая по данной ей подсказке сможет за полиномиальное время либо дать положительный ответ и не ошибиться, либо дать отрицательный ответ с возможной ошибкой. При этом для каждого набора данных, ответ на который положителен, должна существовать подсказка, которую примет эта машина Тьюринга.

Проблема Р называется NP-полной, если Р принадлежит NP и любая задача из NP может быть сведена к задаче Р за полиномиальное время.

Исторически первой из известных NP-полных задач была задача ВЫПОЛНИМОСТЬ (ее полноту доказал Стивен Кук (Stephen Cook) [27]). Это и обусловило ее фундаментальность. Иными словами, существование полиномиального алгоритма решения задачи ВЫПОЛНИМОСТЬ влечет разрешение теоретической проблемы P=NP. Сегодня задача ВЫПОЛНИМОСТЬ занимает первое место в списке избранных NP-полных задач.

На практике, задача ВЫПОЛНИМОСТЬ является фундаментальной для решения многих проблем информатики: искусственного интеллекта, проектирования компьютерных систем, роботостроения, криптографии и других. Тема сведения задач из различных областей прикладной математики и информатики к задаче ВЫПОЛНИМОСТЬ хорошо развивается. В России этому посвящены работы Семенова А.А., Буранова Е.В., за рубежом известны работы Kautz Н. Selman В. [3], [85], [84], [51]. Одна из причин этого — возможность решать задачи, возникающие в самых различных областях, единым алгоритмом решения задачи ВЫПОЛНИМОСТЬ.

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

Цель работы.

Целью данной диссертационной работы является построение и исследование непрерывных моделей задачи ВЫПОЛНИМОСТЬ и исходя из этого построение эффективного метода решения задачи.

Актуальность работы.

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

Основным подходом проверки криптографической стойкости асимметричных шифров в настоящее время являются алгоритмы числового решета в поле чисел общего вида [53] и различные модификации алгоритмов ро - Полларда и лямбда - Полларда, основывающиеся на детерминированном случайном блуждании по группе [51], то есть методы требуют привлечения обширного математического аппарата. Сообщения появляющиеся время от времени лишь подтверждают стойкость известных алгоритмов. Например, для факторизации чисел «рабочих» размерностей (-1000 бит) требуется задействовать на несколько месяцев вычислительные мощности кластеров из самых верхних позиций списка Топ-500 [83]. То есть увеличение длины ключа в полтора или два раза решает вопрос о криптостойкости принципиально.

Совершенно новой альтернативой алгебраическому подходу является так называемый логический криптоанализ, когда криптографический алгоритм, рассматривается, как программа для машины Тьюринга и подстановка открытого и шифрованного текстов в эту программу естественным образом приводит к задаче ВЫПОЛНИМОСТЬ для конъюнктивной нормальной формы. Часть выполняющего набора является ключом алгоритма. Идея такого подхода была впервые предложена в 1997 году в работе Cook S. [28], при поиске сложных задач для тестирования решателей КНФ. Сегодня данная тематика представлена в работах Ушакова A. A., Massacci F., Беспалова Д.В., Marraro L., и других.

Как показал опыт, применение переборных алгоритмов, с частью из которых можно ознакомиться в обзоре Gu J. [44], сталкивается с принципиальными трудностями, задачи криптографии (и задачи больших размерностей вообще) оказываются действительно трудными для переборных алгоритмов. Естественно возникает идея перехода к непрерывным моделям, когда поиск выполнимого набора для КНФ осуществляется как поиск экстремума, ассоциированного с КНФ функционала. Впервые эта идея была реализована в работах Маслова С.Ю., Крейновича В.Я. и получила дальнейшее развитие в работах R.Sosic, J.Gu, A.Tora, A.Zilinskas [13], [14], [70], [69], [72]. Обратим внимание на то, что хотя существенных успехов на данный момент еще нет, но имеется принципиальное отличие непрерывных методов от переборных алгоритмов поиска, — сдвиг по антиградиенту происходит по всем переменным сразу. Кроме того, для многих задач, априори известно, что глобальный минимум функционала единственен и в случае, когда локальных минимумов и других особых точек нет, минимизация происходит эффективно.

С другой стороны, достаточно очевидно, что нет необходимости в том, чтобы «точно» определить все биты ключа. Достаточно той информации, что набор бит, или ключа, или множества бит, однозначно определяющего ключ, совпадает с точным решением с вероятностью значимо большей, чем 0.5. А в результате применения итерационных методов можно надеяться на то, что мы сможем «подобраться» к такой окрестности достаточно близко. Таким образом, проверка известных в настоящее время криптографических алгоритмов на стойкость к поиску глобального экстремума является новым и необходимым тестом.

Содержание работы.

Диссертационная работа состоит из введения, трех глав, заключения, библиографии, двух приложений.

Заключение диссертации по теме «Теоретические основы информатики», Хныкин, Иван Геннадьевич

Заключение

В работе проводятся исследования задачи ВЫПОЛНИМОСТЬ на основе математических моделей минимизации специальным образом построенного функционала.

Среди основных результатов диссертации можно отметить следующие:

1. Разработаны и обоснованы методики, равномерно улучшающие сходимость метода последовательных приближений с «инерцией» на всех типах задач ВЫПОЛНИМОСТЬ. Эффективность гибридного метода не уступает эффективности «лучших» решателей 2005 года.

2. Разработана стратегия применения правил резолюции. Исследована и подтверждена эффективность использования стратегии резолюции как препроцессора КНФ в методе последовательных приближений с «инерцией».

3. Исследована применимость метода последовательных приближений с «инерцией» к КНФ, ассоциированным с задачами криптоанализа асимметричных шифров.

4. Для КНФ, эквивалентных задаче факторизации (с соблюдением всех условий криптостойкости RSA) размерностью до 72 бит были получены точные решения. При этом эффективность предложенного метода превосходит известные нам решатели задачи ВЫПОЛНИМОСТЬ. Приближения, формируемые методом, более чем на 68% совпадают с решением независимо от размерности задачи (до 3072 бит включительно), причем с ростом размерности наблюдается рост доли совпадающих компонент вектора приближения. Кроме того, разработана система дополнительных тестов, позволяющая с высокой долей вероятности определять конкретные биты сомножителей в задаче факторизации.

Список литературы диссертационного исследования кандидат физико-математических наук Хныкин, Иван Геннадьевич, 2009 год

1. Бахвалов Н.С. Численные методы. - М.: Бином. Лаборатория знаний, 2007. -627 с.

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982. 579 с.

3. Дулькейт В.И. КНФ представления для задач факторизации и дискретного логарифмирования // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции. Екатеринбург: УрО РАН,2007. С.350-355.

4. Дулькейт В.И., Файзуллин Р.Е., Хныкин И.Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа асимметричных шифров // Прикладная дискретная математика. 2008. - № 2. - С.113-119.

5. Дулькейт В.И., Файзуллин Р.Т. Хныкин И.Г. Минимизация функционалов, ассоциированных с задачами криптографического анализа. // Доклады Томского государственного универистета систем управления и радиоэлектроники. 2008. -ч. 1.2(18). -С.54-56.

6. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Алгоритм минимизации функционала, ассоциированного с задачей 3-SAT и его практические применения // Компьютерная оптика, т. 32, №1. 2008. - С.68-73.

7. Дулькейт В.И., Файзуллин Р.Т., Хныкин И.Г. Непрерывные аппроксимации решения задачи ВЫПОЛНИМОСТЬ применительно к криптографическому анализу асимметричных шифров // Компьютерная оптика, т. 33, №1. 2009. -С. 86-91

8. Ершов Ю. Л., Палютин Е. А. Математическая логика. М.: Наука, 1987.

9. Кочетков Е.С., Смерчинская С.О., Соколов В.В. Теория вероятностей и математическая статистика. М.: Форум. Профессиональное образование, 2008. -240 с

10. Крейнович В.Я. Семантика итеративного метода С.Ю. Маслова // Вопросы кибернетики. Проблемы сокращения перебора. М.: АН. СССР, 1987. - С. 30-62.

11. Маслов С. Ю. Итеративные методы в переборной модели как модель интуитивных // Тезисы IX Всесоюзной конференции по кибернетике. 1981. -С.26-28.

12. Прикладная статистика. Учебник. / А.И.Орлов.- М.: Издательство «Экзамен», 2004. 656 с.

13. Файзуллин Р. Т. О решении нелинейных алгебраических систем гидравлики // Сибирский журнал индустриальной математики. 1999. - №2. -С. 176-184.

14. Хныкин И.Г. Модификации КНФ, эквивалентным задачам криптоанализа асимметричных шифров методом резолюции // Информационные технологии моделирования и управления. 2007. №2. - С.328-337.

15. Хныкин И.Г. Алгоритм минимизации функционала ассоциированного с задачей 3-SAT // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2007. -С.427-432.

16. Хныкин И.Г. Эквивалентное преобразование КНФ, ассоциированных с задачами криптографического анализа, с помощью правил резолюции // Прикладная дискретная математика, приложение. (Тез. докл. конф. SIBECRYPT'09) Томск: ТГУ, 2009.

17. Billionnet A., Sutter A. An efficient algorithm for 3-satisfiability problem // Operations Research Letters 12. 1992. - P.29-36.

18. Blum L., Blum M., Shub M. A Simple Unpredictable Pseudo-Random Number Generator // SIAM Journal on Computing. 1986. - Vol. 15., P.364-383.

19. Bugrara K., Purdom P. Clause order backtracking // Technical Report 311. -1990.-P. 17-26.

20. Buro M., Biining H.K. Report on a SAT competition // Bulletin of the European

21. Association for Theoretical Computer Science. 1993. - 49. - P. 143-151.

22. Cha В., Iwama K. Adding new clauses for faster local search // In Proceedings of AAAI-96. 1996. - P.332-337.

23. Cook S.A. The complexity of theorem proving procedures // Proceedings of the Third Annual ACM Symposium on Theory of Computing. 1971. - P.151-158.

24. Cook S.A., Mitchel D.G. Finding hard instances for the satisfiability problem // A survey. DIMACS series in discrete mathematics and theoretical computer science. -1997. Vol.5. - 151 p.

25. Davis M., Logemann G., Loveland D. A Machine Program for Theorem Proving // Communications of the ACM. 1962. - 5(7). - P.394-397.

26. Davis M., Putnam H. A Computing Procedure for Quantification Theory // Journal of the ACM. 1960. - 7(3). - P.201-215.

27. Doyle J. A truth maintenance system // Artificial Intelligence. 1979. - 12. -P.231-272.

28. Franco J. Elimination of infrequent variables improves average case performance of satisfiability algorithms // SIAM J. on Computing. 1991. - 20. - P.ll 19-1127.

29. Freuder E.C. Quinn M.J. Taking advantage of stable sets of variables in constraint satisfaction problems // In Proceedings of 9th IJCAI. 1985. - P.1076-1078.

30. Galil Z. On resolution with clauses of bounded size // SIAM Journal on Computing. 1977. - 6. - P.444-459.

31. Gent I., Walsh T. Towards an understanding of hill-climbing procedures for SAT // In Proceedings of AAAI-93. 1993. - 17 p.

32. Gu J. Global optimization for satisfiability (SAT) problem // IEEE Trans, on Knowledge and Data Engineering. 1994. - 6(3)Jun. - P.361-381.

33. Gu J. On Optimizing a Search Problem // In N. G. Bourbakis, editor, Artificial Intelligence Methods and Applications. 1992. Vol.1, chapter 2. - P.63-105.

34. Gu J. Efficient local search for very large-scale satisfiability problem // SIGART Bulletin. 3(1).Jan. - ACM Press, 1992. - P.8-12.

35. Gu J. Parallel algorithms and architectures for very fast search // Ph.D thesis.

36. Technical Report UUCS-TR-88-005. 1988. - 7 p.

37. Gu J. Local search for satisfiability (SAT) problem // IEEE Trans, on Systems, Man, and Cybernetics. 1993. - 23(4)Jul. - P. 1108-1129.

38. Gu J. How to solve Very Large-Scale Satisfiability problems // Technical Report UUCS-TR-88-032. 1988. - 6 p.

39. Gu J., Gu Q.P. Average time complexities of several local search algorithms for the satisfiability (SAT) problem // Technical Report UCECE-TR-91-004. 1991. -Vol. 834.-P. 146-154.

40. Gu J., Lizhoudu. An efficient implementation of the SAT 1.5 algorithm // Technical Report, USTC. 1995. - 11 p.

41. Haken, A. The intractability of resolution // Theoretical Computer Science. -1985.-39.-P. 142-150.

42. Hansen E. R. Global optimization using interval analysis / M. Dekker. N.Y., 1992.-20 p.

43. Horst R., Tuy H. Global Optimization: Deterministic Approaches // Springer, Verlag. Berlin, 1990. - 22 p.

44. Jeroslow R.E., Wang J. Solving prepositional satisfiability problems // Annals of Mathematics and AI. 1990. - 1. - P. 167-187.

45. Johnson D.S. Approximation Algorithms for Combinatorial Problems // Journal of Computer and Systems Sciences. 1974. - 9. - P.256-278.

46. Kautz H., Selman B. Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search //Proc. AAAI-96. 1996. - P.1194-1201.

47. Koblitz N., Menezes A., Vanstone S. The state of elliptic curve cryptography // Designs Codes and Cryptography. 2000. - 19. - P.l73-193.

48. Kodandapani K.L., McGrath E.J. A wirelist compare program for verifying VLSIlayouts // IEEE Design and Test of Computers. 1986. - 3(3). - P.46-51.

49. Lenstra A., Lenstra H. The Development of the Number Field Sieve // Springer, Verlag. Berlin, 1993. - 23 p.

50. Levin L. Universal search problems // Problems of Information Transmission. -1984. -9(3). -P.265-266.

51. Lieberherr K.J., Specker E. Complexity of partial satisfaction // Journal of ACM. 1981.-28. -P.411-421.

52. Minton S., Johnston M.D., Philips A.B., Laird P. A heuristic repair method for constraint satisfaction and scheduling problems // Artificial Intelligence. 1992. - 58. -P. 161-205.

53. Ouyang Ming How Good Are Branching Rules in DPLL? // Discrete Applied Mathematics. 1998. - 89(1-3). - P.281-286.

54. Pardalos P.M., Rosen J.B. Constrained Global Optimization: Algorithms and Applications // Springer, Verlag. N.Y., 1987. - 23 p.

55. Petrie C. Revised dependency-directed backtracking for default reasoning // In Proceedings of АААГ87. 1987. - P. 167-172.

56. Prestwich S., Lynce I. Refutation by Randomized General Resolution // Twenty-Second Conference on Artificial Intelligence (AAAI), Nectar Track. 2007. - 217 p.

57. Purdom P.W., Haven G.N. Backtracking and probing // Technical Report No. 387, Dept. of Computer Science, Indiana University. 1993. - 17 p.

58. Robinson J.A. A machine-oriented logic based on the resolution principle // Journal of the ACM. 1965. - 12. - 111 p.

59. Saab Y.C., Rao V.B. Combinatorial optimization by stochastic evolution // IEEE Transactions on CAD. 1991. - CAD-10(4), Apr. - P.525-535.

60. Schwartzschild B.M. Statistical mechanics algorithm for Monte Carlooptimization // Physics Today. 1982. - 35. - P. 17-19.

61. Selman В., Levesque H., Mitchell D. A new method for solving hard satisfiability problems // In Proceedings of AAAI'92, Jul. 1992. P.440-446.

62. Shapiro, S. S. and Wilk, M. B. (1965). "An analysis of variance test for normality (complete samples)", Biometrika, 52, 3 and 4, pages 591-611.

63. Singer J., Gent I., Smaill A. Backbone Fragility and the Local Search Cost Peak // Journal of Artificial Intelligence Research. 2000. - 12. - P.235-270.

64. Sosic R., Gu J. Efficient local search with conflict minimization // IEEE Trans, on Knowledge and Data Engineering. 1994. 6(5). - P.661-668.

65. Sosic R., Gu J. Fast search algorithms for the n-queens problem // IEEE Trans, on Systems, Man, and Cybernetics. 1991. - SMC-21(6), Nov./Dec. - P. 1572-1576.

66. Stallman R., Sussman G.J. Forward reasoning and dependency directed backtracking. Artificial Intelligence. 1977. - Vol.9(2). - P.135-196.

67. Torn A., Zilinskas A. Global Optimization // Springer,Verlag. N.Y., 1989. - 20 p.

68. Tseitin G.S. On the Complexity of Derivations in Prepositional Calculus // Structures in Constructive Mathematics and Mathematical Logic, A.O. Slisenko, ed. -1968. Part II. - P. 115-125.

69. Urquhart A. Hard examples for resolution // Journal of the Association for Computing Machinery. 1987. - Vol.34. - P. 215-225.75. \vww.maplesoft.com/support/help/view.aspx?path=Statistics/ShapiroWilkWTest