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

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) - или псевдокоде.Очевидно, я хочу сам закодировать решение, но я не смогу добиться большего прогресса, пока не пойму алгоритм.

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

Заранее благодарю

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

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

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

Answer 1

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

y == G.^Икс (мод p).

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

Неэффективный метод для поиска X, было бы просто попробовать все значения в диапазоне 1 .. P-1. Несколько лучше "Детский гигантский шаг" Метод, который требует O (P^0.5) арифметические операции. Оба метода довольно медленные для больших с. Pohlig-Hellman - значительное улучшение, когда P-1 имеет много факторов. То есть предположим, что

P-1 = NR

Тогда какой Pohlig и Hellman предлагают решить уравнение

у^N. == (G.^N.)^z.(мод p).

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

n log_грамм(Y) == журнал_грамм(Y.^N.) == NZ (MOD P-1).

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

журнал_грамм(y) == z (мод r).

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

Это улучшение, поскольку нам нужно только найти диапазон 0 .. R - 1 для решения Z. И снова «Baby-Step Giant-Step» можно использовать для улучшения поиска Z. Очевидно, что это еще не является полным решением. Т.е. нужно повторить алгоритм выше для каждого главного фактора R P-1, а затем использовать китайскую точечную теорему для поиска х из частичных решений. Это хорошо работает, если P-1 - квадратный бесплатный.

Если P-1 делится на главной мощности, то может быть использована илая идея. Например, давайте предположим, что P-1 = MQ^k.Отказ На первом этапе мы вычисляем Z, что X == Z (MOD Q), как показано выше. Далее мы хотим расширить это на решение x == z '(мод Q²). Например, если P-1 = MQ² Тогда это означает, что мы должны найти Z 'такое, что

у^М. == (G.^М.)^{z '} (мод p).

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

Answer 2

Прямо сейчас я сам его кодирую (JAVA).Я использую метод Полларда-Ро, чтобы найти малые простые множители p-1.Затем используйте Pohlig-Hellman для разгадки закрытого ключа DSA.y = g^x.У меня такая же проблема..

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

если вы найдете модификацию a ^ c0, это будет иметь смысл

С уважением