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不是素数。
所有代码
Clear["Global`*"];(*清除所有变量*)
n=37*97 (*n=3589*)
(*计算151模n的阶,得到72*)
m=MultiplicativeOrder
r1=PowerMod-1;g1=GCD;{r1,g1}
r2=PowerMod-1;g2=GCD;{r2,g2}
nyy 发表于 2023-6-13 16:14
我自己找出反例了，光阶足够大还不行，还必须互质！
比如n=3589
找151
这个例子不对，因为需要被证明的数，通常都是素数，
而我这个反例是合数，
不足以证明互质的重要性 把算法数论上的这个定理搬过来了！ https://inria.hal.science/inria-00138382v2/file/paper.pdf
https://www.detailedpedia.com/wiki-Pocklington_primality_test
其实让人很困惑，即使是Pocklington定理，
不同地方，居然不一样。上面的两个不一样
计算数论1：素性检验 - 沙金锐的文章 - 知乎
https://zhuanlan.zhihu.com/p/105902706 看来看去，还是BPSW算法好，miller rabin+lucas U+lucas V ，效率高，准确率高 椭圆曲线证明素数的思路就是
多米诺骨牌思想，
p0>p1>p2>p3>...
p差不多是p的平方根这个数量级，
然后p0的素性由p1来保证，
然后p1的素性由p2来保证，
然后p2的素性由p3来保证，
因为每次都开一个平方根这样，
然后不断降低，最后可以用试除法来判定最小的素数。
最后形成一个多米诺骨牌！最后证明所有的数都是素数 本帖最后由 lihpb00 于 2023-6-26 22:17 编辑
英文看不懂，能翻译成中文吗？
页:
1
[2]