Презентация на тему Новый подход к решению систем уравнений в задачах дискретного логарифмирования

Презентация на тему Презентация на тему Новый подход к решению систем уравнений в задачах дискретного логарифмирования, предмет презентации: Разное. Этот материал содержит 37 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Новый подход к решению систем уравнений в задачах дискретного логарифмированияВыполнила: Савельева
Текст слайда:

Новый подход к решению систем уравнений в задачах дискретного логарифмирования

Выполнила: Савельева А.А.
Научный руководитель: проф., к.т.н. Авдошин С.М.


Слайд 2
Криптографические системы, основанные на сложности дискретного логарифмированияСхема открытого распределения ключей Диффи-ХеллманаСхема ЭЦП Эль-ГамаляГОСТ Р34.10-2001(Россия)ANSI X9.62/63-2001 (США)
Текст слайда:

Криптографические системы, основанные на сложности дискретного логарифмирования

Схема открытого распределения ключей Диффи-Хеллмана
Схема ЭЦП Эль-Гамаля
ГОСТ Р34.10-2001(Россия)
ANSI X9.62/63-2001 (США)


Слайд 3
Алгоритмы дискретного логарифмирования в конечных полях, использующие факторную базуАлгоритм АдлеманаАлгоритм COSIndex-calculusРешето
Текст слайда:

Алгоритмы дискретного логарифмирования в конечных полях, использующие факторную базу


Алгоритм Адлемана
Алгоритм COS
Index-calculus
Решето числового поля

Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: МЦНМО, 2004 .


Слайд 4
Постановка задачиРешить систему n линейных уравнений c m неизвестными:Операции сложения и
Текст слайда:

Постановка задачи

Решить систему n линейных уравнений c m неизвестными:

Операции сложения и умножения определены по правилам:

(здесь p - некоторое целое положительное число)


Слайд 5
Сведение задачи к :решению семейства систем над полями Галуарешению системы над
Текст слайда:


Сведение задачи к :

решению семейства систем над полями Галуа
решению системы над кольцом целых чисел
решению уравнения над кольцом матриц

Анализ методов решения систем линейных уравнений в кольцах вычетов


Слайд 6
Анализ методов решения систем линейных уравнений в кольцах вычетовСведение задачи к
Текст слайда:

Анализ методов решения систем линейных уравнений в кольцах вычетов


Сведение задачи к :

решению семейства систем над простыми полями
решению системы над кольцом целых чисел
решению уравнения над кольцом матриц


Слайд 7
Метод сведения к решению системы над простыми полями: примерВасиленко О.Н. Теоретико-числовые
Текст слайда:

Метод сведения к решению системы над простыми полями: пример


Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: Институт проблем информационной безопасности МГУ, МЦНМО, 2004 .


Слайд 8
Метод сведения к решению системы над простыми полями: пример (продолжение)12
Текст слайда:

Метод сведения к решению системы над простыми полями: пример (продолжение)

1

2


Слайд 9
Метод сведения к решению системы над простыми полями: пример (продолжение)123
Текст слайда:

Метод сведения к решению системы над простыми полями: пример (продолжение)

1

2

3


Слайд 10
Метод сведения к решению системы над простыми полями: пример (продолжение)321
Текст слайда:

Метод сведения к решению системы над простыми полями: пример (продолжение)

3

2

1


Слайд 11
Метод сведения к решению системы над простыми полями: пример (продолжение)По Китайской теореме об остатках:
Текст слайда:

Метод сведения к решению системы над простыми полями: пример (продолжение)

По Китайской теореме об остатках:


Слайд 12
Недостатки метода сведения к решению семейства систем над простыми полямиРешение не
Текст слайда:

Недостатки метода сведения к решению семейства систем над простыми полями



Решение не одной, а нескольких систем
Факторизация числа p: открытая проблема современной теории чисел (не существует алгоритма с полиномиальной сложностью)


Слайд 13
Анализ методов решения систем линейных уравнений в кольцах вычетовСведение задачи к
Текст слайда:

Анализ методов решения систем линейных уравнений в кольцах вычетов


Сведение задачи к :

решению семейства систем над простыми полями
решению системы над кольцом целых чисел
решению уравнения над кольцом матриц


Слайд 14
Метод сведения к решению системы над кольцом целых чисел (1): примерСведение:Общее
Текст слайда:

Метод сведения к решению системы над кольцом целых чисел (1): пример

Сведение:


Общее решение:




экспоненциальный рост коэффициентов

Ноден П., Китте К. Алгебраическая алгоритмика. Пер. с франц. - М.: Мир, 1999.


Слайд 15
Метод сведения к решению системы над кольцом целых чисел (2): модификацииСпособы
Текст слайда:

