Порядок элемента группы примеры

Порядок элемента группы примеры

Порядок группы

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

Порядок элемента группы

Пусть — произвольная группа и — некоторый ее элемент. Имеются две возможности:

  1. Все степени элемента различны, то есть . В этом случае говорят, что элемент имеет бесконечный порядок.
  2. Имеются совпадения при . Если, например, n" title="m>n" />, то , то есть существуют положительные степени элемента , равные единичному элементу. Пусть наименьший положительный показатель, для которого Тогда говорят, что — элемент конечного порядка .

В конечной группе все элементы будут конечного порядка.

Порядок группы с циклическими подгруппами

Пусть — данная группа. Любой ее элемент порождает некоторую циклическую подгруппу. Если — конечная группа, то и все ее циклические подгруппы конечны. Порядок группы делится на порядок ее любой подгруппы, в частности, на порядок любой циклической подгруппы. Этот порядок равен порядку образующего элемента. Таким образом, верна следующая теорема.

Теорема

Порядок конечной группы делится на порядок любого ее элемента.

Пусть — конечная группа порядка и — некоторый ее элемент порядка . Тогда (при целом ) и . Следовательно, верно следующее предположение:
Любой элемент конечной группы при возведении в степень порядка группы дает единичный элемент.
Следовательно, порядок конечной группы делится на порядок любого ее элемента.

Группы

Алгоритм Нечаева – Поллига — Хеллмана

Переборный алгоритм нахождения дискретного логарифма

Дискретный логарифм

Задача дискретного логарифмирования: при заданных значениях параметров a, b и p, p – простое число, 1 x mod p .

Определение. Дискретным логарифмом l числа b при основании a по модулю p называется степень, в которую нужно возвести число a, чтобы получить число b :

Другое название дискретного логарифма l – индекс числа b при основании a по модулю p .

Принятые обозначения : log a b и ind a b .

Определение. Наименьшая степень, в которую нужно возвести число a по модулю p , чтобы получить 1 , называется порядком числа a . Обозначение — ord a .

Утверждение. Пусть p – простое число. Максимальный порядок числа по модулю p равен p – 1.

Утверждение. Пусть p – простое число, параметры a, b удовлетворяют неравенствам 1 x mod p имеет единственное решение относительно x, если порядок числа a равен p – 1.

1. Вычисляем значения a k mod p для k = 1, 2, 3, … до выполнения равенства b = a k mod p .

2. Значение k, при котором выполняется сравнение b = a k mod p, является дискретным логарифмом.

Алгоритм больших — малых шагов (Шенкса)

Пусть n — порядок числа a .

1. Вычисляем m := énù, где énù — округление с избытком.

2. Строим таблицу пар ( j , a j ) для j = 0, 1, 2 , m-1.

3. Вычисляем t := a – m , решая сравнение a m × t = 1 mod p .

5. Цикл по i от 0 до m – 1

проверяем, является ли g второй компонентой в таблице п.2

если g = a j , то полагаем x = m × i + j

Пусть n — порядок числа a .

1. Число n представляем в виде n = q × r, q – простое число.

3. С помощью алгоритма больших — малых шагов находим y , решая сравнение

4. Вычисляем t := a – y , решая сравнение a y × t = 1 mod p .

6. С помощью алгоритма больших — малых шагов находим z , решая сравнение

1. Дайте определение дискретного логарифма.

2. Дайте определение порядка числа.

3. Сформулируйте условия существования дискретного логарифма.

4. Опишите переборный алгоритм дискретного логарифмирования.

5. Опишите алгоритм больших — малых шагов.

6. Опишите алгоритм Нечаева – Поллига — Хеллмана.

7. В каких криптографических алгоритмах необходимо решать задачу дискретного логарифмирования?

Определение. Группа (G, *) состоит из множества G, на котором определена бинарная операция * , удовлетворяющая трем аксиомам:

  1. Операция * в группе ассоциативна: для любых элементов a, b, и c из G выполняется равенство
  1. В множестве G существует такой единичный элемент e, что
Читайте также:  Сайты с поддержкой html5

  1. Для каждого элемента a Î G существует обратный элемент a –1 Î такой, что

Определение. Группа (G, *) называется коммутативной (абелевой), если для любых элементов a, b, и c из G выполняется равенство

Если в качестве бинарной операции определена операция умножения ´, то группа называется мультипликативной, единичный элемент e = 1, обратный элемент обозначается a –1 или 1 / a.

Если в качестве бинарной операции определена операция сложения +, то группа называется аддитивной, единичный элемент e = 0, обратный элемент обозначается – a.

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

Определение. Группа (G, *) называется конечной, если число элементов множества G конечно. В этом случае число элементов множества G называется порядком группы (G, *).

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

1. Множество всех ненулевых действительных чисел относительно операции умножения – «мультипликативная группа действительных чисел» R * .

2. Множество всех целых чисел относительно операции сложения – «аддитивная группа целых чисел» Z.

3. Множество всех векторов в пространстве R n относительно операции сложения векторов.

4. Множество всех многочленов с действительными коэффициентами относительно операции сложения многочленов.

Группы в примерах 1-4 имеют бесконечно много элементов.

