cryptography - 单元组子组中离散对数的 SAGE 实现

Question

这是一个与此相关的问题。简而言之，在具有基础组的 ElGammal 密码系统中，单位组以素数 p 为模，我被告知要找到索引 2 的子组来解决离散对数问题以破坏系统。

显然，由于以素数为模的单元组是循环的，如果 x 是生成器，则 x^2 生成索引为 2 的子组。现在，解决 Sage 上的离散对数问题的好方法是什么？我将如何使用在该子组中解决离散对数问题的结果来解决整个组中的问题？

Answer 1

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、...）的效率与子组的大小直接相关；然而，用于求解有限域中离散对数的算法（数域筛、函数域筛）大多对乘法子群的大小不敏感，并且通常比通用算法更有效。