第一组代表作背景
Miller测试理论简单容易实现, 而且速度快, 所以被许多数学软件包, 例如Maple V.2, 用来作为素性测定的核心部分. 但这样的软件 包对较大的整数进行素性定时有出错的可能, Arnault 构造过四个被Maple V.2误认为是素数的合数(Carmichael数), 分别为29、40、44和80位数.
记ψm为通过前m个素数基的最小强伪素数 (strong pseudoprime), 如果知道ψm的准确值,至多只需m次Miller测试就能为小于ψm的整数 n提供确定型素性证明(准确判断n 是合数还是素数),这就是说, Miller测试 对于这样的整数不再是概率的而是确定的素性测试. (我们把这种方法简称为 ψm方法,以便在个人主页中文版其它地方引用此方法)
1980年, Pomerance 、Selfridge
和 Wagstaff 对于 1≤m
≤4定出了ψm 的准确值:
Ψ1 = 2047= 23 * 89,
Ψ2 = 1373653=829 * 1657,
Ψ3 = 25326001=2251
* 11251,
Ψ4 =
3215031751=151* 751* 28351.
接着,1993年,
Jaeschke 用二次剩余特征为主要工具对于 5≤m
≤8定出了ψm 的准确值, 并给出ψ9、ψ10和ψ11的上界：
Ψ5 =
2152302898747=6763* 10627* 29947,
Ψ6 = 3474749660383=1303*
16927* 157543,
Ψ7 =Ψ8 =341550071728321=10670053
* 32010157,
ψ9 ≤ M9 = 41234 31613 57056 89041 (20 位) =
4540612081 * 9081224161,
ψ10 ≤M10 = 155 33605 66073 14320 55410 02401 (28 位)
= 22754930352733
* 68264791058197,
ψ11 ≤M11 = 5689
71935 26942 02437 03269 72321 (29 位)
=
137716125329053 * 413148375987157.
(我们回顾一下ψm方法 是从 Fermat 测试 发展过来的:
Fermat测试 ==>概素数(probable
prime, prp(b)), 伪素数(pseudoprime, psp(b)) ==> Carmichal 数 ==> Miller测试 ==> 强概素数 (strong probable
prime, sprp(b)), 强伪素数(strong pseudoprime, spsp(b)) ==>ψm ==> ψm方法, 我们不妨称这条链为
Fermat - ψm 链 . )
2020-11-162022-1-18