В §1.1 было дано аксиоматическое определение поля, введены понятия и приведены примеры простого и расширенного поля.

Обобщением сказанного в §1.1 и §1.3 являются следующие определения:

1.Для простых полей:

2.Для расширенных полей:

К многочлену π (x),кроме требования неприводимости, предъявляется ещё одно принципиальное требование – ненулевые элементы поля являются степенями корня α многочлена π(x) .

Если ненулевые элементы поля GF(m ) могут быть представлены как степени некоторого элемента α, то α называют примитивным элементом этого поля.

В §1.1 было показано, что поле GF(2 2 ) в качестве ненулевых элементов имеет 1, α, 1+α, где α- корень π(x)=1+x+x 2 ,т.е.1+α+α 2 =0. Поскольку 1=α 0 , а 1+α=α 2 , то все ненулевые элементы GF(2 2 ) представляются степенями корня π(x) .Элемент α является примитивным элементом GF (2 2 ) , а π(х)=1+х+х 2 является примитивным неприводимым многочленом.

Рассмотрим поле GF(5). Поскольку 5- простое число, то кольцо классов вычетов по модулю 5 образует поле GF(5). Таблицы сложения и умножения по модулю 5 приведены в §1.3. Для этого поля также существует примитивный элемент, степени которого дают все ненулевые элементы поля. Например, 2 0 =1, 2 1 =2, 2 2 =4, 2 3 =8=3,2 4 =16=1,2 5 =32=2.

Эти примеры могут быть обобщены следующим образом. В любой конечной мультипликативной группе можно рассмотреть совокупность элементов, образованную некоторым элементом g и его степенями g 2 , g 3 и т.д. Так как группа имеет конечное число элементов,то неизбежно появится повторение, т.е. для некоторых i и j будет g i =g j .

Если наблюдается g i =g j , то g j - i =1. Следовательно, некоторая степень элемента g равна 1. Пусть e – наименьшее положительное число , при котором g e =1. Совокупность элементов 1, g, g 2 , ..., g e -1 образует подгруппу по операции умножения, т.к. налицо единичный элемент 1, замкнутость, наличие обратных элементов: для g i обратный элемент g e - i . Группа, состоящая из всех степеней одного из ее элементов получила, название циклической группы .

Число e называется порядком элемента g .

Обобщением изложенного выше является следующее:

Если мультипликативная группа порядка q содержит циклическую подгруппу из e элементов, порожденную некоторым элементом g, то число смежных классов в разложении группы по циклической подгруппе будет равно q/e и каждый смежный класс также будет содержатьe элементов. Значит справедливо следующее утверждение:

где φ (e ) – функция Эйлера , равная числу чисел взаимно простых с e и меньших e . Функция Эйлера может быть вычислена следующим образом:

если e – составное число вида e =
, гдеp i > 1 – простое, а l i – натуральное число и i = 1,2, ... t , то

φ(e ) =
.

В частности, для простого р и целого а

φ(р а )= р а - р а-1 , φ(р ) = р – 1.

Кроме того,

φ(а 1 ×а 2) = φ(а 1)φ(а 2),

если а 1 и а 2 взаимно просты.

Например:

φ(1) = 1, φ(4) = 2,

φ(2) = 1, φ(5) = 4,

φ(3) = 2, φ(6) = 2.

Пример1.4.1 . Определить число элементов Ni поля GF(2 6) порядка i = 1, 3, 7, 9, 21, 63.

Решение: Ni = φ(i), где φ(i) – функция Эйлера, для вычисления которой необходимо знать каноническое разложение числа i:

1=1, 3=3, 7=7, 9=3 2 , 21=3×7, 63=3 2 ×7.

Теперь находим:

N9 = φ(9) = 9(1-1/3) = 9×2/3 = 6,

N21 = φ(21) = 21(1-1/3)(1-1/7) = 21×2/3×6/7 = 12,или φ(21)=φ(3)φ(7)=2×6=12,

N63 = φ(63) = 63(1-1/3)(1-1/7) = 63×2/3×6/7 = 36.

Рассмотренные числа 1, 3, 7, 9, 21, 63 являются делителями числа 63 и поэтому определяют все возможные порядки элементов мультипликативной группы поля GF(2 6). Полученный результат может быть обобщен следующим образом:

Важным следствием из рассмотренного является следующее.Пусть а – примитивный элемент GF(p m) Порядок а равен p m -1, т.е α
=1.Если среди элементов поля GF(p m) есть элемент β порядка p r -1 , где r < m, т.е. βα,то последовательность элементов β 1 , β 2 , …,
=
, образует циклическую подгруппу мультипликативной группыGF(p m), т.е. содержит все ненулевые элементы нового поля GF(p r),являющегося подполем GF(p m).Итак,

В § 2.1 будет показано, что p r -1 делит p m -1,если r делит m. Таким образом, окончательно

Пример 1.4.2 .В качестве примера рассмотрим подполя поля GF(2 12). Число 12 делится на числа 6,4,3 и 2, т.е. в составе поля GF(2 12) существуют в качестве подполей поля GF(2 6), GF(2 4), GF(2 3), GF(2 2). Так как любое расширенное поле содержит основное поле, то в каждом из указанных полей содержится поле GF(2). Найдем циклические группы рассматриваемых полей. Обозначим примитивные элементы полей:

GF(2 12)→α,GF(2 6)→β,GF(2 4)→γ,GF(2 3)→δ,GF(2 2)→ε,GF(2)→ζ.

Выразим ненулевые элементы полей через степени примитивных элементов:

GF(2 12): α 1 , α 2 ,α 3 ,… ,α 4095 =α -1 =1= α 0 и порядок α равен 4095;

GF(2 6) : β 1 , β 2 ,β 3 ,… ,β 63 =β -1 =1=β 0 и порядок β равен 63; GF(2 4) : γ 1 , γ 2 ,γ 3 ,… ,γ 15 =γ -1 = 1=γ 0 и порядок γ равен 15; GF(2 3) : δ 1 , δ 2 ,δ 3 ,… ,δ 7 =δ -1 = 1=δ 0 и порядок δ равен 7; GF(2 2) : ε 1 , ε 2 ,ε 3 =ε -1 = 1=ε 0 и порядок ε равен 3; GF(2) : ζ 1 = ζ -1 =1 = ζ 0 и порядок ζ равен 1.

Элементы полей GF(2 6), GF(2 4), GF(2 3), GF(2 2) и GF(2) входят в состав GF(2 12). При этом β = α 65 , т.к. β 63 = α 4095 = 1 = (α 65) 63 . Аналогично γ = α 273 ,δ = α 585 , ε = α 1365 , ζ = α 4095 . Связь между рассмотренными полями иллюстрирует рис.1.1.

Рис.1.1. Поле GF(2 12) и его подполя

Глава.2.Многочлен Х n -1, его корни и неприводимые сомножители

2.1 .Связь между корнями Х n -1 и элементами поля GF ( q )

Многочлен Х n -1, его неприводимые сомножители и их корни играют существенную роль в построении важнейшего класса групповых кодов -циклических кодов. Знание корней сомножителей Х n -1 позволяет решить задачу выбора требуемого кода для конкретного дискретного канала.

Рассмотрим общий случай:

Пусть Х n -1 задан над полем GF(q). Известно, что GF(q) имеет циклическую группу из q-1 своих ненулевых элементов.

Порядок каждого ненулевого элемента GF(q) не может быть выше q-1, а это означает, что α q -1 =1 для любого ненулевого элемента α из GF(q),т.е. любой ненулевой элемент GF(q) обращает Х q -1 -1 в нуль, а, значит, является его корнем. Поскольку Х q -1 -1 имеет ровно q-1 корней, то, следовательно, все ненулевые элементы GF(q) являются корнями Х q -1 -1.

Таким образом,

В случае двоичных циклических кодов нас интересуют многочлены с корнями из расширенных полей Галуа GF(2 m). В соответствии с полученным выше результатом справедливо утверждение:

Важно уметь сопоставлять совокупности элементов GF(q), в частном случае GF(2 m), с корнями неприводимых сомножителей Х q -1 -1 (в двоичном случае с корнями Х -1 -1), ровно как и с корнями Х n -1 при произвольном n.

При выявлении сомножителей Х n -1 полезны следующие свойства, характеризующие связи между элементами GF(q) и многочленами, являющимися делителями Х n -1.

Свойство 1 . Наличие в двучлене Х n -1 сомножителей вида Х m -1, где m

Пусть n=m×d, где n, m и d-целые положительные числа. Рассмотрим двучлен У d -1.Очевидно, что при У=1 он обращается в нуль, и 1 является корнем У d -1.

Тогда по теореме Безу У d -1 делится на У-1.Положим, что У = Х m . Тогда, очевидно, Х md -1 делится на Х m -1.Таким образом, справедливо следующее:

Свойство 2. Поля Галуа GF(p m), образованные классами вычетов многочленов по модулю примитивного неприводимого над полем GF(p) многочлена π(x) степени m, называют полями характеристики р при любомвыборе m.В поле GF(p) элемент p=0.

В поле характеристики p для любых чисел a и b справедлива биноминальная теорема:

(a+b) p = a p + Ca p-1 b + Ca p-2 b 2 +…+ b p ,

где C i p-биноминальные коэффициенты, вычисляемые по формуле:

Поэтому справедливо:

Свойство 3. Пусть многочлен f(x)=a0+a1x+...+amx m степени m неприводим в

поле GF(p). Рассмотрим (f(x)) p .

По предыдущему свойству:

(f(x)) p = (а 0) p +(a1x 1)+...+(amx m) p =

A0 p +a1 p (x p) ’ +...+am p (x p) m =

A0+a1(x p) ’ +...+am(x p) m = f(x p).

Этот результат получен в силу того, что для любого элемента a i из GF(p) справедливо: ai p -1 = 1 и ai p = ai.

Пусть β - корень f(x), тогда f(β) = 0.

В силу полученного результата (f(β)) p = f(β p) = 0, т.е. для любого корня β многочлена f(x) справедливо утверждение, что β p также является корнем f (x ). Так как неприводимый многочлен f (x ) степени m имеет всего m корней и один из его корней есть β, то m степеней β от р 0 =1 до p m -1 являются корнями f(x ), т. е. справедливо:

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

Свойство 4. Прямым следствием из свойства 3 является следующее:

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

Для доказательства этого свойства предположим, что корнями некоторого неприводимого многочлена f (x ) степени m является β, имеющий порядок e и β, имеющий порядокl . Тогда (β) e = (β e )=1, и поэтомуe делится на l . Аналогично, β l = (β) l =β
=((β) l )
=1
=1, так что l делится на e . .Поскольку e и l - целые положительные числа, то e = l , что и доказывает свойство 4.

Свойство 5. Выше было показано однозначное соответствие между ненулевыми элементами GF (p m ) и корнями двучлена Х
-1 . Определим вид многочлена, корнями которого являются все элементы поля GF (p m ). Пусть α – произвольный элемент поля порядка p m -1 . Тогда справедливо: α=α, т.е.α является корнем уравнения

х- х = 0.

Данный результат известен в литературе как теорема Ферма :

Любой элемент α поля GF ( p m ) удовлетворяет тождеству α=α или, эквивалентно, является корнем уравнения х- х = 0 .

Следствием теоремы Ферма является тот факт, что двучлен х- х может быть представлен в виде произведения p m сомножителей следующим образом:

где a i = GF (p m ), т. е. все элементы a i или GF (p m ) являются корнями двучлена х- х , причём каждый корень встречается только один раз.

Выше мы показывали, что элемент поля GF (p m ) α порядка p m -1 называется примитивным и любой ненулевой элемент поля являются степенью α , т. е. для ненулевых элементов a i справедливо a i = α i , где i принимает значение от 1 до p m -1.

Свойство 6.

Свойство 3 устанавливает связь между последовательностями корней неприводимого многочлена f (x ). Естественно считать что корень f (x ) – элемент расширенного поля GF (p m ). Какой может быть максимальная степень неприводимого многочлена с корнями из GF (p m ) или что тоже самое – какова максимальная степень неприводимого сомножителя х- х ?

Ответ на этот вопрос даёт анализ возможной максимальной степени в последовательности корней:

Удобно рассматривать последовательность степеней в выражении корня через примитивный элемент поля GF (p m ). Тогда приведённая выше последовательность корней однозначно соответствует последовательности степеней примитивного элемента:

{s ,

p 2 s ,

p 3 s ,…, p s}

где m s – наименьшее положительное число, такое, что p×s =s по модулю p m -1 . Модуль p m -1 отражает порядок примитивного элемента поля. В последовательности степеней корней следующая степень β=β , т.е.

Максимальная степень неприводимого многочлена в разложении - , равно как и в разложении многочлена - , равна m .

Последовательность, взятая в фигурные скобки, получившая название циклотомического класса, в зависимости от значения s может содержать m s ≤ m элементов. Число s, стоящее в начале циклотомического класса, получило название образующего или представителя циклотомического класса. Ниже будет показано, что число элементов в циклотомическом классе m s должно быть делителем числа m. Справедливо следующее:

Множество целых чисел, отображающих степени примитивного элемента α поля GF (p m ) в представлении ненулевых элементов поля в виде циклической группы распадается на подмножества, называемые циклотомическими классами по модулю p m -1. Каждый циклотомический класс однозначно соответствует одному из неприводимых сомножителей - .

Понятно, что:

Полное число циклотомических классов для поля GF (p m ) совпадает с числом неприводимых сомножителей многочлена - , и множество элементов, охватыаемых циклотомическими классами, отображает все ненулевые элементы поля GF (p m ).

Например, циклотомическими классами по модулю 15 для p =2 являются:

С 0(15) ={0 },

C 1(15) ={1 ,2 ,4 ,8 },

C 3(15) ={3 ,6 ,12 ,9 },

C 5(15) ={5 ,10 },

C 7(15) ={7 ,14 ,13 ,11 }.

Здесь С S (15) обозначает циклотомический класс по модулю 15, начинающийся с числа s .

Анализ приведённых последовательностей означает, что двучлен x 15 +1 над полем GF (2 ) состоит из 5 неприводимых сомножителей: одного сомножителя 1-ой степени с корнем порядка 1, одного сомножителя 2-ой степени с корнем порядка 3 и трёх сомножителей степени 4, два из которых имеют порядок корней 15, а один – имеет порядок корней 5. Результаты этого анализа показывают, что последовательность C 0(15) соответствует многочлену x +1; последовательность C 5(15) соответствует многочлену 2-ой степени с корнями порядка 3 – это многочлен x 2 + x +1 – неприводимый сомножитель двучлена x 3 +1; последовательность C 3(15) соответствует неприводимому сомножителю 4-ой степени двучлена x 5 +1= (x +1)( x 4 + x 3 + x 2 + x +1), отсюда и порядок корней равный пяти. Многочлены, соответствующие последовательностям C 1(15) и C 7(15) могут быть найдены на основе теоремы Безу:

f 1 (x )= (x + α ))(x + α 2 ))(x + α 4 ))(x + α 8 ),

f 7 (x )= (x + α 7 )(x + α 11 )(x + α 13 ))(x + α 14 ).

Анализ многочленов f 1 (x ) и f 7 (x ) будет выполнен ниже.

Свойство 7. Анализ неприводимых многочленов, входящих в разложение Х

, имеющих корни среди элементовGF(2 4) показывает, что степени всех неприводимых многочленов: 1, 2, 4 является делителями числа 4. Обобщим этот результат следующими рассуждениями.

