Теорема (третя теорема про поле галуа) - стор
Теорема (Третя теорема про поле Галуа).
Для будь-якого простого числа p та натурального числа n існує єдине поле Галуа GF(p n ), яке є полем розкладання багаточлена.
За теоремою про поле розкладання, поле розкладання нашого багаточлена існує і воно єдине. Потрібно лише перевірити, що воно містить pn елементів. Оскільки наш многочлен має ступінь p n , Виходить, що поле розкладання має складатися виключно з коренів самого многочлена!
Спочатку перевіримо, що різного коріння рівно p n штук. Т. до. у многочлена над полем не може бути коріння більше, ніж його ступінь, то потрібно з'ясувати, чи є кратне коріння. Якби вони були, то багаточлен та його похідна мали б спільні дільники. Проте похідна многочлена дорівнює (оскільки характеристика поля дорівнює p ).
Тепер перевіримо, що коріння утворюють у полі розкладання підполі, а, отже, збігаються з полем розкладання, адже воно мінімальне поле, що містить усі корені.
Нехай a і b – коріння нашого багаточлена. Потрібно перевірити, що тоді a + b, ab, - a, a -1, а також 0 і 1, теж є корінням багаточлена. Для 0 та 1 це очевидно. Далі, за припущенням, маємо тому, не забуваючи, що характеристика дорівнює p , отримуємо
Обчислення, виконані нами при знаходженні зворотного елемента з множення, виявилися досить громіздкими. Звісно, на комп'ютері вони будуть виконані миттєво. Однак, якщо ступінь багаточлена буде в кілька сотень одиниць, і вирішувати доведеться багато рівнянь, комп'ютер теж мало здасться. Крім того, в машинному вигляді ідеально будь-які об'єкти представляти у вигляді чисел і все зводити до операцій над числами. Але щоб зв'язати числа з елементами кінцевого поля, нам потрібно ввести одне важливе.Концепція.
Визначення. Елемент мультиплікативної групи поля, що породжує, якщо він існує, називається примітивним елементом.
Теорема (Про примітивний елемент).
Будь-яке кінцеве поле має примітивний елемент.
Ми викладемо лише ідею доказу. Примітивний елемент, якщо існує, повинен мати порядок k = p n – 1. т.к. саме стільки ненульових елементів у полі GF(p n ). Якщо ж примітивного елемента немає, всі ненульові елементи поля мають порядки менші числа k . Точніше, їхні порядки мають ділити це число, за теоремою Лагранжа. І якщо S = НОК (порядків ненульових елементів поля) і S k , то вийде, що многочлен x S - 1 має k коріння, що неможливо. Якщо ж S = k = p n – 1, можна сформулювати необхідний примітивний елемент.
Ідея конструкції така. Нехай p 1, p 2, ..., p t - Всі різні прості дільники числа k. За припущенням, для кожного багаточлена повинен знайти елемент поля, який не є його коренем. Нехай це буде елемент a i.
Число k , за основною теоремою арифметики, має деяке розкладання
. Введемо в гру елементи. Добутком цих елементів і є наш примітивний елемент.
При виконанні обчислень у кінцевих полях часто виявляється корисним так званий логарифм Якобі. Якщо розглянути всі ненульові елементи кінцевого поля, що містить елементів q, як ступеня примітивного елемента b , то операція множення у нас стає простим додаванням по модулю q - 1, оскільки .
При використанні примітивних елементів в операціях додавання виникає проблема, як обчислити ступінь примітивного елемента, що дорівнює сумі 1 + b i . Це важливо, оскільки
Визначення. Відображення називається логарифмом Якобі. Тобто, .
Крім того, для b i = q - 1 логарифмЯкобі невизначений, т.к. у цьому випадку b i +1 = 0.
Приклад 2. Обчислимо логарифм Якобі у розширенні поля GF(3) ступеня 2. Нехай x 2 + 1 буде тим багаточленом, чиє поле розкладання шукаємо. Це поле має позначення GF(9), тобто. містить 9 елементів.
Найскладніше – знайти примітивний елемент. З теорії, що буде викладено пізніше, у полі GF(9) їх рівно , тобто. половина. Нагадаємо, що φ(n) - функція Ейлера, що дорівнює кількості натуральних чисел, менших n і взаємно-простих з n. Для малих кінцевих полів цілком може підійти або залишок x або x + 1. Претендента на примітивний елемент потрібно буде звести в 4-у ступінь. Якщо вона виявиться непоодинокою, це він – примітивний елемент.
Так як x 2 + 1 = 0, то x 2 = 2 тому послідовно отримуємо
x, x 2 = 2, x 4 = 2 2 = 1;
x + 1, (x + 1) 2 = x 2 + 2 x + 1 = 2 + 2 x + 1 = 2 x, (x + 1) 4 = (2 x) 2 = x 2 = 2.
Таким чином, b = x + 1 – примітивний елемент. Складаємо таблицю зі ступенів елемента b, з неї таблиця логарифму Якобі виходить миттєво