強偽素數

以基數 為底的強偽素數是一個 奇 合數 且滿足 （其中 為 奇數），滿足以下條件之一：

(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）。