«Алгебраические модели в информационной безопасности» ответы на вопросы зачета

Список вопросов для зачета по дисциплине
«Алгебраические модели в информационной безопасности»

(III семестр)

 

1.                 Построение M(R) – кольца многочленов от одного переменного над кольцом с единицей. Коммутативность M(R).

Пусть R — произвольное кольцо с единицей e.

Теорема 2. Алгебра (R[x], +, ) многочленов над  кольцом R  c единицей есть  кольцо с единицей.  Кольцо R[x] коммутативно тогда  и только  тогда, когда кольцо R коммутативно, и содержит делители нуля тогда и только тогда, когда R содержит делители нуля.

Единицей в R[x], очевидно, является многочлен x⁰. Если кольцо R коммутативно, то коммутативность R[x] доказывают равенства

a(x) · b(x) =        a_ib_jx^i+j  = b_ja_ix^j+i  = b(x) · a(x).

Если же ab = ba для некоторых a, b      R, то в R[x] не коммутируют многочлены ax⁰ и bx⁰.

Если в R нет делителей нуля, то для любых ненулевых многочленов a(x), b(x) ∈ R[x] справедливы соотношения deg(a(x) · b(x)) = deg a(x)+ deg b(x) ≥ 0

 

2.                 Степень многочлена, свойства. Свойства кольца R[x].

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

Частным случаем является постоянная функция f(x)=a ,a-cost. Многочлен коэффициенты которого равны 0 называется, многочлен нулевой степени. Над многочленами можно выполнять: сложение, вычитание, умножения в результате чего получается снова многочлен. сумма, разность и произведение многочленов также являются многочленом то многочлены образуют под кольцо в кольце всех функций действительного аргумента. Кольцо многочленов от действительной переменной x обозначается R[x] .

 

3.                 Деление с остатком в кольце R[x].

Теорема. Если старший коэффициент многочлена b(x)  R[x]  0  обратим в кольце R, то любой многочлен a(x) R[x] можно разделить справа (слева) с остатком на b(x). При этом правые (левые) неполное частное и остаток опреде- ляются однозначно.

Следствие 1. Если P  — поле и b(x)     P [x]     0  , то любой многочлен a(x)     P [x] можно разделить с остатком на b(x) и притом единственным способом.

 

4.                 Значение и корень многочлена, теорема Безу.

Значением многочлена a(x) = a₀ + a₁x + ... + a_nxⁿ из R[x] в точке α ∈ R называют элемент кольца R, α — корень многочлена a(x), если a(α) = 0.

Теорема Безу. Остаток от деления справа многочлена a(x) ∈ R[x] на двучлен x − α ∈ R[x] равен a(α). В частности, элемент α кольца R является корнем многочлена a(x) ∈ R[x] тогда и только тогда, когда a(x) делится справа на x − α.

 

5.                 Полиномиальные отображения. Многочлен как функция, следствия.

Отображение ϕ кольца R в себя называют полиномиальным, если для некоторого a(x) R[x] выполняется равенство ϕ = a_R. В этом случае говорят, что ϕ задается многочленом (полиномом) a(x).

Если R — коммутативное кольцо, то любое отображение ϕ: R R полиномиально в том и только в том случае, когда R — конечное поле. Полиномиальность любого преобразования конечного поля вытекает из следующего общего результата.

Теорема 6. Если в поле P  есть  n  попарно  различных  элементов  α₁,... , α_n,  то для любых β₁,... , β_n P существует единственный многочлен a(x) P [x] со свойствами.

Следствие 1. Многочлен степени n > 0 над полем P имеет в этом поле не более n различных корней.

Следствие 2. Если P — бесконечное поле, то многочлены a(x) и b(x) из P [x] равны в том и только в том случае, когда равны функции a_P и b_P .

 

6.                 Ассоциированные многочлены над полем, эквивалентные определения ассоциированности. 

Элементы a и b коммутативного кольца S с единицей называются ассоциированными, если b = ua для некоторого обратимого элемента u ∈ S. Отношение ассоциированности элементов есть отношение эквивалентности на S. Ассоциированность чисел a, b ∈ Z эквивалентна  равенству  |a| =  |b|,  которое,  в  свою  очередь,  эквивалентно  условию: a | b и b | a.

В кольце P [x] обратимы все многочлены нулевой степени и толь- ко они. Для многочленов a(x), b(x) P [x] следующие утверждения эквивалентны:

(а) a(x) и b(x) ассоциированы;

(б) a(x) | b(x) и b(x) | a(x);

(в) a(x) | b(x) и deg a(x) = deg b(x).

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

 

7.                 Унитарные многочлены. Существование и единственность многочлена ассоциированного данному.

