主题
Search

Baillie-PSW 素性测试

Baillie 和 Wagstaff (1980) 以及 Pomerance 等人 (1980, Pomerance 1984) 提出了一个基于强伪素数和Lucas 伪素数组合的测试（或者说是一组相关的测试）。 有许多变体，以下算法给出了其中一个特定版本 (Pomerance 1984)

1. 对 n 执行以 2 为底的强伪素数测试。 如果此测试失败，则声明 n 为合数并停止。 如果此测试成功，则 n 很可能是素数。 继续步骤 2。

2. 在序列 5, -7, 9, -11, 13, ..., 中，找到第一个数字 D，使得 Jacobi 符号 (D/n)=-1。 然后对 n 执行判别式为 D 的 Lucas 伪素数测试。 如果此测试失败，则声明 n 为合数。 如果成功，则 n 很可能是一个素数。

Pomerance (1984) 最初悬赏 30 美元以奖励发现通过此测试的合数，但后来悬赏金额提高到 620 美元 (Guy 1994, p. 28)。

目前还没有已知通过此测试的合数示例，截至 2009 年 6 月 13 日，Jeff Gilchrist 已经确认，在 10^(17) 以内没有 Baillie-PSW 伪素数。 然而，椭圆曲线素性证明程序PRIMO使用此测试检查所有中间可能的素数，如果其中任何一个是合数，则认证必然会失败。 基于三年的使用中未发生这种情况的事实，PRIMO作者 M. Martin 估计，没有小于约 10000 位数的合数可以欺骗此测试。

另请参阅

Lucas 伪素数, 强伪素数

使用 Wolfram|Alpha 探索

参考文献

Arnault, F. Ph.D. thesis, p. 72.Baillie, R. and Wagstaff, S. W. Jr. "Lucas Pseudoprimes." Math. Comput. 35, 1391-1417, 1980. http://mpqs.free.fr/LucasPseudoprimes.pdf.Gilchrist, J. "Pseudoprime Enumeration with Probabilistic Primality Tests (Fermat Base 2, Baillie-PSW)." http://gilchrist.ca/jeff/factoring/pseudoprimes.html.Guy, R. K. "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.Martin, M. "Re: Baillie-PSW - Which variant is correct?" http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&safe=off&selm=3FFF275C.2C6B5185%40ellipsa.no.sp.am.net.Martin, M. "PRIMO--Primality Proving." http://www.ellipsa.net.Nicely, T. R. "The Baillie-PSW Primality Test." http://www.trnicely.net/misc/bpsw.html.Pomerance, C. "Are There Counterexamples to the Baillie-PSW Primality Test?" 1984. http://www.pseudoprime.com/dopo.pdf.Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to 25·10^9." Math. Comput. 35, 1003-1026, 1980. http://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.

在 Wolfram|Alpha 中被引用

Baillie-PSW 素性测试

引用为

Weisstein, Eric W. "Baillie-PSW 素性测试。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Baillie-PSWPrimalityTest.html

主题分类