Введение в современную криптографию



Pdf көрінісі
бет233/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   229   230   231   232   233   234   235   236   ...   249
Криптография Катц

ТЕОРЕМА A.20 Пусть Fq – конечное поле характеристики p. Тогда для всех 
 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.


319


Достарыңызбен бөлісу:
1   ...   229   230   231   232   233   234   235   236   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет