Примітивні многочлени

У кожного ненульового многочлена над скінченним полем окрім його степеня є ще одна важлива цілочисельна характеристика – його порядок.

Лема. Якщо– многочлен степеня, що задовольняє умові, то існує натуральне число, для якого двочлен ділиться на.

Цей факт дозволяє ввести означення порядку многочлена над скінченним полем.

Означення. Нехай – ненульовий многочлен. Якщо, то найменше натуральне число, для якого многочлен ділить многочлен називається порядком многочлена і позначається. Якщо ж, то многочлен однозначно представлений у вигляді, де, і і тоді многочлена визначається як.

Порядок многочлена іноді називають його періодом або експонентою.

Приклад 15. Визначити порядок многочлена над полем.

Розв’язання. Оскільки

,

то в полі многочлен ділиться на. Отже,.

Властивості порядку нормованого многочлена,, степеня над полем:

1..

2. Якщо многочлен – незвідний над полем, то його порядок ділить націло число.

3. Порядок многочлена – найменше натуральне число, що задовольняє конгруенцію.

4. Якщо – незвідний нормований многочлен над полем характеристики і,, то

,

де – найменше ціле число, що є розв’язком нерівності.

5. Якщо – попарно взаємно прості ненульові многочлени над полем, а – їх порядки відповідно, то порядок добутку многочленів

дорівнює найменшому спільному кратному порядків:

.

6. Якщо – многочлен степеня над полем характеристики, то порядок многочлена дорівнює порядку многочлена.

Для визначення порядку многочлена треба:

1) Число розкласти на прості множники:.

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

3) Якщо, то порядок ділиться на, а якщо, то порядок не ділиться на.

4) В останньому випадку з’ясувати, чи буде число ділитися на,,…,, обчислюючи відповідні лишки. Такі розрахунки виконати для кожного простого дільника числа і в результаті знайти число.

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

Теорема. Нехай – незвідний многочлен степеня m, що задовольняє умові. Порядок цього многочлена збігається з порядком будь-якого кореня цього многочлена в мультиплікативній групі поля.

Звідси випливає важливий наслідок:

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

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

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

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

,

де – значення функції Ейлера.

Приклад 16. З’ясувати, чи буде примітивним многочлен

над полем?

Розв’язання. Многочлен є незвідним над полем,,,. Для визначення порядку многочлена:

1) Розкладемо число 80 на прості множники.

2) Знайдемо лишок одночлена за модулем:

.

Знайдемо лишок одночлена за модулем:

.

3) Оскільки, то порядок ділиться на.

Так само, оскільки, то порядок ділиться на. Звідси і многочлен є примітивним над полем.

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

Розв’язання.

.

Хоча існує багато критеріїв перевірки незвідності многочленів над скінченними полями та методів їх побудови, довести примітивність того чи іншого незвідного многочлена можна тільки в окремих випадках. Для генерування примітивного многочлена найпростіше вибрати випадковий многочлен і перевірити, чи є він насправді примітивним (в багатьох пакетах математичних програм ці питання вирішуються достатньо швидко). На практиці часто використовують готові таблиці примітивних многочленів над різними скінченними полями. (Див., наприклад, Шнайер Б. Прикладная криптография. – М.: Триумф, 2002. – 815 с.)

Для побудови полів Галуа у криптографії часто застосовують як модулі тричлени виду, тому що довгий рядок нулів між коефіцієнтами та у їх канонічному записі дає змогу просто реалізувати швидке множення за модулем. Крім того, многочлен повинен бути примітивним, інакше математика перестає спрацьовувати. Наприклад, многочлен буде примітивним для значень, менших за 1000: 1, 3, 4, 6, 9, 15, 22. 28, 30, 46, 60, 127, 153, 172, 303, 471, 532, 865, 900.

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