適切に設定されたフェルマーテストをパスした数は、素数と断定してまず間違いありません。数学的に「絶対」という保証はないのですが、実用上は問題ありません。「実用上」の意味については後でもう少しつっこんで検討します。フェルマーテストを通過できない数は素数でありません。こっちは絶対的に断言できます。フェルマーテストを通過した数のみが素数でありえます。すべての素数候補が本当に素数であるわけではありません。「素数候補」のなかには真の素数と、実際には合成数である数(まれ)が混ざっています。2をベースとするフェルマーテストを通過します。割った余りが1であることを直接、確認できます。etc.)で暗号鍵の生成に使う巨大素数は、底(てい)(累乗計算の下にくる数のこと)を変えて4度フェルマーテストを繰り返し4回連続で合格したものが選ばれます。ほかの底に対しては擬素数にならないです。擬素数そのものがかなり珍しく、複数の底に対して同時に擬素数になるような数は、存在はしますが、きわめてまれです。数学的には、どこまでいっても素数候補であり、実際に個々に確認するまでは100%確実に素数とは断言できません。暗号のような、デリケートなセキュリティにかかわることが、そんなあいまいな話でいいのでしょうか。数学的に間違いがありうると分かっているような方法で良いのでしょうか。それに対する答は、「これは純粋数学ではないから、数学的に厳密でなくても実用上かまわない」です。動画処理ソフトのノイズフィルターが100%すべてのノイズを除去できなくても実用上、有用なのと同じこと。暗号ソフトもあくまでソフトウェア製品であり、数学を応用したアプリケーションです。それがまじ素数でなかったなら何が起きるでしょうか。全体として3つまたはそれ以上の数の積になっている、という状態です。PGPの安全性は公開鍵の素因数分解が難しい、という事実にもとづいています。公開鍵が100桁の素数2つの積だと思っていたら、そのうち1つは実は合成数で30桁の整数と70桁の整数にさらに分解できるとしたら......。その場合「素因数分解が思ったよりは少し簡単にできる」ということになります。いうなれば「ゾウが踏んでも壊れません。子どもがちょっとけとばしたら、壊れてしまった、という状態です。この場合、客は当然、文句を言うでしょう。このような欠陥商品が例えば1%の割合で混ざっていたら、あそこの製品は品質に問題がある、ということになるでしょう。1%は実用上、問題になるレベルです。問題にならないでしょう。それどころか、99.999999%の圧倒的な成績を誇る高品質の製品と威張れるかもしれません。そもそもまず発覚しないでしょう。100桁×50桁×50桁のひとつの50桁の数が分かるだけで、素因数分解を完成するには、まだまだたいへんな計算量が必要。欠陥商品で非素数が混入していてさえ、それでただちにすべてがぶっこわれるほどヤワじゃない、ってなことです。だいたいのイメージとしては。いうか、1億ぶんの1とか、そんなの宝くじに当たる確率よりもっと難しいでしょう......欠陥商品を手に入れるのは。フェルマーテストを使って素数でないものを除外できる、ということを説明しました。素数を間違えて失格させることはありません。フェルマーテストではねられた数は、実際に割り算しなくても合成数だと断定できます。フェルマーテストにかけて否定されれば、それは絶対に素数でない、と断言できます。いうふうに素因数分解できるのかは分からない」というある意味「おもしろい」状態になります。いっても「絶対的」な見地からは素数であるかないかのどっちかひとつです。どっちつかずの状態こそが人のこころを引きつけるのでしょうが......。50桁や100桁の指数計算89715021234567890123456789012345678901234567890123456789077777のような、とんでもない累乗計算を意味します。一般にはフェルマーテストのほうがずっと速いです。nこのページに関するご連絡は、下記メールアドレスへお願いします。メールでの個別のサポートはできませんので、質問がある場合、掲示板をご利用ください。このウェブサイトは、都合により、まもなく終了します。書いてあった情報は、特に断り書きがない限り、自由に使ってください。そのまま転載しても、書き換えたりして再利用してもかまいません。出典を明記する必要もありません。記事の中には情報が古くて現状と合っていないものや、不正確な点を含むものがあるかもしれません。うのみにせず、ほかのソースにも当たってご確認ください。修正が必要と思われる点がありましたら、お気軽にお知らせください。