プライバシーは素数が守る [応用] | 逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓rpnの実践ウェブ   
rpn hacks! アールピーエヌ・ハックスサイトマップ

rpn | 応用 | rpn電卓の高いポテンシャルはビジネス・実用・ゲームなどのアプリケーションにも対応。

HOME > 応用 > プライバシーは素数が守る hatena yahoo buzzurl livedoor del.icio.us nifty newsing twitter facebook rss ソーシャルブックマーク

プライバシーは素数が守る

 キャッシュカードの暗証番号、携帯電話のロック番号、コンピュータのログインパスワード…。預金残高・メール・社内データなど、誰もが自分しかアクセスできない情報を持っています。

これらの暗証やパスワードといった認証とは別に、情報自体を守るための技術として暗号化があります。旧日本軍の真珠湾攻撃における「ニイタカヤマノボレ一二〇八」や「トラ・トラ・トラ」は有名ですが、ローマ時代のシーザー暗号に始まり、第二次世界大戦でのドイツ軍のエニグマなど、暗号技術は共通鍵方式を軸に進化を続けてきました(示した暗号は全て解読されてしまいましたが)。

「ニイタカヤマノボレ一二〇八」の意味は12月8日午前零時、戦闘を開始せよ。「トラ・トラ・トラ」は我奇襲に成功せりです。※新高山は台湾の玉山(3952m)で当時の日本領で最高峰の山。
戦争は暗号の解読合戦でもあります。第二次世界大戦時には日本もアメリカの重要暗号を解読しています。開戦当初は暗号書と乱数表(暗号を解くキー)を使う日本軍の暗号は破られていませんでしたが、戦闘でそれらが回収され、解読され始めました。それ以降、日本の暗号は筒抜け状態でした。一方、日本陸軍の暗号は強力で統制もあり、最後まで解読できなかったという話もあります。

共通鍵方式は暗号を解くキーを秘密裏に相手に渡さなければならないという欠点を持っていましたが、現在の暗号は公開鍵と秘密鍵のペアを持つ公開鍵方式が主流です。この方式の中核を担っているのが、なんとあの素数だというのですから驚きです。

素数(prime number)とは2以上の整数で、1と自分自身以外では割り切れない数字のことです。なお、素数が無限にあることは紀元前300年にユークリッドが証明済み。

そして、2つの大きな素数を掛け合わせた数から元の2つの素数を見つけることは、最新のコンピュータをもってしても時間が掛かるという性質を使って、暗号理論が構築されています。つまり、銀行間の通信、軍事情報、企業の機密データ、プライバシーなど、全ての社会基盤が素数の性質に掛かっているわけです。

素数は判定も発見も困難

 そんな素数の世界をちょっとだけ垣間見てみましょう。古来より、人類はある数字が素数かどうかを簡単に判別する方法を捜し求めてきましたが、未だに分かっていません。

エラトステネスのふるいという有名なアルゴリズムがありますが、数字が大きくなると処理時間が急速に増えてしまいます。改良版もたくさん発表されていますが、現在でもコンピュータパワーに任せた力ずくの探索であることに違いはありません。

加えて興味深いことに、2以上の整数は全て素数の掛け算で表すことができます。そのように掛け合わせて作られた数字を合成数といいます(合成数が素因数と同じときが素数)。

 合成数=素因数{×素因数} ※{}は0回以上の繰り返し

これ自体、凄いことのように思えますが、肝心の素数(素因数)を求めるにはどうすればいいのでしょうか。そうです。あのやっかいな素因数分解が必要になります。例えば、2から10までの数字を素因数分解すると次のようになります。

数字
素因数分解 (合成数=素因数{×素因数} ※{}は0回以上の繰り返し)
2
2 (2 = 2)
3
3 (3 = 3)
4
2 2 (4 = 2 * 2)
5
5 (5 = 5)
6
2 3 (6 = 2 * 3)
7
7 (7 = 7)
8
2 2 2 (8 = 2 * 2 * 2)
9
3 3 (9 = 3 * 3)
10
2 5 (10 = 2 * 5)

素因数分解された数字を掛け合わせると元の数字になります。つまり、2、3、5、7が素数、4、6、8、9、10が合成数です(素因数分解した数字が1つしかないときが素数)。

さて、小さな数字を素因数分解するなら簡単ですが、大きい数字となると人間には難しいものがあります。例えば、2011は素数かと問われて即答できる人はまずいません。そこで、rpnプログラムを用意します。プログラム名はprimesです。

ちなみに2011は素数です(2000年から2030年の間では2003、2011、2017、2027、2029が該当)。また、任意の数が素数である確率は1/ln(n)です。2011の場合、rpn式では「2011 l n」(13%)。

素因数分解プログラムのダウンロード

  • 素因数分解プログラムのZIPファイルをダウンロードしてください。
  • ダウンロードしたZIPファイルをダブルクリックするとprimes.objが表示されます。
  • primes.objを格納したいフォルダにドラッグすると以下のダイアログが出てきます。
  • パスワードを入力してください。一致していれば、primes.objが解凍されます。
      ※primes.zipのダウンロードはこちら


  +-------------------------------------------------+
  |  パスワードの入力                                  |
  +-------------------------------------------------+
  |                                        +-----+  |
  |  ファイル'primes.obj'はパスワードで保護されて | OK  |  |
  |  います。 パスワードを入力してください。    +-----+  |
  |                                                 |
  |              +----------------------+  +-----+  |
  |  パスワード(P): |                      |  |キャンセル|  |
  |              +----------------------+  +-----+  |
  +-------------------------------------------------+


 ※パスワードは講座サポートpasteプログラムのダウンロードと同じです。

素因数分解プログラムの使い方

ここでは、c:\rpnディレクトリにobjファイルが保存してあるものとして説明します。DOSプロンプトを起動して、c:\rpnまで移動してください。以下のrpn式を入力すると素因数分解してくれます。

  >rpn 123 -c primes
  3 41


123は素因数が3と41の合成数であることが分かりますね。

primesプログラムは最大16桁の数値まで対応しています。

素因数分解≒素数判定(1000までの素数)

 結局、素因数分解ができるなら素数の判定ができていることになります。ところで一体、素数はどれくらいあるのでしょうか。素因数分解プログラムのprimesを使って、2から1000までの間の素数を探してみましょう。

  >rpn @n @n 1 + #n -b 2 #n -r 999 -c primes
  2
  3
  2 2
    :
  (中略)
    :
  2 499
  3 3 3 37
  2 2 2 5 5 5


一気に999個の数字(2~1000)までの素因数分解が終わりました。このうち、素因数が1つしかないものが素数です。

素数を表示するには元の数字をファイルの"num.txt"に格納して、素因数分解した数字をファイルの"tmp"に格納します。その後、ファイルを横結合して、素因数の数が1つのものだけピックアップすればOKです。

  >rpn @n @n 1 + #n -b 2 #n -r 999 >num.txt
  >rpn @n @n 1 + #n -b 2 #n -r 999 -c primes | rpn -c colcount >tmp
  >paste tmp num.txt | rpn 1 1 -c lookup
  1 2
  1 3
  1 5
    :
  (中略)
    :
  1 983
  1 991
  1 997


行数カウントを取ると素数の数が分かります。その数は168個です。

  >paste tmp num.txt | rpn 1 1 -c lookup | rpn -c count
  168


168個÷999個で0.168168の出現率になります(何故か小数点以下は見つけた素数の数である168の繰り返し)。2割弱が素数で8割強が合成数です(パレートの80対20ルールのようですね)。

2から10000までの場合はどうなるでしょう。大数学者のガウスは「nが十分に大きいとき、nを超えない素数の数はn÷ln(n)にほぼ等しい」ことを15歳のときに発見しています(素数定理)。この定理によると10000までなら約1085個ということになります(rpn式で「10000 . l /」)。

素数に規則性はあるのか?

 それでは、168個の素数を横15個で整列表示してみましょう。素数の数字に何かの規則性を感じることができるでしょうか。

  >paste tmp num.txt | rpn 1 1 -c lookup | rpn _, 15 -c fold'
  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
  53 59 61 67 71 73 79 83 89 97 101 103 107 109 113
  127 131 137 139 149 151 157 163 167 173 179 181 191 193 197
  199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
  283 293 307 311 313 317 331 337 347 349 353 359 367 373 379
  383 389 397 401 409 419 421 431 433 439 443 449 457 461 463
  467 479 487 491 499 503 509 521 523 541 547 557 563 569 571
  577 587 593 599 601 607 613 617 619 631 641 643 647 653 659
  661 673 677 683 691 701 709 719 727 733 739 743 751 757 761
  769 773 787 797 809 811 821 823 827 829 839 853 857 859 863
  877 881 883 887 907 911 919 929 937 941 947 953 967 971 977
  983 991 997


ちなみに168個の素数を幹葉表示してみると次のようになります。

  >paste tmp num.txt | rpn 1 1 -c lookup | rpn _, -c stemleaf
   0 | 0000111122334445566777889
   1 | 000012333455667789999
   2 | 1222334556677889
   3 | 0111334455677889
   4 | 00123334456667899
   5 | 00224456677899
   6 | 0011134445567789
   7 | 00123345566789
   8 | 012222355567888
   9 | 01123445677899


やはり、ランダムな感じがしますね。次に素数を1、合成数を0として横70個に整列表示してみましょう(npdを使って空白を詰めています)。素数の出現間隔に何か規則性を見出せるでしょうか。

  >rpn 1 - m z 1 + <tmp | rpn 70 -c fold' | npd
  1101010001010001010001000001010000010001010001000001000001010000010001
  0100000100010000010000000100010100010100010000000000000100010000010100
  0000000101000001000001000100000100000101000000000101000101000000000001
  0000000000010001010001000001010000000001000001000001000001010000010001
  0100000000010000000000000100010100010000000000000100000100000000010100
  0100000100000001000001000001000100000100000001000100000001000000000101
  0000000001010000010001000001000000010001010001000000000001000000010001
  0000000100010000010000000000010100000000000000000100000100000000010000
  0100000101000001000000000100000100000101000001000001000101000000000001
  0000000001010001000001000001010000000000010001000001000000010000000001
  0000000100000000010000000100000100000100010000000100000100010000000100
  0100000000000001000000000100000000000101000000000101000101000000000100
  0000000000010001010001000000000000010001010001000000000000000000010001
  0000000100000000010000000100010000010000010000000000000100010000010000
  0100000001000001000


        *


 これら素数となる数字に規則性はありませんし、素数が発生する間隔にも規則性はありません。数学者も規則性を見つけていないし、証明もできていないので、少なくとも今日現在ではそう信じられています。

不思議なことに、1(素数)と0(素数でない)の列を中心から外側に向かって渦巻状に並べていくとパターンらしきものが浮かび上がってきます。

情報実践コーナー数学アラカルト黄金比率とフィボナッチ数列に渦巻きの話があります。数列と渦巻きの関係に興味のある人は閲覧ください。

素数の出現規則や完全な生成方法が解明されれば、パスワードも暗号文も全て破られます。あなたのプライバシーの鍵は素数が握っていると言っても過言ではないのです。アメリカも国家安全保障の観点から、世界中の優秀な数学者を集めて、日々研究していることは確かなようです。

アメリカはリーマン予想をはじめ、既に素数の謎を解いているという噂があります(あくまで噂)。いずれにしても、仮に効率的な素因数分解のアルゴリズムが見つかってしまえば、公開鍵方式の暗号技術は崩壊します。

歴史上、素数の不思議さは多くの天才数学者を魅了しました。フェルマーは素数と平方数との関係を、オイラーは素数とπとの間に関連を見出しました。なかには没頭しすぎて統合失調症にまでなった人(ナッシュ均衡のジョン・ナッシュ)もいます。

素数を4で割って余りが1ならば、素数は二つの平方数の和になる(素数全体の半数が該当)。

