Как найти минимальный многочлен элемента поля

From Wikipedia, the free encyclopedia

In field theory, a branch of mathematics, the minimal polynomial of an element α of a field extension is, roughly speaking, the polynomial of lowest degree having coefficients in the field, such that α is a root of the polynomial. If the minimal polynomial of α exists, it is unique. The coefficient of the highest-degree term in the polynomial is required to be 1.

More formally, a minimal polynomial is defined relative to a field extension E/F and an element of the extension field E/F. The minimal polynomial of an element, if it exists, is a member of F[x], the ring of polynomials in the variable x with coefficients in F. Given an element α of E, let J_α be the set of all polynomials f(x) in F[x] such that f(α) = 0. The element α is called a root or zero of each polynomial in J_α

More specifically, J_α is the kernel of the ring homomorphism from F[x] to E which sends polynomials g to their value g(α) at the element α. Because it is the kernel of a ring homomorphism, J_α is an ideal of the polynomial ring F[x]: it is closed under polynomial addition and subtraction (hence containing the zero polynomial), as well as under multiplication by elements of F (which is scalar multiplication if F[x] is regarded as a vector space over F).

The zero polynomial, all of whose coefficients are 0, is in every J_α since 0αⁱ = 0 for all α and i. This makes the zero polynomial useless for classifying different values of α into types, so it is excepted. If there are any non-zero polynomials in J_α, i.e. if the latter is not the zero ideal, then α is called an algebraic element over F, and there exists a monic polynomial of least degree in J_α. This is the minimal polynomial of α with respect to E/F. It is unique and irreducible over F. If the zero polynomial is the only member of J_α, then α is called a transcendental element over F and has no minimal polynomial with respect to E/F.

Minimal polynomials are useful for constructing and analyzing field extensions. When α is algebraic with minimal polynomial f(x), the smallest field that contains both F and α is isomorphic to the quotient ring F[x]/⟨f(x)⟩, where ⟨f(x)⟩ is the ideal of F[x] generated by f(x). Minimal polynomials are also used to define conjugate elements.

Definition[edit]

Let E/F be a field extension, α an element of E, and F[x] the ring of polynomials in x over F. The element α has a minimal polynomial when α is algebraic over F, that is, when f(α) = 0 for some non-zero polynomial f(x) in F[x]. Then the minimal polynomial of α is defined as the monic polynomial of least degree among all polynomials in F[x] having α as a root.

Properties[edit]

Throughout this section, let E/F be a field extension over F as above, let α ∈ E be an algebraic element over F and let J_α be the ideal of polynomials vanishing on α.

Uniqueness[edit]

The minimal polynomial f of α is unique.

To prove this, suppose that f and g are monic polynomials in J_α of minimal degree n > 0. We have that r := f−g ∈ J_α (because the latter is closed under addition/subtraction) and that m := deg(r) < n (because the polynomials are monic of the same degree). If r is not zero, then r / c_m (writing c_m ∈ F for the non-zero coefficient of highest degree in r) is a monic polynomial of degree m < n such that r / c_m ∈ J_α (because the latter is closed under multiplication/division by non-zero elements of F), which contradicts our original assumption of minimality for n. We conclude that 0 = r = f − g, i.e. that f = g.

Irreducibility[edit]

The minimal polynomial f of α is irreducible, i.e. it cannot be factorized as f = gh for two polynomials g and h of strictly lower degree.

To prove this, first observe that any factorization f = gh implies that either g(α) = 0 or h(α) = 0, because f(α) = 0 and F is a field (hence also an integral domain). Choosing both g and h to be of degree strictly lower than f would then contradict the minimality requirement on f, so f must be irreducible.

Minimal polynomial generates J_α[edit]

The minimal polynomial f of α generates the ideal J_α, i.e. every g in J_α can be factorized as g=fh for some h’ in F[x].

To prove this, it suffices to observe that F[x] is a principal ideal domain, because F is a field: this means that every ideal I in F[x], J_α amongst them, is generated by a single element f. With the exception of the zero ideal I = {0}, the generator f must be non-zero and it must be the unique polynomial of minimal degree, up to a factor in F (because the degree of fg is strictly larger than that of f whenever g is of degree greater than zero). In particular, there is a unique monic generator f, and all generators must be irreducible. When I is chosen to be J_α, for α algebraic over F, then the monic generator f is the minimal polynomial of α.

Examples[edit]

Minimal polynomial of a Galois field extension[edit]

