Задача дискретного логарифмирования



страница3/5
Дата22.12.2012
Размер0.51 Mb.
ТипЗадача
1   2   3   4   5

3.64 Пример (Алгоритм Полига-Хеллмана для логарифмов в Z*251 ) Пусть p = 251. Элемент  = 71 порождающий элемент Z*251 порядка n = 250. Рассмотрим β = 210. Тогда x = log 71 210 вычисляется так.

  1. Разложение на простые множители числа n будет 250 = 2 · 53.

  2. (a) (Вычислить x1 = x mod 2)

Вычислить  =  n/2 mod p = 250 и β = β n/2 mod p = 250. Отсюда x1 = log 250 250 = 1.

(b) (Вычислить x2 = x mod 53 = 0 + 1 5 + 2 52)

i. Вычислить =  n/5 mod p = 20.

ii. Вычислить  = 1 и β = (β-1 )n/5 mod p = 149. Используя исчерпывающий поиск (exhaustive search),5 вычислить 0 = log 20 149 = 2.

iii. Вычислить  =  2 mod p = 21 и β = (β-1 )n/25 mod p = 113. Используя исчерпывающий поиск, вычислить 1 = log 20 113 = 4.

iv. Вычислить  =  45 mod p = 115 и β = (β-1 )(p-1)/125 mod p = 149. Используя исчерпывающий поиск, вычислить 2 = log 20 149 = 2.

Следовательно, x2 = 2 + 4 · 5 + 2·5 2 = 72.

3. Наконец, найти пару сравнимых по модулю x  1 (mod 2), x  72 (mod 125) и получить x = log 71 210 = 197. 
5 В очень маленьких группах исчерпывающий поиск предпочтительнее Алгоритма 3.56 (здесь порядок равен 5).
3.65 Утверждение Дана факторизация n, временем выполнения алгоритма Полига-Хеллмана (Алгоритм 3.63) будет O( ri=1 ei (lg n + )) групповых умножений.
3.66 Замечание (эффективность алгоритма Полига-Хеллмана) Утверждение 3.65 означает, что алгоритм Полига-Хеллмана эффективен только если каждый простой делитель pi числа n относительно мал; то есть, если n является гладким числом (Определение 3.13). Пример группы, в которой алгоритм Полига-Хеллмана эффективен, следующий.
Рассмотрим мультипликативную группу Z*p, где p простое число из 107-цифр:

p = 227088231986781039743145181950291021585250524967592855

96453269189798311427475159776411276642277139650833937.

Порядком Z*p является n = p - 1 = 24 · 1047298 · 2247378 · 3503774. Так как наибольший простой делитель p - 1 только 350377, относительно просто вычислять логарифмы в этой группе, используя алгоритм Полига-Хеллмана.
3.67 Замечание (другие замечания)

(i) Если n простое, то Алгоритм3.63 (Полига-Хеллмана) аналогичен алгоритму маленьких и больших шагов (Алгоритм 3.56).

(ii) На 1 шаге Алгоритма3.63, должен применяться алгоритм факторизации, который находит сначала маленькие множители (например, Алгоритм 3.9), если порядок n не является гладким, следовательно, Алгоритм 3.63 все равно не эффективен.

(iii) Необходимость задействования памяти согласно Алгоритму3.56 на шаге 2.4 может быть исключена путем использования вместо него rho-алгоритма Полларда (Алгоритм 3.60).
3.6.5 Алгоритм вычисления индекса

Алгоритм вычисления индекса является наиболее мощным из известных методов вычисления дискретных логарифмов. Применяющийся метод не подходит для всех групп, но когда это возможно, время работы алгоритма не превышает экспоненциальное. Алгоритм впервые реализован для основных параметров циклической группы G (Алгоритм3.68). Далее представлены два примера для иллюстрации работы алгоритма вычисления индекса в двух видах групп, которые используются на практике, а именно Z*p (Пример 3.69) и F*2 m (Пример 3.70).

Алгоритм вычисления индекса требует выбор относительно маленького подмножества S элементов группы G, называемых ключевыми элементами факторизации, таким образом, что бы значительная часть элементов группы G могла быть легко представлена, как произведение элементов S. Алгоритм 3.68 продолжает делать предварительные вычисления базы данных, содержащую логарифмы всех элементов множества S, а затем многократно использует эту базу данных каждый раз, когда потребуется узнать логарифм определенной группы элементов.

Описание Алгоритма 3.68 не завершено по двум причинам. Во-первых, не определен способ выбора ключевых элементов факторизации S. Во-вторых, не известен метод эффективной генерации соотношений выражений (3.5) и (3.7). Ключевые элементы факторизации S должны быть подгруппой группы G, которая мала (так что система уравнений, решаемая на 3 шаге, не слишком большая), но и не очень маленькая (так что ожидаемое число попыток получить отношение (3.5) или (3.7) не слишком большое). Соответствующие ключевые элементы факторизации и способы получения соотношений известны для некоторых циклических групп, включая Z*p (см. §3.6.5(i)) и F*2 m (см. §3.6.5(ii)), и, более того, мультипликативную группу F*q общего конечного поля Fq.
3.68 Алгоритм Алгоритм вычисления индекса для дискретных логарифмов в циклических группах

