Нормальная основа

В математике , особенно в алгебраической теории полей , нормальный базис — это особый вид базиса для расширений Галуа конечной степени, характеризуемый как образующий единственную орбиту для группы Галуа . Теорема о нормальном базисе утверждает, что любое конечное расширение полей Галуа имеет нормальный базис. В алгебраической теории чисел исследование более тонкого вопроса о существовании нормального целочисленного базиса является частью модулей Галуа теории .

Теорема о нормальном базисе

Позволять $F\subset K$ быть расширением Галуа с группой Галуа $G$. Классическая теорема о нормальном базисе утверждает, что существует элемент $\beta \in K$ такой, что $\{g(\beta ):g\in G\}$ образует базис K рассматриваемый как векторное пространство над F. , То есть любой элемент $\alpha \in K$ можно записать однозначно как ${\textstyle \alpha =\sum _{g\in G}a_{g}\,g(\beta )}$ для некоторых элементов $a_{g}\in F.$

Нормальный базис контрастирует с примитивным элементным базисом вида $\{1,\beta ,\beta ^{2},\ldots ,\beta ^{n-1}\}$, где $\beta \in K$ - это элемент, минимальный многочлен которого имеет степень $n=[K:F]$.

Точка зрения группового представительства

Расширение поля K / F с группой Галуа G естественно рассматривать как представление группы G над полем F , в котором каждый автоморфизм представлен самим собой. Представления G над полем F можно рассматривать как левые модули групповой алгебры F [ G ]. Любой гомоморфизм левых F [ G ]-модулей $\phi :F[G]\rightarrow K$ имеет форму $\phi (r)=r\beta$ для некоторых $\beta \in K$. С $\{1\cdot \sigma |\sigma \in G\}$ является линейным базисом F [ G ] над F , легко следует, что $\phi$ является биективным тогда и только тогда, когда $\beta$ порождает нормальный базис K над F . Таким образом, теорема о нормальном базисе сводится к утверждению, что если K / F является конечным расширением Галуа, то $K\cong F[G]$ как слева $F[G]$-модуль. В терминах представлений группы G над F это означает, что K изоморфно регулярному представлению .

Случай конечных полей

Для конечных полей это можно сформулировать следующим образом: Позволять $F=\mathrm {GF} (q)=\mathbb {F} _{q}$ обозначим поле из q элементов, где q = p ^м является первичной степенью, и пусть $K=\mathrm {GF} (q^{n})=\mathbb {F} _{q^{n}}$ обозначим его поле расширения степени n ≥ 1 . Здесь группа Галуа $G={\text{Gal}}(K/F)=\{1,\Phi ,\Phi ^{2},\ldots ,\Phi ^{n-1}\}$ с $\Phi ^{n}=1,$ циклическая группа, порожденная q -степенным автоморфизмом Фробениуса $\Phi (\alpha )=\alpha ^{q},$с $\Phi ^{n}=1=\mathrm {Id} _{K}.$ Тогда существует элемент β ∈ K такой, что $$\{\beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-1}(\beta )\}\ =\ \{\beta ,\beta ^{q},\beta ^{q^{2}},\ldots ,\beta ^{q^{n-1}}\!\}$$является базисом K над F .

Доказательство для конечных полей

В случае, если группа Галуа циклическая, как указано выше, порожденная $\Phi$ с $\Phi ^{n}=1,$ теорема о нормальном базисе следует из двух основных фактов. Во-первых, это линейная независимость характеров: мультипликативный характер — это отображение χ группы H в поле K, удовлетворяющее условиям $\chi (h_{1}h_{2})=\chi (h_{1})\chi (h_{2})$; затем любые отдельные символы $\chi _{1},\chi _{2},\ldots$ линейно независимы в K -векторном пространстве отображений. Мы применим это к автоморфизмам группы Галуа $\chi _{i}=\Phi ^{i}:K\to K,$ мыслится как отображения мультипликативной группы $H=K^{\times }$. Сейчас $K\cong F^{n}$как F -векторное пространство, поэтому мы можем рассматривать $\Phi :F^{n}\to F^{n}$ как элемент матричной алгебры M _n ( F ); поскольку его полномочия $1,\Phi ,\ldots ,\Phi ^{n-1}$ линейно независимы (над K и тем более над F ), его минимальный полином должен иметь степень не ниже n , т.е. он должен быть $X^{n}-1$.

