Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Сведения из теории чисел
Содержание
- 1. Сведения из теории чисел
- 2. Сведения из теории чиселФункция ЭйлераЛегко вычисляется для
- 3. Теорема ЭйлераДля взаимнопростых a и n справедливо:a φ(n) =1 mod n
- 4. Теорема Ферма (малая)Для взаимнопростых a и p и простого p справедливо :a p-1 =1 mod p
- 5. Особенность шифрования в системах с открытым ключомШифрование
- 6. Сложность операций в модульной арифметикеСледующие операции простые:Операция
- 7. Сложность операций в модульной арифметикеВозведение в степень:Тривиальный
- 8. Возведение в степеньБолее эффективный алгоритм использует тот факт, что:a16=a8*a8;a8=a4*a4;a4=a2*a2;a2=a*a – т.е. вместо 16 умножений – 4.
- 9. Возведение в степеньколичество операций ~ 2*log x
- 10. Дискретный логарифмlogay=x mod n;Т.е. Такой х:y=ax mod nДискретный логарифм существует не всегда:log37mod 17;
- 11. Дискретный логарифмОперация дискретного логарифмирования – сложнаяНаилучший алгоритм требует:
- 12. Разложение на множителиФакторизацияОсновная теорема арифметики:Такое представление всегда
- 13. Вычисление наибольшего общего делителя (НОД или gcd)НОД(x,y)=?Тривиальный
- 14. НОДАлгоритм Эвклида (полиномиальный)Пусть y>x, делим y на
- 15. НОДЕсли bk=0, то bk-1 – НОДЕсли bk-1
- 16. Нахождение обратного элемента по модулю.Дано a, найти
- 17. Деление4/2=4*2-1=4*3=2 mod 53/2=3*2-1=3*3=4 mod 5
- 18. Нахождение обратного элемента по модулюРешение существует не
- 19. Нахождение обратного элемента по модулюНахождение обратного элемента – простая задача, основанная на алгоритме Евклида…
- 20. Нахождение простых чиселДля ряда криптографических приложений необходимо
- 21. Нахождение простых чиселДля нахождения простых чисел задаются
- 22. Тест на простотуНе существует эффективных (простых) методов
- 23. Тест ФермаОснован на малой т. Фермаbin-1=1 mod
- 24. Тест ФермаВыбирается k – число тестовСлучайно выбирают b1 b2 … bk ; bi
- 25. Тест ФермаЕсли все тесты пройдены, число принимается
- 26. Задача об укладке ранцаДано:ai – целые положительныеn – целое положительноеНайти bi - двоичные
- 27. Криптосистемы, основанные на сложных задачахRSA (дискретное логарифмирование,
- 28. RSAФормирование ключа Шифрование E=MKmod NРасшифрование M=Ekmod N
- 29. Скачать презентанцию
Сведения из теории чиселФункция ЭйлераЛегко вычисляется для простого числа p:φ(p) = p-1Для взаимно простых аргументов x и y функция Эйлера обладает свойством мультипликативности:φ(xy)=φ(x) φ(y)Пример: φ(35)=φ(5) φ(7)=4*6=24
Слайды и текст этой презентации
Слайд 2Сведения из теории чисел
Функция Эйлера
Легко вычисляется для простого числа p:
φ(p)
= p-1
Для взаимно простых аргументов x и y функция Эйлера
обладает свойством мультипликативности:φ(xy)=φ(x) φ(y)
Пример: φ(35)=φ(5) φ(7)=4*6=24
Слайд 5Особенность шифрования в системах с открытым ключом
Шифрование в системах с
открытым ключом – вычисление некоторого математического выражения с большими аргументами.
Вычисления
производятсяв целых числах;
по модулю некоторого числа “n”;
без округлений;
без приближенных методов.
Слайд 6Сложность операций в модульной арифметике
Следующие операции простые:
Операция сложения (вместо вычитания
используют сложение – см. введение в модульную арифметику)
Операция умножения (вместо
деления используют умножение на обратное – см. далее)
Слайд 7Сложность операций в модульной арифметике
Возведение в степень:
Тривиальный метод:
ax=a*a*a* … *
a mod n
Этот метод малоэффективен, а в языках программирования реализованы
приближенные методы возведения в степеньx
Слайд 8Возведение в степень
Более эффективный алгоритм использует тот факт, что:
a16=a8*a8;
a8=a4*a4;
a4=a2*a2;
a2=a*a –
т.е. вместо 16 умножений – 4.
Слайд 9Возведение в степень
количество операций ~ 2*log x – определяется количеством
ненулевых разрядов в двоичном представлении показателя.
двоичное представление x=x0+2x1+…+2k-1xk-1
Слайд 10Дискретный логарифм
logay=x mod n;
Т.е. Такой х:
y=ax mod n
Дискретный логарифм существует
не всегда:
log37mod 17;
Слайд 11Дискретный логарифм
Операция дискретного логарифмирования – сложная
Наилучший алгоритм требует:
Слайд 12Разложение на множители
Факторизация
Основная теорема арифметики:
Такое представление всегда существует и оно
единственно.
pi – простые, si >0, целые.
Факторизация – сложная задача –
сравнима с дискретным логарифмированием.
Слайд 13Вычисление наибольшего общего делителя (НОД или gcd)
НОД(x,y)=?
Тривиальный метод – разложить
x и y на множители и найти в двух группах
максимальный одинаковый.Такой метод будет вычислительно сложным, так как факторизация – сложная операция
Слайд 14НОД
Алгоритм Эвклида (полиномиальный)
Пусть y>x, делим y на x находим число
целых a1 и остаток b1:
y =a1*x +b1
x
=a2*b1 +b2b1 =a3*b2 +b3
...
bk-2=ak*bk-1+bk
Слайд 15НОД
Если bk=0, то
bk-1 – НОД
Если bk-1 = 1 то
у чисел «нет» наибольшего общего делителя и их называют взаимно
простыми.
Слайд 16Нахождение обратного элемента по модулю.
Дано a, найти такое a-1:
a* a-1
= 1 mod n
Пример:
a=2
Модуль n =5
a-1 = 3
2*0=0 mod 5
2*1=2
mod 52*2=4 mod 5
2*3=1 mod 5
2*4=3 mod 5
Слайд 18Нахождение обратного элемента по модулю
Решение существует не всегда, только если
НОД(a,n)=1, т.е. Если n – простое, то для любого а
будет существовать обратное.Если обратного не существует, то элемент называют делителем нуля.
2*?=1mod6,
2*1=2mod6
2*2=4mod6
2*3=0mod6
2*4=2mod6
2*5=4mod6
Слайд 19Нахождение обратного элемента по модулю
Нахождение обратного элемента – простая задача,
основанная на алгоритме Евклида
…
Слайд 20Нахождение простых чисел
Для ряда криптографических приложений необходимо уметь находить простые
числа.
Известно, что простых чисел бесконечно много.
Известно, что количество простых чисел
меньших n ~ n/log(n) (при больших n), т.е. их достаточно много.
(Количество простых чисел между n-q и n ~q/ln(n) )Пусть n=10127 q=104 простых чисел в диапазоне ~ 34.
Не существует вычислительного алгоритма, который бы выдавал в качестве результата список простых числе в заданном диапазоне.
Слайд 21Нахождение простых чисел
Для нахождения простых чисел задаются разрядностью числа, а
затем определенным образом перебирают числа, проверяя (тестируя) каждое на простоту,
т.е. простое оно или составное.
Слайд 22Тест на простоту
Не существует эффективных (простых) методов определения составное число
или простое *.
Для проверки используют вероятностные тесты, которые с некоторой
вероятностью могут принять составное число за целое.
Слайд 23Тест Ферма
Основан на малой т. Ферма
bin-1=1 mod n (n –
простое и НОД(n; bi)=1)
Т.е., если n – простое, то для
любых bi должно выполняться равенство.
Слайд 24Тест Ферма
Выбирается k – число тестов
Случайно выбирают b1 b2 …
bk ; bi
i, если хоть раз не выполнено n –составное.Проверяют bin-1=1 mod n для всех i, если хоть раз не выполнено n –составное.
Слайд 25Тест Ферма
Если все тесты пройдены, число принимается за простое.
Вероятность принять
составное число за простое (½)k. k-число тестов
k=20 pош~10-6
Недостаток теста Ферма
– пропускает с большой вероятностью ставные числа специального вида (числа Кармайкла).На практике используют несколько более сложный тест – лишенный данного недостатка.
Слайд 26Задача об укладке ранца
Дано:
ai – целые положительные
n – целое положительное
Найти
bi - двоичные
Слайд 27Криптосистемы, основанные на сложных задачах
RSA (дискретное логарифмирование, факторизация)
Эль-Гамаля (факторизация )
Мак-Элиса
(задача декодирования произвольного линейного кода)
Меркля (задача об укладке ранца)
ECC (операции
на эллиптических кривых) 