Ненулевой многочлен со старшим коэффициентом, равным единице, называют унитарным. Множество всех унитарных многочленов из P [x] замкнуто относительно операции умножения, и, так как P [x]^∗ = P ^∗, то с любым ненулевым многочленом f (x) P [x] ассоциирован единственный унитарный многочлен, который мы будем обозначать символом f ^∗(x).

Аналогия между унитарными многочленами и натуральными числами имеет ограниченную область применения. Если целое a делится с остатком на b   Z   0  , то остаток r есть либо нуль, либо натуральное число. Если же многочлен a(x)     P [x]  делится с  остатком на  b(x)      P [x]      0    и  остаток  r(x)  отличен от нуля, то r(x) — не обязательно унитарный многочлен. Аналогия между r и r(x) здесь состоит в том, что r удовлетворяет условию 0 ≤ r < b , а r(x) — условию

deg r(x) < deg b(x).

 

8.                 НОД многочленов над полем. Существование и единственность НОД в случае, когда все числа равны нулю. Описание всех НОД многочленов, если хотя бы один НОД существует.

Наибольшим              общим  делителем (НОД)  многочленов

a₁(x),... , a_n(x)                              P [x] называют многочлен d(x)        P [x] такой, что

1)                  d(x) есть общий делитель многочленов a₁(x),... , a_n(x);

2)                  d(x) делится на любой другой общий делитель этих многочленов.

3)                  Если a₁(x) = ... = a_n(x) = 0, то НОД {a₁(x),... , a_n(x)} = {0}.

4)                  (б)  Если  хотя  бы  один  из  многочленов  a₁(x),... , a_n(x)  не  равен  нулю   и НОД a₁(x),..., a_n(x) = ∅, то для любого d(x) НОД a₁(x),..., a_n(x) верно равенство

5)                  НОД {a₁(x),... , a_n(x)} = {ud(x): u ∈ P ^∗},

6)                  и существует единственный унитарный НОД этих многочленов.

 

9.                 Существование НОД n многочленов, алгоритм Евклида. 

Теорема 9.  Если среди многочленов a₁(x),..., a_n(x) принадлежит P [x] есть ненулевые, то для  них в P [x] существует единственный унитарный наибольший общий делитель.

Алгоритм Евклида является универсальным способом, позволяющим вычислять наибольший общий делитель двух положительных целых чисел. Для нахождения наибольшего общего делителя двух чисел aи b (a и b – целые положительные числа, причем a больше или равно b) последовательно выполняется деление с остатком. Деление заканчивается, когда r_k+1=0, при этом r_k=НОД(a, b).

 

10.            Линейное представление НОД n многочленов.

Если многочлен d делит какие-либо многочлены, то он называется их общим делителем. Многочлены степени 0, т.е. постоянные, отличные от нуля, всегда являются общими делителями. Общий делитель наибольшей степени называется наибольшим общим делителем. Наибольший общий делитель d многочленовобозначается НОДили просто.

Теорема 1 (о линейном представлении наибольшего общего делителя двух многочленов).Еслито существуют многочлены и и v, для которых

Следствие. Наибольший общий делитель многочленов f  и g делится на их любой общий делитель.

Теорема. Существуют целые числа u и v, удовлетворяющие уравнению линейного представления HOД:

uA+vB=HOD(A,B) .

 

11.            Взаимно простые многочлены над полем и их свойства. Критерий взаимной простоты.

Многочлены a₁(x),... , a_n(x) P [x] взаимно просты тогда  и только тогда, когда существуют многочлены u₁(x),... , u_n(x) P [x] такие, что u₁(x)a₁(x)+ ... + u_n(x)a_n(x) = e.

Теорема 12.  Для любых многочленов a(x), b(x), c(x)        P [x] справедливы утвержде- ния:

(а) если (a(x), b(x)) = e и  (a(x), c(x)) = e,  то  (a(x), b(x)c(x)) = e;

(б) если (a(x), b(x)) = e  и   a(x) | b(x)c(x),  то  a(x) | c(x);

(в) если (a(x), b(x)) = e,  a(x)  c(x)  и  b(x)   c(x),  то  a(x)b(x)   c(x);

(г) если (a(x), b(x)) = c(x) = 0,  то    a(x) , b(x)    = e.

 

12.            НОК многочленов над полем. Существование и единственность НОК в случае, когда среди чисел имеется нуль. Описание всех НОК в случае существования одного НОК.

Наименьшим общим кратным (НОК) многочленов a₁(x),... , a_n(x) ∈ P [x] называют многочлен k(x) ∈ P [x] со свойствами:

1)                  k(x) — общее кратное многочленов a₁(x),... , a_n(x);

2)                  если k₁(x) — любое общее кратное многочленов a₁(x),..., a_n(x), то k(x) | k₁(x).

Совокупность всех описанных многочленов k(x) обозначают следующим образом: НОК{a₁(x),... , a_n(x)}.