Пусть f(х)- неприводимый сомножитель степени d ≤ m многочлена Х-Х и пусть β элемент порядкаp d -1 поля GF(p m), являющийся примитивным элементом подполя GF(p d) поля GF(p m), принадлежит циклической группе GF(p m) порядка p m -1.Следовательно p d -1 делит p m -1, а это возможно только в том случае, когда d делит m. Значит справедливо:

Свойство 8. Аналогичные рассуждения приводят к следующему утверждению:

Свойство 9.

Рассмотрим подробнее многочлены над GF(2):

f 1 (x ) = (x + α )(x + α 2 )(x + α 4 )(x + α 8 ),

f 7 (x ) = (x + α 7 )(x + α 11 )(x + α 13 )(x +2 14 ).

Корни этих многочленов являются элементами поля GF(2 4).С учетом правил сложения и умножения в этом поле простым умножением находим:

f 1 (x ) = 1+ x + x 4 ,

f 7 (x ) = 1+ x 3 + x 4 .

Многочлены f1(x) и f7(х) относятся к двойственным (взаимным) многочленам.

Многочлен f * (x), двойственный некоторому многочлену f (x), определяется как f * (x) = х m f(1/х), где m-степень f(x).

Для двойственных многочленов f * (x) и f(x) справедливо:

1.Корни f * (x) обратны корням f(x).

2.Многочлен f * (x) неприводим тогда и только тогда, когда неприводим f(x).

3.Если многочлен f(x) неприводим, то f(x) и f * (x) принадлежат к одному и тому же показателю.

Пусть А? <А, ·> - мультипликативная группа,

Н - подмножество множества А, Н?.

Определение 1. <Н,·> - называется подгруппой мультипликативной группы А, если выполняются следующие условия:

1. Н - замкнуто относительно бинарной операции "*" а, b Н, ab H;

2. Существует еН = еА - единственный элемент относительно "°";

3. а Н существует а-1 Н.

Определение 2. Если Н = А или Н = {е}, то <Н,·> - называется несобственной подгруппой группы А.

Если Н А, Н - собственное подмножество множества А, то подгруппа называется собственной подгруппой группы А .

Н = А - сама группа А.

Н = {е} - единичная подгруппа.

циклическая подгруппа группа мультипликативная

Пример. Является ли <А, ·>, где А = {1, - 1, i, - i}, i - мнимая единица, группой?

1) Проверим условия мультипликативной группы.

"·" - бинарная ассоциативная операция на множестве А.

Таблица Кэли для "·" на множестве А.

<А, ·> - подгруппа.

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

Пусть <А, ·> - группа. Элемент е А - единичный элемент. Элемент а? е, а А.

(а) - множество целых степеней элемента а: (а) = {х = а n: n Z, a A, a ? e}

Справедлива

Теорема 1. < (а), ·> является подгруппой группы <А, ·>.

Доказательство. Проверим условия мультипликативной подгруппы.

1) Н = (а) - замкнуто относительно "·":

х = а n , y = a l , n,e Z, x, y Н, xy = a n a l = a n+l H, т.к. n + l Z;

2) e = 1 = a 0 H, A: x H xa 0 = a 0 x = x;

3) x = a H, x -1 = a -n Н: a n a -n = a -n a n = a 0 = 1.

Из 1) - 3) по определению Н имеем < (а), ·> - подгруппа мультипликативной группы А.

Определение 3. Пусть <А, ·> - некоторая мультипликативная группа и

Порядком элемента а называется наименьшее натуральное число n такое, что а n = е.

Пример. Найти порядки элементов а = - 1, b = i, c = - i мультипликативной группы А = {1; - 1; i; - i}

1: (-1) 1 = - 1, (-1) 2 = 1 = e. Следовательно,

n = 2 - порядок элемента - 1.

i: (i) 1 = i, (i) 2 = - 1, (i) 4 = 1 = e. Следовательно,

n = 4 - порядок элемента i.

i: (-i) 1 = - i, (-i) 2 = - 1, (-i) 4 = 1 = e. Следовательно,

n = 4 порядок элемента - i.

Теорема 2. Пусть <А, ·> - группа, а А, а? е, а - элемент n-го порядка, тогда:

1) Подгруппа (а) группы А имеет вид: (а) = {а 0 = е, а, а 2 , …, а n-1 } -

n - элементное множество неотрицательных степеней элемента а;

2) Любая целая степень элемента а k , k Z, принадлежит множеству (а) и

a k = e <=> k = nq, n N, q Z.

Доказательство. Покажем, что все элементы (а) различны. Предположим противное: a k = a l , k > l, тогда a k-l = e. k - l < n, что противоречит определению порядка элемента (а). В множестве (а) все элементы различны.

Покажем, что а k , К Z, принадлежит множеству (а).

Пусть k = n, k: n, a k = a nq + r = a k Ч a nq + r = (a n) q Ч a r = e q Ч a r = e Ч a r = a r ,

0 ? r ? n ? 1 => a k (a). Если r = 0, то k = nq <=> a k = e.

Определение 4. Подгруппа < (а), ·>, где (а) = {а 0 = е, а, а 2 , …, а n-1 }, группы А, а - элемент n-го порядка, называется циклической подгруппой группы А (мультипликативной циклической подгруппой группы А).

