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

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.  := b .

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

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

   1. если  = a ^j , то полагаем x = m  i + j

   2.  :=   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. В каких криптографических алгоритмах необходимо решать задачу дискретного логарифмирования?

§ 10 Группы

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

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

a(bc) = (ab)c.

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

ea = ae = a.

3. Для каждого элемента 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 имеют бесконечно много элементов.