Processing math: 62%

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

ро-метод Полларда для дискретного логарифмирования(ρ-метод) — алгоритм дискретного логарифмирования вкольце вычетов по простому модулю, имеющий экспоненциальную сложность.Предложен британским математиком в 1978 году, основные идеи алгоритмаочень похожи на идеи ро-алгоритма Полларда для факторизации чисел.Данный метод рассматривается для группы ненулевых вычетов по модулю p,где p — простое число, большее 3.

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


 Для заданного простого числа p и двух целых чисел a и b требуетсянайти целое число x, удовлетворяющее сравнению:
 где b является элементом циклической группы G, порожденной элементомa.

Алгоритмро-метода


 Рассматриваются последовательность пар {ui, vi} целых чисел помодулю p1 и последовательность {zi} целых чисел по модулю p,определенные следующим образом :
 a\^\{v\_\{i+1\}\} \{pmod\{p\} =\{begin\{cases\}bz\_i\{;\{bmod\{;p, \&05\}\}
Замечание: во всех выражениях рассматривается наименьшиенеотрицательные вычеты.
Замечание 2: в более общем случае возможно разбиение на 3подмножества несколько иным способом: разбиваем группу G на трипримерно равных по мощности подмножества S1,S2,S3 так, чтобы 1не принадлежала подмножеству S2.
 Поскольку каждая треть отрезка, которой принадлежит элемент, вероятно,никак не связана с элементами последовательностей {ui,vi},полученная последовательность — псевдослучайная. Поэтому могутсуществовать такие числа j и k, что zk=zj. Если удастся найтитакую пару чисел, то получится:
 Если число ujuk взаимно простое с числом p1, то этосравнение можно решить и найти дискретный логарифм:
 Если же наибольший общий делитель чисел ujuk и p1 равенчислу d>1, то существует решение этого сравнения для x по модулю(p1)/d. Пусть x=x0 (mod(p1)/d), тогда искомое числоx=x0+m(p1)/d, где m может принимать значения0,1,...,d1. Поэтому если d — достаточно небольшое число, тозадача решается перебором всех возможных значений для m. В худшемслучае — когда d=p1 — метод оказывается ничем не лучшеполного перебора всех возможных значений для дискретного логарифма.
 Для поиска индексов j и k используется алгоритм поиска цикловФлойда. При использовании данного алгоритма на i-м шаге имеютсязначения (zi, ui, vi, z2i, u2i, v2i) и ищется номерi, для которого zi=z2i. Наименьшее значение i, при которомвыполняется данное условие, называется епактой. Если при этом(u2iui, p1)=1, то

Pо-метод для группы точек эллиптическойкривой


 Пусть задана группа точек эллиптической кривой (ЭК) E(Fp). Неограничивая общности, можно предположить, что p>3 и p — простоечисло. Обозначим подгруппу E(Fp) порядка n через G и зафиксируемпорождающий элемент P. Для произвольного элемента группы Q=xPзадача дискретного логарифмирования заключается в нахождении элемента1<x<n.
 Группа G представляется в виде объединенияG=S1S2S3, где Si — произвольные множестваприблизительно одинаковой мощности. Функция итерированияf:GG определяется какТаким образом Ri=aiP+biQ, гдекоэффициенты определяются следующим образомВыбирая произвольноеначальное значение R0, строятся две последовательности Ri иR2i, пока не будет обнаружена коллизия при некоторомm:Rm=R2m. Исходя из формул (10) и (11), решается задачадискретного логарифмирования:
 12\}\}Важно то, что полученное значение при коллизии mзависит от начального значения R0 и определяет вычислительнуюсложность метода Полларда.

Сложностьалгоритма


 Основная работа алгоритма состоит в вычислении последовательностей{xi},{x2i}. Данные вычисления требуют трех умножений помодулю для перехода к следующей итерации. Размер необходимой памяти приэтом минимален, поскольку нет необходимости хранения информации о всехпредыдущих элементах последовательностей. Таким образом, сложностьалгоритма сводится к сложности задачи нахождения епакты, которая, в своюочередь, имеет эвристическую оценку сложности O(p), причем дляразных случаев значения константы Cp могут довольно сильноотличаться, но, как правило лежат в пределах [1;3].

Сравнение с другимиалгоритмами


 По сравнению с другими алгоритмами дискретного логарифмирования алгоритмρПолларда является менее затратным как по отношению к бинарнымоперациям, так и по отношению к необходимому количеству памяти.Например, при достаточно больших значениях числа p данный алгоритмявляется более эффективным по сложности, чем алгоритм COS и алгоритмАдлемана, имеющие сложность O(exp((logploglogp)1/2)). Всравнении с алгоритмом Шенкса, также имеющим сложность O(p),алгоритм Полларда является более выгодным по отношению к используемойпамяти — для алгоритма Шенкса требуется O(p) памяти, в то время какдля данного алгоритма размер требуемой памяти постоянен (при условиииспользования алгоритма поиска циклов Флойда).

Распараллеливаниеметода


Системы с распределеннойпамятью


 Идея метода ρПолларда для систем с распределенной памятью состоитв разделении итерирования точек между клиентскими рабочими станциями ипоиска коллизии сервером. Пусть задано множество клиентских рабочихстанций S={Sii=1...r}. Сервер определяетпараметры, общие для системы, некоторое подмножествоDG ивыполняет инициализацию рабочих станций. Клиентская рабочая станцияSi строит последовательность точек RijD и отправляетпоэлементно точки на сервер. Если точка не содержится в базе данных,сервер добавляет точку в базу данных, иначе вычисляет значениедискретного логарифма.

Системы с общейпамятью


 Идея такого метода состоит в распараллеливании отдельно функцииитерирования и алгоритма обнаружения коллизии. Функция итерированияраспараллеливается на этапе вычисления последовательностей Ri иR2i.Следует отметить, что параллельное вычислениеRi0 иR2i0 для фиксированного значения i0 и последующее сравнениеявляется неэффективным. Это объясняется тем фактом, что накладныерасходы, связанные с использованием потоков, являются вычислительноболее затратными, чем вычисление R2i0=f(R2i02).Такимобразом, целесообразно вычислять последовательности так, чтобы накладныерасходы нивелировались. Это может быть достигнуто организациейвычислений последовательностей вида {Riw+j}li=0и {R2(iw+j)}li=0, где w — размер блокавычислений,0. Функцияобнаружения коллизии в методе \rho-Полларда сравнивает значения R_mи R_{2m}. Такое сравнение можно распараллелить, если использоватьалгоритм итерирования для систем с общей памятью. Результатом выполненияфункции итерирования точек являются два множества точек\left \{ R_{i}\right \}^w_{i=0} и\left \{ R_{2i}\right \}^w_{i=0},сравнение которых осуществляется поблокам, то есть R_i = R_{2i}, i = 1 ...\frac{w}{2} иR_i = R_{2i}, i = \frac{w}{2} ... w в случае с двумя ядрами.

Комбинированныйметод


 Метод \rho-Полларда для систем с распределенной памятью может бытьрасширен для использования на многоядерных рабочих станциях. Идея методасостоит в том, что итерирование точек клиентскими рабочими станциямипроисходит в соответствии с определенным алгоритмом, суть которого втом, что есть клиентская рабочая станция S_i строит последовательностьточек \left \{ R_{ij}\right \}^w_{j=0}. Далее рабочая станция S_iвыбирает подмножество точек \left \{ R_{ij}\right \}^w_{j=0} \cap D иотправляет его серверу. Проверка на принадлежность подмножествуосуществляется в параллельном режиме:R_{ij} \in D, i = 1 ...\frac{w}{2} иR_{ij} \in D, i = \frac{w}{2} ... w (в случае с двумя ядрами). Сервердобавляет точки и \left \{ R_{ij}\right \}^w_{j=0} \cap D в базуданных до тех пор, пока не найдет уже существующую точку.

Модификации иоптимизации


 Существует несколько значительных улучшений алгоритма, основанных наразличных приемах.
 Одно из улучшений описано в работе [Teske 1998]. Отличиеприведенного в работе метода заключается в усложненной итерационнойфункции — она содержит 20 различных веток вместо описанных выше трех.Численные эксперименты показывают, что такое улучшение приводит кускорению работы алгоритма случайного блуждания в среднем на 20 

\Lambda-методПолларда


 В работе по вычислению дискретных логарифмов Поллардом также былпредложен \lambda-метод, названный так потому, что форма греческойбуквы напоминает изображение двух путей, соединяющихся в один. Идеяметода состоит в том, чтобы идти сразу двумя путями: одним от числа b,чей дискретный логарифм надо найти, другим от числа B, чей дискретныйлогарифм уже известен. Если эти два пути сойдутся, появляетсявозможность найти дискретный логарифм числа b. Поллард предложилрассматривать шаги на каждом пути как прыжки кенгуру, поэтому этоталгоритм иногда называют «методом кенгуру». Если известно, что искомыйдискретный логарифм лежит в некотором коротком интервале, то можноадаптировать метод кенгуру, а именно, использовать кенгуру с болеекороткими прыжками.
 Одним важным свойством лямбда-метода является тот факт, что он легкораспределяется на несколько компьютеров. Каждый участник распределенныхвычислений выбирает случайное число r и начинает делатьпсевдослучайные шаги от числа b^r, где b — элемент группы, длякоторого ищется дискретный логарифм. Каждый участник использует одну иту же легко вычислимую псевдослучайную функцию f\colon G \to S, гдеS — относительно небольшое множество чисел со средним значением,сравнимым с размером группы G, имеющей порядок n. Степени a^s дляs \in S вычисляются заранее. Тогда «блуждание», начиная с элементаb^r, принимает вид:w_0 = b^r, w_1 = w_0a^{f(w_0)}, w_2 = w_1a^{f(w_1)}, ...
 Пусть другой участник, выбрав начальное число r^\prime , получилпоследовательность w^\prime_0, w^\prime_1, w^\prime_2, ... Если онапересекается с последовательностью w_0, w_1, w_2, ... , то естьw^\prime_i = w_j при некоторых i, j, то, учитывая, что b = a^x,выполняется:
 Обычно этот метод используется, когда порядок группы n являетсяпростым. Так как тогда, если все выбираемые в начале вычислений числаr различны по модулю n, то сравнение (14) может быть легко решенодля нахождения дискретного логарифма x. Небольшая трудностьзаключается в том, что совпадение может произойти внутри однойпоследовательности, это означает, что r = r^\prime . Однако, есликоличество участников вычислений достаточно велико, то вероятностьсовпадения между последовательностями больше, чем вероятность совпадениявнутри одной последовательности.
 Возможно использование псевдослучайной функции (5). В таком случаебудут полезны все совпадения: совпадение внутри одной последовательноститакже может быть использовано для вычисления дискретного логарифма. Вслучае такого совпадения \lambda-метод просто превращается в\rho-метод. Однако, если известно, что искомый дискретный логарифмлежит в коротком интервале, то можно использовать первоначальный метод.Тогда время работы будет около квадратного корня из длины интервала. Вэтом случае среднее значение целых чисел из множества S должно бытьменьше для того, чтобы «кенгуру» прыгали только по интервалу нужнойдлины.
 Центральный компьютер должен отслеживать все последовательности от всехучастников для выявления совпадений. Согласно парадоксу дней рождения,совпадение ожидается, когда количество элементов во всехпоследовательностях будет порядка O(\sqrt{n})). Очевидно, что вописанном виде этот метод требует больших затрат памяти центральногокомпьютера. Следующая идея, описанная в работе ван Оршотом, сильноуменьшает требования к памяти и, таким образом, делает этот методприменимым к решению сложных проблем. Идея состоит в рассмотрении такназываемых выделенных точек. Предполагается, что элементы группыпредставляются целыми числами (или, возможно, наборами целых чисел).Выделенное двоичное поле длины k в таком числе будет состоять из однихнулей примерно 1/2k -ю часть всего времени. Случайное блуждание будетпроходить через такие выделенные точки в среднем через каждые 2^kшагов. Если две случайные последовательности где-нибудь пересекутся, тоони будут пересекаться и дальше и вместе попадут в следующую выделеннуюточку. Итак, идея состоит в отправке на центральный компьютер толькоэтих выделенных точек, что уменьшит необходимый размер памяти в 2^kраз.