Factorization of Polynomials: reducible, irreducible и тесты разложения

#абстрактная алгебра #cs #zero knowledge

В прошлой части мы говорили про polynomial rings:

R[x]

То есть про polynomials with coefficients in a ring R.

Теперь вопрос другой:

можно ли polynomial разложить на более простые множители?

Например:

x^2 - 1

можно записать как:

(x - 1)(x + 1)

А вот polynomial:

x^2 + 1

over real numbers так разложить уже нельзя.

Но over complex numbers можно:

x^2 + 1 = (x - i)(x + i)

То есть reducibility polynomial зависит не только от самого polynomial, но и от того, над каким ring или field мы работаем.

Reducible и irreducible polynomials

Пусть D — область целостности, а f(x) ∈ D[x]. Многочлен называется irreducible (неприводимым) над D, если его нельзя разложить на произведение двух множителей, ни один из которых не является обратимым.

Но сначала вспомним, что такое обратимый элемент.

Напоминание: что такое unit

Unit (обратимый элемент) — это элемент кольца, для которого существует обратный по умножению в том же кольце. То есть a является unit, если существует b из того же кольца, такое что:

ab = 1

Например:

  • В Z обратимы только 1 и -1.
  • В Q обратимо любое ненулевое число: например, для 2 обратным будет 1/2.
  • В Q[x] units — все ненулевые постоянные многочлены.
  • В Z[x] units — только постоянные многочлены 1 и -1.

Важно не путать unit с unity: unity — это сама мультипликативная единица кольца, а unit — любой элемент, имеющий обратный по умножению.

Почему это важно для многочленов? Рассмотрим:

x² + 1 = 2 · (x²/2 + 1/2)

В Q[x] такое разложение допустимо, но 2 является unit. Мы не считаем его настоящим разложением на множители, поскольку умножение на обратимый элемент не меняет существенную структуру многочлена.

Irreducible polynomial

Ненулевой многочлен f(x) ∈ D[x], который сам не является unit, называется irreducible over D, если любое его разложение:

f(x) = g(x)h(x)

обязательно содержит хотя бы один обратимый множитель:

g(x) — unit

или:

h(x) — unit

Иными словами, многочлен нельзя разложить на два необратимых множителя.

Reducible polynomial

Многочлен называется reducible (приводимым), если он ненулевой, не является unit и допускает разложение:

f(x) = g(x)h(x)

где оба множителя необратимы.

Например, в Z[x]:

x² - 1 = (x - 1)(x + 1)

Ни x - 1, ни x + 1 не являются units. Поэтому x² - 1 — приводимый многочлен. А вот нулевой многочлен и units по определению не относятся ни к приводимым, ни к неприводимым.

Если коэффициенты берутся из поля

Если мы работаем над полем F, всё становится проще. В F[x] обратимы только ненулевые постоянные многочлены, то есть многочлены степени 0. Почему? При умножении двух ненулевых многочленов над полем их степени складываются:

deg(fg) = deg(f) + deg(g)

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

Если многочлен f(x) обратим, должен существовать g(x) такой, что:

f(x)g(x) = 1

Но степень 1 равна 0, а степени ненулевых многочленов неотрицательны. Следовательно, сумма их степеней может равняться 0, только если оба множителя имеют степень 0. Поэтому многочлен положительной степени не может быть обратимым в F[x].

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

И наоборот: если ненулевой многочлен положительной степени нельзя разложить на произведение двух многочленов положительной степени, он неприводим над F.

Например, в Q[x]:

f(x) = x² - 1

приводим, поскольку:

f(x) = (x - 1)(x + 1)

Оба множителя имеют степень 1, меньшую степени исходного многочлена.

А вот:

f(x) = x + 1

неприводим над Q, поскольку его степень равна 1. Разложить его на два многочлена положительной степени невозможно: при умножении их степени складывались бы и дали как минимум 2.

Reducibility test for degrees 2 and 3

Для многочленов степени 2 и 3 существует простой способ проверить приводимость: достаточно выяснить, есть ли у многочлена хотя бы один корень в рассматриваемом поле.

Пусть F — поле, а f(x) ∈ F[x] — многочлен степени 2 или 3. Тогда:

f(x) reducible over F

тогда и только тогда, когда существует a ∈ F, для которого:

f(a) = 0

Иными словами:

  • Если корень есть, многочлен приводим.
  • Если корней нет, многочлен неприводим.

Почему это работает

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

deg f = deg g + deg h

Для многочлена степени 2 единственный вариант такого разложения:

2 = 1 + 1

То есть оба множителя линейные. Для многочлена степени 3 возможны варианты:

3 = 1 + 2

или:

3 = 2 + 1

Получается, что в обоих случаях хотя бы один множитель обязательно имеет степень 1. А любой линейный многочлен над полем можно записать в виде:

c(x - a)

где c ≠ 0 и a ∈ F.

По Factor theorem наличие множителя x - a означает, что a — корень исходного многочлена:

f(a) = 0

Верно и обратное: если мы нашли корень a, то можем выделить множитель x - a. Оставшийся множитель тоже будет иметь положительную степень, поскольку исходная степень равна 2 или 3. Таким образом, для многочленов степени 2 и 3 поиск корней полностью решает вопрос о приводимости.

Пример: проверка многочлена над Z₂

Рассмотрим:

f(x) = x³ + x + 1

над полем:

Z₂ = {0, 1}

Поскольку степень многочлена равна 3, нам достаточно проверить, существуют ли корни в Z₂. Возможных значений всего два. Подставим 0:

f(0) = 0³ + 0 + 1 = 1

Подставим 1:

f(1) = 1³ + 1 + 1
     = 3
     ≡ 1 (mod 2)

Ни в одном случае не получили 0. Значит, многочлен не имеет корней в Z₂. А поскольку его степень равна 3, по нашему тесту:

x³ + x + 1 — irreducible over Z₂

Мы доказали неприводимость, просто проверив два возможных значения, без перебора всевозможных разложений.

Почему тест не работает для степени 4 и выше

Для многочлена степени 4 появляется новый вариант разложения:

4 = 2 + 2

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

f(x) = (x² + 1)(x² + 2)

Очевидно, что многочлен приводим: мы уже разложили его на два необратимых множителя. Но при этом у него нет рациональных корней. Почему? Для любого рационального x:

x² ≥ 0

Поэтому:

x² + 1 > 0
x² + 2 > 0

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

Примеры приводимых и неприводимых многочленов

Рассмотрим несколько примеров, показывающих, как приводимость одного и того же многочлена зависит от кольца его коэффициентов.

Пример 1: 2x² + 4 над Z и Q

Рассмотрим:

f(x) = 2x² + 4

Над Z

В Z[x] мы можем записать:

2x² + 4 = 2(x² + 2)

Здесь оба множителя необратимы:

  • 2 не является unit в Z[x], поскольку 1/2 не принадлежит этому кольцу.
  • x² + 2 также не является unit, поскольку это многочлен положительной степени.

Значит, мы разложили многочлен на два необратимых множителя. Поэтому 2x² + 4 приводим над Z.

Над Q

В Q[x] то же разложение:

2x² + 4 = 2(x² + 2)

уже не доказывает приводимость. Почему? Потому что 2 теперь является unit: у него есть обратный элемент 1/2. Остаётся проверить, можно ли разложить x² + 2 на два линейных множителя. Для этого ищем корни:

x² + 2 = 0

x² = -2

Но квадрат рационального числа не может быть отрицательным. Значит, рациональных корней нет. Следовательно, x² + 2 неприводим над Q, а умножение на обратимый элемент 2 этого не меняет.

Пример 2: 2x² + 4 над R и C

Рассмотрим тот же многочлен:

f(x) = 2x² + 4

Над R

Число 2 является unit, поэтому достаточно исследовать:

x² + 2

Уравнение:

x² + 2 = 0