Множество Zn

Пусть n – натуральное число. Введем на множестве целых чисел Z операцию сравнения по mod n: a mod n, a ÎZ. Операция сравнения по mod n разбивает множество Z на классы эквивалентности, соответствующие остаткам от деления целых чисел на n: 0, 1, 2, … , n–1. Множество классов эквивалентности по mod n образует множество Zn. Все арифметические операции < +, –, ´, : >в Zn выполняются по mod n .

Пример. Рассмотрим множество Z25= < 0, 1, 2,…, 24 >. Для элементов этого множества имеем 13 + 16 = 4, 13 ´ 4 = 2, 13 – 16 = 22, 15 : 2 = ?

Определение. Пусть a ÎZn. Мультипликативным обратным элементом элемента a по mod n называется элемент a – 1 , такой что a ´ a – 1 = 1 mod n. Элемент a называется обратимым по mod n, если для него существует обратный.

Деление в Zn определяется как умножение на обратный элемент a : b = a ´ b – 1 , если делитель b обратим.

Пример. В множестве Z25 2 – 1 = 13, т.к. сравнение 2 x = 1 mod 25 дает решение x = 13. Отсюда 15 : 2 = 15 ´ 2 – 1 = 15 ´ 13 = 195 = 20 mod 25.

Утверждение. Элемент a ÎZn обратим в том и только том случае, когда a и n взаимно просты, (a, n ) = 1.

Пример. Обратимые элементы в Z9 : 1, 2, 4, 5, 7, 8. Для определения 5 –1 решаем сравнение 5 x = 1 mod 9,которое дает решение x = 2. Отсюда 5 – 1 = 2.

Множество Zn с операцией сложения по mod n образует конечную аддитивную группу порядка n .

Введем множество Zn * , определяемое как подмножество множества Zn, состоящее только из обратимых элементов

Zn * = < a ÎZn |(a, n ) = 1 >

Множество Zn * с операцией умножения по mod n образует конечную мультипликатив-ную группу порядка j(n).

Если n– простое число, то j(n)= n – 1 и Zn * = < 1, 2, 3, …, n – 1 >.

Определение. Пусть a Î Zn * . Порядком элемента группы называется наименьшая степень t, в которую нужно возвести элемент, чтобы получить 1 :

a t = 1 mod n .

Обозначение t = ord ( a ).

Утверждение. Если ord ( a ) = t и a s = 1 mod n , то s делится на t .

Утверждение. Если t – порядок некоторого элемента a Î Zn * , то j(n) делится на t .

Определение. Если ord(a) = j(n) для a Î Zn * , то элемент a называется образующим, или примитивным, элементом группы.

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

Читайте также:  Rombica smart cast v04 4pda

Утверждение. Всякая циклическая группа абелева.

Свойства образующих (примитивных) элементов мультипликативной группы Zn *

1. Группа Zn * имеет образующий элемент в том и только том случае, когда

n = 2, 4, p k , 2p k , p – простое нечетное число.

2.Если a – образующий элемент Zn * , то

Zn * = < a i mod n, i = 0, 1, 2, 3, …, j(n) – 1 >

3.Если a – образующий элемент Zn * , то b = a i mod n является образующим элементом в том и только том случае, когда i взаимно просто с j(n), ( i , j(n)) = 1.

4.Если Zn * – циклическая группа, то число образующих элементов группы равно j (j(n)).

5.Элемент a Î Zn * является образующим элементом группы в том и только том случае, когда

a j (n)/ p ¹ 1 mod n

для любого простого делителя p числа j(n).

В группе Z21 * j(21)= ( 3 – 1 ) ( 7 – 1 ) = 12 элементов: 1,2,4,5,8,10,11,13,16,17,19,20. Каждый элемент имеет обратный, например, 2 – 1 = 11, 10 – 1 = 19. Группа не является циклической. Ord ( 1 ) = 1, ord ( 8,13,20 ) = 2, ord ( 4,16 ) = 3, ord ( 2,5,10,11,17,19 ) = 6.

В группе Z25 * j(25)= 5 ( 5 – 1 ) = 20 элементов. Группа циклическая, содержит j(j(25)) = j(20) =2 ( 2 – 1 ) ( 5 – 1 ) = 8 образующих.

В группе Z13 * j(13)= 13 – 1 = 12 элементов. Группа циклическая, содержит j(j(13)) = j(12) =2 ( 2 – 1 ) ( 3 – 1 ) = 4 образующих. Элемент a = 2 является образующим, так как 2 6 = 64 = 12 mod 13 ¹ 1, ( j(13)/2 = 6 ), 2 4 = 16 = 3 mod 13 ¹ 1, ( j(13)/3 = 4 ).

Найдем остальные образующие элементы: < i | ( i , j(n)) = 1 >= < 1, 5, 7, 11 >.

Образующие элементы – 2, 6, 7, 11:

Если некоторое подмножество H множества G само образует группу относительно операции *, определенной в G, то (H, *) называется подгруппой группы (G, *).