Given a Galois field extension the minimal polynomial of any not in can be computed as

if has no stabilizers in the Galois action. Since it is irreducible, which can be deduced by looking at the roots of , it is the minimal polynomial. Note that the same kind of formula can be found by replacing with where is the stabilizer group of . For example, if then its stabilizer is , hence is its minimal polynomial.

Quadratic field extensions[edit]

Q(√2)[edit]

If F = Q, E = R, α = √2, then the minimal polynomial for α is a(x) = x² − 2. The base field F is important as it determines the possibilities for the coefficients of a(x). For instance, if we take F = R, then the minimal polynomial for α = √2 is a(x) = x − √2.

Q(√d)[edit]

In general, for the quadratic extension given by a square-free , computing the minimal polynomial of an element can be found using Galois theory. Then

in particular, this implies and . This can be used to determine through a series of relations using modular arithmetic.

Biquadratic field extensions[edit]

If α = √2 + √3, then the minimal polynomial in Q[x] is a(x) = x⁴ − 10x² + 1 = (x − √2 − √3)(x + √2 − √3)(x − √2 + √3)(x + √2 + √3).

Notice if then the Galois action on stabilizes . Hence the minimal polynomial can be found using the quotient group .

Roots of unity[edit]

The minimal polynomials in Q[x] of roots of unity are the cyclotomic polynomials.

Swinnerton-Dyer polynomials[edit]

The minimal polynomial in Q[x] of the sum of the square roots of the first n prime numbers is constructed analogously, and is called a Swinnerton-Dyer polynomial.

See also[edit]

• Ring of integers
• Algebraic number field
• Minimal polynomials of

References[edit]

• Weisstein, Eric W. «Algebraic Number Minimal Polynomial». MathWorld.
• Minimal polynomial at PlanetMath.
• Pinter, Charles C. A Book of Abstract Algebra. Dover Books on Mathematics Series. Dover Publications, 2010, p. 270–273. ISBN 978-0-486-47417-5

Возвращаясь
к многочленам f(x)
= x⁴+x+1
и f^*(x)
= x⁴+x³+1,
отмечаем , что всё сказанное относительно
двойственных многочленов справедливо
для этих многочленов.

1.
Корни f(x)
– α¹,
α²,
α⁴,
α⁸
и корни f^*(x)
– α⁷,
α¹¹,
α¹³,
α¹⁴
являются элементами поля GF(2⁴).
Справедливо:

α¹
α¹⁴
= α¹⁵
= 1; α²
α¹³
= α¹⁵
= 1; α⁴
α¹¹
= α¹⁵
= 1;α⁸
α⁷
= α¹⁵ =
1.

2.
f(x)
и f^*(x)
– неприводимые многочлены, при этом

