找回密码
 欢迎注册
楼主: wsc810

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

[复制链接]
发表于 2013-3-30 02:15:09 | 显示全部楼层
1# wsc810

要搞素数的确定性证明,很不容易啊。我这里有一个资料,是颜松远教授的一本书上写的。
大家可以看一下,和我们现在的差距有多大。
我把他写的原文附在下面:

  将Lucas数$u_n$定义成$u_n=(a^k-b^k)/(a-b)$,其中,$a$和$b$为$x^2-Ax+B=0$之根,称奇合数$n$(其中,$n-1=2^d$,$d$为奇数)为基$2$的“强伪质数”(或“强拟质数”),如果它满足$A^d-=1(mod n)$或者满足$A^(d*(2^r))-=-1(mod n)$,$0<=r<s$.找出这样的一个合数$n$,使其最后一个十进制位或者是$5$或者是$7$,并且$n$ 是基$2$的“强伪质数”,同时$n$还必须能够整除Lucas数$u_(n+1)$.
  你要能找到这样一个合数,美国3位著名数学家Pomerance,Selfridge和Wagstaff将奖励你620美元,(这个问题在质性判定和密码学中有重要应用,计算机代数系统Maple的质性检验就是基于组合应用Miller-Rabin和Lucas这两个概率检验方法的。该组合方法自1980年提出至今,还没有发现一个反例。如果该合数存在的话,它至少具有数百个十进制位。)

  以上是颜松远教授的原文。(颜松远:江西吉安人,毕业于中国科学院研究生院,获理学硕士学位,并在英国York大学数学系获得数论专业博士学位,先后在英、美等多所大学从事科研和教学工作,长期从事数论、计算理论、算法分析设计、密码学和信息安全等方面的研究与教学工作,在国际著名出版社Springer出版过三本专著)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-3-31 15:33:45 | 显示全部楼层
本帖最后由 只是呼吸 于 2013-3-31 15:44 编辑

我在21楼的那个原文有一处错了。是这样写的:(其中,n-1=2^s*d,d为奇数)为基2的“强伪质数”(或“强拟质数”)。另外,那个大写的N应该是小写。我个人的看法就是把n-1分解为2的s次幂和一个奇数d的乘积。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-19 13:36 , Processed in 0.038733 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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