偽素數

下載 Wolfram 筆記本

偽素數是一個合數，它通過了一個或一系列對於大多數合數都失敗的測試。不幸的是，一些作者去掉了“合數”的要求，將任何透過指定測試的數稱為偽素數，即使它是素數。Pomerance、Selfridge 和 Wagstaff (1980) 將“偽素數”的使用限制為奇合數。

不加限定地使用“偽素數”指的是費馬偽素數，即一個合數，但它仍然滿足費馬小定理對於某些基或一組基。

卡邁克爾數是對於每個基都是費馬偽素數的奇合數；它們有時被稱為絕對偽素數。

下表給出了以 2 為底的 Poulet 數 psp(2)、尤拉-雅可比偽素數 ejpsp(2) 和強偽素數 spsp(2) 的數量，以及小於 10 的前幾個冪的卡邁克爾數 CN（Guy 1994）。下表擴充套件了 Guy 的表格，加入了 Pinch 的結果，他計算了高達的偽素數數量。

	psp(2)	ejpsp(2)	spsp(2)	CN
Sloane	A055550	A055551	A055552	A055553
Sloane 計數	A001567	A047713	A001262	A002997
	0	0	0	0
	0	0	0	0
	3	1	0	1
	22	12	5	7
	78	36	16	16
	245	114	46	43
	750	375	162	105
	2057	1071	488	255
	5597	2939	1282	646
	14884	7706	3291	1547
	38975	20417	8607	3605
	101629	53332	22407	8241
	264239	124882	58892	19279

另請參閱

卡邁克爾數, 橢圓偽素數, 尤拉偽素數, 尤拉-雅可比偽素數, 超強 Lucas 偽素數, 費馬偽素數, 斐波那契偽素數, 弗羅貝尼烏斯偽素數, 盧卡斯偽素數, 佩蘭偽素數, Poulet 數, 可能素數, 索默-盧卡斯偽素數, 強橢圓偽素數, 強弗羅貝尼烏斯偽素數, 強盧卡斯偽素數, 強偽素數

使用探索

更多嘗試

參考文獻

Caldwell, C. K. "素數連結++." http://primes.utm.edu/links/theory/finding_and_proving/probable_primality/.Grantham, J. "弗羅貝尼烏斯偽素數." http://www.clark.net/pub/grantham/pseudo/pseudo1.ps.Grantham, J. "偽素數/可能素數." http://www.clark.net/pub/grantham/pseudo/.Guy, R. K. "偽素數。尤拉偽素數。強偽素數。" §A12 in 數論中的未解決問題，第二版。 New York: Springer-Verlag, pp. 27-30, 1994.Pinch, R. G. E. "高達

的偽素數." ftp://ftp.dpmms.cam.ac.uk/pub/PSP/.Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "高達

的偽素數." Math. Comput. 35, 1003-1026, 1980. http://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.Sloane, N. J. A. 序列 A001262, A001567/M5441, A002997/M5462, A047713, A055550, A055551, A055552, 和 A055553 in "整數序列線上百科全書."

在中被引用

請引用為

Weisstein, Eric W. "偽素數。" 來自 —— 資源。 https://mathworld.tw/Pseudoprime.html

主題分類