第二组代表作背景
1956年,ErdÖs 猜测 < x的 Carmichael
数有xa 个，当 x 趋于∞时,a
趋于1. 他用的方法是: 给定x,用前 s(x)个素数为种子构造某个 Carmichael
数的集合C s(x). 他猜测
| C s(x)| > xa，当 x趋于∞时,a
趋于1. 但如果给定 s (与x无关), 他没有给出作为s的函数 |Cs|
的值.
1977年, Williams 问是否存在有奇数个素因子的
Carmichael 数 n 具有附加性质： 对于 n 的任一素因子 p 都有 p+1 | n+1. 后来人们把满足如此条件的 Carmichael 数
称为 Williams 数 (虽然自今还未找出Williams 数的具体例子).
1980年, Baillie、Pomerance、Selfridge 和 Wagstaff 提出双参数
Lucas 测试, 并发现被
Miller测试 误认为是素数的合数都不能通过
Lucas 测试, 于是提出著名的
BPSW测试, 它是一次
Miller 测试和一次“真正的” (即满足
Jacobi 符号
(D/n) = -1) 的双参数 Lucas 测试的组合. 但不明白为什么 BPSW 测试比单独仅用 Miller 测试或 Lucas
测试要安全得多？
1984年, 基于 ErdÖs构造集合C s(x)的方法, Pomerance在一篇未正式发表的短文中,提出构造一个集合W (x) 的方法,此集合中的每个数都是
BPSW 测试的反例,猜测有无穷多个这样的数.事实上,他构造的反例就是 Williams数, 虽然他在短文中未提及 Williams 1977年的问题.
1997年,
Arnault
证明了双参数 Lucas测试出错概率为4/15 或1/2,
并指出, 人们对 BPSW测试出错概率尚无准确结果.
1998年,
Grantham基于双参数二次多项式提出一个出错概率为
1/7710 的测试 (简称RQFT), 并指出, 找不到 BPSW 测试的反例表明它的出错概率可能低得多.
2007年, Pinch 求出所有小于1021 的
Carmichael 数 , 共 20138200 个 , 其中没有Williams 数, 同年, Echi认为可能不存在Williams 数.
在这样的背景下, 留给我们的任务是:
(1) 确定 BPSW 测试的出错概率, . 以便弄明白人们对 BPSW测试的两个未知问题： 为什么 BPSW 测试比分开来考虑单个子测试 安全可靠得多和为什么很难找到 BPSW 测试的反例
(2) 由于BPSW 测试的反例(Williams
数)的求出将会推动把此测试转化为比ψm方法有效得多的确定型实用素性测试的进程,先要找到Williams 数的具体例子,或至少提出找Williams 数的方案; 由于Williams数是Carmichael 数,
而小于1021
的Carmichael 数, 共 20138200
个(2007年Pinch 求出), 其中没有Williams数,
所以先要找更大的有更多个Carmichael 数,的集合. 这些就是第二组代表作要做的事.
2022-1-18