+
Действующая цена700 499 руб.
Товаров:
На сумму:

Электронная библиотека диссертаций

Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО

Расширенный поиск

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

  • Автор:

    Дулькейт, Владимир Игоревич

  • Шифр специальности:

    01.01.09

  • Научная степень:

    Кандидатская

  • Год защиты:

    2010

  • Место защиты:

    Омск

  • Количество страниц:

    131 с.

  • Стоимость:

    700 р.

    499 руб.

до окончания действия скидки
00
00
00
00
+
Наш сайт выгодно отличается тем что при покупке, кроме PDF версии Вы в подарок получаете работу преобразованную в WORD - документ и это предоставляет качественно другие возможности при работе с документом
Страницы оглавления работы


ОГЛАВЛЕНИЕ

Введение
ГЛАВА 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.
Доказательство. Покажем, что описываемое преобразование обладает свойством консервативности, для этого будем рассматривать соблюдение этого

Рекомендуемые диссертации данного раздела

Время генерации: 0.180, запросов: 967