找回密码
 欢迎注册
查看: 20553|回复: 21

[原创] 二次基伪素数与素性判定

[复制链接]
发表于 2012-11-22 15:02:43 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
首先有如下论断 ,若  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}$为基的伪素数,谁能求得这样的几个伪素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-11-22 18:25:31 | 显示全部楼层
很难呀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-11-23 18:53:18 | 显示全部楼层
别搞了,现在的bpsw算法已经很不错非常实用了,如果仅仅只是从工程的角度来处罚,已经完全够你用了!
如果你不相信判定的是素数,你再用miller-rabin算法就可以了!多判定几次,肯定能让你满意的.
如果你不能搞出确定的并且是高效的算法,那么做的功是没有多少价值的!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-11-24 19:32:09 | 显示全部楼层
你是不折腾不回头~
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-11-25 23:20:21 | 显示全部楼层
是不是通过拉宾—米勒测试的所有伪素数都通不过卢卡斯测试?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-11-27 14:02:40 | 显示全部楼层
请举例说明是什么样的伪素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-11-27 16:04:41 | 显示全部楼层
{27, 1127, 1853, 3703, 5473, 5777, 7587} 是10000以内以$sqrt{5}$为基的伪素数,
Mathematica代码:
  1. Select[Range[7, 10000, 2], (JacobiSymbol[#, 5] == -1 && Mod[ChebyshevT[(# + 1)/2, 9], #] == # - 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$,所以经检验也是正确的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-11-27 16:22:18 | 显示全部楼层
现在发现10000以内上述合数做以5为基的米勒——拉宾测试,都不能通过,是否可以断定以$sqrt{5}$为基的卢卡斯伪素数不能通过以$5$为基的米勒——拉宾测试。

谁能够优化一下那个mathematica代码,找到100万以内的以$sqrt{5}$为基的伪素数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-11-27 19:39:53 | 显示全部楼层
gxqcn感兴趣吗,你可是专做素性判定的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2012-12-1 12:29:35 | 显示全部楼层
考虑一下高斯整数,对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万以下这样的伪素数存在吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 10:25 , Processed in 0.044957 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表