Определение 5. Группа, совпадающая со своей подгруппой <А, ·>, < (а), ·>, мультипликативной циклической подгруппой, называется циклической группой .

Теорема 3. Всякая мультипликативная циклическая группа является абелевой.

Доказательство. А = (а), а? е, а - образующий элемент группы

a k , a l A, a k Ч a l = a l Ч a k . Действительно, a k Ч a l = a k+l = a l+k = a l Ч a k , l,k Z.

По модулю m , которая обозначается $\backslash mathbb\{Z\}\_m^\{\backslash times\}$ или $U(\backslash mathbb\{Z\}\_m)$ .

Если m простое, то, как отмечалось выше, элементы 1, 2, ...,m -1 входят в $\backslash mathbb\{Z\}\_m^\{\backslash times\}$. В этом случае $\backslash mathbb\{Z\}\_m^\{\backslash times\}$ является полем .

Формы записи

Кольцо вычетов по модулю n обозначают $\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}$ или $\backslash mathbb\{Z\}\_n$. Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^*,$ $(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})^\backslash times,$ $U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}),$ $E(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\}),$ $\backslash mathbb\{Z\}\_n^\{\backslash times\},$ $U(\backslash mathbb\{Z\}\_n)$.

Простейший случай

Чтобы понять структуру группы $U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$, можно рассмотреть частный случай $n=p^a$, где $p$ - простое число, и обобщить его. Рассмотрим простейший случай, когда $a=1$, т.е. $n=p$.

Теорема: $U(\backslash mathbb\{Z\}/p\backslash mathbb\{Z\})$ - циклическая группа.

Пример : Рассмотрим группу $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$

$U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ = {1,2,4,5,7,8} Генератором группы является число 2. $2^1\; \backslash equiv\; 2\backslash \; \backslash pmod\; 9$ $2^2\; \backslash equiv\; 4\backslash \; \backslash pmod\; 9$ $2^3\; \backslash equiv\; 8\backslash \; \backslash pmod\; 9$ $2^4\; \backslash equiv\; 7\backslash \; \backslash pmod\; 9$ $2^5\; \backslash equiv\; 5\backslash \; \backslash pmod\; 9$ $2^6\; \backslash equiv\; 1\backslash \; \backslash pmod\; 9$ Как видим, любой элемент группы $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ может быть представлен в виде $2^l$, где . То есть группа $U(\backslash mathbb\{Z\}/9\backslash mathbb\{Z\})$ - циклическая.

Общий случай

Для рассмотрения общего случая необходимо определение примитивного корня . Примитивный корень по простому модулю $p$ – это число, которое вместе со своим классом вычетов порождает группу $U(\backslash mathbb\{Z\}/p\backslash mathbb\{Z\})$.

Примеры: 2 11 ; 8 - примитивный корень по модулю 11 ; 3 не является примитивным корнем по модулю 11 .

В случае целого модуля $n$ определение такое же.

Структуру группы определяет следующая теорема: Если p - нечётное простое число и l – целое положительное, то существуют примитивные корни по модулю $p^\{l\}$, то есть $U(\backslash mathbb\{Z\}/p^\{l\}\backslash mathbb\{Z\})$ - циклическая группа.

Подгруппа свидетелей простоты

Пусть $m$ - нечётное число большее 1. Число $m-1$ однозначно представляется в виде $m-1\; =\; 2^s\; \backslash cdot\; t$, где $t$ нечётно. Целое число $a$, , называется свидетелем простоты числа $m$, если выполняется одно из условий:

• $a^t\backslash equiv\; 1\backslash pmod\; m$

• существует целое число $k$,

Если число $m$ - составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Её элементы, возведённые в степень $m-1$, совпадают с $1$ по модулю $m$.

Пример : $m=9$. Есть $6$ остатков, взаимно простых с $9$, это $1,2,4,5,7$ и $8$. $8$ эквивалентно $-1$ по модулю $9$, значит $8^\{8\}$ эквивалентно $1$ по модулю $9$. Значит, $1$ и $8$ - свидетели простоты числа $9$. В данном случае {1, 8} - подгруппа свидетелей простоты.

Свойства

Экспонента группы

Порождающее множество

$U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$ - циклическая группа тогда и только тогда, когда $\backslash varphi(n)=\backslash lambda(n).$ В случае циклической группы генератор называется первообразным корнем .

Пример

Приведённая система вычетов по модулю $10$ состоит из $4$ классов вычетов: $\_\{10\},\; \_\{10\},\; \_\{10\},\; \_\{10\}$. Относительно определённого для классов вычетов умножения они образуют группу, причём $\_\{10\}$ и $\_\{10\}$ взаимно обратны (то есть $\_\{10\}\{\backslash cdot\}\_\{10\}\; =\; \_\{10\}$), а $\_\{10\}$ и $\_\{10\}$ обратны сами себе.

Структура группы

Запись $C\_n$ означает «циклическая группа порядка n».

Структура группы $U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$