Вторым основным фактом является классификация конечно порожденных модулей по PID, таких как $F[X]$. Каждый такой модуль M можно представить в виде ${\textstyle M\cong \bigoplus _{i=1}^{k}{\frac {F[X]}{(f_{i}(X))}}}$, где $f_{i}(X)$ могут быть выбраны так, чтобы они были моническими полиномами или нулевыми и $f_{i+1}(X)$ кратно $f_{i}(X)$. $f_{k}(X)$ - это унитарный многочлен наименьшей степени, аннулирующий модуль, или ноль, если такого ненулевого многочлена не существует. В первом случае ${\textstyle \dim _{F}M=\sum _{i=1}^{k}\deg f_{i}}$, во втором случае $\dim _{F}M=\infty$. В нашем случае циклического G размера n, порожденного $\Phi$ у нас есть изоморфизм F -алгебры ${\textstyle F[G]\cong {\frac {F[X]}{(X^{n}-1)}}}$ где X соответствует $1\cdot \Phi$, поэтому каждый $F[G]$-модуль можно рассматривать как $F[X]$-модуль, в котором умножение на X является умножением на $1\cdot \Phi$. В случае К это означает $X\alpha =\Phi (\alpha )$, поэтому монический многочлен наименьшей степени, аннулирующий K, является минимальным многочленом $\Phi$. Поскольку K — конечномерное F -пространство, приведенное выше представление возможно с помощью $f_{k}(X)=X^{n}-1$. С $\dim _{F}(K)=n,$ мы можем иметь только $k=1$, и ${\textstyle K\cong {\frac {F[X]}{(X^{n}{-}\,1)}}}$ как F [ X ]-модули. (Обратите внимание, что это изоморфизм F -линейных пространств, но не колец или F -алгебр.) Это дает изоморфизм $F[G]$-модули $K\cong F[G]$ о котором мы говорили выше, а под ним основа $\{1,X,X^{2},\ldots ,X^{n-1}\}$ в правой части соответствует нормальному базису $\{\beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-1}(\beta )\}$ К . слева

Заметим, что это доказательство применимо и в случае циклического расширения Куммера .

Пример

Рассмотрим поле $K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}$ над $F=\mathrm {GF} (2)=\mathbb {F} _{2}$, с автоморфизмом Фробениуса $\Phi (\alpha )=\alpha ^{2}$. Приведенное выше доказательство проясняет выбор нормальных базисов в терминах структуры K как представления G (или F [ G ]-модуля). Неприводимая факторизация $$X^{n}-1\ =\ X^{3}-1\ =\ (X{-}1)(X^{2}{+}X{+}1)\ \in \ F[X]$$ означает, что мы имеем прямую сумму F [ G ]-модулей (по китайской теореме об остатках ): $$K\ \cong \ {\frac {F[X]}{(X^{3}{-}\,1)}}\ \cong \ {\frac {F[X]}{(X{+}1)}}\oplus {\frac {F[X]}{(X^{2}{+}X{+}1)}}.$$Первый компонент просто $F\subset K$, а второй как F [ G ]-модуль изоморфен $\mathbb {F} _{2^{2}}\cong \mathbb {F} _{2}[X]/(X^{2}{+}X{+}1)$ под действием $\Phi \cdot X^{i}=X^{i+1}.$ (Таким образом $K\cong \mathbb {F} _{2}\oplus \mathbb {F} _{4}$ как F [ G ]-модули, а не как F -алгебры.)

Элементы $\beta \in K$ которые можно использовать для нормального базиса, являются именно теми, которые находятся вне любого из подмодулей, так что $(\Phi {+}1)(\beta )\neq 0$ и $(\Phi ^{2}{+}\Phi {+}1)(\beta )\neq 0$. С точки зрения G -орбит K , которые соответствуют неприводимым факторам: $$t^{2^{3}}-t\ =\ t(t{+}1)\left(t^{3}+t+1\right)\left(t^{3}+t^{2}+1\right)\ \in \ F[t],$$элементы $F=\mathbb {F} _{2}$ являются корнями $t(t{+}1)$, ненулевые элементы подмодуля $\mathbb {F} _{4}$ являются корнями $t^{3}+t+1$, а нормальный базис, который в данном случае единственный, задается корнями оставшегося множителя $t^{3}{+}t^{2}{+}1$.

