擬素數

一般來說判斷一個數是素數是不容易的（這裡並不是說它是NPC的，2002年印度數學家給出的ASK素性檢驗已經證明了它是P類問題）。但要判定一個數是合數卻相對容易，因為此時只需找出一個使得素數滿足，但它不滿足的性質即可。所以原始的素性檢驗思想就是檢驗某個素數的通性，不滿足的即為合數，如果滿足而它又是合數則稱為關於此種性質的擬素數（quasi prime number）。

基本介紹

• 中文名：擬素數
• 外文名：擬素數
• 英文：uasi prime number
• 原始的：素性檢驗思想就是檢驗

定義

常用的擬素數有以下幾種：

1、擬素數（Fermat）：設是奇合數，如果整數 使得同餘式：

成立，則叫做基於的擬素數。

2、Euler擬素數：若是正的奇合數，如果整數與互素，且滿足條件：

則稱為基於的Euler擬素數。（其中表示關於的Jacobi符號）

3、強擬素數：設為正的奇合數，且滿足,其中為奇數。與互素，若有以下關係成立：

或者存在一個整數使得：

則叫做基於的強擬素數。

性質

定理1：存在無窮多個擬素數，Euler擬素數和強擬素數。

證明概要：只需證明如果為擬素數，則為強擬素數即可。

定理2：如果一個數是基於的Euler擬素數，那么它也是基於的擬素數。

證明：顯然。

定理3：如果一個數是基於強擬素數，那么它也是基於的Euler擬素數。

證明：令為基於的強擬素數，則其可分解為（允許重複）。定義使得並且假定。由為強擬素數知，存在k使得對任意均滿足（k即為關於的指數所包含的因子2的個數）。因此有，令表示的個數，那么有

所以或取決於是奇數還是偶數。所以≡-1或1(mod )取決於是奇還是偶。

另一方面，若那么，若則有。

所以，因此也取決於的奇偶性。所以，即也為基於的Euler擬素數。

算法

通過如上三種擬素數的定義，可以直接導出三種素性檢驗的方法，分別為：Fermat素性檢驗、Solovay-Stassen素性檢驗（基於Euler擬素數）、Miller-Rabin素性檢驗（基於強擬素數）。可以證明前兩者檢測出n為合數的機率不小於50%，後者檢測出來的機率不小於75%。