ОТЧЕТ

По учебно-компьютерной практике

по алгебре

 

 

 

Оглавление

 

Введение…………….. …………………………………………………………………………………………………….3

1 Основные понятия теории многочленов……………………………………………………………….4

2 Признаки неприводимости многочленов..……………………………………………………………7

            2.1 Признак Эйзенштейна………………………………………………………………………………….7

          2.2 Признак Дюма………………………………………………………………………………………………...8

          2.3 Признак Перрона……………………………………………………………………………………………12

3 Алгоритм проверки неприводимости многочлена………………………………………………13

Список литературы………………………………………………………………………………………………….. .14

Приложение А……………………………………………………………………………………………………………15

Приложение В(таблицы неприводимых многочленов)…………………………………………..16

 

Введение

 

          В математике, многочлены или полиномы от одной переменной — функции вида  где c_i фиксированные коэффициенты, а x — переменная. Многочлены составляют один из важнейших классов элементарных функций.
         Изучение полиномиальных уравнений и их решений составляло едва ли не главный объект «классической алгебры». С изучением многочленов связан целый ряд преобразований в математике: введение в рассмотрение нуля, отрицательных, а затем и комплексных чисел, а также появление теории групп как раздела математики и выделение классов специальных функций в анализе.

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

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

 

 

