ОТЧЕТ По учебно-компьютерной практике по алгебре

0

 

 

ОТЧЕТ

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

по алгебре

 

 

 

Оглавление

 

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

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

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

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

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

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

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

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

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

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

 


Введение

 

          В математике, многочлены или полиномы от одной переменной — функции вида  где ci фиксированные коэффициенты, а 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. Пусть r1 —остаток от деления f на g ,r2 — остаток от деления g на r1,…,rk+1—остаток от деления rk-1 на rk. Степени многочленов ri строго убывают, поэтому для неко­торого n получим rn+1 = 0, т.е. rn-1 делится на rn.  При этом fиg делятся на rn, так как на rn делятся многочлены rn-1, rn-2,… Кроме того, если f и g делятся на некоторый многочлен h, то rn  делится на h, так как на h делятся многочлены r1, r2,… Таким образом, rn = (f, g).

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

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

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

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

           Пусть f = f1*…*fs — некоторое разложение многочлена f над по­лем к на множители f1,…,fs,  являющиеся многочленами над полем к. От разложения на множители с произвольными коэффициентами можно перейти к разложению со старшим коэффициентом 1. В самом деле, если fi(x) = aixi +… — многочлен над полем к, то gi = аi-1fi — тоже много­член над полем к, причем его старший коэффициент равен 1. Поэтому разложение f = f1*…fs можно заменить на разложение f = ag1*…gs, где а = a1*…а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 существуют по предположе­нию индукции.

             Докажем теперь единственность разложения. Пусть ag1*…gs = bh1*…ht, где a, b  к и g1,…, gs1 h1,…, ht — неприводимые мно­гочлены над к со старшим коэффициентом 1. Ясно, что в таком случае а = b. Многочлен g1 …gs делится на неприводимый многочлен h1. Это означает, что один из многочленов g1,…,gs делится на h1. Чтобы убе­диться в этом, достаточно доказать следующее вспомогательное утвер­ждение.

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

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

           Пусть для определенности gi делится на h1. Учитывая, что g1 и h1 — неприводимые многочлены со старшим коэффициентом 1, получаем g1 = h1. Сократим обе части равенства g1*…*gs = h1*…ht на g1 = h1. После нескольких таких операций получим s = t и g1 = hi,…gs = his,  где {i1,…,is} = {1,…,s}.

              Для кольца целых чисел Z неприводимость многочленов определя­ется точно так же, как и в случае поля, т. Е. многочлен f     Z[x] непри­водим над Z, если его нельзя представить в виде произведения много­членов положительной степени с целыми коэффициентами. Но в случае кольца не всегда можно поделить коэффициенты многочлена на стар­ший коэффициент; можно лишь поделить коэффициенты на наибольший общий делитель всех коэффициентов. Это приводит к следующему опре­делению. Пусть f(x) =       , где ai   Z. Наибольший общий делитель коэффициентов а0,… ,а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, не делящийся на р, bs — первый коэффициент многочлена g, не делящийся на р. Тогда

   

    так как

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

 

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

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

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

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

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

 

     Причем g и h – многочлены положительной степени с целыми коэффициентами. Число b0c0 = a0 делится на р, поэтому одно из чисел b0 и c0   делится на р. Пусть, для определенности, Ьо делится на р. Тогда со не де­лится на р, так как ао = Ьосо не делится на р2. Если все числа bi делятся на р, то ап делится на р. Поэтому bi не делится на р при некотором i, где 0 <i  < deg g < n; можно считать, что i — наименьший номер чи­сла bi, не делящегося на р. С одной стороны, по условию число аi делится на р. С другой стороны, ai = bic0+bi-1c1+ ... + boci, причем все числа  bi-1c1,..., b0ci  делятся на р, а число bicо не делится на р. Получено противоречие.  

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

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

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

 

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

 

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

 

 

          Пусть р—фиксированное простое число,                   — многочлен с целыми коэффициентами, причем A0An ≠ 0. Запишем ненулевые коэффициенты многочлена f в виде Ai  = aipai   ,где ai — целое число, не делящееся на р. Каждому ненулевому коэффициенту  aipai  сопоста­вим точку на плоскости с координатами (i,аi). По этим точкам можно построить диаграмму Ньютона многочлена f (соответствующую про­стому числу р). Делается это следующим образом. Пусть Р0 = (0,а0) и P1 = (i1, ai1), где i1 — наибольшее целое число, для которого ниже прямой Р0Р1 нет данных точек. Пусть,  далее, Р2 = (i2, ai2), где i2 - наибольшее целое число, для которого ниже прямой P1P2 нет данных точек и т.д. (рис. 1). Самый последний отрезок имеет вид Pr-iPr, где Рr = (n, an). Если звенья ломаной Р0...Рr  проходят через точки с це­лочисленными координатами, то все эти точки мы тоже считаем вер­шинами ломаной. При этом к вершинам Р0,..., Рг добавляется еще    s ≥ 0 вершин . Полученную в результате ломанную Q0…Qr+s называют диаграммой Ньютона (здесь Q0 =P0 и Qr+s = Pr). Отрезки PiPi+1 и QiQi+1 будем называть , соответственно, сторонами и звеньями диаграммы Ньютона.

Рис. 1

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

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

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

 

    (числа ai, bj, ck не делятся на р). Возьмем некоторую сторону PiPi+1 диаграммы Ньютона многочлена f(сторона PiPi+1 может состоять из нескольких звеньев диаграммы Ньютона). Пусть точки Pi и Pi+1 имеют соответственно координаты (i_, ai_) и (i+, ai+). Наклон стороны  PiPi+1  равен

 

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

             Рассматриваемая сторона PiPi+1  диаграммы Ньютона лежит на прямой Ia-Ai=F, где F=Iai+-Ai+=Iai_-Ai_. По условию все точки (I, ai), I = 0,1…,n, лежат не ниже прямой, т.е. Iai-Ai ≥ F, причем это неравенство строгое при i < i_ и при i >i+ . Будем на­зывать число Iai - Ai весом монома apaxi, где (а,р) = 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_. Тогда вес члена bjpβjxj строго больше G, а вес члена ckpγkxk не меньше H.

            Вес члена (bjpβjxj)( ckpγkxk) при j + к = const монотонно возрастает с возрастанием βjk, поскольку I > 0. В рассматриваемом случае j + к = j_ + к_, поэтому сумма βjk строго минимальна при j = j_ и  к = к_. Следовательно, вес члена  aj_+k_paj_+k_    равен G + H. Ясно также, что при i < j_ + к_ вес члена аiрaixi строго больше G + H, а при i ≥ j_ + k_ вес члена аiрaixi   не меньше 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. Тогда многочлен хn + срт неприводим.

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

 

 

 

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

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

           Теорема 2.3.1 Пусть f(x) = xn + a1xn-1 +... + an — многочлен с целыми коэффициентами, причем ап ≠ 0.

    а)           Если | a1| > 1 + | a2| + … + | an|, то многочлен f неприводим.

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

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

|f(z)-g(z)|= | a2zn-2 +... + an |≤| a2| + … + | an|<| a1|  -1,    (1)

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

|f(z) |+|g(z)|≥ |g(z)|= | zn +a1zn-1 |=|z+ a1| ≥| a1|  -1.    (2)

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

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

|f(z) |+|g(z)|= |a1|  -1

    возможно лишь в том случае, когда одновременно выполняются равенства |f(z) |=0 и |z+ a1| ≥| a1|  -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

Категория: Отчеты по практике

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.