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


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

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

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

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

Далее на G задается последовательность x0, x1, x2, … , где x0=1, xi+1 вычисляется по xi посредством функции f для i≥0:

xi+1=f(xi)=

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

Такая последовательность групповых элементов может быть представлена двумя последовательностями u0, u1, u2,… и v0, v1, v2,… такими, что xi= , u0=v0=0,

ui+1= , vi+1=

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

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

(vi—v2i)logga≡(u2i—ui) (mod n)

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

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

Замечание. Метод может дать отказ в том случае, когда vi =v2i. Тогда следует назначить случайные значения от 0 до n—1 переменным u0, v0 , вычислить x0= и повторить все шаги алгоритма.

Замечание. В том случае, когда имеется достаточно места для хранения данных в процессе вычислений (например, когда G невелико или вычисления производятся вручную), можно обойтись без метода Флойда. Тогда следует хранить все члены последовательностей x, u и v до того, как xi = xj и дискретный логарифм находится из сравнения (vi—vj)logga≡(uj—ui) (mod n).

 

Пример.

G=Z*19, a=8, g=2.

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

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

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

xi+1=f(xi)=

ui+1= , vi+1=

 

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

 

x3=x8. Логарифм найдем из сравнения (v3—v8)log28≡(u8—u3) (mod 18)

-5 log28≡3(mod 18)

13 log28≡3(mod 18)

log28≡3·7(mod 18)

log28≡3(mod 18).

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

Ответ: log28≡3(mod 18).

 



Дата добавления: 2018-11-26; просмотров: 943;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.012 сек.