2. Многочлени над скінченними полями
Многочленом степеня над скінченним полем від однієї змінної називається вираз вигляду:
,
де коефіцієнти многочлена . Найбільше число таке, що коефіцієнт називається степенем многочлена і позначається . Якщо при цьому , то многочлен називається нормованим.
Многочлени над скінченним полем відносно звичайних операцій додавання і множення утворюють кільце, яке називається кільцем многочленів над полем і позначається .
Відзначимо, що многочлени над скінченним полем утворюють саме кільце, а не поле, тому що не існує таких многочленів степеня , які б при множенні давали б одиницю: , тобто в кільці многочленів для кожного елемента, що не є ненульовим сталим многочленом, відсутній обернений елемент
Для кільця многочленів над скінченним полем справедливі операції додавання, множення, ділення з остачею. У кільці зберігаються означення та властивості найбільшого спільного дільника многочленів, зокрема діє алгоритм Евкліда для визначення НСД і розширений алгоритм Евкліда для визначення лінійного представлення НСД.
Для многочленів над скінченним полем, як і для чисел, можна ввести поняття конгруенції.
Нехай , , – многочлени з . Многочлен називається конгруентним многочлену за модулем многочлена , якщо різниця ділиться на . Цей факт позначають так:
Останнє співвідношення називається конгруенцією многочленів за модулем многочлена .
Лишок многочлена за модулем многочлена дорівнює остачі від ділення на . Очевидно, у такому випадку при діленні на многочлени і дають однакову остачу. Процес переходу від до називається зведенням за модулем .
Многочлен називається незвідним над полем або у кільці , якщо рівність , де , – многочлени над , виконується тільки за умови, що якийсь з многочленів чи є сталим.
Незвідність многочленів аналогічна простоті цілих чисел. Незвідний многочлен не ділиться ні на який многочлен меншого степеня. Зокрема, всякий многочлен першого степеня є незвідним. Для незвідності многочлена степеня 2 або 3 над полем необхідно і достатньо, щоб він не мав коренів в полі .
Властивості незвідних многочленів над полем :
Будь-який незвідний многочлен степеня над полем є дільником многочлена .
Незвідний многочлен степеня над полем є дільником многочлена тоді і тільки тоді, коли .
Число нормованих незвідних многочленів степеня над полем дорівнює , де сума береться за всіма додатними дільниками числа , – функція Мебіуса.
Щоб знайти всі незвідні многочлени даного степеня над полем , треба:
Знайти всі звідні нормовані многочлени даного степеня над полем .
Вилучити отриману множину з множини всіх можливих нормованих многочленів степеня над полем .
Скінченні поля будуються з кілець многочленів так само, як вони будувалися з кілець класів лишків.
Для довільного зведеного многочлена ненульового степеня над полем кільцем многочленів за модулем називається множина всіх многочленів над цим полем, степені яких не перевищують степеня самого многочлена , з операціями додавання і множення многочленів за модулем . Позначають .
Кільце класів лишків цілих чисел за модулем утворює поле тільки коли , де – просте число. Так само, кільце утворює поле тільки коли многочлен – незвідний.
Теорема (необхідна і достатня умова перетворення кільця многочленів на поле.) Кільце многочленів за модулем буде полем тоді і тільки тоді, коли многочлен – нормований і незвідний.
Якщо над полем Галуа знайдено нормований незвідний многочлен степеня , то на основі викладеної теорії можна побудувати поле Галуа, елементи якого зображуються многочленами над степенів не вище . Всього існує таких многочленів, тому і поле буде складатися з елементів.
У кожного ненульового многочлена над скінченним полем окрім його степеня є ще одна важлива цілочисельна характеристика – його порядок.
Нехай – ненульовий многочлен. Якщо , то найменше натуральне число , для якого многочлен ділить многочлен називається порядком многочлена і позначається . Якщо ж , то многочлен однозначно представлений у вигляді , де , і і тоді многочлена визначається як .
Порядок многочлена іноді називають його періодом або експонентою.
Властивості порядку нормованого многочлена , , степеня над полем :
.
Якщо многочлен – незвідний над полем , то його порядок ділить націло число .
Порядок многочлена – найменше натуральне число, що задовольняє конгруенцію .
Якщо – незвідний нормований многочлен над полем характеристики і , , то
,
де – найменше ціле число, що є розв’язком нерівності .
Якщо – попарно взаємно прості ненульові многочлени над полем , а – їх порядки відповідно, то порядок добутку многочленів
дорівнює найменшому спільному кратному порядків :
.
Якщо – многочлен степеня над полем характеристики , то порядок многочлена дорівнює порядку многочлена .
Для визначення порядку многочлена треба:
Число розкласти на прості множники: ;
Для кожного множника відшукати лишки одночленів за модулем і далі серед них відшукати порядок многочлена;
Якщо , то порядок ділиться на , а якщо , то порядок не ділиться на ;
В останньому випадку з’ясувати, чи буде число ділитися на , ,…, , обчислюючи відповідні лишки. Такі розрахунки виконати для кожного простого дільника числа і в результаті знайти число .
Порядок незвідного многочлена можна визначити, користуючись наступною теоремою.
Теорема. Нехай – незвідний многочлен степеня m, що задовольняє умові . Порядок цього многочлена збігається з порядком будь-якого кореня цього многочлена в мультиплікативній групі поля
Звідси випливає важливий наслідок:
Наслідок. Якщо – незвідний многочлен степеня m над полем , то його порядок ділить число .
Означення. Незвідний нормований многочлен степеня над полем називається примітивним многочленом над полем , якщо його порядок дорівнює і .
Число примітивних многочленів степеня над полем дорівнює
,
де – значення функції Ейлера.
ІІ. Практичні завдання.
Завдання 1. Знайти суму і добуток многочленів і над полем
1) , ;
2) , ;
3) , ;
4) , ;
5) ; ;
6) , ;
7) ; ;
8) ; ;
9) ; ;
10) , ;
Завдання 2. Знайти
а) НСД многочленів і над полем ;
б) лінійне представлення НСД многочленів і над полем .
1) , , ;
2) , , ;
3) , , ;
4) , , ;
5) , , ;
6) , , ;
7) , ;
8) , , ;
9) , , ;
10) , , .
Завдання 3. Знайти лишок многочлена за модулем над полем .
1) , ;
2) , ;
3) , ;
4) , ;
5) , ;
6) , ;
7) , ;
8) , ;
9) , ;
10) , .
Завдання 4. Розкласти многочлен на добуток незвідних множників над полем .
1) , ;
2) , ;
3) , ;
4) , ;
5) , ;
6) , ;
7) , ;
8) , ;
9) , ;
10) , .
Завдання 5. З’ясувати, чи буде примітивним многочлен над полем .
1) , ;
2) , ;
3) , ;
4) , ;
5) , ;
6) , ;
7) , ;
8) , ;
9) , ;
10) , .
Завдання 6. Побудувати поле як поле многочленів за модулем многочлена над полем .
1) , ;
2) , ;
3) , ;
4) , ;
5) , ;
6) , ;
7) , ;
8) , ;
9) , ;
10) , .
ІІІ. Порядок виконання роботи.
1. Вивчити короткі теоретичні відомості з основ теорії подільності в кільці цілих чисел.
2. Розв’язати задачі згідно варіантам.
3. Скласти звіт, приєднавши отримані результати.
Вимоги до звіту.
У звіті мають бути приведені:
Вихідні дані (варіанти завдань);
результати і проміжні дані з необхідними поясненнями.
Література:
Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т.– М.: Мир, 1988. – Т.1. – 430 с., Т.2. – 392 с.
Нечаев В.И. Элементы криптографии (Основы теории защиты информации) –М.: Высшая школа, 1999. – 109 с.
Матемтические и компьютерные основы криптологии: Уч. пос. / Ю.С. Харин, В.И. Берник, Г.В. Матвеев, С.В. Агиевич. – МН.: Новое знание, 2003. – 382 с.