Бинарные отношения 3 страница

В случае F Ì P говорят также, что поле P является расширением своего подполя F. Из определения подполя следует, что ноль и единица поля P будут содержаться также в F и служить для F нулем и единицей. Если взять в P пересечение F₁ всех подполей, содержащих F и некоторый элемент a Î P, не принадлежащий F, то F₁ будет минимальным полем, содержащим множество {F, a}. Говорят, что расширение F₁ поля F получено присоединением к F элемента a, и отражают этот факт в записи F₁=F(a).

Аналогично можно говорить о подполе F₁ = F(a₁, …a_n) поля P, полученном присоединением к F n элементов a ₁, … a _n поля P.

Поля P и P' называются изоморфными, если они изоморфны как кольца. По определению f (0)=0' и f (1)=1' для любого изоморфного отображения f. Не имеет смысла говорить о гомоморфизмах полей, так как Ker f ≠ 0 Þ f(a) = 0, a ≠ 0 Þ f(1) = f(a∙ a^-1) = f(a) ∙ f(a^-1)=0∙ f(a^-1) = 0 Þ f(b) = f(1∙ b) = 0∙ f(b) = 0 " b Þ Ker f = P. Напротив, автоморфизмы, т.е. изоморфные отображения поля P на себя, связаны с самыми глубокими свойствами полей и являются мощным инструментом для изучения этих свойств.

2.7.2. Поле Галуа

Поле К называется конечным, или полем Галуа, если оно состоит из конечного числа элементов.

Теорема. Кольцо классов вычетов Z_m с элементами 0, 1,..., m-1 будет областью целостности, а значит и полем, лишь при простом m.

Именно конечное кольцо классов вычетов Z_p и называется полем Галуа порядка p и обозначается через F_p или GF(p). Характеристика поля GF(p) равна p.

Образующим элементом q поля GF(p) называется элемент порядка

