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

wsc810

错误证明。不过这方法的确通常比没有虚部的要好，但是不同的底，可靠性不同
mathe 发表于 2012-12-5 21:42

具体错在哪里，请指明好吗？而且对于合数N我在自己2G内存的笔记本上做了验证的，10^8以内无反例， 且每次最大只能验证(2*10^8)/4 个数，区间范围设得太大则提示内存不足。

wsc810

我在梅森数论坛上发表了同样的帖子，已有高人指出这就是AKS算法的特例，现在的情况就是不需要那么高次数的多项式。

wsc810

8# mathe

（a+bx)^p(mod p,x^2-u) 这种写法代表什么意思呢，请mathe说明一下

wsc810

维基百科：AKS质数测试 “虽然说关系式 (1) 基本上构成了整个质数测试，但是验证花费的时间却是指数时间”对模幂运算，不是有对幂的二进制扫描算法吗（大概是$O(log(N))$），怎么还是指数时间，这段话该怎么理解？

郭先抢

14# wsc810

维基百科：AKS质数测试 “虽然说关系式 (1) 基本上构成了整个质数测试，但是验证花费的时间却是指数时间”对模幂运算，不是有对幂的二进制扫描算法吗（大概是$O(log(N))$），怎么还是指数时间，这段话该怎么理解？
wsc810 发表于 2012-12-6 10:07

你是个不撞南墙不回头的人,AKS的效率远远小于黎曼假设下的miller-rabin算法.
而后者从效率上还不如BPSW算法

郭先抢

BPSW再加上若干次miller-rabin测试,结果远远比你想象的要好,现在的概率性算法已经
非常好了,也是非常实用的

wsc810

16# 郭先抢
看了维基百科BPSW的算法介绍，这是一个综合性的算法，它首先进行的是试除法，然后是米勒——拉宾测试，最后是卢卡斯测试。

wsc810

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

一次miller-rabin 是$O(log^3(N))$,你居然说你的算法是$O(log(N))$,
还是劝你不要再折腾这个的,但是凭借对你发帖的了解,你应该不撞南墙不回头的,
只有你撞疼了,你才会回头

郭先抢

我发现我很聪明,把你的公式修改一下,然后,,,,,哈哈哈