Система Orphus

Построение, операции, свойства, использование в криптографии

Построение

Построение поля Голуа \mathbb{GF}(p^n)

  1. Построить простое поле \mathbb{GF}(p)=\{0,1,\ldots,p-1\}, если n=1, то поле построено
  2. Выбрать неприводимый многочлен степени n над полем \mathbb{Z}_p
  3. Строить \mathbb{GF}(p^n) как факторкольцо \mathbb{K}=\mathbb{Z}_p[x]/\langle f(x)\rangle - поле построено.

Элементами поля \mathbb{K} являются все многочлены степени меньшей n с коэффициентами из \mathbb{Z}_p. Арифметические операции (сложение и умножение) проводятся по модулю многочлена f(x), то есть, результат соответствующей операции — это остаток от деления на f(x) с приведением коэффициентов по модулю p.

Свойства

  • Характеристика конечного поля является простым числом.
  • Число элементов любого конечного поля есть его характеристика в натуральной степени: |\mathbb{F}_q|=q=p^n.
  • Для каждого простого числа p и натурального n существует конечное поле из q=p^n элементов, единственное с точностью до изоморфизма. Это поле изоморфно полю разложения многочлена x^q-x\in\mathbb{F}_p[x].
  • Мультипликативная группа  \mathbb{F}^*_q конечного поля \mathbb{F}_q является циклической группой порядка q-1.
    • В частности, в конечном поле всегда существует примитивный элемент \alpha, порядок которого равен q-1, то есть \alpha^{q-1}=1 и \alpha^i \neq 1 для 0<i<q-1.
    • Любой ненулевой элемент \beta является некоторой степенью примитивного элемента:
      \beta = \alpha^i,\quad i \in \{0,1,...,q-2\}.
  • Поле \mathbb{F}_{p^n} содержит в себе в качестве подполя \mathbb{F}_{p^k} тогда и только тогда, когда k является делителем n.

Система Orphus

Комментарии