Напротив, для поля расширения $L=\mathrm {GF} (2^{4})=\mathbb {F} _{16}$ в котором n = 4 делится на p = 2 , мы имеем изоморфизм F [ G ]-модуля $$L\ \cong \ \mathbb {F} _{2}[X]/(X^{4}{-}1)\ =\ \mathbb {F} _{2}[X]/(X{+}1)^{4}.$$Здесь оператор $\Phi \cong X$ недиагонализуем имеет вложенные подмодули , , модуль L заданные обобщенными собственными пространствами модуля L. $\Phi$, а нормальные базисные элементы β — это элементы, находящиеся вне наибольшего собственного обобщенного собственного пространства, элементы с $(\Phi {+}1)^{3}(\beta )\neq 0$.

Приложение к криптографии

Нормальный базис часто используется в криптографических приложениях, основанных на задаче дискретного логарифма , таких как криптография на эллиптических кривых , поскольку арифметика с использованием нормального базиса обычно более эффективна в вычислительном отношении, чем использование других базисов.

Например, в области $K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}$ выше мы можем представлять элементы как битовые строки: $$\alpha \ =\ (a_{2},a_{1},a_{0})\ =\ a_{2}\Phi ^{2}(\beta )+a_{1}\Phi (\beta )+a_{0}\beta \ =\ a_{2}\beta ^{4}+a_{1}\beta ^{2}+a_{0}\beta ,$$где коэффициенты - биты $a_{i}\in \mathrm {GF} (2)=\{0,1\}.$ Теперь мы можем возводить элементы в квадрат, делая круговой сдвиг влево: $\alpha ^{2}=\Phi (a_{2},a_{1},a_{0})=(a_{1},a_{0},a_{2})$, поскольку возведение в квадрат β ⁴ дает β ⁸ = β . Это делает нормальный базис особенно привлекательным для криптосистем, использующих частое возведение в квадрат.

Доказательство для случая бесконечных полей.

