Задача дискретного логарифмирования
|
Скачать 0.51 Mb.
|
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). В случае, если bi b2i (mod n) (Замечание: bi b2i встречается с незначительной вероятностью), 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 bi b2i mod n. Если r = 0, то завершиться с ошибкой (then terminate with failure); иначе, вычислить x = r -1 (a2i a 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 на три подмножества в соответствии с правилом x S1 если x 1 (mod 3), x S2 если x 0 (mod 3), и x S3 если x 2 (mod 3). Таблица 3.2 показывает значения xi, ai, bi, x2i , a2i , и b2i в конце каждой итерации шага 2 Алгоритма 3.60. Заметим, что x14 = x28 = 144. Вычислить, наконец, r = b14 – b28 mod 191 = 125, r -1 = 125 –1 mod 191 = 136, и r -1 (a28 – a14 ) mod 191 = 110. Следовательно, log 2 228 = 110.
Таблица 3. 2: Промежуточные шаги rho-алгоритма Полларда в Примере 3.61. 3.62 Утверждение Пусть G группа простого порядка n. Предположим, что функция f: G → G, описанная уравнением (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 i r, и тогда используется алгоритм Гаусса (Алгоритм 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 (Упростить запись) Присвоить значение q pi и e ei. 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 Присвоить значение xi ℓ0 + ℓ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-31 03 01-01 «математика (научно-производственная деятельность)». Для понимания... | | Лекции 50 часов Экзамен 8 семестр практические занятия 50 часов Диф зачет нет самостоятельная работа 20 часов Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления.... |
| Лекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления.... | | Лабораторная работа №2 Транспортная задача Транспортная задача (Задача Монжа — Канторовича) — задача об оптимальном плане перевозок продуктов из пунктов отправления в пункты... |
 | Задача 1 Задача 2 Медицина. Задача 3 Основные понятия моделирования Модель — это некоторое упрощенное подобие реального объекта, явления или процесса | | Экзаменационные вопросы Понятие математической модели. Инструментальные переменные и параметры математической модели. Критерий оптимизации и целевая функция Математические модели простейших экономических задач: задача использования сырья, задача о диете; задача планирования товарооборота;... |
| Комплексный анализ Автор: д-р физ мат наук, профессор, зав кафедрой дискретного анализа Бондаренко В. А | | Задача на границах периодической системы 3 Задача кот шредингера и химия 4 Задача 22. Необычные пути окисления жирных кислот: омега- и (омега-1)-окисление 42 |
| Задача №1. Вычислить определитель четвертого порядка Задача №2. Даны матрицы А, В, с и числа и Задача № Для данной матрицы найти обратную и убедиться, что обратная матрица найдена правильно | | Задача №1: получение данных 6 Задача №2 модели и программное обеспечение управления добычей 7 Задача №3 Переход к технологиям облачных вычислений в задачах связанных с «интеллектуальным месторождением». Высокопроизводительные... |