Если  среди  многочленов   a₁(x),... , a_n(x)   есть   нулевой,   то НОК {a₁(x),... , a_n(x)} = {0}. В противном случае справедлива

Теорема 13. Если a₁(x),..., a_n(x) ∈ P [x] \ {0}, то существует единственный унитарный многочлен k(x) ∈ НОК {a₁(x),..., a_n(x)} и справедливо равенство

НОК {a₁(x),..., a_n(x)} = {uk(x):  u ∈ P ^∗}.

Существование НОК указанных многочленов доказывается индукцией по параметру n.

Если  k(x) =  f^٨(x)  — унитарный многочлен, ассоциированный с f (x), то он также соответствует k(x) НОК a₁(x),... , a_n(x) .

Унитарный многочлен k(x), являющийся наименьшим общим кратным многочленов a₁(x),... , a_n(x) P [x] 0 , обозначают k(x) = [a₁(x),... , a_n(x)].

 

13. Существование НОК n ненулевых многочленов.

Наименьшим общим кратным (НОК) системы {f1; f2; : : : ; fs} называется любой ненулевой многочлен m, удовлетворяющий любому из равносильных условий теоремы Пусть {f1; f2; : : : ; fs} система ненулевых много-

членов и m ≠ 0 (некоторый ненулевой многочлен). НОК системы многочленов называется такое общее кратное этой системы, которое делит любое другое общее кратное этой системы многочленов. Следствие: Если НОК системы многочленов существует, то оно определено с точностью до ассоциированности.

ТЕОРЕМА: Если существует НОК 2-х любых ненулевых многочленов, то существует НОК и любой конечной системы многочленов, при этом имеет место следующая индукционная формула:

HOK {f1; f2; : : : ; fs−1; fs} = HOK {HOK {f1; f2; : : : ; fs−1} ; fs}

 

14. Неприводимые многочлены над полем, основные свойства. Критерий неприводимости для многочленов степени 2 и 3.

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

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

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

 

 

15. Каноническое разложение многочлена над полем.

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

 

 

16. Выражение НОД и НОК многочленов с использованием их канонических разложений.

Любое составное число m можно однозначно представить в виде произведения простых сомножителей p, m = p₁*p₂*.....*p_k, где m – составное число, p – простое. Составное число может раскладываться на простые, при этом могут быть две формы:

1)когда все сомножители разные

2) когда есть кратные сомножители

Пример:

720 = 2⁴*3²*5 - такая форма носит название – каноническое разложение на простые сомножители. M=p₁^α1* p₂^α2* p_k^αk. Это позволяет при большем числе кратных сомножителей достаточно компактно записать разложение.

 

 

 

17. Бесконечность множества унитарных неприводимых многочленов, следствие.

Множество унитарных многочленов неприводимых над полем бесконечно. Доказательство аналогично доказательству теоремы Евклида о бесконечности множества простых чисел. Для бесконечных полей доказательство очевидно, так как по св 1 многочлен (t c), c 2 P неприводим над любым полем, а число таких многочленов в бесконечном поле бесконечно.

 

 

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

Натуральное число k называется кратностью корня α многочлена f (x), если f (x) = g(x)(x − α) k и g(α) 6= 0.

Кратность корня α многочлена f (x) равна кратности неприводимого множителя x − α этого многочлена. Поэтому любой многочлен степени n ≥ 1 имеет не более n корней в поле F, а сумма кратностей его корней также не превосходит n.

Теорема: Любой многочлен степени больше 0 над полем C имеет корень в C.

Пусть f ∈ C[x], deg(f ) ≥ 1. По теореме Гаусса f (x) имеет некоторый корень α. Следовательно, f = (x − α)g для некоторого многочлена g ∈ C[x]. Если многочлен f (x) неприводим над полем C, то deg(f ) = 1.

Следствие 1. Неприводимыми над полем C являются только многочлены первой степени.

Следствие 2. Любой многочлен с комплексными коэффициентами степени больше 1 разлагается на линейные множители с комплексными коэффициентами.

19. Производная многочлена, ее свойства, следствия.

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

Теорема 1. Простой корень многочлена не является корнем его производной; кратный корень кратности  является корнем производной, и кратность его в производной равна  .

Теорема 2. Для того чтобы число было корнем кратности многочлена необходимо и достаточно, чтобы  и  .

Всякий многочлен можно представить в виде

 ,

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

 .

 

20. Неприводимые многочлены над полями комплексных (без доказательства) и действительных чисел.

Следствие 1. Всякий многочлен f (x) степени n ≥ 1 разлагается над полем комплексных чисел в произведение линейных множителей, т.е. поле C комплексных чисел алгебраически замкнуто по определению 1.

Следствие 2. Всякий многочлен f (x) из кольца C[x] степени n ≥ 1 имеет точно n комплексных корней.

