じぶん更新日記

じぶん更新日記・隠居の日々 1997年5月6日開設
Copyright(C)長谷川芳典

04月のインデックスへ戻る

最新版へ戻る

※クリックで全体表示。

　県道沿いのフラワーポットで見かけた葉ボタンの花。葉ボタンは葉っぱを鑑賞する目的で流通しているが、花もなかなか美しい。

2024年4月13日（土）
【連載】隠居人が楽しめる素数の話題(9)メルセンヌ素数と完全数(4)暗号技術、疑似乱数生成、メルセンヌ素数の拡張　昨日に続いて素数の話題。 ●かーるのゆっくり数学　近年解明された素数の法則 6選【総集編】を中心にメモと感想を記す。　総集編第四話の終わりのところでは、現代社会におけるメルセンヌ素数の役割（暗号技術、疑似乱数生成）メルセンヌ素数の拡張　という話題が取り上げられていた。　まず、暗号技術への応用として、RSA暗号にメルセンヌ素数が使われていると紹介された。この話は以前にもいくつかの雑学系番組で聞いたことがある。ウィキペディアのリンク先では、 2004年の時点では、インターネットで公募した数多くのPCを用いると512ビット程度の数なら素因数分解できるので、RSA暗号に使用する法 n は1024-4096ビット（10進数で300-1000桁程度）にすることが推奨されている。しかしシャミアは、RSA問題を解くための専用装置 (TWIRL) を作成すれば、1024ビットの n に関するRSA問題ですら解くことができると主張している。また、実用的な量子コンピュータが登場した場合には、素因数分解の桁数増に対する計算時間の増加が緩やかなショアのアルゴリズム（英語版）と呼ばれる高速な量子コンピュータアルゴリズムが実行可能となるため、たとえ鍵のビット数を増やしてもRSA暗号の安全性が保証されなくなる可能性が指摘されている。という記述があり、暗号を解読する新たな方法が発見されなかったとしても、量子コンピュータのスピード力によって、近い将来に安全性が脅かされるようになりそう。　次の、｢疑似乱数生成への応用にメルセンヌ素数が使われている」という話題については特に具体例は挙げられていなかった。ネットで検索したところメルセンヌ・ツイスタという疑似乱数生成器があり、｢既存の疑似乱数列生成手法にある多くの欠点がなく、高品質の疑似乱数列を高速に生成できる。」とされているが、具体的な方法についてはよく分からなかった。Bingに尋ねたところ、メルセンヌ・ツイスタ(Mersenne Twister)法まとめ擬似乱数生成器：メルセンヌ・ツイスタの使い方といったコンテンツを紹介していただいたが、残念ながら私には理解できなかった。　総集編第4話の最後では「メルセンヌ素数の拡張」として、メルセンヌ数は2進数では「11」とか「111」というようにすべて「1」だけで表される数であったが、3進数や4進数ではどうなる？メルセンヌ数は、「2ⁿ-1」であったが、「2ⁿ+1」の場合はどうなる？といった問題が示されていた。　このうち2.の「2ⁿ+1」はフェルマー数の「2^2ⁿ+1」を含むものであり、素数との関係についても研究が進んでいるようだ。ウィキペディアによれば、フェルマー自身は、すべてのフェルマー数はフェルマー素数であると予想していたが、1732年にレオンハルト・オイラーが5番目のフェルマー数は次のように分解できることを示し、反例が与えられた。 F₅ = 2^2⁵ + 1 = 4294967297 = 641 × 6700417 オイラーは 4294967297 という数を小さい数からやみくもにわり算して素因数分解をしたのではなく、フェルマー数F_nの因数がk2ⁿ⁺¹+1の形となることを先に証明していたようである。これにより、F₅である4294967297が合成数であるならばその因数は64k+1の形をとる。kに1から順番に数を入れてわり算していけば、kが10の時、すなわち641によって4294967297が割り切れることが確認できた。なお、現在 F₅ 以降のフェルマー数で素数であるものが存在するかどうかは知られていない。また、フェルマー素数やフェルマー合成数が無限にあるかどうかも知られていないという【←フェルマー合成数が無限に存在しないとしたら、ある最大値より大きいフェルマー数はすべて素数になり無限に存在する、ということになるのだろうか】。　もう1つ、上掲の1.の ●メルセンヌ数は2進数では「11」とか「111」というようにすべて「1」だけで表される数であったが、3進数や4進数ではどうなる？については、どこまで研究が進んでいるのかは分からなかった。3進数表記を《　》内で表したとすると、3は《10》、4は《11》、5は《12》、6は《20》、7は《21》、8は《22》、...となるので、「1」だけで表される数といってもそもそも4＝《11》というように偶数になる場合があり、あまり規則性はないように思われる。なので3進法ではなく、あくまで10進数で考えた時に、3ⁿ+2がどういう振る舞いをするのか考えたほうが面白そうだ。なお、「3ⁿ-1」や「3ⁿ+1」は「奇数±1」で偶数となるため、そもそも素数になることはありえない。じっさいに1から順番に数を入れていくと、 n＝1：3ⁿ+2=5 n＝2：3ⁿ+2=11 n＝3：3ⁿ+2=29 n＝4：3ⁿ+2=83 n＝5：3ⁿ+2=245＝5×7×7 n＝6：3ⁿ+2=731=17×43 n＝7：3ⁿ+2=2189＝11×199 となって、最初のうちは素数になったが、数が大きくなると合成数が生成されるようになってきた。といって、さらに数が多くなっていった時にどうなるのかは分からない。　次回に続く。