2012年1月16日月曜日

数の感覚

公開鍵暗号の,授業プリントに,「1024ビットの整数10^308個のうち,素数はざっと 10^305個」と書いたら,それを見た数学の先生が,
「素数って,そんなにあるの? ほとんど素数ってこと?」
「3ケタ違うんですよ.つまり0.1% 程度ってこと.」
「あ,そうか.」
308個のうちの305個(これだと99%)でなくて,10^308個のうち 10^305個.
10^305÷10^308=0.001

実際は,2進 1024ビットの整数は,
2^1023 ~ 2^1024 -1 の 8.98847×10^307 個で,そのうち,素数は 1.26692×10^305 個しかない.割合にして,0.140949パーセント.ざっと700個に1個.
自分も最初,素数定理で個数を計算したとき,「ずいぶん多いな」と思ったから,人のこと言えないw
実際は,スカスカである.

1024ビットの最小の素数は,2^1023 + 1155 の,
8988465674311579538646525953945123668089884894711532863671504057886633
7902750481566354238661203768010560056939935696678829394884407208311246
4237153197370621888839467124327426381511098006230470597265414760425028
8441907534117123144073695655527041361858167525534229314911997362296923
9858152417678164812112069763

1024ビットの最大の素数は,2^1024 -105 の,
1797693134862315907729305190789024733617976978942306572734300811577326
7580550096313270847732240753602112011387987139335765878976881441662249
2847430639474124377767893424865485276302219601246094119453082952085005
7688381506823424628814739131105408272371633505106845862982399472459384
79716304835356329624224137111

であった,その間に,
1266900000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000
個以上の素数があるわけだ.(指数で書くと,上記のような勘違いするから全桁並べてみた.)

0 件のコメント:

コメントを投稿

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.