Метод сведения к решению системы над кольцом целых чисел (2): модификации

Способы избежать экспоненциального роста коэффициентов:

Использование диагональной формы Смита
Модификация метода Гаусса




Недостаток:
Асимптотическая временная и емкостная сложность значительно больше сложности метода Жордана решения систем в полях Галуа

Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. - Нижегородский Государственный Университет им. Н.И. Лобачевского. – 2002.


Полиномиальный рост коэффициентов


Слайд 16
Анализ методов решения систем линейных уравнений в кольцах вычетовСведение задачи к
Текст слайда:

Анализ методов решения систем линейных уравнений в кольцах вычетов


Сведение задачи к :

решению семейства систем над простыми полями
решению системы над кольцом целых чисел
решению уравнения над кольцом матриц


Слайд 17
Метод сведения к уравнению над кольцом матрицAx=bx=A-1bЕлизаров В.П. Успехи мат. наук.
Текст слайда:

Метод сведения к уравнению над кольцом матриц





Ax=b


x=A-1b

Елизаров В.П. Успехи мат. наук. – 1993. Т. 48, вып. 2. с. 181-182.

Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003


Слайд 18
Предложенный методВ основе:Расширенный алгоритм ЕвклидаСхема ЖорданаПрименим для:колец вычетовполей ГалуаЭффективность:По временной и
Текст слайда:

Предложенный метод

В основе:
Расширенный алгоритм Евклида
Схема Жордана
Применим для:
колец вычетов
полей Галуа
Эффективность:
По временной и емкостной сложности эквивалентен классическим алгоритмам Жордана и Гаусса решения систем в полях Галуа


Слайд 19
Расширенный алгоритм ЕвклидаАЛГ Евклид(a,b)
Текст слайда:

Расширенный алгоритм Евклида

АЛГ Евклид(a,b)



ПОКА ЦИКЛ




К.Ц.
К.АЛГ.

Вход:
Выход: d, x, y, r, s такие, что





Слайд 20
Схема Жордана
Текст слайда:

Схема Жордана


Слайд 21
Матрицы над кольцомОпр.2 Матрица
Текст слайда:

Матрицы над кольцом

Опр.2 Матрица называется строчно эквивалентной матрице если она может быть получена из A с помощью конечной последовательности элементарных преобразований строк.

Элементарными преобразованиями строк матрицы называют:
умножение любой ее строки на обратимый элемент кольца R;
прибавление к любой ее строке другой строки, умноженной на произвольный элемент кольца R;
транспозицию строк.

Опр.1 Множество всех матриц размером m x n с элементами из кольца R будем обозначать через Rm,n


Слайд 22
Применение алгоритма Евклида к матрице
Текст слайда:

Применение алгоритма Евклида к матрице






Слайд 23
Работа алгоритмаРешение системы:Вычисление обратной матрицы:
Текст слайда:

Работа алгоритма

Решение системы:




Вычисление обратной матрицы:





Слайд 24
АлгоритмАЛГ Жордан(А, n, m, p)   ДЛЯ i=1 ДО n
Текст слайда:

Алгоритм

АЛГ Жордан(А, n, m, p)
ДЛЯ i=1 ДО n ЦИКЛ
{обнуляем эл-ты i-го столбца ниже i-й строки}
ДЛЯ j=i+1 ДО n ЦИКЛ





К.Ц. {для j}

Вход: {расширенная матрица}
Выход: А {преобразованная матрица}




Слайд 25
Алгоритм (продолжение)  ЕСЛИ  НОД(aii, p)>1  ТО выйти из
Текст слайда:

Алгоритм (продолжение)

ЕСЛИ НОД(aii, p)>1 ТО выйти из алгоритма {матрица вырождена}
ИНАЧЕ {обнуляем элементы i-го столбца выше i-й строки}



К.Е.
ВЕРНУТЬ(А)
К.АЛГ.



Слайд 26
Временная сложность алгоритмовКузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная
Текст слайда:

Временная сложность алгоритмов





Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. - Нижегородский Государственный Университет им. Н.И. Лобачевского. – 2002.

Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003
Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2.

Метод сведения к уравнению над кольцом матриц

Метод сведения к диофантовым уравнениям (с построением матрицы Смита)

Метод сведения к полям Галуа

Метод, предложенный в данной работе

Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: Институт проблем информационной безопасности МГУ, МЦНМО, 2004

Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005


Слайд 27
Временная сложность алгоритмовАвдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы
Текст слайда:

Временная сложность алгоритмов





Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005

