現代でも活躍している「フェルマーの小定理」って何？ (2/2)

素数判定に使える！

フェルマーの小定理は素数判定に応用されています。

試しに「221」が素数かどうかを判定してみましょう！

221と互いに素な整数2を、(221-1)乗、つまり、220乗してみます。

計算すると

$$2^{220}=1684996666696914987166688442938726917102321526408785780068975640576$$

となりました。

この数を221で割ると、商が7624419306320882294871893406962565235757110979225275022936541360、余り16となります。

もしも、221が素数ならば、フェルマーの小定理を使うと、余りは1にならないとおかしいですよね。このことから、221は素数ではないということがわかります。

このようにフェルマーの小定理を活用した素数判定アルゴリズムは実際に存在しており、「フェルマーテスト」という名前で知られています。

残念ながら、フェルマ―テストは「確率的素数判定」と呼ばれる素数判定であり、その精度は完璧ではありません。

また、今回取りあげた「221の素数判定」は、フェルマーテストのアルゴリズムのほんの一部分を掻い摘んで紹介したものです。興味を持った方は、ぜひフェルマ―テストの全貌を調べてみてくださいね！

フェルマーの小定理は、素数判定アルゴリズムだけでなく、RSA暗号にも使われており、まさに現代になくてはならない定理となっています。「小定理」という名前ではありますが、とても偉大な定理なんですね。