[Zhang and Tang 2003] (with Min Tang) Finding strong pseudoprimes to several bases. II, Mathematics of Computation (ISSN: 0025-5718), 72:244 (2003), 2085-2097. ABSTRACT

代表作 [Zhang and Tang 2003] 内容简介: 提出找C₃ -数的快速算法, 把Jaeschke 1993年的ψ₉的20位上界和我们2001年的ψ₁₀ 和ψ₁₁的22位数上界降到19位; 据理提出 ψ₉、ψ₁₀ 和ψ₁₁ 的准确值的猜想(猜想1).

该文§2用四次剩余特征为主要工具找到157个小于10²⁴通过前5个素数基2,3,5,7,11 的 k4/3-强伪素数, 其中只有3个是spsp(13). 这157个强伪素数被Maple V.2的素性测定误认为是素数, 其中最小的为16位数, 比Arnault构造的例子小得多。这些例子促进了软件包Maple V.2的更新优化, 加强了素性测定的条件. 这个软件包发展到Maple V.8时, 已很难找到把合数误判为素数的例子了. 该节还找到30个小于10²⁴通过前5个素数基 的K5/2-强伪素数, 其中只有1个是spsp(13).

该文§3用三次剩余特征为主要工具找到44个小于10²⁴通过前6个素数基2,3,5,7,11,13 的K3/2-强伪素数强伪素数, 其中只有2个是spsp(17)；还找到94个小于10²⁴通过前6个素数基的K6-强伪素数, 其中只有7个是spsp(17).

该文§4提出寻找C₃ -数的快速算法, 并找到了所有(共110个) 小于10²⁰通过前5个素数基的C₃ -强伪素数， 这些强伪素数和该文§2中的157个强伪素数一样被Maple V.2的素性测定误认为是素数。这110个强伪素数中有一个19位数是通过前11个素数基的强伪素数, 这样把Jaeschke 于1993年确定的ψ₉的20位数上界和代表作 [Zhang 2001a ] 确定的ψ₁₀ 和ψ₁₁的22位数上界降到了19位:

ψ₉ ≤ψ₁₀ ≤ψ₁₁ ≤ N₉=N₁₀=N₁₁=3825 12305 65464 13051

= 149491 · 747451 · 34233211.

该文§4还把寻找C₃ -数的算法与Arnault 、Bleichenbacher、Jaeschke 和Pinch 的方法进行了比较，详见该节注解5、6、7.

该文§5, 由以上3 节和代表作 [Zhang 2001] 中的数据得到提示, 给出令人信服的理由 (不同形式的强伪素数有不同的出错概率) 让人们相信如下

猜想1. ψ₉ =ψ₁₀ =ψ₁₁ = N₉=N₁₀=N₁₁= 3825 12305 65464 13051.

Devenport 曾猜测通过前k个素数基的强伪素数必大于10^2k 。Bleichenbacher 构造了一个41位合数, 它是通过前21个素数基的强伪素数, 因而是Devenport 猜想的反例. 我们的这个通过前11个素数基的19位强伪素数是Devenport 猜想的一个比Bleichenbacher 的 41位数更好的反例, 因为

11/19 = 0.578 … > 0.512 … = 21/41.

这个19位数表明像软件包Axiom 2.0 那样对2k位的数选用k个素数基来进行Miller 测试 是不够安全的.

猜想1 已于2014年被Yupeng Jiang 和 Yingpu Deng 证得 [Math. Comp. 83:290 (2014), 2915–2924. ]

 
2022-1-28