July 3, 2026 #абстрактная алгебра #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 — integral domain.

Polynomial:

f(x) ∈ D[x]

называется irreducible over D / неприводимым над D, если:

f(x) не является zero polynomial;
f(x) не является unit in D[x];
если:

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

где:

g(x), h(x) ∈ D[x]

то один из множителей обязан быть unit. То есть polynomial нельзя разложить на произведение двух “настоящих” nonunit factors.

Reducible polynomial

Polynomial называется reducible over D / приводимым над D, если он:

nonzero;
nonunit;
не является irreducible.

Проще:

reducible polynomial можно разложить на произведение двух nonunit polynomials.

То есть:

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

где ни g(x), ни h(x) не являются units.

Если coefficients берутся из field

Если D на самом деле field F, определение становится проще.

Polynomial:

f(x) ∈ F[x]

nonconstant polynomial называется irreducible over F, если его нельзя представить как product двух polynomials меньшей degree.

То есть нельзя записать:

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

где:

deg g < deg f

и:

deg h < deg f

Почему тут проще? Потому что в F[x] units — это все nonzero constant polynomials. Например, в Q[x] число:

является unit, потому что:

2 · 1/2 = 1

А в Z[x] число 2 не является unit, потому что:

1/2 not in Z[x]

Из-за этого один и тот же polynomial может быть irreducible над одним ring и reducible над другим.

Важно: irreducible depends on the base ring

Фраза:

f(x) is irreducible

сама по себе неполная.

Нужно уточнять:

irreducible over Q

irreducible over R

irreducible over C

irreducible over Z_3

Один и тот же polynomial может вести себя по-разному.

Пример: `2x^2 + 4` over `Q` и over `Z`

Рассмотрим:

f(x) = 2x^2 + 4

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

2x^2 + 4 = 2(x^2 + 2)

Здесь:

не является unit in Z[x].

И:

x^2 + 2

тоже не является unit.

Значит:

2x^2 + 4

reducible over Z.

Почему over `Q` иначе

В Q[x] тот же factorization:

2x^2 + 4 = 2(x^2 + 2)

не делает polynomial reducible, потому что:

является unit in Q[x].

У него есть inverse:

1/2

Поэтому multiplication by 2 не считается настоящим разложением на nonunit factors. А polynomial:

x^2 + 2

не имеет rational roots и не раскладывается на два linear factors over Q.

Поэтому:

2x^2 + 4

irreducible over Q, но reducible over Z.

Пример: `2x^2 + 4` over `R` и over `C`

Рассмотрим снова:

2x^2 + 4

Over R число 2 является unit, так что это essentially то же самое, что:

x^2 + 2

Но:

x^2 + 2 = 0

не имеет real roots. Значит polynomial irreducible over R. А over C roots существуют:

x^2 + 2 = 0

значит:

x^2 = -2

и:

x = i√2

или:

x = -i√2

Поэтому over C:

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

Значит polynomial reducible over C.

Пример: `x^2 - 2`

Polynomial:

x^2 - 2

irreducible over Q. Почему? Если quadratic polynomial reducible over a field, он должен иметь root in that field.

Но roots:

x = √2

и:

x = -√2

не являются rational numbers. Поэтому:

x^2 - 2

irreducible over Q. Но over R он reducible:

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

Пример: `x^2 + 1` over `Z_3` и `Z_5`

Рассмотрим:

x^2 + 1

over:

Z_3

Проверим possible roots:

0, 1, 2

Подставляем:

0^2 + 1 = 1

1^2 + 1 = 2

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

Нуля нет. Так как degree равна 2, отсутствие roots означает irreducible over Z_3. Теперь over:

Z_5

Проверим:

2^2 + 1 = 4 + 1 = 5 ≡ 0 (mod 5)

и:

3^2 + 1 = 9 + 1 = 10 ≡ 0 (mod 5)

Значит roots есть 2 и 3. Поэтому:

x^2 + 1

reducible over Z_5.

