КНФ представления для задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой

• Автор: Дулькейт, Владимир Игоревич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Омск
• Количество страниц: 131 с.

ОГЛАВЛЕНИЕ

Введение

ГЛАВА 1. Обзор

1.1 Логический криптоанализ

1.2 Методы теории чисел

1.2.1 Задача факторизации

1.2.2 Задача дискретного логарифмирования

ф 1.2.3 Задача логарифмирования на эллиптической кривой

ГЛАВА 2. Генерация эквивалентных КНФ

2.1 КНФ представления для задачи факторизации
2.1.1 КНФ представление операции умножения двух чисел
2.1.2 Обеспечение консервативности преобразований
2.1.3 Сведение задачи факторизации к задаче «ВЫПОЛНИМОСТЬ»
2.1.4 Эквивалентные КНФ представления операции умножения двух
чисел
2.1.5 Сведение задачи факторизации к набору эквивалентных задач
# «ВЫПОЛНИМОСТЬ»
2.1.6 3-КНФ представление операции умножения двух чисел
2.2 КНФ представление задачи дискретного логарифмирования
2.2.1 Кодирование базовых операций
2.2.2 Сведение задачи дискретного логарифмирования к задаче «ВЫПОЛНИМОСТЬ»
2.3 КНФ представление задачи логарифмирования на эллиптической
кривой

2.3.1 Базовые операции
2.3.2 Сложение точек эллиптической группы
2.3.3 Корректировка результатов суммирования точек кривой с учетом их возможного равенства точке
2.3.4 Сведение задачи логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ»
2.4 Проекция вещественного вектора приближений на пространство булевых переменных
2.5 КНФ представления для отношения неделимости на малые простые числа
ГЛАВА 3. Вычислительные эксперименты
3.1 Генерация КНФ для задач практически значимых размерностей
3.2 Решение полученных экземпляров задачи «ВЫПОЛНИМОСТЬ»
3.3 Определение наиболее вероятных значений битов сомножителей
для задачи факторизации
3.4 Исследование стойкости рассматриваемых задач к восстановлению полного ключа по его известным фрагментам
Заключение
Список таблиц
Литература

ВВЕДЕНИЕ
Задача поиска выполнимого набора логической формулы — одна из наиболее важных задач математической логики и теории вычислений. Она имеет фундаментальное значение для решения прикладных задач в области искусственного интеллекта, проектирования компьютерных систем, роботостроения, криптографии и других. В настоящее время наблюдается бурное развитие в области сведения задач из различных областей прикладной математики к задаче «ВЫПОЛНИМОСТЬ». В России этому посвящены работы Семенова A.A., Буранова Е.В., и др. [51, 67], за рубежом известны работы Kautz Н. Selman В. [19, 41]. Одна из причин этого - возможность решать задачи, возникающие в самых различных областях, единым алгоритмом решения задачи «ВЫПОЛНИМОСТЬ».
Но, несмотря на столь высокое внимание к этой проблеме, имеется еще достаточно большое количество задач, для которых вопрос их сведения к задаче «ВЫПОЛНИМОСТЬ»до сих пор остается открытым. И это при том, что еще в 1971 году Кук С. в своей работе [2] показал принципиальную возможность такого сведения.
Цель работы.
Целью данной диссертационной работы является построение и исследование алгоритмов сведения задач 2-факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к задаче «ВЫПОЛНИМОСТЬ».

Шаг 2. Избавляемся от операции сложения по модулю два в левой части (2.2) (используется лемма 2.1.2). После осуществления этого шага общий вид полученной формулы может быть представлен следующим образом:
лчулаИул*)).
где греческие буквы обозначают один литерал либо его отрицание. Таким образом, формула является произведением скобок с логическими суммами, в которых часть литералов стоят свободно (обозначены как /часть литералов образуют произведения (V /Р!?')> и> наконец, часть литералов образуют произведения с навешенным отрицанием
(УЛтф
Шаг 3. До тех пор, пока формула не является КНФ, т.е. в дизъюнктах присутствуют произведения, выполнять следующие действия:
Шаг 3.1. Для литералов, образующих произведения (V Л Д/) применяется лемма 2.1.3, в результате устраняются произведения литералов внутри скобок.
Шаг 3.2. Для литералов образующих произведения с отрицанием (V Л 7применяется правил о де-Моргана, в результате конъюнкция переписывается в виде дизъюнкции.
Конец Алгоритма 2.1.1.
Теорема 2.1.1. Алгоритм 2.1.1 строит конечное, консервативное (т.е. не вносящее новых паразитных решений) представление в виде КНФ операции сложения по модулю 2.
Доказательство. Покажем, что описываемое преобразование обладает свойством консервативности, для этого будем рассматривать соблюдение этого