f7(x)
= x⁴f1(1/x)
= x⁴(1+.

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

Проверить
этот факт можно непосредственным
делением х⁵+1,
х⁶+1
и т.д. на многочлены f1(x)
и f7(x).
Найдем двучлен минимальной степени,
делителем которого является f1(x)f7(x)
= f17(x)
=

=
(x⁴+x+1)(x⁴⁺x³+1)
= x⁸+x⁷+x⁵+x⁴+x³+x+1.

Воспользуемся
приемом [4], который эффективнее, чем
последовательное деление х⁹+1,
х¹⁰+1
и т.д. на f17(x).

Будем
искать одночлен хⁿ
остаток от деления которого на f17(x)
равен 1.

Остаток
от деления х⁸
на f17(x):

X⁸
= x⁷+x⁵+x⁴+x³+x+1
(mod f17(x));

X⁹
= x⁸+x⁶+x⁵+x⁴+x²+x
=

=
x⁷+x⁵+x⁴+x³+x+1+x⁶+x⁵+x⁴+x²+x
=

=
x⁷+x⁶+x³+x²+1
(mod f17(x));

X¹⁰
= x⁸+x⁷+x⁴+x³+x
=

=
x⁷+x⁵+x⁴+x³+x+1+x⁷+x⁴+x³+x
=

=
x⁵+1
(mod f17(x));

X¹¹
= x⁶+x
(mod f17(x));

X¹²
= x⁷+x²
(mod f17(x));

X¹³
= x⁸+x³
= x⁷+x⁵+x⁴+x³+x+1+x³
=

=
x⁷+x⁵+x⁴+x+1
(mod f17(x));

X¹⁴
= x⁸+x⁶+x⁵+x²+x
=

=
x⁷+x⁵+x⁴+x³+x+1+x⁶+x⁵+x²+x
=

=
x⁷+x⁶+x⁴+x³+x²+1
(mod f17(x));

X¹⁵
= x⁸+x⁷+x⁵+x⁴+x³+x
=

=x⁷+x⁵+x⁴+x³+x+1+x⁷+x⁵+x⁴+x³+x
= 1(mod f17(x)).

Итак
х¹⁵+1
– двучлен минимальной степени сомножителем
которого является (х⁴+х+1)(х⁴+х³+1).

2.2.Минимальные
многочлены и их свойства

Выше
было показано, что между корнями х^q-x
и элементами GF(q),
где q
= p^m
существует однозначное соответствие,
заключающееся в том, что каждый элемент
β из GF(q)
является корнем х^q-х.

При
этом коэффициенты многочлена х^q-x
и его неприводимых сомножителей являются
элементами поля GF(q).Элемент
β, являясь корнем
х^q-х,
является корнем одного из его сомножителей.

Минимальным многочленом элемента β из поля GF(pm) называют нормированный многочлен минимальной степени m(x) с коэффициентами из поля GF(p), такой, что m(β) = 0.

Пример2.2.1.
Для элементов поля GF(2⁴)
минимальными многочленами являются:

Элемент Минимальный
многочлен

1. х,

2. х+1,

α х⁴+х+1,

α^-1
= α¹⁴ х⁴+х³+1,

α³ х⁴+х³+х²+х+1,

α⁵ х²+х+1.

Процесс
нахождения минимальных многочленов
будет обобщен в §2.4.

2.3. Свойства минимальных многочленов над полем gf(p)

1.

Минимальный многочлен неприводим.

Действительно,
если m(x)
= m1(x)m2(x),
то m(β)
= m1(β)m2(β)
= 0, так что либо m1(β)
= 0, либо m2(β)
= 0, что противоречит определению.

2.

Если некоторый многочлен f(x) с коэффициентами из GF(p) такой что f(β) = 0, то минимальный многочлен m(x) для β делит f(x).

Из
этого
вытекает:

3.

Минимальный многочлен m(x) степени m является делителем X-X.

Из
этого следует, что

4.

Степени минимальных многочленов m(x) для элементов поля GF(pm) не превышают m.

С
учетом сказанного:

5.

Если корень β является примитивным элементом GF(pm), то m(x) для β имеет степень, равную m.

6.

Как
найти m(x)
минимальный многочлен для β = αⁱ
из GF(p^m)
?

Если
i
лежит в циклотомическом классе C_S(P^m_-1)
, то

Из
свойства 3 непосредственно следует

7.

где
s
пробегает всё множество представителей
циклотомических классов по модулю p^m-1.

Полученный
результат конкретизирует свойство 5
§2.1.

Пример
2.3.1. В
соответствии с данными Примера 2.2.1
произведение всех минимальных многочленов
для элементов поля GF(2⁴)
равно:

х(х+1)(х⁴+х+1)(х⁴+х³+1)(х⁴+х³+х²+х+1)(х²+х+1)
= х¹⁶+х,
откуда (х+1)(х⁴+х+1)(х⁴+х³+1)(х⁴+х³+х²+х+1)(х²+х+1)
= х¹⁵+1.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Сообщения без ответов | Активные темы | Избранное

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения

Пусть $%x=sqrt{q}+sqrt[4]p$%. Тогда $%(x-sqrt{q})^2=sqrt{p}$%, то есть $%x$% будет корнем уравнения $%x^2+q-sqrt{p}=2xsqrt{q}$%. После возведения в квадрат ещё раз, получится $%x^4+2(q-sqrt{p})x^2+q^2+p-2qsqrt{p}=4x^2q$%, и возникает уравнение 4-й степени $%x^4-2(q+sqrt{p})x^2+q^2+p-2qsqrt{p}=0$%.

Этим описывается общая ситуация. Данный многочлен в отдельных случаях может не быть минимальным. Однако в условии про значения $%p$% и $%q$% не сказано даже то, что они рациональны, поэтому анализировать все случаи представляется нецелесообразным. Ясно, например, что при $%p=q=1$% минимальный многочлен будет иметь степень 1. Если $%q$% является квадратом рационального числа, то $%x$% выражается как корень квадратного уравнения, и так далее. Но раз само условие дано без уточнений, то и в решении детально ничего уточнять не будем.