p-1. (Это равносильно тому, что степени q пробегают все элементы GF(p).

Всего в GF(p) имеется φ (p-1) различных образующих элементов,

где φ (p) – функция Эйлера.

Если q – образующий элемент поля GF(p), то q^j является корнем n -ой степени из единицы тогда и только тогда, когда n∙ j ≡ 0(mod p-1). Число корней n -ой степени из единицы равно НОД(n, p-1). В частности, GF(p) содержит так называемый примитивный корень n -ой степени из единицы (т.е. такой элемент ψ, что степени ψ пробегают все корни n -ой степени из единицы), тогда и только тогда, когда n|p-1. Если ψ - примитивный корень n -ой степени из единицы в GF(p), то ψ ^j – также примитивный корень n -ой степени из единицы, если НОД(n, j) = 1.

Квадраты в GF(p) – называются квадратичными вычетами. Остальные элементы называются невычетами. В GF(p) имеется ровно (p-1)/2 квадратичных вычетов и невычетов

Пример 24. Пусть p = 11. Тогда квадратичными вычетами в GF(11) будут следующие числа: 1² = 1; 2² = 4; 3² = 9; 4² = 5; 5² = 3; 6² = 3; 7² = 5; 8² = 9; 9² = 4; 10² = 1, т.е. числа 1, 3, 4, 5, 9. Невычетами будут числа 2, 6, 7, 8, 10. ▲

Среди квадратичных вычетов присутствуют числа, являющиеся обычными квадратами в Z. В примере это 2²=4, 3²=9. Числа 2 и 4 называются главными квадратичными корнями.

Пусть F – конечное поле, содержащее подполе К из q элементов. Тогда F состоит из q^m элементов, где m = [F: K].

Здесь [F: K] обозначает степень поля F над К, т.е. размерность пространства F над К, если рассматривать F как векторное пространство над полем К.

Теорема. Пусть F – конечное поле. Тогда оно состоит из рⁿ элементов, где р простое число, являющееся характеристикой поля F, а n – натуральное число, являющееся степенью поля F над его простым подполем.

Если F – конечное поле из q элементов, то каждый элемент а Î F удовлетворяет равенству а^q = а .

...;

f(x) ≡ 0(mod m_r)

2. Число решений сравнения f(x) ≡ 0(mod m) равно произведению числа решений отдельных сравнений, указанной в п.1. системы сравнений.

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

Теорема. Пусть f₁(x),..., f_n(x) – многочлены, не все равные нулю. Тогда существует однозначно определенный нормативный многочлен d(x), обладающий свойствами:

1. d(x) делит каждый многочлен f_i(x), i = 1,..., n.

2. Любой многочлен g(x), который делит каждый из многочленов f_i(x), i = 1,..., n, делит и многочлен d(x).

Нормированный многочлен d(x) называют наибольшим общим делителем многочленов f₁(x),..., f_n(x) и обозначают НОД(f₁(x),..., f_n(x)). Если НОД(f₁(x),..., f_n(x)) = 1, то многочлены f₁(x),..., f_n(x) являются взаимнопростыми. Многочлены называются попарно взаимно простыми, если

НОД(f_i(x), f_j(x)) = 1; для всех 1 ≤ i < j ≤ n.

Наибольший общий делитель двух многочленов (также как и двух целых чисел) можно найти при помощи алгоритма Евклида. Пусть многочлен g(x) ¹ 0 и не делит многочлен f(x).

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

f(x) = g₁(x)·g(x) + r₁(x) 0 ≤ deg (r₁(x)) < deg (g(x))

g(x) = g₂(x)·r₁(x) + r₂(x) 0 ≤ deg (r₂(x)) < deg (r₁(x))

r₁(x) = g₃(x)·r₂(x) + r₃(x) 0 ≤ deg (r₃(x)) < deg (r₂(x))

· · ·

r_s-2(x) = g_s(x)·r_s-1(x) + r_s(x) 0 ≤ deg (r_s(x)) < deg (r_s-1(x))

r_s-1(x) = g_s+1(x)·r_s(x)

Т.к. степень deg(g(x)) конечна, то процедура заканчивается за конечное число шагов. Если старший коэффициент последнего ненулевого остатка r_s(x) равен b, то НОД(f(x), g(x)) = b^-1·r_s (x).

Пример 28. Найти НОД по алгоритму Евклида следующих многочленов над полем F₂:

f(x) = x⁶ + x³ + x² + 1

g(x) = x⁴ + x² + x

x⁶ + x³ + x² + 1 = (x² - 1)·(x⁴ + x² + x) + x +1

x⁴ + x² + x = (x³ - x² +1)·(x + 1) + 1

x + 1 = (x + 1)· 1

Значит, НОД(f(x), g(x)) = 1 то есть многочлены f(x) и g(x) взаимно простые. ▲

3.3. Неприводимые многочлены

Многочлен f(x) ненулевой степени из кольца R [ X ] называется неприводимым в R [ X ] (или неприводимым над полем P), если он не делится ни на какой многочлен g Î R[X], у которого 0 < deg g(x) < deg f(x). В частности, всякий многочлен первой степени неприводим. Совершенно очевидно, что неприводимость многочлена степени > 1 или разложение его на простые множители – понятия, тесно связанные с основным полем P. Как простых чисел в Z, так и унитарных неприводимых многочленов над произвольным полем P бесконечно много.

Так как над конечным полем количество многочленов заданной степени ограничено, то можно сделать следующее полезное заключение: над любым конечным полем существуют неприводимые многочлены сколь угодно высокой степени.

А теперь приведем без доказательства к ритерий неприводимости:

пусть f(x) = xⁿ + a₁ x^n-1 +…+ a^n-1 x + a_n Î Z[x] – унитарный многочлен над Z, все коэффициенты a₁, …, a_n которого делятся на некоторое простое число p, но a_n не делится на p². Тогда f[x] неприводим над Q (множеством рациональных чисел).

Примечание.Критерий действует и в том случае, когда старший коэффициент отличен от 1, но не делится на p.

Многочлен положительной степени f(x) называется приводимым, если существуют два многочлена положительной степени f₁(x) и f₂(x) такие, что f(x) = f₁(x)·f₂(x), т.е. если этот многочлен f(x) не является неприводимым.

Неприводимые многочлены играют важную роль в теории чисел, так как любой многочлен f(x) может быть записан, причем единственным способом, в виде произведения неприводимых многочленов (аналог того, что любое число n > 1 может быть представлено в виде произведения простых чисел).

Теорема. (Об однозначном разложении на множители)

Каждый многочлен положительной степени f(x) может быть представлен в виде произведения f(x) = a·f₁^m1(x)·...·f_n^mn(x),

где а - старший коэффициент f(x);

f₁(x),..., f_n – различные нормированные неприводимые многочлены;

m₁,...m_n – натуральные числа 1, 2, ….

При этом такое разложение называют каноническим разложением многочлена.

В криптосистемах особенный интерес представляют неприводимые многочлены степени n над простыми полями F_p порядка p, где p – простое число. Поиск всех неприводимых многочленов заданной степени n над некоторым полем F_p представляет собой очень сложную задачу. Французский математик Эварист Галуа (1811 -1832гг) создал теорию (теорию поля Галуа), доказывающую существование неприводимых многочленов сколь угодно большой степени, но поиск таких многочленов – очень сложная задача, и криптографические службы всего мира ведут активную работу по поиску таких многочленов. Известен неприводимый многочлен степени x⁶¹ + x³ +1, а для n > 61 данных найти не удалось. Разложение многочленов на множители над конечными полями связанны с проблемами построения линейных рекуррентных последовательностей над конечными полями, которые в свою очередь лежат в основе построения современных криптосистем (рассмотрены далее).

Пусть F – произвольное поле и f(x) Î F[x]. Тогда замена переменной x в многочлене f(x) произвольным элементом b Î F обращает этот многочлен в корректно определенный элемент поля F. Если f(x) = a₀+a₁x +...+a_nxⁿ Î F[x] и bÎ F, то, заменяя x на b, получаем элемент f(b) = a₀ + a₁b +...+ a_nbⁿ Î F. Элемент f(b) называют значением многочлена f(x) при x = b. Если в кольце F[x] имеется какое-либо полиномиальное равенство, то заменяя в нем x на bÎ F, получаем равенство в поле F. (Принцип подстановки). Элемент b Î F называют корнем (или нулем) многочлена f(x) Î F[x], если при x = b f(b) = 0. Элемент b Î F является корнем многочлена f(x) Î F[x] тогда и только тогда, когда многочлен x - b делит f(x) (т.е. x - b|f(x)).

Существует связь между отсутствием корней и неприводимостью многочленов. Если f(x) – неприводимый многочлен из F[x] степени n ³ 2, то согласно теореме он не имеет корней в поле F. Обратное утверждение справедливо только для многочленов степени 2 и 3.

Теорема. Для неприводимости многочлена f(x) Î F[x] степени 2 и 3 в кольце F[x] необходимо и достаточно, чтобы он не имел корней в поле F.

Пример 29. Пользуясь этой теоремой, можно найти неприводимые многочлены степени 2 и 3 в кольце F₂[x] над конечным полем F₂. Исключаем из всей совокупности многочленов указанной степени, принадлежащих кольцу F₂[x], те многочлены, которые имеют корни в поле F₂. Тогда получим, что в кольце F₂[x] имеется только один неприводимый многочлен степени 2: f(x) = x² + x + 1 и два неприводимых многочлена степени 3: f(x) = x³ + x + 1, f(x) = x³ + x² + 1.

Действительно: многочлены степени 2 – это f₁= x² + 1, f₂ = x² + x, f₃ = x² + x + 1.

Подставляя в них вместо x элементы поля F₂, т.е. 0 или 1, видно, что f₁ = 0 при x = 1, f₂ = 0 при x = 1 и x=0, а f₃ ¹ 0 при любом x Î { 0, 1}. Тоже самое и для многочленов степени 3: f₁ = x³ + x² + x +1, f₂ = x³ + x² +1, f₃ = x³ + x +1, f₄ = x³ + x² + x, f₅ = x³ + x ² … ▲

3.4 Порядок многочлена

У каждого ненулевого многочлена f(x) над конечным полем кроме его степени deg(f(x)) имеется еще одна важная целочисленная характеристика – его порядок.

Если f (x) Î F_q [ x ] многочлен степени m ³ 1, удовлетворяющий условию f(0) ¹ 0, то существует натуральное число e ≤ q^m - 1, для которого двучлен x^e -1 делится на f(x).

Этот факт позволяет ввести определение порядка многочлена над конечным полем.

Определение. Пусть f (x) Î F_q [ x ] ненулевой многочлен. Если f (0) ¹ 0, то наименьшее натуральное число е, для которого многочлен f (x) делит (x^e -1) называется порядком многочлена f (x) и обозначается ord (f (x)). Если же f(0) = 0, то многочлен f (x) однозначно представим в виде f (x) = x^h·g (x) где h Î N, g (x) Î F_q [ x ] и g(0) = 0 и тогда ord (f (x)) многочлена f (x) определяется как ord (g (x)).

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

Теорема. Пусть f (x) Î F_q [ x ] неприводимый многочлен степени m, удовлетворяющий условию f(0) ¹ 0. Порядок этого многочлена совпадает с порядком любого корня этого многочлена в мультипликативной группе F* поля F_q^m.

Отсюда вытекает важное следствие: Если f (x) Î F_q [ x ] неприводимый многочлен степени m над полем F_q, то его порядок ord (f (x)) делит число q^m -1.

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