Математические основы криптографии

Вспомним какие бывают числа (:
Link: https://ru.wikipedia.org/wiki/Число

Что для нас важно?
Главным образом в криптографии используются НАТУРАЛЬНЫЕ числа.
Мы не работаем с дробными, иррациональными и комплексными числами.

Что еще для нас важно?
В криптографии как правило используется не бесконечное множество натуральных чисел, а вполне себе конечное.
О чем речь? Об алгебраических структурах.
Алгебраическая структура – некоторое множество элементов (не обязательно чисел) с определенных на ней операциях алгебры.
То есть их бывает много? Как правило 9.
Чтобы понять в чем их отличие нужно разобрать некоторые алгебраические свойства.

Алгебраические
свойства

Какие алгебраические свойства у операции бывают?
1) Конечно же + (известно со школы – от перестановки слагаемых сумма не меняется). 3+2 = 2+3. Еще?
2) Произведение. Еее, вы знали. 3*2 = 2*3. Может что-то из дискретной математики?
3) Молодец! Конъюнкция и дизъюнкция. А из теории множеств?
4) Объединение, пересечение и симметрическая разность. Супер!

Ок, это было просто, а какие тогда не коммутативны?
2) Матрицы, матрицы... Ага. Перемножение матриц!

Какие они бывают?

Вроде разобрались. У нас есть некоторые операции и свойства этих операций. А еще мы будем работать с натуральными числами.
Все супер, переходим к алгебраическим структурам.

Алгебраические
структуры

К основным алгебраическим структурам относятся:
Алгебраические структуры с одной бинарной операцией
Группоид
Полугруппа
Моноид
Группа
Алгебраические структуры с двумя бинарными операциями
Кольцо
Кольцо с единицей
Коммутативное кольцо
Тело
Поле

Так так так стоп! Ничего не понятно, что за нейтральный элемент, что за обратный элемент и нужны же примеры!
Ок, справедливо. Давайте разберёмся.

Нейтральный элемент
Ничего сложного, правда? Да и вы и сами сможете назвать нейтральный элемент множества натуральных чисел по сложению и умножению.
А по сложению?

Обратный элемент
Что будет обратным элементов для 4 по умножению для множества рациональных чисел (те, что с дробями)
Что будет обратным элементом для 4 по сложению для множества рациональных чисел (те, что с дробями)

Поле
Группа с четырьмя операциями, имеющие свойства, близкие к свойствам четырех основных операций с числами (сложения, умножения, вычитания, деления)
- Выполняются коммутативность, ассоциативность и дистрибутивность для сложения и умножения
Имеется нейтральный и обратный элемент по сложению и по умножению
Поле Галуа (конечное поле)
Поле, количество элементов в котором не бесконечно.

Математические операции
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61….
Факторизация числа
Представление числа в виде произведения простых сомножителей

Функция Эйлера