Предполагать $K/F$ является конечным расширением Галуа бесконечного поля F . Пусть [ K : F ] = n , ${\text{Gal}}(K/F)=G=\{\sigma _{1}...\sigma _{n}\}$, где $\sigma _{1}={\text{Id}}$. По теореме о примитивном элементе существует $\alpha \in K$ такой $i\neq j\implies \sigma _{i}(\alpha )\neq \sigma _{j}(\alpha )$ и $K=F[\alpha ]$. Давайте напишем $\alpha _{i}=\sigma _{i}(\alpha )$. $\alpha$(монический) минимальный многочлен f над K — это неприводимый многочлен степени n, заданный формулой $${\begin{aligned}f(X)&=\prod _{i=1}^{n}(X-\alpha _{i})\end{aligned}}$$Поскольку f отделима (она имеет простые корни), мы можем определить $${\begin{aligned}g(X)&=\ {\frac {f(X)}{(X-\alpha )f'(\alpha )}}\\g_{i}(X)&=\ {\frac {f(X)}{(X-\alpha _{i})f'(\alpha _{i})}}=\ \sigma _{i}(g(X)).\end{aligned}}$$Другими словами, $${\begin{aligned}g_{i}(X)&=\prod _{\begin{array}{c}1\leq j\leq n\\j\neq i\end{array}}{\frac {X-\alpha _{j}}{\alpha _{i}-\alpha _{j}}}\\g(X)&=g_{1}(X).\end{aligned}}$$Обратите внимание, что $g(\alpha )=1$ и $g_{i}(\alpha )=0$ для $i\neq 1$. Далее определите $n\times n$ матрица A многочленов над K и многочлен D по формуле $${\begin{aligned}A_{ij}(X)&=\sigma _{i}(\sigma _{j}(g(X))=\sigma _{i}(g_{j}(X))\\D(X)&=\det A(X).\end{aligned}}$$Обратите внимание, что $A_{ij}(X)=g_{k}(X)$, где k определяется соотношением $\sigma _{k}=\sigma _{i}\cdot \sigma _{j}$; в частности $k=1$ если только $\sigma _{i}=\sigma _{j}^{-1}$. Отсюда следует, что $A(\alpha )$ — матрица перестановок, соответствующая перестановке G , которая отправляет каждый $\sigma _{i}$ к $\sigma _{i}^{-1}$. (Мы обозначаем через $A(\alpha )$ матрица, полученная путем оценки $A(X)$ в $x=\alpha$.) Поэтому, $D(\alpha )=\det A(\alpha )=\pm 1$. Мы видим, что D — ненулевой многочлен и, следовательно, имеет лишь конечное число корней. Поскольку мы предположили, что F бесконечно, мы можем найти $a\in F$ такой, что $D(a)\neq 0$. Определять $${\begin{aligned}\beta &=g(a)\\\beta _{i}&=g_{i}(a)=\sigma _{i}(\beta ).\end{aligned}}$$Мы утверждаем, что $\{\beta _{1},\ldots ,\beta _{n}\}$ это нормальная база. Нам осталось только это показать $\beta _{1},\ldots ,\beta _{n}$ линейно независимы над F , поэтому предположим, что ${\textstyle \sum _{j=1}^{n}x_{j}\beta _{j}=0}$ для некоторых $x_{1}...x_{n}\in F$. Применение автоморфизма $\sigma _{i}$ урожайность ${\textstyle \sum _{j=1}^{n}x_{j}\sigma _{i}(g_{j}(a))=0}$ для всех я . Другими словами, $A(a)\cdot {\overline {x}}={\overline {0}}$. С $\det A(a)=D(a)\neq 0$, мы заключаем, что ${\overline {x}}={\overline {0}}$, что завершает доказательство.

Заманчиво взять $a=\alpha$ потому что $D(\alpha )\neq 0$. Но это недопустимо, потому что мы использовали тот факт, что $a\in F$ заключить, что для любого F -автоморфизма $\sigma$ и полиномиальный $h(X)$ над $K$ значение многочлена $\sigma (h(X))$ на равных ​ $\sigma (h(a))$.

Примитивный нормальный базис

Примитивным нормальным базисом расширения конечных полей E / F является нормальный базис для E / F который порождается примитивным элементом E K. , то есть генератором мультипликативной группы , ^× . (Обратите внимание, что это более ограничительное определение примитивного элемента, чем упомянутое выше после общей теоремы о нормальном базисе: для создания каждого ненулевого элемента K , а не просто базиса, требуются степени элемента.) Lenstra and Schoof (1987). ) доказал, что каждое расширение конечного поля обладает примитивным нормальным базисом, а случай, когда F является простым полем, был урегулирован Гарольдом Дэвенпортом .

Бесплатные элементы

Если K / F — расширение Галуа и в K порождает нормальный базис над F , то x свободен x в K / F . Если x обладает свойством, что для каждой подгруппы H группы Галуа G с фиксированным полем K ^ЧАС , x свободен для K / K ^ЧАС , то x говорят, что совершенно свободен в K / F . Каждое расширение Галуа имеет совершенно свободный элемент.

См. также

• Двойной базис в расширении поля
• Полиномиальный базис
• логарифм Зеха

Ссылки

• Коэн, С.; Нидеррайтер, Х. , ред. (1996). Конечные поля и приложения. Материалы 3-й международной конференции, Глазго, Великобритания, 11–14 июля 1995 г. Серия лекций Лондонского математического общества. Том. 233. Издательство Кембриджского университета . ISBN  978-0-521-56736-7 . Збл   0851.00052 .
• Ленстра, Х.В.младший ; Шуф, Р.Дж. (1987). «Примитивные нормальные базисы для конечных полей» . Математика вычислений . 48 (177): 217–231. дои : 10.2307/2007886 . hdl : 1887/3824 . JSTOR   2007886 . Збл   0615.12023 .
• Менезес, Альфред Дж. , изд. (1993). Приложения конечных полей . Международная серия Kluwer по инженерным наукам и информатике. Том. 199. Бостон: Академическое издательство Kluwer. ISBN  978-0792392828 . Збл   0779.11059 .