Кузнецов М.И., Бурланков Д.Е., Чирков А.Ю., Яковлев В.А. Компьютерная алгебра: Учебник. - Нижегородский Государственный Университет им. Н.И. Лобачевского. – 2002.

Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003
Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2.

Метод сведения к уравнению над кольцом матриц

Метод сведения к диофантовым уравнениям (с построением матрицы Смита)

Метод сведения к полям Галуа

Метод, предложенный в данной работе


Слайд 28
Временная сложность алгоритмовАвдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы
Текст слайда:

Временная сложность алгоритмов





Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005

Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра (в 2-х т). Т. I - М.: Гелиос АРВ, 2003
Елизаров В.П. Успехи мат. наук.–1993.Т. 48, вып. 2.

Метод сведения к уравнению над кольцом матриц

Метод сведения к диофантовым уравнениям (с построением матрицы Смита)

Метод сведения к полям Галуа

Метод, предложенный в данной работе


Слайд 29
Временная сложность алгоритмовАвдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы
Текст слайда:

Временная сложность алгоритмов





Авдошин С.М., Савельева А.А. Свид. Об официальной регистрации программы для ЭВМ № 2005612258: «Программа решения систем линейных уравнений в кольцах вычетов». Зарегистрировано в Реестре программ для ЭВМ 02.09.2005

Метод сведения к уравнению над кольцом матриц

Метод сведения к диофантовым уравнениям (с построением матрицы Смита)

Метод сведения к полям Галуа

Метод, предложенный в данной работе


Слайд 30
Временная сложность алгоритмовМетод сведения к уравнению над кольцом матрицМетод сведения к
Текст слайда:

Временная сложность алгоритмов





Метод сведения к уравнению над кольцом матриц

Метод сведения к диофантовым уравнениям (с построением матрицы Смита)

Метод сведения к полям Галуа

Метод, предложенный в данной работе


Слайд 31
Решение систем, возникающих при дискретном логарифмировании Свойства:Большой размер (миллионы уравнений с
Текст слайда:

Решение систем, возникающих при дискретном логарифмировании

Свойства:
Большой размер (миллионы уравнений с миллионами неизвестных)
Разреженные матрицы

Поля: структурированное гауссово исключение

Кольца: модифицированный алгоритм структурированного гауссова исключения



Слайд 32
ЗаключениеРезультаты, полученные в данной работе:Проведен анализ известных методов решения систем линейных
Текст слайда:

Заключение

Результаты, полученные в данной работе:
Проведен анализ известных методов решения систем линейных уравнений над кольцом вычетов
Разработан алгоритм, эквивалентный по сложности методам Жордана и Гаусса решения систем линейных уравнений над полями Галуа
Программа, реализующая разработанный алгоритм, зарегистрирована Федеральной службой по интеллектуальной собственности, патентам и товарным знакам (Роспатент)
Результаты исследований опубликованы в журнале «Информационные технологии» (№2, 2006)


Слайд 33
Направление дальнейшей работыТеоретическое и экспериментальное исследование влияния полученного метода на временную
Текст слайда:

Направление дальнейшей работы

Теоретическое и экспериментальное исследование влияния полученного метода на временную сложность алгоритмов дискретного логарифмирования, использующие факторную базу:
Алгоритм Адлемана
Index-calculus
Алгоритм COS
Решето числового поля


Слайд 34
Кольца вычетовОперации сложения и умножения определяют кольцо вычетов по модулю p
Текст слайда:

Кольца вычетов

Операции сложения и умножения определяют кольцо вычетов по модулю p . Оно является коммутативным кольцом с единицей.

Опр.1 Делителем нуля в произвольном кольце R называется любой его элемент для которого в R существует элемент удовлетворяющий условию a ·b=0 или b ·a=0

Опр.2 Обратимым элементом в произвольном кольце R называется любой его элемент для которого в R существует обратный элемент a-1, удовлетворяющий условию a · a-1 =1 или a-1 ·a=1


Слайд 35
Обратный элементЭлемент
Текст слайда:

Обратный элемент

Элемент называется обратным к , если

Для нахождения обратного элемента нужно решить линейное диофантово уравнение:

Уравнение разрешимо относительно u и v тогда и только тогда, когда НОД(x,p)=1; в этом случае Для вычисления u и v (коэффициентов Безу) используется расширенный алгоритм Евклида.


Слайд 36
Пример решения системы в поле Галуа порядка 37
Текст слайда:

Пример решения системы в поле Галуа порядка 37




Слайд 37
Пример решения системы в кольце вычетов по модулю 36Все коэффициенты системы
Текст слайда:

Пример решения системы в кольце вычетов по модулю 36

Все коэффициенты системы являются делителями нуля, т.е. необратимы. Однако решение существует и единственно:


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика