НОУ ІНТУІТ, Лекція, Алгебраїчні структури

Поле, позначене " style="display: inline; "> - комутативне кільце, в якому друга операція задовольняє всім п'яти властивостям, визначеним для першої операції, за винятком того, що нейтральний елемент першої операції (іноді званий нульовий елемент) не має інверсії. Малюнок 5.5 показує поле.

множення

Додаткове зауваження

Поле - структура, яка підтримує дві пари операцій, що використовуються в математиці: складання/віднімання та множення/розподіл. Є один виняток: не дозволено поділ на нуль.

Кінцеві поля

Хоча загальне визначення стосується полів нескінченного порядку, криптографії використовуються екстенсивно тільки кінцеві поля.Кінцеве поле- поле з кінцевим числом елементів - є дуже важливою структурою криптографії. Галуа показав, що поля, щоб бути кінцевими, повинні мати число елементів p n , де p - просте, а n - позитивне ціле число. Кінцеві поля зазвичай називають полями Галуа і позначають як GF(p n ).

Коли n = 1 ми маємо поле GF (p) . Це поле може бути безліччю Zp, (0, 1, …p–1) з двома арифметичними операціями (складання та множення). Будь-який елемент у цій множині має адитивну інверсію і елементи, відмінні від нуля, мають мультиплікативну інверсію (мультиплікативна інверсія для 0 відсутня).

Є кілька моментів, які слід зазначити у визначенні цього поля. Перший: множина має тільки два елементи, які є двійковими цифрами або бітами (0 і 1). Другий: операція додавання - фактично ВИКЛЮЧАЮЧЕ АБО (XOR), операція, яку ми використовуємо з двома двійковими цифрами. Третій: операція множення - AND, операція, яку ми використовуємо з двома двійковими цифрами. Четвертий: додавання таоперації віднімання - ті самі (операція XOR). П'ятий: множення та операції поділу — ті самі (ОПЕРАЦІЯ AND).

Ми можемо визначити GF(5) на множині Z5 (5 просте) з операторами додавання та множення, показаними на рис. 5.7.

Хоча ми можемо використовувати розширений алгоритм Евкліда, щоб знайти мультиплікативні інверсії елементів у GF(5) , простіше скласти таблицю множення та знаходити кожну пару, добуток якої дорівнює 1 . Це (1, 1), (2, 3), (3, 2) та (4, 4) . Зауважимо, що ми можемо на цій множині застосувати віднімання та множення/поділ (за винятком забороненого поділу на 0).

Поля GF(p у ступені n)

Крім полів GF(p) у криптографії ми також цікавимося полями GF(pn) . Проте безліч Z , Zn , Zn* і Zp , які ми використовували досі з операціями складання та множення, не можуть задовольнити вимоги поля. Тому мають бути визначені деякі нові множини та деякі нові операції на цих множинах. У наступній лекції ми розглядаємо дуже корисне у криптографії поле GF(2n).

Підсумки розглянутих структур

Вивчення трьох структур алгебри дозволяє нам використовувати множини, в яких можуть застосовуватися операції, подібні до складання/віднімання і множення/розподілу. Ми маємо розрізняти ці три структури. Перша структура - група, що підтримує одну пару пов'язаних операцій. Друга структура - кільце, підтримує одну пару пов'язаних операцій та одну одиночну операцію. Третя структура – ​​поле, що підтримує дві пари операцій. Таблиця 5.3 допоможе нам побачити цю різницю.