Indeed:

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

in Z_5[x].

Так как:

-2 ≡ 3 (mod 5)

и:

-3 ≡ 2 (mod 5)

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

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

Reducibility test for degrees 2 and 3

Есть полезный тест.

Пусть F — field, и:

f(x) ∈ F[x]

Если:

deg f = 2

или:

deg f = 3

то:

f(x) reducible over F

тогда и только тогда, когда f(x) имеет root in F.

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

Если polynomial degree 2 reducible, то он раскладывается на product polynomials меньшей degree. Единственный вариант:

degree 1 · degree 1

То есть появляется linear factor:

x - a

А значит a — root. Для degree 3 варианты такие:

degree 1 · degree 2

То есть если cubic polynomial reducible, у него обязательно есть linear factor.

А linear factor:

x - a

эквивалентен root:

f(a) = 0

по factor theorem.

Почему это не работает так же для degree 4

Для degree 4 reducible polynomial может раскладываться как:

degree 2 · degree 2

и не иметь linear factors.

Например over Q:

(x^2 + 1)(x^2 + 2)

reducible, но rational roots не имеет.

Поэтому тест “нет roots значит irreducible” безопасен только для degrees 2 и 3.

Content of a polynomial

Теперь перейдём к polynomials in:

Z[x]

Для nonzero polynomial with integer coefficients:

f(x) = anx^n + a(n-1)x^(n-1) + ... + a1x + a0

content / содержание polynomial — это greatest common divisor coefficients:

gcd(an, a(n-1), ..., a1, a0)

Обычно берут positive gcd.

Примеры content

Для polynomial:

6x^2 + 10x + 14

content равен:

gcd(6, 10, 14) = 2

Для:

3x^3 - 9x + 12

content равен:

gcd(3, -9, 12) = 3

Для:

2x^2 + 5x + 7

content равен:

gcd(2, 5, 7) = 1

Primitive polynomial

Polynomial in Z[x] называется primitive polynomial / примитивным многочленом, если его content равен 1. То есть coefficients не имеют общего divisor больше 1.

Например:

2x^2 + 5x + 7

primitive, потому что:

gcd(2, 5, 7) = 1

А polynomial:

6x^2 + 10x + 14

не primitive, потому что all coefficients divisible by 2.

Зачем нужен content

Любой nonzero polynomial in Z[x] можно представить как:

content · primitive polynomial

Например:

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

Здесь:

— content, а:

3x^2 + 5x + 7

primitive polynomial.

Так мы отделяем “числовой общий множитель” от настоящей polynomial structure.

Gauss’s Lemma

Gauss’s Lemma говорит:

product of two primitive polynomials is primitive.

То есть если:

f(x)

и:

g(x)

primitive in Z[x], то:

f(x)g(x)

тоже primitive.

Интуиция

Если у двух polynomials нет общего divisor во всех coefficients, то после multiplication внезапно не появится prime number, который делит все coefficients результата.

Например, если ни один polynomial не имеет all coefficients even, то их product тоже не станет polynomial, у которого all coefficients even.

Это не совсем очевидно, но именно это утверждает Gauss’s Lemma.

Reducibility over `Q` and over `Z`

Следствие Gauss’s Lemma:

если polynomial from Z[x] reducible over Q, то он reducible over Z.

То есть если integer polynomial можно разложить с rational coefficients, то его можно разложить и с integer coefficients.

Формально:

f(x) ∈ Z[x]

если f(x) reducible over Q, then f(x) reducible over Z.

Почему это важно

На практике это значит:

чтобы проверить reducibility integer polynomial over Q, часто можно искать factorization уже в Z[x].

Rational coefficients можно “очистить от знаменателей” и получить integer factorization.

Пример: rational factorization превращается в integer factorization

Рассмотрим:

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

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

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

Тут coefficients rational.

Но theorem говорит, что если factorization over Q существует, то есть factorization over Z.

Indeed:

6x^2 + x - 2 = (2x - 1)(3x + 2)