1 Основные понятия теории многочленов

 

         Пусть f и g — многочлены с коэффициентами из поля к. Говорят, что многочлен f делится на многочлен g, если f = gh_, где h— некоторый многочлен (с коэффициентами из поля к).

         Многочлен d называют общим делителем многочленов fug, если f и g делятся на d. Общий делитель d многочленов f и g называют наибольшим общим делителем многочленов fug, если он делится на любой общий делитель многочленов f и g. Ясно, что наибольший общий делитель определен однозначно с точностью до умножения на ненулевой элемент поля к.

          Наибольший общий делитель d = (f,g) многочленов f и g можно найти с помощью следующего алгоритма Евклида.  Для определенно­сти будем считать, что deg f > deg g. Пусть r₁ —остаток от деления f на g ,r₂ — остаток от деления g на r₁,…,r_k+1—остаток от деления r_k-1 на r_k. Степени многочленов r_i строго убывают, поэтому для неко­торого n получим r_n+1 = 0, т.е. r_n-1 делится на r_n.  При этом fиg делятся на r_n, так как на r_n делятся многочлены r_n-1, r_n-2,… Кроме того, если f и g делятся на некоторый многочлен h, то rn  делится на h, так как на h делятся многочлены r₁, r₂,… Таким образом, r_n = (f, g).

           Непосредственно из алгоритма Евклида вытекают важные след­ствия, которые формулируются в виде отдельной теоремы.

             Теорема 1.1. а) Если d — наибольший общий делитель многочленов f и g, то найдутся такие многочлены а и b, что d = af + bg.

    Б) Пусть f и g многочлены над полем к   К. Тогда если у многочле­нов f и g есть нетривиальный общий делитель над полем К, то у них есть нетривиальный общий делитель и над полем к.

            Многочлен f с коэффициентами из кольца к называют приводимым над к, если f = gh, где g и h — многочлены положительной степени с ко­эффициентами из кольца к. В противном случае многочлен f называют неприводимым над к.

           Пусть f = f₁*…*f_s — некоторое разложение многочлена f над по­лем к на множители f₁,…,f_s,  являющиеся многочленами над полем к. От разложения на множители с произвольными коэффициентами можно перейти к разложению со старшим коэффициентом 1. В самом деле, если f_i(x) = a_ixⁱ +… — многочлен над полем к, то g_i = а_i^-1f_i — тоже много­член над полем к, причем его старший коэффициент равен 1. Поэтому разложение f = f₁*…f_s можно заменить на разложение f = ag₁*…g_s, где а = a₁*…а_s.

            Теорема 1.2. Пусть к — поле. Тогда у многочлена f    k[x] есть разложение на неприводимые множители, причем это разложение един­ственно.

              Доказательство. Существование разложения легко доказывается индукцией по n = deg f. Прежде всего отметим, что для неприводимого многочлена f требуемое разложение состоит из самого многочлена f. При n = 1 многочлен f неприводим. Пусть разложение существует для любого многочлена степени меньше n и f — многочлен степени n. Мож­но считать, что многочлен f неприводим, т.е. f = gh, где deg g < п и deg h < n. Но тогда разложения для g и h существуют по предположе­нию индукции.

             Докажем теперь единственность разложения. Пусть ag₁*…g_s = bh₁*…h_t, где a, b  к и g₁,…, g_s1 h1,…, ht — неприводимые мно­гочлены над к со старшим коэффициентом 1. Ясно, что в таком случае а = b. Многочлен g₁ …g_s делится на неприводимый многочлен h₁. Это означает, что один из многочленов g₁,…,g_s делится на h₁. Чтобы убе­диться в этом, достаточно доказать следующее вспомогательное утвер­ждение.

               Лемма. Если многочлен qr делится на неприводимый многочлен р, то один из многочленов q и г делится на р.

             Доказательство. Пусть многочлен q не делится на р. Тогда (р, q) = 1, т. Е. существуют такие многочлены a и b, что ap + bq = 1. Умножив обе части этого равенства на г, получим apr + bqr = г. Многочлены рr и qr делятся на р, поэтому r делится на р.                                                                              □

           Пусть для определенности g_i делится на h₁. Учитывая, что g₁ и h₁ — неприводимые многочлены со старшим коэффициентом 1, получаем g₁ = h₁. Сократим обе части равенства g₁*…*g_s = h₁*…h_t на g₁ = h₁. После нескольких таких операций получим s = t и g1 = h_i,…g_s = h_is,  где {i₁,…,i_s} = {1,…,s}.

              Для кольца целых чисел Z неприводимость многочленов определя­ется точно так же, как и в случае поля, т. Е. многочлен f     Z[x] непри­водим над Z, если его нельзя представить в виде произведения много­членов положительной степени с целыми коэффициентами. Но в случае кольца не всегда можно поделить коэффициенты многочлена на стар­ший коэффициент; можно лишь поделить коэффициенты на наибольший общий делитель всех коэффициентов. Это приводит к следующему опре­делению. Пусть f(x) =       , где a_i   Z. Наибольший общий делитель коэффициентов а₀,… ,а_n называют содержанием многочлена f. Содер­жание многочлена f обозначают cont(f). Ясно, что f(х) = cont(f)g(x)_t где g — многочлен над Z с содержанием 1.

              Лемма (Гаусс).  Cont(fg) = cont(f)cont(g).

              Доказательство. Достаточно рассмотреть случай, когда cont(f)= cont (g)= 1. В самом деле, коэффициенты многочленов f, g и fg можно разделить на cont(f), cont(g) и cont(fg), соответственно.

            Пусть f(х) =     , g(х) =  , fg(x) =   . Предположим, что cont(fg) = d > 1 и р— простой делитель числа d. Тогда все коэф­фициенты многочлена fg делятся на р, а у многочленов fug есть ко­эффициенты, не делящиеся на р. Пусть a — первый коэффициент мно­гочлена f, не делящийся на р, b_s — первый коэффициент многочлена g, не делящийся на р. Тогда

   

    так как

     Получено противоречие.                                        

 

2 Признаки неприводимости многочленов

2.1 Признак Эйзенштейна

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

             Теорема 2.1.3 (признак Эйзенштейна). Пусть f(x) =a₀ + a₁*x + …+ a_nx_n – многочлен с целыми коэффициентами, причем для некоторого простого числа р коэффициент аn не делится на р, коэффициенты а₀,…,а_n-1 делятся на р, но коэффициент а₀ не делится на р². Тогда f – неприводимый многочлен.

              Доказательство. Предположим, что

 

     Причем g и h – многочлены положительной степени с целыми коэффициентами. Число b₀c₀ = a₀ делится на р, поэтому одно из чисел b₀ и c₀   делится на р. Пусть, для определенности, Ь_о делится на р. Тогда со не де­лится на р, так как а_о = Ь_ос_о не делится на р². Если все числа b_i делятся на р, то а_п делится на р. Поэтому b_i не делится на р при некотором i, где 0 <i  < deg g < n; можно считать, что i — наименьший номер чи­сла b_i, не делящегося на р. С одной стороны, по условию число аi делится на р. С другой стороны, a_i = b_ic₀+b_i-1c₁+ ... + b_oc_i, причем все числа  b_i-1c₁,..., b₀c_i  делятся на р, а число b_ic_о не делится на р. Получено противоречие.  

              Пример 2.1.1. Пусть р—простое число, а число q не делится на р. Тогда многочлен х^т - pq неприводим над Z.

              Пример 2.1.2. Если р — простое число, то многочлен   f(x) = х^р-1 + + х^р-² +... + х +1 неприводим.

          В самом деле, к многочлену

 

 можно применить признак Эйзенштейна.

 

