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

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

ОГЛАВЛЕНИЕ

Следующая >>

но найдем разные элементы последовательности с условием
Xi = Xj ( m o d p ) .

8.3.4. Объясните, как найти такие элементы, используя небольшое
количество памяти.

8.3.5. (Р — 1)-метод Полларда основывается на арифметике поля Fp
и позволяет раскладывать на множители произведения pq с
гладким р — 1 и не гладким g — 1. Разработайте аналогичный
метод, опирающийся на арифметику поля Fp2, позволяющий
факторизовать числа с гладким р + 1. Такой метод носит
название (Р Н- 1)-метода Полларда.

8.3.6*. Обобщите (Р — 1)- и ( Р + 1)-методы на эллиптические кривые
следующим образом. Рассмотрите эллиптическую кривую Е
над кольцом Z/NZ и покажите, что в случае гладкого числа
i^E{?p) число N можно разложить, опираясь на закон сложе­
ния точек эллиптической кривой. Это обобщение носит на­
звание метода факторизации Ленстры.
ГЛАВА 9
ДИСКРЕТНЫЕ
ЛОГАРИФМЫ

Ц е л и главы
• Исследовать алгоритмы, решающие проблему дискретного ло­
гарифмирования.
• Ввести алгоритм Полига-Хеллмана.
• Рассказать об алгоритме шаги младенца/шаги гиганта.
• Объяснить методы Полларда.
• Показать, как в конечных полях с помощью методов, похожих
на алгоритмы факторизации, вычисляются дискретные лога­
рифмы.
• Описать известные результаты о дискретном логарифмирова­
нии на эллиптических кривых.


9.1. Введение
Здесь мы познакомимся с известными методами дискретного лога­
рифмирования в различных группах, т. е. способами решения урав­
нения


относительно неизвестной ж, где Н иО — элементы конечной абеле­
вои группы. Эти методы можно разделить на две категории: общие
алгоритмы, применяемые к любой конечной абелевои группе, или
специфические алгоритмы, разработанные для специальных групп.
Начав знакомство с общих, к концу главы мы подойдем к специаль­
ным способам.


9.2. Метод Полига-Хеллмана
Первое наблюдение, связанное с дискретным логарифмированием в
абелевои группе Л, состоит в том, что сложность этой задачи совпа­
дает с ее сложностью в максимальной подгруппе простого порядка.
9.2. Метод Полига-Хеллмана

Такое наблюдение было сделано Полигом и Хеллманом и справедли­
во в любой конечной абелевой группе. Вот его обоснование.
Предположим, что у нас есть конечная циклическая абелева груп­
па А = (G), чей порядок имеет следующее разложение на простые
множители:
t
N = #A = fjp;
i=l
Допустим, нам дан элемент Н G (G), т.е. существует натуральное
число :г, для которого Н = G^. Наша цель — найти х. Можно сна­
чала отыскать решения по всем модулям р^% а затем применить
китайскую теорему об остатках и восстановить решение по модулю ЛГ.
Из теории групп известно, что существует групповой изомор­
физм
Ф:А • Cei X • • • X Get,
Pi • Pt '
где Gpe — циклическая группа порядка р^. Проекция отображения
Ф на компоненту Gpe задается формулой
С^е
•рс
ФР
fN/p
Поскольку Фр — гомоморфизм групп, его применение к соотноше­
нию Н = G^ приводит к равенству Фр{Н) = Фp(G)^ в группе Gpe,
Проблема дискретного логарифмирования в группе Gpe определена
только по модулю р^. Решая ее, мы найдем х по модулю р^. Сделав
это А,ля всех простых делителей 7V, мы восстановим х по модулю 7V,
используя китайскую теорему об остатках. Подводя итог, предполо­
жим, что мы владеем оракулом 0 ( G , if,p, е), который по элементам
G^ Н Е Gpe вычисляет дискретный логарифм элемента Н по основа­
нию G. Тогда мы отыщем нужный нам х в результате следующего
алгоритма:

s={ };
для всех простых р, делящих N
{ вычислить наибольшее число е, для которого Т=р"е делит N;
G1=G"{M/T};
H1=H-{N/T};
z=0(Gl,Hl,p,e);
S = S + { (z.T) }; }
x=KTO(S);
Осталось только показать, как отыскать дискретный логарифм
в группе Сре. Сделаем это, сводя задачу к случаю е = 1. Пусть
238 Глава 9. Дискретные логарифмы

G^ Н Е Сре^ причем А^ля некоторого натурального числа х имеет
место равенство Н = G^. Очевидно, число х определено по модулю
р^, и мы можем представить его в виде
X = Х^+ Xip Н h Xe-lP^˜^.

Будем искать коэффициенты XQ-, xi^ ... по очереди, используя
индуктивную процедуру. Допустим, мы знаем х^ — значение х по
модулю р*, т.е.
х^ = хо-\ \-xt-ip^˜^,
и хотим определить Xt (или найти х по модулю х^'^^). Запишем х
как
X = х^ -\- р^х",
где ж" = Xt -\-pxiJ^\ + • • • Н- Хе-\р^˜^˜^' Тогда



Следовательно, положив
H'^HG-'"' и G' = G^\
получим уравнение на х":
Н' = G""".
Теперь G' — элемент порядка р^˜^. Поэтому, чтобы получить эле­
мент порядка р, и, следовательно, свести задачу к группе Ср, нам
нужно возвести предыдущее уравнение в степень s = р^˜^˜^. Поло­
жив
Н" = Н" и G" = G'%
МЫ получим задачу о вычислении логарифмов в группе Ср'.
тП _ ^ПХ" _ ^ffXt-\-pXt-\-l-\--'-\-Xe-lP^ *^
Н" = G'"" = G" • "" "'""'
_ ^ffXt j^ffp{xt + l + '"Xe-lP^ * ^) _




Предполагая, что мы можем решить задачу о логарифмах в группе
простого порядка, найдем ж^, а значит и требуемый х.
Способ решения задачи дискретного логарифмирования в груп­
пах Ср мы осветим в следуюш;их двух параграфах, а сейчас проил­
люстрируем изложенное, предполагая, что случай простого порядка
группы нам известен.
В качестве примера рассмотрим мультипликативную группу ко­
нечного поля F397- Ее порядок равен 396 = 2^ • 3^ • 11. Одна из обра-
9.2. Метод Полига-Хеллмана 239

зующих группы F397 — это G = 5. Решим показательное уравнение
Я = 208 = 5^ (mod 397).
Разделим задачу между тремя подгруппами, порядок которых —
степень простого числа:
334 = Я^^^/^ = Cf396x4/4 ^ 334^^ (mod397),
286 = Я^^^/^ = g.396a;9/9 ^ 79^9 (mod397),
273 = H^^^l^^ = QS96xu/n ^ 290^^^ (mod397).
Обратите внимание на то, что Ха (где а = 4, 9, 11) — решение исход­
ной задачи по модулю а. Поэтому, найдя все три гГд, мы восстановим
X по модулю 396, что нам и нужно.

9.2.1. Определяем х^
Легко увидеть, что Ж = 1, но стоит потрудиться и понять, как это
4
обнаруживает алгоритм. Представим Х4 в виде
Х4 = а;4,0 + 2 • 0^4,1 7
где 0:4,0? ^4,1 ^ {О? !}• Напомним, что нам нужно решить уравнение
Я ' = 334 = 334^^ =G'''\
Вводим элементы W^ = Н' is. G" — G' \L решаем задачу дискрет­
ного логарифмирования


в циклической группе порядка 2. Применяя метод, о котором будет
рассказано позже (назовем его временно оракул), найдем Ж4,о = 1-
Теперь, идя по индукции, приходим к уравнению
1Г_
- = G'"''^' (mod 397).
О'
Подставляя численные значения, имеем
1 = 396^^'S
что является очередной задачей дискретного логарифмирования в
группе простого порядка. Вновь прибегая к помош;и оракула, нахо­
дим Х4,1 = 0. Значит, Г 4 = Ж4,о + 2 • 0:4,1 = 1 + 2 - 0 = 1.
Г

9.2.2. Ищем хд
Представляем его в виде многочлена:

^9 = ^9,0 + 3 • ^9,1
240 Глава 9. Дискретные логарифмы

с коэффициентами 0:9^0? ^9,1 ^ {0,1,2}. Как Вы помните, мы решаем
уравнение
Н' = 286 = 79'^^ = 0""^
Положим Н" — Н' , G" = О' VL получим задачу логарифмирования
в группе порядка 3:


Применяя оракул, определим Ж9,о = 2. Это нам дает соотношение

^ = G^'^^'^ (mod397).

Следовательно, 1 = 362^^'^ — очередная задача логарифмирования
в группе порядка 3. Находим ждд = О, откуда
Х9 = ^9,0 + 3 • Ж9,1 = 2 + 3 - 0 = 2.


9.2.3. Определяем хц
Здесь задача
273 = 290^^11 (mod 397)
сформулирована в циклической группе простого порядка. Поэто­
му для ее решения можно воспользоваться оракулом, который нам
найдет Хц = 6.
Финал заключается в восстановлении решения исходной задачи
208 = 5^ (mod 397)
по установленным тождествам:
( X = 1 (mod4),
< х = 2 (mod9),
( ж = 6 (mod 11).
^
Применяя китайскую теорему об остатках к этой системе, находим
ответ исходной задачи: х = 281.


9.3. Шаги младенца/шаги гиганта
в предыдуш;ем параграфе мы предполагали, что суш;ествует ора­
кул, решаюш;ий задачу дискретного логарифмирования в цикличе­
ских группах простого порядка. Теперь мы опишем обилий метод
решения этой проблемы, который называется «шаги младенца/шаги
9.3. Шаги младенца/шаги гиганта

гиганта» и применяется, вообще говоря, в любой конечной абелевой
группе.
Поскольку предварительные этапы в методе Полига-Хеллмана
довольно просты, основная трудность решения общей проблемы дис­
кретных логарифмов падает на группу простого порядка. Таким
образом, в общих группах сложность метода шаги младенца/шаги
гиганта будет доминировать над сложностью любого алгоритма.
Действительно, можно показать, что метод, о котором сейчас пой­
дет речь, — лучший из решающих задачу дискретного логариф­
мирования в произвольной группе. Конечно, в любой конкретной
группе может найтись специальный алгоритм, который работает
быстрее, но для общей группы, метод «шагов»— вероятно, самое
лучшее, что можно придумать.
Зафиксируем обозначения. Пусть А = (G) — циклическая груп­
па простого порядка р. В ней выделен элемент Н и спрашивает­
ся: как найти число х по модулю р, удовлетворяющее уравнению
Н = G^? Будем предполагать, что фиксирован некий способ записи
элементов группы в компьютер, так что без труда можно хранить
ее элементы, сортировать их и производить среди них поиск требу­
емого элемента.
Идея, легшая в основу метода «шагов», — стандартная стратегия
«разделяй и властвуй», используемая во многих областях информа­
тики. Решение определяется в виде
X = XQ + Xi\y/p]^

где \у] — целая часть числа у с недостатком, т. е. наибольшее целое
п, удовлетворяющее неравенству п ^ у. Неравенство х ^ р влечет:
О ^хо, XI < [ ^ ] .
Сначала делаем шаги младенца:
Gi=:G' для0^i< Tv^.
Пары (Gi^i) хранятся в таблице таким образом, что любую из них
можно легко найти по первому элементу. Это делается либо с помо­
щью упорядочивания таблицы но первому элементу, либо, что более
эффективно, с помощью хэш-таблиц. На вычисления результатов
алгоритму требуется


операций и примерно такой же объем компьютерной памяти для их
хранения. Далее вычисляют шаги гиганта:
Hj = HG-^^^^ для О ^ i < r v p ] .
242 Глава 9. Дискретные логарифмы

После этого пытаемся найти такую пару из таблицы, сформирован­
ной на предыдуш;ем этапе, чтобы Gi = Hj. Если такая пара найдет­
ся, то

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

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

ОГЛАВЛЕНИЕ

Следующая >>