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

Question

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

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

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 

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

Верно, что эффективность общих алгоритмов (например, шаг Магического шага, Поллард Ро, ...) напрямую связана с размером подгруппы; однако алгоритмы, используемые для решения дискретных логарифмов в конечных полях (сито с численным полем, сито силовых полей), в основном нечувствительны к размеру мультипликативной подгруппы и, как правило, намного эффективнее общих алгоритмов.