Алгоритм Полигла – Хеллмана для вычисления дискретных логарифмов

Question

Я работаю над кодированием алгоритма Полигли-Хеллмана, но у меня возникают проблемы с пониманием шагов алгоритма, основанных на определении алгоритма.

По вики алгоритма :

Я знаю, что первая часть 1) - это вычисление простого множителя для p-1, что нормально.

Однако я не уверен, что мне нужно делать в шагах 2), где вы рассчитываете коэффициенты:

Let x2 = c0 + c1(2). 
125(180/2) = 12590 1 mod (181) so c0 = 0.
125(180/4) = 12545 1 mod (181) so c1 = 0.
Thus, x2 = 0 + 0 = 0.

и 3) сложите коэффициенты вместе и решите в китайской теореме об остатках.

Может ли кто-нибудь помочь с объяснением этого на простом английском (i) - или псевдокоде. Я, конечно, хочу сам написать решение, но больше не смогу продвинуться, пока не пойму алгоритм.

Примечание: я много искал это, и я читал С. Полиг и М. Хеллман (1978). «Улучшенный алгоритм вычисления логарифмов над GF (p) и его криптографическое значение, но он все еще не имеет для меня смысла.

Заранее спасибо

Обновление: почему q (125) остается постоянным в в этом примере .

Где, как в этом примере, появляется, как будто он вычисляет новое q каждый время .

Если быть более точным, я не понимаю, как вычисляется следующее: Теперь разделите 7531 на ^ c0, чтобы получить 7531(a^-2) = 6735 mod p.

Answer 1

Начнем с основной идеи Полиг-Хеллмана. Предположим, что нам даны y, g и p, и мы хотим найти x, такой что

у == г ^х (мод р).

(я использую == для обозначения отношения эквивалентности). Для упрощения я также предполагаю, что порядок g равен p-1, то есть наименьшее положительное k с 1 == g ^k (mod p) равно k = p-1.

Неэффективный метод для нахождения x, будет просто попробовать все значения в диапазоне 1 .. p-1. Несколько лучше метод * «Большой шаг младенца», который требует O (p ^0.5 ) арифметических операций. Оба метода довольно медленные для больших р. Pohlig-Hellman является значительным улучшением, когда p-1 имеет много факторов. То есть предположим, что

p-1 = n r

Тогда Полиг и Хеллман предлагают решить уравнение

y ⁿ == (g ⁿ ) ^z (мод р).

Если мы возьмем логарифмы к основанию g с обеих сторон, это то же самое, что и

n log _g (y) == log _g (y ⁿ ) == nz (mod p-1).

n можно разделить, давая

log _g (y) == z (mod r).

Следовательно, x == z (mod r).

Это улучшение, поскольку нам нужно только найти диапазон 0 .. r-1 для решения z. И снова «Baby-step-гигант-шаг» можно использовать для улучшения поиска по z. Очевидно, что сделать это один раз еще не является полным решением. То есть необходимо повторить алгоритм выше для каждого простого множителя r из p-1, а затем использовать китайскую теорему об остатках, чтобы найти x из частных решений. Это хорошо работает, если р-1 свободен от квадратов.

Если p-1 делится на простую степень, то можно использовать аналогичную идею. Например, предположим, что p-1 = m q ^k . На первом этапе мы вычисляем z таким образом, что x == z (mod q), как показано выше. Далее мы хотим расширить это до решения x == z '(мод q ² ). Например. если p-1 = m q ² , то это означает, что мы должны найти z 'такой, что

y ^m == (g ^m ) ^{z '} (mod p).

Поскольку мы уже знаем, что z '== z (mod q), z' должно быть в множестве {z, z + q, z + 2q, ..., z + (q-1) q}. Опять же, мы могли бы либо сделать исчерпывающий поиск по z ', либо улучшить поиск с помощью «гигантского шага младенца». Этот шаг повторяется для каждого показателя степени q, то есть, зная x mod q ⁱ , мы итеративно получаем x mod q ^{i + 1} .

Answer 2

Я сам сейчас это кодирую (ЯВА). Я использую Полларда-Ро, чтобы найти малые простые факторы р-1. Затем с помощью Pohlig-Hellman найти закрытый ключ DSA. у = г ^ х. У меня та же проблема ..

ОБНОВЛЕНИЕ: «Чтобы быть более конкретным, я не понимаю, как вычисляется следующее: теперь разделите 7531 на ^ c0, чтобы получить 7531 (a ^ -2) = 6735 мод р."

если вы найдете modInverse для ^ c0, это будет иметь смысл

Привет