二次基伪素数与素性判定
首先有如下论断 ，若d 是4k+1型的素数 且 合数 (N/d)= -1 ,则$x^2 = d (mod N )$无解。然后计算 pell 方程$p^2-dq^2=1 $
若$(p+q*sqrt{d})^{(n+1)/2} = -1 (mod N)$ ,则称 合数$N$是以$sqrt{d}$为基的伪素数，谁能求得这样的几个伪素数 很难呀 别搞了,现在的bpsw算法已经很不错非常实用了,如果仅仅只是从工程的角度来处罚,已经完全够你用了!
如果你不相信判定的是素数,你再用miller-rabin算法就可以了!多判定几次,肯定能让你满意的.
如果你不能搞出确定的并且是高效的算法,那么做的功是没有多少价值的! 你是不折腾不回头~ 是不是通过拉宾—米勒测试的所有伪素数都通不过卢卡斯测试？ 请举例说明是什么样的伪素数 {27, 1127, 1853, 3703, 5473, 5777, 7587} 是10000以内以$sqrt{5}$为基的伪素数,
Mathematica代码：Select, (JacobiSymbol[#, 5] == -1 && Mod, #] == # - 1 && ! PrimeQ[#]&)]现在取$N=1853$ 加以分析
因为有 雅克比符号$ (N/5)=-1$
且$(9+4*sqrt{5})^{(1853+1)/2}=-1 mod (1853)$而1853=17*109
现在再来分析一下，因为$ (5/17)=-1$ ,所以有$(9+4*sqrt{5})^17=(9-4*sqrt{5}) (mod 17)$则
$(9+4*sqrt{5})^18=1 (mod 17)$,$(9+4*sqrt{5})^9=-1(mod 17)$ 又$ (5/109)=1$ 所以有
$(9+4*sqrt{5})^108=1 (mod 109) $现在寻找它的阶 ，因为 $21^2=5 (mod 109)$
所以可以用mathematica找到它的阶 $(9+4*21)^18=1 (mod 109 )$ ,$(9+4*21)^9=-1 (mod 109 )$而 $(1853+1)/2=927$ ,而 $927/9=103$,所以经检验也是正确的 现在发现10000以内上述合数做以5为基的米勒——拉宾测试，都不能通过，是否可以断定以$sqrt{5}$为基的卢卡斯伪素数不能通过以$5$为基的米勒——拉宾测试。
谁能够优化一下那个mathematica代码，找到100万以内的以$sqrt{5}$为基的伪素数 gxqcn感兴趣吗，你可是专做素性判定的 考虑一下高斯整数，对4k+3的数N，我们熟知有
(a+bI)^N = a-bI则
(a+bI)^(N+1)=a^2+b^2
现在假设a+bI=2+3I,满足(2+3I)^N=2-3I的合数，500万以下，用
Mathematica一个也没有找到，据此，能否给出一个对于4k+3的数的一个有力的素性判定的方法呢，BTW.谁电脑强悍，算以下5000万以下这样的伪素数存在吗？