ВХОД: порождающий элемент  циклической группы G порядка n, и элемент β G.

ВЫХОД: дискретный логарифм y = log α β.

1. (Выбор ключевых элементов факторизации S) Выберите подмножество S = {p1, p2,…, pt} из G такое, что “значительное количество (significant proportion)” всех элементов в G могло бы быть эффективно представлено, как произведение элементов из S.

2. (Получение линейных соотношений, включающих логарифмы элементов из S)

2.1 Выберите любое целое k, 0  k n -1, и вычислите k.

    1. Попытайтесь записать k, как произведение элементов S:

k = (3.5)

Если получилось, взяв логарифмы от обеих частей равенства (3.5), получить линейное соотношение

k (3.6)

2.3 Повторять шаги 2.1 и 2.2, пока не получим t + c соотношений вида (3.6) (c –маленькое положительное целое, если, например, c = 10, то система уравнений из t + c соотношений в большой вероятностью будет иметь единственное решение).

3. (Поиск логарифмов элементов S) Чтобы получить значения log pi, 1  i t вычислить по модулю n решение линейной системы из t + c уравнений (при неизвестном t) вида (3.6), полученных на 2 шаге.

4. (Вычисление y)

4.1 Выбрать любое целое k, 0  k n-1, и вычислить β · k.

4.2 Попытаться записать β · k, как произведение элементов S:

β · k = (3.7)

Если попытка неудачна, повторить шаг 4.1. Или же взять логарифмы от обеих частей уравнения (3.7) log α β = (ti=1 di log α pi k) mod n; таким образом вычислить y = (ti=1 di log α pi k) mod n и вернуть (y).
(i) Алгоритм вычисления индекса в Z*p

Для поля Zp, p простое, ключевые элементы факторизации S могут выбираться, как первые t простых чисел. Соотношение (3.5) получается при вычислении k mod p и использовании пробного деления (trial division), что бы проверить, действительно ли это целое является произведением простых чисел из S. Пример 3.69 иллюстрирует Алгоритм 3.68 в Z*p на задаче с искусственно маленькими параметрами.
3.69 Пример (Алгоритм 3.68 для логарифмов в Z*229 ) Пусть p = 229. Элемент  = 6 порождающий элемент группы Z*229 порядка n = 228. Рассмотрим β = 13. Тогда log6 13 вычисляется с использованием алгоритма вычисления индекса следующим образом.

1.Ключевыми элементами факторизации выбираются первые 5 простых: S = {2, 3, 5, 7, 11}.

2.Получены следующие 6 соотношений, включающие элементы из ключевых элементов факторизации (неудачные попытки не показываются):
6100 mod 229 = 180 = 22 · 3 2 · 5

618 mod 229 = 176 = 24 · 11

612 mod 229 = 165 = 3 · 5 · 11

662 mod 229 = 154 = 2 · 7· 11

6143 mod 229 = 198 = 2 · 3 2 · 11

6206 mod 229 = 210 = 2 · 3 · 5 · 7.
Эти соотношения дают следующие 6 уравнений, включающих логарифмы элементов из ключевых элементов факторизации:
100  2 log 6 2 + 2log 6 3 + log 6 5 (mod 228)

18  4 log 6 2 + log 6 11 (mod 228)

12  log 6 3 + log 6 5 + log 6 11 (mod 228)

62  log 6 2 + log 6 7 + log 6 11 (mod 228)

143  log 6 2 + 2log 6 3 + log 6 11 (mod 228)

206  log 6 2 + log 6 3 + log 6 5 + log 6 7 (mod 228).
3.Решение линейной системы из 6 уравнений с 5 неизвестными (логарифм xi = log 6 pi) дает значения log 6 2 = 21, log 6 3 = 208, log 6 5 = 98, log 6 7 = 107, и log 6 11 = 162.

4.Предположим, что выбрано целое k = 77. Так как β · k = 13 · 6 77 mod 229 = 147 = 3 · 72, то
log 6 13 = (log 6 3 + 2log 6 7 - 77) mod 228 = 117. ڤ
(ii) Алгоритм вычисления индекса в F*2 m