$n\backslash ;$	$U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$	$\backslash varphi(n)$	$\backslash lambda(n)\backslash ;$	генератор		$n\backslash ;$	$U(\backslash mathbb\{Z\}/n\backslash mathbb\{Z\})$	$\backslash varphi(n)$	$\backslash lambda(n)\backslash ;$	генератор
2	C 1	1	1	1		33	C 2 ×C 10	20	10	10, 2
3	C 2	2	2	2		34	C 16	16	16	3
4	C 2	2	2	3		35	C 2 ×C 12	24	12	6, 2
5	C 4	4	4	2		36	C 2 ×C 6	12	6	19, 5
6	C 2	2	2	5		37	C 36	36	36	2
7	C 6	6	6	3		38	C 18	18	18	3
8	C 2 ×C 2	4	2	7, 3		39	C 2 ×C 12	24	12	38, 2
9	C 6	6	6	2		40	C 2 ×C 2 ×C 4	16	4	39, 11, 3
10	C 4	4	4	3		41	C 40	40	40	6
11	C 10	10	10	2		42	C 2 ×C 6	12	6	13, 5
12	C 2 ×C 2	4	2	5, 7		43	C 42	42	42	3
13	C 12	12	12	2		44	C 2 ×C 10	20	10	43, 3
14	C 6	6	6	3		45	C 2 ×C 12	24	12	44, 2
15	C 2 ×C 4	8	4	14, 2		46	C 22	22	22	5
16	C 2 ×C 4	8	4	15, 3		47	C 46	46	46	5
17	C 16	16	16	3		48	C 2 ×C 2 ×C 4	16	4	47, 7, 5
18	C 6	6	6	5		49	C 42	42	42	3
19	C 18	18	18	2		50	C 20	20	20	3
20	C 2 ×C 4	8	4	19, 3		51	C 2 ×C 16	32	16	50, 5
21	C 2 ×C 6	12	6	20, 2		52	C 2 ×C 12	24	12	51, 7
22	C 10	10	10	7		53	C 52	52	52	2
23	C 22	22	22	5		54	C 18	18	18	5
24	C 2 ×C 2 ×C 2	8	2	5, 7, 13		55	C 2 ×C 20	40	20	21, 2
25	C 20	20	20	2		56	C 2 ×C 2 ×C 6	24	6	13, 29, 3
26	C 12	12	12	7		57	C 2 ×C 18	36	18	20, 2
27	C 18	18	18	2		58	C 28	28	28	3
28	C 2 ×C 6	12	6	13, 3		59	C 58	58	58	2
29	C 28	28	28	2		60	C 2 ×C 2 ×C 4	16	4	11, 19, 7
30	C 2 ×C 4	8	4	11, 7		61	C 60	60	60	2
31	C 30	30	30	3		62	C 30	30	30	3
32	C 2 ×C 8	16	8	31, 3		63	C 6 ×C 6	36	6	2, 5

Применение

История

Вклад в исследование структуры мультипликативной группы кольца вычетов внесли Артин , Билхарц, Брауэр , Вильсон, Гаусс , Лагранж , Лемер, Уоринг , Ферма, Хули, Эйлер . Лагранж доказал лемму о том, что если $f(x)\; \backslash in\; k[x]$, и k - поле, то f имеет не более n различных корней, где n - степень f. Он же доказал важное следствие этой леммы, заключающееся в сравнении $x^\{p-1\}-1$ ≡ $(x-1)(x-2)...(x-p+1)mod(p)$. Эйлер доказал малую теорему Ферма . Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых - k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.

Напишите отзыв о статье "Мультипликативная группа кольца вычетов"

Примечания

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. - М .: Мир, 1987.
• Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. - Москва: «Гелиос АРВ», 2002.
• Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - Санкт-Петербург: НПО «Профессионал», 2004.

Ссылки

• Бухштаб А. А. Теория чисел. - М .: Просвещение, 1966.
• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .

Отрывок, характеризующий Мультипликативная группа кольца вычетов

