廣義費馬數
很早以前數學家已發現研究費馬數 (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 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 個數位。
下表列出現在最大的十個廣義費馬素數的資料,欲知更多可參考大素數表,或到 Prime Page。
廣義費馬素數 |
數位 |
發現者 |
年份 |
24518262144 + 1 |
1150678 |
史葛 (Stephen Scott) |
2008 |
1372930131072 + 1 |
804474 |
侯亞 (Danial Heuer) |
2003 |
1361244131072 + 1 |
803988 |
侯亞 (Danial Heuer) |
2004 |
1176694131072 + 1 |
795695 |
侯亞 (Danial Heuer) |
2003 |
572186131072 + 1 |
754652 |
加洛特 (Yves Gallot) |
2004 |
130816131072 + 1 |
670651 |
安祖 (Michael Angel) |
2003 |
62722131072 + 1 |
628808 |
安祖 (Michael Angel) |
2003 |
811606848 + 1 |
483712 |
Tadashi Taura |
2007 |
1950221265536 + 1 |
477763 |
安祖 (Michael Angel) |
2005 |
1768482865536 + 1 |
474949 |
不清楚 |
2007 |
個個如此巨大,真佩服發現它們的人。
參考文獻及網址:
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.