伪素数

下载 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 数, 可能素数, 索默-卢卡斯伪素数, 强椭圆伪素数, 强弗罗贝尼乌斯伪素数, 强卢卡斯伪素数, 强伪素数

使用 Wolfram|Alpha 探索

更多尝试

参考文献

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 "整数序列在线百科全书."

在 Wolfram|Alpha 中被引用

请引用为

Weisstein, Eric W. "伪素数。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/Pseudoprime.html

主题分类