素数とは神が授けた暗号なのでしょうか。それにπ、e…。果たして、これらに関連性はあるのでしょうか、それともないのでしょうか。

2の素数乗-1(メルセンヌ素数)は素数である確率が高く、かつ素数判定が簡単です。例えば、2の31乗-1=2147483647は素数。この方法を使って2013年1月15日に最大素数の記録が更新されました(48番目のメルセンヌ素数)。その値は素数乗が57885161、素数は17425170桁に及ぶ長大なもの。なお、1000万桁以上の素数発見には賞金が掛けられているそうです。あなたも挑戦してみては。
2015年9月に49番目のメルセンヌ素数が発見され、最大素数の記録が更新されました。その桁数は2,233万8,618。48番目よりも500万桁大きいことになります。

応用応用コーナーに戻るLinkIcon

情報素数を使った暗号の話が、実践コーナー数学アラカルトRSA公開鍵暗号を紙上体験に詳しくあります。普通の文章が暗号化される過程を見てみたい人は閲覧ください。

警告rpnプログラムを実行するには、rpn試用版かrpn標準版が必要です(バージョンの違いはこちら)。

情報pasteは講座サポートで公開されています。colcountはカンタン分析パッケージに同梱されています。lookup, fold'はユーティリティーパッケージに同梱されています。stemleafはrpnマイスターパッケージに同梱されています。xypとnpdはrpnの姉妹ソフトウェアです。詳しくはプロダクトを参照ください。

記事閲覧ランキング (毎月初更新)

人気記事(過去1ヶ月閲覧数)

広報他にもアプリケーションを公開中!タブ「i~v..」をご覧ください。

※応用コーナーのTOP

紹介 rpnの利用シーンはこちら…

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

i

アプリケーションで楽しもう

広報他にもアプリケーションを公開中!タブ「i~v..」をご覧ください。

※応用コーナーのTOP

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

ii

アプリケーションで楽しもう

広報他にもアプリケーションを公開中!タブ「i~v..」をご覧ください。

※応用コーナーのTOP

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

iii

アプリケーションで楽しもう

広報他にもアプリケーションを公開中!タブ「i~v..」をご覧ください。

※応用コーナーのTOP

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

iv

アプリケーションで楽しもう

広報他にもアプリケーションを公開中!タブ「i~v..」をご覧ください。

※応用コーナーのTOP

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

v …

アプリケーションで楽しもう

広報他にもアプリケーションを公開中!タブ「i~v..」をご覧ください。

※応用コーナーのTOP

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

書籍紹介

記事に関連した書籍

本ウェブサイトで扱った話題に関連した書物で、スタッフが実際に読了したものを紹介。

書籍数学の書籍
数の世界は思ったよりもエキサイティング。

  • 書籍統計の書籍
  • ビジネスで統計が使えるととっても有利。

書籍投資の書籍
失敗しない投資には広範囲で実践的な知識が必要。

警告バックスラッシュはエンマークに読み替えてください( IEのみ)。
バックスラッシュとエンマーク

警告文字で作られた図表や式が崩れることがあります。ブラウザによっては固定幅フォントをMSゴシックにするときれいに表示されます。それでも崩れる場合は図表や式をメモ帳にコピー後、閲覧下さい。

警告rpn試用版と標準版(2kリビジョン)はダブルクォートで囲ってください。

rpn 1 2 + ⇒ rpn "1 2 +"
rpn 1 -c foo ⇒ rpn "1" -c "foo"

ダブルクォートは省略できることが多いのですが、慣れない間は囲んだほうが無難です。なお、本ウェブサイトの記事ではrpn標準版(98リビジョン)を使用しているため囲っていません。詳しくは技術サポートの「rpn TIPS参照ください。

注意rpnの障害情報はこちら

警告rpn試用版の場合、複雑なプログラムや処理時間のかかるプログラムの一部には動作しないものがあるかもしれません。あくまで無料提供であることを勘案・了承ください。rpn標準版は、すべてのプログラムが動作します。