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

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

Теорема о нормальном базисе [ править ]

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

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

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

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

Случай конечных полей [ править ]

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

${\displaystyle \{\beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-1}(\beta )\}\ =\ \{\beta ,\beta ^{q},\beta ^{q^{2}},\ldots ,\beta ^{q^{n-1}}\!\}}$

является основой K над F .

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

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

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

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

Пример [ править ]

Рассмотрим поле над с автоморфизмом Фробениуса . Приведенное выше доказательство поясняет выбор нормальных базисов в терминах структуры K как представления G (или F [ G ] -модуля). Неприводимая факторизация ${\displaystyle K=GF(2^{3})=\mathbb {F} _{8}}$${\displaystyle F=GF(2)=\mathbb {F} _{2}}$${\displaystyle \Phi (\alpha )=\alpha ^{2}}$

${\displaystyle X^{n}-1\ =\ X^{3}-1\ =\ (X{+}1)(X^{2}{+}X{+}1)\ \in \ F[X]}$

означает, что у нас есть прямая сумма F [ G ] -модулей (по китайской теореме об остатках ):

${\displaystyle K\ \cong \ {\frac {F[X]}{(X^{3}{-}\,1)}}\ \cong \ {\frac {F[X]}{(X{+}1)}}\oplus {\frac {F[X]}{(X^{2}{+}X{+}1)}}.}$

Первый компонент справедлив , а второй как F [ G ] -модуль изоморфен под действием (то есть как F [ G ] -модули, но не как F -алгебры.) ${\displaystyle F\subset K}$${\displaystyle \mathbb {F} _{2^{2}}\cong \mathbb {F} _{2}[X]/(X^{2}{+}X{+}1)}$${\displaystyle \Phi \cdot X^{i}=X^{i+1}.}$${\displaystyle K\cong \mathbb {F} _{2}\oplus \mathbb {F} _{4}}$

Элементы, которые могут быть использованы для нормального базиса, - это как раз те элементы, которые находятся вне любого из подмодулей, так что и . В терминах G- орбит K , которые соответствуют неприводимым множителям:${\displaystyle \beta \in K}$${\displaystyle (\Phi {+}1)(\beta )\neq 0}$${\displaystyle (\Phi ^{2}{+}\Phi {+}1)(\beta )\neq 0}$

${\displaystyle t^{2^{3}}-t\ =\ t(t{+}1)(t^{3}{+}t{+}1)(t^{3}{+}t^{2}{+}1)\ \in \ F[t],}$

элементы являются корнями , ненулевые элементы подмодуля являются корнями , а нормальный базис, который в данном случае единственен, задается корнями оставшегося фактора .${\displaystyle F=\mathbb {F} _{2}}$${\displaystyle t(t{+}1)}$${\displaystyle \mathbb {F} _{4}}$${\displaystyle t^{3}{+}t{+}1}$${\displaystyle t^{3}{+}t^{2}{+}1}$

Напротив, для поля расширений, в котором n = 4 делится на p = 2, мы имеем изоморфизм F [ G ] -модулей ${\displaystyle L=GF(2^{4})=\mathbb {F} _{16}}$

${\displaystyle L\ \cong \ \mathbb {F} _{2}[X]/(X^{4}{-}1)\ =\ \mathbb {F} _{2}[X]/(X{+}1)^{4}.}$

Здесь оператор не диагонализируем , модуль L имеет вложенные подмодули , данные обобщенных подпространства из и нормальных базисных элементов β являются те , за пределами собственно самым крупным обобщенно подпространством, элементы с .${\displaystyle \Phi \cong X}$${\displaystyle \Phi }$${\displaystyle (\Phi {+}1)^{3}(\beta )\neq 0}$

Применение в криптографии [ править ]

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

Например, в поле выше мы можем представить элементы как битовые строки:${\displaystyle K=GF(2^{3})=\mathbb {F} _{8}}$

${\displaystyle \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 ,}$

где коэффициенты - биты. Теперь мы можем возводить элементы в квадрат, выполняя круговой сдвиг влево, поскольку возведение в квадрат β ⁴ дает β ⁸ = β . Это делает нормальную основу особенно привлекательной для криптосистем, использующих частое возведение в квадрат.${\displaystyle a_{i}\in GF(2)=\{0,1\}.}$${\displaystyle \alpha ^{2}=\Phi (a_{2},a_{1},a_{0})=(a_{1},a_{0},a_{2})}$

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

Пусть это конечное расширение Галуа бесконечного поля F . Пусть , где . По теореме о примитивных элементах существуют такие, что . Пусть f - минимальный монический многочлен для . Тогда f - неприводимый монический многочлен степени n над F / Обозначим . Поскольку f имеет степень n , для . Обозначить ${\displaystyle K/F}$${\displaystyle [K:F]=n}$${\displaystyle {\text{Gal}}(K/F)=G=\{\sigma _{1}...\sigma _{n}\}}$${\displaystyle \sigma _{1}={\text{Id}}}$${\displaystyle \alpha \in K}$${\displaystyle K=F[\alpha ]}$${\displaystyle \alpha }$${\displaystyle \alpha _{i}=\sigma _{i}\alpha }$${\displaystyle \alpha _{i}\neq \alpha _{j}}$${\displaystyle i\neq j}$

