这是一个与这个相关的问题。简而言之，在以素数p为模的基础群的ElGammal密码系统中，我被告知要找到索引2的子群来解决离散对数问题，以破坏系统。
显然，由于模一个素数的单位群是循环的，如果x是生成子，则x^2生成一个指标2的子群。那么，在sage上解决离散对数问题的好方法是什么呢?如何将离散对数问题在这个子群中的求解结果应用到整个群中?
Sage知道如何在有限域中计算离散对数:
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 - step- giant step, Pollard rho，…)的效率与子群的大小直接相关;然而，用于求解有限域中离散对数的算法(数域筛，函数域筛)大多对乘法子群的大小不敏感，并且通常比一般算法更有效。