не имеет вещественных решений, поскольку x² ≥ 0 для любого вещественного x. Значит, многочлен степени 2 не может разложиться на два линейных множителя над R. Поэтому 2x² + 4 неприводим над R.

Над C

Теперь коэффициенты могут быть комплексными числами.

Решим:

x² + 2 = 0

x² = -2

Получаем два комплексных корня:

x = i√2
x = -i√2

По Factor theorem им соответствуют линейные множители:

x - i√2
x + i√2

Следовательно:

2x² + 4 = 2(x - i√2)(x + i√2)

Оба линейных множителя необратимы в C[x]. Поэтому многочлен приводим над C.

Пример 3: x² - 2 над Q и R

Рассмотрим:

f(x) = x² - 2

Над Q

Чтобы выяснить, приводим ли этот многочлен, попробуем найти его рациональные корни.

Решаем:

x² - 2 = 0

x² = 2

x = ±√2

Но √2 и -√2 — иррациональные числа. Они не принадлежат Q. Значит, рациональных корней нет, а многочлен степени 2 без корней над полем неприводим.

Поэтому:

x² - 2 — irreducible over Q

Над R

Вещественные числа уже содержат √2 и -√2. Поэтому мы можем разложить многочлен:

x² - 2 = (x - √2)(x + √2)

Оба множителя имеют положительную степень. Следовательно:

x² - 2 — reducible over R

Этот пример показывает, что при расширении поля коэффициентов могут появиться новые корни, а вместе с ними — новые способы разложения многочлена.

Пример 4: x² + 1 над Z₃ и Z₅

Теперь рассмотрим многочлен:

f(x) = x² + 1

над двумя конечными полями.

Над Z₃

Поле Z₃ содержит всего три элемента:

Z₃ = {0, 1, 2}

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

f(0) = 0² + 1 = 1

f(1) = 1² + 1 = 2

f(2) = 2² + 1 = 5 ≡ 2 (mod 3)

Ни в одном случае не получили 0. Значит, у x² + 1 нет корней в Z₃. Поскольку степень многочлена равна 2, этого достаточно для вывода:

x² + 1 — irreducible over Z₃

Над Z₅

Теперь работаем в поле:

Z₅ = {0, 1, 2, 3, 4}

Попробуем подставить 2:

f(2) = 2² + 1
     = 5
     ≡ 0 (mod 5)

Получили корень! Проверим 3:

f(3) = 3² + 1
     = 10
     ≡ 0 (mod 5)

Итак, у многочлена два различных корня в Z₅:

2 и 3

По Factor theorem им соответствуют множители:

x - 2
x - 3

Следовательно:

x² + 1 = (x - 2)(x - 3)

Проверим раскрытием скобок:

(x - 2)(x - 3)
= x² - 5x + 6

Но в Z₅:

-5 ≡ 0 (mod 5)
6 ≡ 1 (mod 5)

Поэтому:

x² - 5x + 6 = x² + 1

Всё сходится. Таким образом:

x² + 1 — reducible over Z₅

Кстати, поскольку:

-2 ≡ 3 (mod 5)
-3 ≡ 2 (mod 5)

можно записать то же разложение так:

x² + 1 = (x + 3)(x + 2)

Это одно и то же равенство в Z₅[x].

Content of a polynomial

Рассмотрим многочлены с целыми коэффициентами, то есть элементы кольца Z[x]. Содержание многочлена (content) — это наибольший общий делитель всех его коэффициентов.

Например, возьмём:

f(x) = 6x² + 10x + 14

Его коэффициенты:

6, 10, 14

Их наибольший общий делитель:

gcd(6, 10, 14) = 2

Значит, содержание многочлена равно 2. Почему это полезно? Потому что мы можем вынести 2 за скобки:

6x² + 10x + 14 = 2(3x² + 5x + 7)

При этом у многочлена 3x² + 5x + 7 уже нет общего делителя коэффициентов больше 1.

Таким образом, содержание показывает наибольший положительный целочисленный множитель, который можно вынести из всех коэффициентов многочлена.

Формальное определение

Пусть f(x) — ненулевой многочлен с целыми коэффициентами:

f(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀

Тогда его содержание:

content(f) = gcd(aₙ, aₙ₋₁, ..., a₁, a₀)

По соглашению берём положительный НОД. Отрицательные коэффициенты не меняют результат, поскольку НОД вычисляется по их абсолютным значениям.

Дополнительные примеры

Пример 1.

f(x) = 3x³ - 9x + 12

Коэффициенты:

3, 0, -9, 12

Поэтому:

content(f) = gcd(3, 0, -9, 12) = 3

Можем вынести 3:

f(x) = 3(x³ - 3x + 4)

Обратим внимание: отсутствующий член x² имеет коэффициент 0, но это не влияет на НОД.

Пример 2.

f(x) = 2x² + 5x + 7

Наибольший общий делитель коэффициентов:

content(f) = gcd(2, 5, 7) = 1

Это означает, что мы не можем вынести из всех коэффициентов никакой целочисленный множитель больше 1. Такой многочлен называется primitive polynomial (примитивным многочленом).

Gauss’s Lemma

Итак, примитивный многочлен — это многочлен с целыми коэффициентами, наибольший общий делитель которых равен 1. Лемма Гаусса утверждает: произведение двух примитивных многочленов тоже является примитивным.

То есть если f(x) и g(x) примитивны в Z[x], то:

content(fg) = 1

Пример

Возьмём два примитивных многочлена:

f(x) = 2x + 1

g(x) = 3x + 2

Проверим их содержание:

content(f) = gcd(2, 1) = 1

content(g) = gcd(3, 2) = 1

Теперь перемножим:

(2x + 1)(3x + 2)

= 6x² + 4x + 3x + 2

= 6x² + 7x + 2

Найдём содержание результата:

content(fg) = gcd(6, 7, 2) = 1

Получили ещё один примитивный многочлен.

Обратим внимание: отдельные коэффициенты могут иметь общие делители. Например, 6 и 2 делятся на 2. Но нет числа больше 1, которое делило бы сразу все коэффициенты. Лемма Гаусса гарантирует, что такой общий делитель не появится при умножении любых двух примитивных многочленов.

Почему это работает

Предположим обратное: произведение двух примитивных многочленов не является примитивным. Тогда НОД его коэффициентов равен некоторому числу d > 1. Любое целое число больше 1 имеет хотя бы один простой делитель. Выберем такой простой делитель p числа d. Поскольку d делит все коэффициенты произведения, p тоже делит каждый из них.

Перейдём к вычислениям modulo p. Поскольку все коэффициенты произведения делятся на p, в Z_p[x] оно превратится в нулевой многочлен:

f(x)g(x) = 0

Здесь под f(x) и g(x) понимаем многочлены, коэффициенты которых приведены modulo p.

Но Z_p — поле, а значит, Z_p[x] является областью целостности. В ней нет делителей нуля. Следовательно, если произведение равно нулю, то хотя бы один множитель сам должен быть нулевым многочленом. А это означало бы, что все коэффициенты одного из исходных многочленов делятся на p. Но мы начали с примитивных многочленов, у которых НОД коэффициентов равен 1. Поэтому такого простого числа p существовать не может. Получили противоречие.

Значит, произведение двух примитивных многочленов обязательно примитивно.

Зачем нужна лемма Гаусса

Она позволяет связать разложение многочленов над Z и над Q. Например, если примитивный многочлен с целыми коэффициентами удаётся разложить на множители с рациональными коэффициентами, то существует и разложение на множители с целыми коэффициентами положительной степени.

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

Reducibility over Q and over Z

Из леммы Гаусса следует важное утверждение:

Если многочлен с целыми коэффициентами приводим над Q, то он также приводим над Z.

Что это означает? Допустим, у нас есть многочлен:

f(x) ∈ Z[x]

Мы рассматриваем его над полем рациональных чисел Q и обнаруживаем, что он раскладывается на произведение двух многочленов положительной степени:

f(x) = g(x)h(x)

При этом коэффициенты g(x) и h(x) могут быть дробными.

Следствие леммы Гаусса гарантирует, что существует и разложение на два многочлена с целыми коэффициентами положительной степени.

Это полезно при проверке приводимости: нам необязательно искать всевозможные множители с рациональными коэффициентами. Достаточно выяснить, существует ли разложение в Z[x], где коэффициенты целые.

Пример: избавляемся от дробных коэффициентов

Рассмотрим:

f(x) = 6x² + x - 2

Допустим, мы нашли разложение над Q:

6x² + x - 2 = (3x - 3/2)(2x + 4/3)

Оба множителя имеют степень 1, поэтому многочлен приводим над Q. Но можно ли избавиться от дробей и получить разложение над Z?

Посмотрим на первый множитель:

3x - 3/2 = (3/2)(2x - 1)

А второй перепишем так:

2x + 4/3 = (2/3)(3x + 2)

Теперь подставим эти выражения в наше разложение:

f(x) = (3/2)(2x - 1) · (2/3)(3x + 2)

Обратим внимание на числовые множители:

(3/2) · (2/3) = 1

Они сокращаются! Поэтому остаётся:

f(x) = (2x - 1)(3x + 2)

Мы получили разложение с целыми коэффициентами.

Проверим:

(2x - 1)(3x + 2)
= 6x² + 4x - 3x - 2
= 6x² + x - 2

Всё сходится.

Таким образом:

6x² + x - 2

приводим и над Q, и над Z.

При чём здесь лемма Гаусса

В нашем примере получилось удачно перераспределить числовые множители и избавиться от знаменателей. Но почему это возможно не только для конкретного примера? Вспомним, что любой ненулевой многочлен из Z[x] можно представить как произведение его содержания и примитивного многочлена:

f(x) = content(f) · f₀(x)

Поскольку содержание — это НОД коэффициентов, его всегда можно вынести за скобки. После этого оставшийся многочлен будет примитивным: иначе у исходных коэффициентов существовал бы ещё больший общий делитель.

Лемма Гаусса позволяет доказать, что если примитивный многочлен f₀(x) раскладывается над Q, то он также раскладывается на многочлены положительной степени с целыми коэффициентами. Если исходный многочлен имеет содержание больше 1, этот числовой множитель можно просто включить в один из полученных множителей.

Поэтому результат справедлив для любого многочлена из Z[x], приводимого над Q.

А обратное утверждение верно?

Нет. Приводимость над Z не всегда означает приводимость над Q.

Например:

f(x) = 2x + 2

Над Z:

2x + 2 = 2(x + 1)

Оба множителя необратимы в Z[x], поэтому многочлен приводим. Но над Q число 2 уже является unit, а x + 1 имеет степень 1 и неприводим. Поэтому 2x + 2 неприводим над Q.

Однако для примитивных многочленов из Z[x] приводимость над Z и Q эквивалентна. Именно для них мы можем проверять разложение над целыми числами, не опасаясь разницы из-за общего числового множителя.

Mod p irreducibility test

Мы уже знаем, что лемма Гаусса позволяет связать разложение многочленов над Z и Q. Теперь рассмотрим ещё один способ проверки неприводимости: иногда вместо сложного многочлена с целыми коэффициентами можно исследовать гораздо более простой многочлен над конечным полем.

Для этого мы заменяем каждый коэффициент его остатком от деления на некоторое простое число p.

Как работает reduction modulo p

Пусть у нас есть многочлен:

f(x) = 21x³ - 3x² + 2x + 9

Его коэффициенты — целые числа, поэтому:

f(x) ∈ Z[x]

Попробуем привести все коэффициенты modulo 2:

21 ≡ 1 (mod 2)
-3 ≡ 1 (mod 2)
 2 ≡ 0 (mod 2)
 9 ≡ 1 (mod 2)

Подставляем полученные остатки вместо исходных коэффициентов:

21x³ - 3x² + 2x + 9

↓

x³ + x² + 1

Новый многочлен обозначим:

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

Теперь он принадлежит не Z[x], а:

Z₂[x]

То есть мы перешли от многочлена с произвольными целыми коэффициентами к многочлену, коэффициенты которого могут быть только 0 или 1. При этом степени x не меняются — мы заменяем только коэффициенты.

Как это помогает проверить неприводимость

Пусть p — простое число, f(x) ∈ Z[x], а f̄(x) — многочлен, полученный приведением коэффициентов modulo p. Работает следующий тест:

Если f̄(x) неприводим над Z_p и его степень совпадает со степенью исходного многочлена, то f(x) неприводим над Q.

То есть нам нужно проверить два условия:

  1. Полученный многочлен неприводим над Z_p.
  2. При приведении коэффициентов его степень не уменьшилась:
deg f̄ = deg f

Если оба условия выполнены, исходный многочлен точно неприводим над Q.

Почему это работает

Предположим, что исходный многочлен f(x) всё-таки приводим над Q. Тогда по следствию леммы Гаусса он раскладывается и над Z:

f(x) = g(x)h(x)

где оба множителя имеют положительную степень и целые коэффициенты. Теперь приведём коэффициенты всех трёх многочленов modulo p. Поскольку такое приведение сохраняет сложение и умножение, равенство останется верным:

f̄(x) = ḡ(x)h̄(x)

Но здесь важно условие о степени. Если степень f(x) при приведении не уменьшилась, значит, его старший коэффициент не превратился в 0. А старший коэффициент произведения g(x)h(x) равен произведению старших коэффициентов множителей. Следовательно, ни один из этих коэффициентов тоже не мог превратиться в 0 modulo p. Иначе старший коэффициент произведения стал бы нулём.

Поэтому степени обоих множителей сохраняются:

deg ḡ = deg g > 0

deg h̄ = deg h > 0

Получается, что f̄(x) раскладывается на два многочлена положительной степени. Но мы предположили, что f̄(x) неприводим! Это противоречие. Значит, исходный f(x) не мог быть приводим над Q.

Пример: проверяем кубический многочлен

Вернёмся к нашему многочлену:

f(x) = 21x³ - 3x² + 2x + 9

Мы уже привели его modulo 2 и получили:

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

Теперь проверим, неприводим ли этот многочлен над Z₂.

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

В Z₂ всего два элемента:

Z₂ = {0, 1}

Проверим оба.

При x = 0:

f̄(0) = 0³ + 0² + 1 = 1

При x = 1:

f̄(1) = 1³ + 1² + 1
      = 3
      ≡ 1 (mod 2)

Ни в одном случае не получили 0. Значит, у f̄(x) нет корней в Z₂, поэтому он неприводим.

Теперь проверим второе условие:

deg f = 3

deg f̄ = 3

Степень не уменьшилась.

Оба условия выполнены, поэтому:

21x³ - 3x² + 2x + 9

неприводим над Q. Мы доказали это, проверив всего два возможных корня в Z₂, вместо того чтобы искать разложения с рациональными коэффициентами.

Почему важно условие о степени

Возьмём тот же многочлен:

f(x) = 21x³ - 3x² + 2x + 9

Но теперь приведём коэффициенты modulo 3:

21 ≡ 0 (mod 3)
-3 ≡ 0 (mod 3)
 2 ≡ 2 (mod 3)
 9 ≡ 0 (mod 3)

Получаем:

f̄(x) = 2x

Этот многочлен неприводим над Z₃, поскольку имеет степень 1.

Однако:

deg f = 3

deg f̄ = 1

Степень уменьшилась! Исчезли члены 21x³ и -3x², поскольку их коэффициенты стали нулевыми modulo 3. Поэтому применить наш тест нельзя.

Неприводимость 2x ничего не говорит о неприводимости исходного кубического многочлена. Нам нужен такой p, при котором старший коэффициент не исчезнет.

Осторожно: обратное утверждение неверно

Наш тест работает только в одну сторону:

f̄ irreducible over Z_p
+
deg f̄ = deg f

⇒

f irreducible over Q

Но если приведённый многочлен оказался приводимым, это ещё не означает, что исходный многочлен приводим над Q. Возможно, выбранное простое число просто не подходит для доказательства.

Рассмотрим конкретный пример.

Пример: modulo 2 не помогает, но modulo 5 помогает

Возьмём:

f(x) = 21x³ - 3x² + 2x + 8

Сначала попробуем modulo 2.

Приводим коэффициенты:

21 ≡ 1
-3 ≡ 1
 2 ≡ 0
 8 ≡ 0

Получаем:

f̄(x) = x³ + x²

Но этот многочлен приводим:

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

Значит ли это, что исходный многочлен приводим над Q? Нет. Мы просто не смогли доказать его неприводимость с помощью modulo 2.

Попробуем другое простое число — 5.

Приводим коэффициенты:

21 ≡ 1 (mod 5)
-3 ≡ 2 (mod 5)
 2 ≡ 2 (mod 5)
 8 ≡ 3 (mod 5)

Получаем:

f̄(x) = x³ + 2x² + 2x + 3

Теперь работаем над Z₅. Поскольку степень равна 3, достаточно проверить наличие корней.

В Z₅ пять элементов:

0, 1, 2, 3, 4

Подставим их по очереди:

f̄(0) = 3

f̄(1) = 1 + 2 + 2 + 3
      = 8 ≡ 3 (mod 5)

f̄(2) = 8 + 8 + 4 + 3
      = 23 ≡ 3 (mod 5)

f̄(3) = 27 + 18 + 6 + 3
      = 54 ≡ 4 (mod 5)

f̄(4) = 64 + 32 + 8 + 3
      = 107 ≡ 2 (mod 5)

Ни одно значение не равно 0. Следовательно, f̄(x) не имеет корней в Z₅ и является неприводимым многочленом степени 3.

Проверим степень:

deg f = 3

deg f̄ = 3

Она не уменьшилась. Поэтому по нашему тесту исходный многочлен:

21x³ - 3x² + 2x + 8

неприводим над Q.

Обратим внимание: modulo 2 получился приводимый многочлен, а modulo 5 — неприводимый. Но оба раза мы работали с одним и тем же исходным многочленом.

Итог

Проверка modulo p позволяет заменить задачу о многочлене с целыми коэффициентами задачей над небольшим конечным полем. Если приведённый многочлен неприводим и его степень не уменьшилась, исходный многочлен неприводим над Q. Если же приведённый многочлен приводим или его степень уменьшилась, тест не даёт ответа. Можно попробовать другое простое число или воспользоваться другим методом.

Важно: не для каждого неприводимого многочлена обязательно найдётся простое p, при котором этот тест сработает. Поэтому это полезный способ доказательства неприводимости, но не универсальный алгоритм.

Polynomials with rational coefficients

Тест на неприводимость modulo p можно применять и к многочленам с рациональными коэффициентами. Для этого сначала нужно избавиться от знаменателей, умножив многочлен на их общее кратное.

Например, рассмотрим:

f(x) = (3/7)x⁴ - (2/7)x² + (9/35)x + 3/5

Умножим все коэффициенты на 35:

h(x) = 35f(x) = 15x⁴ - 10x² + 9x + 21

Мы получили многочлен с целыми коэффициентами. При этом умножение на 35 не влияет на приводимость над Q, поскольку любое ненулевое рациональное число является unit в Q[x].

Поэтому:

f(x) irreducible over Q
⇔
h(x) irreducible over Q

Теперь можно применить тест modulo p к h(x).

Проверка modulo 2

Приведём коэффициенты modulo 2:

15 ≡ 1
-10 ≡ 0
9 ≡ 1
21 ≡ 1

Получаем:

h̄(x) = x⁴ + x + 1

Степень осталась равной 4.

Проверим корни в Z₂:

h̄(0) = 1
h̄(1) = 1 + 1 + 1 ≡ 1 (mod 2)

Корней нет, значит, линейных множителей тоже нет. Но для степени 4 этого недостаточно: многочлен может раскладываться на два квадратичных множителя.

В Z₂[x] единственный неприводимый квадратичный многочлен с коэффициентом 1 при x²:

x² + x + 1

Проверим делимость на него. При делении с остатком можем использовать:

x² ≡ x + 1 (mod x² + x + 1)

Отсюда:

x³ ≡ 1
x⁴ ≡ x

Поэтому:

x⁴ + x + 1 ≡ x + x + 1 = 1

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

x⁴ + x + 1

неприводим над Z₂. Поскольку степень при приведении не уменьшилась, исходный многочлен:

h(x) = 15x⁴ - 10x² + 9x + 21

неприводим над Q. Следовательно, исходный многочлен с рациональными коэффициентами:

f(x) = (3/7)x⁴ - (2/7)x² + (9/35)x + 3/5

тоже неприводим над Q.

Главная идея: сначала избавляемся от дробных коэффициентов, а затем применяем обычный тест неприводимости modulo p.

Eisenstein’s criterion

Критерий Эйзенштейна — ещё один способ доказать, что многочлен с целыми коэффициентами неприводим над Q, не пытаясь разложить его на множители. Вместо поиска корней и множителей мы проверяем, делятся ли коэффициенты на определённое простое число.

Условия критерия

Пусть:

f(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀

— многочлен из Z[x].

Если существует простое число p, для которого выполняются три условия:

  1. Старший коэффициент не делится на p:

    p ∤ aₙ

  2. Все остальные коэффициенты делятся на p:

    p | aₙ₋₁, ..., p | a₁, p | a₀

  3. Свободный член не делится на p²:

    p² ∤ a₀

то многочлен f(x) неприводим над Q.

Напомним обозначения:

p | a   — p делит a без остатка
p ∤ a   — p не делит a без остатка

Таким образом, мы ищем простое число, которое делит все коэффициенты, кроме старшего. Причём свободный член должен делиться на p, но не на p².

Пример

Рассмотрим:

f(x) = 3x⁵ + 15x⁴ - 20x³ + 10x + 20

Попробуем применить критерий с:

p = 5

Условие 1. Старший коэффициент равен 3:

5 ∤ 3

Выполнено.

Условие 2. Проверим остальные коэффициенты:

5 | 15
5 | -20
5 | 0
5 | 10
5 | 20

Все они делятся на 5. Отсутствующий член x² имеет коэффициент 0, который тоже делится на 5.

Второе условие выполнено.

Условие 3. Свободный член равен 20. Проверяем делимость на квадрат выбранного простого числа:

5² = 25

25 ∤ 20

Третье условие тоже выполнено.

Следовательно, по критерию Эйзенштейна:

3x⁵ + 15x⁴ - 20x³ + 10x + 20

неприводим над Q. Мы доказали это, проверив всего три условия, без поиска корней и разложения многочлена пятой степени.

Почему критерий работает

Попробуем понять, откуда взялись эти условия.

Предположим, что наш многочлен всё-таки приводим над Q. Тогда по следствию леммы Гаусса его можно разложить над Z:

f(x) = g(x)h(x)

где оба множителя имеют положительную степень и целые коэффициенты. Теперь приведём коэффициенты modulo p. Поскольку все коэффициенты f(x), кроме старшего, делятся на p, они превратятся в нули.

Получим:

f̄(x) = aₙxⁿ

где коэффициент aₙ рассматривается modulo p и не равен нулю. То есть после приведения остался только один член многочлена. Но у нас также должно выполняться:

f̄(x) = ḡ(x)h̄(x)

В Z_p[x] произведение двух многочленов может состоять только из одного ненулевого члена вида aₙxⁿ лишь тогда, когда оба множителя тоже состоят из одного члена:

ḡ(x) = cxʳ

h̄(x) = dxˢ

где r, s > 0.

Почему степени положительные? Потому что старшие коэффициенты исходных множителей не исчезают modulo p: иначе исчез бы и старший коэффициент их произведения. Следовательно, свободные члены обоих множителей равны нулю modulo p. Иными словами, свободные члены g(x) и h(x) оба делятся на p. Но свободный член произведения равен произведению свободных членов множителей. Значит, свободный член f(x) должен делиться на:

p · p = p²

А третье условие критерия утверждает, что он не делится на p²! Получили противоречие. Следовательно, исходное разложение на два многочлена положительной степени невозможно, и f(x) неприводим над Q.

Важно

Критерий Эйзенштейна даёт достаточное, но не необходимое условие неприводимости. Если удалось найти подходящее простое p, неприводимость доказана. Но если ни одно простое число не подходит, это ещё не означает, что многочлен приводим. Возможно, его неприводимость придётся доказывать другим способом.

Irreducible polynomials and quotient fields

Мы уже знаем, что факторкольцо по максимальному идеалу является полем. Теперь выясним, как это связано с неприводимыми многочленами.

Напоминалка

  • Обычный идеал — подмножество кольца, замкнутое относительно сложения и вычитания. Кроме того, если умножить любой элемент идеала на любой элемент всего кольца, результат тоже должен принадлежать идеалу. Например, 6Z — идеал в Z, состоящий из всех целых чисел, кратных 6.
  • Максимальный идеал — собственный идеал (то есть не равный всему кольцу), который нельзя расширить до другого собственного идеала. Например, 5Z максимален в Z: любой идеал, содержащий 5Z, либо совпадает с ним, либо равен всему Z. А вот 6Z не максимален, поскольку существует промежуточный идеал: 6Z ⊂ 2Z ⊂ Z.

Связь неприводимых многочленов и теоремы про максимальный идеал

Мы уже встречали теорему: факторкольцо R/A является полем тогда и только тогда, когда A — максимальный идеал (для коммутативного кольца с unity). Максимальность гарантирует, что каждый ненулевой элемент факторкольца имеет обратный по умножению. Например, 5Z максимален в Z, поэтому Z/5Z ≅ Z₅ — поле.

Пусть F — поле, а p(x) ∈ F[x] — ненулевой многочлен положительной степени. Рассмотрим идеал:

<p(x)>

Он состоит из всех многочленов, кратных p(x). Оказывается, этот идеал максимален тогда и только тогда, когда p(x) неприводим над F. А поскольку факторкольцо по максимальному идеалу является полем, получаем:

F[x] / <p(x)> is a field
⇔
p(x) is irreducible over F

Таким образом, неприводимые многочлены позволяют строить новые поля из колец многочленов.

Почему приводимый многочлен не подходит

Предположим, что p(x) приводим. Тогда:

p(x) = a(x)b(x)

где оба множителя имеют положительную степень, меньшую степени p(x). Теперь построим факторкольцо:

F[x] / <p(x)>

В нём мы считаем p(x) равным нулю, поскольку все элементы идеала <p(x)> принадлежат нулевому классу.

Следовательно:

a(x)b(x) = 0

Поскольку a(x)b(x) = p(x), а p(x) принадлежит идеалу <p(x)>, его класс в факторкольце является нулевым. Поэтому произведение классов a(x) и b(x) равно нулю.

Но сами a(x) и b(x) не равны нулю в факторкольце! Почему? Нулевому классу принадлежат только многочлены, кратные p(x). А наши множители имеют меньшую степень, поэтому не могут делиться на p(x) без остатка.

Говоря иначе: поскольку по нашему предположению p(x) приводим, он раскладывается на два многочлена положительной степени. При умножении их степени складываются, поэтому степень каждого множителя обязательно меньше степени p(x).

Получается:

a(x) ≠ 0
b(x) ≠ 0

a(x)b(x) = 0

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

Конкретный пример

Возьмём:

p(x) = x² - 1

Этот многочлен приводим над R:

x² - 1 = (x - 1)(x + 1)

Построим факторкольцо:

R[x] / <x² - 1>

В нём выполняется:

x² - 1 = 0

Поэтому:

(x - 1)(x + 1) = 0

Но ни x - 1, ни x + 1 не принадлежат идеалу <x² - 1>: их степень меньше 2. Следовательно, их классы ненулевые, однако произведение этих классов равно нулю. Мы получили делители нуля, поэтому такое факторкольцо не является полем.

Почему неприводимый многочлен подходит

Теперь предположим, что p(x) неприводим над F. Мы уже доказали, что F[x] является PID, то есть каждый его идеал порождается одним многочленом. Покажем, что <p(x)> — максимальный идеал.

Допустим, существует идеал I, содержащий <p(x)>:

<p(x)> ⊆ I ⊆ F[x]

Поскольку F[x] — PID, найдётся многочлен g(x), такой что:

I = <g(x)>

Но p(x) принадлежит I. Значит, он должен быть кратен g(x):

p(x) = g(x)q(x)

А поскольку p(x) неприводим, один из множителей обязательно является unit.

Возможны два случая:

1. g(x) — unit.

Тогда идеал, порождённый g(x), совпадает со всем кольцом:

I = F[x]

2. q(x) — unit.

Тогда g(x) отличается от p(x) только обратимым множителем, поэтому они порождают один и тот же идеал:

I = <p(x)>

Других вариантов нет! Получается, что между <p(x)> и F[x] невозможно вставить другой собственный идеал. Значит, <p(x)> — максимальный идеал. А факторкольцо по максимальному идеалу является полем:

F[x] / <p(x)> is a field

Пример: комплексные числа

Мы уже рассматривали многочлен:

p(x) = x² + 1

Он неприводим над R, поскольку не имеет вещественных корней.

Значит, идеал:

<x² + 1>

максимален в R[x].

Почему <x² + 1> — максимальный идеал? Мы уже знаем, что R[x] — PID, то есть каждый его идеал порождается одним многочленом. Если некоторый идеал I = <g(x)> содержит <x² + 1>, то g(x) должен делить x² + 1. Но x² + 1 неприводим над R, поэтому один из множителей в разложении x² + 1 = g(x)q(x) обязательно является unit. Значит, I либо совпадает с <x² + 1>, либо равен всему R[x]. Промежуточного идеала нет, поэтому <x² + 1> максимален.

Поэтому:

R[x] / <x² + 1>

является полем.

Более того, мы уже доказали, что:

R[x] / <x² + 1> ≅ C

То есть из кольца вещественных многочленов мы действительно получили поле комплексных чисел.

Polynomial analogue of Euclid’s lemma

Вспомним лемму Евклида для простых чисел:

p | ab ⇒ p | a или p | b

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

Пусть F — поле, а p(x), a(x) и b(x) — многочлены из F[x]. Если p(x) неприводим над F и:

p(x) | a(x)b(x)

то обязательно:

p(x) | a(x)

или:

p(x) | b(x)

То есть неприводимый многочлен не может делить произведение, не разделив хотя бы один из его множителей.

Пример

Возьмём неприводимый над R многочлен:

p(x) = x² + 1

И два других многочлена:

a(x) = x - 2

b(x) = (x² + 1)(x + 3)

Их произведение:

a(x)b(x) = (x - 2)(x² + 1)(x + 3)

Очевидно, что p(x) = x² + 1 делит это произведение без остатка. При этом p(x) не делит a(x) = x - 2, поскольку степень a(x) меньше степени p(x).

Зато:

b(x) = p(x)(x + 3)

Поэтому p(x) делит b(x).

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

Почему это работает

В предыдущем разделе мы доказали, что если p(x) неприводим над F, то факторкольцо:

F[x] / <p(x)>

является полем. А в поле нет делителей нуля.

Теперь предположим:

p(x) | a(x)b(x)

Это означает, что произведение a(x)b(x) принадлежит идеалу <p(x)>, а значит, представляет нулевой класс в факторкольце:

(a(x) + I)(b(x) + I) = I

где:

I = <p(x)>

Но факторкольцо является полем, поэтому произведение двух ненулевых классов не может равняться нулю. Следовательно, хотя бы один класс должен быть нулевым:

a(x) + I = I

или:

b(x) + I = I

А это означает:

a(x) ∈ <p(x)>

или:

b(x) ∈ <p(x)>

То есть p(x) делит хотя бы один из множителей.

Почему важна неприводимость

Если p(x) приводим, утверждение может оказаться неверным. Например:

p(x) = x² - 1

Разложим его:

p(x) = (x - 1)(x + 1)

Очевидно, что p(x) делит произведение:

(x - 1)(x + 1)

Но при этом:

p(x) ∤ (x - 1)

p(x) ∤ (x + 1)

поскольку каждый множитель имеет меньшую степень, чем p(x). Получается, что приводимый многочлен делит произведение, но не делит ни один из множителей по отдельности.

Constructing a field with eight elements

Мы уже выяснили, что из кольца многочленов над полем можно построить новое поле, если взять факторкольцо по идеалу, порождённому неприводимым многочленом. Теперь воспользуемся этим способом, чтобы построить поле, состоящее ровно из восьми элементов.

Выбираем неприводимый многочлен

Начнём с поля:

Z₂ = {0, 1}

и рассмотрим многочлен:

p(x) = x³ + x + 1

Он принадлежит кольцу Z₂[x], то есть все его коэффициенты вычисляются modulo 2.

Мы хотим построить факторкольцо:

Z₂[x] / <x³ + x + 1>

Но чтобы оно стало полем, нужно убедиться, что p(x) неприводим над Z₂. Поскольку степень многочлена равна 3, достаточно проверить, есть ли у него корни в Z₂. Возможных значений всего два:

p(0) = 0³ + 0 + 1 = 1

p(1) = 1³ + 1 + 1
     = 3 ≡ 1 (mod 2)

Ни в одном случае не получили 0. Значит, у многочлена нет корней в Z₂, а следовательно, он неприводим. Мы уже знаем, что неприводимый многочлен порождает максимальный идеал в F[x], а факторкольцо по максимальному идеалу является полем.

Поэтому:

Z₂[x] / <x³ + x + 1>

действительно является полем.

Почему в нём ровно восемь элементов

Вспомним, как устроено факторкольцо. Его элементы — классы многочленов. Два многочлена принадлежат одному классу, если их разность кратна x³ + x + 1. Но любой многочлен из Z₂[x] можно разделить на x³ + x + 1:

f(x) = (x³ + x + 1)q(x) + r(x)

где:

deg r < 3

В факторкольце часть (x³ + x + 1)q(x) принадлежит нулевому классу. Поэтому f(x) и r(x) представляют один и тот же элемент. Получается, каждый элемент нашего поля можно представить многочленом степени не выше 2:

ax² + bx + c

где:

a, b, c ∈ Z₂

А в Z₂ каждый коэффициент может принимать только два значения:

0 или 1

У нас три коэффициента, и каждый выбирается независимо. Поэтому количество возможных комбинаций:

2 · 2 · 2 = 8

Вот все восемь элементов:

0
1
x
x + 1
x²
x² + 1
x² + x
x² + x + 1

Причём они представляют восемь различных классов, потому что разность двух разных многочленов степени меньше 3 не может делиться на x³ + x + 1 без остатка. Таким образом, мы действительно получили поле с восемью элементами.

Как выполнять вычисления

Теперь нужно разобраться, как складывать и умножать эти элементы. Поскольку мы построили факторкольцо по идеалу:

<x³ + x + 1>

все многочлены этого идеала представляют нулевой класс. Поэтому в нашем поле выполняется соотношение:

x³ + x + 1 = 0

Отсюда:

x³ = -x - 1

Но мы работаем modulo 2, где:

-1 = 1
-x = x

Следовательно:

x³ = x + 1

Это главное правило вычислений в нашем новом поле. Если при умножении появляются степени x³ или выше, мы используем это равенство, чтобы свести результат к многочлену степени меньше 3. Строго говоря, все такие равенства относятся к классам многочленов в факторкольце.

Пример: сложение

Сложим:

x² + x + 1

и:

x² + 1

Получаем:

(x² + x + 1) + (x² + 1)
= 2x² + x + 2

Но в Z₂:

2 ≡ 0 (mod 2)

Поэтому:

2x² + x + 2 = x

И окончательный результат:

(x² + x + 1) + (x² + 1) = x

Обратим внимание: при сложении нам даже не пришлось использовать правило x³ = x + 1. Мы просто сложили коэффициенты modulo 2.

Пример: умножение

Теперь умножим те же элементы:

(x² + x + 1)(x² + 1)

Раскрываем скобки:

= x⁴ + x³ + 2x² + x + 1

Поскольку 2x² = 0 в Z₂, получаем:

= x⁴ + x³ + x + 1

Но мы уже знаем, что в нашем факторкольце:

x³ + x + 1 = 0

Поэтому эта часть выражения исчезает, и остаётся:

x⁴

Однако x⁴ не входит в список наших восьми представителей: его степень слишком велика. Воспользуемся правилом:

x³ = x + 1

Умножим обе стороны на x:

x⁴ = x² + x

Следовательно:

(x² + x + 1)(x² + 1) = x² + x

Получили один из восьми элементов нашего поля.

Пример: находим обратный элемент

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

xy = 1

Возьмём:

y = x² + 1

Проверим:

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

Используем наше правило:

x³ = x + 1

Получаем:

x³ + x = (x + 1) + x
        = 2x + 1
        = 1

Отлично! Значит:

x · (x² + 1) = 1

То есть x² + 1 — обратный элемент к x в построенном поле. Это было бы невозможно в обычном кольце многочленов Z₂[x], где x не имеет обратного. Но в нашем факторкольце такой элемент существует.

Ещё пример: field with nine elements

Теперь построим поле из 9 элементов. Для этого рассмотрим факторкольцо:

Z₃[x] / <x² + 1>

Проверяем неприводимость

Начнём с многочлена:

p(x) = x² + 1

Чтобы факторкольцо стало полем, p(x) должен быть неприводим над Z₃. Поскольку степень многочлена равна 2, достаточно проверить, есть ли у него корни в Z₃. В этом поле всего три элемента:

Z₃ = {0, 1, 2}

Проверим все варианты:

p(0) = 0² + 1 = 1

p(1) = 1² + 1 = 2

p(2) = 2² + 1 = 5 ≡ 2 (mod 3)

Ни в одном случае не получили 0. Значит, x² + 1 неприводим над Z₃, а идеал <x² + 1> максимален. Следовательно:

Z₃[x] / <x² + 1>

является полем.

Почему в нём девять элементов

Вспомним, что элементы факторкольца — это классы многочленов. Любой многочлен можно разделить на x² + 1:

f(x) = (x² + 1)q(x) + r(x)

где степень остатка меньше 2.

Поскольку (x² + 1)q(x) принадлежит нулевому классу, каждый элемент факторкольца можно представить остатком:

r(x) = ax + b

где:

a, b ∈ Z₃

Для каждого коэффициента есть три варианта:

0, 1, 2

Поэтому число различных комбинаций:

3 · 3 = 9

Вот все девять элементов нашего поля:

0
1
2
x
x + 1
x + 2
2x
2x + 1
2x + 2

Эти многочлены представляют девять разных классов, поскольку разность двух различных представителей степени меньше 2 не может делиться на x² + 1 без остатка.

Как выполнять вычисления

В факторкольце:

Z₃[x] / <x² + 1>

многочлен x² + 1 принадлежит нулевому классу. Поэтому мы можем использовать соотношение:

x² + 1 = 0

Отсюда:

x² = -1

Но в Z₃:

-1 ≡ 2 (mod 3)

Значит, главное правило вычислений в нашем поле:

x² = 2

Строго говоря, речь идёт о равенстве классов в факторкольце. Например, умножим:

(x + 1)(x + 2)

Раскрываем скобки:

(x + 1)(x + 2) = x² + 3x + 2

В Z₃ имеем 3x = 0, поэтому:

= x² + 2

Заменяем x² на 2:

= 2 + 2
= 4
≡ 1 (mod 3)

Получили:

(x + 1)(x + 2) = 1

Следовательно, x + 1 и x + 2 — обратные элементы в нашем поле.

Это ещё один пример того, как в факторкольце появляются обратные элементы, которых не было в исходном кольце многочленов.

Связь с Z₃[i]

Вспомним, как мы строили комплексные числа:

R[x] / <x² + 1> ≅ C

Там элемент x в факторкольце вёл себя как мнимая единица i, поскольку:

i² = -1

Здесь идея аналогичная. Мы можем обозначить класс многочлена x символом i и договориться, что:

i² = -1 = 2

Тогда элементы нашего поля будут иметь привычный вид:

a + bi

где a, b ∈ Z₃.

Полученное поле обозначают:

Z₃[i] = {a + bi | a, b ∈ Z₃}

Например, ранее найденное равенство можно переписать так:

(i + 1)(i + 2) = 1

Важно: здесь i — не обычное комплексное число, а элемент построенного поля, который удовлетворяет тому же соотношению i² = -1. Все вычисления с коэффициентами выполняются modulo 3.

Таким образом:

Z₃[x] / <x² + 1> ≅ Z₃[i]

General pattern: finite fields from irreducible polynomials

В предыдущих разделах мы построили два конечных поля:

Z₂[x] / <x³ + x + 1>  →  8 элементов

Z₃[x] / <x² + 1>     →  9 элементов

Оба примера устроены одинаково. Мы брали поле Z_p, выбирали неприводимый многочлен и строили факторкольцо по порождённому им идеалу. Таким способом можно построить поле с p^n элементами для любого простого p и положительного целого n.

Откуда берётся p^n

Пусть p — простое число. Тогда:

Z_p = {0, 1, ..., p-1}

является полем. Выберем неприводимый многочлен:

f(x) ∈ Z_p[x]

степени n.

Мы уже знаем, что неприводимый многочлен порождает максимальный идеал, поэтому факторкольцо:

Z_p[x] / <f(x)>

тоже является полем. Но почему в нём именно p^n элементов? Вспомним, что любой многочлен можно разделить на f(x) и заменить остатком степени меньше n. Поэтому каждый элемент нового поля имеет единственное представление:

a_(n-1)x^(n-1) + ... + a₁x + a₀

Здесь все коэффициенты принадлежат Z_p. Получается:

  • У нас ровно n коэффициентов.
  • Каждый коэффициент может принимать p различных значений.
  • Все комбинации коэффициентов представляют разные элементы поля.

Следовательно, общее количество элементов:

p · p · ... · p = p^n

Такие поля обозначают:

GF(p^n)

или:

F_(p^n)

При n = 1 получаем обычное простое поле Z_p. При n > 1 — расширение поля, построенное с помощью многочленов.

Почему это важно для криптографии

Конечные поля используются в криптографии, поскольку позволяют выполнять точные алгебраические операции над ограниченным набором элементов. При этом существуют два основных варианта:

  • Простые поля GF(p). Их элементы — остатки modulo простого числа p. Например, такие поля широко используются в криптографии на эллиптических кривых.
  • Поля расширения GF(p^n). Их элементы можно представить многочленами степени меньше n, а операции выполняются modulo выбранного неприводимого многочлена.

Пример: AES

Конкретный пример — алгоритм шифрования AES, в котором используется поле:

GF(2⁸) = GF(256)

Его элементы можно представлять многочленами степени меньше 8 с коэффициентами 0 и 1. Поэтому каждому элементу соответствует один байт. Для построения поля в AES используется неприводимый многочлен:

x⁸ + x⁴ + x³ + x + 1

Он определяет правила сокращения степеней при умножении элементов поля. Конечные поля и их расширения также встречаются в кодах исправления ошибок, криптографии на эллиптических кривых, билинейных спариваниях и системах доказательств с нулевым разглашением (ZK).

Unique factorization in Z[x]

Мы уже знаем, что любое целое число, кроме 0 и units (например, 1), можно разложить на произведение простых чисел. Например:

60 = 2 · 2 · 3 · 5

Причём такое разложение единственно с точностью до порядка множителей и знаков. Оказывается, похожее свойство есть и у кольца многочленов Z[x].

Любой ненулевой многочлен, не являющийся unit, можно разложить на произведение неприводимых множителей. Причём это разложение тоже единственно с точностью до порядка множителей и умножения их на units. Такое свойство называется unique factorization (однозначное разложение на множители), а кольцо с этим свойством — Unique Factorization Domain (UFD).

Units в Z[x]

Сначала вспомним, какие элементы обратимы в Z[x]. Unit — это элемент, для которого существует обратный по умножению в том же кольце.

В Z[x] таких элементов всего два:

1
-1

Почему? Если два ненулевых многочлена при умножении дают 1, сумма их степеней должна равняться 0:

deg(fg) = deg f + deg g = 0

Следовательно, оба многочлена должны быть постоянными. А среди целых чисел обратимы только 1 и -1:

1 · 1 = 1

(-1) · (-1) = 1

Например, число 2 не является unit в Z[x], поскольку его обратный элемент 1/2 не принадлежит этому кольцу.

Какие множители считаются неприводимыми

В Z[x] неприводимые множители бывают двух типов.

1. Постоянные многочлены, соответствующие простым числам.

Например:

2, 3, 5, -2, -3, -5

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

А вот:

6 = 2 · 3

приводим, поскольку оба множителя не являются units.

Таким образом, ненулевой постоянный многочлен неприводим в Z[x] тогда и только тогда, когда его абсолютное значение — простое число.

2. Неприводимые многочлены положительной степени.

Например:

x - 1
x + 1
x² + 1

Они неприводимы в Z[x]. Первые два имеют степень 1 и являются примитивными, поэтому разложить их на два необратимых множителя невозможно. А x² + 1 примитивен и не имеет рациональных корней. Следовательно, он неприводим над Q, а по лемме Гаусса — и над Z.

Пример: раскладываем многочлен

Рассмотрим:

f(x) = 12x² - 12

Сначала найдём его содержание:

content(f) = gcd(12, -12) = 12

Выносим общий множитель:

12x² - 12 = 12(x² - 1)

Теперь разложим число 12 на простые множители:

12 = 2 · 2 · 3

А многочлен x² - 1 — по формуле разности квадратов:

x² - 1 = (x - 1)(x + 1)

Получаем:

12x² - 12 = 2 · 2 · 3 · (x - 1)(x + 1)

Все полученные множители неприводимы в Z[x]. Мы разложили исходный многочлен на два типа неприводимых множителей: простые целые числа и многочлены положительной степени.

Почему разложение считается единственным

Посмотрим ещё раз:

12x² - 12 = 2 · 2 · 3 · (x - 1)(x + 1)

Конечно, мы можем переставить множители:

3 · (x + 1) · 2 · (x - 1) · 2

Или изменить знаки двух множителей:

2 · 2 · 3 · (1 - x)(-x - 1)

Произведение останется тем же. Такие изменения не считаются разными разложениями, поскольку в Z[x] умножение на -1 означает умножение на unit. Поэтому говорят, что разложение единственно с точностью до порядка множителей и умножения на units. Это означает, что любое другое разложение исходного многочлена на неприводимые множители будет содержать те же множители с теми же кратностями, возможно, в другом порядке и с другими знаками.

Почему Z[x] обладает этим свойством

Здесь важную роль играет лемма Гаусса. Мы уже выяснили, что любой ненулевой многочлен из Z[x] можно представить так:

f(x) = content(f) · f₀(x)

где f₀(x) — примитивный многочлен.

Дальше мы можем отдельно разложить:

  • content(f) на простые целые числа;
  • примитивную часть f₀(x) на неприводимые многочлены.

Лемма Гаусса связывает разложения примитивных многочленов над Z и Q, где доступна привычная теория делимости многочленов над полем. Вместе с однозначным разложением целых чисел это позволяет доказать, что разложение многочленов из Z[x] также единственно с точностью до units и порядка множителей.

Таким образом:

Z[x] is a UFD

Итог

Кольцо Z[x] обладает свойством однозначного разложения на неприводимые множители, подобно кольцу целых чисел Z. При этом важно различать два понятия:

  • PID — каждый идеал порождается одним элементом.
  • UFD — каждый ненулевой необратимый элемент раскладывается на неприводимые множители единственным образом с точностью до порядка и units.

Z[x] является UFD, но не является PID. То есть однозначность разложения многочленов вовсе не означает, что каждый идеал можно породить одним многочленом.

Uniqueness up to units

Мы уже выяснили, что Z[x] является UFD — кольцом с однозначным разложением на неприводимые множители. Теперь уточним, что именно означает эта однозначность.

Предположим, один и тот же ненулевой многочлен, не являющийся unit, удалось разложить двумя способами:

f(x) = p₁(x)p₂(x)...pₘ(x)

и:

f(x) = q₁(x)q₂(x)...qₙ(x)

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

  • Количество множителей одинаково: m = n.
  • После перестановки множителей каждый pᵢ(x) отличается от соответствующего qᵢ(x) не более чем умножением на unit.

А поскольку в Z[x] существуют только два units, 1 и -1, получаем:

pᵢ(x) = ±qᵢ(x)

Например, разложения:

6x² - 6 = 2 · 3 · (x - 1)(x + 1)

и:

6x² - 6 = (-2) · 3 · (1 - x)(x + 1)

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

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

Weird dice: an application of unique factorization

Рассмотрим необычное применение однозначного разложения многочленов на неприводимые множители — задачу о двух игральных кубиках.

У обычного шестигранного кубика на гранях написаны числа:

1, 2, 3, 4, 5, 6

Если бросить два таких кубика, сумма может принимать значения от 2 до 12.

Причём разные суммы выпадают с разной вероятностью:

СуммаКоличество способов
21
32
43
54
65
76
85
94
103
112
121

Например, сумму 6 можно получить пятью способами:

1 + 5
2 + 4
3 + 3
4 + 2
5 + 1

Но возникает интересный вопрос: можно ли заменить числа на гранях обоих кубиков другими положительными целыми числами (в том числе повторяющимися) так, чтобы вероятности всех сумм от 2 до 12 остались такими же, как при броске двух обычных кубиков? Например, чтобы сумма 7 по-прежнему выпадала шестью способами, а сумма 2 — только одним?

Оказывается, можно. И разобраться в этом помогают многочлены.

Представляем кубик многочленом

Каждому числу на грани сопоставим степень x. Например, обычный кубик представим многочленом:

D(x) = x + x² + x³ + x⁴ + x⁵ + x⁶

Здесь степень каждого слагаемого соответствует числу на одной грани. Если бросить два кубика, их многочлены нужно перемножить:

D(x)²

Коэффициент при x^k показывает, сколькими способами можно получить сумму k. Почему? Потому что при умножении степеней показатели складываются:

x^a · x^b = x^(a+b)

Например, при раскрытии скобок D(x)² слагаемое x⁶ появляется пять раз:

x · x⁵
x² · x⁴
x³ · x³
x⁴ · x²
x⁵ · x

Поэтому коэффициент при x⁶ равен 5. Так задача о вероятностях превращается в задачу об умножении многочленов.

Кубики Сичермана

В 1978 году Джордж Сичерман обнаружил необычную пару шестигранных кубиков с положительными целыми числами на гранях.

Первый кубик:

1, 2, 2, 3, 3, 4

Второй:

1, 3, 4, 5, 6, 8

Несмотря на странную нумерацию, вместе они дают точно такое же распределение сумм, как два обычных кубика. Их называют Sicherman dice — кубиками Сичермана.

Представим их многочленами:

A(x) = x + 2x² + 2x³ + x⁴

B(x) = x + x³ + x⁴ + x⁵ + x⁶ + x⁸

Коэффициент 2 в A(x) означает, что соответствующее число написано на двух гранях.

Чтобы распределения сумм совпадали, должно выполняться:

A(x)B(x) = D(x)²

Именно это равенство мы теперь исследуем.

Разлагаем многочлен обычного кубика

Начнём с:

D(x) = x + x² + x³ + x⁴ + x⁵ + x⁶

Выносим x:

D(x) = x(1 + x + x² + x³ + x⁴ + x⁵)

Оставшуюся часть можно разложить:

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

Следовательно:

D(x) = x(x + 1)(x² + x + 1)(x² - x + 1)

Все четыре множителя неприводимы в Z[x]: линейные многочлены примитивны, а оба квадратных не имеют рациональных корней. Поэтому мы получили разложение на неприводимые множители.

Возведём его в квадрат:

D(x)² =
x²(x + 1)²(x² + x + 1)²(x² - x + 1)²

По свойству однозначного разложения любые многочлены A(x) и B(x), произведение которых равно D(x)², должны состоять из этих же неприводимых множителей. Остаётся выяснить, как именно можно распределить их между двумя кубиками.

Почему возможны только три варианта

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

Первое: минимальная степень каждого многочлена должна равняться 1.

Минимальная сумма обычных кубиков равна 2. Поскольку все числа на гранях положительны, наименьшее число на каждом необычном кубике тоже должно быть 1. Поэтому из множителя x² каждый кубик получает ровно один x.

Второе: сумма коэффициентов каждого многочлена должна равняться 6.

Ведь каждому слагаемому с учётом коэффициента соответствует одна грань. Сумму коэффициентов легко найти, подставив x = 1:

A(1) = 6

B(1) = 6

Посмотрим, какие значения дают наши неприводимые множители при x = 1:

x                  → 1
x + 1              → 2
x² + x + 1         → 3
x² - x + 1         → 1

Чтобы получить 6 = 2 · 3, каждый кубик должен получить ровно по одному множителю x + 1 и x² + x + 1.

Итак, обязательная часть многочлена каждого кубика:

x(x + 1)(x² + x + 1)

Осталось распределить два экземпляра последнего множителя:

(x² - x + 1)²

Он при x = 1 равен 1, поэтому не меняет количество граней.

У нас ровно три варианта:

  1. Отдать первому кубику 0 экземпляров, второму — 2.
  2. Отдать каждому по 1 экземпляру.
  3. Отдать первому 2 экземпляра, второму — 0.

Третий вариант совпадает с первым, если поменять кубики местами.

Посмотрим, что получается.

Вариант 1: обычные кубики

Каждый получает по одному экземпляру всех четырёх множителей:

D(x) = x(x + 1)(x² + x + 1)(x² - x + 1)

Это наш обычный кубик с гранями 1, 2, 3, 4, 5, 6.

Вариант 2: кубики Сичермана

Первый получает:

A(x) = x(x + 1)(x² + x + 1)
     = x + 2x² + 2x³ + x⁴

То есть грани:

1, 2, 2, 3, 3, 4

А второй получает оставшиеся множители:

B(x) = x(x + 1)(x² + x + 1)(x² - x + 1)²

После раскрытия скобок:

B(x) = x + x³ + x⁴ + x⁵ + x⁶ + x⁸

То есть грани:

1, 3, 4, 5, 6, 8

И поскольку вместе они содержат все неприводимые множители из D(x)² с нужными кратностями, получаем:

A(x)B(x) = D(x)²

Следовательно, распределение сумм полностью совпадает с обычной парой кубиков.

Что мы доказали

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

И всё благодаря двум свойствам многочленов:

  • Умножение многочленов позволяет подсчитывать количество способов получения каждой суммы.
  • Однозначность разложения в Z[x] ограничивает способы распределения неприводимых множителей между двумя кубиками.

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