Следствие 3. Неприводимым над полем C комплексных чисел может быть только многочлен первой степени.

Следствие 4. Пусть  - мнимый корень многочлена f (x) с действительными коэффициентами, тогда число  также является корнем многочлена f (x) .

Следствие 5. Неприводимым над полем R действительных чисел может быть только многочлен не выше второй степени.

Следствие 6. Всякий многочлен f (x) степени n ≥ 1 из кольца  разлагается над полем R действительных чисел в произведение линейных и квадратных неприводимых множителей. Всякому линейному множителю соответствует действительный корень, а всякому квадратному – пара сопряженных мнимых корней многочлена.

21. Примитивные многочлены и их свойства.

Определение Многочлен f ∈ Z[x] называется примитивным, если f 6= 0 и наибольший общий делитель всех коэффициентов многочлена f равен 1. Очевидно, что для любого g ∈ Z[x], g 6= 0, существует единственный примитивный многочлен f такой что g = mf , где m – наибольший общий делитель всех коэффициентов многочлена g. Лемма Гаусса Произведение двух примитивных многочленов является примитивным многочленом. Признаком примитивных полиномов является наличие остатка равного 1 только для полиномов x⁰ и xⁿ.

 

22. Рациональные корни многочлена над полем рациональных чисел.

Теорема 6.1 (о рациональных корнях многочлена с целыми коэффициентами). Если –рациональный корень многочлена f(x) = a_n × xⁿ+ + …+ a₁ × x + a₀ с целыми коэффициентами, причем (p, q) = 1, то числитель дроби p является делителем свободного члена а₀, а знаменатель q является делителем старшего коэффициента а₀.

Теорема 6.2. Если Q (где (p, q) = 1) является рациональным корнем многочлена f(x) с целыми коэффициентами, то –целые числа.

 

23. Неприводимые многочлены над полем рациональных чисел. (Признак Эйзенштейна).

Теорема. Многочлен f ∈ Z[x] неприводим над полем Q тогда и только тогда, когда он неприводим над кольцом Z.

Теорема (признак Эйзенштейна). Пусть многочлен f = α0 + α1x + . . . + αk x k ∈ Z[x]. Если существует простое число p, которое делит коэффициенты αk−1, . . . , α0, но не делит αk и p 2 не делит α0, то многочлен f неприводим над полем Q.

Наблюдение. Многочлен f (x) ∈ Z[x] неприводим над полем Q тогда и только тогда, когда для некоторого r ∈ Z многочлен f (x − r) неприводим над полем Q.

 

24. Сравнения первой степени с одним неизвестным в кольце многочленов. Решение.

Будем рассматривать сравнения вида a₀xⁿ + a₁x^n-1 + … + a_n≡ 0 (mod m) (*).

Если a₀ не делится на m, то n называется степенью сравнения.

Решить сравнение – значит найти все x, ему удовлетворяющие. Два сравнения, которые удовлетворяют одни и те же значения x, называются равносильными.

Если сравнению (*) удовлетворяет какое-то x=x₁, то ему же будут удовлетворять все числа, сравнимые с x₁ по модулю m: x ≡ x₁(mod m). Весь класс чисел, сравнимых с x₁ по модулю m считается за одно решение. Таким образом, (*) будет иметь столько решений, сколько вычетов из полной системы ему удовлетворяет.

 

 

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

Теорема 9. Если (a, m) = d, то сравнение (5) разрешимо в том и только том случае, когда d b. При выполнении последнего условия сравнение (5) имеет ровно d решений по модулю m.

Теорема 10 (китайская теорема об остатках). Если    натуральные       числа

m₁, m₂,..., m_k попарно взаимно просты, то система сравнений

x ≡ a₁ (mod m₁)

x ≡ a₂ (mod m₂)

................

x ≡ a_k (mod m_k)

 

имеет  единственное  решение  по  модулю  m  =       m₁m₂ ... m_k при любых

a₁, a₂,..., a_k ∈ Z.

 

 

Список источников

1.  Глухов М. М., Елизаров В. П., Нечаев А. А.

Алгебра: Учебник. — 2-е изд., испр. и доп. — СПб.: Издательство «Лань», 2015. — 608 с.: ил. — (Учебники для ву- зов. Специальная литература).

2. Куликов Л.Я. Алгебра и теория чисел: Учеб. пособие для педагогических институтов. — М.: Высш. школа, 1979. — 559 с.

3. Математика, ее содержание, методы и значение. Под ред. Александрова А.Д., Колмогорова А.Н., Лаврентьева М.А. М.: Изд. Академии наук СССР, 1956; т.1 - 296с.

4. Многочлены и их корни. Записки лекций П.С. Петров Дальневосточный федеральный университет Тихоокеанский океанологический институт им. В.И. Ильичева ДВО РАН

5. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971, пер. с англ.