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

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

Для заданного простого числа ${\displaystyle p}$ и двух целых чисел ${\displaystyle a}$ и ${\displaystyle b}$ требуется найти целое число ${\displaystyle x}$, удовлетворяющее сравнению:

${\displaystyle a^{x}\equiv b\;{\pmod {p}},}$

(1)

где ${\displaystyle b}$ является элементом циклической группы ${\displaystyle G}$, порождённой элементом ${\displaystyle a}$.

Рассматриваются последовательность пар ${\displaystyle \{u_{i},\ v_{i}\}}$ целых чисел по модулю ${\displaystyle p-1}$ и последовательность ${\displaystyle \{z_{i}\}}$ целых чисел по модулю ${\displaystyle p}$, определённые следующим образом:

${\displaystyle \{u_{i}\},\{v_{i}\},\{z_{i}\},\ i\in N,}$

(2)

${\displaystyle u_{0}=v_{0}=0,\ z_{0}=1;}$

${\displaystyle u_{i+1}={\begin{cases}u_{i}+1\;{\bmod {\;}}(p-1),&0<z_{i}<{\frac {p}{3}};\\2u_{i}\;{\bmod {\;}}(p-1),&{\frac {p}{3}}<z_{i}<{\frac {2}{3}}p;\\u_{i}\;{\bmod {\;}}(p-1),&{\frac {2}{3}}p<z_{i}<p;\end{cases}}}$

(3)

${\displaystyle v_{i+1}={\begin{cases}v_{i}\;{\bmod {\;}}(p-1),&0<z_{i}<{\frac {p}{3}};\\2v_{i}\;{\bmod {\;}}(p-1),&{\frac {p}{3}}<z_{i}<{\frac {2}{3}}p;\\v_{i}+1\;{\bmod {\;}}(p-1),&{\frac {2}{3}}p<z_{i}<p;\end{cases}}}$

(4)

${\displaystyle z_{i+1}\equiv b^{u_{i+1}}a^{v_{i+1}}{\pmod {p}}={\begin{cases}bz_{i}\;{\bmod {\;}}p,&0<z_{i}<{\frac {p}{3}};\\z_{i}^{2}\;{\bmod {\;}}p,&{\frac {p}{3}}<z_{i}<{\frac {2}{3}}p;\\az_{i}\;{\bmod {\;}}p,&{\frac {2}{3}}p<z_{i}<p.\end{cases}}}$

(5)

Замечание 1: во всех выражениях рассматривается наименьшие неотрицательные вычеты.

Замечание 2: в более общем случае возможно разбиение на 3 подмножества несколько иным способом: разбиваем группу ${\displaystyle G}$ на три примерно равных по мощности подмножества ${\displaystyle S_{1},S_{2},S_{3}}$ так, чтобы ${\displaystyle 1}$ не принадлежала подмножеству ${\displaystyle S_{2}}$.

Поскольку каждая треть отрезка, которой принадлежит элемент, вероятно, никак не связана с элементами последовательностей ${\displaystyle \{u_{i},v_{i}\}}$, полученная последовательность — псевдослучайная. Поэтому могут существовать такие числа ${\displaystyle j}$ и ${\displaystyle k}$, что ${\displaystyle z_{k}=z_{j}}$. Если удастся найти такую пару чисел, то получится:

${\displaystyle b^{u_{j}}a^{v_{j}}\equiv b^{u_{k}}a^{v_{k}}{\pmod {p}}.}$

(6)

Если число ${\displaystyle u_{j}-u_{k}}$ взаимно простое с числом ${\displaystyle p-1}$, то это сравнение можно решить и найти дискретный логарифм:

${\displaystyle b^{u_{j}-u_{k}}\equiv a^{v_{k}-v_{j}}{\pmod {p}}.}$

${\displaystyle x\equiv \log _{a}{b}\equiv (u_{j}-u_{k})^{-1}(v_{k}-v_{j}){\pmod {p-1}}.}$

(7)

