SAGE реализация дискретного логарифма в подгруппе группы единиц

Question

Это вопрос, связанный с этим. Вкратце, в криптосистеме ElGammal с лежащей в основе группой группой модулей по модулю простого числа p мне сказали найти подгруппу индекса 2 для решения задачи дискретного логарифма, чтобы сломать систему.

Ясно, что, поскольку группа единиц по модулю простого числа циклическая, если x - генератор, то x^2 порождает подгруппу индекса 2. Теперь, каков хороший способ решения задачи дискретного логарифма в sage? Как бы я использовал результат решения задачи дискретного логарифма в этой подгруппе, чтобы решить ее во всей группе?

Answer 1

Мудрец знает, как вычислить дискретные логарифмы в конечных полях:

sage: K = GF(19)
sage: z = K.primitive_element()
sage: a = K.random_element()
sage: b = a.log(z)
sage: z^b == a
True

Вы можете использовать эту функцию для решения дискретного логарифма в подгруппе индекса 2

sage: x = z^2
sage: a = K.random_element()^2
sage: a.log(x)
6

Это всего лишь игрушечный пример, но обратите внимание, что это не более эффективно, чем решение дискретного логарифма в полной группе ₁₉*.

Это правда, что эффективность универсальных алгоритмов (например, шаг Baby Giant, Pollard rho, ...) напрямую связана с размером подгруппы; однако алгоритмы, используемые для решения дискретных логарифмов в конечных полях (сито числового поля, сито функционального поля), в основном нечувствительны к размеру мультипликативной подгруппы и в целом гораздо более эффективны, чем универсальные алгоритмы.