Проверим:

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

Так мы получили integer factorization.

Mod `p` irreducibility test

Теперь перейдём к более удобным tests for irreducibility. Идея такая: иногда polynomial с integer coefficients сложно проверять напрямую over Q. Но можно reduce coefficients modulo prime p и получить polynomial over finite field:

Z_p[x]

Там часто проще проверять roots и factors, потому что элементов мало.

Reduction modulo `p`

Пусть:

f(x) ∈ Z[x]

Например:

f(x) = 21x^3 - 3x^2 + 2x + 9

Если мы reduce coefficients modulo 2, то получаем polynomial over:

Z_2[x]

Считаем coefficients:

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

Значит reduced polynomial:

f_bar(x) = x^3 + x^2 + 1

Эту новую версию обычно обозначают:

f_bar(x)

Она живёт уже не в Z[x], а в:

Z_p[x]

Mod `p` irreducibility test

Пусть p — prime, и:

f(x) ∈ Z[x]

Пусть:

f_bar(x)

— polynomial in Z_p[x], полученный reduction coefficients modulo p.

Если:

f_bar(x)

irreducible over Z_p, и при reduction не упала degree:

deg f_bar(x) = deg f(x)

то:

f(x)

irreducible over Q.

Почему это полезно

Вместо того чтобы factor polynomial over rational numbers, можно попробовать несколько small primes:

2, 3, 5, 7, ...

Если хотя бы для одного prime p reduced polynomial оказался irreducible over Z_p, и degree не упала, то original polynomial irreducible over Q.

Пример: cubic polynomial

Рассмотрим:

f(x) = 21x^3 - 3x^2 + 2x + 9

Reduce modulo 2:

Получаем:

f_bar(x) = x^3 + x^2 + 1

Теперь проверим roots in Z_2.

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

0, 1

Подставляем:

f_bar(0) = 1

и:

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

Roots нет.

Так как polynomial degree 3, по reducibility test for degrees 2 and 3 отсутствие roots означает irreducible.

Значит:

f_bar(x)

irreducible over Z_2.

Degree не упала:

deg f_bar = 3 = deg f

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

21x^3 - 3x^2 + 2x + 9

irreducible over Q.

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

Возьмём тот же polynomial:

f(x) = 21x^3 - 3x^2 + 2x + 9

но теперь reduce modulo 3.

Coefficients:

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

Получаем:

f_bar(x) = 2x

Этот polynomial irreducible over Z_3, потому что он degree 1.

Но degree упала:

deg f = 3
deg f_bar = 1

Поэтому theorem применить нельзя. Такой reduction потерял старшие terms polynomial, и он уже не отражает исходную структуру достаточно хорошо.

Осторожно: converse не работает

Mod p test работает только в одну сторону:

f_bar irreducible over Z_p
=> f irreducible over Q

Но обратное неверно.

Если для какого-то prime p reduced polynomial оказался reducible, это не значит, что original polynomial reducible over Q.

Может просто не повезло с этим p.

Пример, где один prime не помогает

Рассмотрим:

f(x) = 21x^3 - 3x^2 + 2x + 8

Modulo 2:

Получаем:

f_bar(x) = x^3 + x^2

А это reducible:

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

Но это ещё не доказывает, что f(x) reducible over Q.

Попробуем modulo 5.

Coefficients:

Получаем:

f_bar(x) = x^3 + 2x^2 + 2x + 3

Проверяем roots in Z_5:

f_bar(0) = 3

f_bar(1) = 1 + 2 + 2 + 3 = 8 ≡ 3

f_bar(2) = 8 + 8 + 4 + 3 = 23 ≡ 3

f_bar(3) = 27 + 18 + 6 + 3 = 54 ≡ 4

f_bar(4) = 64 + 32 + 8 + 3 = 107 ≡ 2

Roots нет. Так как degree 3, это означает irreducible over Z_5. Degree не упала, значит original polynomial:

21x^3 - 3x^2 + 2x + 8

irreducible over Q.

Главная мысль:

один prime может не сработать, но другой prime может сработать.

Polynomials with rational coefficients

Mod p test можно использовать и для polynomials with rational coefficients. Но сначала нужно убрать denominators.

Например:

f(x) = (3/7)x^4 - (2/7)x^2 + (9/35)x + 3/5

Умножим на общий denominator:

Получаем:

h(x) = 35f(x) = 15x^4 - 10x^2 + 9x + 21

Over Q multiplication by nonzero rational number не влияет на irreducibility, потому что nonzero rational constants являются units in Q[x].

То есть:

f(x) irreducible over Q

iff:

h(x) irreducible over Q

Теперь можно проверять h(x) modulo primes.

Modulo 2:

Получаем:

h_bar(x) = x^4 + x + 1

У него нет roots in Z_2:

h_bar(0) = 1

h_bar(1) = 1 + 1 + 1 = 1

Для degree 4 этого ещё недостаточно: polynomial мог бы раскладываться как product двух quadratics. Но проверка quadratic factors показывает, что таких factors тоже нет.

Значит:

x^4 + x + 1

irreducible over Z_2.

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

h(x)

irreducible over Q, а значит и исходный:

f(x)

тоже irreducible over Q.

Eisenstein’s criterion

Есть ещё один очень мощный irreducibility test.

Пусть:

f(x) = a_nx^n + a_(n-1)x^(n-1) + ... + a_1x + a_0

is in:

Z[x]

Если существует prime p, такой что:

p не делит leading coefficient:

p ∤ a_n

p делит все остальные coefficients:

p | a_(n-1), ..., p | a_1, p | a_0

p^2 не делит constant term:

p^2 ∤ a_0

то:

f(x)

irreducible over Q.

Это называется:

Eisenstein's criterion

Как читать условия Eisenstein

Polynomial должен выглядеть так:

leading coefficient не делится на p

но все остальные coefficients делятся на p. При этом constant term делится на p, но не делится на p^2. То есть p входит в constant term ровно “не слишком сильно”.

Пример Eisenstein

Рассмотрим:

f(x) = 3x^5 + 15x^4 - 20x^3 + 10x + 20

Попробуем:

p = 5

Leading coefficient:

не делится на 5:

5 ∤ 3

Все остальные coefficients делятся на 5:

Constant term:

не делится на:

То есть:

25 ∤ 20

Все условия Eisenstein выполнены.

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

3x^5 + 15x^4 - 20x^3 + 10x + 20

irreducible over Q.

Cyclotomic polynomial for prime `p`

Для prime p polynomial:

Φ_p(x) = (x^p - 1) / (x - 1)

равен:

Φ_p(x) = x^(p-1) + x^(p-2) + ... + x + 1

Он называется:

pth cyclotomic polynomial

И theorem говорит:

Φ_p(x) is irreducible over Q

Почему здесь появляется Eisenstein

Напрямую Eisenstein к:

x^(p-1) + x^(p-2) + ... + x + 1

не применяется, потому что все coefficients равны 1. Но можно сделать substitution:

x -> x + 1

и рассмотреть:

Φ_p(x + 1)

Такая замена не меняет reducibility over Q, потому что её можно обратить заменой:

x -> x - 1

После substitution получается polynomial, к которому применяется Eisenstein with prime p. Отсюда следует, что:

Φ_p(x)

irreducible over Q.

Почему irreducible polynomials важны

Irreducible polynomials — это polynomial analogue of prime numbers. В integers prime number нельзя разложить на nontrivial factors. В polynomial rings irreducible polynomial нельзя разложить на product polynomials lower degree. Но ещё важнее связь с quotient rings.

Если F — field, то:

F[x] / <f(x)>

является field тогда и только тогда, когда:

f(x)

irreducible over F. Именно поэтому irreducible polynomials так важны для construction finite fields.

Например, fields вида:

F_(p^n)

строятся через quotients:

