偽素數大家庭

引子

在《從費馬小定理談起》一文中,為大家介紹了偽素數 (Pseudoprime) 的由來。其實偽素數何止一種,自費馬偽素數 (Fermat Pseudoprime) 出現以後,數學家漸漸喜歡把符合一些素數性質的逆命題的合數 (Composite Number) 稱為偽素數 (Pseudoprime),我們便出現了很多不同的偽素數。

 

歐拉 - 雅可比偽素數

歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime) 或簡稱歐拉偽素數 (Euler Pseudoprime) 簡記 ejpsp(a)。這是由歐拉判別式 (Euler's Criterion) 開始,對任何奇素數,我們有:

其中上式中的 (a/p) 為勒讓德符號 (Legendre Symbol) 。所謂勒讓德符號,可看《勒讓德符號》。

 

例:取 a = 4,p = 23,我們得知 411 = 1 (mod 23),另一方面 (4/23) = (2*2/23) = 1,故成立。當然這一例不算得什麼證明。

若有一合數 a,使 (a,n) = 1 ,即 a 與 n 互素,且符合下式,式中的 (a/n) 為雅可比符號 (Jacobi Symbol):

對此我們稱 n 為以 a 為底的歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime to Base a) ,簡記 ejpsp(a)。

那雅可比符號又是什麼?

若 m 可分解成 m = p1a1 * p2a2 * ...... * pkak,則有 (n/m) = (n/p1)a1 * (n/p2)a2 * ...... * (n/pk)ak,式中右方的括號為勒讓德符號。

若考慮所有與 n 互素的底 a,我們發現沒有一個奇合數可使之成為以所有 a 為底的歐拉 - 雅可比偽素數。

以 2 為底的歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime to Base 2,簡記 ejpsp(2)) 有:561, 1105, 1729, 1905, 2047, 2465, ...... (OEIS A047713)

以 3 為底的歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime to Base 3,簡記 ejpsp(3)) 有:121, 703, 1729, 1891, 2821, 3281, 7381, ...... (OEIS A048950)

 

強偽素數

強偽素數 (Strong Pseudoprime) ,我們簡記 spsp(a)。

以 a 為底的強偽素數 (Strong Pseudoprime to Base a) 是指一奇合數 n,其中 n-1 = d*2s (d 為奇數),滿足:

,r = 0,1,2, ...... , s-1

以 2 為底的強偽素數 (Strong Pseudoprime to Base 2) 有:2047, 3277, 4033, 4681, ...... (OEIS A001262)

強偽素數亦是一些素數判別方法,如魯賓 - 米勒強偽素數測試 (Rabin - Miller Strong Pseudoprime Test) 、 巴利爾 - PSW 素性測試 (Baillie - PSW Primality Test) 等。

 

參考文獻及網址

Guy, R. K. "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

Weisstein, E. W. "Euler-Jacobi Pseudoprime." From MathWorld. http://mathworld.wolfram.com/Euler-JacobiPseudoprime.html.

Weisstein, E. W. "Euler Pseudoprime." From MathWorld. http://mathworld.wolfram.com/EulerPseudoprime.html.

Weisstein, E. W. "Pseudoprime." From MathWorld. http://mathworld.wolfram.com/Pseudoprime.html.

Weisstein, E. W. "Strong Pseudoprime." From MathWorld. http://mathworld.wolfram.com/StrongPseudoprime.html.