Lenstra的ECM算法-字段要求

Question

在Lenstra的ECM算法中，要求\#E(\mathbb{F}_{p})具有较小的素因子。为何会这样呢？

据我所知，p-1方法对于小因子分解N是有效的.该算法用椭圆曲线上的点代替\mathbb{Z}/p\mathbb{Z}群，这两个群都具有有限基数。为什么对前者没有限制呢？

Answer 1

在Lenstra的ECM算法中，要求\#E(\mathbb{F}_{p})具有较小的素因子。为何会这样呢？

实际上，它不需要有小的素因子；如果它碰巧有较小的因素，它确实工作得更好(也就是说，成功得更快)。为了更全面地解释它，我们将查看ECM和p-1方法，该方法将给出您的评论：

据我所知，p-1方法对于小因子分解N是有效的.

实际上，它擅长的是分解N，它恰好有一个素因子p，其中p-1是光滑的；也就是说，只有小的因子。

p-1和ECM方法都是这样工作的:我们采用我们的复合数n = pq (其中，通常可以有两个以上的素数)，并设置秘密值p - \epsilon_1，q - \epsilon_2。然后，我们继续猜测p - \epsilon_1，q - \epsilon_2的素数；如果我们猜测其中一个因子的所有素数，那么我们立即得到因式分解(并且除了时间之外，作出错误的猜测是没有惩罚的)。

这就是他们的共同点；现在，这里是p-1和ECM之间的区别。使用p-1方法，我们总是有\epsilon_1 = \epsilon_2 = 1 (这就是使p-1平滑很重要的地方；我们将猜测小的因素，所以当所有的因素都很小时，p-1就能工作)。现在，对于ECM，\epsilon_1, \epsilon_2很小(相对于p, q的大小)，但是可以在很大程度上改变(取决于曲线)。

这就是ECM的优点: p-1方法完全依赖于算法控制之外的东西。如果p-1和q-1都包含一个很大的(不可猜测的)因子，这是不走运的，而且算法对此无能为力。使用ECM，我们可以尝试许多不同的曲线(不同的\epsilon_1, \epsilon_2值)，我们可能会得到一个幸运。