数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[讨论] 能通过2,3,5,7的检验的合数

[复制链接]
发表于 2008-10-8 10:06:28 | 显示全部楼层
看来合数的不好.
对于求解某个底a的一定范围内所有奇伪素数
我们知道,这个伪素数N一定满足$a^{N-1}=1(mod N)$
所以我们可以用这个作为一个最初的筛选条件.
我们先指定一个范围M(比如M=$10^8$)
对于M以内所有同a互素的素数的幂b,我们计算a关于b的最小指数$r(a,b)$,也就是$a^{r(a,b)}=1(mod b)$,而且这个数值要求最小.
然后我们假设伪素数$N=p_1*p_2*...*p_t*q$
其中$p_1,p_2,...,p_t$都是M以内的素数的幂,q为大于M的素数幂的乘积,而且它们都互素(q可以同前面某些$p_i$有公因子.
那么我们可以得到表达式$N=1(mod LCM(r(a,p_1),r(a,p_2),...,r(a,p_t)))$,
对于给定的$p_1,p_2,...,p_t$,我们基本可以非常容易判断所有可能的q的值了(除了$p_1*p_2*...*p_t$很小的时候)
所以对于我们来说,最麻烦的对象是那些一个大素数乘上小因子的情况
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 10:16:14 | 显示全部楼层
对于小因子b乘上大素数Q的情况
假设
N=b*Q是伪素数,我们知道
$a^{Q-1}=1(mod Q)$
$a^{b*Q-1}=1(mod Q)$
由此得出
$a^{(b*Q-1,Q-1)}=1(mod Q)$
由此得出
$a^{(b-1,Q-1)}=1(mod Q)$
得出
$a^{b-1}=1(mod Q)$
也就是
Q是$a^{b-1}-1$的因子,在a和b都不是太大的时候,特别是a是2,b也不算太大时应该能够确定可能的Q.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 10:21:46 | 显示全部楼层
所以如果b*Q是一个关于底2和3的伪素数,而且Q为素数,那么我们可以知道
$Q|(2^{b-1}-1,3^{b-1}-1)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 10:24:00 | 显示全部楼层
那如果是n=p*q,p,q接近的时候呢?如何处理?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 10:53:06 | 显示全部楼层
应该
$p | a^(q - 1) - 1$
$q | a^(p - 1) - 1$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 11:04:23 | 显示全部楼层
安徽芜湖  安徽师范大学 张振祥
这个人是我知道的国内作计算数论的

也许能联系他获得些资料
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 11:07:19 | 显示全部楼层
76#的结论不大好用,我觉得这个时候用72#的结果比较好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 11:10:43 | 显示全部楼层
http://zhangzhx.ik8.com/Cindex.htm
是否有必要拉这个人来看看?

呵呵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-8 11:22:30 | 显示全部楼层
呵呵,我觉得没必要。
他有两篇论文:
Finding strong pseudoprimes to several bases
Finding strong pseudoprimes to several bases II
我有第一篇,大家可以参考一下。

Finding strong pseudoprimes to several bases.pdf

171.15 KB, 下载次数: 15, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-8 11:25:24 | 显示全部楼层


我是说,拉来好不好
如果好,我就拉来了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-5-25 16:40 , Processed in 0.509649 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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