■
ランダムな素数を作るためにまずランダムな整数を作る必要がある。(ランダムな素数はその整数が素数かどうかを調べ、素数が見つかるまで繰り返す方法を取る)
そこでランダムな整数を作る方法にはどんなのがあるかというと以下の方法があるらしい。(擬似乱数)
・線形合同法 ・一方向ハッシュ関数 ・暗号を使う ・ANSI X9.17
暗号としての使用に耐える乱数には以下の性質の内、上二つが必要
・無作為性 --- 暗号の乱数では必須 ・予測不可能性 --- 暗号の乱数では必須 ・再現不可能性 --- 暗号の乱数では必須ではない(というより再現不可能性は完全な乱数であり、専用のハードウェアで乱数を生成する必要がある)
この要件のため実際に暗号に使える乱数としては「一方向ハッシュ関数」「暗号を使う」「ANSI X9.17」により生成された物らしい。
ただ、これらの方法を使うとしても乱数を作るための「種」が必要で、これは完全な乱数である必要があるようだ。今回はそこまでは不可能なのでこれはrand()か何かで生成させたい。
よってランダムな素数を作成するフローとしては以下のような感じでやってみる。
1. rand()により乱数生成用の「種」を生成する 2. ハッシュ関数により種から擬似乱数を生成する。(md5かsha1を使う予定) 3. 擬似乱数がある程度大きいかをチェック 4. 擬似乱数が素数かをチェック