Регистрация Войти
Рейтинг:1
avatar Crypto

Восстановление альтернативных решений дискретного логарифма, которые можно атаковать с помощью Pohlig-Hellman

флаг in
ARandomUser

В процессе изучения дискретных логарифмов и подходов, которые можно было применить, я увидел алгоритм Полига-Хеллмана.

Позже, когда я работал с $h = g^x \mod p$ куда $p-1$ является гладким, использование Pohlig-Hellman не дало ожидаемого результата и вернуло нечто гораздо большее, чем ожидалось. Я предполагаю, что это связано с тем, что Полиг-Хеллман иногда пропускает самый маленький ответ.

Вопросы:

  1. Как я могу восстановить наименьший возможный $х$ правильно?
  2. у меня больше $х$; может ли это быть использовано для восстановления меньшего $х'$?
59
0 + 0
kelalaka avatar
флаг in
kelalaka
Вы видели [Алгоритм Полига — Хеллмана: общий алгоритм] (https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm#The_general_algorithm)
0
Ответить
флаг in
ARandomUser
@kelalaka Я прочитал это. Это похоже на общий алгоритм использования. Однако я не понимаю, как это допускает альтернативные решения. Можете ли вы указать мне, на что я должен смотреть?
0
Ответить
meshcollider avatar
флаг gb
meshcollider
Наименьшим будет $x \bmod{(p-1)}$, если $p$ — простое число.
0
Ответить
флаг et
user93353
Все решения являются частью класса эквивалентности, заданного $\bmod (p-1)$. Итак, $x' = x \bmod (p-1)$. Тем не менее, последним шагом в алгоритме PH является объединение решений в подгруппы с использованием китайской теоремы об остатках, и решение будет иметь вид $x = something \bmod (p-1)$. Таким образом, вы всегда будете получать наименьшее решение. Не могли бы вы перечислить различные решения вашей подгруппы, которые вы комбинируете с CRT?
0
Ответить
флаг in
ARandomUser
@user93353 user93353 В итоге я решил это из вашего сообщения. Спасибо!
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.