Если же наибольший общий делитель чисел ${\displaystyle u_{j}-u_{k}}$ и ${\displaystyle p-1}$ равен числу ${\displaystyle d>1}$, то существует решение этого сравнения для ${\displaystyle x}$ по модулю ${\displaystyle (p-1)/d}$. Пусть ${\displaystyle x=x_{0}}$ ${\displaystyle (mod(p-1)/d)}$, тогда искомое число ${\displaystyle x=x_{0}+m(p-1)/d}$, где ${\displaystyle m}$ может принимать значения ${\displaystyle 0,1,...,d-1}$. Поэтому если ${\displaystyle d}$ — достаточно небольшое число, то задача решается перебором всех возможных значений для ${\displaystyle m}$. В худшем случае — когда ${\displaystyle d=p-1}$ — метод оказывается ничем не лучше полного перебора всех возможных значений для дискретного логарифма.

Для поиска индексов ${\displaystyle j}$ и ${\displaystyle k}$ используется алгоритм поиска циклов Флойда. При использовании данного алгоритма на ${\displaystyle i}$-м шаге имеются значения ${\displaystyle (z_{i},\ u_{i},\ v_{i},\ z_{2i},\ u_{2i},\ v_{2i})}$ и ищется номер ${\displaystyle i}$, для которого ${\displaystyle z_{i}=z_{2i}}$. Наименьшее значение ${\displaystyle i}$, при котором выполняется данное условие, называется епактой. Если при этом ${\displaystyle (u_{2i}-u_{i},\ p-1)=1}$, то

${\displaystyle x\equiv \log _{a}{b}\equiv (u_{2i}-u_{i})^{-1}(v_{i}-v_{2i}){\pmod {p-1}}.}$

(8)

Пусть задана группа точек эллиптической кривой (ЭК) ${\displaystyle E(F_{p})}$. Не ограничивая общности, можно предположить, что ${\displaystyle p>3}$ и ${\displaystyle p}$ — простое число. Обозначим подгруппу ${\displaystyle E(F_{p})}$ порядка ${\displaystyle n}$ через ${\displaystyle G}$ и зафиксируем порождающий элемент ${\displaystyle P}$. Для произвольного элемента группы ${\displaystyle Q=xP}$ задача дискретного логарифмирования заключается в нахождении элемента ${\displaystyle 1<x<n.}$

Группа ${\displaystyle G}$ представляется в виде объединения ${\displaystyle G=S_{1}\cup S_{2}\cup S_{3}}$, где ${\displaystyle S_{i}}$ — произвольные множества приблизительно одинаковой мощности. Функция итерирования ${\displaystyle f\colon G\to G}$ определяется как

${\displaystyle R_{i+1}=f(R_{i})={\begin{cases}Q+R_{i},&R_{i}\in S_{1};\\2R_{i},&R_{i}\in S_{2};\\P+R_{i},&R_{i}\in S_{3}.\end{cases}}}$

(9)

Таким образом, ${\displaystyle R_{i}=a_{i}P+b_{i}Q}$, где коэффициенты определяются следующим образом

${\displaystyle a_{i+1}={\begin{cases}a_{i},&R_{i}\in S_{1};\\2a_{i},&R_{i}\in S_{2};\\a_{i}+1,&R_{i}\in S_{3};\end{cases}}}$

(10)

${\displaystyle b_{i+1}={\begin{cases}b_{i}+1,&R_{i}\in S_{1};\\2b_{i},&R_{i}\in S_{2};\\b_{i},&R_{i}\in S_{3}.\end{cases}}}$

(11)

Выбирая произвольное начальное значение ${\displaystyle R_{0}}$, строим две последовательности ${\displaystyle R_{i}}$ и ${\displaystyle R_{2i}}$, пока не будет обнаружена коллизия при некотором ${\displaystyle m:R_{m}=R_{2m}}$. Исходя из формул (10) и (11), решается задача дискретного логарифмирования:

${\displaystyle x={\frac {a_{2m}-a_{m}}{b_{m}-b_{2m}}}.}$

(12)

Важно то, что полученное значение при коллизии ${\displaystyle m}$ зависит от начального значения ${\displaystyle R_{0}}$ и определяет вычислительную сложность метода Полларда.

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

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

Идея метода ${\displaystyle \rho -}$Полларда для систем с распределённой памятью состоит в разделении итерирования точек между клиентскими рабочими станциями и поиска коллизии сервером. Пусть задано множество клиентских рабочих станций ${\displaystyle S=\left\{S_{i}\mid i=1...r\right\}.}$ Сервер определяет параметры, общие для системы, некоторое подмножество${\displaystyle D\subset G}$ и выполняет инициализацию рабочих станций. Клиентская рабочая станция ${\displaystyle S_{i}}$ строит последовательность точек ${\displaystyle R_{ij}\subset D}$ и отправляет поэлементно точки на сервер. Если точка не содержится в базе данных, сервер добавляет точку в базу данных, иначе вычисляет значение дискретного логарифма.

