皆さん、おはようございます。時空 解です。   久しぶりにマスペディア１０００からの話題です。今日はトピック１７２から１７４までの内容を加味して、素数判定法について書いてみます。 現代、素数判定法として採用されている方法はリュカ-レーマーテストと呼ばれている方法が一般的のようです。この方法は GIMPS にも採用されています。 リュカ-レーマーテストとはどんな判定方法かを簡素に書いてみると、下記のようになりますかね。 ・ある整数 $ n $ が...

皆さん、おはようございます。時空 解です。   今日はマスペディアの第１７１番目のトピックから、巨大な素数に付いて書いてみましょう。 １１月２３日のブログで紹介したメルセンヌ素数が、今では大きな素数を発見す足掛かりとなっています。それと言うのもメルセンヌ数 $ M_n $ は $ 2^n − 1 $ と言う形をしていて、 $ 2^n − 1 $ が素数であるならば $ n $ もまた素数である、と言う性質があるからです。でも $...