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