Идея такого метода состоит в распараллеливании отдельно функции итерирования и алгоритма обнаружения коллизии. Функция итерирования распараллеливается на этапе вычисления последовательностей ${\displaystyle R_{i}}$ и ${\displaystyle R_{2i}}$. Следует отметить, что параллельное вычисление${\displaystyle R_{i_{0}}}$ и ${\displaystyle R_{2i_{0}}}$ для фиксированного значения ${\displaystyle i_{0}}$ и последующее сравнение является неэффективным. Это объясняется тем фактом, что накладные расходы, связанные с использованием потоков, являются вычислительно более затратными, чем вычисление ${\displaystyle R_{2i_{0}}=f(R_{2i_{0}-2})}$.Таким образом, целесообразно вычислять последовательности так, чтобы накладные расходы нивелировались. Это может быть достигнуто организацией вычислений последовательностей вида ${\displaystyle \left\{R_{iw+j}\right\}_{i=0}^{l}}$ и ${\displaystyle \left\{R_{2(iw+j)}\right\}_{i=0}^{l}}$, где ${\displaystyle w}$ — размер блока вычислений, ${\displaystyle 0\leqslant j<w,l=\left\lceil {\frac {m}{w}}\right\rceil }$. Функция обнаружения коллизии в методе ${\displaystyle \rho -}$Полларда сравнивает значения ${\displaystyle R_{m}}$ и ${\displaystyle R_{2m}}$. Такое сравнение можно распараллелить, если использовать алгоритм итерирования для систем с общей памятью. Результатом выполнения функции итерирования точек являются два множества точек ${\displaystyle \left\{R_{i}\right\}_{i=0}^{w}}$ и ${\displaystyle \left\{R_{2i}\right\}_{i=0}^{w}}$,сравнение которых осуществляется по блокам, то есть ${\displaystyle R_{i}=R_{2i},i=1...{\frac {w}{2}}}$ и ${\displaystyle R_{i}=R_{2i},i={\frac {w}{2}}...w}$ в случае с двумя ядрами.

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

Существует несколько значительных улучшений алгоритма, основанных на различных приемах.

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

В работе по вычислению дискретных логарифмов Поллардом также был предложен ${\displaystyle \lambda -}$метод, названный так потому, что форма греческой буквы напоминает изображение двух путей, соединяющихся в один. Идея метода состоит в том, чтобы идти сразу двумя путями: одним от числа ${\displaystyle b}$, чей дискретный логарифм надо найти, другим от числа ${\displaystyle B}$, чей дискретный логарифм уже известен. Если эти два пути сойдутся, появляется возможность найти дискретный логарифм числа ${\displaystyle b}$. Поллард предложил рассматривать шаги на каждом пути как прыжки кенгуру, поэтому этот алгоритм иногда называют «методом кенгуру». Если известно, что искомый дискретный логарифм лежит в некотором коротком интервале, то можно адаптировать метод кенгуру, а именно, использовать кенгуру с более короткими прыжками.

Одним важным свойством лямбда-метода является тот факт, что он легко распределяется на несколько компьютеров. Каждый участник распределённых вычислений выбирает случайное число ${\displaystyle r}$ и начинает делать псевдослучайные шаги от числа ${\displaystyle b^{r}}$, где ${\displaystyle b}$ — элемент группы, для которого ищется дискретный логарифм. Каждый участник использует одну и ту же легко вычислимую псевдослучайную функцию ${\displaystyle f\colon G\to S}$, где ${\displaystyle S}$ — относительно небольшое множество чисел со средним значением, сравнимым с размером группы ${\displaystyle G}$, имеющей порядок ${\displaystyle n}$. Степени ${\displaystyle a^{s}}$ для ${\displaystyle s\in S}$ вычисляются заранее. Тогда «блуждание», начиная с элемента ${\displaystyle b^{r}}$, принимает вид: ${\displaystyle w_{0}=b^{r},w_{1}=w_{0}a^{f(w_{0})},w_{2}=w_{1}a^{f(w_{1})},...}$

