フェルマーの小定理
フェルマーの小定理 / credit: ナゾロジー編集部
mathematics

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

2021.03.27 Saturday

高校数学の美しい物語 https://mathtrain.jp/rsaango

素数判定に使える!

フェルマーの小定理の応用例
フェルマーの小定理の応用例 / credit: ナゾロジー編集部

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

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

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

計算すると

$$2^{220}=1684996666696914987166688442938726917102321526408785780068975640576$$

となりました。

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

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

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

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

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

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

<

1

2

>

みなさんのおかげでナゾロジーの記事が「Googleニュース」で読めるようになりました!
Google ニュースを使えば、ナゾロジーの記事はもちろん国内外のニュースをまとめて見られて便利です。
ボタンからダウンロード後は、ぜひフォローよろしくおねがいします。
App Store からダウンロード Google Play で手に入れよう

数学のニュースmathematics news

もっと見る

役立つ科学情報

注目の科学ニュースpick up !!