廣義費馬數

美國數學家、電腦學家、物理學家克蘭特爾 (Richard E. Crandall, 1947- )

(照片取自 http://people.reed.edu/~crandall/)

 

 

很早以前數學家已發現研究費馬數 (Fermat Number) 的局限,為了更有效的利用這素數類別,數學家轉向研究廣義費馬數 (Generalized Fermat Number):

Fn(x) = x^(2n)+1, n = 1、2、3、 ......,或記 GF (n,x),我們稱其為以 x 為底的廣義費馬數。

顯然,Fn(2) 是我們先前詳細介紹的費馬數

 

早在十七世紀,對廣義費馬數的素性研究已開展,然而由於計算方法的局限,研究到了某一大數值上便停滯不前。到了二十世紀 50 至 70 年代,大型電子計算機的發展使研究上取得突破,但方法依然源用十九世紀的分解法。到了 80 年代,尋找素數的方法有所改為,引進離散變換 (Discrete Transformation) 和 快速傅立葉變換 (Fast Fourier Transformation, FFT) 使搜索範圍大大提昇,當時已可攀登一萬數位,甚至十萬數位的素數 。

 

在 1994年,克蘭特爾 (Richard E. Crandall, 1947- ) 和費根 (B. Fagin) 發明離散加權變換 (Discrete Weighted Transformation),使尋找廣義費馬素數的速度提升一倍。到了 1998年,加洛特 (Yves Gallot) 發現離散加權變換的多項式運算特性,並把之推廣至非二底的變換。以此為基礎,卡莫迪 (Phil Carmody)、費爾 (B. Frey) 創製了廣義費馬素數的篩選程式,使搜索範圍登上八十萬數位。

 

現在新世紀伊始,在密碼學的發展需求下 (詳見另文《RSA公鑰密碼淺介》) ,尋找大素數依然存在很大的空間,更多更大的廣義費馬素數等待人們找尋。雖云已知最大的廣義費馬素數為 n=17 和 x= 1372930,即 1372930131072+1 已是天文數字,但我們是不會因此卻步的。順帶一提,此數是在 2003 年九月二十二日由侯亞 (Danial Heuer) 發現,共有 804474 個數位。

 

參考文獻及網址:

Caldwell, C. K. "The Top Twenty: Generalized Fermat." http://primes.utm.edu/top20/page.php?id=12.

Weisstein, E. W. "Generalized Fermat Number." From MathWorld. http://mathworld.wolfram.com/GeneralizedFermatNumber.html.