Нормальная основа - Normal basis

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

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

Позволять ${ Displaystyle F подмножество K}$ - расширение Галуа с группой Галуа ${ displaystyle G}$. Классический теорема о нормальном базисе заявляет, что есть элемент ${ displaystyle beta in K}$ такой, что ${ Displaystyle {г ( бета): г в г }}$ составляет основу K, рассматриваемое как векторное пространство над F. То есть любой элемент ${ 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]}$.

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

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

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

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

${ Displaystyle { бета, Phi ( beta), Phi ^ {2} ( beta), ldots, Phi ^ {n-1} ( beta) } = { beta , beta ^ {q}, beta ^ {q ^ {2}}, ldots, beta ^ {q ^ {n-1}} ! }}$

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

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

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

Второй основной факт - это классификация конечно порожденных модули через PID такие как ${ Displaystyle F [X]}$. Каждый такой модуль M можно представить как ${ Displaystyle M cong bigoplus _ {я = 1} ^ {k} { frac {F [X]} {(f_ {i} (X))}}}$, где ${ displaystyle f_ {i} (X)}$ могут быть выбраны так, чтобы они были моническими многочленами или нулем и ${ displaystyle f_ {я + 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}$ у нас есть F-алгебр изоморфизм ${ Displaystyle F [G] cong { frac {F [X]} {(X ^ {n} -1)}}}$ где Икс соответствует ${ Displaystyle 1 cdot Phi}$так что каждый ${ displaystyle F [G]}$-модуль можно рассматривать как ${ Displaystyle F [X]}$-модуль с умножением на Икс умножение на ${ Displaystyle 1 cdot Phi}$. В случае K это означает ${ Displaystyle Х альфа = Фи ( альфа)}$, так что унитарный многочлен наименьшей степени, аннулирующий K - минимальный многочлен от ${ displaystyle Phi}$. поскольку K является конечномерным F-пространство, приведенное выше представление возможно с ${ displaystyle f_ {k} (X) = X ^ {n} -1}$. поскольку ${ Displaystyle тусклый _ {F} (К) = п,}$ мы можем иметь только ${ displaystyle k = 1}$, и ${ Displaystyle К конг { гидроразрыва {F [X]} {(X ^ {n} {-} , 1)}}}$ так как ${ displaystyle F [X]}$-модули. (Обратите внимание, что это изоморфизм F-линейные пространства, но нет колец или F-алгебры!) Это дает изоморфизм ${ displaystyle F [G]}$-модули ${ Displaystyle K cong F [G]}$ о котором мы говорили выше, и под ним основа ${ displaystyle {1, X, X ^ {2}, ldots, X ^ {n-1} }}$ справа соответствует нормальному основанию ${ Displaystyle { бета, Phi ( beta), Phi ^ {2} ( beta), ldots, Phi ^ {n-1} ( beta) }}$ из K слева.

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

пример

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

${ Displaystyle X ^ {n} -1 = X ^ {3} -1 = (X {+} 1) (X ^ {2} {+} X {+} 1) in F [ИКС]}$

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

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

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

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

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

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

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

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

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

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

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

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

${ displaystyle alpha = (a_ {2}, a_ {1}, a_ {0}) = a_ {2} Phi ^ {2} ( beta) + a_ {1} Phi ( бета) + 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})}$, поскольку возведение в квадрат β⁴ дает β⁸ = β. Это делает нормальную основу особенно привлекательной для криптосистем, использующих частое возведение в квадрат.

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

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

${ Displaystyle { begin {align} 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)) конец {выровнен}}}$

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

${ Displaystyle { begin {align} е (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) конец {выровнено}}}$

Обратите внимание, что ${ Displaystyle г ( альфа) = 1}$ и ${ Displaystyle g_ {я} ( альфа) = 0}$ за ${ Displaystyle я neq 1}$. Затем определите ${ Displaystyle п раз п}$ матрица А многочленов над K и полином D от

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

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

${ Displaystyle { begin {align} beta & = & g (a) beta _ {i} & = & g_ {i} (a) & = & sigma _ {i} ( beta) end { выровнено}}}$

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

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

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

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

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

Если K/F является расширением Галуа и Икс в E генерирует нормальную основу над F, тогда Икс является свободный в K/F. Если Икс обладает тем свойством, что для каждой подгруппы ЧАС группы Галуа г, с фиксированным полем K^ЧАС, Икс бесплатно для K/K^ЧАС, тогда Икс как говорят совершенно бесплатно в K/F. Каждое расширение Галуа имеет полностью бесплатный элемент.^[2]

Смотрите также

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

использованная литература

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