主题
Search

米勒素性检验

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

如果一个数未能通过以某个基数 a 的米勒素性检验，则它不是素数。如果该数通过了检验，它可能是素数。一个通过米勒检验的合数被称为以基数 a 的强伪素数。如果一个数 n 未能通过检验，则它被称为合数性的见证。如果 n 是一个奇正合数，那么 n 对于至多 (n-1)/4 个基数 -1<=a<=1 (Long 1995) 通过米勒检验。对于强伪素数，没有类似于 卡迈克尔数 的概念。

对于基数 2、3、5 和 7 而言（因此会未能通过基于这些基数的检验）最小的强伪素数是 3215031751、118670087467、307768373641、315962312077、... (OEIS A074773; Jaeschke 1993)。

米勒证明了，如果 黎曼猜想 为真，则任何合数 n 都有一个小于 70(lnn)^2 的见证。

另请参阅

Adleman-Pomerance-Rumely 素性检验, 合数问题, 强伪素数

使用 Wolfram|Alpha 探索

参考文献

Caldwell, C. "Finding Primes & Proving Primality. 2.3: Strong Probable-Primality and a Practical Test." http://primes.utm.edu/prove/prove2_3.html.Jaeschke, G. "On Strong Pseudoprimes to Several Bases." Math. Comput. 61, 915-926, 1993.Long, C. T. Th. 4.21 in Elementary Introduction to Number Theory, 3rd ed. Prospect Heights, IL: Waveland Press, 1995.Miller, G. "Riemann's Hypothesis and Tests for Primality." J. Comput. System Sci. 13, 300-317, 1976.Sloane, N. J. A. Sequence A074773 in "The On-Line Encyclopedia of Integer Sequences."

在 Wolfram|Alpha 中被引用

米勒素性检验

请按如下方式引用

Weisstein, Eric W. “米勒素性检验。” 来自 MathWorld-- Wolfram Web 资源。 https://mathworld.net.cn/MillersPrimalityTest.html

主题分类