首先我們給出偽素數的定義。

在a＝2時滿足Fermat小定理逆定理表示式的非素數n，稱之為偽素數，比如341。同時對於此定義我們可以進行引申，即對於任意a，滿足式子成立的非質數我們稱為基a的偽素數，比如63是基8的偽素數。

對於偽素數而言，其滿足基的連乘性和可逆性，並且我們可以證明偽素數是無窮多的。

由於偽素數的存在，我們為了尋找大素數，第一想法是去透過更換a的值來進行反覆驗證，也就得到了Fermat素性檢驗，但是這種方法是存在缺陷的，因為存在Carmichael數，用Fermat素性檢驗無法檢測，並且Carmichael數的數量是無窮多的。

接下來我們可以將偽素數的定義進行加強，即對基於Jacobi方式依然無法判定的偽素數，我們稱之為基a的Euler偽素數，其個數也是無窮的。

類似Fermat素性檢驗的思想，我們任意選取a，去驗證是二次剩餘與Jacobi計算式是否相同，避免了固定a後，對基a的Euler偽素數無法檢測這一問題，我們稱這種檢測方法為Solovay-Stassen素性檢驗。但是其演算法複雜度略高。

我們再將偽素數的定義增強，基於中國剩餘定理去計算一個s個式子的方程組（其中s滿足2∧s || n-1），得到的解中的合球我們稱為基a的強偽素數，強偽素數的個數依然是無窮的，其中對奇合數n，其為基a的強偽素數的機率≤25％

還是類似前兩種素性檢驗的方法，我們任意選取a進行迴圈計算，得到了Miller-Rabin素性檢驗法，特別的，由於Miller-Rabin素性檢驗法中可以採用模平方演算法，可以降低其演算法複雜度。

當下，最快的素性檢驗演算法是APRCL演算法，最有使用價值的是ECPP演算法，但是都不能在多項式時間內完成。2002年印度幾位數學家給出了AKS素性檢驗，但是由於常數過大，目前並無大的使用價值。

在密碼學的角度來看，素性檢驗的主要用途在於需要生成大素數的RSA公鑰金鑰體制，同時也是大數分解數學難題中不可缺少的一部分。