标签：#偽素數

可能質數

在數論上，可能質數（probable prime，縮寫為PRP）指的是一個滿足所有質數都會滿足、但多數合成數都不會滿足的特定條件的數。不同的可能質數會有不同的條件。雖說一些可能質數會是合成數（也就所謂的偽質數），但一般會透過條件的選取讓這種狀況變得少見。 像例如一個基於費馬小定理的費馬合成數測試，其原理如次：在給定一個的狀況下，選取一個不是的倍數的數（一般會在1 的範圍中選取），然後計算a^{n-1}\pmod{n}。若結果不是1，則是…