Группа вычетов по модулю n. Мультипликативная группа кольца вычетов. Оценим время работы процедуры. Если три числа, являющиеся её исходными данными, имеют не более β битов, то число арифметических операций ес

В §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 ). Тогда приведённая выше последовательность корней однозначно соответствует последовательности степеней примитивного элемента:

где 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) принадлежат к одному и тому же показателю.

Теорема 7.

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

В дальнейшем мы для простоты будем обозначать сложение и умножение по модулю обычными знаками + и ∙ (иногда опуская знак умножения), а аддит

5) Количество обратимых элементов в кольце вычетов.

Можно доказать такую формулу для функции Эйлера: (3) где p1,….,ps – список всех простых делителей числа n. Можно пояснить эту формулу так: случа

6) Подгруппы.

10. Если является подгруппой конечной группы, то делит.

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

12. Следствие 8.1.

13. 7) Подгруппа, порожденная элементом группы.

14. Если группа S конечна, то последовательность будет периодической (следующий элемент определяется предыдущим, поэтому раз повторившись, эл

15. Указанные t элементов образуют подгруппу, т.к. групповая операция соответствует сложению «показателей степени». Эта подгруппа называется

16. Вот несколько подгрупп группы Z6 , порожденных различными элементами: . Аналогичный пример для мультипликативной группы: здесь Из сказанно

17. Пусть - конечная группа. Если, то число элементов в подгруппе, порождаемой а, совпадает с порядком а (т.е.).

18. Следствие 9.1.

19. Следствие 9.2.

20. 8) Решение линейных диофантовых уравнений.

21. Напомним, что через обозначается порождённая элементом а подгруппа (в данном случае подгруппа группы Zn). По определению, поэтому уравнени

22. Пусть уравнение разрешимо и является его решением. Тогда уравнение имеет d =НОД(а,n) решений в Zn , задаваемых формулой, где i = 0,1,2,... , n - 1.

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

24. Пусть n > 1. Если НОД(а, n) = 1, то уравнение имеет единственное решение (в Zn). Случай b=1 особенно важен – при этом мы находим обратный к х элемент п

25. Следствие 10.2

26. 9) Китайская теорема об остатках.

27. Пусть некоторое число п представлено в виде произведения попарно взаимно простых чисел. Китайская теорема об остатках утверждает, что кол

28. 10) Степени элемента.

29. 11) Теорема 11 (Эйлер).

30. 12) Теорема 12 (малая теорема Ферма).

31. Следствие 12.1. Пусть p – простое число Следствие 12.2. Пусть p – простое число, тогда теорема Ферма будет применима и к а=0.

32. 13) Теорема 13 (Усиление теоремы Эйлера).

33. ч.т.д.

34. 14) Вычисление степеней повторным возведением в квадрат.

35. Пусть мы хотим вычислить ab mod n, где а – вычет по модулю n, a b – целое неотрицательное число, имеющее в двоичной записи вид (bk,bk-1,... ,b1,b0) (число з

36. При умножении с на 2 число ас возводится в квадрат, при увеличении с на 1 число ас умножается на a. На каждом шаге двоичная запись с сдвигается

37. Оценим время работы процедуры. Если три числа, являющиеся её исходными данными, имеют не более β битов, то число арифметических операций ес

38.

Тела группа, элементами к рой являются все ненулевые элементы данного тела, а операция совпадает с операцией умножения в теле. М. г. поля абелева группа. О. А. Иванова … Математическая энциклопедия

Приведённая система вычетов по модулю m множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) функция Эйлера. В качестве приведённой системы вычетов… … Википедия

Теория групп … Википедия

Группа в абстрактной алгебре непустое множество с определённой на нём бинарной операцией, удовлетворяющей указанным ниже аксиомам. Ветвь математики, занимающаяся группами, называется теорией групп. Всем знакомые вещественные числа наделены… … Википедия

Группа автоморфизмов нек рой полуторалинейной формы f на правом K модуле Е, где К кольцо; при этом f и Е(а иногда и К)удовлетворяют дополнительным условиям. Точного определения К. г. нет. Предполагается, что f либо нулевая, либо невырожденная… … Математическая энциклопедия

