素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法
【課題】２のべき乗長以外の素数を確定的な素数判定（生成）手法を用いて効率的に生成すること。
【解決手段】所望の素数Ｐnのビット長の指定を受け付け、指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を事前に算出する。そして、算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用して、素数Ｐiのビット長より長いビット長でかつ素数Ｐiより大きな値の素数Ｐi+1を順次生成することにより、最終的に所望の素数Ｐnを生成することができる。
【解決手段】所望の素数Ｐnのビット長の指定を受け付け、指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を事前に算出する。そして、算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用して、素数Ｐiのビット長より長いビット長でかつ素数Ｐiより大きな値の素数Ｐi+1を順次生成することにより、最終的に所望の素数Ｐnを生成することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、公開鍵暗号方式におけるデータの暗号化／復号化に使用される公開鍵または暗号鍵を生成する素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法に関する。
【背景技術】
【０００２】
公開鍵暗号（たとえば、ＲＳＡ暗号、ＥｌＧａｍａｌ暗号など）では、データの暗号化／復号化に使用する鍵（公開鍵、秘密鍵）を生成するために、素数が用いられることが多い。素数を生成する手法として、「確率的な手法による素数生成」および「確定的な手法による素数生成」が存在している。
【０００３】
これら手法のうち、前者は、生成された値が極めて高い確率で素数となるが、素数であることは保証されない手法である。また、後者は、生成された値が確実に素数であることが保証される手法である。このため、高度な安全性が要求されるシステムでは、後者の手法が採用されている。
【０００４】
これまでは、ＲＳＡ暗号などでは、公開鍵の鍵長（ビット長）として、５１２［ｂｉｔ］，１０２４［ｂｉｔ］など「２のべき乗長の鍵長」が使用されることが多かったが、近年、セキュリティシステムの多様化などにより、「２のべき乗長以外の鍵長」が使用される機会が増えてきている。
【０００５】
一般に、「２のべき乗長の鍵長」の公開鍵を生成するためには「２のべき乗長の素数」が必要となる。一方で、「２のべき乗長以外の鍵長」の公開鍵を生成するためには「２のべき乗長以外の素数」が必要となる。
【０００６】
「２のべき乗長の素数」を生成する確定的な手法としては、たとえば、Ｐｏｃｋｌｉｎｇｔｏｎの素数判定法を利用して、小さい値の素数から大きい値の素数を順次生成する素数生成手法が知られている。
【０００７】
ここで、Ｐｏｃｋｌｉｎｇｔｏｎの素数判定法（たとえば、下記非特許文献１参照。）を利用した素数生成手法（以下、「第１の手法」という）により、「２のべき乗長の素数」を生成する処理手順について説明する。
【０００８】
（１）ｒ＜ｐとなる乱数ｒを生成する。（ｐ：２のべき乗長の素数）
（２）ｐ2＝２×ｒ×ｐ＋１を導出する。
（３）ｐ2が所定の条件を満たしている場合（Ｐｏｃｋｌｉｎｇｔｏｎ法による素数判定 法）、ｐ2は素数となる。ｐ2が所定の条件を満たしていない場合、（１）に戻り、 一連の処理をやり直す。なお、所定の条件には、たとえば、非特許文献１のｐ１４４ ．４．４０に記載された条件を用いることができる。
（４）ｐ2が最終的に求めたいビット長の素数となっていない場合、ｐ＝ｐ2として（１ ）に戻り、一連の処理を繰り返す。
【０００９】
この第１の手法によれば、（２）の処理により、ｐのビット長よりも長いビット長かつｐより大きな値のｐ2を生成することができる。このため、（４）において、ｐ2を新たにｐと置き換えて、（１）からの処理を繰り返し実行することにより、長いビット長の素数を順次生成することができる。
【００１０】
ただし、（１）において、ｒが小さいとｐ2のビット長がｐのビット長に比べてあまり大きくならない。このため、効率よく長いビット長の素数を生成するために、たとえば、ｐ2のビット長がｐのビット長の約２倍となるように生成する（たとえば、３２［ｂｉｔ］→６４［ｂｉｔ］→１２８［ｂｉｔ］→・・・）。
【００１１】
このように、第１の手法によれば、（１）〜（４）の処理を繰り返しおこなうことにより、「２のべき乗長の素数」を効率的に生成することができる。
【００１２】
つぎに、３０数ビット程度の短いビット長の素数を生成する第２の手法について説明する。以下、Ｑ［ｂｉｔ］の短いビット長の素数を生成する第２の手法の処理手順を示す。
【００１３】
（１）２［ｂｉｔ］〜Ｑ／２［ｂｉｔ］によって表現可能な素数を事前に計算し、その計 算結果をテーブルに保持しておく。
（２）Ｑ［ｂｉｔ］の乱数Ｒを生成する。
（３）（２）で生成された乱数Ｒを（１）のテーブルに保持されている各要素で除算し、 割り切れなければ乱数Ｒが求める素数となる。また、割り切れたら（２）に戻り、新 たな乱数Ｒを生成して、処理を繰り返す。なお、本出願においては、短い素数を生成 する手法は上記第２の手法に限らず、いかなる手法を用いてもよい。
【００１４】
つぎに、第１の手法を拡張することにより、「２のべき乗長以外の素数」を生成する第３の手法について説明する。以下、「２のべき乗長以外の素数」として、７６８［ｂｉｔ］のビット長の素数を例に挙げて説明する。
【００１５】
まず、第１の手法により、２のべき乗長、かつ、生成したい素数のビット長を超えない素数を生成する。具体的には、まず、３２［ｂｉｔ］→６４［ｂｉｔ］→１２８［ｂｉｔ］→２５６［ｂｉｔ］→５１２［ｂｉｔ］までは第１の手法により、ｐ2のビット長がｐのビット長の約２倍となるように素数を順次生成する。そして、５１２［ｂｉｔ］→７６８［ｂｉｔ］の素数を生成するために、第１の手法の（２）の式にビット長の短い乱数ｒを代入して、ｐ2＝７６８［ｂｉｔ］を生成する。
【００１６】
このように、第３の手法によれば、「２のべき乗長の素数」を生成する処理を繰り返しおこない、最後に、乱数ｒのビット長を調整してｐ2を生成することにより、所望のビット長（２のべき乗長以外）の素数を生成することができる。
【００１７】
【非特許文献１】ＨＡＮＤＢＯＯＫ ｏｆ ＡＰＰＬＩＥＤ ＣＲＹＰＴＯＧＲＡＰＨＹ（Ａｌｆｒｅｄ Ｊ．Ｍｅｎｅｚｅｓ， Ｐａｕｌ Ｃ．ｖａｎ Ｏｏｒｓｃｈｏｔ， Ｓｃｏｔｔ Ａ．Ｖａｎｓｔｏｎｅ． １９９７ ＣＲＣ Ｐｒｅｓｓ）
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかしながら、上述した非特許文献１による従来技術によれば、「２のべき乗長以外の素数」を確定的な素数判定手法を用いて効率的に生成することができないため、たとえば、高度な安全性が要求されるシステムに使用するための「２のべき乗長以外の鍵長」の公開鍵、暗号鍵を生成することができないという問題があった。
【００１９】
また、上述した第３の手法によれば、「２のべき乗長の素数」よりもある程度長いビット長（たとえば、７６８［ｂｉｔ］）の「２のべき乗長以外の素数」を確定的に生成することができる。しかしながら、「２のべき乗長＋数ビット」のビット長の素数を生成することは非常に困難であるという問題があった。
【００２０】
ここで、従来技術の第３の手法の問題点を具体的に説明する。以下、「２のべき乗長以外の素数」として、「２のべき乗長＋数ビット」＝５１２＋２＝５１４［ｂｉｔ］のビット長の素数を生成する場合を例に挙げて説明する。
【００２１】
まず、上述した第２の手法により、３２［ｂｉｔ］の素数を生成する。このあと、第１の手法により、２のべき乗長、かつビット長が５１４［ｂｉｔ］を超えない素数を生成する。この結果、ビット長が５１２［ｂｉｔ］の素数が生成される（３２［ｂｉｔ］→６４［ｂｉｔ］→１２８［ｂｉｔ］→２５６［ｂｉｔ］→５１２［ｂｉｔ］）。
【００２２】
つぎに、残りのビット長分（２［ｂｉｔ］）について、乱数ｒのビット長を調整して生成する。ここでは、第１の手法の手順（２）において、ｐのビット長が５１２［ｂｉｔ］となり、ｐ2のビット長が５１４［ｂｉｔ］となるためには、手順（１）で生成する乱数ｒのビット長を２［ｂｉｔ］以内とする必要がある。すなわち、乱数ｒの取り得る値は『０，１，２，３』のいずれかとなる。
【００２３】
これにより、第１の手法によって生成されるｐ2の値は４種類となる。ここで、ビット長が５１４［ｂｉｔ］の値をランダムに選択したときに、その値が素数である確率は約１／２9となる。このため、第３の手法によって５１４［ｂｉｔ］のビット長の素数を生成することができる確率は約４／２9となり、一回の処理で所望の素数を生成することが非常に難しい。
【００２４】
このため、前段の処理に戻り、５１２［ｂｉｔ］のビット長の素数を生成し、５１４［ｂｉｔ］のビット長の値が素数となるまでこの処理を繰り返しおこなう必要がある。このように、第３の手法によれば、所望のビット長の素数を生成するためのやり直し回数（上記例では約２9回）が非常に多くなってしまい、素数生成処理にかかる作業時間および作業負荷が著しく増大してしまうという問題があった。
【００２５】
この発明は、上述した従来技術による問題点を解消するため、任意のビット長の素数を確定的に、かつ、効率的に生成することができる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法を提供することを目的とする。
【課題を解決するための手段】
【００２６】
上述した課題を解決し、目的を達成するため、この発明にかかる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法は、素数Ｐnのビット長の指定を受け付け、指定された素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出し、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成することを特徴とする。
【００２７】
また、上記発明において、算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、当該各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝を生成し、前記素数Ｐ1のビット長によって特定される素数を生成し、乱数｛ｒ1，…，ｒn-1｝を用いて、前記素数Ｐiと前記乱数ｒiとを乗算することにより、素数Ｐnを生成することとしてもよい。
【００２８】
これらの発明によれば、素数Ｐnを生成する前に途中で生成されることとなる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を予め算出しておくことにより、素数Ｐn-1から素数Ｐnを生成する際のやり直し回数を低減させることができる。
【００２９】
また、上記発明において、２ビット以上のビット長によって表現可能な素数を記憶する素数テーブルを参照することにより、前記素数Ｐ1のビット長によって特定される素数を生成することとしてもよい。
【００３０】
この発明によれば、３０数ビット程度以内の短いビット長の素数を確定的に生成することができる。
【００３１】
また、上記発明において、前記乱数ｒiのビット長より前記素数Ｐiのビット長が長くなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。
【００３２】
また、上記発明において、前記Ｐi+1のビット長が前記素数Ｐiのビット長の２倍程度の長さとなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。
【００３３】
また、上記発明において、Ｌｅｎｇｔｈ（Ｐi）＝[Ｌｅｎｇｔｈ（Ｐi+1）＋１]／２＋１により、前記素数Ｐnのビット長に従って、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【００３４】
また、上記発明において、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐi+1）／２＋１により、前記素数Ｐnのビット長に従って、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【００３５】
これらの発明によれば、短いビット長の素数から、より長いビット長の素数を効率的に生成することができる。
【００３６】
また、上記発明において、前記素数Ｐ1のビット長が３０数ビット程度の長さとなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。
【００３７】
この発明によれば、簡単な手法によって確定的に素数Ｐ1を生成することができる程度の短いビット長となるまで素数｛Ｐ1，…，Ｐn-1｝の各ビット長の算出処理を繰り返し実行させることができる。
【発明の効果】
【００３８】
本発明にかかる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法によれば、任意のビット長の素数を確定的に、かつ、効率的に生成することができるという効果を奏する。
【発明を実施するための最良の形態】
【００３９】
以下に添付図面を参照して、この発明にかかる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法の好適な実施の形態を詳細に説明する。
【００４０】
（素数生成装置のハードウェア構成）
まず、この発明の実施の形態にかかる素数生成装置のハードウェア構成について説明する。図１は、この発明の実施の形態にかかる素数生成装置のハードウェア構成を示すブロック図である。
【００４１】
図１において、素数生成装置１００は、コンピュータ本体１１０と、入力装置１２０と、出力装置１３０と、から構成されており、不図示のルータやモデムを介してＬＡＮ，ＷＡＮやインターネットなどのネットワーク１４０に接続可能である。
【００４２】
コンピュータ本体１１０は、ＣＰＵ，メモリ，インターフェースを有する。ＣＰＵは、素数生成装置１００の全体の制御を司る。メモリは、ＲＯＭ，ＲＡＭ，ＨＤ，光ディスク１１１，フラッシュメモリから構成される。メモリはＣＰＵのワークエリアとして使用される。
【００４３】
また、メモリには各種プログラムが格納されており、ＣＰＵからの命令に応じてロードされる。ＨＤおよび光ディスク１１１はディスクドライブによりデータのリード／ライトが制御される。また、光ディスク１１１およびフラッシュメモリはコンピュータ本体１１０に対し着脱自在である。インターフェースは、入力装置１２０からの入力、出力装置１３０への出力、ネットワーク１４０に対する送受信の制御をおこなう。
【００４４】
また、入力装置１２０としては、キーボード１２１、マウス１２２、スキャナ１２３などがある。キーボード１２１は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式であってもよい。マウス１２２は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。スキャナ１２３は、画像を光学的に読み取る。読み取られた画像は画像データとして取り込まれ、コンピュータ本体１１０内のメモリに格納される。なお、スキャナ１２３にＯＣＲ機能を持たせてもよい。
【００４５】
また、出力装置１３０としては、ディスプレイ１３１、スピーカ１３２、プリンタ１３３などがある。ディスプレイ１３１は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。また、スピーカ１３２は、効果音や読み上げ音などの音声を出力する。また、プリンタ１３３は、画像データや文書データを印刷する。
【００４６】
（素数テーブル２００のデータ構造）
つぎに、素数テーブル２００のデータ構造について説明する。図２は、素数テーブル２００のデータ構造を示す説明図である。図２において、素数テーブル２００は、２［ｂｉｔ］〜１７［ｂｉｔ］までの各ビット数によって表現可能な素数を保持している。
【００４７】
たとえば、２［ｂｉｔ］の素数である２，３を保持しており、３［ｂｉｔ］の素数である２，３，５，７を保持している。すなわち、素数テーブル２００は、１７［ｂｉｔ］のビット数によって表現可能なすべての素数を保持していることとなる。なお、１７［ｂｉｔ］のビット数によって表現可能な最大の素数をＮと表記する。
【００４８】
この素数テーブル２００は、たとえば、後述する素数生成装置１００の素数生成部３０３によって素数Ｐ1を生成する場合に用いられる。具体的には、［背景技術］で示した第２の手法により、３０数ビット程度以内の短いビット長の素数Ｐ1を生成する場合に用いる。一般的に、テーブルに１７［ｂｉｔ］までの素数を準備する場合、３４［ｂｉｔ］までの素数を生成することができる。
【００４９】
（素数生成装置１００の機能的構成）
つぎに、この発明の実施の形態にかかる素数生成装置１００の機能的構成について説明する。図３は、この発明の実施の形態にかかる素数生成装置１００の機能的構成を示すブロック図である。図３において、素数生成装置１００は、素数テーブル２００と、受付部３０１と、算出部３０２と、素数生成部３０３と、乱数生成部３０４と、出力部３０５と、を備えている。
【００５０】
これら各機能３０１〜３０５は、メモリに格納された当該機能に関するプログラムをＣＰＵに実行させることにより、当該機能を実現することができる。また、各機能３０１〜３０５からの出力データはメモリに保持される。また、図３中矢印で示した接続先の機能的構成は、接続元の機能からの出力データをメモリから読み込んで、当該機能に関するプログラムをＣＰＵに実行させる。
【００５１】
図３において、まず、受付部３０１は、素数Ｐnのビット長の指定を受け付ける機能を有する。具体的には、図１に示したキーボード１２１やマウス１２２などの入力装置１２０をユーザが操作することで、素数Ｐnのビット長の指定を受け付けて、メモリに保持する。たとえば、素数Ｐnのビット長をあらわす任意の数字（たとえば、５１４，１０２８など）をユーザが入力することにより、素数Ｐnのビット長を指定する。
【００５２】
この素数Ｐnは、たとえば、ＲＳＡ暗号などの公開鍵暗号に使用する鍵（公開鍵、秘密鍵）を生成する場合に必要となる素数である。一般に、鍵長が長いほど暗号強度が高くなるため、高度な安全性が要求されるシステムでは鍵長の長い鍵が使用される。ここでは、鍵長の長い鍵を生成する場合などに必要となる素数Ｐnのビット長を指定する。
【００５３】
算出部３０２は、受付部３０１によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する機能を有する。具体的には、算出部３０２は、メモリから素数Ｐnのビット長を読み出し、素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出し、メモリに保持する。
【００５４】
素数｛Ｐ1，…，Ｐn-1｝は、後述する素数生成部３０３により、最終的に素数Ｐnを生成する前に生成されることとなる素数である。算出部３０２は、所望の素数Ｐnを生成するために、途中で生成される素数｛Ｐ1，…，Ｐn-1｝の各ビット長を事前に算出してメモリに保持する。
【００５５】
また、算出部３０２は、乱数ｒi（後述する乱数生成部３０４によって生成される乱数｛ｒ1，…，ｒn-1｝）のビット長より素数Ｐiのビット長が長くなる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する機能を有する。たとえば、素数Ｐ3のビット長が５０［ｂｉｔ］であった場合、素数Ｐ3に乗算する乱数ｒ3のビット長は、少なくとも５０［ｂｉｔ］よりも短いビット長（たとえば、４９［ｂｉｔ］）となる。
【００５６】
また、算出部３０２は、Ｐi+1のビット長が素数Ｐiのビット長の２倍程度の長さとなる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する機能を有する。たとえば、Ｐ4のビット長が１００［ｂｉｔ］の場合、素数Ｐ3のビット長は５０［ｂｉｔ］程度となる。
【００５７】
また、算出部３０２は、下記式（１）または（２）により、素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【００５８】
Ｌｅｎｇｔｈ（Ｐi）＝[Ｌｅｎｇｔｈ（Ｐi+1）＋１]／２＋１ …（１）
【００５９】
Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐi+1）／２＋１ …（２）
【００６０】
また、算出部３０２は、素数Ｐ1のビット長が３０数ビット程度以内の長さとなる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する。たとえば、上記式（１）または（２）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する場合、Ｌｅｎｇｔｈ（Ｐ1）≦３４となるまで、Ｌｅｎｇｔｈ（Ｐi）を順次算出することとなる。
【００６１】
なお、素数｛Ｐ1，…，Ｐn-1｝の各ビット長の算出処理を終了する素数のビット長を任意に設定することとしてもよい。具体的には、図１に示したキーボード１２１やマウス１２２などの入力装置１２０をユーザが操作してビット長を設定する。たとえば、３５［ｂｉｔ］を設定した場合、素数Ｐ1のビット長が３５［ｂｉｔ］以下となった時点で算出処理を終了することとなる。
【００６２】
なお、上記式（１）を用いて素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出部３０２による算出処理の詳細な説明は後述する。
【００６３】
素数生成部３０３は、算出部３０２によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを乗算することにより、素数Ｐiのビット長より長いビット長でかつ素数Ｐiより大きな値の素数Ｐi+1を順次生成して、素数Ｐnを生成する機能を有する。
【００６４】
すなわち、素数生成部３０３は、小さい値の素数から、その素数のビット長より長いビット長でかつ大きい値の素数を順次生成していくことにより、長いビット長の素数Ｐnを確定的に生成する。素数生成部３０３による素数生成処理は、たとえば、［背景技術］で示した第１の手法により、実行することができる。
【００６５】
具体的には、素数生成部３０３は、メモリから素数｛Ｐ1，…，Ｐn-1｝の各ビット長を読み出し、素数Ｐ1のビット長によって特定される素数を生成し、後述する乱数生成部３０４によって生成された乱数｛ｒ1，…，ｒn-1｝を用いて、素数｛Ｐ2，…，Ｐn｝を順次生成する。素数生成部３０３によって生成された素数｛Ｐ1，…，Ｐn｝はメモリに保持される。
【００６６】
より具体的には、たとえば、第１の手法の（２）に表記した数式を用いて、素数Ｐiと乱数ｒiとを乗算することにより、素数Ｐiのビット長より長いビット長でかつ素数Ｐiより大きな値の素数候補を生成し、その素数候補が素数であるか否かの判定をおこなう。ここで、素数と判定された場合、その素数候補を素数Ｐi+1とする。
【００６７】
一方、素数と判定されなかった場合、新たな乱数ｒiを生成し、素数候補が素数と判定されるまで処理を繰り返す。素数候補が素数であるか否かの判定には、たとえば、Ｐｏｃｋｌｉｎｇｔｏｎの素数判定法を利用することができる。なお、Ｐｏｃｋｌｉｎｇｔｏｎ法については公知技術のため説明を省略する。
【００６８】
また、素数Ｐ1のビット長によって特定される素数は、たとえば、［背景技術］で示した第２の手法により生成することができる。具体的には、乱数生成器（乱数生成法）により、算出部３０２によって算出された素数Ｐ1のビット長の乱数Ｒを生成し、その乱数Ｒを素数テーブル２００に保持されている各要素で除算する。
【００６９】
このとき、乱数Ｒが各要素で割り切れなければ、乱数Ｒが求める素数Ｐ1となる。一方、乱数Ｒがいずれかの要素で割り切れたら、割り切れない乱数Ｒが生成されるまで、新たな乱数Ｒを生成し、素数テーブル２００に保持されている各要素で除算する処理を繰り返しおこなう。なお、本出願において使用する乱数は、一般的に計算機で使用するための擬似乱数を含むものとし、たとえば、乱数生成器または擬似乱数生成器によって生成される。
【００７０】
ここでは、素数生成部３０３により素数Ｐ1を生成することとしたが、算出部３０２によって算出された素数Ｐ1のビット長に応じて素数生成装置１００に直接入力することとしてもよく、また、ネットワーク１４０を介して外部のコンピュータ装置から素数Ｐ1を取得することとしてもよい。
【００７１】
乱数生成部３０４は、算出部３０２によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝を生成する機能を有する。具体的には、乱数生成部３０４は、メモリから素数｛Ｐ1，…，Ｐn-1｝の各ビット長を読み出し、各ビット長に従って、乱数｛ｒ1，…，ｒn-1｝を生成する。
【００７２】
より具体的には、たとえば、乱数生成器（乱数生成法）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、乱数｛ｒ1，…，ｒn-1｝を生成することとしてもよい。ここで、乱数ｒiのビット長について説明する。上述したように、乱数ｒiのビット長は素数Ｐiのビット長よりも短くなる。
【００７３】
乱数｛ｒ1，…，ｒn-1｝のビット長は、受付部３０１によって指定を受け付けた素数Ｐnのビット長、および算出部３０２によって算出された各素数｛Ｐ1，…，Ｐn-1｝のビット長を用いて算出する。具体的には、たとえば、乱数ｒiのビット長は下記式（３）によりあらわすことができる。ただし、Ｌｅｎｇｔｈ（ｒi）は乱数ｒiのビット長、ｍ＝１，２，３とする。
【００７４】
Ｌｅｎｇｔｈ（ｒi）＝Ｌｅｎｇｔｈ（Ｐi+1）−Ｌｅｎｇｔｈ（Ｐi）−ｍ…（３）
また、以下に示す式を用いることとしてもよい。
Ｌｅｎｇｔｈ（ｒi）＝｛Ｌｅｎｇｔｈ（Ｐi）−ｍ｝／２…（３’）
また、Ｍ＝１，２とし、以下に示す式を用いることとしてもよい。
Ｌｅｎｇｔｈ（ｒi）＝｛Ｌｅｎｇｔｈ（Ｐi）＋Ｍ｝／２…（３”）
【００７５】
乱数生成部３０４は、上記式（３）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、乱数｛ｒ1，…，ｒn-1｝を生成し、メモリに保持する。たとえば、素数Ｐnのビット長が５１４［ｂｉｔ］、素数Ｐn-1のビット長が２５８［ｂｉｔ］、ｍ＝１とすると、乱数ｒiのビット長はＬｅｎｇｔｈ（ｒi）＝５１４−２５８−１＝２５５となる。
【００７６】
なお、乱数生成部３０４は、素数生成部３０３による素数生成処理時に、各素数｛Ｐ1，…，Ｐn-1｝に対応する乱数｛ｒ1，…，ｒn-1｝を個々に生成することとしてもよく、また、乱数｛ｒ1，…，ｒn-1｝を一括して生成することとしてもよい。
【００７７】
出力部３０５は、素数生成部３０３によって生成された素数Ｐnを出力する機能を有する。具体的には、出力部３０５は、素数生成部３０３によって生成された素数Ｐnをメモリから読み出して、図１に示すディスプレイ１３１やスピーカ１３２などの出力装置１３０により、素数Ｐnを出力する。なお、出力部３０５は、素数Ｐnを生成する前に途中で生成された素数｛Ｐ1，…，Ｐn-1｝をあわせて出力することとしてもよい。
【００７８】
（素数生成装置１００の素数生成処理手順）
つぎに、この発明の実施の形態にかかる素数生成装置１００の素数生成処理手順について説明する。図４は、この発明の実施の形態にかかる素数生成装置１００の素数生成処理手順を示すフローチャートである。
【００７９】
図４のフローチャートにおいて、まず、受付部３０１により、素数Ｐnのビット長の指定を受け付けたか否かを判断する（ステップＳ４０１）。ここで、素数Ｐnのビット長の指定を受け付けるのを待って（ステップＳ４０１：Ｎｏ）、受け付けた場合（ステップＳ４０１：Ｙｅｓ）、算出部３０２により、指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出処理を実行する（ステップＳ４０２）。
【００８０】
このあと、素数生成部３０３により、算出部３０２によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用して、素数Ｐiのビット長より長いビット長でかつ素数Ｐiより大きな値の素数Ｐi+1を順次生成して、素数Ｐnを生成する素数生成処理を実行する（ステップＳ４０３）。
【００８１】
最後に、出力部３０５により、ステップＳ４０３において生成された素数Ｐnを出力して（ステップＳ４０４）、本フローチャートによる一連の処理を終了する。
【００８２】
＜算出処理手順＞
つぎに、算出部３０２による上述したステップＳ４０２における素数｛Ｐ1，…，Ｐn-1｝の各ビット長の算出処理手順について説明する。図５は、ステップＳ４０２における算出処理手順を示すフローチャートである。ここでは、上記式（１）を用いて素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する場合を例に挙げて説明する。なお、Ｐnとして５１４［ｂｉｔ］の素数を生成するものとし、Ｐ1として生成可能な短い素数の最大長が３４［ｂｉｔ］であった場合の例である。
【００８３】
また、図４に示すステップＳ４０１において、素数Ｐnのビット長として５１４［ｂｉｔ］の指定を受け付け、素数Ｐ1のビット長が３０数ビット程度以内（〜３４［ｂｉｔ］）となった時点で算出処理を終了することとする。
【００８４】
図５のフローチャートにおいて、上記式（１）により、図４に示すステップＳ４０１において指定を受け付けた素数Ｐnのビット長に従って、素数Ｐiのビット長であるＬｅｎｇｔｈ（Ｐi）を算出する（ステップＳ５０１）。具体的には、ｉ＝ｎ−１として、Ｌｅｎｇｔｈ（Ｐn-1）を算出する。
【００８５】
すなわち、上記式（１）において、Ｌｅｎｇｔｈ（Ｐi+1）＝Ｌｅｎｇｔｈ（Ｐn）＝５１４として、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐn-1）を算出する。ここでは、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐn-1）＝[５１４＋１]／２＋１＝２５８．５≒２５８となる。ただし、小数点以下は切り捨てとする。
【００８６】
つぎに、ステップＳ５０１において算出されたＬｅｎｇｔｈ（Ｐi）が３０数ビット程度以内の長さであるか否かを判断する（ステップＳ５０２）。ここで、Ｌｅｎｇｔｈ（Ｐi）≦３４でない場合（ステップＳ５０２：Ｎｏ）、ｉを１つデクリメントして（ステップＳ５０３）、ステップＳ５０１に戻る。
【００８７】
一方、Ｌｅｎｇｔｈ（Ｐi）≦３４である場合（ステップＳ５０２：Ｙｅｓ）、図４に示すステップＳ４０３に移行する。ここでは、ステップＳ５０１において算出されたビット長がＬｅｎｇｔｈ（Ｐi）＝２５８＞３４となるため、ｉを１つデクリメントして、ステップＳ５０１に戻る。
【００８８】
そして、上記式（１）において、Ｌｅｎｇｔｈ（Ｐi+1）＝Ｌｅｎｇｔｈ（Ｐn-1）＝２５８として、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐn-2）を算出する。ここでは、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐn-2）＝[２５８＋１]／２＋１≒１３０となる。このように、素数Ｐnのビット長に従って、Ｌｅｎｇｔｈ（Ｐi）≦３４となるまで、素数｛Ｐ1，…，Ｐn-1｝の各ビット長の長いものから順次算出する。
【００８９】
ここでは、Ｌｅｎｇｔｈ（Ｐ4）＝２５８［ｂｉｔ］→Ｌｅｎｇｔｈ（Ｐ3）＝１３０［ｂｉｔ］→Ｌｅｎｇｔｈ（Ｐ2）＝６６［ｂｉｔ］→Ｌｅｎｇｔｈ（Ｐ1）＝３４［ｂｉｔ］≒３０［ｂｉｔ］と順次算出されることとなる。
【００９０】
これにより、素数生成処理を実行する前に、所望の素数Ｐnを効率的に生成することができる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することができる。具体的には、素数Ｐn-1と乱数ｒn-1とを乗算したときに、高い確率で素数Ｐnを生成することができる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することができる。
【００９１】
＜素数生成処理手順＞
【００９２】
つぎに、素数生成部３０３による上述したステップＳ４０３における素数生成処理手順について説明する。図６は、ステップＳ４０３における素数生成処理手順を示すフローチャート（その１）である。ここでは、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝の各ビット長を一括して算出する場合について説明する。
【００９３】
図６のフローチャートにおいて、まず、素数生成部３０３により、図４に示すステップＳ４０２において算出された素数Ｐ1のビット長に基づいて素数Ｐ1を生成する（ステップＳ６０１）。具体的には、たとえば、［背景技術］で示した第２の手法により、素数Ｐ1のビット長によって特定される素数を生成する。
【００９４】
つぎに、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝の各ビット長を算出する（ステップＳ６０２）。具体的には、上記式（３）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、乱数｛ｒ1，…，ｒn-1｝の各ビット長を算出する。具体的には、ｉをｉ＝１〜ｎ−１まで順にインクリメントして乱数｛ｒ1，…，ｒn-1｝の各ビット長をすべて算出する。
【００９５】
すなわち、上記式（３）において、ｉをｉ＝１〜ｎ−１まで順にインクリメントして、Ｌｅｎｇｔｈ（Ｐi）およびＬｅｎｇｔｈ（Ｐi+1）を順に与え、乱数｛ｒ1，…，ｒn-1｝の各ビット長を算出する。ここでは、乱数｛ｒ1，…，ｒ4｝のビット長は、Ｌｅｎｇｔｈ（ｒ1）＝３１，Ｌｅｎｇｔｈ（ｒ2）＝６３，Ｌｅｎｇｔｈ（ｒ3）＝１２７，Ｌｅｎｇｔｈ（ｒ4）＝２５７となる。
【００９６】
つぎに、ｉをｉ＝１から順にインクリメントして乱数ｒiとＰi+1を生成する。具体的には、乱数生成部３０４により、ステップＳ６０２において算出された乱数｛ｒ1，…，ｒn-1｝の各ビット長に従って乱数ｒiを生成する（ステップＳ６０３）。
【００９７】
このあと、素数生成部３０３により、ステップＳ６０３において生成された乱数ｒiを用いて素数Ｐi+1を生成する（ステップＳ６０４）。このとき、Ｐｏｃｋｌｉｎｇｔｏｎの素数判定法を利用して素数Ｐi+1を生成し、生成された素数候補が素数とならなかった場合、ステップＳ６０３に戻り、素数となるまで処理を繰り返しおこなう。
【００９８】
つぎに、ｉ＝ｎ−１であるか否かを判断し（ステップＳ６０５）、ｉ＝ｎ−１でない場合（ステップＳ６０５：Ｎｏ）、ｉを１つインクリメントして（ステップＳ６０６）、ステップＳ６０３に戻る。
【００９９】
一方、ｉ＝ｎ−１である場合（ステップＳ６０５：Ｙｅｓ）、図４に示すステップＳ４０４に移行する。すなわち、ｉをｉ＝１から順にインクリメントして素数｛Ｐ1，…，Ｐn-1｝を順次生成し、最終的に素数Ｐnを生成すると図４に示すステップＳ４０４に移行することとなる。
【０１００】
このように、算出部３０２により予め算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、当該素数｛Ｐ1，…，Ｐn｝を順次生成することにより、素数Ｐn-1から素数Ｐnを生成する際のやり直し回数を低減させ、所望の素数Ｐnを効率的に生成することができる。
【０１０１】
つぎに、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝の各ビット長を生成される素数Ｐi+1に応じて算出する場合について説明する。図７は、ステップＳ４０３における素数生成処理手順を示すフローチャート（その１）である。ここでは、素数Ｐnのビット長として５１４［ｂｉｔ］の指定を受け付け、乱数ｒiのビット長は上記式（３）であらわされることとする。なお、上記式（３）においてｍ＝１とする。
【０１０２】
図７のフローチャートにおいて、まず、素数生成部３０３により、図４に示すステップＳ４０２において算出された素数Ｐ1のビット長に基づいて素数Ｐ1を生成する（ステップＳ７０１）。つぎに、素数Ｐiに乗算する乱数ｒiのビット長を算出する（ステップＳ７０２）。
【０１０３】
具体的には、上記式（３）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、乱数ｒiのビット長を算出する。具体的には、ｉをｉ＝１から順にインクリメントして乱数ｒiのビット長を算出することとなる。
【０１０４】
すなわち、上記式（３）において、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐ1）＝３４、Ｌｅｎｇｔｈ（Ｐi+1）＝Ｌｅｎｇｔｈ（Ｐ2）＝６６として、Ｌｅｎｇｔｈ（ｒ1）を算出する。ここでは、Ｌｅｎｇｔｈ（ｒi）＝Ｌｅｎｇｔｈ（ｒ1）＝６６−３４−１＝３１となる。
【０１０５】
つぎに、乱数生成部３０４により、ステップＳ７０２において算出された乱数ｒiのビット長に従って乱数ｒiを生成する（ステップＳ７０３）。このあと、素数生成部３０３により、ステップＳ７０３において生成された乱数ｒiを用いて素数Ｐi+1を生成する（ステップＳ７０４）。
【０１０６】
このあと、ｉ＝ｎ−１であるか否かを判断し（ステップＳ７０５）、ｉ＝ｎ−１でない場合（ステップＳ７０５：Ｎｏ）、ｉを１つインクリメントして（ステップＳ７０６）、ステップＳ７０２に戻る。一方、ｉ＝ｎ−１である場合（ステップＳ７０５：Ｙｅｓ）、図４に示すステップＳ４０４に移行する。
【０１０７】
すなわち、ｉをｉ＝１から順にインクリメントして乱数ｒiのビット長を順次算出し、乱数ｒn-1のビット長を算出し、素数Ｐnを生成すると図４に示すステップＳ４０４に移行することとなる。
【０１０８】
このように、算出部３０２により予め算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、当該素数｛Ｐ1，…，Ｐn｝を順次生成することにより、素数Ｐn-1から素数Ｐnを生成する際のやり直し回数を低減させ、所望の素数Ｐnを効率的に生成することができる。
【０１０９】
また、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝の各ビット長を、生成する素数Ｐiに応じて、その都度算出するため、乱数｛ｒ1，…，ｒn-1｝の各ビット長を一括して算出した場合に比べて、乱数｛ｒ1，…，ｒn-1｝を記憶するために使用するメモリ量を低減させることができる。
【０１１０】
以上説明したように、素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法によれば、任意のビット長の素数を確定的に、かつ、効率的に生成することができるという効果を奏する。
【０１１１】
なお、本実施の形態で説明した素数生成方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【０１１２】
また、本実施の形態で説明した素数生成装置１００は、スタンダードセルやストラクチャードＡＳＩＣ(Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ)などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ(Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ)によっても実現することができる。具体的には、たとえば、上述した素数生成装置１００の機能的構成３０１〜３０５をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、素数生成装置１００を製造することができる。また、３０１〜３０５の各処理の一部分のみをこれらの手法で製造、実現し、残りの処理をプログラムなどで実現してもよい。
【０１１３】
（付記１）素数Ｐnのビット長の指定を受け付けさせる受付工程と、
前記受付工程によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させる算出工程と、
前記算出工程によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成させる素数生成工程と、
をコンピュータに実行させることを特徴とする素数生成プログラム。
【０１１４】
（付記２）前記算出工程によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、当該各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝を生成させる乱数生成工程を前記コンピュータに実行させ、
前記素数生成工程は、
前記素数Ｐ1のビット長によって特定される素数を生成し、前記乱数生成工程によって生成された乱数｛ｒ1，…，ｒn-1｝を用いて、前記素数Ｐiと前記乱数ｒiとを乗算することにより、前記素数Ｐnを生成させることを特徴とする付記１に記載の素数生成プログラム。
【０１１５】
（付記３）前記素数生成工程は、
２ビット以上のビット長によって表現可能な素数を記憶する素数テーブルを参照することにより、前記素数Ｐ1のビット長によって特定される素数を生成させることを特徴とする付記２に記載の素数生成プログラム。
【０１１６】
（付記４）前記算出工程は、
前記乱数ｒiのビット長より前記素数Ｐiのビット長が長くなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記１〜３のいずれか一つに記載の素数生成プログラム。
【０１１７】
（付記５）前記算出工程は、
前記Ｐi+1のビット長が前記素数Ｐiのビット長の２倍程度の長さとなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記４に記載の素数生成プログラム。
【０１１８】
（付記６）前記算出工程は、
下記式（１）により、前記素数Ｐnのビット長に従って、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記１〜３のいずれか一つに記載の素数生成プログラム。
Ｌｅｎｇｔｈ（Ｐi）＝[Ｌｅｎｇｔｈ（Ｐi+1）＋１]／２＋１・・・（１）
ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【０１１９】
（付記７）前記算出工程は、
下記式（２）により、前記素数Ｐnのビット長に従って、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記１〜３のいずれか一つに記載の素数生成プログラム。
Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐi+1）／２＋１・・・（２）
ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【０１２０】
（付記８）前記算出工程は、
前記素数Ｐ1のビット長が３０数ビット程度の長さとなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記１〜７のいずれか一つに記載の素数生成プログラム。
【０１２１】
（付記９）前記素数生成プログラムは、
Ｐｏｃｋｌｉｎｇｔｏｎ法を利用した素数判定手法により、前記素数Ｐnを確定的に生成させることを特徴とする付記１〜８のいずれか一つに記載の素数生成プログラム。
【０１２２】
（付記１０）付記１〜９のいずれか一つに記載の素数生成プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【０１２３】
（付記１１）素数Ｐnのビット長の指定を受け付ける受付手段と、
前記受付手段によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出手段と、
前記算出手段によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成する素数生成手段と、
を備えることを特徴とする素数生成装置。
【０１２４】
（付記１２）素数Ｐnのビット長の指定を受け付ける受付工程と、
前記受付工程によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出工程と、
前記算出工程によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成する素数生成工程と、
を含んだことを特徴とする素数生成方法。
【産業上の利用可能性】
【０１２５】
以上のように、本発明にかかる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法は、確定的な素数生成手法を用いて所定長の素数を生成する場合に有用であり、特に、２のべき乗長以外のビット長の素数を生成する場合に適している。
【図面の簡単な説明】
【０１２６】
【図１】この発明の実施の形態にかかる素数生成装置のハードウェア構成を示すブロック図である。
【図２】素数テーブルのデータ構造を示す説明図である。
【図３】この発明の実施の形態にかかる素数生成装置の機能的構成を示すブロック図である。
【図４】この発明の実施の形態にかかる素数生成装置の素数生成処理手順を示すフローチャートである
【図５】ステップＳ４０２における算出処理手順を示すフローチャートである。
【図６】ステップＳ４０３における素数生成処理手順を示すフローチャート（その１）である。
【図７】ステップＳ４０３における素数生成処理手順を示すフローチャート（その２）である。
【符号の説明】
【０１２７】
１００ 素数生成装置
２００ 素数テーブル
３０１ 受付部
３０２ 算出部
３０３ 素数生成部
３０４ 乱数生成部
３０５ 出力部
【技術分野】
【０００１】
この発明は、公開鍵暗号方式におけるデータの暗号化／復号化に使用される公開鍵または暗号鍵を生成する素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法に関する。
【背景技術】
【０００２】
公開鍵暗号（たとえば、ＲＳＡ暗号、ＥｌＧａｍａｌ暗号など）では、データの暗号化／復号化に使用する鍵（公開鍵、秘密鍵）を生成するために、素数が用いられることが多い。素数を生成する手法として、「確率的な手法による素数生成」および「確定的な手法による素数生成」が存在している。
【０００３】
これら手法のうち、前者は、生成された値が極めて高い確率で素数となるが、素数であることは保証されない手法である。また、後者は、生成された値が確実に素数であることが保証される手法である。このため、高度な安全性が要求されるシステムでは、後者の手法が採用されている。
【０００４】
これまでは、ＲＳＡ暗号などでは、公開鍵の鍵長（ビット長）として、５１２［ｂｉｔ］，１０２４［ｂｉｔ］など「２のべき乗長の鍵長」が使用されることが多かったが、近年、セキュリティシステムの多様化などにより、「２のべき乗長以外の鍵長」が使用される機会が増えてきている。
【０００５】
一般に、「２のべき乗長の鍵長」の公開鍵を生成するためには「２のべき乗長の素数」が必要となる。一方で、「２のべき乗長以外の鍵長」の公開鍵を生成するためには「２のべき乗長以外の素数」が必要となる。
【０００６】
「２のべき乗長の素数」を生成する確定的な手法としては、たとえば、Ｐｏｃｋｌｉｎｇｔｏｎの素数判定法を利用して、小さい値の素数から大きい値の素数を順次生成する素数生成手法が知られている。
【０００７】
ここで、Ｐｏｃｋｌｉｎｇｔｏｎの素数判定法（たとえば、下記非特許文献１参照。）を利用した素数生成手法（以下、「第１の手法」という）により、「２のべき乗長の素数」を生成する処理手順について説明する。
【０００８】
（１）ｒ＜ｐとなる乱数ｒを生成する。（ｐ：２のべき乗長の素数）
（２）ｐ2＝２×ｒ×ｐ＋１を導出する。
（３）ｐ2が所定の条件を満たしている場合（Ｐｏｃｋｌｉｎｇｔｏｎ法による素数判定 法）、ｐ2は素数となる。ｐ2が所定の条件を満たしていない場合、（１）に戻り、 一連の処理をやり直す。なお、所定の条件には、たとえば、非特許文献１のｐ１４４ ．４．４０に記載された条件を用いることができる。
（４）ｐ2が最終的に求めたいビット長の素数となっていない場合、ｐ＝ｐ2として（１ ）に戻り、一連の処理を繰り返す。
【０００９】
この第１の手法によれば、（２）の処理により、ｐのビット長よりも長いビット長かつｐより大きな値のｐ2を生成することができる。このため、（４）において、ｐ2を新たにｐと置き換えて、（１）からの処理を繰り返し実行することにより、長いビット長の素数を順次生成することができる。
【００１０】
ただし、（１）において、ｒが小さいとｐ2のビット長がｐのビット長に比べてあまり大きくならない。このため、効率よく長いビット長の素数を生成するために、たとえば、ｐ2のビット長がｐのビット長の約２倍となるように生成する（たとえば、３２［ｂｉｔ］→６４［ｂｉｔ］→１２８［ｂｉｔ］→・・・）。
【００１１】
このように、第１の手法によれば、（１）〜（４）の処理を繰り返しおこなうことにより、「２のべき乗長の素数」を効率的に生成することができる。
【００１２】
つぎに、３０数ビット程度の短いビット長の素数を生成する第２の手法について説明する。以下、Ｑ［ｂｉｔ］の短いビット長の素数を生成する第２の手法の処理手順を示す。
【００１３】
（１）２［ｂｉｔ］〜Ｑ／２［ｂｉｔ］によって表現可能な素数を事前に計算し、その計 算結果をテーブルに保持しておく。
（２）Ｑ［ｂｉｔ］の乱数Ｒを生成する。
（３）（２）で生成された乱数Ｒを（１）のテーブルに保持されている各要素で除算し、 割り切れなければ乱数Ｒが求める素数となる。また、割り切れたら（２）に戻り、新 たな乱数Ｒを生成して、処理を繰り返す。なお、本出願においては、短い素数を生成 する手法は上記第２の手法に限らず、いかなる手法を用いてもよい。
【００１４】
つぎに、第１の手法を拡張することにより、「２のべき乗長以外の素数」を生成する第３の手法について説明する。以下、「２のべき乗長以外の素数」として、７６８［ｂｉｔ］のビット長の素数を例に挙げて説明する。
【００１５】
まず、第１の手法により、２のべき乗長、かつ、生成したい素数のビット長を超えない素数を生成する。具体的には、まず、３２［ｂｉｔ］→６４［ｂｉｔ］→１２８［ｂｉｔ］→２５６［ｂｉｔ］→５１２［ｂｉｔ］までは第１の手法により、ｐ2のビット長がｐのビット長の約２倍となるように素数を順次生成する。そして、５１２［ｂｉｔ］→７６８［ｂｉｔ］の素数を生成するために、第１の手法の（２）の式にビット長の短い乱数ｒを代入して、ｐ2＝７６８［ｂｉｔ］を生成する。
【００１６】
このように、第３の手法によれば、「２のべき乗長の素数」を生成する処理を繰り返しおこない、最後に、乱数ｒのビット長を調整してｐ2を生成することにより、所望のビット長（２のべき乗長以外）の素数を生成することができる。
【００１７】
【非特許文献１】ＨＡＮＤＢＯＯＫ ｏｆ ＡＰＰＬＩＥＤ ＣＲＹＰＴＯＧＲＡＰＨＹ（Ａｌｆｒｅｄ Ｊ．Ｍｅｎｅｚｅｓ， Ｐａｕｌ Ｃ．ｖａｎ Ｏｏｒｓｃｈｏｔ， Ｓｃｏｔｔ Ａ．Ｖａｎｓｔｏｎｅ． １９９７ ＣＲＣ Ｐｒｅｓｓ）
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかしながら、上述した非特許文献１による従来技術によれば、「２のべき乗長以外の素数」を確定的な素数判定手法を用いて効率的に生成することができないため、たとえば、高度な安全性が要求されるシステムに使用するための「２のべき乗長以外の鍵長」の公開鍵、暗号鍵を生成することができないという問題があった。
【００１９】
また、上述した第３の手法によれば、「２のべき乗長の素数」よりもある程度長いビット長（たとえば、７６８［ｂｉｔ］）の「２のべき乗長以外の素数」を確定的に生成することができる。しかしながら、「２のべき乗長＋数ビット」のビット長の素数を生成することは非常に困難であるという問題があった。
【００２０】
ここで、従来技術の第３の手法の問題点を具体的に説明する。以下、「２のべき乗長以外の素数」として、「２のべき乗長＋数ビット」＝５１２＋２＝５１４［ｂｉｔ］のビット長の素数を生成する場合を例に挙げて説明する。
【００２１】
まず、上述した第２の手法により、３２［ｂｉｔ］の素数を生成する。このあと、第１の手法により、２のべき乗長、かつビット長が５１４［ｂｉｔ］を超えない素数を生成する。この結果、ビット長が５１２［ｂｉｔ］の素数が生成される（３２［ｂｉｔ］→６４［ｂｉｔ］→１２８［ｂｉｔ］→２５６［ｂｉｔ］→５１２［ｂｉｔ］）。
【００２２】
つぎに、残りのビット長分（２［ｂｉｔ］）について、乱数ｒのビット長を調整して生成する。ここでは、第１の手法の手順（２）において、ｐのビット長が５１２［ｂｉｔ］となり、ｐ2のビット長が５１４［ｂｉｔ］となるためには、手順（１）で生成する乱数ｒのビット長を２［ｂｉｔ］以内とする必要がある。すなわち、乱数ｒの取り得る値は『０，１，２，３』のいずれかとなる。
【００２３】
これにより、第１の手法によって生成されるｐ2の値は４種類となる。ここで、ビット長が５１４［ｂｉｔ］の値をランダムに選択したときに、その値が素数である確率は約１／２9となる。このため、第３の手法によって５１４［ｂｉｔ］のビット長の素数を生成することができる確率は約４／２9となり、一回の処理で所望の素数を生成することが非常に難しい。
【００２４】
このため、前段の処理に戻り、５１２［ｂｉｔ］のビット長の素数を生成し、５１４［ｂｉｔ］のビット長の値が素数となるまでこの処理を繰り返しおこなう必要がある。このように、第３の手法によれば、所望のビット長の素数を生成するためのやり直し回数（上記例では約２9回）が非常に多くなってしまい、素数生成処理にかかる作業時間および作業負荷が著しく増大してしまうという問題があった。
【００２５】
この発明は、上述した従来技術による問題点を解消するため、任意のビット長の素数を確定的に、かつ、効率的に生成することができる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法を提供することを目的とする。
【課題を解決するための手段】
【００２６】
上述した課題を解決し、目的を達成するため、この発明にかかる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法は、素数Ｐnのビット長の指定を受け付け、指定された素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出し、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成することを特徴とする。
【００２７】
また、上記発明において、算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、当該各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝を生成し、前記素数Ｐ1のビット長によって特定される素数を生成し、乱数｛ｒ1，…，ｒn-1｝を用いて、前記素数Ｐiと前記乱数ｒiとを乗算することにより、素数Ｐnを生成することとしてもよい。
【００２８】
これらの発明によれば、素数Ｐnを生成する前に途中で生成されることとなる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を予め算出しておくことにより、素数Ｐn-1から素数Ｐnを生成する際のやり直し回数を低減させることができる。
【００２９】
また、上記発明において、２ビット以上のビット長によって表現可能な素数を記憶する素数テーブルを参照することにより、前記素数Ｐ1のビット長によって特定される素数を生成することとしてもよい。
【００３０】
この発明によれば、３０数ビット程度以内の短いビット長の素数を確定的に生成することができる。
【００３１】
また、上記発明において、前記乱数ｒiのビット長より前記素数Ｐiのビット長が長くなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。
【００３２】
また、上記発明において、前記Ｐi+1のビット長が前記素数Ｐiのビット長の２倍程度の長さとなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。
【００３３】
また、上記発明において、Ｌｅｎｇｔｈ（Ｐi）＝[Ｌｅｎｇｔｈ（Ｐi+1）＋１]／２＋１により、前記素数Ｐnのビット長に従って、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【００３４】
また、上記発明において、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐi+1）／２＋１により、前記素数Ｐnのビット長に従って、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【００３５】
これらの発明によれば、短いビット長の素数から、より長いビット長の素数を効率的に生成することができる。
【００３６】
また、上記発明において、前記素数Ｐ1のビット長が３０数ビット程度の長さとなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。
【００３７】
この発明によれば、簡単な手法によって確定的に素数Ｐ1を生成することができる程度の短いビット長となるまで素数｛Ｐ1，…，Ｐn-1｝の各ビット長の算出処理を繰り返し実行させることができる。
【発明の効果】
【００３８】
本発明にかかる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法によれば、任意のビット長の素数を確定的に、かつ、効率的に生成することができるという効果を奏する。
【発明を実施するための最良の形態】
【００３９】
以下に添付図面を参照して、この発明にかかる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法の好適な実施の形態を詳細に説明する。
【００４０】
（素数生成装置のハードウェア構成）
まず、この発明の実施の形態にかかる素数生成装置のハードウェア構成について説明する。図１は、この発明の実施の形態にかかる素数生成装置のハードウェア構成を示すブロック図である。
【００４１】
図１において、素数生成装置１００は、コンピュータ本体１１０と、入力装置１２０と、出力装置１３０と、から構成されており、不図示のルータやモデムを介してＬＡＮ，ＷＡＮやインターネットなどのネットワーク１４０に接続可能である。
【００４２】
コンピュータ本体１１０は、ＣＰＵ，メモリ，インターフェースを有する。ＣＰＵは、素数生成装置１００の全体の制御を司る。メモリは、ＲＯＭ，ＲＡＭ，ＨＤ，光ディスク１１１，フラッシュメモリから構成される。メモリはＣＰＵのワークエリアとして使用される。
【００４３】
また、メモリには各種プログラムが格納されており、ＣＰＵからの命令に応じてロードされる。ＨＤおよび光ディスク１１１はディスクドライブによりデータのリード／ライトが制御される。また、光ディスク１１１およびフラッシュメモリはコンピュータ本体１１０に対し着脱自在である。インターフェースは、入力装置１２０からの入力、出力装置１３０への出力、ネットワーク１４０に対する送受信の制御をおこなう。
【００４４】
また、入力装置１２０としては、キーボード１２１、マウス１２２、スキャナ１２３などがある。キーボード１２１は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式であってもよい。マウス１２２は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。スキャナ１２３は、画像を光学的に読み取る。読み取られた画像は画像データとして取り込まれ、コンピュータ本体１１０内のメモリに格納される。なお、スキャナ１２３にＯＣＲ機能を持たせてもよい。
【００４５】
また、出力装置１３０としては、ディスプレイ１３１、スピーカ１３２、プリンタ１３３などがある。ディスプレイ１３１は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。また、スピーカ１３２は、効果音や読み上げ音などの音声を出力する。また、プリンタ１３３は、画像データや文書データを印刷する。
【００４６】
（素数テーブル２００のデータ構造）
つぎに、素数テーブル２００のデータ構造について説明する。図２は、素数テーブル２００のデータ構造を示す説明図である。図２において、素数テーブル２００は、２［ｂｉｔ］〜１７［ｂｉｔ］までの各ビット数によって表現可能な素数を保持している。
【００４７】
たとえば、２［ｂｉｔ］の素数である２，３を保持しており、３［ｂｉｔ］の素数である２，３，５，７を保持している。すなわち、素数テーブル２００は、１７［ｂｉｔ］のビット数によって表現可能なすべての素数を保持していることとなる。なお、１７［ｂｉｔ］のビット数によって表現可能な最大の素数をＮと表記する。
【００４８】
この素数テーブル２００は、たとえば、後述する素数生成装置１００の素数生成部３０３によって素数Ｐ1を生成する場合に用いられる。具体的には、［背景技術］で示した第２の手法により、３０数ビット程度以内の短いビット長の素数Ｐ1を生成する場合に用いる。一般的に、テーブルに１７［ｂｉｔ］までの素数を準備する場合、３４［ｂｉｔ］までの素数を生成することができる。
【００４９】
（素数生成装置１００の機能的構成）
つぎに、この発明の実施の形態にかかる素数生成装置１００の機能的構成について説明する。図３は、この発明の実施の形態にかかる素数生成装置１００の機能的構成を示すブロック図である。図３において、素数生成装置１００は、素数テーブル２００と、受付部３０１と、算出部３０２と、素数生成部３０３と、乱数生成部３０４と、出力部３０５と、を備えている。
【００５０】
これら各機能３０１〜３０５は、メモリに格納された当該機能に関するプログラムをＣＰＵに実行させることにより、当該機能を実現することができる。また、各機能３０１〜３０５からの出力データはメモリに保持される。また、図３中矢印で示した接続先の機能的構成は、接続元の機能からの出力データをメモリから読み込んで、当該機能に関するプログラムをＣＰＵに実行させる。
【００５１】
図３において、まず、受付部３０１は、素数Ｐnのビット長の指定を受け付ける機能を有する。具体的には、図１に示したキーボード１２１やマウス１２２などの入力装置１２０をユーザが操作することで、素数Ｐnのビット長の指定を受け付けて、メモリに保持する。たとえば、素数Ｐnのビット長をあらわす任意の数字（たとえば、５１４，１０２８など）をユーザが入力することにより、素数Ｐnのビット長を指定する。
【００５２】
この素数Ｐnは、たとえば、ＲＳＡ暗号などの公開鍵暗号に使用する鍵（公開鍵、秘密鍵）を生成する場合に必要となる素数である。一般に、鍵長が長いほど暗号強度が高くなるため、高度な安全性が要求されるシステムでは鍵長の長い鍵が使用される。ここでは、鍵長の長い鍵を生成する場合などに必要となる素数Ｐnのビット長を指定する。
【００５３】
算出部３０２は、受付部３０１によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する機能を有する。具体的には、算出部３０２は、メモリから素数Ｐnのビット長を読み出し、素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出し、メモリに保持する。
【００５４】
素数｛Ｐ1，…，Ｐn-1｝は、後述する素数生成部３０３により、最終的に素数Ｐnを生成する前に生成されることとなる素数である。算出部３０２は、所望の素数Ｐnを生成するために、途中で生成される素数｛Ｐ1，…，Ｐn-1｝の各ビット長を事前に算出してメモリに保持する。
【００５５】
また、算出部３０２は、乱数ｒi（後述する乱数生成部３０４によって生成される乱数｛ｒ1，…，ｒn-1｝）のビット長より素数Ｐiのビット長が長くなる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する機能を有する。たとえば、素数Ｐ3のビット長が５０［ｂｉｔ］であった場合、素数Ｐ3に乗算する乱数ｒ3のビット長は、少なくとも５０［ｂｉｔ］よりも短いビット長（たとえば、４９［ｂｉｔ］）となる。
【００５６】
また、算出部３０２は、Ｐi+1のビット長が素数Ｐiのビット長の２倍程度の長さとなる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する機能を有する。たとえば、Ｐ4のビット長が１００［ｂｉｔ］の場合、素数Ｐ3のビット長は５０［ｂｉｔ］程度となる。
【００５７】
また、算出部３０２は、下記式（１）または（２）により、素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することとしてもよい。ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【００５８】
Ｌｅｎｇｔｈ（Ｐi）＝[Ｌｅｎｇｔｈ（Ｐi+1）＋１]／２＋１ …（１）
【００５９】
Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐi+1）／２＋１ …（２）
【００６０】
また、算出部３０２は、素数Ｐ1のビット長が３０数ビット程度以内の長さとなる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する。たとえば、上記式（１）または（２）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する場合、Ｌｅｎｇｔｈ（Ｐ1）≦３４となるまで、Ｌｅｎｇｔｈ（Ｐi）を順次算出することとなる。
【００６１】
なお、素数｛Ｐ1，…，Ｐn-1｝の各ビット長の算出処理を終了する素数のビット長を任意に設定することとしてもよい。具体的には、図１に示したキーボード１２１やマウス１２２などの入力装置１２０をユーザが操作してビット長を設定する。たとえば、３５［ｂｉｔ］を設定した場合、素数Ｐ1のビット長が３５［ｂｉｔ］以下となった時点で算出処理を終了することとなる。
【００６２】
なお、上記式（１）を用いて素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出部３０２による算出処理の詳細な説明は後述する。
【００６３】
素数生成部３０３は、算出部３０２によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを乗算することにより、素数Ｐiのビット長より長いビット長でかつ素数Ｐiより大きな値の素数Ｐi+1を順次生成して、素数Ｐnを生成する機能を有する。
【００６４】
すなわち、素数生成部３０３は、小さい値の素数から、その素数のビット長より長いビット長でかつ大きい値の素数を順次生成していくことにより、長いビット長の素数Ｐnを確定的に生成する。素数生成部３０３による素数生成処理は、たとえば、［背景技術］で示した第１の手法により、実行することができる。
【００６５】
具体的には、素数生成部３０３は、メモリから素数｛Ｐ1，…，Ｐn-1｝の各ビット長を読み出し、素数Ｐ1のビット長によって特定される素数を生成し、後述する乱数生成部３０４によって生成された乱数｛ｒ1，…，ｒn-1｝を用いて、素数｛Ｐ2，…，Ｐn｝を順次生成する。素数生成部３０３によって生成された素数｛Ｐ1，…，Ｐn｝はメモリに保持される。
【００６６】
より具体的には、たとえば、第１の手法の（２）に表記した数式を用いて、素数Ｐiと乱数ｒiとを乗算することにより、素数Ｐiのビット長より長いビット長でかつ素数Ｐiより大きな値の素数候補を生成し、その素数候補が素数であるか否かの判定をおこなう。ここで、素数と判定された場合、その素数候補を素数Ｐi+1とする。
【００６７】
一方、素数と判定されなかった場合、新たな乱数ｒiを生成し、素数候補が素数と判定されるまで処理を繰り返す。素数候補が素数であるか否かの判定には、たとえば、Ｐｏｃｋｌｉｎｇｔｏｎの素数判定法を利用することができる。なお、Ｐｏｃｋｌｉｎｇｔｏｎ法については公知技術のため説明を省略する。
【００６８】
また、素数Ｐ1のビット長によって特定される素数は、たとえば、［背景技術］で示した第２の手法により生成することができる。具体的には、乱数生成器（乱数生成法）により、算出部３０２によって算出された素数Ｐ1のビット長の乱数Ｒを生成し、その乱数Ｒを素数テーブル２００に保持されている各要素で除算する。
【００６９】
このとき、乱数Ｒが各要素で割り切れなければ、乱数Ｒが求める素数Ｐ1となる。一方、乱数Ｒがいずれかの要素で割り切れたら、割り切れない乱数Ｒが生成されるまで、新たな乱数Ｒを生成し、素数テーブル２００に保持されている各要素で除算する処理を繰り返しおこなう。なお、本出願において使用する乱数は、一般的に計算機で使用するための擬似乱数を含むものとし、たとえば、乱数生成器または擬似乱数生成器によって生成される。
【００７０】
ここでは、素数生成部３０３により素数Ｐ1を生成することとしたが、算出部３０２によって算出された素数Ｐ1のビット長に応じて素数生成装置１００に直接入力することとしてもよく、また、ネットワーク１４０を介して外部のコンピュータ装置から素数Ｐ1を取得することとしてもよい。
【００７１】
乱数生成部３０４は、算出部３０２によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝を生成する機能を有する。具体的には、乱数生成部３０４は、メモリから素数｛Ｐ1，…，Ｐn-1｝の各ビット長を読み出し、各ビット長に従って、乱数｛ｒ1，…，ｒn-1｝を生成する。
【００７２】
より具体的には、たとえば、乱数生成器（乱数生成法）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、乱数｛ｒ1，…，ｒn-1｝を生成することとしてもよい。ここで、乱数ｒiのビット長について説明する。上述したように、乱数ｒiのビット長は素数Ｐiのビット長よりも短くなる。
【００７３】
乱数｛ｒ1，…，ｒn-1｝のビット長は、受付部３０１によって指定を受け付けた素数Ｐnのビット長、および算出部３０２によって算出された各素数｛Ｐ1，…，Ｐn-1｝のビット長を用いて算出する。具体的には、たとえば、乱数ｒiのビット長は下記式（３）によりあらわすことができる。ただし、Ｌｅｎｇｔｈ（ｒi）は乱数ｒiのビット長、ｍ＝１，２，３とする。
【００７４】
Ｌｅｎｇｔｈ（ｒi）＝Ｌｅｎｇｔｈ（Ｐi+1）−Ｌｅｎｇｔｈ（Ｐi）−ｍ…（３）
また、以下に示す式を用いることとしてもよい。
Ｌｅｎｇｔｈ（ｒi）＝｛Ｌｅｎｇｔｈ（Ｐi）−ｍ｝／２…（３’）
また、Ｍ＝１，２とし、以下に示す式を用いることとしてもよい。
Ｌｅｎｇｔｈ（ｒi）＝｛Ｌｅｎｇｔｈ（Ｐi）＋Ｍ｝／２…（３”）
【００７５】
乱数生成部３０４は、上記式（３）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、乱数｛ｒ1，…，ｒn-1｝を生成し、メモリに保持する。たとえば、素数Ｐnのビット長が５１４［ｂｉｔ］、素数Ｐn-1のビット長が２５８［ｂｉｔ］、ｍ＝１とすると、乱数ｒiのビット長はＬｅｎｇｔｈ（ｒi）＝５１４−２５８−１＝２５５となる。
【００７６】
なお、乱数生成部３０４は、素数生成部３０３による素数生成処理時に、各素数｛Ｐ1，…，Ｐn-1｝に対応する乱数｛ｒ1，…，ｒn-1｝を個々に生成することとしてもよく、また、乱数｛ｒ1，…，ｒn-1｝を一括して生成することとしてもよい。
【００７７】
出力部３０５は、素数生成部３０３によって生成された素数Ｐnを出力する機能を有する。具体的には、出力部３０５は、素数生成部３０３によって生成された素数Ｐnをメモリから読み出して、図１に示すディスプレイ１３１やスピーカ１３２などの出力装置１３０により、素数Ｐnを出力する。なお、出力部３０５は、素数Ｐnを生成する前に途中で生成された素数｛Ｐ1，…，Ｐn-1｝をあわせて出力することとしてもよい。
【００７８】
（素数生成装置１００の素数生成処理手順）
つぎに、この発明の実施の形態にかかる素数生成装置１００の素数生成処理手順について説明する。図４は、この発明の実施の形態にかかる素数生成装置１００の素数生成処理手順を示すフローチャートである。
【００７９】
図４のフローチャートにおいて、まず、受付部３０１により、素数Ｐnのビット長の指定を受け付けたか否かを判断する（ステップＳ４０１）。ここで、素数Ｐnのビット長の指定を受け付けるのを待って（ステップＳ４０１：Ｎｏ）、受け付けた場合（ステップＳ４０１：Ｙｅｓ）、算出部３０２により、指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出処理を実行する（ステップＳ４０２）。
【００８０】
このあと、素数生成部３０３により、算出部３０２によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用して、素数Ｐiのビット長より長いビット長でかつ素数Ｐiより大きな値の素数Ｐi+1を順次生成して、素数Ｐnを生成する素数生成処理を実行する（ステップＳ４０３）。
【００８１】
最後に、出力部３０５により、ステップＳ４０３において生成された素数Ｐnを出力して（ステップＳ４０４）、本フローチャートによる一連の処理を終了する。
【００８２】
＜算出処理手順＞
つぎに、算出部３０２による上述したステップＳ４０２における素数｛Ｐ1，…，Ｐn-1｝の各ビット長の算出処理手順について説明する。図５は、ステップＳ４０２における算出処理手順を示すフローチャートである。ここでは、上記式（１）を用いて素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する場合を例に挙げて説明する。なお、Ｐnとして５１４［ｂｉｔ］の素数を生成するものとし、Ｐ1として生成可能な短い素数の最大長が３４［ｂｉｔ］であった場合の例である。
【００８３】
また、図４に示すステップＳ４０１において、素数Ｐnのビット長として５１４［ｂｉｔ］の指定を受け付け、素数Ｐ1のビット長が３０数ビット程度以内（〜３４［ｂｉｔ］）となった時点で算出処理を終了することとする。
【００８４】
図５のフローチャートにおいて、上記式（１）により、図４に示すステップＳ４０１において指定を受け付けた素数Ｐnのビット長に従って、素数Ｐiのビット長であるＬｅｎｇｔｈ（Ｐi）を算出する（ステップＳ５０１）。具体的には、ｉ＝ｎ−１として、Ｌｅｎｇｔｈ（Ｐn-1）を算出する。
【００８５】
すなわち、上記式（１）において、Ｌｅｎｇｔｈ（Ｐi+1）＝Ｌｅｎｇｔｈ（Ｐn）＝５１４として、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐn-1）を算出する。ここでは、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐn-1）＝[５１４＋１]／２＋１＝２５８．５≒２５８となる。ただし、小数点以下は切り捨てとする。
【００８６】
つぎに、ステップＳ５０１において算出されたＬｅｎｇｔｈ（Ｐi）が３０数ビット程度以内の長さであるか否かを判断する（ステップＳ５０２）。ここで、Ｌｅｎｇｔｈ（Ｐi）≦３４でない場合（ステップＳ５０２：Ｎｏ）、ｉを１つデクリメントして（ステップＳ５０３）、ステップＳ５０１に戻る。
【００８７】
一方、Ｌｅｎｇｔｈ（Ｐi）≦３４である場合（ステップＳ５０２：Ｙｅｓ）、図４に示すステップＳ４０３に移行する。ここでは、ステップＳ５０１において算出されたビット長がＬｅｎｇｔｈ（Ｐi）＝２５８＞３４となるため、ｉを１つデクリメントして、ステップＳ５０１に戻る。
【００８８】
そして、上記式（１）において、Ｌｅｎｇｔｈ（Ｐi+1）＝Ｌｅｎｇｔｈ（Ｐn-1）＝２５８として、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐn-2）を算出する。ここでは、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐn-2）＝[２５８＋１]／２＋１≒１３０となる。このように、素数Ｐnのビット長に従って、Ｌｅｎｇｔｈ（Ｐi）≦３４となるまで、素数｛Ｐ1，…，Ｐn-1｝の各ビット長の長いものから順次算出する。
【００８９】
ここでは、Ｌｅｎｇｔｈ（Ｐ4）＝２５８［ｂｉｔ］→Ｌｅｎｇｔｈ（Ｐ3）＝１３０［ｂｉｔ］→Ｌｅｎｇｔｈ（Ｐ2）＝６６［ｂｉｔ］→Ｌｅｎｇｔｈ（Ｐ1）＝３４［ｂｉｔ］≒３０［ｂｉｔ］と順次算出されることとなる。
【００９０】
これにより、素数生成処理を実行する前に、所望の素数Ｐnを効率的に生成することができる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することができる。具体的には、素数Ｐn-1と乱数ｒn-1とを乗算したときに、高い確率で素数Ｐnを生成することができる素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出することができる。
【００９１】
＜素数生成処理手順＞
【００９２】
つぎに、素数生成部３０３による上述したステップＳ４０３における素数生成処理手順について説明する。図６は、ステップＳ４０３における素数生成処理手順を示すフローチャート（その１）である。ここでは、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝の各ビット長を一括して算出する場合について説明する。
【００９３】
図６のフローチャートにおいて、まず、素数生成部３０３により、図４に示すステップＳ４０２において算出された素数Ｐ1のビット長に基づいて素数Ｐ1を生成する（ステップＳ６０１）。具体的には、たとえば、［背景技術］で示した第２の手法により、素数Ｐ1のビット長によって特定される素数を生成する。
【００９４】
つぎに、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝の各ビット長を算出する（ステップＳ６０２）。具体的には、上記式（３）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、乱数｛ｒ1，…，ｒn-1｝の各ビット長を算出する。具体的には、ｉをｉ＝１〜ｎ−１まで順にインクリメントして乱数｛ｒ1，…，ｒn-1｝の各ビット長をすべて算出する。
【００９５】
すなわち、上記式（３）において、ｉをｉ＝１〜ｎ−１まで順にインクリメントして、Ｌｅｎｇｔｈ（Ｐi）およびＬｅｎｇｔｈ（Ｐi+1）を順に与え、乱数｛ｒ1，…，ｒn-1｝の各ビット長を算出する。ここでは、乱数｛ｒ1，…，ｒ4｝のビット長は、Ｌｅｎｇｔｈ（ｒ1）＝３１，Ｌｅｎｇｔｈ（ｒ2）＝６３，Ｌｅｎｇｔｈ（ｒ3）＝１２７，Ｌｅｎｇｔｈ（ｒ4）＝２５７となる。
【００９６】
つぎに、ｉをｉ＝１から順にインクリメントして乱数ｒiとＰi+1を生成する。具体的には、乱数生成部３０４により、ステップＳ６０２において算出された乱数｛ｒ1，…，ｒn-1｝の各ビット長に従って乱数ｒiを生成する（ステップＳ６０３）。
【００９７】
このあと、素数生成部３０３により、ステップＳ６０３において生成された乱数ｒiを用いて素数Ｐi+1を生成する（ステップＳ６０４）。このとき、Ｐｏｃｋｌｉｎｇｔｏｎの素数判定法を利用して素数Ｐi+1を生成し、生成された素数候補が素数とならなかった場合、ステップＳ６０３に戻り、素数となるまで処理を繰り返しおこなう。
【００９８】
つぎに、ｉ＝ｎ−１であるか否かを判断し（ステップＳ６０５）、ｉ＝ｎ−１でない場合（ステップＳ６０５：Ｎｏ）、ｉを１つインクリメントして（ステップＳ６０６）、ステップＳ６０３に戻る。
【００９９】
一方、ｉ＝ｎ−１である場合（ステップＳ６０５：Ｙｅｓ）、図４に示すステップＳ４０４に移行する。すなわち、ｉをｉ＝１から順にインクリメントして素数｛Ｐ1，…，Ｐn-1｝を順次生成し、最終的に素数Ｐnを生成すると図４に示すステップＳ４０４に移行することとなる。
【０１００】
このように、算出部３０２により予め算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、当該素数｛Ｐ1，…，Ｐn｝を順次生成することにより、素数Ｐn-1から素数Ｐnを生成する際のやり直し回数を低減させ、所望の素数Ｐnを効率的に生成することができる。
【０１０１】
つぎに、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝の各ビット長を生成される素数Ｐi+1に応じて算出する場合について説明する。図７は、ステップＳ４０３における素数生成処理手順を示すフローチャート（その１）である。ここでは、素数Ｐnのビット長として５１４［ｂｉｔ］の指定を受け付け、乱数ｒiのビット長は上記式（３）であらわされることとする。なお、上記式（３）においてｍ＝１とする。
【０１０２】
図７のフローチャートにおいて、まず、素数生成部３０３により、図４に示すステップＳ４０２において算出された素数Ｐ1のビット長に基づいて素数Ｐ1を生成する（ステップＳ７０１）。つぎに、素数Ｐiに乗算する乱数ｒiのビット長を算出する（ステップＳ７０２）。
【０１０３】
具体的には、上記式（３）により、素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、乱数ｒiのビット長を算出する。具体的には、ｉをｉ＝１から順にインクリメントして乱数ｒiのビット長を算出することとなる。
【０１０４】
すなわち、上記式（３）において、Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐ1）＝３４、Ｌｅｎｇｔｈ（Ｐi+1）＝Ｌｅｎｇｔｈ（Ｐ2）＝６６として、Ｌｅｎｇｔｈ（ｒ1）を算出する。ここでは、Ｌｅｎｇｔｈ（ｒi）＝Ｌｅｎｇｔｈ（ｒ1）＝６６−３４−１＝３１となる。
【０１０５】
つぎに、乱数生成部３０４により、ステップＳ７０２において算出された乱数ｒiのビット長に従って乱数ｒiを生成する（ステップＳ７０３）。このあと、素数生成部３０３により、ステップＳ７０３において生成された乱数ｒiを用いて素数Ｐi+1を生成する（ステップＳ７０４）。
【０１０６】
このあと、ｉ＝ｎ−１であるか否かを判断し（ステップＳ７０５）、ｉ＝ｎ−１でない場合（ステップＳ７０５：Ｎｏ）、ｉを１つインクリメントして（ステップＳ７０６）、ステップＳ７０２に戻る。一方、ｉ＝ｎ−１である場合（ステップＳ７０５：Ｙｅｓ）、図４に示すステップＳ４０４に移行する。
【０１０７】
すなわち、ｉをｉ＝１から順にインクリメントして乱数ｒiのビット長を順次算出し、乱数ｒn-1のビット長を算出し、素数Ｐnを生成すると図４に示すステップＳ４０４に移行することとなる。
【０１０８】
このように、算出部３０２により予め算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、当該素数｛Ｐ1，…，Ｐn｝を順次生成することにより、素数Ｐn-1から素数Ｐnを生成する際のやり直し回数を低減させ、所望の素数Ｐnを効率的に生成することができる。
【０１０９】
また、各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝の各ビット長を、生成する素数Ｐiに応じて、その都度算出するため、乱数｛ｒ1，…，ｒn-1｝の各ビット長を一括して算出した場合に比べて、乱数｛ｒ1，…，ｒn-1｝を記憶するために使用するメモリ量を低減させることができる。
【０１１０】
以上説明したように、素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法によれば、任意のビット長の素数を確定的に、かつ、効率的に生成することができるという効果を奏する。
【０１１１】
なお、本実施の形態で説明した素数生成方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【０１１２】
また、本実施の形態で説明した素数生成装置１００は、スタンダードセルやストラクチャードＡＳＩＣ(Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ)などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ(Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ)によっても実現することができる。具体的には、たとえば、上述した素数生成装置１００の機能的構成３０１〜３０５をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、素数生成装置１００を製造することができる。また、３０１〜３０５の各処理の一部分のみをこれらの手法で製造、実現し、残りの処理をプログラムなどで実現してもよい。
【０１１３】
（付記１）素数Ｐnのビット長の指定を受け付けさせる受付工程と、
前記受付工程によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させる算出工程と、
前記算出工程によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成させる素数生成工程と、
をコンピュータに実行させることを特徴とする素数生成プログラム。
【０１１４】
（付記２）前記算出工程によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、当該各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝を生成させる乱数生成工程を前記コンピュータに実行させ、
前記素数生成工程は、
前記素数Ｐ1のビット長によって特定される素数を生成し、前記乱数生成工程によって生成された乱数｛ｒ1，…，ｒn-1｝を用いて、前記素数Ｐiと前記乱数ｒiとを乗算することにより、前記素数Ｐnを生成させることを特徴とする付記１に記載の素数生成プログラム。
【０１１５】
（付記３）前記素数生成工程は、
２ビット以上のビット長によって表現可能な素数を記憶する素数テーブルを参照することにより、前記素数Ｐ1のビット長によって特定される素数を生成させることを特徴とする付記２に記載の素数生成プログラム。
【０１１６】
（付記４）前記算出工程は、
前記乱数ｒiのビット長より前記素数Ｐiのビット長が長くなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記１〜３のいずれか一つに記載の素数生成プログラム。
【０１１７】
（付記５）前記算出工程は、
前記Ｐi+1のビット長が前記素数Ｐiのビット長の２倍程度の長さとなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記４に記載の素数生成プログラム。
【０１１８】
（付記６）前記算出工程は、
下記式（１）により、前記素数Ｐnのビット長に従って、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記１〜３のいずれか一つに記載の素数生成プログラム。
Ｌｅｎｇｔｈ（Ｐi）＝[Ｌｅｎｇｔｈ（Ｐi+1）＋１]／２＋１・・・（１）
ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【０１１９】
（付記７）前記算出工程は、
下記式（２）により、前記素数Ｐnのビット長に従って、前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記１〜３のいずれか一つに記載の素数生成プログラム。
Ｌｅｎｇｔｈ（Ｐi）＝Ｌｅｎｇｔｈ（Ｐi+1）／２＋１・・・（２）
ただし、Ｌｅｎｇｔｈ（Ｐi）は素数Ｐiのビット長とする。
【０１２０】
（付記８）前記算出工程は、
前記素数Ｐ1のビット長が３０数ビット程度の長さとなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする付記１〜７のいずれか一つに記載の素数生成プログラム。
【０１２１】
（付記９）前記素数生成プログラムは、
Ｐｏｃｋｌｉｎｇｔｏｎ法を利用した素数判定手法により、前記素数Ｐnを確定的に生成させることを特徴とする付記１〜８のいずれか一つに記載の素数生成プログラム。
【０１２２】
（付記１０）付記１〜９のいずれか一つに記載の素数生成プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【０１２３】
（付記１１）素数Ｐnのビット長の指定を受け付ける受付手段と、
前記受付手段によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出手段と、
前記算出手段によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成する素数生成手段と、
を備えることを特徴とする素数生成装置。
【０１２４】
（付記１２）素数Ｐnのビット長の指定を受け付ける受付工程と、
前記受付工程によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出工程と、
前記算出工程によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成する素数生成工程と、
を含んだことを特徴とする素数生成方法。
【産業上の利用可能性】
【０１２５】
以上のように、本発明にかかる素数生成プログラム、該プログラムを記録した記録媒体、素数生成装置および素数生成方法は、確定的な素数生成手法を用いて所定長の素数を生成する場合に有用であり、特に、２のべき乗長以外のビット長の素数を生成する場合に適している。
【図面の簡単な説明】
【０１２６】
【図１】この発明の実施の形態にかかる素数生成装置のハードウェア構成を示すブロック図である。
【図２】素数テーブルのデータ構造を示す説明図である。
【図３】この発明の実施の形態にかかる素数生成装置の機能的構成を示すブロック図である。
【図４】この発明の実施の形態にかかる素数生成装置の素数生成処理手順を示すフローチャートである
【図５】ステップＳ４０２における算出処理手順を示すフローチャートである。
【図６】ステップＳ４０３における素数生成処理手順を示すフローチャート（その１）である。
【図７】ステップＳ４０３における素数生成処理手順を示すフローチャート（その２）である。
【符号の説明】
【０１２７】
１００ 素数生成装置
２００ 素数テーブル
３０１ 受付部
３０２ 算出部
３０３ 素数生成部
３０４ 乱数生成部
３０５ 出力部
【特許請求の範囲】
【請求項１】
素数Ｐnのビット長の指定を受け付けさせる受付工程と、
前記受付工程によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させる算出工程と、
前記算出工程によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成させる素数生成工程と、
をコンピュータに実行させることを特徴とする素数生成プログラム。
【請求項２】
前記算出工程によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、当該各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝を生成させる乱数生成工程を前記コンピュータに実行させ、
前記素数生成工程は、
前記素数Ｐ1のビット長によって特定される素数を生成し、前記乱数生成工程によって生成された乱数｛ｒ1，…，ｒn-1｝を用いて、前記素数Ｐiと前記乱数ｒiとを乗算することにより、前記素数Ｐnを生成させることを特徴とする請求項１に記載の素数生成プログラム。
【請求項３】
前記算出工程は、
前記乱数ｒiのビット長より前記素数Ｐiのビット長が長くなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする請求項１または２に記載の素数生成プログラム。
【請求項４】
請求項１〜３のいずれか一つに記載の素数生成プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【請求項５】
素数Ｐnのビット長の指定を受け付ける受付手段と、
前記受付手段によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出手段と、
前記算出手段によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成する素数生成手段と、
を備えることを特徴とする素数生成装置。
【請求項６】
素数Ｐnのビット長の指定を受け付ける受付工程と、
前記受付工程によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出工程と、
前記算出工程によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成する素数生成工程と、
を含んだことを特徴とする素数生成方法。
【請求項１】
素数Ｐnのビット長の指定を受け付けさせる受付工程と、
前記受付工程によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させる算出工程と、
前記算出工程によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成させる素数生成工程と、
をコンピュータに実行させることを特徴とする素数生成プログラム。
【請求項２】
前記算出工程によって算出された素数｛Ｐ1，…，Ｐn-1｝の各ビット長に従って、当該各素数｛Ｐ1，…，Ｐn-1｝に乗算する乱数｛ｒ1，…，ｒn-1｝を生成させる乱数生成工程を前記コンピュータに実行させ、
前記素数生成工程は、
前記素数Ｐ1のビット長によって特定される素数を生成し、前記乱数生成工程によって生成された乱数｛ｒ1，…，ｒn-1｝を用いて、前記素数Ｐiと前記乱数ｒiとを乗算することにより、前記素数Ｐnを生成させることを特徴とする請求項１に記載の素数生成プログラム。
【請求項３】
前記算出工程は、
前記乱数ｒiのビット長より前記素数Ｐiのビット長が長くなる前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出させることを特徴とする請求項１または２に記載の素数生成プログラム。
【請求項４】
請求項１〜３のいずれか一つに記載の素数生成プログラムを記録した前記コンピュータに読み取り可能な記録媒体。
【請求項５】
素数Ｐnのビット長の指定を受け付ける受付手段と、
前記受付手段によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出手段と、
前記算出手段によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成する素数生成手段と、
を備えることを特徴とする素数生成装置。
【請求項６】
素数Ｐnのビット長の指定を受け付ける受付工程と、
前記受付工程によって指定を受け付けた素数Ｐnのビット長に従って、素数｛Ｐ1，…，Ｐn-1｝の各ビット長を算出する算出工程と、
前記算出工程によって算出された前記素数｛Ｐ1，…，Ｐn-1｝の各ビット長に基づいて、素数Ｐi（１≦ｉ≦ｎ−１）と乱数ｒiとを利用することにより、前記素数Ｐiのビット長より長いビット長でかつ前記素数Ｐiより大きな値の素数Ｐi+1を順次生成して、前記素数Ｐnを生成する素数生成工程と、
を含んだことを特徴とする素数生成方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００８−２１６４１１（Ｐ２００８−２１６４１１Ａ）
【公開日】平成２０年９月１８日（２００８．９．１８）
【国際特許分類】
【出願番号】特願２００７−５１０６２（Ｐ２００７−５１０６２）
【出願日】平成１９年３月１日（２００７．３．１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２０年９月１８日（２００８．９．１８）
【国際特許分類】
【出願日】平成１９年３月１日（２００７．３．１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]