F_p[x] / <irreducible polynomial of degree n>

Irreducible polynomials and quotient fields

Главная причина, почему irreducible polynomials так важны, — это связь с quotient rings.

Пусть F — field, и пусть:

p(x) ∈ F[x]

Тогда ideal:

<p(x)>

является maximal ideal in F[x] тогда и только тогда, когда:

p(x)

irreducible over F. А мы уже знаем:

R / A is a field iff A is maximal

Поэтому получаем важнейшее следствие:

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

То есть irreducible polynomial позволяет построить new field как quotient polynomial ring.

Почему это логично

Если p(x) reducible, то его можно разложить:

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

где neither a(x) nor b(x) is a unit.

Тогда в quotient:

F[x] / <p(x)>

имеем:

p(x) = 0

то есть:

a(x)b(x) = 0

Но сами a(x) и b(x) не обязаны быть zero в quotient. Значит появляются zero divisors. А field не может иметь zero divisors. Поэтому reducible polynomial не даёт field.

Если polynomial irreducible

Если p(x) irreducible over F, то ideal:

<p(x)>

maximal. А значит quotient:

F[x] / <p(x)>

is a field.

Интуитивно:

quotient by irreducible polynomial добавляет relation p(x) = 0, но не создаёт zero divisors.

Именно поэтому irreducible polynomials играют роль prime numbers.

В integers:

Z / pZ

is a field, если p prime.

В polynomial rings:

F[x] / <p(x)>

is a field, если p(x) irreducible.

Polynomial analogue of Euclid’s lemma

Для prime numbers есть Euclid’s lemma:

p | ab => p | a or p | b

Для irreducible polynomials over a field есть аналог. Пусть F — field, и пусть:

p(x), a(x), b(x) ∈ F[x]

Если p(x) irreducible over F и:

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

то:

p(x) | a(x)

или:

p(x) | b(x)

То есть irreducible polynomial over a field behaves like a prime.

Почему это важно

Это делает F[x] очень похожим на integers. В Z prime numbers контролируют divisibility. В F[x] irreducible polynomials контролируют polynomial divisibility. Поэтому можно думать так:

prime number in Z

соответствует:

irreducible polynomial in F[x]

Constructing a field with eight elements

Теперь построим field with 8 elements.

Возьмём:

F = Z_2

и polynomial:

p(x) = x^3 + x + 1

в:

Z_2[x]

Чтобы quotient:

Z_2[x] / <x^3 + x + 1>

был field, нужно проверить, что p(x) irreducible over Z_2. Так как degree равна 3, достаточно проверить roots in Z_2. В Z_2 всего два элемента:

0, 1

Проверяем:

p(0) = 0^3 + 0 + 1 = 1

и:

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

Roots нет. Значит:

x^3 + x + 1

irreducible over Z_2.

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

Z_2[x] / <x^3 + x + 1>

is a field.

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

В quotient:

Z_2[x] / <x^3 + x + 1>

каждый element можно представить remainder degree меньше 3. То есть каждый element имеет вид:

ax^2 + bx + c

где:

a, b, c ∈ Z_2

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

0 or 1

Поэтому всего элементов:

2 · 2 · 2 = 8

То есть quotient field has 8 elements.

Список elements:

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

Как считать в этом field

В quotient:

Z_2[x] / <x^3 + x + 1>

мы считаем:

x^3 + x + 1 = 0

Значит:

x^3 = -x - 1

Но в Z_2:

-1 = 1

и:

-x = x

поэтому:

x^3 = x + 1

Это главное reduction rule. Если при multiplication появляется x^3 или higher power, мы заменяем:

x^3

на:

x + 1

Пример addition

Возьмём:

x^2 + x + 1

и:

x^2 + 1

Складываем:

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

В Z_2:

2 = 0

поэтому:

2x^2 + x + 2 = x

Значит:

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

Пример multiplication

Умножим:

(x^2 + x + 1)(x^2 + 1)

Раскрываем:

x^4 + x^3 + x + 1

Теперь используем relation:

x^3 + x + 1 = 0

Значит часть:

x^3 + x + 1

исчезает в quotient. Остаётся:

x^4

Теперь из:

x^3 = x + 1

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

x^4 = x^2 + x

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

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

в этом field.

Another example: field with nine elements

Рассмотрим:

Z_3[x] / <x^2 + 1>

Сначала проверим, что:

x^2 + 1

irreducible over Z_3.

В Z_3 элементы:

0, 1, 2

Проверяем roots:

0^2 + 1 = 1

1^2 + 1 = 2

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

Нуля нет. Так как degree равна 2, отсутствие roots означает irreducible. Значит:

Z_3[x] / <x^2 + 1>

is a field.

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

Каждый element quotient можно представить remainder degree меньше 2:

ax + b

где:

a, b ∈ Z_3

Для a есть 3 варианта, для b тоже 3.

Всего:

3 · 3 = 9

elements.

Relation with `Z_3[i]`

В quotient:

Z_3[x] / <x^2 + 1>

мы считаем:

x^2 + 1 = 0

то есть:

x^2 = -1

А в Z_3:

-1 ≡ 2

поэтому:

x^2 = 2

Это похоже на construction:

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

где:

i^2 = -1

То есть x в quotient играет роль i.

Поэтому:

Z_3[x] / <x^2 + 1>

is essentially the same field as:

Z_3[i]

General pattern: finite fields from irreducible polynomials

Если p — prime, то:

Z_p

is a field.

Если взять irreducible polynomial:

f(x) ∈ Z_p[x]

degree n, то quotient:

Z_p[x] / <f(x)>

is a field.

Каждый element quotient можно представить polynomial degree меньше n:

a_(n-1)x^(n-1) + ... + a_1x + a_0

где каждый coefficient лежит в:

Z_p

Для каждого coefficient есть p choices. Всего coefficients:

поэтому всего elements:

p^n

Так строятся finite fields with:

p^n

elements.

Почему это важно для crypto

В crypto часто работают with finite fields.

Prime fields:

F_p

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

Z_p

Но есть ещё extension fields:

F_(p^n)

Их можно строить как:

F_p[x] / <irreducible polynomial of degree n>

То есть irreducible polynomial задаёт relation, по которой мы сокращаем powers of x.

Например:

x^3 + x + 1 = 0

даёт field with 8 = 2^3 elements over Z_2.

Это уже не просто abstract algebra ради abstract algebra.

Это основа того, как строятся finite fields, которые дальше встречаются в coding theory, cryptography, elliptic curves и ZK systems.

Unique factorization in `Z[x]`

В конце главы появляется ещё одна важная мысль:

Z[x]

имеет unique factorization property. То есть polynomials with integer coefficients можно раскладывать на irreducible factors essentially uniquely. Это похоже на integers.

В Z любое nonzero nonunit число можно разложить на primes:

60 = 2 · 2 · 3 · 5

И это разложение unique up to order and signs.

В Z[x] происходит похожая история, только factors могут быть двух типов:

irreducible constant polynomials;
irreducible polynomials positive degree.

Units в `Z[x]`

В Z[x] units — это только:

и:

-1

Почему?

Чтобы polynomial был unit, у него должен быть multiplicative inverse inside Z[x]. Но если polynomial имеет positive degree, то при умножении degree обычно растёт, а не исчезает. А среди integer constants обратимы только:

1
-1

потому что:

1 · 1 = 1

и:

(-1)(-1) = 1

А, например:

не unit in Z[x], потому что:

1/2 not in Z[x]

Irreducible constants в `Z[x]`

Constant polynomial:

irreducible in Z[x], если p — prime number.

Например:

2
3
5
-2
-3
-5

are irreducible constant polynomials.

А:

не irreducible, потому что:

6 = 2 · 3

и neither 2 nor 3 is unit in Z[x].

Unique factorization in `Z[x]`

