Шемякин лекции 2023 / Л10. Элементы теории чисел. Ред.1 - копия
.pdfЛекция Элементы теории чисел
1
Арифметика классов вычетов
•Данная арифметика используется в несимметрических криптографических системах.
•- RSA;
•- Эль Гамаль;
•- КС на эллиптических кривых.
Несимметричность означает, что ключи шифрования и расшифрования разные.
При этом:
- определение одного ключа по другому
2
является вычислительно трудной задачей.
Примеры вычислительно-сложных задач:
-разложение большого простого числа на простые множители;
-определение индекса числа в простом поле, кольце классов вычетов, в поле Галуа (логарифмирование).
Большим целым числом на настоящий момент считают такое, что в его десятичной записи не менее 200 знаков.
а ˃ 2 500
3
Кольцо классов вычетов Z(m)
•Кольцо – множество элементов с двумя операциями, например сложением и умножением.
по сложению – противоположный
элемент найдётся для любого элемента кольца Z(m)
a -a / а +(-a) = 0.
по умножению – обратный элемент для заданного не обязательно существует.
4
•Пусть Z – кольцо целых чисел.
Выберем в нём число m, зададим множество представителей классов
вычетов
{0, 1, 2, … m-1}
и обычные действия арифметики, сложение и умножение.
Результат этих действий зададим остатком от деления на m.
с= a + b ( mod m )
с= a * b ( mod m )
5
• Это и будет кольцом Z(m).
Пример 1.
m = 2 – двоичное поле, сложение по модулю 2, правильное наименование – GF(2).
Пример 2.
m = 6 – кольцо классов вычетов по модулю 6,
правильное наименование – Z(6).
2*3 = 0 ( mod 6 )
5*8 = 4 ( mod 6 ) -5 +17 = 0 ( mod 6 )
6
•Все привычные свойства – коммутативность, ассоциативность и дистрибутивность здесь сохраняются.
7
Поле классов вычетов
•Поле классов вычетов по модулю простого числа – подмножество кольца классов вычетов.
Правильное наименование GF(p). p – простое число.
по сложению – противоположный элемент найдётся для любого элемента поля
a -a / а +(-a) = 0.
по умножению – обратный элемент найдётся для любого элемента поля
a a-1 / а * a-1 = 1.
8
Пример 3.
p = 13 – поле классов вычетов по модулю 13, правильное наименование – GF(13).
5*8 = 1 ( mod 13 )
-5 +17 = 12 = -1 ( mod 13 ) 7-1 = 2 ( mod 13 ) 7*2 = 1 ( mod 13 )
9
Поле Галуа
Определим кольцо Z[x] полиномов над полем GF(2).
Это множество полиномов с коэффициентами { 0, 1 }. Полиномы можно складывать и перемножать по привычным правилам.
В этом кольце выберем неприводимый и примитивный полином f(x).
Поле Галуа – множество классов вычетов по модулю полинома f(x) над полем
GF(2).
10