An Overview of Elliptic Curve Primality Proving

nyy

我想了解ECPP的细节！！！！！！！！！！有谁知道？

nyy

@无心人 来，过来研究研究椭圆曲线

nyy

nyy 发表于 2023-6-12 08:44
Pocklington 似乎是这个定理在椭圆曲线里面的推广，简单的说就是阶足够大！
然后就是素数！

我自己找出反例了，光阶足够大还不行，还必须互质！
比如n=3589
找151
151^72=1(mod n)
151模n的阶是72，这个阶大于3589的平方根，
但是
151^(72/2)-1与n的不互质，最大公约数37
151^(72/3)-1与n的不互质，最大公约数97

因此n=3589不是素数。

所有代码

1. Clear["Global`*"];(*清除所有变量*)
   
2. n=37*97 (*n=3589*)
   
3. (*计算151模n的阶,得到72*)
   
4. m=MultiplicativeOrder[151,n]
   
5. r1=PowerMod[151,m/2,n]-1;g1=GCD[r1,n];{r1,g1}
   
6. r2=PowerMod[151,m/3,n]-1;g2=GCD[r2,n];{r2,g2}
   

复制代码

nyy

nyy 发表于 2023-6-13 16:14
我自己找出反例了，光阶足够大还不行，还必须互质！
比如n=3589
找151

这个例子不对，因为需要被证明的数，通常都是素数，
而我这个反例是合数，
不足以证明互质的重要性

nyy

把算法数论上的这个定理搬过来了！

nyy

https://inria.hal.science/inria-00138382v2/file/paper.pdf

https://www.detailedpedia.com/wiki-Pocklington_primality_test

其实让人很困惑，即使是Pocklington定理，
不同地方，居然不一样。上面的两个不一样

nyy

计算数论1：素性检验 - 沙金锐的文章 - 知乎
https://zhuanlan.zhihu.com/p/105902706

nyy

看来看去，还是BPSW算法好，miller rabin+lucas U+lucas V ，效率高，准确率高

nyy

椭圆曲线证明素数的思路就是
多米诺骨牌思想，
p0>p1>p2>p3>...
p[i]差不多是p[i-1]的平方根这个数量级，
然后p0的素性由p1来保证，
然后p1的素性由p2来保证，
然后p2的素性由p3来保证，
因为每次都开一个平方根这样，
然后不断降低，最后可以用试除法来判定最小的素数。
最后形成一个多米诺骨牌！最后证明所有的数都是素数

lihpb00

英文看不懂，能翻译成中文吗？