一、定義
一般來說判斷一個數是素數是不容易的（這裡並不是說它是NP的，2002年印度數學家給出的ASK素性檢驗已經證明了它是P類問題）。但要判定一個數是合數卻相對容易，因為此時只需找出一個使得素數滿足，但它不滿足的性質即可。所以原始的素性檢驗思想就是檢驗某個素數的通性，不滿足的即為合數，如果滿足而它又是合數則稱為關於此種性質的擬素數（quasi prime number）。常用的擬素數有以下幾種：
1、擬素數（Fermat）：設n是奇合數，如果整數b,(b,n)=1使得同餘式：
b^n-1≡1(mod n)
成立，則n叫做基於b的擬素數。
2、Euler擬素數：若n是正的奇合數，若果整數b與n互素，且滿足條件：
b^(n-1)/2≡〔b/n〕(mod n)
則稱n為基於b的Euler擬素數。（〔b/n〕表示b關於n的Jacobi符號）
3、強擬素數：設n為正的奇合數，且滿足n-1=t*2^s,其中t奇數。b與n互素，若有以下關係成立：
b^t≡1(mod n)
或者存在一個整數r,0≤r<s使得：
b^(t*2^r)≡-1(mod n)
則n叫做基於b的強擬素數。
二、性質
定理1：存在無窮多個擬素數，Euler擬素數和強擬素數。證明概要：只需證明如果n為擬素數，則2^n-1為強擬素數即可。
定理2：若果一個數n是基於a的Euler擬素數，那么它也是基於a的擬素數。
證明：顯然。
定理3：若果一個數n是基於a強擬素數，那么它也是基於a的Euler擬素數。
證明：令n為基於a的強擬素數，則其可分解為p1p2...pt（允許重複）。定義kj使得2^kj||pj-1並且假定k1≤k2≤···≤kt。由n為強擬素數知，存在k使得2^k||ord_a(p^d)對任意p^d||n均滿足（k即為a關於n的指數所包含的因子2的個數）。因此有k≤k1，令i表示kj=k的個數，那么有n≡p1p2...pt≡(2^k+1)^i(mod 2^(k+1))
所以2^k||n-1或2^(k+1)||n-1取決於i是奇數還是偶數。所以a^(n-1)/2≡-1或1（mod n)取決於i是奇還是偶。
另一方面，若kj=k那么〔a/pj〕=(2^(pj-1)/2)mod pj=-1，若kj>k則有〔a/pj〕=(2^(pj-1)/2)mod pj=1。
所以〔a/n〕=(-1)^i，因此也取決於i的奇偶性。所以a^(n-1)/2≡〔a/n〕(mod n)，即n也為基於a的Euler擬素數。