${\displaystyle {\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}}}$

Другими словами, у нас есть

${\displaystyle {\begin{aligned}f(X)&=\ \prod _{i=1}^{n}(X-\alpha _{i})\\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}}}$

Обратите внимание, что и для . Затем определим матрицу A многочленов над K и многочлен D как${\displaystyle g(\alpha )=1}$${\displaystyle g_{i}(\alpha )=0}$${\displaystyle i\neq 1}$${\displaystyle n\times n}$

${\displaystyle {\begin{aligned}A_{ij}(X)&=&\sigma _{i}(\sigma _{j}(g(X))&=&\sigma _{i}(g_{j}(X))\\D(X)&=&\det A(X)\end{aligned}}}$

Заметим, что , где k определяется , в частности, тогда и только тогда . Отсюда следует, что это матрица перестановок, соответствующая перестановке G, которая отправляет каждую в . (Обозначим через матрицу, элементы которой являются значениями элементов at .) Следовательно, мы имеем . Мы видим, что D - ненулевой многочлен, поэтому он может иметь только конечное число корней. Поскольку мы предполагаем, что F бесконечно, мы можем найти такое, что . Определять${\displaystyle A_{ij}(X)=g_{k}(X)}$${\displaystyle \sigma _{k}=\sigma _{i}\cdot \sigma _{j}}$${\displaystyle k=1}$${\displaystyle \sigma _{i}=\sigma _{j}^{-1}}$${\displaystyle A(\alpha )}$${\displaystyle \sigma _{i}}$${\displaystyle \sigma _{i}^{-1}}$${\displaystyle A(\alpha )}$${\displaystyle A(X)}$${\displaystyle \alpha }$${\displaystyle D(\alpha )=\det A(\alpha )=\pm 1}$${\displaystyle a\in F}$${\displaystyle D(a)\neq 0}$

${\displaystyle {\begin{aligned}\beta &=&g(a)\\\beta _{i}&=&g_{i}(a)&=&\sigma _{i}(\beta )\end{aligned}}}$

Мы утверждаем, что это нормальная основа. Нам нужно только показать, что они линейно независимы над F , так что предположим для некоторых . Применяя автоморфизм, получаем для всех i . Другими словами, . Поскольку , мы заключаем , что завершает доказательство.${\displaystyle \{\beta _{1}...\beta _{n}\}}$${\displaystyle \beta _{1}...\beta _{n}}$${\displaystyle \sum _{j=1}^{n}x_{j}\beta _{j}=0}$${\displaystyle x_{1}...x_{n}\in F}$${\displaystyle \sigma _{i}}$${\displaystyle \sum _{j=1}^{n}x_{j}\sigma _{i}(g_{j}(a))=0}$${\displaystyle A(a)\cdot {\overline {x}}={\overline {0}}}$${\displaystyle \det A(a)=D(a)\neq 0}$${\displaystyle {\overline {x}}={\overline {0}}}$

Обратите внимание, что мы использовали тот факт, что для любого F -автоморфизма и многочлена по значению многочлена at равно . Поэтому мы не могли просто взять .${\displaystyle a\in F}$${\displaystyle \sigma }$${\displaystyle h(X)}$${\displaystyle K}$${\displaystyle \sigma (h(X))}$${\displaystyle a}$${\displaystyle \sigma (h(a))}$${\displaystyle a=\alpha }$

Примитивная нормальная основа [ править ]

Примитивный нормальный базис из расширения конечных полей E / F является нормальной основой для E / F , который генерируется с помощью примитивного элемента из Е , который является образующей мультипликативной группы (Обратите внимание , что это более ограничительное определение примитивных элемент, чем упомянутый выше после общей теоремы о нормальном базисе: для получения каждого ненулевого элемента K требуются степени элемента , а не просто базис.) Ленстра и Шуф (1987) доказали, что каждое расширение конечного поля обладает примитивной нормалью базис, случай, когда F - простое поле${\displaystyle K^{\times }.}$заселенный Гарольдом Давенпортом .

Бесплатные элементы [ править ]

Если К / Р является расширением Галуа и х в Е порождает нормальный базис над F , то х является свободным в K / F . Если x обладает тем свойством, что для любой подгруппы H группы Галуа G с фиксированным полем K ^H , x свободен для K / K ^H , то x называется полностью свободным в K / F. Каждое расширение Галуа имеет полностью бесплатный элемент. ^[2]

См. Также [ править ]

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

Ссылки [ править ]

• Cohen, S .; Niederreiter, H. , eds. (1996). Конечные поля и приложения. Труды 3 - й международной конференции, Глазго, Великобритания, 11-14 июля 1995 года . Серия лекций Лондонского математического общества. 233 . Издательство Кембриджского университета . ISBN 978-0-521-56736-7. Zbl  0851,00052 .
• Ленстра, HW, младший ; Schoof, RJ (1987). «Примитивные нормальные базисы для конечных полей» . Математика вычислений . 48 (177): 217–231. DOI : 10.2307 / 2007886 . JSTOR  2007886 . Zbl  0615.12023 .
• Менезеш, Альфред Дж. , Изд. (1993). Приложения конечных полей . Международная серия Kluwer в области инженерии и информатики. 199 . Бостон: Kluwer Academic Publishers. ISBN 978-0792392828. Zbl  0779.11059 .