2.2 Признак Дюма

 

          Пусть р—фиксированное простое число,                   — многочлен с целыми коэффициентами, причем A₀A_n ≠ 0. Запишем ненулевые коэффициенты многочлена f в виде A_i  = a_ip^ai   ,где a_i — целое число, не делящееся на р. Каждому ненулевому коэффициенту  a_ip^ai  сопоста­вим точку на плоскости с координатами (i,а_i). По этим точкам можно построить диаграмму Ньютона многочлена f (соответствующую про­стому числу р). Делается это следующим образом. Пусть Р₀ = (0,а₀) и P₁ = (i₁, a_i1), где i₁ — наибольшее целое число, для которого ниже прямой Р₀Р₁ нет данных точек. Пусть,  далее, Р₂ = (i₂, a_i2), где i₂ - наибольшее целое число, для которого ниже прямой P₁P₂ нет данных точек и т.д. (рис. 1). Самый последний отрезок имеет вид P_r-iP_r, где Р_r = (n, a_n). Если звенья ломаной Р₀...Р_r  проходят через точки с це­лочисленными координатами, то все эти точки мы тоже считаем вер­шинами ломаной. При этом к вершинам Р₀,..., Р_г добавляется еще    s ≥ 0 вершин . Полученную в результате ломанную Q₀…Q_r+s называют диаграммой Ньютона (здесь Q₀ =P₀ и Q_r+s = P_r). Отрезки P_iP_i+1 и Q_iQ_i+1 будем называть , соответственно, сторонами и звеньями диаграммы Ньютона.

Рис. 1

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

            Теорема 2.2.1 (Дюма). Пусть f = gh, где f, g, h – многочлены с целыми коэффициентами. Тогда система векторов звеньев для многочлена f представляет собой объединение систем векторов звеньев для g и h. (Простое число р для всех многочленов берется одно и тоже)

           Доказательство. Пусть

 

    (числа a_i, b_j, c_k не делятся на р). Возьмем некоторую сторону P_iP_i+1 диаграммы Ньютона многочлена f(сторона P_iP_i+1 может состоять из нескольких звеньев диаграммы Ньютона). Пусть точки P_i и P_i+1 имеют соответственно координаты (i_, a_{i_}) и (i₊, a_i+). Наклон стороны  P_iP_i+1  равен

 

      Пусть  a_i+ - a_{i_} = At и i₊ - i_ = It, где t>0 – наибольший общий делитель чисел a_i+ - a_{i_} и i₊ - i_. Тогда М = A/I, причем (A, I) = 1.

             Рассматриваемая сторона P_iP_i+1  диаграммы Ньютона лежит на прямой Ia-Ai=F, где F=Ia_i+-Ai₊=Ia_{i_}-Ai_. По условию все точки (I, a_i), I = 0,1…,n, лежат не ниже прямой, т.е. Ia_i-Ai ≥ F, причем это неравенство строгое при i < i_ и при i >i₊ . Будем на­зывать число Ia_i - Ai весом монома ap^axⁱ, где (а,р) = 1. Числа i_ и i₊ однозначно определяются как наименьший и наибольший показатели степени х мономов многочлена f с минимальным весом.

              Для многочлена g рассмотрим величину

G = min {Iβ_j-Aj}, j=0,…,m

     и определим j_ и j₊ как наименьший и наибольший индексы, для кото­рых

