Подгруппы

Группы

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

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

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

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

b = a ^x mod p.

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

b = a ^l mod p.

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

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

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

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

Утверждение. Пусть p – простое число, параметры a, b удовлетворяют неравенствам 1< a, b < p. Тогда сравнение b = a ^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, является дискретным логарифмом.

3. x:= k.

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

Пусть 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.

4. g:= b.

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

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

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

g:= g × t.

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

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

2. Вычисляем значения a ₁:= a ^r mod p, b ₁:= b ^r mod p.

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

b ₁:= a ₁ ^y mod p, ord a ₁ = q.

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

5. Вычисляем значения a ₂:= a ^q mod p, b ₂:= b × t mod p.

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

b ₂:= a ₂ ^z mod p, ord a ₂ = r.

7. x = z × q + y

Контрольные вопросы

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

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

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

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

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

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

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

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

1. Операция * в группе ассоциативна: для любых элементов a, b, и c из G выполняется равенство

a *(b * c) = (a * b)* c.

1. В множестве G существует такой единичный элемент e, что

e * a = a * e = a.

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

a * a ^–1 = a ^–1* a = e.

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

a * b = b * a.

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

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

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

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

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

Примеры групп:

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

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

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

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

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

Множество Z _n

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

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

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

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

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

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

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

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

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

Z _n^* = { a Î Z _n | (a, n) = 1 }

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

Если n – простое число, то j (n) = n – 1 и Z _n^* = { 1, 2, 3, …, n – 1 }.

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

a ^t = 1 mod n.

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

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

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

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

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

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

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

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

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

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

Z _n^* = { aⁱ mod n, i = 0, 1, 2, 3, …, j (n) – 1 }

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

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

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

a ^{j (n)/ p} ¹ 1 mod n

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

Примеры.

В группе Z ₂₁^* 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.

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

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

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

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

b ₀ = 2¹ mod 13 = 2

b ₁ = 2⁵ mod 13 = 32 mod 13 = 6

b ₂ = 2⁷ mod 13 = 128 mod 13 = 11

b ₃ = 2¹¹ mod 13 = 2048 mod 13 = 7.

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

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

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

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

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

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

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

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

a^k * a^m = a^{k + m} , (a^k) ^m = a^{k m}, a ^{– k} = (a ^{– 1}) ^k .

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

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

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

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

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

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

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

Пример. В группе Z ₂₉^* ord (24) = 14, 24¹⁰ = 20, ord (20) = 14 / НОД (14, 10) = 7.

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

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

Определение. Две группы (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. Каковы свойства образующих элементов группы Z _n^*?

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

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