Пусть другой участник, выбрав начальное число ${\displaystyle r^{\prime }}$ , получил последовательность ${\displaystyle w_{0}^{\prime },w_{1}^{\prime },w_{2}^{\prime },...}$ Если она пересекается с последовательностью ${\displaystyle w_{0},w_{1},w_{2},...}$, то есть ${\displaystyle w_{i}^{\prime }=w_{j}}$ при некоторых ${\displaystyle i,j}$, то, учитывая, что ${\displaystyle b=a^{x}}$, выполняется:

${\displaystyle b^{r^{\prime }}a^{f(w_{0}^{\prime })+f(w_{1}^{\prime })+...+f(w_{i-1}^{\prime })}=b^{r}a^{f(w_{0})+f(w_{1})+...+f(w_{j-1})},}$

(13)

${\displaystyle (r^{\prime }-r)x\equiv \sum _{\mu =0}^{j-1}{f(w_{\mu })}-\sum _{\nu =0}^{i-1}{f(w_{\nu }^{\prime })}{\pmod {n}}.}$

(14)

Обычно этот метод используется, когда порядок группы ${\displaystyle n}$ является простым. Так как тогда, если все выбираемые в начале вычислений числа ${\displaystyle r}$ различны по модулю ${\displaystyle n}$, то сравнение ${\displaystyle (14)}$ может быть легко решено для нахождения дискретного логарифма ${\displaystyle x}$. Небольшая трудность заключается в том, что совпадение может произойти внутри одной последовательности, это означает, что ${\displaystyle r=r^{\prime }}$. Однако, если количество участников вычислений достаточно велико, то вероятность совпадения между последовательностями больше, чем вероятность совпадения внутри одной последовательности.

Возможно использование псевдослучайной функции (5). В таком случае будут полезны все совпадения: совпадение внутри одной последовательности также может быть использовано для вычисления дискретного логарифма. В случае такого совпадения ${\displaystyle \Lambda -}$метод просто превращается в ${\displaystyle \rho -}$метод. Однако, если известно, что искомый дискретный логарифм лежит в коротком интервале, то можно использовать первоначальный метод. Тогда время работы будет около квадратного корня из длины интервала. В этом случае среднее значение целых чисел из множества ${\displaystyle S}$ должно быть меньше для того, чтобы «кенгуру» прыгали только по интервалу нужной длины.

Центральный компьютер должен отслеживать все последовательности от всех участников для выявления совпадений. Согласно парадоксу дней рождения, совпадение ожидается, когда количество элементов во всех последовательностях будет порядка ${\displaystyle O({\sqrt {n}})}$. Очевидно, что в описанном виде этот метод требует больших затрат памяти центрального компьютера. Следующая идея, описанная в работе ван Оршотом, сильно уменьшает требования к памяти и, таким образом, делает этот метод применимым к решению сложных проблем. Идея состоит в рассмотрении так называемых выделенных точек. Предполагается, что элементы группы представляются целыми числами (или, возможно, наборами целых чисел). Выделенное двоичное поле длины ${\displaystyle k}$ в таком числе будет состоять из одних нулей примерно ${\displaystyle 1/2k}$-ю часть всего времени. Случайное блуждание будет проходить через такие выделенные точки в среднем через каждые ${\displaystyle 2^{k}}$ шагов. Если две случайные последовательности где-нибудь пересекутся, то они будут пересекаться и дальше и вместе попадут в следующую выделенную точку. Итак, идея состоит в отправке на центральный компьютер только этих выделенных точек, что уменьшит необходимый размер памяти в ${\displaystyle 2^{k}}$ раз.

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — С. 328. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
• Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты. — М.: УРСС, 2011 — С.664. — ISBN 978-5-453-00016-6
• Pollard J. M. Monte Carlo methods for index computation (mod p). Mathematics of Computation — 32 (143), 1978—918—924 — JSTOR 2006496
• Teske, Speeding up Pollard’s rho method for computing discrete logarithms. Algorithmic Number Theory Symposium (ANTS IV), 1998—541—553
• Горбенко И. Д., Качко Е. Г. Методы распараллеливания алгоритма Полларда решения задачи дискретного логарифмирования для систем с общей памятью — 2012
• van Oorschot P.C., Wiener M.J. Parallel collision search with cryptanalytic applications — Journal of Cryptology 12 (1) — 1-28 — 1999