G = Iβ_{j_}-Aj_=Iβ_j+-Aj₊.

     Аналогично для многочлена h рассмотрим величину

H = min {Iγ_k-Ak}, k=0,…,n-m

    и определим k_ и k₊ как наименьший и наибольший индексы, для кото­рых

H = Iγ_{k_}-Ak_=Iγ_k+-Ak₊.

          Ясно, что

 

     Вес произведения двух членов равен сумме их весов, поэтому вес слага­емого с j = j_- и к = к_- равен G + Н. Веса всех остальных слагаемых строго больше G + Н, так как для них j < j_- или к < к_. В самом деле, пусть, например, j < j_. Тогда вес члена b_jp^βjx^j строго больше G, а вес члена c_kp^γkx^k не меньше H.

            Вес члена (b_jp^βjx^j)( c_kp^γkx^k) при j + к = const монотонно возрастает с возрастанием β_j+γ_k, поскольку I > 0. В рассматриваемом случае j + к = j_ + к_, поэтому сумма β_j+γ_k строго минимальна при j = j_ и  к = к_. Следовательно, вес члена  a_{j_+k_}p^aj_+k_    равен G + H. Ясно также, что при i < j_ + к_ вес члена а_iр^aixⁱ строго больше G + H, а при i ≥ j_ + k_ вес члена а_iр^aixⁱ   не меньше G + H. Следовательно. G + H = F и j_+k_ = i_. Аналогично доказывается, что j₊+k₊=i₊. Таким образом,

i₊ - i_-=(j₊ - j_-) + (k₊ - k_-). (1)

    В частности, одно из чисел j₊ - j_- и k₊ - k_- отлично от нуля.

             Если оба числа j₊ - j_- и k₊ - k_- отличны от нуля, то отрезок с кон­цами     (j_, β_{j_}) и (j₊,β_j+) является стороной диаграммы Ньютона мно­гочлена g, а отрезок с концами (k_, γ_{j_}) и (k₊,γ_k+) является стороной диаграммы Ньютона мно­гочлена h. Наклон сторон в обоих случаях равен M = A/I, так как

 

     Соотношение (1) показывает, что сумма длин сторон с наклоном М диаграмм Ньютона многочленов g и h равна длине стороны( с тем же самым наклоном М) диаграммы Ньютона многочлена f.

              Если же одно из чисел j₊ - j_- и k₊ - k_-  равно нулю, то у диаграммы Ньютона одного из многочленов g и h есть сторона с наклоном М, причем ее длина равна длине стороны диаграммы Ньютона многочлена f, а у диаграммы Ньютона другого многочлена сторон с наклоном М нет.

              Итак, вектор стороны с наклоном М диаграммы Ньютона многочлена f равен сумме векторов сторон с тем же наклоном М диаграмм Ньютона многочленов g и h. Соотношение (1) показывает, что если у одной из диаграмм Ньютона многочленов g и h есть сторона с некоторым наклоном М, то у диаграммы Ньютона многочлена f тоже должна быть сторона с таким наклоном.

                Следствие(Признак Дюма). Если для некоторого простого числа р диаграмма Ньютона многочлена f состоит ровно из одного звена(т.е. состоит из отрезка, внутри которого нет точек с целочисленными координатами), то многочлен f неприводим.

                Пример 2.2.1. Пусть р—простое число, (с,р) = 1 и (m,n) = 1. Тогда многочлен хⁿ + ср^т неприводим.

              Доказательство. Диаграмма Ньютона рассматриваемого много­члена представляет собой отрезок с концами (0, m) и (n, 0). Из условия (m, n) = 1 следует, что внутри этого отрезка нет точек с целочислен­ными координатами.                                                                                               

 

 

 