– Получил известие. В числе пленных нет, в числе убитых нет. Кутузов пишет, – крикнул он пронзительно, как будто желая прогнать княжну этим криком, – убит!
Княжна не упала, с ней не сделалось дурноты. Она была уже бледна, но когда она услыхала эти слова, лицо ее изменилось, и что то просияло в ее лучистых, прекрасных глазах. Как будто радость, высшая радость, независимая от печалей и радостей этого мира, разлилась сверх той сильной печали, которая была в ней. Она забыла весь страх к отцу, подошла к нему, взяла его за руку, потянула к себе и обняла за сухую, жилистую шею.
– Mon pere, – сказала она. – Не отвертывайтесь от меня, будемте плакать вместе.
– Мерзавцы, подлецы! – закричал старик, отстраняя от нее лицо. – Губить армию, губить людей! За что? Поди, поди, скажи Лизе. – Княжна бессильно опустилась в кресло подле отца и заплакала. Она видела теперь брата в ту минуту, как он прощался с ней и с Лизой, с своим нежным и вместе высокомерным видом. Она видела его в ту минуту, как он нежно и насмешливо надевал образок на себя. «Верил ли он? Раскаялся ли он в своем неверии? Там ли он теперь? Там ли, в обители вечного спокойствия и блаженства?» думала она.
– Mon pere, [Отец,] скажите мне, как это было? – спросила она сквозь слезы.
– Иди, иди, убит в сражении, в котором повели убивать русских лучших людей и русскую славу. Идите, княжна Марья. Иди и скажи Лизе. Я приду.
Когда княжна Марья вернулась от отца, маленькая княгиня сидела за работой, и с тем особенным выражением внутреннего и счастливо спокойного взгляда, свойственного только беременным женщинам, посмотрела на княжну Марью. Видно было, что глаза ее не видали княжну Марью, а смотрели вглубь – в себя – во что то счастливое и таинственное, совершающееся в ней.
– Marie, – сказала она, отстраняясь от пялец и переваливаясь назад, – дай сюда твою руку. – Она взяла руку княжны и наложила ее себе на живот.
Глаза ее улыбались ожидая, губка с усиками поднялась, и детски счастливо осталась поднятой.
Княжна Марья стала на колени перед ней, и спрятала лицо в складках платья невестки.
– Вот, вот – слышишь? Мне так странно. И знаешь, Мари, я очень буду любить его, – сказала Лиза, блестящими, счастливыми глазами глядя на золовку. Княжна Марья не могла поднять головы: она плакала.
– Что с тобой, Маша?
– Ничего… так мне грустно стало… грустно об Андрее, – сказала она, отирая слезы о колени невестки. Несколько раз, в продолжение утра, княжна Марья начинала приготавливать невестку, и всякий раз начинала плакать. Слезы эти, которых причину не понимала маленькая княгиня, встревожили ее, как ни мало она была наблюдательна. Она ничего не говорила, но беспокойно оглядывалась, отыскивая чего то. Перед обедом в ее комнату вошел старый князь, которого она всегда боялась, теперь с особенно неспокойным, злым лицом и, ни слова не сказав, вышел. Она посмотрела на княжну Марью, потом задумалась с тем выражением глаз устремленного внутрь себя внимания, которое бывает у беременных женщин, и вдруг заплакала.
– Получили от Андрея что нибудь? – сказала она.
– Нет, ты знаешь, что еще не могло притти известие, но mon реrе беспокоится, и мне страшно.
– Так ничего?
– Ничего, – сказала княжна Марья, лучистыми глазами твердо глядя на невестку. Она решилась не говорить ей и уговорила отца скрыть получение страшного известия от невестки до ее разрешения, которое должно было быть на днях. Княжна Марья и старый князь, каждый по своему, носили и скрывали свое горе. Старый князь не хотел надеяться: он решил, что князь Андрей убит, и не смотря на то, что он послал чиновника в Австрию розыскивать след сына, он заказал ему в Москве памятник, который намерен был поставить в своем саду, и всем говорил, что сын его убит. Он старался не изменяя вести прежний образ жизни, но силы изменяли ему: он меньше ходил, меньше ел, меньше спал, и с каждым днем делался слабее. Княжна Марья надеялась. Она молилась за брата, как за живого и каждую минуту ждала известия о его возвращении.

