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

wsc810

设$N=4k+3$, 计算 $x=(a+bI)^N (mod N)$,如果$x=a-bI$,则$N$为素数. 其中基$a+bI$可以 任意取，但$a,b$不能相等,且$GCD[a+bI,N]=1$。在实际计算中，为了等式更好地比较，可以两边同乘以 $(a+bI)$ 则有 $a^2+b^2=(a+bI)^{N+1} (mod N)$

郭先抢

哈哈哈,这个小论坛,一些计算机水平较高的人是有的,也有一些数学水平比较高的人, 但是要谈到数论水平很高的人,我觉得是找不到的. 我建议你自己找反例,应该很容易找到反例的.我觉得你可以很快找到反例, 凭借我对数论的感觉,我觉得你的算法应该是有伪素数的.

郭先抢

其实不是看不起你,而是基本上你能想到的方法,那些专门研究的人肯定能想到的, 其实我早就劝你不要折腾素数了,这个东西也许有统计规律,但是像你这么简单的 方法应该不行的

郭先抢

假设我取b=0,然后a=2, N取一个除以4余3的伪素数, 这样你的算法不就被推翻了吗?

wsc810

4# 郭先抢 那就变为特殊情况了，这里虚数I就不起作用了

wsc810

$mathe$,$wanye$,数学星空,hujunhua能给出一个证明吗，我想只要稍努力思考一下，证明的方法是有的。

mathe

没有本质变化，由于$p|C_p^k$,所以二项式展开即可

mathe

本质是对于任意素数p和非平方剩余u,多项式a+bx有 （a+bx)^p(mod p,x^2-u)=a+bx^p(mod p,x^2-u)=a+bu^((p-1)/2)x(mod p)=a-bx

wsc810

没人证明我给出自己的证明，用反证法：现在考虑以下何种情况下$(a+bI)^N=a-bI(mod N)$ 我们可以断定$N$没有$4k+1$ 的因子, 假设$N$有$q=4k+1$ 的因子$N=q*d$ , then $(a+bI)^N=((a+bI)^q)^d=(a-bI)^d=a^d+b^d(-I)^{4k+3}=a^d+b^d*I\ne a-bI (mod q)$, so所以 N 没有 $4k+1$ 的因子。 所以$N$ 只能含有3,or 5 or 7 个形如$4k+3$的因子 ， 现在考虑3个因子的情况. 假设同余式成立 $(a+bI)^{q_1q_2q_3}=a-bI (mod q_1q_2q_3 )$ 则有 $((a+bI)^{q_1})^{q_2q_3}=(a-bI)^{q_2q_3}=a-bI(mod q_1)$ (1) $((a+bI)^{q_2})^{q_1q_3}=(a-bI)^{q_1q_3}=a-bI(mod q_2)$ (2) $((a+bI)^{q_3})^{q_1q_2}=(a-bI)^{q_1q_2}=a-bI(mod q_3)$ (3) 因为 $ ((a-bI)^{q_1+1})^{(q_1-1)k}=(a^2+b^2)^{(q_1-1)k}=1(mod q_1) $ (1)式两边同乘以$(a-bI)$ $(a-bI)((a-bI)^{q_1+1})^{(q_1-1)*k_1}=(a-bI)^{(q_1^2-1)*k_1+1}(mod q_1)$ (2),(3)式同样处理 $(a-bI)((a-bI)^{q_2+1})^{(q_2-1)*k_2}=(a-bI)^{(q_2^2-1)*k_2+1}(mod q_2)$ $(a-bI)((a-bI)^{q_3+1})^{(q_3-1)*k_3}=(a-bI)^{(q_3^2-1)*k_3+1}(mod q_3)$ 所以 $q_2q_3=(q_1^2-1)*k_1+1$ (1) $q_1q_3=(q_2^2-1)*k_2+1$ (2) $q_1q_2=(q_3^2-1)*k_3+1$ (3) (1)/(2) $\frac{q_2}{q_1}=\frac{(q_1^2-1)*k_1+1}{(q_2^2-1)*k_2+1}$ $q_2*((q_2^2-1)*k_2+1)=q_1*((q_1^2-1)*k_1+1)$ 因 $q_2,q_1$是素数，所以有 $(q_2^2-1)*k_2+1=q_1*t$ (3) $(q_1^2-1)*k_1+1=q_2*t$ (4) 整理，得 $(q_1^2-1)k_1=q_2-1$ (3) $(q_2^2-1)k_2=q_1-1$ (4) 将$q_2=\frac{(q_1^2-1)k_1+1 }{t}$带入(4)，整理得 $q_1t^3+(k_2-1)t_2^2-k_2((q_1^2-1)*k_1+1)^2=0$ 现在只需证明该三次方程对t无正整数解，到这里我卡住了，望高人指点。 我前面的证明有问题吗？

mathe

错误证明。不过这方法的确通常比没有虚部的要好，但是不同的底，可靠性不同