Презентация на тему: Математические основы шифрования

Математические основы шифрования
Разделы
Алгоритм Евклида
Алгоритм Евклида(частный пример)
Алгоритм Евклида(общий случай)
Алгоритм Евклида(общий случай)
Расширенный алгоритм Евклида
Расширенный алгоритм Евклида ( частный случай )
Расширенный алгоритм Евклида ( частный случай )
Проверка связи
Китайская теорема об остатках
Китайская теорема об остатках
Китайская теорема об остатках(пример)
Китайская теорема об остатках(пример)
Решето Эратосфена
Решето Эратосфена
Тест Ферма
Тест Ферма
Тест Ферма
Тест Ферма
Тест Миллера - Рабина
Знать
Уметь
Расширенный алгоритм Евклида ( частный случай )
1/24
Средняя оценка: 4.8/5 (всего оценок: 88)
Код скопирован в буфер обмена
Скачать (295 Кб)
1

Первый слайд презентации: Математические основы шифрования

Изображение слайда
2

Слайд 2: Разделы

Арифметика остатков Алгоритм Евклида Китайская теорема об остатках Тест Ферма Решето Эратосфена Вероятность Теорема Байеса Парадокс Дней Рождений

Изображение слайда
3

Слайд 3: Алгоритм Евклида

Алгоритм описанный Евклидом в книге «Начала» Используется для нахождения НОД двух чисел, для Евклида важно было то, что с использованием этого алгоритма можно было находить отношения между отрезками По сути основан на последовательном взаимном вычитании двух величин

Изображение слайда
4

Слайд 4: Алгоритм Евклида(частный пример)

Найдём НОД( 585, 135 ) 585 mod 135 = 45 135 mod 45 = 0 НОД(585,135)=45 Найдём НОД(1877, 1032) 1877 mod 1032 = 845 1032 mod 845 = 187 845 mod 187 = 97 187 mod 97 = 90 97 mod 90 = 7 90 mod 7 = 6 7 mod 6 = 1 6 mod 1=0 НОД(1877, 1032)=1

Изображение слайда
5

Слайд 5: Алгоритм Евклида(общий случай)

Изображение слайда
6

Слайд 6: Алгоритм Евклида(общий случай)

Найдём НОД(1877, 1032) 1877 = 1032 *1 + 845 1032 = 845 * 1 + 187 845 = 187 * 4 + 97 187 = 97 * 1 + 90 97 = 90 *1 + 7 90 = 7 * 12 + 6 7 = 6 * 1 + 1 6 = 1*6 + 0 НОД(1877, 1032)=1

Изображение слайда
7

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

Позволяет найти НОД( a,b ) и такие числа x и y что В частном случае, когда НОД( a,b )=1 этот алгоритм позволяет найти обратный к a элемент по модулю b В случае простого модуля N, в кольце Z/NZ каждый ненулевой элемент обратим и существует только одно решение уравнения

Изображение слайда
8

Слайд 8: Расширенный алгоритм Евклида ( частный случай )

Изображение слайда
9

Слайд 9: Расширенный алгоритм Евклида ( частный случай )

Изображение слайда
10

Слайд 10: Проверка связи

1 2 3 4 5 19* x=1(mod 2423 ) 48*x=1(mod 2351 ) 80*x=1(mod 2393 ) 5*x=1(mod 2879 ) 97*x=1(mod 2801 ) Найти обратный X к указанному по данному модулю

Изображение слайда
11

Слайд 11: Китайская теорема об остатках

В общем случае, если разложение числа n на простые сомножители представляет собой p 1 * p 2 *...* p t, то система уравнений x = a i (mod p i ), где i = 1, 2,..., t имеет единственное решение, x, меньшее n. Другими словами, число (меньшее, чем произведение нескольких простых чисел) однозначно определяется своими остатками от деления на эти простые числа.

Изображение слайда
12

Слайд 12: Китайская теорема об остатках

Система уравнений Имеет только одно решение Где

Изображение слайда
13

Слайд 13: Китайская теорема об остатках(пример)

Система уравнений

Изображение слайда
14

Слайд 14: Китайская теорема об остатках(пример)

Решить систему уравнений

Изображение слайда
15

Слайд 15: Решето Эратосфена

Алгоритм нахождения всех простых чисел от 2 до заданного Составляется список чисел от 2 до n Первое число принимается за p Двигаясь по списку шагами по p вычёркивают соответствующие числа После достижения конца списка, полагают p, равным первому не вычеркнутому элементу и возвращаются к предыдущему шагу

Изображение слайда
16

Слайд 16: Решето Эратосфена

Изображение слайда
17

Слайд 17: Тест Ферма

Вероятностный тест на простоту основанный на малой теореме ферма Вероятность того, что число прошедшее тест ферма простое более 0,5 Тест ферма может убедить нас в том, что число составное, но не может доказать его простоту

Изображение слайда
18

Слайд 18: Тест Ферма

Порядок мультипликативной группы G = Z/NZ равен, для любого члена a<N данной группы будет выполнено равенство Если равенство не верно, число N бесспорно является составным, если равенство верно, число может оказаться простым, например

Изображение слайда
19

Слайд 19: Тест Ферма

Про числа вроде 341 говорят, что они псевдопростые (в смысле Ферма) по основанию 2, следует отметить, что при выборе иного основания тест может дать отрицательный результат, например, если взять в качестве основания 5, то при возведении в 340 степень, получится остаток от деления на 341 отличный от 1. Иногда основание называют свидетелем делимости

Изображение слайда
20

Слайд 20: Тест Ферма

C уществуют составные числа, относительно которых тест Ферма выдаст ответ правдоподобно простое, для всех взаимно простых с N оснований а. Такие числа называются числами Кармайкла.

Изображение слайда
21

Слайд 21: Тест Миллера - Рабина

Пусть — нечётное число большее 1. Число однозначно представляется в виде, где t нечётно. Целое число, 1<a<m, называется свидетелем простоты числа, если выполняется одно из условий: Или существует целое число,, такое, что Теорема Рабина утверждает, что составное нечётное число m имеет не более φ( m ) / 4 различных свидетелей простоты.

Изображение слайда
22

Слайд 22: Знать

Алгоритм Евклида Расширенный алгоритм Евклида Формулировку китайской теоремы об остатках Что такое тест Ферма Что такое псевдопростые числа по определённому основанию Что такое числа Кармайкла Что такое решето Эратосфена

Изображение слайда
23

Слайд 23: Уметь

Находить НОД( a,b ) Находить элемент a обратный к элементу Z/NZ, такой, что 0 >a<N Решать системы типа Проводить тест Ферма

Изображение слайда
24

Последний слайд презентации: Математические основы шифрования: Расширенный алгоритм Евклида ( частный случай )

Изображение слайда