强伪素数

以基数 为底的强伪素数是一个 奇 合数 且满足 （其中 为 奇数），满足以下条件之一：

(1)

或

(2)

对于某些 , 1, ..., （Riesel 1994, p. 91）。 请注意，Guy（1994, p. 27）将强伪素数的定义限制为仅满足条件 (1) 的那些。

这个定义的动机是费马伪素数 以基数 为底满足

(3)

但是由于 是 奇数，它可以写成 ，并且

(4)

如果 是 素数，它必须 整除 至少一个 因子，但不能同时 整除 两者，因为它会 整除 它们的差

(5)

因此，

(6)

所以写成 以得到

(7)

如果 整除 这些 因子 中的恰好一个，但它是 合数，那么它是一个强伪素数。一个 合数 对于小于它自身的所有基数中的至多 1/4 是强伪素数（Monier 1980，Rabin 1980）。强伪素数为 Miller 素性测试 和 Rabin-Miller 强伪素性测试 提供了基础。

以基数 为底的强伪素数也是以基数 为底的 欧拉伪素数 （Pomerance 等人，1980）。强伪素数包括一些 欧拉伪素数、费马伪素数 和 卡迈克尔数。

下表列出了对于一些小基数的前几个伪素数。

	OEIS	-强伪素数
2	A001262	2047, 3277, 4033, 4681, 8321, ...
3	A020229	121, 703, 1891, 3281, 8401, 8911, ...
4	A020230	341, 1387, 2047, 3277, 4033, 4371, ...
5	A020231	781, 1541, 5461, 5611, 7813, ...
6	A020232	217, 481, 1111, 1261, 2701, ...
7	A020233	25, 325, 703, 2101, 2353, 4525, ...
8	A020234	9, 65, 481, 511, 1417, 2047, ...
9	A020235	91, 121, 671, 703, 1541, 1729, ...

小于 , , ... 的强 2-伪素数的数量分别为 0、5、16、46、162、...（OEIS A055552）。请注意，Guy（1994, p. 27）的定义仅给出了子集 2047、4681、15841、42799、52633、90751、...，其计数与 Guy 表中的计数不一致。

对于 =2、3、5 的强 k-伪素数测试正确识别了小于 的所有 素数，仅有 13 个例外，如果添加 7，则小于 的唯一例外是 3215031751。Jaeschke (1993) 表明，对于小于 的基数 2、3 和 5，只有 101 个强伪素数，如果添加 7，则有 9 个，如果添加 11，则没有。此外，基数 2、13、23 和 1662803 在高达 的范围内没有例外。

如果 是 合数，那么存在一个基数，使得 不是强伪素数。因此，没有“强卡迈克尔数”。设 表示以所有前 k 个 素数 为基数的最小强伪素数（即，对于基数小于或等于第 k 个素数 的 Rabin-Miller 强伪素性测试 失败的最小 奇数）。Jaeschke (1993) 计算了 从 到 8，并给出了 到 11 的上限。

			(8)
			(9)
			(10)
			(11)
			(12)
			(13)
			(14)
			(15)
			(16)
			(17)
			(18)

（OEIS A014233），其中 , , 和 的界限由 Zhang 和 Tang（2003）确定。一个七步测试，利用这些结果的旧界限（Riesel 1994），允许测试所有小于 的数字。

张 (2001, 2002, 2005, 2006, 2007) 推测

			(19)
			(20)
			(21)
			(22)
			(23)
			(24)
			(25)
			(26)
			(27)
			(28)
			(29)
			(30)

Baillie-PSW 素性测试 是一种基于强伪素数和 Lucas 伪素数 组合的测试，由 Pomerance 等人提出。（Pomerance 等人，1980；Pomerance，1984）。