[jfriends-ml 10138] Re: Effective Java 第 1 回議事録

[TAKAHASHI Toru <torutk@xxxxxxxxxxxx>]

高橋(徹)です。

安藤さん、齋藤さん、どうも。

   ""Koji Saito" <saito@xxxxxxxxxxx>"さんは書きました：

> > > >   BigInteger.probablePrime()メソッドを使う時はどのような時だろうか?
：中略
> > 暗号化の手法の一つで、公開鍵を使うタイプのヤツは、
> > 複数個の素数を元にキーを生成します。そういう用途用ですな。
なんとなく必要な状況が見えました（かな？）
例えば512bitの任意の素数が必要なときに、
java.math.BigInteger.probablePrime(512, new Random())
を実行してみると
8794575807645304968125757625607455805493514543126577819989018543
2603984081243211185894935617012956107184681980236867818040495029
69478216034587613730337561
なんて数が得られました。
＃これだけの桁数の整数を簡単に扱えるってのもすごいなぁ

> probable ってことは、「多分」素数、ってことで、
> 素数であるか否かのチェックを、高速化の為、
> フェルマーの小定理かなんかでチェックしているのではないでしょうか。
絶対に素数とは云えないけど、何パーセントかの確率で素数であると
判定できるアルゴリズムがいくつかあるようですね。
BigIntegerクラスでは、ANSI X9.80（ドラフト仕様）に基づく素数の生
成と判定を行っているとドキュメントされています。
ANSI X9.80-2001 "Prime Number Generation, Primality Testing, and
 Primality Certificates"
javaのソースをちらっと眺めてみると、比較的小さい数値のときは
Miller Rabin判定を、大きいときはLucas Lehmer判定を使っているよう
です。
＃アルゴリズムを見切ったのではなく、単にメソッドの名前から見て
＃とっただけです。。。

> > このへん興味ある方は「暗号化：スティーブン・レビー」とか
> > 「クリプトノミコン：ニール・スティーブンスン」とか読むと
> > 楽しいです。ま、コンピュータ業界、色んな知識が必用ってことで。
> 
> 確かに... :-)
今回の読書会範囲だけでも素数、ハッシュの生成と・・・

---
Toru TAKAHASHI