Группа всех обратимых матриц степени пнад ассоциативным кольцом K с единицей; общепринятое обозначение: GLn(K).или GL(n, К). П. л. г. GL(n, K) может быть также определена как группа автоморфизмов АutK(V) свободного правого K модуля Vс… … Математическая энциклопедия

Для общего описания теории групп см. Группа (математика) и Теория групп. Курсив обозначает ссылку на этот словарь. # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У … Википедия

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

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

Определение 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.

Ты - не раб!
Закрытый образовательный курс для детей элиты: "Истинное обустройство мира".
http://noslave.org

Материал из Википедии - свободной энциклопедии

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

Приведённая система вычетов

Приведённая система вычетов по модулю m - множество всех чисел полной системы вычетов по модулю m , взаимно простых с m . В качестве приведённой системы вычетов по модулю m обычно берутся взаимно простые с m числа от 1 до m - 1 .

Пример : приведенной системой вычетов по модулю 42 будет: { 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41 }.

Свойства

Приведённая система вычетов с умножением по модулю m образует группу , называемую мультипликативной группой или группой обратимых элементов кольца вычетов по модулю m , которая обозначается texvc или Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): U(\mathbb{Z}_m) .

Если m простое, то, как отмечалось выше, элементы 1, 2, ...,m -1 входят в Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): \mathbb{Z}_m^{\times} . В этом случае Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): \mathbb{Z}_m^{\times} является полем .

Формы записи

Кольцо вычетов по модулю n обозначают Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): \mathbb{Z}/n\mathbb{Z} или Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): \mathbb{Z}_n . Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): (\mathbb{Z}/n\mathbb{Z})^*, Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): (\mathbb{Z}/n\mathbb{Z})^\times, Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): U(\mathbb{Z}/n\mathbb{Z}), Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): E(\mathbb{Z}/n\mathbb{Z}), Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): \mathbb{Z}_n^{\times}, Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): U(\mathbb{Z}_n) .

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

Чтобы понять структуру группы Невозможно разобрать выражение (Выполняемый файл texvc , можно рассмотреть частный случай Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): n=p^a , где Невозможно разобрать выражение (Выполняемый файл texvc - простое число, и обобщить его. Рассмотрим простейший случай, когда Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): a=1 , т.е. Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): n=p .

Теорема: Невозможно разобрать выражение (Выполняемый файл texvc - циклическая группа.

Пример : Рассмотрим группу Невозможно разобрать выражение (Выполняемый файл texvc

Общий случай

Для рассмотрения общего случая необходимо определение примитивного корня . Примитивный корень по простому модулю Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): p – это число, которое вместе со своим классом вычетов порождает группу Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): U(\mathbb{Z}/p\mathbb{Z}) .

В случае целого модуля Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): n определение такое же.

Структуру группы определяет следующая теорема: Если p - нечётное простое число и l – целое положительное, то существуют примитивные корни по модулю Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): p^{l} , то есть Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): U(\mathbb{Z}/p^{l}\mathbb{Z}) - циклическая группа.

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

Пусть Невозможно разобрать выражение (Выполняемый файл texvc - нечётное число большее 1. Число Невозможно разобрать выражение (Выполняемый файл texvc однозначно представляется в виде Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): m-1 = 2^s \cdot t , где Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): t нечётно. Целое число Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): a , Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 1 < a < m , называется свидетелем простоты числа Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): m , если выполняется одно из условий:

• Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): a^t\equiv 1\pmod m

• существует целое число Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): k , Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 0\leq k , такое, что Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): a^{2^kt}\equiv m-1\pmod m.

Если число Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): m - составное, существует подгруппа мультипликативной группы кольца вычетов, называемая подгруппой свидетелей простоты. Её элементы, возведённые в степень Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): m-1 , совпадают с Невозможно разобрать выражение (Выполняемый файл texvc по модулю Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): m .

Пример : Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): m=9 . Есть Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 6 остатков, взаимно простых с Невозможно разобрать выражение (Выполняемый файл texvc , это Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 1,2,4,5,7 и Невозможно разобрать выражение (Выполняемый файл texvc . Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 8 эквивалентно Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): -1 по модулю Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 9 , значит Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 8^{8} эквивалентно Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 1 по модулю Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 9 . Значит, Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 1 и Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 8 - свидетели простоты числа Невозможно разобрать выражение (Выполняемый файл texvc не найден; См. math/README - справку по настройке.): 9 . В данном случае {1, 8} - подгруппа свидетелей простоты.