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

Этот алгоритм осуществляет случайный поиск дискретных логарифмов, как и метод «шаг ребенка – шаг великана», но он требует меньшего объема памяти для хранения данных, поэтому предпочтительней для практических целей. В основе данного метода лежит та же идея, что и в основе ро-метода для факторизации – строится псевдослучайная последовательность, в которой находятся совпадающие элементы при помощи метода Флойда, а затем на основании полученной величины вычисляется искомый дискретный логарифм.

Пусть требуется вычислить log_ga в конечной группе G порядка n.

Группа G разбивается на три непересекающихся подмножества примерно равной мощности: G=S₁US₂US₃, так чтобы 1 S₂. Причем разбиение должно быть построено таким образом, чтобы проверка, к какому подмножеству принадлежит данный элемент x, была простой.

Например, если G=Z_p, где p – простое число, то можно задать разбиение S₁={1,…, }, S₂={ ,…, }, S₃={ , … , p—1}, или разбиение может быть таким: если x mod 3=1, то x S₁, если x mod 3=2, то x S₂, если x mod 3=0, то x S₃.

Далее на G задается последовательность x₀, x₁, x₂, … , где x₀=1, x_i+1 вычисляется по x_i посредством функции f для i≥0:

x_i+1=f(x_i)=

Вычисления проводятся в группе G, то есть если G=Z_m, то вычисления следует производить по модулю m.

Такая последовательность групповых элементов может быть представлена двумя последовательностями u₀, u₁, u₂,… и v₀, v₁, v₂,… такими, что x_i= , u₀=v₀=0,

u_i+1= , v_i+1=

Вычисления в последовательностях u и v производятся по модулю n.

В силу того, что группа G – конечная, при помощи метода Флойда можно найти такие x_i и x_2i, что x_i = x_2i. Тогда = . Логарифмируя по основанию g обе части данного уравнения, получим

(v_i—v_2i)log_ga≡(u_2i—u_i) (mod n)

Решая это сравнение, получим искомый логарифм. (Заметим, что если G=Z^*_m, то n=φ(m)).

Сложность данного метода составляет O( ) , где n – порядок группы G.

Замечание. Метод может дать отказ в том случае, когда v_i =v_2i. Тогда следует назначить случайные значения от 0 до n—1 переменным u₀, v₀ , вычислить x₀= и повторить все шаги алгоритма.

Замечание. В том случае, когда имеется достаточно места для хранения данных в процессе вычислений (например, когда G невелико или вычисления производятся вручную), можно обойтись без метода Флойда. Тогда следует хранить все члены последовательностей x, u и v до того, как x_i = x_j и дискретный логарифм находится из сравнения (v_i—v_j)log_ga≡(u_j—u_i) (mod n).

Пример.

G=Z^*₁₉, a=8, g=2.

Тогда n=φ(19)=18. Поскольку решение будем производить вручную, то не будем пользоваться методом Флойда.

Разбиение G на подмножества произведем следующим образом: если x mod 3=1, то x S₁, если x mod 3=2, то x S₂, если x mod 3=0, то x S₃.

Вычисления будут производиться по формулам:

x_i+1=f(x_i)=

u_i+1= , v_i+1=

i
xi				18					18
ui
vi
S	S1	S2	S1	S3	S2	S1	S1	S3	S3

x₃=x₈. Логарифм найдем из сравнения (v₃—v₈)log₂8≡(u₈—u₃) (mod 18)

-5 log₂8≡3(mod 18)

13 log₂8≡3(mod 18)

log₂8≡3·7(mod 18)

log₂8≡3(mod 18).

Действительно, 2³≡8 (mod 19).

Ответ: log₂8≡3(mod 18).