あっ、急に素数が必要!でも大丈夫

By | 2013年11月27日

日常生活で、急に大きな素数が必要になることってありますよね。
でもこれで安心!いつでもツイッターアカウントさえあれば、すぐに素数が手に入ります。

primenumber_profile

そうです。あなたは@primenumber_botにメンションを投げさえすればいいのです!

そしてこれが動作例:


例えばこんなときに:

  • RSA暗号の鍵ペアを手動で作りたくなったとき(公開でツイートするからセキュリティ筒抜けですけどね!)
  • おしゃれな自作Tシャツのデザインに
  • お守りに入れて魔除けに

クリスマスに素数のプレゼントはいかがですか?

以下解説

これは有名なMiller-Rabinのアルゴリズムというのを使っています。大きな数の素数判定でもわりと高速に計算できます。Miller-Rabinのアルゴリズムについては、ウィキペディアの解説がわかりやすいのでお勧めです。

ウィキペディア:ミラー-ラビン素数判定法

さらに詳細な解説、とくに計算量については、こちらの本をお薦めします。


Randomized Algorithms (Cambridge International Series on Parallel Computation)

なんでこんなものを作ったのかというと、理由は主に2つで、1)世の中素数萌えというジャンルの人たちが結構な数いる。2)Miller-Rabinアルゴリズムはほぼソラでかけるので、実装コストが低い(つまりツイッターボットのHello Worldをやったような感覚)。

ソースコードはこちらです(BSDライセンスにしておきました)
http://github.com/hamukazu/primenumber_bot

これを期に、素数芸人としての地位を確立していこうかと思う。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です