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

Хорошо известно, что для любого конечного поля ${\mathbf F}_q$ и его конечного расширения, поля ${\mathbf F}_{q^n}$, существует нормальный базис. Не составляет труда и доказательство того факта, что мультипликативная группа ${\mathbf F}_{q^n}^*$ циклическая. Интересен и нетривиален следующий факт: для любого конечного поля ${\mathbf F}_q$ и его расширения ${\mathbf F}_{q^n}$ существует элемент $x$ из поля ${\mathbf F}_{q^n}$, который является примитивным корнем для ${\mathbf F}_{q^n}^*$ (т. е образующим всей мультипликативной группы ${\mathbf F}_{q^n}^*$), и в тоже время является генератором нормального базиса для данного расширения (т. е элемент $x$ вместе со своими Галуа сопряжёнными элементами образует базис векторного пространства ${\mathbf F}_{q^n}$ над полем ${\mathbf F}_q$). Оригинальное доказательство данного утверждения было в полной общности получено Х. Ленстрой и Р. Шуфом и существенно опиралось на использование компьютера. Я расскажу о той части их рассуждений, которая может быть проведена без вычислений на машине, и о дальнейшем продвижении по данному вопросу (Коэн и Хусцинска), которое в конце концов позволило полностью избавиться от машинных вычислений.