<< Предыдущая

стр. 37
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

хо = г и XI = j ,
поскольку при Gi — Hj имеет место равенство
G' = HG-^^^\ т.е. G^+^Tv^l = я .
Заметим, что время, требуемое на вычисление шагов гиганта не
больше


Следовательно, сложность метода шаги младенца/шаги гиганта равна

oiVp)-
Таким образом, если мы хотим, чтобы решение задачи дискрет­
ного логарифмирования в группе А с учетом алгоритма Полига-
Хеллмана занимало около 2^^ операций, нам нужно подобрать та­
кую группу А, у которой суш;ествует подгруппа простого прядка р
ср>2^^^.
Разберем пример, взяв в качестве группы подгруппу порядка
101 в мультипликативной группе поля Fgor? порожденную элементом
G = 64. Допустим, нам нужно решить уравнение
Н = 182-:64^ (mod 607).
Сначала делаем шаги младенца:
Gi = 64^ (mod 607) для О ^ г < [VM] = 11.
Результаты вычислений занесем в таблицу:

64^ (mod 607)
i 64^ (mod 607) i
1
0 6 330
64
1 482
7
2 454 8 498
3 527 9 308
4 343 10 288
100
5
Затем вычисляем шаги гиганта:
Hj = 182 • 64^1^^ (mod 607) для О ^ j < 11
9.4- Методы Полларда 243

и смотрим, когда шаг гиганта совпадает с шагом младенца:
J 182 64-
182 • 64- i (mod 607)
-J
i -11^ (mod 607)
j
и 182 6 60
1 7 394
143
2 69 8 483
3 271 9 76
4 343 10 580
573
5
Из сравнения таблиц видно, что совпадение имеет место при г = 4
и j = 4. Это означает, что
=
а; = 4 + 1 1 - 4 = 48,
что можно проверить, вычислив
64^^ (mod 607) = 182.



9.4. Методы Полларда
Недостаток метода шаги младенца/шаги гиганта заключается в
том, что несмотря на сравнительно малое время работы ( 0 ( у ^ ) ) ,
он требует столько же места в памяти компьютера. Такие требова­
ния, предъявляемые алгоритмами к памяти, даже более обремени­
тельны на практике, чем несколько большее время работы. В связи с
этим возникает вопрос: можно ли суп1,ественно снизить требования
к памяти, не увеличивая существенно сложность алгоритма? Ответ
положителен, но, к сожалению, мы при этом можем оценить лишь
ожидаемое время работы, но не фактическое. Существует несколько
алгоритмов, которые снижают требования к памяти. Все они своим
существованием обязаны идеям Полларда.

9.4.1. р-метод Полларда
Пусть / : S • S — случайная функция на множестве S и # 5 = п.
Выбираем произвольный элемент XQ Е S и последовательно вычи­
сляем
Xi+i = f{xi) при г > 0.
Значения XQ^ xi^ Х2^ . . . будем рассматривать как детерминирован­
ное случайное блуэюдание. Последнее высказывание означает, что
Глава 9. Дискретные логарифмы

каждый шаг x^+i = fi^i) пути — детерминированная функция теку-
ш;ей позиции Xi, Но мы будем предполагать, что последовательность
хо-, Ж1, Х2-, . . . ведет себя как случайная. Такие последовательности
еще называют псевдо-случайными.
Поскольку S — конечное множество, мы должны получить ра­
венство Хг = Xj д^ля некоторой пары индексов, и тогда
Xi^l = f{Xi) = f{Xj) = Xj+i.

