Незвідні многочлени над скінченним полем

Конгруентність многочленів над скінченним полем

Для многочленів над скінченним полем, як і для чисел, можна ввести поняття конгруенції.

Означення. Нехай,, – многочлени з. Многочлен називається конгруентним многочлену за модулем многочлена, якщо різниця ділиться на. Цей факт позначають так:

Останнє співвідношення називається конгруенцієюмногочленів за модулем многочлена.

Лишок многочлена за модулем многочлена дорівнює остачі від ділення на. Очевидно, у такому випадку при діленні на многочлени і дають однакову остачу. Процес переходу від до називається зведенням за модулем.

Приклад 6. Знайти лишок многочлена за модулем над полем.

Розв’язання. У прикладі 3 знайдено

За означенням конгруентності многочленів маємо:

.

Приклад 7. Знайти лишок многочлена за модулем над полем.

Розв’язання. У прикладі 4 знайдено

За означенням конгруентності многочленів маємо:

.

Означення . Многочлен називається незвідним над полем або у кільці, якщо рівність, де, – многочлени над, виконується тільки за умови, що якийсь з многочленів чи є сталим.

Незвідність многочленів аналогічна простоті цілих чисел. Незвідний многочлен не ділиться ні на який многочлен меншого степеня. Зокрема, всякий многочлен першого степеня є незвідним. Для незвідності многочлена степеня 2 або 3 над полем необхідно і достатньо, щоб він не мав коренів в полі.

Приклад 8. Знайти всі незвідні многочлени степенів 2 та 3 над полем.

Розв’язання. З множини всіх многочленів відповідного степеня, які належать кільцю, вилучимо ті, які не мають коренів в полі. Ними виявляються один незвідний многочлен степеня 2 і два незвідні многочлени степеня 3 та.

Незвідні многочлени відіграють велику роль в побудові кільця, тому що кожен многочлен з можна єдиним способом подати у вигляді добутку незвідних нормованих многочленів над полем.

.

де,.

Розкладання многочлена на добуток незвідних нормованих многочленів відбувається за допомогою тотожних перетворень, які використовують властивості операцій в кільці многочленів: комутативність, асоціативність додавання і множення многочленів і дистрибутивність множення відносно додавання: винесення спільного множника за дужки, групування доданків, застосування формул скороченого множення тощо. Також можна скористатися методом невизначених коефіцієнтів, в основі якого лежать твердження:

Приклад 9. Розкласти многочлен на добуток незвідних множників над полем.

Розв’язання. Скористаємося методом невизначених коефіцієнтів. Оскільки многочлен третього степеня розкладається на добуток лінійного і квадратичного многочленів, то будемо шукати многочлени і такі, що справедлива рівність:

або

.

Прирівнюючи коефіцієнти при однакових степенях в лівій і правій частинах рівності, отримуємо систему для визначення невідомих коефіцієнтів. Розв’язуючи цю систему над полем, будемо мати:

Отже,

.

Для криптографічних цілей особливо важливі многочлени, незвідні над скінченним полем простої характеристики.

Властивості незвідних многочленів над полем:

1. Будь-який незвідний многочлен степеня над полем є дільником многочлена.

2. Незвідний многочлен степеня над полем є дільником многочлена тоді і тільки тоді, коли.

3. Число нормованих незвідних многочленів степеня над полем дорівнює, де сума береться за всіма додатними дільниками числа, – функція Мебіуса:

Приклад 10. Знайти число нормованих незвідних многочленів степеня 4 над полем.

Розв’язання. Додатні дільники числа є 1, 2, 4. Отже

.

Отже, існує 3 нормованих незвідних многочленів степеня 4 над полем.

Щоб знайти всі незвідні многочлени даного степеня над полем, треба:

1) Знайти всі звідні нормовані многочлени даного степеня над полем.

2) Вилучити отриману множину з множини всіх можливих нормованих многочленів степеня над полем.

Зауваження. При великих і цей спосіб непридатний.

Приклад 11 Знайти всі незвідні многочлени степеня 4 над полем.

Розв’язання. Число елементів поля дорівнює. Число різних многочленів четвертого степеня над полем дорівнює:

,,,,

,,,,

,,,,

,,,.

Всі потрібні звідні многочлени можна утворити, знайшовши добутки нормованих многочленів або, де всі. Після вилучення із списку всіх подібних добутків дістанемо всі незвідні многочлени степеня 4 над полем:

,,.

Їх 3, як було визначено раніше.

Розглянемо тепер питання про множину коренів незвідного многочлена над скінченним полем. На це важливе питання дають відповідь наступні теореми.

Лема. Нехай – незвідний многочлен степеня над полем. Тоді ділить многочлен тоді і тільки тоді, коли число ділить.

Теорема Галуа. Якщо – незвідний многочлен степеня над полем, то в полі міститься будь-який корінь многочлена. Більше того, всі корені многочлена прості (згадаємо, що корінь простий, якщо його кратність) і ними є різних елементів,,,.., поля.

З цієї теореми випливають наступні факти:

1. Незвідний многочлен над полем цілком розкладається в цьому полі, тобто, поле є полемо розкладання над полем.

2. Поля розкладання будь-яких двох незвідних многочленів одного й того самого степеня з кільця ізоморфні.

3. Кожне скінченне розширення скінченного поля є нормальним розширенням, тобто воно має властивість, що кожен незвідний многочлен з що має хоча б один корінь в полі, розкладається в цьому полі на лінійні співмножники.

4. Будь-яке скінченне поле є досконалим полем, тобто має властивість: кожний незвідний многочлен над цим полем має тільки прості корені.

Дата добавления: 2014-01-07