Theorem говорит:

every polynomial in Z[x] that is neither zero nor unit can be written as a product of irreducible polynomials, and this factorization is unique up to order and multiplication by ±1.

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

f(x) = p1(x)p2(x)...pm(x)

и:

f(x) = q1(x)q2(x)...qn(x)

где все factors irreducible, то на самом деле:

m = n

и после перестановки factors каждый pi(x) совпадает с соответствующим qi(x) up to sign:

pi(x) = ±qi(x)

Простой пример

Возьмём:

f(x) = 6x^2 - 6

Можно разложить:

6x^2 - 6 = 6(x^2 - 1)

Дальше:

6 = 2 · 3

и:

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

Получаем:

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

Это factorization into irreducibles in Z[x].

Можно переставить factors:

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

или вынести signs:

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

Но по сути это то же самое разложение.

Unique factorization разрешает такие изменения:

order of factors

и:

multiplication by units ±1

Но новых fundamentally different irreducible factors не появится.

Почему это важно

Unique factorization позволяет работать с polynomials почти как с integers. В integers primes являются “атомами” multiplication. В Z[x] irreducible polynomials играют похожую роль. Это важно для:

divisibility
factorization
irreducibility tests
quotient rings
finite fields

Если polynomial factorization не была бы unique, то многие рассуждения о divisibility ломались бы.

Weird dice: application of unique factorization

Есть красивое применение unique factorization к задаче про dice. Обычный кубик имеет faces:

1, 2, 3, 4, 5, 6

Если бросить два обычных кубика, суммы имеют распределение:

2: 1 way
3: 2 ways
4: 3 ways
5: 4 ways
6: 5 ways
7: 6 ways
8: 5 ways
9: 4 ways
10: 3 ways
11: 2 ways
12: 1 way

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

Encoding dice as polynomials

Обычный кубик можно encoded as polynomial:

D(x) = x + x^2 + x^3 + x^4 + x^5 + x^6

Почему так? Каждая face label становится exponent.

Face 1 даёт:

Face 2 даёт:

x^2

и так далее.

Если бросаем два кубика, нужно перемножить их polynomials:

D(x)D(x)

Тогда coefficient при:

x^k

показывает, сколькими способами можно получить sum k.

Например, term:

x^6

может появиться как:

x · x^5
x^2 · x^4
x^3 · x^3
x^4 · x^2
x^5 · x

То есть ровно 5 ways.

Sicherman dice

Оказывается, есть необычная пара dice, которая даёт те же probabilities sums, что и обычные dice. Одна die имеет labels:

1, 2, 2, 3, 3, 4

Другая:

1, 3, 4, 5, 6, 8

Эти dice называются:

Sicherman dice

Если бросать их вместе, distribution sums будет таким же, как у двух обычных dice.

Polynomial version of the problem

Для обычной пары dice:

D(x)^2
=
(x + x^2 + x^3 + x^4 + x^5 + x^6)^2

Для weird dice с labels:

a1, a2, a3, a4, a5, a6

и:

b1, b2, b3, b4, b5, b6

получаем polynomials:

A(x) = x^a1 + x^a2 + x^a3 + x^a4 + x^a5 + x^a6

и:

B(x) = x^b1 + x^b2 + x^b3 + x^b4 + x^b5 + x^b6

Чтобы weird dice давали те же probabilities, нужно:

A(x)B(x) = D(x)^2

То есть задача про dice превращается в задачу про factorization polynomials.

Factorization обычного dice polynomial

Сначала factor обычного dice polynomial:

D(x) = x + x^2 + x^3 + x^4 + x^5 + x^6

Выносим x:

D(x) = x(1 + x + x^2 + x^3 + x^4 + x^5)

А дальше:

1 + x + x^2 + x^3 + x^4 + x^5
=
(x + 1)(x^2 + x + 1)(x^2 - x + 1)

Поэтому:

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

Значит:

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

Теперь unique factorization says:

