错误证明。不过这方法的确通常比没有虚部的要好，但是不同的底，可靠性不同
mathe 发表于 2012-12-5 21:42 http://bbs.emath.ac.cn/images/common/back.gif
具体错在哪里，请指明好吗？而且对于合数N我在自己2G内存的笔记本上做了验证的，10^8以内无反例， 且每次最大只能验证(2*10^8)/4 个数，区间范围设得太大则提示内存不足。
我在梅森数论坛上发表了同样的帖子，已有高人指出这就是AKS算法的特例，现在的情况就是不需要那么高次数的多项式。
8# mathe
（a+bx)^p(mod p,x^2-u) 这种写法代表什么意思呢，请mathe说明一下
维基百科：AKS质数测试 “虽然说关系式 (1) 基本上构成了整个质数测试，但是验证花费的时间却是指数时间”对模幂运算，不是有对幂的二进制扫描算法吗（大概是$O(log(N))$），怎么还是指数时间，这段话该怎么理解？
14# wsc810
维基百科：AKS质数测试 “虽然说关系式 (1) 基本上构成了整个质数测试，但是验证花费的时间却是指数时间”对模幂运算，不是有对幂的二进制扫描算法吗（大概是$O(log(N))$），怎么还是指数时间，这段话该怎么理解？
wsc810 发表于 2012-12-6 10:07 http://bbs.emath.ac.cn/images/common/back.gif
你是个不撞南墙不回头的人,AKS的效率远远小于黎曼假设下的miller-rabin算法.
而后者从效率上还不如BPSW算法
BPSW再加上若干次miller-rabin测试,结果远远比你想象的要好,现在的概率性算法已经
非常好了,也是非常实用的
16# 郭先抢
看了维基百科BPSW的算法介绍，这是一个综合性的算法，它首先进行的是试除法，然后是米勒——拉宾测试，最后是卢卡斯测试。
15# 郭先抢
AKS算法最好情况下的时间复杂度为$O(log^6(N))$ ，而我说算法的时间复杂度为$O(log(N))$,是否比AKS算法的时间复杂度还小。
15# 郭先抢
AKS算法最好情况下的时间复杂度为$O(log^6(N))$ ，而我说算法的时间复杂度为$O(log(N))$,是否比AKS算法的时间复杂度还小。
wsc810 发表于 2012-12-6 14:36 http://bbs.emath.ac.cn/images/common/back.gif
一次miller-rabin 是$O(log^3(N))$,你居然说你的算法是$O(log(N))$,
还是劝你不要再折腾这个的,但是凭借对你发帖的了解,你应该不撞南墙不回头的,
只有你撞疼了,你才会回头
我发现我很聪明,把你的公式修改一下,然后,,,,,哈哈哈