Например, подмножество четных целых чисел есть подгруппа аддитивной группы Z всех целых чисел, а подмножество нечетных чисел не будет подгруппой этой группы (сложение на Z не задает операцию на этом подмножестве, так как сумма двух нечетных чисел есть число четное).

Утверждение. Для того чтобы подмножество H образовывало подгруппу группы (G, *), необходимо и достаточно, чтобы выполнялись два условия:

1. Результат операции * (определенной в G) над любыми двумя элементами h1, h2 из подмножества H также является элементом из H ( h1*h2 Î H ).

2. Если h Î H, то и обратный к нему элемент h –1 принадлежит H ( h –1 Î H ).

Наиболее просты так называемые циклические подгруппы, которыми обладает любая группа G. Со всяким элементом a Î G можно связать «порожденную» им циклическую подгруппу, которая, по существу представляет собой наименьшую из подгрупп, содержащую данный элемент.

Введем понятие степени a i элемента a, полагая a i = a i – 1 * a, a 0 = e.

При таком определении степени выполняются правила действий со степенями: для любых целых чисел k и m

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

Утверждение. Пусть группа (G, *) содержит элемент a. Тогда все степени a i элемента a образуют циклическую подгруппу, порождаемую элементом a.

Определение. Наименьшая степень t , при которой a t = e называется порядком элемента a группы (G, *) , ord (a ) = t.

Утверждение. Циклическая подгруппа, порожденная элементом a порядка t, имеет порядок t.

Утверждение. Порядок любого элемента группы делит порядок группы.

Утверждение. (Теорема Лагранжа) Порядок любой подгруппы конечной группы является делителем порядка группы.

Утверджение. Если ord (a ) = t, то элемент a k имеет порядок, равный t / НОД ( t, k ).

Пример. В группе Z29 * ord (24) = 14 , 24 10 = 20, ord (20) = 14 / НОД ( 14, 10 ) = 7.

Утверждение. Если (G, *) – циклическая группа порядка n , d – делитель n , то группа (G, *) имеет ровно j( d)элементов порядка d .

Пример. Порядок группы Z29 * равен 28, d =14 – делитель порядка группы. Группа Z29 * имеет j( d)= j(14)= 6элементов порядка 14: 4, 5, 6, 9, 13, 22.

Читайте также:  Sony vegas черные полосы по бокам

Определение. Две группы (A, *) и (G, ·) называются изоморфными, если существует взаимно однозначное соответствие f : A ® G между элементами множеств A и G, сохраняющее действие операций : для любых элементов a, b Î A выполняется равенство f (a * b ) = f (a ) · f (b ) Î G .

Пример. Мультипликативная группа положительных вещественных чисел – ( R+ , ´ ). Аддитивная группа вещественных чисел – ( R , +). Взаимно однозначное соответствие – log : R+ ® R сохраняет действие операций в группах : log ( x y ) = log ( x ) + log ( y ). Следовательно, группы ( R+ , ´ ) и ( R , +) являются изоморфными.

1. Дайте определение группы.

2. Дайте определение порядка группы.

3. Что такое порядок элемента группы?

4. Какая группа называется коммутативной?

5. Дайте определение циклической группы.

6. Дайте определение подгруппы.

7. Дайте определение циклической подгруппы.

8. Какой элемент группы называется образующим?

9. Каковы свойства образующих элементов группы Zn * ?

10. Сформулируйте теорему Лагранжа.

11. Какие группы называются изоморфными?

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 8908 — | 7222 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Определение и примеры

В мультипликативной группе Q* любая натуральная степень двойки отлична от единицы, т.е. 2 п Ф 1 при любом натуральном показателе п. В этом случае говорят, что элемент 2 имеет бесконечный порядок. В этой же группе (-1) 2 = 1. В этом случае говорят, что элемент -1 имеет порядок 2. Дадим общее определение.

Определение 1.7. Пусть дана мультипликативная группа G с единицей ей ае G. Если а п Ф е для любого натурального показателя п, то будем говорить, что элемент а имеет бесконечный порядок, и писать |а| = °° (читается: порядок элемента а бесконечен) . Если же существует натуральное число т, такое что а т = е, то наименьшее натуральное число п, такое что а п = е, будем называть порядком элемента а и писать | а — п (читается: порядок элемента а равен п).

В аддитивной группе считаем |а| = °° Vne N па ф О и | а | = п п — наименьшее натуральное число, такое что па = 0.

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

Если | a | = то все степени элемента а можно изобразить целочисленными точками числовой прямой, здесь «кручения» нет (рис. 1.3).

Если же, например, | а | = 6, то степени элемента а повторяются с периодом 6, наблюдаем «кручение» (рис. 1.4).

  • 1. Аддитивная группа целых чисел Z является группой без кручения.
  • 2. Ясно, что в конечной группе порядок всякого элемента конечен.
  • 3. Мультипликативная группа комплексных корней всех степеней из единицы бесконечна, а всякий ее элемент имеет конечный порядок, т.е. это пример бесконечной периодической группы.
  • 4. Найдем порядок подстановки а = (135) (24) в симметрической группе подстановок S5. Терпеливо находим степени элемента а, пока не получим единицу группы (тождественную подстановку):

Ссылка на основную публикацию
Adblock detector