代表作 [Zhang 2002] 内容简介
[Zhang 2002] A one-parameter quadratic-base
version of the Baillie-PSW probable prime test, Mathematics of Computation ,71:240
(2002),
1699-1734. ABSTRACT
内容简介：定义单参数二次基伪素数和强伪素数(定义2.1), 给出基计数函数的计算公式(定理1),证明了基计数函数值的上界为1/2和1/8(定理2); 基于单参数二次基(强)伪素数提出BPSW测试的单参数二次基版本, 简称单参数二次基测试(OPQBT).
————————————————
定义2.2：单参数二次基测试(OPQBT )————————————————————
给定一个正奇数 n ≥ 5.
第一步： (非完全平方预测试)
用 Newton 方法测试 n 是否完全平方. 如果n 是完全平方, 宣布 n 是合数, 终止程序.
第二步： (第一个概素性子测试) 随机取整数 u：0 ≤ u < n, u 不等于 ± 2 mod n ， 且 gcd(u2 – 4, n)=1. 令 ε = ((u2 –4)/n) in {1, –1}.
如果n 不是 sprp(Tu) , 宣布 n 是合数, 终止程序.
第三步： (第二个概素性子测试) 随机取整数 v：0 ≤
v < n, v 不等于
± 2 mod n ， 且 ((v2 – 4)/n) = – ε . 如果n 不是 sprp(Tv) , 宣布 n 是合数, 终止程序.
如果n 在上述三步中没有被宣布是合数，宣布 n 是概素数, 即 通过了OPQBT 的一次迭代.
—————————————————————————————————————————————————————
给出了OPQBT的出错概率计算公式 (定理3)， 根据n的素因子个数给出了出错概率的上界(定理4)，给出了 OPQBT运行时间(定理5)
通过算法比较(§8), 得出结论: OPQBT的出错概率和运行时间的综合性能优于RQFT 和Frobenius测试.
该文结束语(§9)阐明: 定理3，4和5 回答了为什么BPSW测试比分开来考虑单个子测试安全可靠得多的问题; 定理3和4回答了为什么很难找到BPSW测试的反例的问题. 结束语最后指出, OPQBT 有清楚的有限群(域)结构和漂亮的对称性, 因此可以给出明确的基计数函数公式和出错概率, 于是可以仔细研究这些函数的上界. 由于BPSW测试的原始版本和Grantham的RQFT都没有明确的出错概率计算公式, OPQBT 将是能够通向确定型素性测定算法的那些概率素性测定算法中的最佳候选者之一.
2022-1-28