如下方法是一个确定性的素性检验方法吗

wsc810

19# 郭先抢 因为我的方法只需测试一次，计算幂模时间复杂度仅为$O(log(N))$，另外针对梅森数的卢卡斯——勒默测试的时间复杂度是$O(N)$ 吗？

郭先抢

19# 郭先抢 因为我的方法只需测试一次，计算幂模时间复杂度仅为$O(log(N))$，另外针对梅森数的卢卡斯——勒默测试的时间复杂度是$O(N)$ 吗？ wsc810 发表于 2012-12-6 17:15

是模幂,不是幂模

郭先抢

还有,虽然我对算法复杂度不了解,但是目前即使是最快的概率型的算法, 复杂度也是O(log^3(N)),而不是O(log(N))

郭先抢

hao了 我不折腾了

郭先抢

你的这种交流方式我表示个人很不喜欢，幂模这种说法也是有的，你上百度搜搜就知道了，绝不是我自创新词，或者连基本概念都表达不清楚，我有我自己做事的方式，这种探索问题的过程也是一种乐趣。注意这是一个技术性论 ... wsc810 发表于 2012-12-6 21:05

呵呵,看来这个是翻译的问题,第一次领教了,真没想到两者都有. 好了抱歉了

郭先抢

好的,大哥,你继续研究,如果研究出了确定性的并且是高效的算法,记得告诉我. 楼主专研的精神还是值得鼓励的

wsc810

完整的证明方法我已找到了！！！！！

郭先抢

完整的证明方法我已找到了！！！！！ wsc810 发表于 2012-12-13 18:09

恭喜,真的恭喜,上传上来吧!

郭先抢

楼主的证明呢?

wsc810

修改后的证明可以到 mathoverflow 去看，点标签 数论 素数 ，在第一页就可以找到。我相信稍有数学水平的人都可以看懂我的证明。