Элементы конечного поля F2 m представлены, как полиномы в Z2[x] порядка не более m-1, где умножение производится по модулю постоянного неприводимого многочлена f(x) степени m в Z2[x] (см. §2.6). Ключевые элементы факторизации S могут быть выбраны, как множество неприводимых многочленов в Z2[x] степени не более какой-то заданной границы b. Соотношение (3.5) получается при вычислении k mod f(x) и использовании пробного деления для проверки, является ли этот полином произведением многочленов в S. Пример 3.70 иллюстрирует Алгоритм 3.68 в F*2 m на задаче с искусственно маленькими параметрами.
3.70 Пример (Алгоритм 3.68 для логарифмов в F*27 ) Полином f(x) =x7 + x + 1 неприводим на Z2 . Следовательно, элементы конечного поля F27 порядка 128 могут быть представлены, как множество многочленов в Z2 [x] степени не более 6, где выполняется умножение по модулю f(x). Порядок группы F*27 число n = 27 - 1 = 127, и  = x порождающий элемент группы F*27. Пусть β = x4 + x3 + x2 + x+ 1. Тогда y = log x β вычисляется с использованием алгоритма вычисления индекса следующим образом.

1. Ключевыми элементами факторизации выбрано множество неприводимых многочленов в Z2 [x] со степенью, не превышающей 3: S = {x, x + 1, x2 + x + 1, x3 + x + 1, x3 + x2 + 1}.

2.Получены следующие 5 соотношений, включающие элементы из множества ключевых элементов факторизации (неудачные попытки не показаны):
x18 mod f(x) = x6 + x4 = x4 (x + 1)2

x105mod f(x) = x6 + x5 + x4 + x = x(x + 1)2 (x3 + x2 + 1)

x72 mod f(x) = x6 + x5 + x3 + x2 = x2 (x + 1)2 (x2+ x + 1)

x45 mod f(x) = x5 + x2+ x + 1 = (x + 1)2 (x3 + x + 1)

x121 mod f(x) = x6 + x5 + x4 + x3 + x2 + x + 1= ( x3 + x + 1)( x3 + x2 +1).
Эти соотношения дают следующие 5 уравнений, включающих логарифмы элементов из ключевых элементов факторизации (для удобства записи, пусть p1 = log x x, p2 = log x (x+1), p3 = log x (x2 + x + 1), p4 = log x (x3 + x + 1), и p5 = log x (x3+ x2 + 1)):
18  4 p1 + 2 p2 (mod 127)

105  p1 + 2 p2 + p5 (mod 127)

72  2 p1+ 2 p2 + p3 (mod 127)

45  2 p2 + p4 (mod 127)

121  p4 + p5 (mod 127).
3. Решение линейной системы из 5 уравнений с 5 неизвестными дает значения p1 = 1, p2 = 7, p3 = 56, p4 = 31, и p5 = 90.

4. Допустим выбрано k = 66. Так как β · k = (x4 + x3 + x2 + x + 1) x66 mod f(x) = x5 + x3 + x = x (x2 + x + 1)2, то log x (x4 + x3 + x2 + x + 1) = ( p1+ 2 p3 - 66) mod 127 = 47. 
1   2   3   4   5

Похожие:

Задача дискретного логарифмирования iconМетоды факторизации и дискретного логарифмирования
Учебный курс предназначен для студентов специальности 1-31 03 01-01 «математика (научно-производственная деятельность)». Для понимания...
Задача дискретного логарифмирования iconЛекции 50 часов Экзамен 8 семестр практические занятия 50 часов Диф зачет нет самостоятельная работа 20 часов
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Задача дискретного логарифмирования iconЛекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Задача дискретного логарифмирования iconЛабораторная работа №2 Транспортная задача
Транспортная задача (Задача Монжа — Канторовича) — задача об оптимальном плане перевозок продуктов из пунктов отправления в пункты...
Задача дискретного логарифмирования iconЗадача 1 Задача 2 Медицина. Задача 3 Основные понятия моделирования
Модель — это некоторое упрощенное подобие реального объекта, явления или процесса
Задача дискретного логарифмирования iconЭкзаменационные вопросы Понятие математической модели. Инструментальные переменные и параметры математической модели. Критерий оптимизации и целевая функция
Математические модели простейших экономических задач: задача использования сырья, задача о диете; задача планирования товарооборота;...
Задача дискретного логарифмирования iconКомплексный анализ
Автор: д-р физ мат наук, профессор, зав кафедрой дискретного анализа Бондаренко В. А
Задача дискретного логарифмирования iconЗадача на границах периодической системы 3 Задача кот шредингера и химия 4
Задача 22. Необычные пути окисления жирных кислот: омега- и (омега-1)-окисление 42
Задача дискретного логарифмирования iconЗадача №1. Вычислить определитель четвертого порядка Задача №2. Даны матрицы А, В, с и числа  и 
Задача № Для данной матрицы найти обратную и убедиться, что обратная матрица найдена правильно
Задача дискретного логарифмирования iconЗадача №1: получение данных 6 Задача №2 модели и программное обеспечение управления добычей 7
Задача №3 Переход к технологиям облачных вычислений в задачах связанных с «интеллектуальным месторождением». Высокопроизводительные...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org