a3f
Fermat数
$F_n=2^{2^n}+1$ を Fermat数、$F_n$ が素数のとき $F_n$ を Fermat素数と呼ぶ。 $F_0=3,$ $F_1=5,$ $F_2=17,$ $F_3=257,$ $F_4=65537$ はすべて素数である。 1640年に Fermat は、$F_n$ はすべて素数であろうと宣言した。しかし、Euler は 1732年に \[F_5=641\times6700417\] と分解できることを計算した。（Fermat が言明した問題のうち、Fermat数に関するもの以外はすべて正しいと確認されている。）
Fermat の小定理を用いると、$F_n$ を割る素数は $k \cdot 2^{n+1}+1$ という形をしていることが示される。Euler は $F_5$ を素数 193,257,449,577,641 で５回割り算をして $F_5$ の素因子 641 を見つけたのである。その後、Lucas は 1877年に $F_n$ を割る素数は $k \cdot 2^{n+2}+1$ と言う形であることを証明した。1880年に Landry はこの事を使って \[F_6=274177\times67280421310721\] と分解できることを計算した。
Pépin は 1877年に $F_n$ が素数か否か判定する効率的な次の Pépinの判定法を発明した。
$F_n$ が素数であるための必要十分条件は、 $3^{(F_n-1)/2} \equiv -1 \pmod{F_n}$ となることである。
$F_7$が合成数であることは 1905年に Pépin の判定法を用いて証明された。
2017年現在では、$5 \leq n \leq 32$ に対して $F_n$ が合成数であることが分かっている。 $F_{20}, F_{24}$ は合成数だが素因子は一つも見つかっていない。($F_{14}, F_{22}$については長い間素因子は一つも見つかっていなかったが、いずれも2010年に素因子が見つかった)。 $F_{24}$ は Pépinの判定法を実行するのに1999年当時の計算機で約半年かかった。 $F_{33}$ は素数か否か分かっていない。大型計算機で Pépin の判定法を実行しようとしても、時間的に現在のところ不可能である。
Morrison と Brillhart は 1970年に連分数展開法を用いて
\[F_7= 59649589127497217 \times 5704689200685129054721\]
と素因子分解できることを計算した。
Brent と Pollard は 1980年に ρ法を用いて
\[F_8= 1238926361552897 \times p_{62}\]
と素因子分解できることを計算した。ここで $p_n$ は $n$桁の素数を表すものとする。
Brent は 1988年に楕円曲線法を用いて \[F_{11}= 319489 \times 974849 \times 167988556341760475137 \times\] \[3560841906445833920513 \times p_{564}\] と素因子分解できることを計算した。
Lenstra と Manasse は 1989年に NFS法を用いて \[\begin{eqnarray*} F_9 &=& 2424833 \times p_{49} \times p_{99}, \\ p_{49} &=& \small{7455602825647884208337395736200454918783366342657} \end{eqnarray*}\] と素因子分解できることを計算した。
楕円曲線法と NFS法は共に高速な素因数分解の方法であるが両者は分解できる数の傾向が違う。楕円曲線法は見つける素因子の大きさで大体実行時間が決まるのに対し、 NFS法は分解しようとする合成数の大きさで大体実行時間が決まる。
Brent は 1995年に楕円曲線法を用いて \[\begin{eqnarray*} F_{10} &=& 45592577 \times 6487031809 \times p_{40} \times p_{252}, \\ p_{40} &=& 4659775785220018543264560743076778192897 \end{eqnarray*}\] と素因子分解できることを計算した。