Иначе говоря, последовательность XQ^ xi, Х2^ . . . будет вести себя
циклическим образом. Если мы попытаемся изобразить это блужда­
ние на множестве 5, то получится что-то вроде греческой буквы
«ро», т.е. р. Другими словами, в нем есть циклическая часть и не­
который начальный «хвост», в цикл не входящий. Можно показать,
что ожидаемая длина хвоста случайного отображения / (т.е. чи­
сло элементов в хвосте), равна у т ш / З , а ожидаемая длина цикла —
у/37гп/8. Цель большинства методов, восходяш;их к Полларду, —
найти начало цикла в случайном блуждании т. е. такие элементы Xi
и Xj последовательности, которые равны друг другу при несовпа-
даюш,их индексах. Благодаря парадоксу дней рождений мы получа­
ем, что ожидаемое повторение произойдет через у^7гп/2 итераций
функции / . Наивно говоря, до ожидаемого повтора пройдет 0{л/п)
времени, а чтобы засечь повторение, нам потребуется 0{л/п) памя­
ти. Но это и есть та самая проблема, с которой мы сталкиваемся в
методе шаги младенца/шаги гиганта.
Чтобы найти повтор и воспользоваться /9-формой случайного
блуждания, применяется алгоритм Флойда поиска циклов. Он за­
ключается в следующем: по паре (д^1,Ж2) мы вычисляем {x2-,X4)i за­
тем (XS^XQ) И Т.Д., т.е. вслед за парой {xi^X2i) вычисляется пара
{^г+Ь^2г+2) = { / ( ^ г ) , / ( / f e ) ) ) -
Процесс заканчивается при равенстве: Хт = ^2т- Если длина хвоста
нашей последовательности равна Л, а длина ее цикла — /i, то такое
совпадение можно ожидать при^
m = /i(l + LA//iJ).
Принимая во внимание неравенство Л < m ^ А + //, мы получа­
ем, что т = 0{у/п). Причем это будет точной оценкой сложности,
если / ведет себя как средняя случайная функция. Следовательно,
мы можем обнаружить повторение, практически ничего не храня в
памяти компьютера.
Символ \у\ означает целую часть у с избытком, т. е. наименьшее целое п, для
которого п ^ у. — Прим. перев.
9.4- Методы Лолларда 245

Все это замечательно, но мы не показали, как это блуждание свя­
зано с дискретным логарифмированием. Пусть А — группа порядка
п и мы решаем в ней задачу дискретного логарифмирования:


Разобьем группу на три части ^ i , ^2 и 5з, причем 1 ^ 52, и опреде­
лим случайное блуждание по группе А следующим образом:
Л. • Х{^ Xi G <bi,

xi+i = f{xi) = { x}, Xi e ^2,
G -Xi, Xi e 5з.
Фактически нам нужно хранить данные в виде вектора: {xi^ai^bi)^
где
Gij Xi G <bi,

a^+i = ^ 2ai (modn), Xi e S2,
ai + 1 (modn), Xi G 83;

bi + l (modn), Xi G Si,
[?г+1 = \ 2bi (modn), Xi e S2,
bi, Xi e Ss-
Если мы начинаем с тройки (xo^ao^bo) = (1,0,0), то для всех г
logG(^i) = ai + bi logG{H) ^щ + bix,
где X = logQH. Применяя алгоритм Флойда поиска циклов, мы
получим повторение последовательности, т.е. такое число т , что
Хщ = Х2т- Это позволяет нам вывести следующее равенство:
Ctm + ЬтХ = ат + Ьт ^OgQ{H) = logciXm) = log^(x2m) =
= а2т + b2m logQ{H) = a2m + b2m^-
После преобразований находим
{bm — b2m)x = a2m ˜ Ctm,

так ЧТО если bm ф b2mi получаем

X= — (modn).
bm — b2m
При больших n вероятность равенства bm = b2m настолько мала,
что ее можно игнорировать.
Глава 9. Дискретные логарифмы

Итак, если случайное блуждание получается из случайной функ­
ции / : А • Л, то вышеописанный алгоритм решит задачу дис­
кретного логарифмирова.ния за 0{у/п) операций.
В качестве примера рассмотрим подгруппу А поля Feor порядка
п — 101, порожденную элементом 64. Поставим задачу о вычислении
логарифма:
Я - 122 - 64^.

Определяем подмножества группы:

5i = {:rGF607|^^201},
S2 = {xe Feorl 202 ^ X ^ 403},
S^ = {xe Feo?! 404 ^ ж ^ 606}.
В процессе работы алгоритма Флойда будут получаться следуюш;ие
данные:
г bi
Xi Ь2г
Щ а.2г
Х2г
1 "Т 1
0 0 0
˜сГ
1 122 0 1 2
316 0
172
2 316 0 2 0 8
4
3 308 0 137 0 18
4 172 0 8 7 0 38
309 78
5 346 0 9 0
352
6 137 0 18 0 56
12
7 325 0 19 167 0
8 70 38 498 0 26
172 52
9 247 0 2
39
137 4 5
10 309 0 78
И 182 0 12
55 7 8
12 352 0 56 309 16 26
13 76 0 11 352 32 53
14 12 64
167 0 167 6
Повторение произошло при т = 14. Значит,
g0fjl2 ^ Q^Ajj^^

откуда вытекает уравнение

12а; = 64 + 6ж mod 101.
9.4' Методы Лолларда

Другими словами,

^=Y^ (mod 1 0 1 ) - 7 8 .

9.4.2. Л-метод П о л л а р д а
Этот алгоритм похож на р-метод тем, что в нем используется детер­
минированное случайное блуждание и задействовано мало памяти
для хранения промежуточных шагов. Однако Л-метод предназна­
чен, в первую очередь, для ситуации, когда известен отрезок, где
может лежать значение логарифма:
ж G [а, . . . , й].
В р-методе используется одно случайное блуждание, своей формой
напоминающее греческую букву «р». А в Л-методе используются две
случайные последовательности элементов группы, которые выгля­
дят как буква «Л», откуда и происходит название алгоритма.
Расскажем о Л-методе. Пусть w = b — а обозначает длину от­
резка, в котором лежит значение искомого дискретного логарифма.
Задают множество
S = {50, . . . , Sk-i}
целых чисел, расположенных по неубыванию, средний элемент т
которого приблизительно равен N = л/w. Как правило, выбирают
Si = 2* для О ^ i < к.
В этой ситуации средний член равен ^ . Поэтому берут к ^ ^ log2(tL?).
Группу Л, в которой ставится задача, разбивают на к подмно­
жеств б'г (г = О, . . . , А — 1) и фиксируют функцию, определяющую
:
псевдо-случайную последовательность:
Xi^i — Xi • G^^ если Xi G Sj.
После этого вычисляются элементы детерминированного случайно­
го блуждания, начиная с Go = G^, по правилу
Gi = Gi-i ' G ^
для г = 1, . . . , TV. Обозначают CQ = b и c^+i = Ci Л- Sj (mod^), где
q — порядок группы А. В результате последовательных вычисле­
ний будет найден элемент GN (где N = \/w)^ который и записыва­
ется в память компьютера. При этом нам известен элемент с^ =
— log^{G7v), который тоже следует запомнить.
Теперь вычисляют второе детерминированное случайное блу­
ждание, начинающееся с неизвестной точки интервала д;, а именно.
Глава 9. Дискретные логарифмы

пусть iifo = Н — G^, тогда /fi+i = Hi - G^K Кроме того, обозна­
чают do = О и di^i = di -\- Sj (mod^). Заметим, что имеет место
=
соотношение:
logoiHi) =x + di.
Если путь Hi пересечется с последовательностью G^, то Hi дальше
пойдет по пути Gi и можно будет найти такое значение М, при
котором Нм окажется равным сохраненному нами элементу GN- В
этой ситуации
CN = logQ{GN) = log(^(Ям) ^X-h dM-

<< Предыдущая

стр. 37
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>