2.3 Признак Перрона

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

           Теорема 2.3.1 Пусть f(x) = xⁿ + a₁x^n-1 +... + a_n — многочлен с целыми коэффициентами, причем а_п ≠ 0.

    а)           Если | a₁| > 1 + | a₂| + … + | a_n|, то многочлен f неприводим.

    б)          Если | a₁|  ≥ 1 + | a₂| + ... + | a_n|  и f(±1) ≠ 0, то многочлен f непри­водим.

           Доказательство, а) Проверим сначала, что все корни много­члена f, за исключением ровно одного корня, лежат строго внутри единичного круга |z| ≤ 1. Ясно, что требуемым свойством обла­дает многочлен g(x) = х^п + a₁x^n-1, поэтому согласно теореме Руше достаточно доказать, что при |z| = 1 выполняется неравенство |f(z)-g(z)|< |f(z)| + |g(z)|. Но при \z\ = 1, с одной стороны,

|f(z)-g(z)|= | a₂z^n-2 +... + a_n |≤| a₂| + … + | a_n|<| a₁|  -1,    (1)

    а с другой стороны

|f(z) |+|g(z)|≥ |g(z)|= | zⁿ +a₁z^n-1 |=|z+ a₁| ≥| a₁|  -1.    (2)

            Предположим, что многочлен f можно представить в виде произведения многочленов f₁ и f₂ положительной степени с целыми коэффициентами. Произведение корней каждого из многочленов f₁ и f₂ – целое число, не равное нулю, поэтому у каждого из этих многочленов есть корень, модуль которого не меньше 1. Но у многочлена f есть лишь один такой корень. Приходим к противоречию.

          б) В случае | a₁|  = 1 + | a₂| + ... + | a_n|  неравенство (1) становится нестрогим. Но при условии f(±1) ≠ 0  становится строгим неравенство (2). В самом деле, при | z|  = 1 равенство

|f(z) |+|g(z)|= |a₁|  -1

    возможно лишь в том случае, когда одновременно выполняются равенства |f(z) |=0 и |z+ a₁| ≥| a₁|  -1.  Последнее равенство может выполняться лишь в том случае, когда z   R. А так как   |z|  = 1, то z = ±1.

 

Алгоритм

 

1. Вводим многочлен, который требуется проверить.
2. Подставляем во введенном многочлене вместо неизвестных все элементы конечного поля до тех пор пока мы не получим верное равенство. Если после подстановки мы получили верное равенство, значит многочлен приводим. Если после подстановки всех возможных значений мы не получили равенства, то переходим к шагу 3.
3. По методу неопределенных коэффициентов находим разложение многочлена на более простые. Если такого разложения не было найдено, то можно сделать вывод: многочлен неприводим.

 
Список литературы

 

1. Лидл Р., Пильц Г. Прикладная абстрактная алгебра.
2. Лидл Р., Нидеррайтер Г. Конечные поля.
3. Нечаев В.И. Элементы криптографии.
4. Прасолов В.В. Многочлены.

 

 

 

Приложение А

 

 (Таблицы неприводимых многочленов)

          В данном приложении приведены таблицы неприводимых многочленов  малых степеней n над  для малых простых p. Многочлены сокращенно указываются вектором коэффициентов . Столбец  указывает порядок многочлена.

n=1
10
11	1

     Для p=2:

n=6
1000011	63
1001001	9
1010111	21
1011011	63
1100001	63
1100111	63
1101101	63
1110011	63
1110101	21

 

n=7
10000011	127
10001001	127
10001111
10010001	127
10011101	127
10100111	127
10101011	127
10111001	127
10111111	127
11000001	127
11001011	127
11010011	127
11010101	127
11100101	127
11101111	127
11110001	127
11110111	127
11111101	127

 

n=8
100011011	51
100011101	255
100101011	255
100101101	255
100111001	17
100111111	85
101001101	255
101011111	255
101100011	255
101100101	255
101101001	255
101110001	255
101110111	85
101111011	85
110000111	255
110001011	85
110001101	255
110011111	51
110100011	85
110101001	255
110110001	51
110111101	85
111000011	255
111001111	255
111010111	17
111011101	85
111100111	255
111110011	51
111110101	255
111111001	85

 

 

 

 

 

 

 

 

n=2
111	3

 

 

 

n=5
100101	31
101001	31
101111	31
110111	31
111011	31
111101	31

 

n=3
1011	7
1101	7

 

Скачать: otchet-po-praktike-2010.doc