主題
Search

米勒素性檢驗


如果一個數未能透過以某個基數 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 素性檢驗, 合數問題, 強偽素數

使用 探索

參考文獻

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."

在 中被引用

米勒素性檢驗

請按如下方式引用

Weisstein, Eric W. “米勒素性檢驗。” 來自 -- 資源。 https://mathworld.tw/MillersPrimalityTest.html

主題分類