廣義費馬數

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

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

　

　

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

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

顯然，F_n(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，即 1372930¹³¹⁰⁷²+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.