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



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

3.6.3 Rho-алгоритм Полларда для логарифмов

Rho-алгоритм Полларда (Алгоритм3.60) для вычисления дискретных логарифмов является рандомизированным алгоритмом с ожидаемым временем работы таким же, как у алгоритма маленьких и больших шагов (Алгоритм 3.56), но не требующим много памяти. По этой причине для практически важных задач на много предпочтительнее Алгоритм 3.56. Для простоты, в этом подразделе предполагается, что G - циклическая группа, где порядок n – простое число.

Группа G разделена на 3 множества S1, S2, и S3 приблизительно одинакового размера, на основании некоторого свойства, обеспечивающего удобство тестируемости. При выборе подмножеств необходимо исключить некоторые варианты, например, 1  S2. Определим последовательность элементов группы x0 , x1, x2, …, как x0 = 1 и

Xi+1 = f(xi) (3.2)

для i  0. Эта последовательность элементов группы в свою очередь определяет 2 последовательности целых чисел a0, a1, a2,…. и b0, b1, b2,…, удовлетворяющих условию xi = ai bi для i  0: a0 = 0, b0 = 0, и для i  0,

ai+1 = (3.3)

и

bi+1 = (3.4)
Алгоритм Флойда обнаружения циклов (Замечание 3.8) может быть использован для нахождения двух элементов группы xi и x2i таких, что xi = x2i.
Отсюда ai bi = a2 i b2 i, и, следовательно, bi - b2i = a2i - ai. Взяв от обеих частей последнего уравнения логарифм по основанию , получим

(bi - b2i )  log α β  (a2i - ai) (mod n).

В случае, если bib2i (mod n) (Замечание: bib2i встречается с незначительной вероятностью), log α β может быть легко найден из этого уравнения.
3.60 Алгоритм Rho-алгоритм Полларда для вычисления дискретных логарифмов

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

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

1. Присвоить значение x0  1, a0 0, b0  0.

2. Для i = 1, 2,…выполнять:

2.1 Используя значения xi-1, ai-1, bi-1 и x2 i - 2, a2 i – 2 , b2 i – 2 , вычисленные ранее, найти xi, ai, bi и x2i , a2i , b2i , используя равенства (3.2), (3.3) и (3.4).

2.2 Если xi = x2i, то выполнять следующее:

Присвоить значение r bib2i mod n.

Если r = 0, то завершиться с ошибкой (then terminate with failure); иначе, вычислить x = r -1 (a2ia i) mod n и вернуть (x).
В редком случае Алгоритм 3.60 заканчивается ошибкой, операцию можно повторить выбрав случайные целые a0, b0 из интервала [1; n -1], и начав с x0 = a0 b0. Rho-алгоритм Полларда иллюстрирует Пример 3.61 с искусственно маленькими параметрами.
3.61 Пример (Rho-алгоритм Полларда для логарифмов в подгруппе группы Z*383 ) Элемент  = 2 порождающий элемент подгруппы G множества Z*383 порядка n = 191. Положим = 228. Разделим элементы группы G на три подмножества в соответствии с правилом xS1 если x  1 (mod 3), xS2 если x  0 (mod 3), и xS3 если x  2 (mod 3). Таблица 3.2 показывает значения xi, ai, bi, x2i , a2i , и b2i в конце каждой итерации шага 2 Алгоритма 3.60. Заметим, что x14 = x28 = 144. Вычислить, наконец, r = b14b28 mod 191 = 125, r -1 = 125 –1 mod 191 = 136, и r -1 (a28a14 ) mod 191 = 110. Следовательно, log 2 228 = 110. 


i

xi

ai

bi

x2i

a2i

b2i

1

228

0

1

279

0

2

2

279

0

2

184

1

4

3

92

0

4

14

1

6

4

184

1

4

256

2

7

5

205

1

5

304

3

8

6

14

1

6

121

6

18

7

28

2

6

144

12

38

8

256

2

7

235

48

152

9

152

2

8

72

48

154

10

304

3

8

14

96

118

11

372

3

9

256

97

119

12

121

6

18

304

98

120

13

12

6

19

121

5

51

14

144

12

38

144

10

104


Таблица 3. 2: Промежуточные шаги rho-алгоритма Полларда в Примере 3.61.

3.62 Утверждение Пусть G группа простого порядка n. Предположим, что функция f: GG, описанная уравнением (3.2), ведет себя, как случайная функция. Тогда предположительное время работы rho-алгоритма Полларда для дискретных логарифмов в G равно O() групповых операций. Более того, алгоритм не требует много памяти.
3.6.4 Алгоритм Полига-Хеллмана

Алгоритм3.63 для вычисления логарифмов использует преимущество факторизации порядка n группы G. Пусть n = p1e 1 p2e2 prer - разложение на простые множители числа n. Если x = log α β, тогда решением будет определение xi = x mod piei для 1  ir, и тогда используется алгоритм Гаусса (Алгоритм 2.121) восстановления x mod n. Каждое целое xi определяется вычислением цифр 0, 1,… ei -1 согласно их pi-арному представлению: xi = 0 + 1pi + … + ei -1 piei -1, где 0  j pi -1.

Что бы увидеть, что результат работы Алгоритма 3.63 правильный, заметим сначала, что на шаге 2.3 порядком  будет q. Далее, на j-ой итерации шага 2.4,  = 0 + 1 q + … + i -1 q j - 1. Следовательно,

β = (β / ) n/q j + 1 = (x - ℓ 0 - 1 q - … - j -1 q j 1) n/q j + 1

= (n/q j + 1)x i - ℓ 0 - 1 q - … - j -1 q j 1

= (n/q j + 1) j q j +… + e -1 qe 1

= (n/q ) j +… + e -1 qe 1 – j = ( )j ,

последнее равенство будет верным, потому что имеет порядок q. Следовательно, logαβ действительно равен j .
3.63 Алгоритм Алгоритм Полига-Хеллмана для вычисления дискретных логарифмов

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

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

1. Найти разложение на простые множители числа n: n = p1e 1 p2e2 prer, где ei  1.

2. Для i от 1 до r выполнять:

(Вычислить xi = 0 + 1pi + … + ei -1 piei -1 , где xi = x mod piei )

2.1 (Упростить запись) Присвоить значение qpi и eei.

2.2 Присвоить значение  1 и -1 0.

2.3 Вычислить   n/q.

2.4 (Вычислить ℓj ) Для j от 0 до e - 1 выполнять:

Вычислить   j -1 q j 1 и β  ( β-1) n/ q j +1.

Вычислить j logαβ (например, используя Алгоритм 3.56; см. Замечание 3.67(iii)).

2.5 Присвоить значение xi0 + 1q + … + e -1 qe -1.

3. Используя алгоритм Гаусса (Алгоритм 2.121) вычислить целое x, 0  x n -1, такое, что x xi (mod piei ) для 1  i r.

4. Вернуть (x).
Пример 3.64 иллюстрирует Алгоритм 3.63 с искусственно маленькими параметрами.
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