情報処理装置、情報処理方法、及びプログラム
【課題】複数の演算ユニットを用いた並列処理において、より高速に素数を求める。
【解決手段】複数の演算ユニットのうち何れか１つを選択し、選択した演算ユニットに対してメモリに格納されているシードを用いた乱数発生処理の実行を指示する。複数の演算ユニットのそれぞれは、乱数発生処理の実行が指示されると、メモリに格納されているシードを用いて乱数を生成し、メモリに格納されているシードを生成した乱数で更新し、生成した乱数が素数であれば、該生成した乱数を出力する。乱数発生処理の実行を指示した演算ユニットによる更新処理が完了したことを検知すると、演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、選択した演算ユニットに対してメモリに格納されているシードを用いた乱数発生処理の実行を指示する。
【解決手段】複数の演算ユニットのうち何れか１つを選択し、選択した演算ユニットに対してメモリに格納されているシードを用いた乱数発生処理の実行を指示する。複数の演算ユニットのそれぞれは、乱数発生処理の実行が指示されると、メモリに格納されているシードを用いて乱数を生成し、メモリに格納されているシードを生成した乱数で更新し、生成した乱数が素数であれば、該生成した乱数を出力する。乱数発生処理の実行を指示した演算ユニットによる更新処理が完了したことを検知すると、演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、選択した演算ユニットに対してメモリに格納されているシードを用いた乱数発生処理の実行を指示する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理技術に関し、特に素数生成技術に関する。
【背景技術】
【０００２】
近年の情報通信において、情報を保護するための暗号技術は必要不可欠である。この暗号技術の一つとして、デジタル署名などに用いられる公開鍵暗号がある。一般的に公開鍵暗号の鍵を生成するためには、桁の大きな素数ｐ，ｑの生成を必要とする。一般的に素数は、乱数生成器にて乱数を生成し、生成された乱数が素数かどうかを判定することにより生成される。
【０００３】
安全性の観点から、素数には高品質な一様性及び予測困難性等が求められる。この要求を満たすために、乱数を生成するために物理的な雑音（熱雑音等）が蓄積されるエントロピーソースを用いることが推奨されている。エントロピーソースから取得したデータ（エントロピー）を乱数の種（シード）として乱数生成器に入力することにより、高品質な乱数が得られる（非特許文献１）。
【０００４】
生成する素数のビット長が大きいほど、素数が見つかる確率は小さくなる。大きな素数を発見するためには、乱数の生成と素数判定とを何度も繰り返す必要があるため、多くのコンピュータリソース及び時間を必要とする。この問題を解決するために、特許文献１においては、暗号処理の全てが画像処理アクセラレータであるＧＰＵで行われる。一般にＧＰＵは多数の演算コアで構成されており、各演算コアは並列に汎用計算ができるため、ＣＰＵよりも高速に暗号処理を行うことができることが期待される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−２３３３８１号公報
【非特許文献】
【０００６】
【非特許文献１】ＮＩＳＴ，“Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ｆｏｒ Ｒａｎｄｏｍ Ｎｕｍｂｅｒ Ｇｅｎｅｒａｔｉｏｎ Ｕｓｉｎｇ Ｄｅｔｅｒｍｉｎｉｓｔｉｃ Ｒａｎｄｏｍ Ｂｉｔ Ｇｅｎｅｒａｔｏｒｓ，ＳＰ８００−９０”
【非特許文献２】ＮＩＳＴ，“ＤＩＧＩＴＡＬ ＳＩＧＮＡＴＵＲＥ ＳＴＡＮＤＡＲＤ（ＤＳＳ）, ＦＩＰＳ１８６−２”
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ＧＰＵに搭載されている複数の演算ユニットを活用するには、素数の生成を多並列に行う必要がある。しかしながら特許文献１に記載の技術によれば、多並列に素数の生成を行う場合に、複数の演算ユニットが同一の乱数を生成する可能性がある。このことは、素数生成処理速度の低下をもたらしうる。
【０００８】
本発明は、複数の演算ユニットを用いた並列処理において、より高速に素数を求めることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の目的を達成するために、例えば、本発明の情報処理装置は以下の構成を備える。すなわち、
乱数を生成するために用いるシードを保持するメモリと、
前記メモリに格納されているシードを用いて乱数を生成する複数の演算ユニットと、
前記複数の演算ユニットのうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する指示手段とを備え、
前記複数の演算ユニットのそれぞれは、
前記指示手段により乱数発生処理の実行が指示されると、前記メモリに格納されているシードを用いて乱数を生成し、前記メモリに格納されているシードを該生成した乱数で更新する更新手段と、
前記更新手段が生成した乱数が素数であれば、該生成した乱数を出力する出力手段とを備え、
前記指示手段は、乱数発生処理の実行を指示した演算ユニットの更新手段による更新処理が完了したことを検知すると、該演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する
ことを特徴とする。
【発明の効果】
【００１０】
複数の演算ユニットを用いた並列処理において、より高速に素数を求めることができる。
【図面の簡単な説明】
【００１１】
【図１】実施例１におけるシステムの全体構成を説明する図である。
【図２】実施例１におけるＧＰＵの構成を示す図である。
【図３】実施例１におけるＣＰＵの処理フローを説明する図である。
【図４】実施例１におけるＧＰＵの処理フローを説明する図である。
【図５】実施例１におけるシステム全体の機能構成を説明する図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態の一例を図面に基づいて説明する。ただし、本発明の範囲は以下の実施例に限定されるものではない。
【００１３】
＜システム全体構成＞
図１は、本実施例に係る情報処理システム１００の例を示す。情報処理システム１００は、ＣＰＵ１０１、グラフィックボード１０２、主メモリ１０５、メモリコントローラハブ１０６、入出力コントローラハブ１０７、ＮＩＣ１０８、記憶装置１０９、及び外部接続ポート１１０を含む。
【００１４】
ＣＰＵ１０１は、主メモリ１０５又は記憶装置１０９に記録されたプログラム（コンピュータプログラム）に従って、情報処理システム１００の動作の少なくとも一部を制御する中央演算装置である。さらに、ＣＰＵ１０１は物理的な雑音をビット列として取得することができる。物理的な雑音は任意のものでありうるが、例えば記憶装置１０９のシークタイムなどが挙げられる。
【００１５】
グラフィックボード１０２は、ＧＰＵ１０３とＧＰＵメモリ１０４とを含む。グラフィックボード１０２は通常、画像処理に特化した拡張ボードである。ＧＰＵ１０３は、リンク１１８を介してＧＰＵメモリ１０４に接続される。ＧＰＵ１０３は、リンク１１３を介してＣＰＵ１０１からＧＰＵメモリ１０４へと転送されたプログラムに従って、グラフィックボード１０２の動作の少なくとも一部を制御する演算ユニットを有する。ＧＰＵメモリ１０４は、ＧＰＵ１０３を制御するプログラムを格納することができる。ＧＰＵメモリ１０４はまた、ＧＰＵ１０３の動作中にデータを一時的に記憶することができる。ＧＰＵメモリ１０４は、例えばＲＡＭでありうる。
【００１６】
主メモリ１０５は、ＣＰＵ１０１を制御するプログラムを格納することができる。主メモリ１０５はまた、ＣＰＵ１０１の動作中にデータを一時的に記憶することができる。主メモリ１０５は、例えばＲＡＭでありうる。
【００１７】
メモリコントローラハブ１０６は、リンク１１３、１１４、１１５及び１１６を介してそれぞれＣＰＵ１０１、主メモリ１０５、グラフィックボード１０２及び入出力コントローラハブ１０７と接続されている。メモリコントローラハブ１０６は、主メモリ１０５、グラフィックボード１０２及び入出力コントローラハブ１０７の間のデータ転送を制御する。
【００１８】
入出力コントローラハブ１０７は、リンク１１７、１１８及び１１９を介してそれぞれＮＩＣ１０８、記憶装置１０９及び外部接続ポート１１０と接続されている。入出力コントローラハブ１０７は、メモリコントローラハブ１０６、ＮＩＣ１０８、記憶装置１０９及び外部接続ポート１１０の間のデータ転送を制御する。
【００１９】
ＮＩＣ１０８は、ネットワークに接続するための通信インターフェイスである。ＮＩＣ１０８は例えば、有線ＬＡＮ、無線ＬＡＮ、又はＢｌｕｅｔｏｏｔｈ用の通信カード等でありうる。
【００２０】
記憶装置１０９は、ＣＰＵ１０１が実行するプログラム、ＣＰＵ１０１が処理に用いるデータ、及び外部から取得したデータ等を格納する。記憶装置は例えば、ハードディスクのような磁気記憶装置、又はＳＳＤのようなフラッシュメモリでありうる。情報処理システム１００は、複数の記憶装置１０９を有していてもよい。
【００２１】
外部接続ポート１１０は、外部機器を情報処理システム１００に接続するためのポートである。外部接続ポート１１０は、例えばＵＳＢポート、ＩＥＥＥ１３９４ポート、ＨＤＭＩポート等でありうる。この外部接続ポート１１０に入力装置１１１を接続することで、情報処理システム１００は入力装置１１１からデータを取得することができる。情報処理システム１００は、複数の外部接続ポート１１０を有していてもよい。
【００２２】
入力装置１１１は、外部接続ポート１１０を介して情報処理システム１００にデータを入力する機器である。入力装置１１１は例えば、キーボード、マウス等でありうる。出力装置１１２は、情報処理システム１００が出力するデータを視覚的に表示する装置である。出力装置１１２は、グラフィックボード１０２が有するポートに接続されることができる。また出力装置１１２は、外部接続ポート１１０に接続されてもよい。出力装置１１２の例としては、例えば液晶モニタ等が挙げられる。出力装置１１２が接続されるポートの例としては、例えばＨＤＭＩポート等が挙げられる。
【００２３】
リンク１１３、１１４、１１５、１１６、１１７、１１８、及び１１９はシリアルバスである。リンク１１３、１１４、１１５、１１６、１１７、１１８、及び１１９は例えば、ＰＣＩ又はＰＣＩエクスプレス等などのバスでありうる。
【００２４】
以上、本実施例に係る情報処理システム１００として利用可能なハードウェア構成の一例を示した。以上説明された情報処理システム１００は、例えば、パーソナルコンピュータ等を用いて実現することができる。しかしながら、本実施例に係る情報処理システム１００は上述の構成に限定されるものではない。例えば変形例において、情報処理システム１００はグラフィックボード１０２を含まずにＧＰＵ１０３を含んでいてもよい。この場合、ＧＰＵ１０３が主メモリ１０５に対してデータを読み書きできるように、情報処理システム１００を構成すればよい。また、ＣＰＵ１０１にＧＰＵ１０３を統合してもよい。この場合にも、情報処理システム１００はグラフィックボード１０２を有さなくてもよい。他の実施例として、ＣＰＵとＧＰＵとの少なくとも一方として、暗号処理に特化したハードウェアである暗号アクセラレータを用いてもよい。また、ＣＰＵとＧＰＵとの少なくとも一方として、演算処理が可能なＩＰコアを用いてもよい。
【００２５】
＜ＧＰＵ１０３の構成＞
以下、図２を参照してＧＰＵ１０３について詳しく説明する。図２は、本実施例に適用可能なＧＰＵ１０３の構成例を示す。図２において、ＧＰＵ１０３は２つの演算ユニット２０１，２０２を含む。しかしながら、ＧＰＵ１０３が含む演算ユニットの数は２つに限定されない。ＧＰＵ１０３は、２つ以上の演算ユニットを含みうる。演算ユニット２０１及び２０２は、並列動作が可能な演算装置である。例えば演算ユニット２０１及び２０２は、それぞれ別の命令を実行することができ、また別のデータを扱うことができる。
【００２６】
演算ユニット２０１はキャッシュメモリ２０３を含む。演算ユニット２０１は、ＧＰＵメモリ１０４又はキャッシュメモリ２０３に記録されたプログラムに従って、ＧＰＵ１０３内の動作の少なくとも一部を制御する。また、また、演算ユニット２０２はキャッシュメモリ２０４を含む。演算ユニット２０２は、ＧＰＵメモリ１０４又はキャッシュメモリ２０４に記録されたプログラムに従って、ＧＰＵ１０３内の動作の少なくとも一部を制御する。キャッシュメモリ２０３及び２０４は、高速に読み書き可能な小容量メモリである。
【００２７】
＜情報処理システム１００の機能構成＞
以下、図５を参照して、図１に係る情報処理システム１００の機能構成について説明する。本実施例に係る情報処理システム１００は、並列に素数の生成を行うことができる。図５に示すように、情報処理システム１００は演算装置と外部演算装置とを含む。演算装置としては、例えば前述したＣＰＵ１０１を用いることができる。また外部演算装置としては、前述したＧＰＵ１０３を用いることができる。この場合、処理装置０及び処理装置１は、それぞれ演算ユニット２０１及び演算ユニット２０２に対応する。
【００２８】
しかしながら、本実施例で用いられる演算装置及び外部演算装置は、上述のＣＰＵ１０１及びＧＰＵ１０３には限られない。例えば、演算装置１０１又は外部演算装置１０３として、前述した暗号アクセラレータを用いてもよい。以下の説明では、演算装置としてＣＰＵ１０１を用いる。また、外部演算装置としてＧＰＵ１０３を用いる。
【００２９】
図５に示すように、演算装置１０１はシード生成部５０１を備える。また、外部演算装置１０３は保存部５０２、制御部５０３、シード更新部５０４、乱数生成部５０５、及び素数判定部５０６を備える。また、並列に動作可能な演算ユニット２０１，２０２はそれぞれ、シード更新部５０４、乱数生成部５０５、及び素数判定部５０６を備える。以下、これらの各部について説明する。
【００３０】
＜シード生成部５０１＞
以下で、シード生成部５０１について説明する。シード生成部５０１は、乱数の種となるシードの初期値を生成し、生成した初期値をＧＰＵ１０３に出力する。シードの生成方法としては任意の公知の方法を用いることができる。本実施例においては、シードの生成のためにエントロピーを用いる。
【００３１】
本実施例においてエントロピーとは、物理的な雑音をビット列に変換することによって得られる値である。すなわちシード生成部５０１は、熱雑音などの物理的な雑音が蓄積されるエントロピーソースから、シードの生成に必要な分のエントロピーを取得する。シードの生成に必要なエントロピーは、生成する乱数のセキュリティ強度によって異なる。例えばセキュリティ強度が１２８ｂｉｔの乱数を生成するときは、１２８ｂｉｔ以上のエントロピーが必要となる（非特許文献１を参照）。
【００３２】
シード生成部５０１が十分なエントロピーを取得すると、シード生成部５０１は、エントロピーを用いてシードを生成する。例えば、エントロピーに対してハッシュ関数を適用することにより、シードを生成することができる（非特許文献１を参照）。また、エントロピーに対してナンスなどの付加データを追加した後に、ハッシュ関数を適用してもよい（非特許文献１）。また、ハッシュ関数の代わりにブロック暗号アルゴリズムを用いることもできる（非特許文献１）。そしてシード生成部５０１は、生成したシードを保存部５０２に出力する。
【００３３】
シード生成部５０１は、保存部５０２に格納されているシード更新回数及び限界シード更新回数に従って、シードを生成及び出力する。ここでシード更新回数とは、シードの更新回数を表す値である。シード生成部５０１が生成したシードを保存部５０２に格納する際に、シード生成部５０１は、保存部に格納されているシード更新回数を０に初期化する。その後、シード更新部５０４が保存部５０２に格納されているシードを更新する際に、シード更新部５０４は、保存部５０２に格納されているシード更新回数を更新する。
【００３４】
限界シード更新回数（所定回数）は、１つのシードから生成できる乱数の総数を示す。１つのシードを更新しながら多数の乱数を生成すると、乱数の周期性が知られる可能性が高くなる。そこで本実施例においては、１つのシードから生成できる乱数の数が予め定められている。限界シード更新回数は、例えばユーザが設定することができる。
【００３５】
シード生成部５０１は、シード更新回数が限界シード更新回数を超えたと判断すると、保存部５０２に格納されているシードを新しいシードで置き換える。すなわち、シード生成部５０１は、まず保存部５０２のシードを削除する。次にシード生成部５０１は上述のようにエントロピーを用いてシードを生成し、生成したシードを保存部５０２に格納する。そしてシード生成部５０１は、保存部５０２に格納されているシード更新回数を０に初期化する。シード更新回数が限界シード更新回数以下の場合にも、シード生成部５０１は、エントロピーを用いたシードの生成処理を行ってもよい。この場合、シード更新回数が限界シード更新回数を超えたときに、シード生成部５０１は生成されたシードを素早く保存部５０２に格納することができる。
【００３６】
＜保存部５０２＞
保存部５０２は、上述のように、乱数を生成するために用いるシード、シード更新回数、及び限界シード更新回数などのデータを格納（保持）することができる。
【００３７】
＜制御部５０３＞
以下で、制御部５０３について説明する。制御部５０３は、乱数生成部５０５の動作を制御する。特に制御部５０３は、複数の乱数生成部５０５のそれぞれが同一の乱数を生成しないように、乱数生成部５０５を制御（指示）する。本実施例において制御部５０３は、複数の演算ユニット群２０１，２０２のうち何れか１つを選択する。そして、選択した演算ユニットに対して、乱数発生処理の実行を指示する。
【００３８】
具体的には制御部５０３は、保存部５０２に格納されたシード更新回数と、演算ユニット２０１，２０２に予め割り当てられた識別子とに応じて、乱数生成部５０５を制御する。本実施例において制御部５０３は、シード更新回数を演算ユニットの総数で割った余りを参照してこの制御を行う。以降、シード更新回数を演算ユニットの総数で割った余りを「シード更新回数（mod 演算ユニット総数）」と記述する。識別子とは、演算ユニット２０１，２０２を特定する数字である。識別子は、各演算ユニットに対して“０”から順に割り当てられる。本実施例において、演算ユニット２０１は識別子“０”を割り当てられており、演算ユニット２０２は識別子“１”を割り当てられている。
【００３９】
制御部５０３は、保存部５０２に格納されているシード更新回数を参照して、１つの演算ユニットに対し、保存部５０２に格納されているシードを用いて乱数を生成させる。具体的には制御部５０３は、シード更新回数（mod 演算ユニット総数）に一致する識別子が割り当てられた演算ユニットに対し、保存部５０２に格納されているシードを用いて乱数を生成させる。このようにして、並列動作を行う演算ユニット２０１，２０２が同一の乱数を生成し、演算ユニット２０１，２０２が同一の乱数に対して素数判定を行うことを回避できる。
【００４０】
より一般的に、情報処理システム１００がＮ個の演算ユニットを有している場合について説明する。この場合、それぞれの演算ユニットには１番からＮ番までの番号（識別子）が付される。そして、「シード更新回数（mod 演算ユニット総数）」と一致する番号を有する演算ユニットに対し、制御部５０３は保存部５０２に格納されているシードを用いて乱数を生成させる。
【００４１】
＜シード更新部５０４＞
以下で、シード更新部５０４について説明する。シード更新部５０４は、保存部５０２に格納されているシードを更新する。またシード更新部５０４は、保存部５０２に格納されているシードを更新する際に、保存部５０２に格納されているシード更新回数を変更する。
【００４２】
乱数生成器は通常、同一のシードからは同じ乱数を生成する。そこで、複数の乱数を生成するために、シードが更新される。つまりシード更新部５０４は、乱数生成部５０５が乱数を生成する度に、保存部５０２に格納されているシードを更新する。この際シード更新部は、乱数生成部５０５が生成した乱数を用いて、保存部５０２に格納されているシードを更新することができる（非特許文献１を参照）。例えばシード更新部５０４は、乱数生成部５０５が生成した乱数で、保存部５０２に格納されているシードを置換すればよい。またシード更新部５０４は、保存部５０２に格納されているシードを更新する際に、保存部５０２に格納されているシード更新回数を更新する。例えば、シード更新回数をインクリメントすればよく、具体的にはシード更新回数に１を加えればよい。
【００４３】
＜乱数生成部５０５＞
以下で、乱数生成部５０５について説明する。乱数生成部５０５は、制御部５０３に指示されると、保存部５０２に格納されているシードと、乱数生成器とを用いて乱数を生成する。そして乱数生成部５０５は、生成した乱数を素数判定部５０６に出力する。乱数生成器は、シードから乱数を生成する。乱数生成器は任意の公知の方法を用いて乱数を生成することができ、例えば、ハッシュ関数やブロック暗号アルゴリズムなどを用いることができる（非特許文献１を参照）。なお、保存部５０２に格納されているシード更新回数が限界シード更新回数を超えている場合には、乱数生成部５０５は乱数の生成を行わず、シード生成部５０１によって新しいシードが保存部５０２に格納されるのを待つ。
【００４４】
＜素数判定部５０６＞
以下で、素数判定部５０６について説明する。素数判定部５０６は、乱数生成部５０５が出力した乱数が素数であるか否かを判定する。素数判定には任意の公知の方法を用いることができ、例えばミラーラビン法を用いることができる（非特許文献２）。
【００４５】
素数判定部５０６は、乱数生成部５０５が出力した乱数が素数であると判断すると、素数生成が完了したことをＣＰＵ１０１に通知する。本実施例において素数判定部５０６は、乱数が素数であると判断すると、ＣＰＵ１０１に生成された素数を転送する。また素数判定部５０６は、乱数が素数であると判断すると、保存部５０２に格納されている素数生成完了フラグをＯＮにする。素数生成完了フラグは、素数の生成が完了した時にＯＮとなり、素数の生成が完了していないときにＯＦＦとなるフラグである。素数生成完了フラグを参照することにより、ＣＰＵ１０１は素数が生成されたことを知ることができる。
【００４６】
＜本実施例に係る処理フロー＞
以下、図３及び図４を参照して、本実施例に係る素数の生成処理のフローを説明する。本実施例に係る素数の生成処理は、ＣＰＵ１０１での処理とＧＰＵ１０３での処理とに分けられる。そこで本明細書では、ＣＰＵ１０１における処理フローと、ＧＰＵ１０３における処理フローとについて、それぞれ説明する。
【００４７】
＜ＣＰＵ１０１における処理フロー＞
図３は本実施例におけるＣＰＵ１０１で実行される処理フローを示すフローチャートである。ステップＳ３０１においてシード生成部５０１は、保存部５０２に格納されている素数生成完了フラグをＯＦＦにする。ステップＳ３０２においてシード生成部５０１は、エントロピーソースにシードを作るのに十分なエントロピーが溜まっているか否かを確認する。所定量のエントロピーが溜まっていない場合、シード生成部５０１は所定量のエントロピーがエントロピーソースに溜まるのを待つ。所定量のエントロピーが溜まっている場合、処理はステップＳ３０３に進む。
【００４８】
ステップＳ３０３においてシード生成部５０１は、エントロピーソースからエントロピーを取得し、上述のようにシードを生成する。ステップＳ３０４においてシード生成部５０１は、限界シード更新回数を設定する。具体的にはシード生成部５０１は、予め定められた限界シード更新回数を保存部５０２に格納すればよい。ステップＳ３０５においてシード生成部５０１は、ステップＳ３０３で生成したシードを保存部５０２に格納する。限界シード更新回数及び生成されたシードは、メモリコントローラハブ１０６を介してＧＰＵ１０３へと転送される。
【００４９】
ステップＳ３０６においてシード生成部５０１は、ＧＰＵ１０３において素数の生成が完了したか否かを判定する。具体的には、保存部５０２に格納されている素数生成完了フラグがＯＮであるか否かを判定すればよい。素数生成完了フラグがＯＮであれば、ステップＳ３０７においてシード生成部はメモリコントローラハブ１０６を介して保存部５０２から生成された素数を取得する。そしてシード生成部５０１は、ＧＰＵ１０３の処理を停止させる。素数生成完了フラグがＯＦＦであれば、処理はステップＳ３０８に進む。
【００５０】
ステップＳ３０８においてシード生成部５０１は、シードの再生成が必要であるか否かを判定する。具体的には上述のように、シード更新回数が限界シード更新回数を超える場合に、シード生成部５０１はシードの再生成が必要であると判定する。シードの再生成が必要である場合、処理はステップＳ３０２に戻る。シードの再生成が必要ではない場合、処理はステップＳ３０６に戻る。
【００５１】
＜ＧＰＵ１０３における処理フロー＞
ＧＰＵ１０３においては、ＧＰＵ１０３の構成要素である演算ユニット２０１及び演算ユニット２０２が並列に処理を行う。演算ユニット２０１と２０２とは同じフローに従って処理を行う。したがって、本明細書においては演算ユニット２０１の処理フローについてのみ説明する。
【００５２】
図４は、本実施例に係る演算ユニット２０１で実行される処理フローを示すフローチャートである。ステップＳ４０１において乱数生成部５０５は、ＣＰＵ１０１から転送されたシードが保存部５０２に格納されているか否かを確認する。シードが格納されていない場合、乱数生成部５０５は保存部５０２にシードが格納されるまで待つ。シードが格納されている場合、ステップＳ４０２において乱数生成部５０５は、格納されているシードで乱数生成器を初期化する。
【００５３】
ステップＳ４０３において乱数生成部５０５は、保存部５０２に格納されているシード更新回数と限界シード更新回数とを比較する。シード更新回数が限界シード更新回数を超えている場合、処理はステップＳ４０１に戻る。超えていない場合、処理はステップＳ４０４に進む。
【００５４】
ステップＳ４０４において乱数生成部５０５は、現在保存部５０２に格納されているシードを用いて乱数を生成してもよいかを、制御部５０３に問い合わせる。制御部５０３の詳細な処理については後述する。乱数を生成してはいけない場合、処理はステップＳ４０３に戻る。乱数を生成してもよい場合、処理はステップＳ４０５に進む。このステップＳ４０４により、複数の演算ユニットが同一のシードを用いて乱数を生成することが防止される。
【００５５】
ステップＳ４０５において乱数生成部５０５は、保存部５０２にシードが格納されているか否かを再び確認する。シードが格納されていない場合、処理はステップＳ４０１に戻る。シードが格納されている場合、ステップＳ４０６において乱数生成部５０５は、保存部５０２に格納されているシードを用いて乱数を生成する。
【００５６】
ステップＳ４０７において乱数生成部５０５は、ステップＳ４０６で生成された乱数を用いて、保存部５０２に格納されているシードを更新する。また乱数生成部５０５は、保存部５０２に格納されているシード更新回数をインクリメントする。ステップＳ４０８において素数判定部５０６は、ステップＳ４０６において生成された乱数が素数かどうかを判定する。生成された乱数が素数でないと判定された場合、処理はステップＳ４０３に戻る。生成された乱数が素数であると判定された場合、ステップＳ４０９において素数判定部５０６は保存部５０２に格納されている素数生成完了フラグをＯＮにし、処理は終了する。
【００５７】
次に、複数の演算ユニット２０１，２０２が同一のシードを用いて乱数を生成することを防止するステップＳ４０４について詳しく説明する。上述のように、演算ユニット２０１は識別子として”０”を有し、演算ユニット２０２は識別子として”１”を有する。また、本実施例において演算ユニット総数は”２”である。したがって、「シード更新回数(mod 演算ユニット総数)」は”０”か”１”かの何れかの値を持つ。すなわち、演算ユニット２０１についての識別子（”０”）が、「シード更新回数(mod 演算ユニット総数)」と一致しない場合、演算ユニット２０２についての識別子（”１”）は、「シード更新回数(mod 演算ユニット総数)」と一致する。また、この逆も成り立つ。
【００５８】
ステップＳ４０４において制御部５０３は、演算ユニットの識別子と「シード更新回数(mod 演算ユニット総数)」とが一致する場合に、演算ユニットに対して乱数の生成を許可する。演算ユニット２０１は、制御部５０３によって乱数の生成を許可されるまで、ステップＳ４０３〜Ｓ４０４を繰り返す。すなわち演算ユニット２０１は、演算ユニット２０１の識別子とシード更新回数(mod 演算ユニット総数)が一致するまで、ステップＳ４０３〜Ｓ４０４を繰り返す。
【００５９】
一方で演算ユニット２０１が乱数の生成を許可されていない際に、演算ユニット２０２は乱数の生成を許可されている。従って演算ユニット２０２は乱数を生成し、生成された乱数を用いて保存部５０２に格納されているシードを更新するとともに、シード更新回数に１を加える。シード更新回数が１つ増えると、演算ユニット２０１の識別子とシード更新回数(mod 演算ユニット総数)が一致する。このため、演算ユニット２０１は制御部５０３によって乱数の生成を許可される。一方で、今度は演算ユニット２０２の識別子とシード更新回数(mod 演算ユニット総数)が不一致となる。このため、演算ユニット２０２は保存部５０２に格納されているシードが更新されるまで、乱数の生成を許可されない。
【００６０】
このように、制御部５０３は保存部５０２に格納されているシード更新回数を監視する。そして制御部５０３は、シード更新回数の増加を検出することにより、ある演算ユニットによる乱数生成処理及びシード更新処理が終了したことを検知できる。制御部５０３は、ある演算ユニットによってシードが更新されたことを検出すると、別の演算ユニットに乱数の生成を許可する。このような処理により、演算ユニット２０１，２０２が同一のシードを用いて乱数を生成することを回避することができる。もっとも制御部５０３は、シードを更新した演算ユニットを特定する情報を参照して、別の演算ユニットに乱数の生成を許可してもよい。また制御部５０３は、演算ユニットが処理を行っているか否か、例えば素数判定処理を完了しているか否かを示すフラグを参照して、処理を行っていない１つの演算ユニットに対して乱数の生成を許可してもよい。このように制御部５０３は、様々な方法を用いて、１つのシードを用いた乱数の生成を特定の演算ユニットのみに行わせるように、演算ユニットを制御することができる。
【００６１】
以上説明したように本実施例によれば、ＣＰＵはエントロピーソースを用いてシードの生成処理を行う。また、ＧＰＵは並列にシードから乱数の生成及び素数の判定を行う。このように、エントロピーソースを持たないＧＰＵが素数を生成することが可能となる。本実施例によれば、同一の乱数に対して複数のＧＰＵが素数判定を行うことが回避される。このため、無駄な素数判定処理を回避することができる。さらに、負荷の大きい素数判定をＧＰＵで並列に処理できるため、ＣＰＵの負荷を下げることができ、かつ素数生成を高速化することが可能となる。
【００６２】
＜変形例１＞
上述の実施例は一例に過ぎず、別の実施例を採用することもできる。例えば、実施例１において乱数生成部５０５は、保存部５０２に格納されているシードを用いて乱数を生成してもよいかを、制御部５０３に問い合わせた。しかしながら素数判定部５０６が、素数判定を行ってもよいかを、制御部５０３に問い合わせてもよい。この場合制御部５０３は、実施例１において乱数生成部５０５を制御したのと同様に、素数判定部５０６を制御することができる。またこの場合、乱数生成部５０５は問い合わせを行うことなく、保存部５０２に格納されているシードを用いて乱数を生成してもよい。こうすることにより、複数の演算ユニットが、同一のシードを用いて生成された同一の乱数について素数であるか否かを判定することを回避できる。
【００６３】
＜変形例２＞
各演算ユニット２０１，２０２は別々のシードを用いてもよい。つまり、演算ユニットのそれぞれに対応付けられたシードが、保存部５０２に格納される。この場合、シード生成部５０１が生成した１つのシードが、それぞれの演算ユニットによって共通に用いられてもよい。各演算ユニット２０１，２０２は、対応付けられたシードを用いて、上述のように乱数生成、シード更新、及び素数判定を行う。
【００６４】
このとき素数判定部５０６は、シード更新回数(mod 演算ユニット総数)と識別子とが一致しない時には、乱数生成部５０５が生成した乱数が素数であるか否かを判定しない。こうすることにより、複数の演算ユニットが、同一のシードを用いて生成された同一の乱数について素数であるか否かを判定することを回避できる。
【００６５】
＜変形例３＞
乱数生成部５０５が、保存部５０２に格納されているシードを用いて乱数を生成してもよいかを、制御部５０３に問い合わせることは必ずしも必須ではない。例えば乱数生成部５０５は、保存部５０２に格納されているシード更新回数を確認し、保存部５０２に現在格納されているシードを用いて乱数を生成してもよいかを判定することができる。この判定は、制御部５０３と同様に行うことができる。
【００６６】
＜変形例４＞
各演算ユニット２０１，２０２は、ステップＳ４０８において素数を見つけた後に、その素数を用いて鍵生成処理を行ってもよい。この場合情報処理システム１００は、並列に複数の鍵を生成することができる。
【００６７】
（他の実施形態）
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）をネットワーク又は各種記憶媒体を介してシステム或いは装置に供給する。そして、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムコードを読み出して実行する。この場合、そのプログラム、及び該プログラムを記憶した記憶媒体は本発明を構成することになる。
【技術分野】
【０００１】
本発明は情報処理技術に関し、特に素数生成技術に関する。
【背景技術】
【０００２】
近年の情報通信において、情報を保護するための暗号技術は必要不可欠である。この暗号技術の一つとして、デジタル署名などに用いられる公開鍵暗号がある。一般的に公開鍵暗号の鍵を生成するためには、桁の大きな素数ｐ，ｑの生成を必要とする。一般的に素数は、乱数生成器にて乱数を生成し、生成された乱数が素数かどうかを判定することにより生成される。
【０００３】
安全性の観点から、素数には高品質な一様性及び予測困難性等が求められる。この要求を満たすために、乱数を生成するために物理的な雑音（熱雑音等）が蓄積されるエントロピーソースを用いることが推奨されている。エントロピーソースから取得したデータ（エントロピー）を乱数の種（シード）として乱数生成器に入力することにより、高品質な乱数が得られる（非特許文献１）。
【０００４】
生成する素数のビット長が大きいほど、素数が見つかる確率は小さくなる。大きな素数を発見するためには、乱数の生成と素数判定とを何度も繰り返す必要があるため、多くのコンピュータリソース及び時間を必要とする。この問題を解決するために、特許文献１においては、暗号処理の全てが画像処理アクセラレータであるＧＰＵで行われる。一般にＧＰＵは多数の演算コアで構成されており、各演算コアは並列に汎用計算ができるため、ＣＰＵよりも高速に暗号処理を行うことができることが期待される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−２３３３８１号公報
【非特許文献】
【０００６】
【非特許文献１】ＮＩＳＴ，“Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ ｆｏｒ Ｒａｎｄｏｍ Ｎｕｍｂｅｒ Ｇｅｎｅｒａｔｉｏｎ Ｕｓｉｎｇ Ｄｅｔｅｒｍｉｎｉｓｔｉｃ Ｒａｎｄｏｍ Ｂｉｔ Ｇｅｎｅｒａｔｏｒｓ，ＳＰ８００−９０”
【非特許文献２】ＮＩＳＴ，“ＤＩＧＩＴＡＬ ＳＩＧＮＡＴＵＲＥ ＳＴＡＮＤＡＲＤ（ＤＳＳ）, ＦＩＰＳ１８６−２”
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ＧＰＵに搭載されている複数の演算ユニットを活用するには、素数の生成を多並列に行う必要がある。しかしながら特許文献１に記載の技術によれば、多並列に素数の生成を行う場合に、複数の演算ユニットが同一の乱数を生成する可能性がある。このことは、素数生成処理速度の低下をもたらしうる。
【０００８】
本発明は、複数の演算ユニットを用いた並列処理において、より高速に素数を求めることを目的とする。
【課題を解決するための手段】
【０００９】
本発明の目的を達成するために、例えば、本発明の情報処理装置は以下の構成を備える。すなわち、
乱数を生成するために用いるシードを保持するメモリと、
前記メモリに格納されているシードを用いて乱数を生成する複数の演算ユニットと、
前記複数の演算ユニットのうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する指示手段とを備え、
前記複数の演算ユニットのそれぞれは、
前記指示手段により乱数発生処理の実行が指示されると、前記メモリに格納されているシードを用いて乱数を生成し、前記メモリに格納されているシードを該生成した乱数で更新する更新手段と、
前記更新手段が生成した乱数が素数であれば、該生成した乱数を出力する出力手段とを備え、
前記指示手段は、乱数発生処理の実行を指示した演算ユニットの更新手段による更新処理が完了したことを検知すると、該演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する
ことを特徴とする。
【発明の効果】
【００１０】
複数の演算ユニットを用いた並列処理において、より高速に素数を求めることができる。
【図面の簡単な説明】
【００１１】
【図１】実施例１におけるシステムの全体構成を説明する図である。
【図２】実施例１におけるＧＰＵの構成を示す図である。
【図３】実施例１におけるＣＰＵの処理フローを説明する図である。
【図４】実施例１におけるＧＰＵの処理フローを説明する図である。
【図５】実施例１におけるシステム全体の機能構成を説明する図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態の一例を図面に基づいて説明する。ただし、本発明の範囲は以下の実施例に限定されるものではない。
【００１３】
＜システム全体構成＞
図１は、本実施例に係る情報処理システム１００の例を示す。情報処理システム１００は、ＣＰＵ１０１、グラフィックボード１０２、主メモリ１０５、メモリコントローラハブ１０６、入出力コントローラハブ１０７、ＮＩＣ１０８、記憶装置１０９、及び外部接続ポート１１０を含む。
【００１４】
ＣＰＵ１０１は、主メモリ１０５又は記憶装置１０９に記録されたプログラム（コンピュータプログラム）に従って、情報処理システム１００の動作の少なくとも一部を制御する中央演算装置である。さらに、ＣＰＵ１０１は物理的な雑音をビット列として取得することができる。物理的な雑音は任意のものでありうるが、例えば記憶装置１０９のシークタイムなどが挙げられる。
【００１５】
グラフィックボード１０２は、ＧＰＵ１０３とＧＰＵメモリ１０４とを含む。グラフィックボード１０２は通常、画像処理に特化した拡張ボードである。ＧＰＵ１０３は、リンク１１８を介してＧＰＵメモリ１０４に接続される。ＧＰＵ１０３は、リンク１１３を介してＣＰＵ１０１からＧＰＵメモリ１０４へと転送されたプログラムに従って、グラフィックボード１０２の動作の少なくとも一部を制御する演算ユニットを有する。ＧＰＵメモリ１０４は、ＧＰＵ１０３を制御するプログラムを格納することができる。ＧＰＵメモリ１０４はまた、ＧＰＵ１０３の動作中にデータを一時的に記憶することができる。ＧＰＵメモリ１０４は、例えばＲＡＭでありうる。
【００１６】
主メモリ１０５は、ＣＰＵ１０１を制御するプログラムを格納することができる。主メモリ１０５はまた、ＣＰＵ１０１の動作中にデータを一時的に記憶することができる。主メモリ１０５は、例えばＲＡＭでありうる。
【００１７】
メモリコントローラハブ１０６は、リンク１１３、１１４、１１５及び１１６を介してそれぞれＣＰＵ１０１、主メモリ１０５、グラフィックボード１０２及び入出力コントローラハブ１０７と接続されている。メモリコントローラハブ１０６は、主メモリ１０５、グラフィックボード１０２及び入出力コントローラハブ１０７の間のデータ転送を制御する。
【００１８】
入出力コントローラハブ１０７は、リンク１１７、１１８及び１１９を介してそれぞれＮＩＣ１０８、記憶装置１０９及び外部接続ポート１１０と接続されている。入出力コントローラハブ１０７は、メモリコントローラハブ１０６、ＮＩＣ１０８、記憶装置１０９及び外部接続ポート１１０の間のデータ転送を制御する。
【００１９】
ＮＩＣ１０８は、ネットワークに接続するための通信インターフェイスである。ＮＩＣ１０８は例えば、有線ＬＡＮ、無線ＬＡＮ、又はＢｌｕｅｔｏｏｔｈ用の通信カード等でありうる。
【００２０】
記憶装置１０９は、ＣＰＵ１０１が実行するプログラム、ＣＰＵ１０１が処理に用いるデータ、及び外部から取得したデータ等を格納する。記憶装置は例えば、ハードディスクのような磁気記憶装置、又はＳＳＤのようなフラッシュメモリでありうる。情報処理システム１００は、複数の記憶装置１０９を有していてもよい。
【００２１】
外部接続ポート１１０は、外部機器を情報処理システム１００に接続するためのポートである。外部接続ポート１１０は、例えばＵＳＢポート、ＩＥＥＥ１３９４ポート、ＨＤＭＩポート等でありうる。この外部接続ポート１１０に入力装置１１１を接続することで、情報処理システム１００は入力装置１１１からデータを取得することができる。情報処理システム１００は、複数の外部接続ポート１１０を有していてもよい。
【００２２】
入力装置１１１は、外部接続ポート１１０を介して情報処理システム１００にデータを入力する機器である。入力装置１１１は例えば、キーボード、マウス等でありうる。出力装置１１２は、情報処理システム１００が出力するデータを視覚的に表示する装置である。出力装置１１２は、グラフィックボード１０２が有するポートに接続されることができる。また出力装置１１２は、外部接続ポート１１０に接続されてもよい。出力装置１１２の例としては、例えば液晶モニタ等が挙げられる。出力装置１１２が接続されるポートの例としては、例えばＨＤＭＩポート等が挙げられる。
【００２３】
リンク１１３、１１４、１１５、１１６、１１７、１１８、及び１１９はシリアルバスである。リンク１１３、１１４、１１５、１１６、１１７、１１８、及び１１９は例えば、ＰＣＩ又はＰＣＩエクスプレス等などのバスでありうる。
【００２４】
以上、本実施例に係る情報処理システム１００として利用可能なハードウェア構成の一例を示した。以上説明された情報処理システム１００は、例えば、パーソナルコンピュータ等を用いて実現することができる。しかしながら、本実施例に係る情報処理システム１００は上述の構成に限定されるものではない。例えば変形例において、情報処理システム１００はグラフィックボード１０２を含まずにＧＰＵ１０３を含んでいてもよい。この場合、ＧＰＵ１０３が主メモリ１０５に対してデータを読み書きできるように、情報処理システム１００を構成すればよい。また、ＣＰＵ１０１にＧＰＵ１０３を統合してもよい。この場合にも、情報処理システム１００はグラフィックボード１０２を有さなくてもよい。他の実施例として、ＣＰＵとＧＰＵとの少なくとも一方として、暗号処理に特化したハードウェアである暗号アクセラレータを用いてもよい。また、ＣＰＵとＧＰＵとの少なくとも一方として、演算処理が可能なＩＰコアを用いてもよい。
【００２５】
＜ＧＰＵ１０３の構成＞
以下、図２を参照してＧＰＵ１０３について詳しく説明する。図２は、本実施例に適用可能なＧＰＵ１０３の構成例を示す。図２において、ＧＰＵ１０３は２つの演算ユニット２０１，２０２を含む。しかしながら、ＧＰＵ１０３が含む演算ユニットの数は２つに限定されない。ＧＰＵ１０３は、２つ以上の演算ユニットを含みうる。演算ユニット２０１及び２０２は、並列動作が可能な演算装置である。例えば演算ユニット２０１及び２０２は、それぞれ別の命令を実行することができ、また別のデータを扱うことができる。
【００２６】
演算ユニット２０１はキャッシュメモリ２０３を含む。演算ユニット２０１は、ＧＰＵメモリ１０４又はキャッシュメモリ２０３に記録されたプログラムに従って、ＧＰＵ１０３内の動作の少なくとも一部を制御する。また、また、演算ユニット２０２はキャッシュメモリ２０４を含む。演算ユニット２０２は、ＧＰＵメモリ１０４又はキャッシュメモリ２０４に記録されたプログラムに従って、ＧＰＵ１０３内の動作の少なくとも一部を制御する。キャッシュメモリ２０３及び２０４は、高速に読み書き可能な小容量メモリである。
【００２７】
＜情報処理システム１００の機能構成＞
以下、図５を参照して、図１に係る情報処理システム１００の機能構成について説明する。本実施例に係る情報処理システム１００は、並列に素数の生成を行うことができる。図５に示すように、情報処理システム１００は演算装置と外部演算装置とを含む。演算装置としては、例えば前述したＣＰＵ１０１を用いることができる。また外部演算装置としては、前述したＧＰＵ１０３を用いることができる。この場合、処理装置０及び処理装置１は、それぞれ演算ユニット２０１及び演算ユニット２０２に対応する。
【００２８】
しかしながら、本実施例で用いられる演算装置及び外部演算装置は、上述のＣＰＵ１０１及びＧＰＵ１０３には限られない。例えば、演算装置１０１又は外部演算装置１０３として、前述した暗号アクセラレータを用いてもよい。以下の説明では、演算装置としてＣＰＵ１０１を用いる。また、外部演算装置としてＧＰＵ１０３を用いる。
【００２９】
図５に示すように、演算装置１０１はシード生成部５０１を備える。また、外部演算装置１０３は保存部５０２、制御部５０３、シード更新部５０４、乱数生成部５０５、及び素数判定部５０６を備える。また、並列に動作可能な演算ユニット２０１，２０２はそれぞれ、シード更新部５０４、乱数生成部５０５、及び素数判定部５０６を備える。以下、これらの各部について説明する。
【００３０】
＜シード生成部５０１＞
以下で、シード生成部５０１について説明する。シード生成部５０１は、乱数の種となるシードの初期値を生成し、生成した初期値をＧＰＵ１０３に出力する。シードの生成方法としては任意の公知の方法を用いることができる。本実施例においては、シードの生成のためにエントロピーを用いる。
【００３１】
本実施例においてエントロピーとは、物理的な雑音をビット列に変換することによって得られる値である。すなわちシード生成部５０１は、熱雑音などの物理的な雑音が蓄積されるエントロピーソースから、シードの生成に必要な分のエントロピーを取得する。シードの生成に必要なエントロピーは、生成する乱数のセキュリティ強度によって異なる。例えばセキュリティ強度が１２８ｂｉｔの乱数を生成するときは、１２８ｂｉｔ以上のエントロピーが必要となる（非特許文献１を参照）。
【００３２】
シード生成部５０１が十分なエントロピーを取得すると、シード生成部５０１は、エントロピーを用いてシードを生成する。例えば、エントロピーに対してハッシュ関数を適用することにより、シードを生成することができる（非特許文献１を参照）。また、エントロピーに対してナンスなどの付加データを追加した後に、ハッシュ関数を適用してもよい（非特許文献１）。また、ハッシュ関数の代わりにブロック暗号アルゴリズムを用いることもできる（非特許文献１）。そしてシード生成部５０１は、生成したシードを保存部５０２に出力する。
【００３３】
シード生成部５０１は、保存部５０２に格納されているシード更新回数及び限界シード更新回数に従って、シードを生成及び出力する。ここでシード更新回数とは、シードの更新回数を表す値である。シード生成部５０１が生成したシードを保存部５０２に格納する際に、シード生成部５０１は、保存部に格納されているシード更新回数を０に初期化する。その後、シード更新部５０４が保存部５０２に格納されているシードを更新する際に、シード更新部５０４は、保存部５０２に格納されているシード更新回数を更新する。
【００３４】
限界シード更新回数（所定回数）は、１つのシードから生成できる乱数の総数を示す。１つのシードを更新しながら多数の乱数を生成すると、乱数の周期性が知られる可能性が高くなる。そこで本実施例においては、１つのシードから生成できる乱数の数が予め定められている。限界シード更新回数は、例えばユーザが設定することができる。
【００３５】
シード生成部５０１は、シード更新回数が限界シード更新回数を超えたと判断すると、保存部５０２に格納されているシードを新しいシードで置き換える。すなわち、シード生成部５０１は、まず保存部５０２のシードを削除する。次にシード生成部５０１は上述のようにエントロピーを用いてシードを生成し、生成したシードを保存部５０２に格納する。そしてシード生成部５０１は、保存部５０２に格納されているシード更新回数を０に初期化する。シード更新回数が限界シード更新回数以下の場合にも、シード生成部５０１は、エントロピーを用いたシードの生成処理を行ってもよい。この場合、シード更新回数が限界シード更新回数を超えたときに、シード生成部５０１は生成されたシードを素早く保存部５０２に格納することができる。
【００３６】
＜保存部５０２＞
保存部５０２は、上述のように、乱数を生成するために用いるシード、シード更新回数、及び限界シード更新回数などのデータを格納（保持）することができる。
【００３７】
＜制御部５０３＞
以下で、制御部５０３について説明する。制御部５０３は、乱数生成部５０５の動作を制御する。特に制御部５０３は、複数の乱数生成部５０５のそれぞれが同一の乱数を生成しないように、乱数生成部５０５を制御（指示）する。本実施例において制御部５０３は、複数の演算ユニット群２０１，２０２のうち何れか１つを選択する。そして、選択した演算ユニットに対して、乱数発生処理の実行を指示する。
【００３８】
具体的には制御部５０３は、保存部５０２に格納されたシード更新回数と、演算ユニット２０１，２０２に予め割り当てられた識別子とに応じて、乱数生成部５０５を制御する。本実施例において制御部５０３は、シード更新回数を演算ユニットの総数で割った余りを参照してこの制御を行う。以降、シード更新回数を演算ユニットの総数で割った余りを「シード更新回数（mod 演算ユニット総数）」と記述する。識別子とは、演算ユニット２０１，２０２を特定する数字である。識別子は、各演算ユニットに対して“０”から順に割り当てられる。本実施例において、演算ユニット２０１は識別子“０”を割り当てられており、演算ユニット２０２は識別子“１”を割り当てられている。
【００３９】
制御部５０３は、保存部５０２に格納されているシード更新回数を参照して、１つの演算ユニットに対し、保存部５０２に格納されているシードを用いて乱数を生成させる。具体的には制御部５０３は、シード更新回数（mod 演算ユニット総数）に一致する識別子が割り当てられた演算ユニットに対し、保存部５０２に格納されているシードを用いて乱数を生成させる。このようにして、並列動作を行う演算ユニット２０１，２０２が同一の乱数を生成し、演算ユニット２０１，２０２が同一の乱数に対して素数判定を行うことを回避できる。
【００４０】
より一般的に、情報処理システム１００がＮ個の演算ユニットを有している場合について説明する。この場合、それぞれの演算ユニットには１番からＮ番までの番号（識別子）が付される。そして、「シード更新回数（mod 演算ユニット総数）」と一致する番号を有する演算ユニットに対し、制御部５０３は保存部５０２に格納されているシードを用いて乱数を生成させる。
【００４１】
＜シード更新部５０４＞
以下で、シード更新部５０４について説明する。シード更新部５０４は、保存部５０２に格納されているシードを更新する。またシード更新部５０４は、保存部５０２に格納されているシードを更新する際に、保存部５０２に格納されているシード更新回数を変更する。
【００４２】
乱数生成器は通常、同一のシードからは同じ乱数を生成する。そこで、複数の乱数を生成するために、シードが更新される。つまりシード更新部５０４は、乱数生成部５０５が乱数を生成する度に、保存部５０２に格納されているシードを更新する。この際シード更新部は、乱数生成部５０５が生成した乱数を用いて、保存部５０２に格納されているシードを更新することができる（非特許文献１を参照）。例えばシード更新部５０４は、乱数生成部５０５が生成した乱数で、保存部５０２に格納されているシードを置換すればよい。またシード更新部５０４は、保存部５０２に格納されているシードを更新する際に、保存部５０２に格納されているシード更新回数を更新する。例えば、シード更新回数をインクリメントすればよく、具体的にはシード更新回数に１を加えればよい。
【００４３】
＜乱数生成部５０５＞
以下で、乱数生成部５０５について説明する。乱数生成部５０５は、制御部５０３に指示されると、保存部５０２に格納されているシードと、乱数生成器とを用いて乱数を生成する。そして乱数生成部５０５は、生成した乱数を素数判定部５０６に出力する。乱数生成器は、シードから乱数を生成する。乱数生成器は任意の公知の方法を用いて乱数を生成することができ、例えば、ハッシュ関数やブロック暗号アルゴリズムなどを用いることができる（非特許文献１を参照）。なお、保存部５０２に格納されているシード更新回数が限界シード更新回数を超えている場合には、乱数生成部５０５は乱数の生成を行わず、シード生成部５０１によって新しいシードが保存部５０２に格納されるのを待つ。
【００４４】
＜素数判定部５０６＞
以下で、素数判定部５０６について説明する。素数判定部５０６は、乱数生成部５０５が出力した乱数が素数であるか否かを判定する。素数判定には任意の公知の方法を用いることができ、例えばミラーラビン法を用いることができる（非特許文献２）。
【００４５】
素数判定部５０６は、乱数生成部５０５が出力した乱数が素数であると判断すると、素数生成が完了したことをＣＰＵ１０１に通知する。本実施例において素数判定部５０６は、乱数が素数であると判断すると、ＣＰＵ１０１に生成された素数を転送する。また素数判定部５０６は、乱数が素数であると判断すると、保存部５０２に格納されている素数生成完了フラグをＯＮにする。素数生成完了フラグは、素数の生成が完了した時にＯＮとなり、素数の生成が完了していないときにＯＦＦとなるフラグである。素数生成完了フラグを参照することにより、ＣＰＵ１０１は素数が生成されたことを知ることができる。
【００４６】
＜本実施例に係る処理フロー＞
以下、図３及び図４を参照して、本実施例に係る素数の生成処理のフローを説明する。本実施例に係る素数の生成処理は、ＣＰＵ１０１での処理とＧＰＵ１０３での処理とに分けられる。そこで本明細書では、ＣＰＵ１０１における処理フローと、ＧＰＵ１０３における処理フローとについて、それぞれ説明する。
【００４７】
＜ＣＰＵ１０１における処理フロー＞
図３は本実施例におけるＣＰＵ１０１で実行される処理フローを示すフローチャートである。ステップＳ３０１においてシード生成部５０１は、保存部５０２に格納されている素数生成完了フラグをＯＦＦにする。ステップＳ３０２においてシード生成部５０１は、エントロピーソースにシードを作るのに十分なエントロピーが溜まっているか否かを確認する。所定量のエントロピーが溜まっていない場合、シード生成部５０１は所定量のエントロピーがエントロピーソースに溜まるのを待つ。所定量のエントロピーが溜まっている場合、処理はステップＳ３０３に進む。
【００４８】
ステップＳ３０３においてシード生成部５０１は、エントロピーソースからエントロピーを取得し、上述のようにシードを生成する。ステップＳ３０４においてシード生成部５０１は、限界シード更新回数を設定する。具体的にはシード生成部５０１は、予め定められた限界シード更新回数を保存部５０２に格納すればよい。ステップＳ３０５においてシード生成部５０１は、ステップＳ３０３で生成したシードを保存部５０２に格納する。限界シード更新回数及び生成されたシードは、メモリコントローラハブ１０６を介してＧＰＵ１０３へと転送される。
【００４９】
ステップＳ３０６においてシード生成部５０１は、ＧＰＵ１０３において素数の生成が完了したか否かを判定する。具体的には、保存部５０２に格納されている素数生成完了フラグがＯＮであるか否かを判定すればよい。素数生成完了フラグがＯＮであれば、ステップＳ３０７においてシード生成部はメモリコントローラハブ１０６を介して保存部５０２から生成された素数を取得する。そしてシード生成部５０１は、ＧＰＵ１０３の処理を停止させる。素数生成完了フラグがＯＦＦであれば、処理はステップＳ３０８に進む。
【００５０】
ステップＳ３０８においてシード生成部５０１は、シードの再生成が必要であるか否かを判定する。具体的には上述のように、シード更新回数が限界シード更新回数を超える場合に、シード生成部５０１はシードの再生成が必要であると判定する。シードの再生成が必要である場合、処理はステップＳ３０２に戻る。シードの再生成が必要ではない場合、処理はステップＳ３０６に戻る。
【００５１】
＜ＧＰＵ１０３における処理フロー＞
ＧＰＵ１０３においては、ＧＰＵ１０３の構成要素である演算ユニット２０１及び演算ユニット２０２が並列に処理を行う。演算ユニット２０１と２０２とは同じフローに従って処理を行う。したがって、本明細書においては演算ユニット２０１の処理フローについてのみ説明する。
【００５２】
図４は、本実施例に係る演算ユニット２０１で実行される処理フローを示すフローチャートである。ステップＳ４０１において乱数生成部５０５は、ＣＰＵ１０１から転送されたシードが保存部５０２に格納されているか否かを確認する。シードが格納されていない場合、乱数生成部５０５は保存部５０２にシードが格納されるまで待つ。シードが格納されている場合、ステップＳ４０２において乱数生成部５０５は、格納されているシードで乱数生成器を初期化する。
【００５３】
ステップＳ４０３において乱数生成部５０５は、保存部５０２に格納されているシード更新回数と限界シード更新回数とを比較する。シード更新回数が限界シード更新回数を超えている場合、処理はステップＳ４０１に戻る。超えていない場合、処理はステップＳ４０４に進む。
【００５４】
ステップＳ４０４において乱数生成部５０５は、現在保存部５０２に格納されているシードを用いて乱数を生成してもよいかを、制御部５０３に問い合わせる。制御部５０３の詳細な処理については後述する。乱数を生成してはいけない場合、処理はステップＳ４０３に戻る。乱数を生成してもよい場合、処理はステップＳ４０５に進む。このステップＳ４０４により、複数の演算ユニットが同一のシードを用いて乱数を生成することが防止される。
【００５５】
ステップＳ４０５において乱数生成部５０５は、保存部５０２にシードが格納されているか否かを再び確認する。シードが格納されていない場合、処理はステップＳ４０１に戻る。シードが格納されている場合、ステップＳ４０６において乱数生成部５０５は、保存部５０２に格納されているシードを用いて乱数を生成する。
【００５６】
ステップＳ４０７において乱数生成部５０５は、ステップＳ４０６で生成された乱数を用いて、保存部５０２に格納されているシードを更新する。また乱数生成部５０５は、保存部５０２に格納されているシード更新回数をインクリメントする。ステップＳ４０８において素数判定部５０６は、ステップＳ４０６において生成された乱数が素数かどうかを判定する。生成された乱数が素数でないと判定された場合、処理はステップＳ４０３に戻る。生成された乱数が素数であると判定された場合、ステップＳ４０９において素数判定部５０６は保存部５０２に格納されている素数生成完了フラグをＯＮにし、処理は終了する。
【００５７】
次に、複数の演算ユニット２０１，２０２が同一のシードを用いて乱数を生成することを防止するステップＳ４０４について詳しく説明する。上述のように、演算ユニット２０１は識別子として”０”を有し、演算ユニット２０２は識別子として”１”を有する。また、本実施例において演算ユニット総数は”２”である。したがって、「シード更新回数(mod 演算ユニット総数)」は”０”か”１”かの何れかの値を持つ。すなわち、演算ユニット２０１についての識別子（”０”）が、「シード更新回数(mod 演算ユニット総数)」と一致しない場合、演算ユニット２０２についての識別子（”１”）は、「シード更新回数(mod 演算ユニット総数)」と一致する。また、この逆も成り立つ。
【００５８】
ステップＳ４０４において制御部５０３は、演算ユニットの識別子と「シード更新回数(mod 演算ユニット総数)」とが一致する場合に、演算ユニットに対して乱数の生成を許可する。演算ユニット２０１は、制御部５０３によって乱数の生成を許可されるまで、ステップＳ４０３〜Ｓ４０４を繰り返す。すなわち演算ユニット２０１は、演算ユニット２０１の識別子とシード更新回数(mod 演算ユニット総数)が一致するまで、ステップＳ４０３〜Ｓ４０４を繰り返す。
【００５９】
一方で演算ユニット２０１が乱数の生成を許可されていない際に、演算ユニット２０２は乱数の生成を許可されている。従って演算ユニット２０２は乱数を生成し、生成された乱数を用いて保存部５０２に格納されているシードを更新するとともに、シード更新回数に１を加える。シード更新回数が１つ増えると、演算ユニット２０１の識別子とシード更新回数(mod 演算ユニット総数)が一致する。このため、演算ユニット２０１は制御部５０３によって乱数の生成を許可される。一方で、今度は演算ユニット２０２の識別子とシード更新回数(mod 演算ユニット総数)が不一致となる。このため、演算ユニット２０２は保存部５０２に格納されているシードが更新されるまで、乱数の生成を許可されない。
【００６０】
このように、制御部５０３は保存部５０２に格納されているシード更新回数を監視する。そして制御部５０３は、シード更新回数の増加を検出することにより、ある演算ユニットによる乱数生成処理及びシード更新処理が終了したことを検知できる。制御部５０３は、ある演算ユニットによってシードが更新されたことを検出すると、別の演算ユニットに乱数の生成を許可する。このような処理により、演算ユニット２０１，２０２が同一のシードを用いて乱数を生成することを回避することができる。もっとも制御部５０３は、シードを更新した演算ユニットを特定する情報を参照して、別の演算ユニットに乱数の生成を許可してもよい。また制御部５０３は、演算ユニットが処理を行っているか否か、例えば素数判定処理を完了しているか否かを示すフラグを参照して、処理を行っていない１つの演算ユニットに対して乱数の生成を許可してもよい。このように制御部５０３は、様々な方法を用いて、１つのシードを用いた乱数の生成を特定の演算ユニットのみに行わせるように、演算ユニットを制御することができる。
【００６１】
以上説明したように本実施例によれば、ＣＰＵはエントロピーソースを用いてシードの生成処理を行う。また、ＧＰＵは並列にシードから乱数の生成及び素数の判定を行う。このように、エントロピーソースを持たないＧＰＵが素数を生成することが可能となる。本実施例によれば、同一の乱数に対して複数のＧＰＵが素数判定を行うことが回避される。このため、無駄な素数判定処理を回避することができる。さらに、負荷の大きい素数判定をＧＰＵで並列に処理できるため、ＣＰＵの負荷を下げることができ、かつ素数生成を高速化することが可能となる。
【００６２】
＜変形例１＞
上述の実施例は一例に過ぎず、別の実施例を採用することもできる。例えば、実施例１において乱数生成部５０５は、保存部５０２に格納されているシードを用いて乱数を生成してもよいかを、制御部５０３に問い合わせた。しかしながら素数判定部５０６が、素数判定を行ってもよいかを、制御部５０３に問い合わせてもよい。この場合制御部５０３は、実施例１において乱数生成部５０５を制御したのと同様に、素数判定部５０６を制御することができる。またこの場合、乱数生成部５０５は問い合わせを行うことなく、保存部５０２に格納されているシードを用いて乱数を生成してもよい。こうすることにより、複数の演算ユニットが、同一のシードを用いて生成された同一の乱数について素数であるか否かを判定することを回避できる。
【００６３】
＜変形例２＞
各演算ユニット２０１，２０２は別々のシードを用いてもよい。つまり、演算ユニットのそれぞれに対応付けられたシードが、保存部５０２に格納される。この場合、シード生成部５０１が生成した１つのシードが、それぞれの演算ユニットによって共通に用いられてもよい。各演算ユニット２０１，２０２は、対応付けられたシードを用いて、上述のように乱数生成、シード更新、及び素数判定を行う。
【００６４】
このとき素数判定部５０６は、シード更新回数(mod 演算ユニット総数)と識別子とが一致しない時には、乱数生成部５０５が生成した乱数が素数であるか否かを判定しない。こうすることにより、複数の演算ユニットが、同一のシードを用いて生成された同一の乱数について素数であるか否かを判定することを回避できる。
【００６５】
＜変形例３＞
乱数生成部５０５が、保存部５０２に格納されているシードを用いて乱数を生成してもよいかを、制御部５０３に問い合わせることは必ずしも必須ではない。例えば乱数生成部５０５は、保存部５０２に格納されているシード更新回数を確認し、保存部５０２に現在格納されているシードを用いて乱数を生成してもよいかを判定することができる。この判定は、制御部５０３と同様に行うことができる。
【００６６】
＜変形例４＞
各演算ユニット２０１，２０２は、ステップＳ４０８において素数を見つけた後に、その素数を用いて鍵生成処理を行ってもよい。この場合情報処理システム１００は、並列に複数の鍵を生成することができる。
【００６７】
（他の実施形態）
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）をネットワーク又は各種記憶媒体を介してシステム或いは装置に供給する。そして、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムコードを読み出して実行する。この場合、そのプログラム、及び該プログラムを記憶した記憶媒体は本発明を構成することになる。
【特許請求の範囲】
【請求項１】
乱数を生成するために用いるシードを保持するメモリと、
前記メモリに格納されているシードを用いて乱数を生成する複数の演算ユニットと、
前記複数の演算ユニットのうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する指示手段とを備え、
前記複数の演算ユニットのそれぞれは、
前記指示手段により乱数発生処理の実行が指示されると、前記メモリに格納されているシードを用いて乱数を生成し、前記メモリに格納されているシードを該生成した乱数で更新する更新手段と、
前記更新手段が生成した乱数が素数であれば、該生成した乱数を出力する出力手段とを備え、
前記指示手段は、乱数発生処理の実行を指示した演算ユニットの更新手段による更新処理が完了したことを検知すると、該演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する
ことを特徴とする情報処理装置。
【請求項２】
シードの初期値を取得し、前記メモリに格納する取得手段をさらに備え、
前記メモリは、前記取得手段によって初期値が格納されてから、シードが更新された回数を記録し、
前記回数が増加した際に、前記指示手段は前記更新処理が完了したことを検知する
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記情報処理装置はＮ個の前記演算ユニットを備え、それぞれの演算ユニットは１番からＮ番までの番号を有し、
前記更新手段は、前記メモリに記録されている回数をＮで割った余りを番号として有する演算ユニットに対して、前記乱数発生処理の実行を指示する
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記指示手段は、前記回数が所定回数を超える場合に、前記取得手段に新たな初期値を取得して前記メモリに格納させることを特徴とする、請求項２又は３に記載の情報処理装置。
【請求項５】
前記更新手段は、前記回数が前記所定回数を超えている場合には、前記メモリに格納されているシードを取得せず、前記新たな初期値が前記メモリに格納されるのを待つことを特徴とする、請求項４に記載の情報処理装置。
【請求項６】
乱数を生成するために用いるシードを保持するメモリと、前記メモリに格納されているシードを用いて乱数を生成する複数の演算ユニットと、を備える情報処理装置が行う情報処理方法であって
前記情報処理装置の指示手段が、前記複数の演算ユニットのうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する指示工程と、
前記演算ユニットの更新手段が、前記指示工程で乱数発生処理の実行が指示されると、前記メモリに格納されているシードを用いて乱数を生成し、前記メモリに格納されているシードを該生成した乱数で更新する更新工程と、
前記演算ユニットの出力手段が、前記更新工程で生成した乱数が素数であれば、該生成した乱数を出力する出力工程とを備え、
前記指示工程では、乱数発生処理の実行を指示された演算ユニットによる更新処理が完了したことを検知すると、該演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する
ことを特徴とする情報処理方法。
【請求項７】
コンピュータを、請求項１乃至５の何れか１項に記載の情報処理装置の各手段として機能させるための、コンピュータプログラム。
【請求項１】
乱数を生成するために用いるシードを保持するメモリと、
前記メモリに格納されているシードを用いて乱数を生成する複数の演算ユニットと、
前記複数の演算ユニットのうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する指示手段とを備え、
前記複数の演算ユニットのそれぞれは、
前記指示手段により乱数発生処理の実行が指示されると、前記メモリに格納されているシードを用いて乱数を生成し、前記メモリに格納されているシードを該生成した乱数で更新する更新手段と、
前記更新手段が生成した乱数が素数であれば、該生成した乱数を出力する出力手段とを備え、
前記指示手段は、乱数発生処理の実行を指示した演算ユニットの更新手段による更新処理が完了したことを検知すると、該演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する
ことを特徴とする情報処理装置。
【請求項２】
シードの初期値を取得し、前記メモリに格納する取得手段をさらに備え、
前記メモリは、前記取得手段によって初期値が格納されてから、シードが更新された回数を記録し、
前記回数が増加した際に、前記指示手段は前記更新処理が完了したことを検知する
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記情報処理装置はＮ個の前記演算ユニットを備え、それぞれの演算ユニットは１番からＮ番までの番号を有し、
前記更新手段は、前記メモリに記録されている回数をＮで割った余りを番号として有する演算ユニットに対して、前記乱数発生処理の実行を指示する
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記指示手段は、前記回数が所定回数を超える場合に、前記取得手段に新たな初期値を取得して前記メモリに格納させることを特徴とする、請求項２又は３に記載の情報処理装置。
【請求項５】
前記更新手段は、前記回数が前記所定回数を超えている場合には、前記メモリに格納されているシードを取得せず、前記新たな初期値が前記メモリに格納されるのを待つことを特徴とする、請求項４に記載の情報処理装置。
【請求項６】
乱数を生成するために用いるシードを保持するメモリと、前記メモリに格納されているシードを用いて乱数を生成する複数の演算ユニットと、を備える情報処理装置が行う情報処理方法であって
前記情報処理装置の指示手段が、前記複数の演算ユニットのうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する指示工程と、
前記演算ユニットの更新手段が、前記指示工程で乱数発生処理の実行が指示されると、前記メモリに格納されているシードを用いて乱数を生成し、前記メモリに格納されているシードを該生成した乱数で更新する更新工程と、
前記演算ユニットの出力手段が、前記更新工程で生成した乱数が素数であれば、該生成した乱数を出力する出力工程とを備え、
前記指示工程では、乱数発生処理の実行を指示された演算ユニットによる更新処理が完了したことを検知すると、該演算ユニットとは別の演算ユニット群のうち何れか１つを選択し、該選択した演算ユニットに対して前記メモリに格納されているシードを用いた乱数発生処理の実行を指示する
ことを特徴とする情報処理方法。
【請求項７】
コンピュータを、請求項１乃至５の何れか１項に記載の情報処理装置の各手段として機能させるための、コンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１３−２９６１８（Ｐ２０１３−２９６１８Ａ）
【公開日】平成２５年２月７日（２０１３．２．７）
【国際特許分類】
【出願番号】特願２０１１−１６４７６５（Ｐ２０１１−１６４７６５）
【出願日】平成２３年７月２７日（２０１１．７．２７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２５年２月７日（２０１３．２．７）
【国際特許分類】
【出願日】平成２３年７月２７日（２０１１．７．２７）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｂｌｕｅｔｏｏｔｈ
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]