any factorization of D(x)^2 must use exactly these irreducible factors, just distributed between A(x) and B(x).

Как из этого появляются Sicherman dice

Каждый weird die polynomial должен быть product of some of these factors.

С учётом условий dice:

у каждого кубика должно быть 6 faces;
labels positive;
minimum sum должен быть 2;
coefficients должны быть nonnegative integers;
сумма coefficients polynomial должна быть 6.

В итоге possible dice polynomials сводятся к трём вариантам для одной die:

x + x^2 + x^3 + x^4 + x^5 + x^6

обычная die:

1, 2, 3, 4, 5, 6

или:

x + 2x^2 + 2x^3 + x^4

Sicherman die:

1, 2, 2, 3, 3, 4

или:

x + x^3 + x^4 + x^5 + x^6 + x^8

другая Sicherman die:

1, 3, 4, 5, 6, 8

Поэтому, кроме обычной пары dice, есть ровно одна nonstandard pair с тем же distribution:

1, 2, 2, 3, 3, 4

и:

1, 3, 4, 5, 6, 8

##Почему это вообще работает

Polynomial multiplication counts sums. Unique factorization restricts possible ways to split the ordinary dice polynomial product into two dice polynomials.

То есть algebra говорит:

если две dice имеют тот же sum distribution, их polynomials должны multiply to the same product.

А unique factorization говорит:

у этого product есть только ограниченное число ways to split irreducible factors.

Так мы получаем Sicherman dice and prove that no other positive integer-labeled dice pair works.

Reducible и irreducible polynomials

Reducible polynomial

Если coefficients берутся из field

Важно: irreducible depends on the base ring

Пример: 2x^2 + 4 over Q и over Z

Почему over Q иначе

Пример: 2x^2 + 4 over R и over C

Пример: x^2 - 2

Пример: x^2 + 1 over Z_3 и Z_5

Reducibility test for degrees 2 and 3

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

Почему это не работает так же для degree 4

Content of a polynomial

Примеры content

Primitive polynomial

Зачем нужен content

Gauss’s Lemma

Интуиция

Reducibility over Q and over Z

Почему это важно

Пример: rational factorization превращается в integer factorization

Mod p irreducibility test

Reduction modulo p

Mod p irreducibility test

Почему это полезно

Пример: cubic polynomial

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

Осторожно: converse не работает

Пример, где один prime не помогает

Polynomials with rational coefficients

Eisenstein’s criterion

Как читать условия Eisenstein

Пример Eisenstein

Cyclotomic polynomial for prime p

Почему здесь появляется Eisenstein

Почему irreducible polynomials важны

Irreducible polynomials and quotient fields

Почему это логично

Если polynomial irreducible

Polynomial analogue of Euclid’s lemma

Почему это важно

Constructing a field with eight elements

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

Как считать в этом field

Пример addition

Пример multiplication

Another example: field with nine elements

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

Relation with Z_3[i]

General pattern: finite fields from irreducible polynomials

Почему это важно для crypto

Unique factorization in Z[x]

Units в Z[x]

Irreducible constants в Z[x]

Unique factorization in Z[x]

Простой пример

Почему это важно

Weird dice: application of unique factorization

Encoding dice as polynomials

Sicherman dice

Polynomial version of the problem

Factorization обычного dice polynomial

Как из этого появляются Sicherman dice

##Почему это вообще работает

Пример: `2x^2 + 4` over `Q` и over `Z`

Почему over `Q` иначе

Пример: `2x^2 + 4` over `R` и over `C`

Пример: `x^2 - 2`

Пример: `x^2 + 1` over `Z_3` и `Z_5`

Reducibility over `Q` and over `Z`

Mod `p` irreducibility test

Reduction modulo `p`

Mod `p` irreducibility test

Cyclotomic polynomial for prime `p`

Relation with `Z_3[i]`

Unique factorization in `Z[x]`

Units в `Z[x]`

Irreducible constants в `Z[x]`

Unique factorization in `Z[x]`