Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА A.21
| ТЕОРЕМА A.20 Пусть Fq – конечное поле характеристики p. Тогда для всех
a ∈ Fq имеем p • a = 0. Пусть q = pr с простым числом p. Для r = 1, мы видели в примере A.18, что Fq =Fp можно взять в виде множества {0, . . . , p − 1} при сложении и умножении по модулю p. Однако мы предупреждаем, что r > 1 множество {0, . . . , q − 1} не является полем при сложении и умножении по модулю q. Например, если взять q = 32 = 9, то элемент 3 не имеет мультипликативной инверсии по модулю 9. Ко- нечные поля характеристики p можно представить, используя полиномы по Fp. Приведем пример, чтобы продемонстрировать разновидность конструкции, не обсуждая вопрос, почему конструкция работает, и не описывая общий слу- чай. Построим поле F4, работая с полиномами по F2. Зафиксируем полином r(x) = x2 +x+1 и заметим, что r(x) не имеет корней по F2, поскольку r(0) = r(1) = 1 (напомним, что мы работаем в F2, а это значит, что все операции выполняются по модулю 2). Таким же способом, каким мы можем ввести мнимое число i, которое будет корнем x2 + 1 по полю действительных чисел, мы можем ввести значение ω, которое будет корнем r(x) по F2; то есть, ω2 = −ω − 1. Затем опреде- лим, что F4 будет множеством всех полиномов степени-1 от ω по F2; то есть, F4 = {0, 1, ω, ω + 1}. Сложение в F4 будет только регулярным сложением полинома, при этом следует помнить о том, что операции с коэффициентами выполняются в F2 (то есть, по модулю 2). Умножение в F4 будет полиномиальным умножени- ем (опять же, при операциях с коэффициентами, выполняемыми по модулю 2), следующих за подстановкой ω2 = −ω − 1; это также гарантирует, что результат лежит в F4. Так, например, ω + (ω + 1) = 2ω + 1 = 1 и (ω + 1) • (ω + 1) = ω2 + 2ω + 1 = (−ω − 1) + 1 = −ω = ω. Несмотря на неочевидность, можно проверить, что это является полем; единственное трудное для проверки условие состоит в том, каждый ненулевой элемент имеет мультипликативную инверсию. Только нам нужен единственный другой результат. ТЕОРЕМА A.21 Пусть Fq будет конечным полем порядка q. Тогда комму- никативная группа Fq \ {0} по отношению к ‘•’ является циклической группой порядка q − 1. |