– Ma bonne amie, [Мой добрый друг,] – сказала маленькая княгиня утром 19 го марта после завтрака, и губка ее с усиками поднялась по старой привычке; но как и во всех не только улыбках, но звуках речей, даже походках в этом доме со дня получения страшного известия была печаль, то и теперь улыбка маленькой княгини, поддавшейся общему настроению, хотя и не знавшей его причины, – была такая, что она еще более напоминала об общей печали.
– Ma bonne amie, je crains que le fruschtique (comme dit Фока – повар) de ce matin ne m"aie pas fait du mal. [Дружочек, боюсь, чтоб от нынешнего фриштика (как называет его повар Фока) мне не было дурно.]
– А что с тобой, моя душа? Ты бледна. Ах, ты очень бледна, – испуганно сказала княжна Марья, своими тяжелыми, мягкими шагами подбегая к невестке.
– Ваше сиятельство, не послать ли за Марьей Богдановной? – сказала одна из бывших тут горничных. (Марья Богдановна была акушерка из уездного города, жившая в Лысых Горах уже другую неделю.)
– И в самом деле, – подхватила княжна Марья, – может быть, точно. Я пойду. Courage, mon ange! [Не бойся, мой ангел.] Она поцеловала Лизу и хотела выйти из комнаты.
– Ах, нет, нет! – И кроме бледности, на лице маленькой княгини выразился детский страх неотвратимого физического страдания.
– Non, c"est l"estomac… dites que c"est l"estomac, dites, Marie, dites…, [Нет это желудок… скажи, Маша, что это желудок…] – и княгиня заплакала детски страдальчески, капризно и даже несколько притворно, ломая свои маленькие ручки. Княжна выбежала из комнаты за Марьей Богдановной.
– Mon Dieu! Mon Dieu! [Боже мой! Боже мой!] Oh! – слышала она сзади себя.
Потирая полные, небольшие, белые руки, ей навстречу, с значительно спокойным лицом, уже шла акушерка.
– Марья Богдановна! Кажется началось, – сказала княжна Марья, испуганно раскрытыми глазами глядя на бабушку.
– Ну и слава Богу, княжна, – не прибавляя шага, сказала Марья Богдановна. – Вам девицам про это знать не следует.
– Но как же из Москвы доктор еще не приехал? – сказала княжна. (По желанию Лизы и князя Андрея к сроку было послано в Москву за акушером, и его ждали каждую минуту.)
– Ничего, княжна, не беспокойтесь, – сказала Марья Богдановна, – и без доктора всё хорошо будет.
Через пять минут княжна из своей комнаты услыхала, что несут что то тяжелое. Она выглянула – официанты несли для чего то в спальню кожаный диван, стоявший в кабинете князя Андрея. На лицах несших людей было что то торжественное и тихое.
Княжна Марья сидела одна в своей комнате, прислушиваясь к звукам дома, изредка отворяя дверь, когда проходили мимо, и приглядываясь к тому, что происходило в коридоре. Несколько женщин тихими шагами проходили туда и оттуда, оглядывались на княжну и отворачивались от нее. Она не смела спрашивать, затворяла дверь, возвращалась к себе, и то садилась в свое кресло, то бралась за молитвенник, то становилась на колена пред киотом. К несчастию и удивлению своему, она чувствовала, что молитва не утишала ее волнения. Вдруг дверь ее комнаты тихо отворилась и на пороге ее показалась повязанная платком ее старая няня Прасковья Савишна, почти никогда, вследствие запрещения князя,не входившая к ней в комнату.
– С тобой, Машенька, пришла посидеть, – сказала няня, – да вот княжовы свечи венчальные перед угодником зажечь принесла, мой ангел, – сказала она вздохнув.
– Ах как я рада, няня.
– Бог милостив, голубка. – Няня зажгла перед киотом обвитые золотом свечи и с чулком села у двери. Княжна Марья взяла книгу и стала читать. Только когда слышались шаги или голоса, княжна испуганно, вопросительно, а няня успокоительно смотрели друг на друга. Во всех концах дома было разлито и владело всеми то же чувство, которое испытывала княжна Марья, сидя в своей комнате. По поверью, что чем меньше людей знает о страданиях родильницы, тем меньше она страдает, все старались притвориться незнающими; никто не говорил об этом, но во всех людях, кроме обычной степенности и почтительности хороших манер, царствовавших в доме князя, видна была одна какая то общая забота, смягченность сердца и сознание чего то великого, непостижимого, совершающегося в эту минуту.
В большой девичьей не слышно было смеха. В официантской все люди сидели и молчали, на готове чего то. На дворне жгли лучины и свечи и не спали. Старый князь, ступая на пятку, ходил по кабинету и послал Тихона к Марье Богдановне спросить: что? – Только скажи: князь приказал спросить что? и приди скажи, что она скажет.
– Доложи князю, что роды начались, – сказала Марья Богдановна, значительно посмотрев на посланного. Тихон пошел и доложил князю.
– Хорошо, – сказал князь, затворяя за собою дверь, и Тихон не слыхал более ни малейшего звука в кабинете. Немного погодя, Тихон вошел в кабинет, как будто для того, чтобы поправить свечи. Увидав, что князь лежал на диване, Тихон посмотрел на князя, на его расстроенное лицо, покачал головой, молча приблизился к нему и, поцеловав его в плечо, вышел, не поправив свечей и не сказав, зачем он приходил. Таинство торжественнейшее в мире продолжало совершаться. Прошел вечер, наступила ночь. И чувство ожидания и смягчения сердечного перед непостижимым не падало, а возвышалось. Никто не спал.

Была одна из тех мартовских ночей, когда зима как будто хочет взять свое и высыпает с отчаянной злобой свои последние снега и бураны. Навстречу немца доктора из Москвы, которого ждали каждую минуту и за которым была выслана подстава на большую дорогу, к повороту на проселок, были высланы верховые с фонарями, чтобы проводить его по ухабам и зажорам.
Княжна Марья уже давно оставила книгу: она сидела молча, устремив лучистые глаза на сморщенное, до малейших подробностей знакомое, лицо няни: на прядку седых волос, выбившуюся из под платка, на висящий мешочек кожи под подбородком.
Няня Савишна, с чулком в руках, тихим голосом рассказывала, сама не слыша и не понимая своих слов, сотни раз рассказанное о том, как покойница княгиня в Кишиневе рожала княжну Марью, с крестьянской бабой молдаванкой, вместо бабушки.
– Бог помилует, никогда дохтура не нужны, – говорила она. Вдруг порыв ветра налег на одну из выставленных рам комнаты (по воле князя всегда с жаворонками выставлялось по одной раме в каждой комнате) и, отбив плохо задвинутую задвижку, затрепал штофной гардиной, и пахнув холодом, снегом, задул свечу. Княжна Марья вздрогнула; няня, положив чулок, подошла к окну и высунувшись стала ловить откинутую раму. Холодный ветер трепал концами ее платка и седыми, выбившимися прядями волос.
– Княжна, матушка, едут по прешпекту кто то! – сказала она, держа раму и не затворяя ее. – С фонарями, должно, дохтур…
– Ах Боже мой! Слава Богу! – сказала княжна Марья, – надо пойти встретить его: он не знает по русски.
Княжна Марья накинула шаль и побежала навстречу ехавшим. Когда она проходила переднюю, она в окно видела, что какой то экипаж и фонари стояли у подъезда. Она вышла на лестницу. На столбике перил стояла сальная свеча и текла от ветра. Официант Филипп, с испуганным лицом и с другой свечей в руке, стоял ниже, на первой площадке лестницы. Еще пониже, за поворотом, по лестнице, слышны были подвигавшиеся шаги в теплых сапогах. И какой то знакомый, как показалось княжне Марье, голос, говорил что то.