フェルマーテストについて

フェルマーテストについての話です。
きっかけは、paizaラーニングのレベルアップ問題集「素数メニュー」からの出題でした。
paiza.jp

フェルマーテストは、フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムです。
フェルマーの小定理は、素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理です。
フェルマーの最終定理と区別するために、あえて「小」定理と称されているらしいです。
だから、Wikipediaでは『フェルマーの小定理』の項目に包含されています。
フェルマーの小定理 - Wikipedia
それから対偶は、ある命題が成立する場合に、その命題の仮定と結論の両方を否定した命題も成立するという命題同士の関係性の事を言います。
高校数学Aの範囲内で、たしか「集合と論理（命題）」の単元で初めて見たような記憶があります。
対偶論法によれば、命題「AならばB」に対し、対偶：「BでないならAでない」と「AならばB」との真偽は一致するので、対偶「BでないならAでない」を証明すれば「AならばB」を証明できるというわけです。

そして、paizaラーニングのレベルアップ問題集「素数メニュー」では、「整数 N が与えられるので、 N が素数かどうかをフェルマーテストを用いて判定してください」という出題でした。

僕が作成、提出したコードは、以下のとおりです。

・フェルマーテスト

/*
C++による「素数メニュー」問題集
フェルマーテスト
https://paiza.jp/works/mondai
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int a=2;
    bool tf=true;
    if(n%a==0){
        tf=false;
    }else{
        int fermat=1;
        for(int i=0;i<n-1;i++){
            fermat*=a;
            fermat%=n;
        }
        if(fermat%n!=1){
            tf=false;
        }
    }
    if(tf==true){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

「3 以上の自然数 n について、xn + yn = zn となる自然数の組 (x, y, z) は存在しない」
というフェルマーの最終定理は、フェルマーの死後330年経った1995年にアンドリュー・ワイルズによって完全に証明されました。
「うわぁー、ドラマティックだなー！」と思います。
そして「僕は数学者になりたいとか思わないなー」って、強く思いました。
だって、死んでるじゃん、フェルマーさん！
死んだ後じゃん、証明されたの！　そんなの嫌だよー！
現代でも、論文の査読とか評価って、めっちゃ時間がかかっちゃうらしくて、コンピュータが発展したり人工知能が〜、機械学習が〜ってなっているけれど、さて証明しようかって段階になると、そこは人間になるわけですよ。
なぜならばコンピュータとか人工知能は、人間が命令しなければ勝手に動作したり、処理してくれないからです。
ざっくり言うと、「設計図を書いてあげないと、何もできあがってこない」のです。
その設計図を、プログラムとかアルゴリズムなどと言ったりします。
だから、とにかく僕も書いているわけですよ、コードを。

paizaラーニングの中だけでも、約一ヶ月で1,564回分のコードを提出していた事実に、自分でもびっくりしました。
どーかしてるし、夏休みって、すごいわー！
ゲームだったら、何かの実績が解除されているだろうなーって思いましたよ、何もないけれど。
って話を親にしたら、フォートナイトの日替わりアイテムを課金してくれました。
うん、これからもがんばろー。

で、フェルマーの最終定理に関しては、英国テレビ局BBCのドキュメンタリー『ホライズン』が有名で、その制作に携わったサイモン・シンの著書も面白くて、僕は『暗号解読』も読みました。

paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。