问求解ECDLP的小复乘法域判别法

EN

在回答问题之前，我首先回顾一些关于离散对数问题和Pollard算法的基础知识。

离散对数问题

给出椭圆曲线上素数阶P的点q和P生成的子群中的点Q，则存在k，使得Q = kP在0\leq k < q中。

Q在基P中的离散对数是k，离散对数问题是寻找k已知的P和Q。

Pollard-rho算法

在素数阶q的一般群上的Pollard算法具有\sqrt{\pi q/2}的复杂性.

它的原理是用随机整数R_0 = a_0P+b_0Q和a_0和b_0来构造一个点序列，然后使用一个作为伪随机游走的函数f来获得点的序列：

最终，会有一个点R_j，它等于序列中的上一个点R_i。然后，我们推断：

当然，如果(b_j-b_i)是可逆的(但这种情况有很高的可能性)。

现在，生日悖论给出了上述复杂性。

快速增长的rho

在椭圆曲线上，自-P以来，由P=(x,y)计算-P=(x,-y)是很容易的。然后，我们可以通过对\{P,-P\}对曲线的所有点进行重组。

我们不是在序列中寻找点R_i和R_j之间的冲突，而是在它们的x-coordinate上寻找碰撞。如果我们有R_i = \pm R_j，就会发现离散对数。

这就好像没有对所有的点进行搜索，但只对其中的一半进行了搜索。然后将复杂性中的值q替换为q/2，这将给出\sqrt{q\pi/4}的复杂性(您将在网站SafeCurves上找到相应的页面)。

加速- rho进一步

我们在上面所做的事情是可能的，因为我们有一个映射(称为自同态) [-1]：

它将椭圆曲线E的一个点发送到它的对立面。我们可以看到，如果我们使用它两次，我们回到原来的观点。我们说这个映射有顺序2，这就是为什么我们可以按对分组。而且计算起来很容易。

现在的问题是:是否还有其他易于计算的地图，可以用更大的因子来加速rho？

答案是肯定的。例如，曲线secp256k1具有以下自同态：

其中，\beta是曲线有限域上的阶3 (满足\beta^3=1和\beta \neq 1)的一个元素。然后我们有：

这意味着\phi的顺序是3。

然后，我们可以将曲线上的点按三组：\{ P, \phi(P), \phi^2(P)\}分组。我们选择三个点中的一个作为代表(例如将最小的x-coordinate看作整数的点)。我们不是在q点上搜索Pollard中的冲突，而是在q/3代表上搜索冲突。由此推断，在这条曲线上，我们可以用一个因子\sqrt 3除以Pollard的复杂性。再加上前面的加速，这给了\sqrt{q\pi/12}的复杂性.

与CM场判别

的关系

关键是我们想要一个易于计算的自同态，否则它将无助于加速Pollard。正如我们所看到的，上面给出的两个例子非常简单。这是因为它们的度是1，这意味着计算\phi(P)坐标的有理函数是1的多项式。

CM场判别小度自同态的存在是有联系的.在曲线secp256k1的情况下，这个判别式是-3这一事实与自同态\phi直接相关，其公式如下：

这意味着有一个度1的非平凡自同态，即上面给出的自同态。

我希望我能给出一些内容来回答你的问题。我稍后会尝试扩展和改正一些问题。