フェルマーの小定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

数論において、フェルマーの小定理(フェルマーのしょうていり、Fermat's little theorem)は素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。

概要[編集]

p を素数とし、ap の倍数でない整数ap互いに素)とするときに、

ap−1 ≡ 1 (mod p)

すなわち、ap − 1 乗を p で割った余りは 1 であるというもの。有名なフェルマーの最終定理と区別するためにあえて「小」定理と称されている。

この定理はピエール・ド・フェルマーの名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって証明が与えられていたことが確認されているわけではない。この定理に対する証明はゴットフリート・ライプニッツによって初めて与えられた。

証明[編集]

証明(1)[編集]

証明(2)[編集]

オイラーの定理[編集]

後になってレオンハルト・オイラーはこの定理を拡張し、an互いに素な整数とすると、

aφ(n) ≡ 1 (mod n)

が成り立つことを示した。ここで、φ(n) は n 未満の n と互いに素な自然数の個数を表し、オイラー関数 と呼ばれる。

特に n が素数のときは、φ(n) = n − 1 より、フェルマーの小定理に一致する。

カーマイケルの定理[編集]

m = φ(n) とすれば、am ≡ 1 (mod n) が n と互いに素な全ての a に対して成り立つが、φ(n) はこの性質を満たす m の最小の数とは限らない。カーマイケルの定理はオイラーの定理を精緻化したもので、最小の m を与える。

カーマイケル関数英語版 λ(n) を以下のように再帰的に定義する。

n = 2e なら、

\lambda (2^e )=\begin{cases}
1 &(e=1)\\
2 &(e=2)\\
2^{e-2} &(e \ge 3)
\end{cases}

n が奇素数 p を用いて n = pe と書けるなら、

λ(pe) = pe−1(p−1)

np1e1 ... pkek素因数分解できるなら、

λ(p1e1 ... pkek) = lcm(λ(p1e1), ... ,λ(pkek))

ここで lcm は最小公倍数

カーマイケルの定理は、an が互いに素なとき、 aλ(n) ≡ 1 (mod n) が成り立つという定理である。

λ(n) が n − 1 の約数であるとき、nカーマイケル数と呼ばれ、自身と互いに素であるような全ての底でフェルマーテストを通過する絶対擬素数となる。

フェルマーテスト[編集]

フェルマーテストは、フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。

フェルマーの小定理の対偶をとると、これは次のように、自然数 n合成数であるための十分条件を与える。

対偶
n と互いに素な整数 a
a^{n-1} \not\equiv 1\pmod{n}
を満たせば、n は合成数である。

この十分条件を用いて、次のように自然数 n の素数判定を行う。

  1. パラメータとして、2 以上 n 未満の自然数 a を1つ定める。
  2. an が互いに素でなければ「n は合成数」と出力して終了。
  3. a^{n-1} \not\equiv 1\pmod{n} ならば「n は合成数」と出力して終了する。そうでないとき「n は確率的素数」と出力して終了する。

フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって n は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも n は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は擬素数と呼ばれる。

疑わしければ、「確率的素数」と出力された場合にはまた異なる a を用いて再びテストを行う。十分な回数だけ a を取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。

しかし、カーマイケル数または絶対擬素数と呼ばれる "反例" もある。カーマイケル数は合成数であるにも拘らず、ほとんどいかなる a を用いても「確率的素数」と判定されてしまう。従って、フェルマーテストは完全な素数判定法ではない。

フェルマーテストを改善するアルゴリズムとしては、ラビン-ミラー素数判定法AKS素数判定法がある。

一般化[編集]

フェルマーの小定理・オイラーの定理は一般の有限群の定理に拡張できる。G位数 m の有限群とすると、G の任意の元 g に対して gm は単位元に一致する。オイラーの定理は G乗法群 (Z/nZ)× のときの場合であり、フェルマーの小定理はさらに n が素数の場合である。

参考文献[編集]

外部リンク[編集]