单元组子组离散对数的SAGE实现
SAGE implementation of discrete logarithm in subgroup of group of units
这是一个与 this 相关的问题。简而言之，在具有基础组的 ElGammal 密码系统中，单位组对质数 p 取模，我被告知要找到索引 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 等）的效率与子组的大小直接相关；然而，用于求解有限域（数域筛、函数域筛）中的离散对数的算法大多对乘法子群的大小不敏感，并且通常比通用算法更有效。
这是一个与 this 相关的问题。简而言之，在具有基础组的 ElGammal 密码系统中，单位组对质数 p 取模，我被告知要找到索引 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 等）的效率与子组的大小直接相关；然而，用于求解有限域（数域筛、函数域筛）中的离散对数的算法大多对乘法子群的大小不敏感，并且通常比通用算法更有效。