素数生成プログラム
【課題】 各素数候補の試行割算後の本格的素数判定に関し、高速化を図る。
【解決手段】 本格的素数判定に用いられる「ミラー-ラビンテスト」は、１つの底における素数判定が合格の場合、素数である可能性が高い。言い換えると、不合格の場合には、１つの底における素数判定で不合格となる傾向がある。従って、１つの底における「ミラー-ラビンテスト」、一般的には「pの本格的素数判定（途中まで）」を先に行う構成にすることにより、「ミラー-ラビンテスト（１つの底におけるテスト）（ＳＴ４）」、一般的には「pの本格的素数判定（途中まで）（ＳＴ４’）」が不合格となる場合に、以後の処理（ステップＳＴ５〜ＳＴ９または、ステップＳＴ５’〜ＳＴ９’）を実行せずに済む。このため、各素数候補の試行割算後の本格的素数判定に関し、以後の処理（ＳＴ５〜ＳＴ９または、ステップＳＴ５’〜ＳＴ９’）の分だけ高速化を図ることができる。
【解決手段】 本格的素数判定に用いられる「ミラー-ラビンテスト」は、１つの底における素数判定が合格の場合、素数である可能性が高い。言い換えると、不合格の場合には、１つの底における素数判定で不合格となる傾向がある。従って、１つの底における「ミラー-ラビンテスト」、一般的には「pの本格的素数判定（途中まで）」を先に行う構成にすることにより、「ミラー-ラビンテスト（１つの底におけるテスト）（ＳＴ４）」、一般的には「pの本格的素数判定（途中まで）（ＳＴ４’）」が不合格となる場合に、以後の処理（ステップＳＴ５〜ＳＴ９または、ステップＳＴ５’〜ＳＴ９’）を実行せずに済む。このため、各素数候補の試行割算後の本格的素数判定に関し、以後の処理（ＳＴ５〜ＳＴ９または、ステップＳＴ５’〜ＳＴ９’）の分だけ高速化を図ることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、素数生成プログラムに係り、例えば、セーフプライム形の素数に限定されず、本格的素数判定を高速化し得る素数生成プログラムに関する。
【背景技術】
【０００２】
暗号分野においては、ｐを素数としたとき、２ｐ＋１という形の素数が、暗号の安全性を高めるために用いられている。この形の素数はセーフプライム（safe Prime）と呼ばれる。セーフプライムは、ディフィー・ヘルマン（Diffie-Hellman）鍵交換を始めとして、多くの暗号通信プロトコルに用いられている。
【０００３】
このセーフプライムを生成するための効率的な方法は、今のところ知られていない。一般的な生成方法においては、素数候補の乱数ｐを素数判定し、素数であれば、さらにセーフプライム候補の２ｐ＋１を素数判定することにより、セーフプライム形の素数２ｐ＋１を生成している。
【０００４】
しかしながら、この一般的な方法では、乱数ｐの値が大きくなるにつれ、セーフプライム形の素数２ｐ＋１を生成するための時間が、非常に増大するという問題がある。このため、セーフプライム形の素数を生成する素数生成装置を備えた情報システムにおいては、素数生成装置の計算負荷を増大させることにより、システム稼働率が低下してしまう問題がある。
【０００５】
この問題を避ける観点から、セーフプライムを予め生成して保持する方式が知られている。しかしながら、この方式は、情報システムのセキュリティレベルを低下させる場合があるので、根本的な解決にはなっていない。
【０００６】
以上の背景の下で本発明者は、各素数候補の試行割算を予め実行する素数生成方法を提案している（例えば、特許文献１参照）。
【特許文献１】特願２００６−０３６７７９号明細書（未公開先行出願）
【非特許文献１】Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone: ”Handbook of Applied Cryptography”, CRC Press, 1996. p.138 4.2.3 Miller-Rabin test.又は下記ＵＲＬ参照。 http://www.cacr.math.uwaterloo.ca/hac/
【非特許文献２】G.H.Hardy and E.M.Wright: “An Introduction to THE THEORY OF NUMBERS”, Oxford University Press, London, p.80 Theorem103. 又は下記ＵＲＬ参照。 http://primes.utm.edu/notes/proofs/MerDiv2.html
【非特許文献３】ANSI X 9.80, “American National Standard for Financial Services - Prime Number Generation, Primality Testing and Primality Certificates”, American National Standard Institute, 2001.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１記載の素数生成方法は、本発明者の検討によれば、各素数候補の試行割算後の本格的素数判定に関し、高速化を図る余地があると考えられる。
【０００８】
本発明は上記実情を考慮してなされたもので、各素数候補の試行割算後の本格的素数判定に関し、高速化を図り得る素数生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
第１の発明は、Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、前記素数生成装置のコンピュータを、予め複数個の除数が記憶された除数記憶手段、Ｌ−１ビットの第１素数候補ｐとして乱数を生成する乱数生成手段、前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第１素数候補ｐに対し、２である底を用いたミラー-ラビンテストを実行する第１のミラー-ラビンテスト実行手段、前記第１のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュの定理」に基づいて素数判定を実行する素数判定手段、前記素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行手段、前記第２のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、として機能させるための素数生成プログラムである。
【００１０】
第２の発明は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、前記素数生成装置のコンピュータを、予め複数個の除数が記憶された除数記憶手段、前記第１素数候補ｐとして乱数を生成する乱数生成手段、前記第１素数候補ｐに基づいて、前記第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第１素数候補ｐに対し、２である底を用いたミラー-ラビンテストを実行する第１のミラー-ラビンテスト実行手段、前記第１のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法を実行する素数判定手段、前記素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行手段、前記第２のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補ｆ（ｐ）を素数として出力する素数出力手段、として機能させるための素数生成プログラムである。
【００１１】
第３の発明は、Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、前記素数生成装置のコンピュータを、予め複数個の除数が記憶された除数記憶手段、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成手段、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、前記Ｌ／２ビット程度の素数Ｆに応じてＬ−１ビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成手段、前記乱数ｒ、前記素数Ｆ及び前記式ｐ＝２ｒＦ＋１に基づいて、Ｌ−１ビットの第１素数候補ｐを算出する第１素数候補算出手段、前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュの定理」に基づいて素数判定を実行する第１の素数判定手段、前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定手段、前記第２の素数判定手段による判定結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、として機能させるための素数生成プログラムである。
【００１２】
第４の発明は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、前記素数生成装置のコンピュータを、予め複数個の除数が記憶された除数記憶手段、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成手段、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、前記Ｌ／２ビット程度の素数Ｆに応じてＬビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成手段、前記乱数ｒ、前記素数Ｆ及び前記式ｐ＝２ｒＦ＋１に基づいて、Ｌビットの第１素数候補ｐを算出する第１素数候補算出手段、前記第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する第１の素数判定手段、前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定手段、前記第２の素数判定手段による判定結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、として機能させるための素数生成プログラムである。
【００１３】
なお、第１及び第２の各発明は、「ミラー-ラビンテスト」に代えて、当該「ミラー-ラビンテスト」とは異なる確率的素数判定法又は確定的素数判定法を実行してもよい。また、第１及び第２の各発明は、素数判定の対象としての各素数候補ｐ，２ｐ＋１を互いに入れ替えて素数判定を実行してもよい。また、第１及び第３の各発明は、「拡張されたオイラー-ラグランジュの定理」に代えて、当該「拡張されたオイラー-ラグランジュの定理」とは異なる確率的素数判定法又は確定的素数判定法を実行してもよい。また、第３及び第４の各発明は、素数判定の対象としての各素数候補ｐ，ｆ（ｐ）を互いに入れ替えて素数判定を実行してもよい。
【００１４】
また、以上の第１〜第４の各発明は、「プログラム」として表現したが、これに限らず、「装置」、「方法」又は「コンピュータ読取り可能な記憶媒体」として表現してもよいことはいうまでもない。
【００１５】
（作用）
第１の発明においては、第１素数候補ｐについて「ミラー-ラビンテスト」を途中まで実行し、第２素数候補２ｐ＋１について「拡張されたオイラー-ラグランジュの定理」を実行し、第１素数候補ｐについて「ミラー-ラビンテスト」を再開している。
【００１６】
ここで、「ミラー-ラビンテスト」は、１つの底における素数判定が合格の場合、他の底における素数判定も合格する傾向がある。言い換えると、「ミラー-ラビンテスト」は、不合格の場合には、１つの底における素数判定で不合格となる傾向がある。
【００１７】
従って、第１の発明においては、「ミラー-ラビンテスト」を分割して実行し、１つの底における「ミラー-ラビンテスト」が不合格となる場合に、以後の「拡張されたオイラー-ラグランジュの定理」及び他の底における「ミラー-ラビンテスト」を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、以後の「拡張されたオイラー-ラグランジュの定理」による素数判定及び他の底における「ミラー-ラビンテスト」の分だけ高速化を図ることができる。
【００１８】
一方、第３の発明においては、「マウアー法」における「ポクリントンの定理」による素数判定を、「拡張されたオイラー-ラグランジュの定理」の後に実行している。
【００１９】
ここで、「ポクリントンの定理」による素数判定は、２に限らない底のベキ乗算を用いるため、２を底としたベキ乗算を用いる「拡張されたオイラー-ラグランジュの定理」の演算時間よりも長い演算時間を必要とする。
【００２０】
言い換えると、第３の発明においては、短い演算時間の「拡張されたオイラー-ラグランジュの定理」により素数判定が不合格となる場合に、長い演算時間の「ポクリントンの定理」による素数判定を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、ポクリントンの定理による素数判定の分だけ、高速化を図ることができる。
【００２１】
他方、第２又は第４の発明は、第１又は第３の発明における第２素数候補２ｐ＋１に代えて、第２素数候補ｆ（ｐ）を用い、「拡張されたオイラー-ラグランジュの定理」に代えて、「確率的素数判定法又は確定的素数判定法」を用いた構成により、第１又は第３の発明と同様の作用効果を得ることができる。
【発明の効果】
【００２２】
以上説明したように本発明によれば、各素数候補の試行割算後の本格的素数判定に関し、高速化を図ることができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の各実施形態を図面を用いて説明する。なお、以下の説明中、乱数、素数、素数候補、定数項、整数係数、多項式、除数、剰余などの語を用いるが、これらは、乱数データ、素数データ、素数候補データ、定数項データ、整数係数データ、多項式データ、除数データ、剰余データ等のように、「データ」の語を追記して読み替えてもよい。
【００２４】
（第１の実施形態）
図１は本発明の第１の実施形態に係る素数生成装置の構成を示す模式図である。この素数生成装置１０は、具体的には携帯電話又はスマートカードなどの演算機の素数生成部として構成され、ハードウェア及びソフトウェアの組合せにより素数生成処理を行うものである。
【００２５】
例えば素数生成装置１０においては、プログラム記憶部１１、テーブル記憶部１２、不揮発性メモリ１３、入出力Ｉ／Ｆ１４、ＣＰＵ（中央処理装置）１５、乱数生成部１６及び演算部１７が互いにバスを介して接続されている。
【００２６】
プログラム記憶部１１は、ＣＰＵ１５に実行されるプログラムが記憶されるハードウェア資源としてのメモリであり、例えばＲＯＭ（リードオンリーメモリ）が使用可能となっている。ここで、プログラムは、例えば図２に示す素数生成機能を実現させるためのものである。この素数生成機能としては、例えば以下の機能(f11-1)〜(f11-9)を含んでいる。
【００２７】
(f11-1) 複数個の除数が記述された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11-2) 乱数生成部１６の制御により、Ｌ−１ビットの第１素数候補ｐとして乱数を生成する機能。
(f11-3) 演算部１７の制御により、第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出機能。
(f11-4) 演算部１７の制御により、除数テーブルＴ内の除数毎に、各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行機能。
(f11-5) 試行割算実行機能による全ての試行割算の結果が剰余を持つとき、演算部１７の制御により、第１素数候補ｐに対し、２である底を用いたミラー-ラビン（Miller - Rabin）テストを実行する第１のミラー-ラビンテスト実行機能。
【００２８】
ここで、「ミラー-ラビンテスト」について説明する。「ミラー-ラビンテスト」は、ミラー-ラビン法とも呼ばれており、一般的な確率的素数判定法であって、計算効率・誤り確率の両面で優れた素数判定法である。ここで、誤り確率とは、合成数を素数と判定する確率をいう。「ミラー-ラビンテスト」では、素数を合成数と判定する誤りはない。
【００２９】
「ミラー-ラビンテスト」では、判定対象の素数候補に対して、相異なる数個の底（base）に関する素数判定を行う。例えばＡＮＳＩ Ｘ９．８０によれば、５１２ビットの素数判定では、８個の底を用いることが推奨されている。また、「ミラー-ラビンテスト」については、例えば非特許文献１にも記載されている。以下に、ミラー-ラビンテストのステップ（MR-ｉ）〜（MR-iv）を示す。
【００３０】
「ミラー-ラビンテスト」
入力：判定対象の整数ｎ、base（底）
出力：判定結果（「ｎはおそらく素数」、または、「ｎは合成数」）
ステップ：
（MR-ｉ） ｎ−１＝２＾ｓ＊ｔ、ｔは奇数、と分解する（なお、＾はベキ乗を表す）。
（MR-ii） ｂ＝base＾ｔ（ｍｏｄ ｎ）を計算する。
→もしもｂ≡±１（ｍｏｄ ｎ）ならば、「ｎはおそらく素数」を返す。
（MR-iii） 以下の処理をｓ−１回繰り返す。
ｂ＝ｂ＾２（ｍｏｄ ｎ）を計算する。
→もしもｂ≡−１（ｍｏｄ ｎ）ならば、「ｎはおそらく素数」を返す。
（MR-iv） 「ｎは合成数」を返す。
なお、第１のミラー-ラビンテストは、以上のミラー-ラビンテストのうち、baseが２の場合のテストに該当する。また、後述する第２のミラー-ラビンテストは、baseが２でない場合のテストに該当する。
【００３１】
(f11-6) 第１のミラー-ラビンテスト実行機能によるテストの結果が合格のとき、演算部１７の制御により、第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」に基づいて素数判定を実行する素数判定機能。
【００３２】
ここで、「拡張されたオイラー-ラグランジュの定理」について説明する。
「拡張されたオイラー-ラグランジュの定理」
ｐを素数とする。この時、次の２つの主張（EL-ｉ）,（EL-ii）が成り立つ。
【００３３】
（EL-ｉ） ｐ≡１（ｍｏｄ ４）ならば、
２ｐ＋１は素数である ⇔ ２ｐ＋１は２＾ｐ＋１を割り切る。
（Ａ⇔Ｂ：Ａである場合にはＢが成り立つという意味を表す。以下同様）
（EL-ii） ｐ≡３（ｍｏｄ ４）ならば、
２ｐ＋１は素数である ⇔ ２ｐ＋１は２＾ｐ−１を割り切る。
【００３４】
すなわち、ｐがbase＝２のミラー-ラビンテストを通ったなら、他の底に関するミラー-ラビンテストを行う前に、一旦、ｐ（ｍｏｄ ４）の値により、（EL-ｉ）、または、（EL-ii）の方法で、ｐが素数である場合の２ｐ＋１の素数判定を行い、合格した場合は、他の底を用いてｐを素数判定する。
【００３５】
なお、「オイラー-ラグランジュの定理」は、「拡張したオイラー-ラグランジュの定理」における２つの主張（EL-ｉ）（EL-ii）のうち、（EL-ｉ）の主張をいう。また、「オイラー-ラグランジュの定理」については、例えば非特許文献２に記載されている。
【００３６】
(f11-7) 素数判定機能による素数判定の結果が合格のとき、演算部１７の制御により、第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行機能。
【００３７】
(f11-8) 第２のミラー-ラビンテスト実行機能によるテストの結果が合格のとき、第１素数候補ｐに対してルーカス-レーマーテスト（Lucas - Lehmer）を実行する機能。ここで、ルーカス-レーマーテストは、ミラー-ラビンテストと組み合わせることにより、誤り確率を低減可能な素数判定法である。このため、ルーカス-レーマーテストの対象（例、第１素数候補ｐ）と、ミラー-ラビンテストの対象（第１素数候補ｐ）とは同じものとなる。
【００３８】
(f11-9) ルーカス-レーマーテストの結果が合格のとき、第２素数候補２ｐ＋１を素数として出力する素数出力機能。
【００３９】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよい。
【００４０】
テーブル記憶部１２は、ＣＰＵ１５から読出／書込可能なハードウェア資源としてのＲＡＭ（ランダムアクセスメモリ）である。テーブル記憶部１２は、予め除数テーブルＴが記憶されており、さらにＣＰＵ１５により、演算に必要なデータや演算途中のデータ等が記憶される。除数テーブルＴは、試行割算に用いる除数が予め記述されたテーブルである。除数としては、２，３，５，…の如き、素数が小さい順から任意の個数だけ用いられる。このような除数の数列に関する説明は、文献（D. E. Knuth 著（中川圭介訳），“KNUTH 第４分冊 準数値算法／算術演算”，サイエンス社，p.205, 1986.）に記載されている。なお、ここでは、除数テーブルＴにおける除数の最大値を“６５５２１”としている。また、除数テーブルＴは、予めプログラム記憶部１１内のプログラムに含まれていてもよい。
【００４１】
不揮発性メモリ１３は、例えば生成された素数ｐ，２ｐ＋１などがＣＰＵ１５から読出／書込可能に記憶されるハードウェア資源としてのメモリであり、例えば、ＥＥＰＲＯＭ（Electric Erasable Programmable ＲＯＭ）が使用可能となっている。但し、不揮発性メモリ１３は、必須ではなく省略してもよい。
【００４２】
入出力Ｉ／Ｆ１４は、素数生成装置１０と、この素数生成装置１０を保持する情報機器との間のインターフェイス機器であり、例えば、素数生成指令を入力し、得られた素数ｐ，２ｐ＋１を出力する際に用いられる。
【００４３】
ここでいう情報機器としては、何らかの暗号処理を実行するものであれば任意のデバイスが適用可能である。何らかの暗号処理とは、例えば公開鍵暗号方式における暗号処理、復号処理、署名生成処理又は署名検証処理などである。情報機器の例としては、スマートカード又は携帯電話等の如き、ユーザ毎に携帯可能なデバイスが挙げられる。情報機器の用途は任意であり、例えば、非匿名又は匿名のユーザ認証などが挙げられる。
【００４４】
ＣＰＵ１５は、プログラム記憶部１１内のプログラムを実行することにより、例えば図３に示す手順で各部１２〜１７を制御し、素数生成処理を実行する機能を有するものである。
【００４５】
乱数生成部１６は、ＣＰＵ１５により制御されて乱数ｐを生成し、この乱数ｐをバスに送出するハードウェア資源としての乱数生成回路である。ここで、乱数生成部１６により生成される乱数ｐは、真の乱数又は疑似乱数のいずれでもよい。
【００４６】
なお、乱数生成部１６は、独立のハードウェア資源で実現する場合に限らず、ＣＰＵ１５とプログラムで実現してもよい。また、乱数生成部１６を省略し、乱数ｐを外部から入力させる構成としてもよい。
【００４７】
演算部１７は、ＣＰＵ１５により制御され、例えばＣＰＵ１５から入力されたデータに基づいて演算を実行し、演算結果をバスに出力するハードウェア資源としての演算回路である。なお、演算部１７は、処理速度を向上させる観点から独立のハードウェア回路として設けられており、例えばコプロセッサ等の如き、多倍長の演算が可能なものであるが、ハードウェア回路に限らず、ＣＰＵ１５とプログラムで実現してもよい。
【００４８】
なお、このような素数生成装置１０は、ハードウェア及びソフトウェアの組合せに限らず、ハードウェア又はソフトウェアのいずれか一方により構成されてもよい。
【００４９】
次に、以上のように構成された素数生成装置による素数生成方法について図２のフローチャートを参照しながら説明する。
【００５０】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数２ｐ＋１を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【００５１】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、Ｌ−１ビットの第１素数候補ｐとしての乱数を生成する（ＳＴ１）。
【００５２】
次に、素数生成装置１０においては、演算部１７が第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する（ＳＴ２）。
【００５３】
続いて、素数生成装置１０においては、演算部１７が、各素数候補ｐ，２ｐ＋１に対し、除数テーブルＴ内の除数毎に、個別に試行割算を実行する（ＳＴ３）。
【００５４】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数で割り算し、得られた剰余をバスに出力する。
【００５５】
ＣＰＵ１５は、第１素数候補ｐを除数で割り算した剰余が０のとき、又は全ての除数による割り算を終えたとき、第１素数候補ｐに対するステップＳＴ３の試行割算を終了する。なお、ＣＰＵ１５は第２素数候補２ｐ＋１についても同様にステップＳＴ３を実行する。
【００５６】
このステップＳＴ３の実行中、ＣＰＵ１５は、ステップＳＴ３の試行割算を終了したときの剰余が０である場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００５７】
一方、ステップＳＴ３の終了時に、全ての試行割算の結果が剰余を持つ場合（試行割算に成功した場合）には、ＣＰＵ１５は演算部１７を制御し、第１素数候補ｐに対し、２である底を用いたミラー-ラビンテスト（１回目）を実行する（ＳＴ４）。
【００５８】
具体的には、ＣＰＵ１５がミラー-ラビンテストのアルゴリズムに従って演算部１７を制御することにより、２である底を用いた場合のミラー-ラビンテストを実行する。
【００５９】
さてステップＳＴ４のテストの結果、第１素数候補ｐが素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１に戻る。
【００６０】
ステップＳＴ４の素数判定の結果、第１素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御することにより、第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」に基づいて素数判定を実行する。
【００６１】
具体的には、ＣＰＵ１５が「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【００６２】
始めに、素数判定装置１０は、ｐ≡１（ｍｏｄ ４）を計算し（ＳＴ５）、ｐ≡１（ｍｏｄ ４）であれば、２＾ｐ≡−１（ｍｏｄ ２ｐ＋１）か否かを判定する（ＳＴ６：主張(EL-ｉ)対応）。ステップＳＴ６の判定の結果、否の場合（＝主張(EL-ｉ)から２ｐ＋１が素数でない場合）には、素数判定装置１０はステップＳＴ１に戻る。また、ステップＳＴ６の判定の結果、２＾ｐ≡−１（ｍｏｄ ２ｐ＋１）である場合（＝主張(EL-ｉ)から２ｐ＋１が素数である場合）には、素数判定装置１０はステップＳＴ８−１に進む。
【００６３】
一方、ステップ５の判定の結果、ｐ≡３（ｍｏｄ ４）であれば、２＾ｐ≡１（ｍｏｄ ２ｐ＋１）か否かを判定する（ＳＴ７：主張(EL-ii)対応）。ステップＳＴ７の判定の結果、否の場合（＝主張(EL-ii)から２ｐ＋１が素数でない場合）には、素数判定装置１０はステップＳＴ１に戻る。また、ステップＳＴ７の判定の結果、２＾ｐ≡１（ｍｏｄ ２ｐ＋１）である場合（＝主張(EL-ii)から２ｐ＋１が素数である場合）には、素数判定装置１０はステップＳＴ８−１に進む。
【００６４】
次に、ステップＳＴ６又はＳＴ７の判定結果から２ｐ＋１が素数である場合には、素数判定装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、他の７個の底を順次用いてミラー-ラビンテスト（２〜８回目）を実行する（ＳＴ８−１〜ＳＴ８−７）。
【００６５】
ステップＳＴ８−１〜ＳＴ８−７においては、それぞれミラー-ラビンテストの結果が不合格であればステップＳＴ１に戻り、ミラー-ラビンテストの結果が合格であれば次の回のミラー-ラビンテストに進む。
【００６６】
このようにして、ステップＳＴ８−７のミラー-ラビンテストの結果が合格であれば、素数生成装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、ルーカス-レーマーテストを実行し（ＳＴ９）、テストの結果が不合格のときにはステップＳＴ１へ戻る。
【００６７】
一方、ステップＳＴ９のテストの結果が合格のとき（第１素数候補ｐが素数である場合には、素数生成装置１０は、第２素数候補２ｐ＋１と、第１素数候補ｐとをそれぞれ素数２ｐ＋１，ｐとして入出力Ｉ／Ｆ１４から出力する。
【００６８】
上述したように本実施形態によれば、第１素数候補ｐについて「ミラー-ラビンテスト」を途中まで実行し、第２素数候補２ｐ＋１について「拡張されたオイラー-ラグランジュの定理」を実行し、第１素数候補ｐについて「ミラー-ラビンテスト」を再開している。ここで、「ミラー-ラビンテスト」は、１つの底における素数判定が合格の場合、他の底における素数判定も合格する傾向がある。言い換えると、「ミラー-ラビンテスト」は、不合格の場合には、１つの底における素数判定で不合格となる傾向がある。
【００６９】
従って、本実施形態においては、「ミラー-ラビンテスト」を分割して実行し、１つの底における「ミラー-ラビンテスト（ＳＴ４）」が不合格となる場合に、以後の処理（ステップＳＴ５〜ＳＴ９）を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、以後の処理（ＳＴ５〜ＳＴ９）の分だけ高速化を図ることができる。
【００７０】
すなわち、本実施形態は、「ミラー-ラビンテスト」を分割して実行する構成により、「ステップＳＴ４の不合格回数」×「ステップＳＴ５〜ＳＴ９の演算時間」だけ、素数判定処理の時間的高速化を図ることができる（補足すると、特許文献１記載の技術は、試行割算後、「ｐの素数判定」、「２ｐ＋１の素数判定」の順に処理を実行していた。これに対し、本実施形態は、試行割算後、「ｐの素数判定の一部（ＳＴ４）」、「２ｐ＋１の素数判定（ＳＴ５〜ＳＴ７）」、「ｐの素数判定の残り（ＳＴ８−１〜ＳＴ８−７，ＳＴ９）」の順に処理を実行している）。
【００７１】
また、２ｐ＋１の素数判定において、「拡張されたオイラー-ラグランジュの定理」を用いるので、２ｐ＋１の本格的素数判定を確定的かつ高速に実行することができる。
【００７２】
（第２の実施形態）
次に、本発明の第２の実施形態について図１及び図３を参照しながら説明する。
本実施形態は、第１の実施形態を拡張した例であり、具体的には、第１の実施形態のミラー-ラビンテストの分割実行方式を、２ｐ＋１、ｐは素数という形の素数に限定することなく、定数項が０ではない一般的な整数係数の多項式ｆ（Ｘ）に対し、ｆ（Ｘ）、Ｘは素数という形の素数を生成する場合に拡張したものである。
【００７３】
すなわち、本実施形態の素数生成装置１０は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、Ｚは整数Ｘを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成するものである。ここで、第２素数ｆ（ｐ）は、例えば多項式の次数をｎとし、次数毎の整数係数をａn，ａn-1，…，ａ2，ａ1とし、定数項をａ0としたとき、次式に示すように計算される。
【００７４】
ｆ（ｐ）＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0
このような第２素数ｆ（ｐ）は、次数ｎ＝１、整数係数ａ1＝２、定数項ａ0＝１の場合、セーフプライム２ｐ＋１となる。但し、第２素数ｆ（ｐ）は、セーフプライム２ｐ＋１に限定されない。
【００７５】
これに伴い、本実施形態では、「拡張されたオイラー-ラグランジェの定理」に基づく素数判定に代えて、「拡張されたオイラー-ラグランジュの定理」とは異なる確率的素数判定法又は確定的素数判定法を用いている。
【００７６】
具体的には、プログラム記憶部１１に記憶され且つＣＰＵ１５に実行されるプログラムは、図２に示した素数生成機能に代えて、図３に示す素数生成機能を実現させるためのものとなっている。この素数生成機能としては、例えば以下の機能(f11a-1)〜(f11a-9)を含んでいる。
【００７７】
(f11a-1) 複数個の除数が記述された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11a-2) 乱数生成部１６の制御により、第１素数候補ｐとして乱数を生成する機能。
(f11a-3) 演算部１７の制御により、第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する第２素数候補算出機能。
(f11a-4) 演算部１７の制御により、除数テーブルＴ内の除数毎に、各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行機能。
(f11a-5) 試行割算実行機能による全ての試行割算の結果が剰余を持つとき、演算部１７の制御により、第１素数候補ｐに対し、２である底を用いたミラー-ラビン（Miller - Rabin）テストを実行する第１のミラー-ラビンテスト実行機能。
【００７８】
(f11a-6) 第１のミラー-ラビンテスト実行機能によるテストの結果が合格のとき、演算部１７の制御により、第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法を実行する素数判定機能。
【００７９】
ここで、確率的素数判定法又は確定的素数判定法としては、前述した確率的素数判定法（例、フェルマー法、ソロベイ-ストラッセン法、ラビン法など）や確定的素数判定法（例、ミラー法、アドルマン−ルメリ法、コーエン−レンストラ法など）が挙げられる。
【００８０】
(f11a-7) 上記(f11a-6)の素数判定機能による素数判定の結果が合格のとき、演算部１７の制御により、第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行機能。
【００８１】
(f11a-8) 第２のミラー-ラビンテスト実行機能によるテストの結果が合格のとき、第１素数候補ｐに対してルーカス-レーマーテスト（Lucas - Lehmer）を実行する機能。
【００８２】
(f11a-9) ルーカス-レーマーテストの結果が合格のとき、第２素数候補ｆ（ｐ）を素数として出力する素数出力機能。
【００８３】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよいことは前述した通りである。
次に、以上のように構成された素数生成装置による素数生成方法について図３のフローチャートを用いて説明する。
【００８４】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数ｆ（ｐ）を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【００８５】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、第１素数候補ｐとしての乱数を生成する（ＳＴ１１）。
【００８６】
次に、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御し、演算部１７が第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する（ＳＴ１２）。具体的には、ＣＰＵ１５は、第１素数候補ｐと、所定の多項式ｆ（Ｘ）の形とに基づいて、次数n，n-1，…，2，1及び次数毎の整数係数ａn，ａn-1，…，ａ2，ａ1を順次、バスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐと、多項式ｆ（Ｘ）の次数及び次数毎の整数係数とに基づいて、第１素数候補ｐに対する次数のベキ乗を計算し、得られたベキ乗結果と整数係数とを乗算し、得られた多項式の変数項をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。また、ＣＰＵ１５は、ｎ次から１次までの変数項ａn・ｐn，ａn-1・ｐn-1，…，ａ2・ｐ2，ａ1・ｐと、定数項ａ0とをバスを介して演算部１７に入力する。演算部１７は、これら変数項と、定数項とを加算し、得られた多項式ｆ（ｐ）をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。
【００８７】
続いて、素数生成装置１０においては、演算部１７が、各素数候補ｐ，ｆ（ｐ）に対し、除数テーブルＴ内の除数毎に、個別に試行割算を実行する（ＳＴ１３）。
【００８８】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数で割り算し、得られた剰余をバスに出力する。
【００８９】
ＣＰＵ１５は、第１素数候補ｐを除数で割り算した剰余が０のとき、又は全ての除数による割り算を終えたとき、第１素数候補ｐに対するステップＳＴ１３の試行割算を終了する。なお、ＣＰＵ１５は第２素数候補ｆ（ｐ）についても同様にステップＳＴ１３を実行する。
【００９０】
このステップＳＴ１３の実行中、ＣＰＵ１５は、ステップＳＴ１３の試行割算を終了したときの剰余が０である場合（試行割算に失敗した場合）にはステップＳＴ１１に戻る。
【００９１】
一方、ステップＳＴ１３の終了時に、全ての試行割算の結果が剰余を持つ場合（試行割算に成功した場合）には、ＣＰＵ１５は演算部１７を制御し、第１素数候補ｐに対し、２である底を用いたミラー-ラビンテスト（１回目）を実行する（ＳＴ１４）。
【００９２】
具体的には、ＣＰＵ１５がミラー-ラビンテストのアルゴリズムに従って演算部１７を制御することにより、２である底を用いた場合のミラー-ラビンテストを実行する。
【００９３】
さてステップＳＴ１４のテストの結果、第１素数候補ｐが素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１１に戻る。
【００９４】
ステップＳＴ１４の素数判定の結果、第１素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御することにより、第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する。
【００９５】
具体的には、ＣＰＵ１５が「確率的素数判定法又は確定的素数判定法」のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する（ＳＴ１５）。
【００９６】
ステップＳＴ１５の判定の結果、素数でない場合には、素数判定装置１０はステップＳＴ１１に戻る。また、ステップＳＴ１５の判定結果からｆ（ｐ）が素数である場合には、素数判定装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、他の７個の底を順次用いてミラー-ラビンテスト（２〜８回目）を実行する（ＳＴ１６−１〜ＳＴ１６−７）。
【００９７】
ステップＳＴ１６−１〜ＳＴ１６−７においては、それぞれミラー-ラビンテストの結果が不合格であればステップＳＴ１１に戻り、ミラー-ラビンテストの結果が合格であれば次の回のミラー-ラビンテストに進む。
【００９８】
このようにして、ステップＳＴ１６−７のミラー-ラビンテストの結果が合格であれば、素数生成装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、ルーカス-レーマーテストを実行し（ＳＴ１７）、テストの結果が不合格のときにはステップＳＴ１１へ戻る。
【００９９】
一方、ステップＳＴ１７のテストの結果が合格のとき（第１素数候補ｐが素数である場合には、素数生成装置１０は、第２素数候補ｆ（ｐ）と、第１素数候補ｐとをそれぞれ素数ｆ（ｐ），ｐとして入出力Ｉ／Ｆ１４から出力する。
【０１００】
上述したように本実施形態によれば、第１の実施形態と同様に、「ミラー-ラビンテスト」を分割して実行し、１つの底における「ミラー-ラビンテスト（ＳＴ１４）」が不合格となる場合に、以後の処理（ステップＳＴ１５〜ＳＴ１７）を実行せずに済む構成のため、各素数候補ｐ，ｆ（ｐ）の試行割算後の本格的素数判定に関し、以後の処理（ＳＴ１５〜ＳＴ１７）の分だけ高速化を図ることができる。
【０１０１】
すなわち、本実施形態は、「ミラー-ラビンテスト」を分割して実行する構成により、「ステップＳＴ１４の不合格回数」×「ステップＳＴ１５〜ＳＴ１７の演算時間」だけ、素数判定処理の時間的高速化を図ることができる（補足すると、特許文献１記載の技術は、試行割算後、「ｐの素数判定」、「２ｐ＋１の素数判定」の順に処理を実行していた。これに対し、本実施形態は、試行割算後、「ｐの素数判定の一部（ＳＴ１４）」、「２ｐ＋１の素数判定（ＳＴ１５）」、「ｐの素数判定の残り（ＳＴ１６−１〜ＳＴ１６−７，ＳＴ１７）」の順に処理を実行している）。
【０１０２】
また、本実施形態によれば、セーフプライムの形の素数に限らず、第１素数ｐから算出可能で定数項（ａ0）が０ではない多項式ｆ（ｐ）（＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0）の形をもつ第２素数ｆ（ｐ）に対しても、各素数候補の試行割算後の本格的素数判定に関し、高速化を図ることができる。
【０１０３】
（第３の実施形態）
次に、本発明の第３の実施形態について図１及び図４を参照しながら説明する。
本実施形態は、第１の実施形態とは異なり、マウアー法を用いた素数生成法の高速化を図るものである。
【０１０４】
これに伴い、プログラム記憶部１１に記憶され且つＣＰＵ１５に実行されるプログラムは、図２に示した素数生成機能に代えて、図４に示す素数生成機能を実現させるためのものとなっている。この素数生成機能としては、例えば以下の機能(f11b-1)〜(f11b-9)を含んでいる。
【０１０５】
(f11b-1) 複数個の除数が記述された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11b-2) 演算部１７の制御により、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成機能。
【０１０６】
ここで、「マウアー法」について説明する。「マウアー法」とはポクリントン（Pocklington（又はポックリントン））の定理を繰り返し用いて確定的に素数を生成する方法である。より詳しくは、「マウアー法」は、以下に示すポクリントンの定理中の（１）式について、試行割算で求めた小さな素数Ｆからポクリントンの定理により素数Ｆ’を生成し、その素数Ｆ’を素数Ｆに代入して、再びポクリントンの定理を用いて新たにＦ’を生成するという演算を、必要なビット数の素数が得られるまで繰り返し行う素数生成方法である。
【０１０７】
「ポクリントンの定理」は、以下の内容である。
Ｆ’＝２ｒＦ＋１ ・・・（１）
２ｒ＜Ｆ、但しｒは乱数、Ｆは素数。
【０１０８】
この時、ある整数ａが存在して、
ａ＾（Ｆ’−１）≡１（ｍｏｄ Ｆ’）、
g.c.d.（ａ＾｛（Ｆ’−１）／Ｆ｝−１，Ｆ’）＝１
が成り立つならば、Ｆ’は素数である。
【０１０９】
(f11b-3) 乱数生成部１６の制御により、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、Ｌ／２ビット程度の素数Ｆに応じてＬ−１ビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成機能。
(f11b-4) 演算部１７の制御により、乱数ｒ、素数Ｆ及び式ｐ＝２ｒＦ＋１に基づいて、Ｌ−１ビットの第１素数候補ｐを算出する第１素数候補算出機能。
【０１１０】
(f11b-5) 演算部１７の制御により、第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出機能。
【０１１１】
(f11b-6) 演算部１７の制御により、除数テーブルＴ内の除数毎に、各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行機能。
(f11b-7) 試行割算実行機能による全ての試行割算の結果が剰余を持つとき、演算部１７の制御により、第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」に基づいて素数判定を実行する第１の素数判定機能。
【０１１２】
(f11b-8) 第１の素数判定機能による素数判定の結果が合格のとき、演算部１７の制御により、第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定機能。
【０１１３】
(f11b-9) 第２の素数判定機能による素数判定の結果が合格のとき、第２素数候補２ｐ＋１を素数として出力する素数出力機能。
【０１１４】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよい。
【０１１５】
次に、以上のように構成された素数生成装置による素数生成法について図４のフローチャートを用いて説明する。
【０１１６】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数２ｐ＋１を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【０１１７】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が演算部１７を制御し、演算部１７が、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する（ＳＴ２１）。
【０１１８】
続いて、素数生成装置１０においては、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、Ｌ／２ビット程度の素数Ｆに応じてＬ−１ビットの第１素数候補ｐを得られるように、乱数ｒを生成する（ＳＴ２２）。
【０１１９】
次に、素数生成装置１０においては、演算部１７が乱数ｒ、素数Ｆ及び式ｐ＝２ｒＦ＋１に基づいて、Ｌ−１ビットの第１素数候補ｐを算出する（ＳＴ２３）。
【０１２０】
また、素数生成装置１０においては、演算部１７が第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する（ＳＴ２４）。
【０１２１】
続いて、素数生成装置１０においては、演算部１７が、各素数候補ｐ，２ｐ＋１に対し、除数テーブルＴ内の除数毎に、個別に試行割算を実行する（ＳＴ２５）。
【０１２２】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数で割り算し、得られた剰余をバスに出力する。
【０１２３】
ＣＰＵ１５は、第１素数候補ｐを除数で割り算した剰余が０のとき、又は全ての除数による割り算を終えたとき、第１素数候補ｐに対するステップＳＴ２５の試行割算を終了する。なお、ＣＰＵ１５は第２素数候補２ｐ＋１についても同様にステップＳＴ２５を実行する。
【０１２４】
このステップＳＴ２５の実行中、ＣＰＵ１５は、ステップＳＴ２５の試行割算を終了したときの剰余が０である場合（試行割算に失敗した場合）にはステップＳＴ２１に戻る。
【０１２５】
一方、ステップＳＴ２５の終了時に、全ての試行割算の結果が剰余を持つ場合（試行割算に成功した場合）には、ＣＰＵ１５は演算部１７を制御することにより、第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」に基づいて素数判定を実行する。
【０１２６】
具体的には、ＣＰＵ１５が「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【０１２７】
始めに、素数判定装置１０は、ｐ≡１（ｍｏｄ ４）を計算し（ＳＴ２６）、ｐ≡１（ｍｏｄ ４）であれば、２＾ｐ≡−１（ｍｏｄ ２ｐ＋１）か否かを判定する（ＳＴ２７：主張(EL-ｉ)対応）。ステップＳＴ２７の判定の結果、否の場合（＝主張(EL-ｉ)から２ｐ＋１が素数でない場合）には、素数判定装置１０はステップＳＴ２２に戻る。また、ステップＳＴ２７の判定の結果、２＾ｐ≡−１（ｍｏｄ ２ｐ＋１）である場合（＝主張(EL-ｉ)から２ｐ＋１が素数である場合）には、素数判定装置１０はステップＳＴ２９に進む。
【０１２８】
一方、ステップ２６の判定の結果、ｐ≡３（ｍｏｄ ４）であれば、２＾ｐ≡１（ｍｏｄ ２ｐ＋１）か否かを判定する（ＳＴ２８：主張(EL-ii)対応）。ステップＳＴ２８の判定の結果、否の場合（＝主張(EL-ii)から２ｐ＋１が素数でない場合）には、素数判定装置１０はステップＳＴ２２に戻る。また、ステップＳＴ２８の判定の結果、２＾ｐ≡１（ｍｏｄ ２ｐ＋１）である場合（＝主張(EL-ii)から２ｐ＋１が素数である場合）には、素数判定装置１０はステップＳＴ２９に進む。
【０１２９】
次に、ステップＳＴ２７又はＳＴ２８の判定結果から２ｐ＋１が素数である場合には、素数判定装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する（ＳＴ２９）。ステップＳＴ２９の判定の結果、不合格の場合（＝第１素数候補ｐが素数でない場合）には、素数判定装置１０はステップＳＴ２２に戻る。
【０１３０】
一方、ステップＳＴ２９の素数判定の結果が合格のとき（第１素数候補ｐが素数である場合）には、素数生成装置１０は、第２素数候補２ｐ＋１と、第１素数候補ｐとをそれぞれ素数２ｐ＋１，ｐとして入出力Ｉ／Ｆ１４から出力する。
【０１３１】
上述したように本実施形態によれば、「マウアー法」における「ポクリントンの定理」による素数判定を、「拡張されたオイラー-ラグランジュの定理」の後に実行している。
【０１３２】
ここで、「ポクリントンの定理」による素数判定は、２に限らない底のベキ乗算を用いるため、２を底としたベキ乗算を用いる「拡張されたオイラー-ラグランジュの定理」の演算時間よりも長い演算時間を必要とする。
【０１３３】
言い換えると、本実施形態においては、短い演算時間の「拡張されたオイラー-ラグランジュの定理」により素数判定が不合格となる場合に、長い演算時間の「ポクリントンの定理」による素数判定を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、ポクリントンの定理による素数判定（ステップＳＴ２９）の分だけ、高速化を図ることができる。
【０１３４】
補足すると、従来、マウアー法においては、多数の乱数ｒを発生させ、複数回ポクリントンの定理が成り立つかを確かめることで、第１素数ｐを生成させ、その後に第２素数候補２ｐ＋１を素数判定する。しかしながら、従来のマウアー法では、第２素数候補２ｐ＋１の素数判定が不合格の場合には、第１素数候補ｐを素数と確定させる演算が無駄になってしまう。そこで、本実施形態では、ポクリントンの定理による第１素数候補ｐの素数判定を行う前に、拡張されたオイラー-ラグランジュの定理を用いた第２素数候補２ｐ＋１の素数判定を先に実行し、第２素数候補２ｐ＋１の素数判定が合格の場合に、ポクリントンの定理を用いて、第２素数候補２ｐ＋１を素数判定している。
【０１３５】
また、本実施形態では、「マウアー法」を用いた構成により、確定的にセーフプライムを生成することができる。
【０１３６】
（第４の実施形態）
次に、本発明の第４の実施形態について図１及び図５を参照しながら説明する。
本実施形態は、第２及び第３の実施形態を組み合わせた例であり、具体的には、第３の実施形態のマウアー法の分割実行方式を、２ｐ＋１、ｐは素数という形の素数に限定することなく、第２の実施形態に述べた多項式ｆ（Ｘ）、Ｘは素数という形の素数を生成する場合に拡張したものである。
【０１３７】
これに伴い、本実施形態では、「拡張されたオイラー-ラグランジェの定理」に基づく素数判定に代えて、「拡張されたオイラー-ラグランジュの定理」とは異なる確率的素数判定法又は確定的素数判定法を用いている。
【０１３８】
具体的には、プログラム記憶部１１に記憶され且つＣＰＵ１５に実行されるプログラムは、図３又は図４に示した素数生成機能に代えて、図５に示す素数生成機能を実現させるためのものとなっている。この素数生成機能としては、例えば以下の機能(f11c-1)〜(f11c-9)を含んでいる。
【０１３９】
(f11c-1) 複数個の除数が記述された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11c-2) 演算部１７の制御により、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成機能。
【０１４０】
(f11c-3) 乱数生成部１６の制御により、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、Ｌ／２ビット程度の素数Ｆに応じてＬビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成機能。
(f11c-4) 演算部１７の制御により、乱数ｒ、素数Ｆ及び式ｐ＝２ｒＦ＋１に基づいて、Ｌビットの第１素数候補ｐを算出する第１素数候補算出機能。
【０１４１】
(f11c-5) 演算部１７の制御により、第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する第２素数候補算出機能。
【０１４２】
(f11c-6) 演算部１７の制御により、除数テーブルＴ内の除数毎に、各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行機能。
(f11c-7) 試行割算実行機能による全ての試行割算の結果が剰余を持つとき、演算部１７の制御により、第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する第１の素数判定機能。
【０１４３】
(f11c-8) 第１の素数判定機能による素数判定の結果が合格のとき、演算部１７の制御により、第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定機能。
【０１４４】
(f11c-9) 第２の素数判定機能による素数判定の結果が合格のとき、第２素数候補ｆ（ｐ）を素数として出力する素数出力機能。
【０１４５】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよいことは前述した通りである。
【０１４６】
次に、以上のように構成された素数生成装置による素数生成法について図５のフローチャートを用いて説明する。
【０１４７】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数ｆ（ｐ）を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【０１４８】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が演算部１７を制御し、演算部１７が、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する（ＳＴ３１）。
【０１４９】
続いて、素数生成装置１０においては、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、Ｌ／２ビット程度の素数Ｆに応じてＬビットの第１素数候補ｐを得られるように、乱数ｒを生成する（ＳＴ３２）。
【０１５０】
次に、素数生成装置１０においては、演算部１７が乱数ｒ、素数Ｆ及び式ｐ＝２ｒＦ＋１に基づいて、Ｌビットの第１素数候補ｐを算出する（ＳＴ３３）。
【０１５１】
また、素数生成装置１０においては、演算部１７が第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する（ＳＴ３４）。
【０１５２】
続いて、素数生成装置１０においては、演算部１７が、各素数候補ｐ，ｆ（ｐ）に対し、除数テーブルＴ内の除数毎に、個別に試行割算を実行する（ＳＴ３５）。
【０１５３】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数で割り算し、得られた剰余をバスに出力する。
【０１５４】
ＣＰＵ１５は、第１素数候補ｐを除数で割り算した剰余が０のとき、又は全ての除数による割り算を終えたとき、第１素数候補ｐに対するステップＳＴ３５の試行割算を終了する。なお、ＣＰＵ１５は第２素数候補ｆ（ｐ）についても同様にステップＳＴ３５を実行する。
【０１５５】
このステップＳＴ３５の実行中、ＣＰＵ１５は、ステップＳＴ３５の試行割算を終了したときの剰余が０である場合（試行割算に失敗した場合）にはステップＳＴ３２に戻る。
【０１５６】
一方、ステップＳＴ３５の終了時に、全ての試行割算の結果が剰余を持つ場合（試行割算に成功した場合）には、ＣＰＵ１５は演算部１７を制御することにより、第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する（ＳＴ３６）。具体的には、ＣＰＵ１５が確率的素数判定法又は確定的素数判定法のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【０１５７】
ステップＳＴ３６の判定の結果、不合格の場合（＝第２素数候補ｆ（ｐ）が素数でない場合）には、素数判定装置１０はステップＳＴ３２に戻る。
【０１５８】
一方、ステップＳＴ３６の判定結果から第２素数候補ｆ（ｐ）が素数である場合には、素数判定装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する（ＳＴ３７）。ステップＳＴ３７の判定の結果、不合格の場合（＝第１素数候補ｐが素数でない場合）には、素数判定装置１０はステップＳＴ３２に戻る。
【０１５９】
一方、ステップＳＴ３７の素数判定の結果が合格のとき（第１素数候補ｐが素数である場合）には、素数生成装置１０は、第２素数候補ｆ（ｐ）と、第１素数候補ｐとをそれぞれ素数ｆ（ｐ），ｐとして入出力Ｉ／Ｆ１４から出力する。
【０１６０】
上述したように本実施形態によれば、第３の実施形態と同様に、「マウアー法」における「ポクリントンの定理」による素数判定を、確率的素数判定法又は確定的素数判定法の後に実行している。
【０１６１】
ここで、「ポクリントンの定理」による素数判定は、２に限らない底のベキ乗算を用いるため、２を底としたベキ乗算を用いる「確率的素数判定法又は確定的素数判定法」の演算時間よりも長い演算時間を必要とする。
【０１６２】
言い換えると、本実施形態においては、短い演算時間の「確率的素数判定法又は確定的素数判定法」により素数判定が不合格となる場合に、長い演算時間の「ポクリントンの定理」による素数判定を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、ポクリントンの定理による素数判定（ステップＳＴ３７）の分だけ、高速化を図ることができる。
【０１６３】
（他の変形例）
（１）第１及び第３の実施形態は、「ミラー-ラビンテスト（ミラー-ラビン法）」や「マウアー法」に代えて、図６に示すように、数ステップからなる他の確率的素数判定法又は確定的素数判定法を分割した構成の素数生成を行なうように変形してもよい。同様に、第１及び第３の実施形態は、「拡張されたオイラー-ラグランジュの定理」に代えて、他の確率的素数判定法又は確定的素数判定法を用いるように変形してもよい。
【０１６４】
ここで、確率的素数判定法の例としては、フェルマー(Fermat)法、ソロベイ(Solovay)ーストラッセン(Strassen)法、ラビン法などが挙げられる。確定的素数判定法の例としては、ミラー法、アドルマン(Adleman)−ルメリ(Rumely)法、コーエン(Cohen)−レンストラ(Lenstra)法を用いる方法などが挙げられる。これらの例は、文献（池野信一、小山謙二共著、“現代暗号理論”、（社）電子情報通信学会、コロナ社、ｐ２４０−２４１、１９８６）に記載されている。また、ポクリントンの定理を用いる素数生成法である、シャウ(Shawe)−テイラー(Taylor)の方法は、非特許文献３に記載されている。
【０１６５】
また、変形例（１）においては、第１の実施形態を変形した場合、第１素数候補ｐに対し、「ミラー-ラビンテスト」とは異なる第１の確率的素数判定法又は確定的素数判定法を途中まで実行し、この第１の素数判定法による素数判定の結果が合格のとき、第２素数候補２ｐ＋１に対し、第２の確率的素数判定法又は確定的素数判定法を実行し、この第２の素数判定法による素数判定の結果が合格のとき、第１素数候補ｐに対し、第１の素数判定法による素数判定を再開し、この素数判定を最後まで実行して素数判定の結果が合格のとき、各素数候補ｐ，２ｐ＋１を素数として出力する。
【０１６６】
また、変形例（１）においては、第３の実施形態を変形した場合、第１素数候補ｐに対し、「マウアー法」とは異なる第１の確率的素数判定法又は確定的素数判定法を途中まで実行し、この第１の素数判定法による素数判定の結果が合格のとき、第２素数候補２ｐ＋１に対し、第２の確率的素数判定法又は確定的素数判定法を実行し、この第２の素数判定法による素数判定の結果が合格のとき、第１素数候補ｐに対し、第１の素数判定法による素数判定を再開し、この素数判定を最後まで実行して素数判定の結果が合格のとき、各素数候補ｐ，２ｐ＋１を素数として出力する。
【０１６７】
以上のように変形しても、適用した第１又は第３の実施形態と同様の作用効果を得ることができる。
【０１６８】
（２）第２及び第４の実施形態は、「ミラー-ラビンテスト（ミラー-ラビン法）」や「マウアー法」に代えて、図７に示すように、数ステップからなる他の確率的素数判定法又は確定的素数判定法を分割した構成の素数生成を行なうように変形してもよい。このように変形しても、適用した第２又は第４の実施形態と同様の作用効果を得ることができる。
【０１６９】
詳しくは、変形例（２）においては、第２の実施形態を変形した場合、第１素数候補ｐに対し、「ミラー-ラビンテスト」とは異なる第１の確率的素数判定法又は確定的素数判定法を途中まで実行し、この第１の素数判定法による素数判定の結果が合格のとき、第２素数候補ｆ（ｐ）に対し、第２の確率的素数判定法又は確定的素数判定法を実行し、この第２の素数判定法による素数判定の結果が合格のとき、第１素数候補ｐに対し、第１の素数判定法による素数判定を再開し、この素数判定を最後まで実行して素数判定の結果が合格のとき、各素数候補ｐ，ｆ（ｐ）を素数として出力する。
【０１７０】
また、変形例（２）においては、第４の実施形態を変形した場合、第１素数候補ｐに対し、「マウアー法」とは異なる第１の確率的素数判定法又は確定的素数判定法を途中まで実行し、この第１の素数判定法による素数判定の結果が合格のとき、第２素数候補ｆ（ｐ）に対し、第２の確率的素数判定法又は確定的素数判定法を実行し、この第２の素数判定法による素数判定の結果が合格のとき、第１素数候補ｐに対し、第１の素数判定法による素数判定を再開し、この素数判定を最後まで実行して素数判定の結果が合格のとき、各素数候補ｐ，ｆ（ｐ）を素数として出力する。
【０１７１】
（３）上記変形例（１）は、図８に示すように、第１素数候補ｐと、第２素数候補２ｐ＋１との素数判定の順番を逆にするように変形してもよい。このように変形しても、適用した変形例（１）と同様の作用効果を得ることができる。また、第２素数候補２ｐ＋１を最後まで素数判定し、その後、第１素数候補ｐを素数判定してもよい。
【０１７２】
（４）上記変形例（２）は、図９に示すように、第１素数候補ｐと、第２素数候補ｆ（ｐ）との素数判定の順番を逆にするように変形してもよい。このように変形しても、適用した変形例（２）と同様の作用効果を得ることができる。また、第２素数候補ｆ（ｐ）を最後まで素数判定し、その後、第１素数候補ｐを素数判定してもよい。
【０１７３】
変形例（２）、（４）については、次のように処理を効率化することができる。素数pをマウアー法で生成し、偶数kについて、f(p)=kp+1とし、f(p)をポクリントンの定理で判定する際に、kがp及びf(p)へ行う試行割算の最大数のビット数以下程度にとる。このとき、次のステップ(a)-(e)により、確定的にp及びf(p)を素数判定することが出来る。
【０１７４】
(a)素数p=2rF+1となるFをマウアー法で生成する。
【０１７５】
(b)乱数rを生成する。
【０１７６】
(c)pとf(p)へ試行割算を行う。
【０１７７】
(d)f(p)が素数であるかポクリントンの定理で判定するため、下記を検証。
2^{f(p)-1} ≡ 1 (mod f(p))
(e)pを通常のマウアー法で、素数判定する。
【０１７８】
ここで、(d)において、通常のポクリントンの定理に従うならば、
G.C.D.( 2^{(f(p)-1)/F}−1, f(p)) = 1
についても検証しなくてはならないが、これについては(c)の試行割算を通過した時点で、検証を行っているため、この処理を省くことが出来る。
【０１７９】
（５）上記変形例（１）から（４）において、いずれかの素数をポクリントンの定理を用いて素数判定する際に、第１の判定条件を次のように変形してもよい。すなわち、整数nを素数判定する際に、ある整数aが存在して、
a^{n-1} ≡ 1 (mod n)
が成立することを確かめるフェルマー(Fermat)法の代わりに、整数nに対して底aに関するミラー-ラビンテストが成り立つことを確かめる。このように変形しても、検証の誤判定率を低減させることなく、変形例（１）から（４）と同様の作用効果を得ることができる。更には一般にミラー-ラビンテストに要する時間は、フェルマー(Fermat)法に要する時間より短いため、判定時間を低減させることが可能となる。
【０１８０】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１８１】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１８２】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１８３】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１８４】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１８５】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１８６】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１８７】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１８８】
【図１】本発明の第１の実施形態に係る素数生成装置の構成を示す模式図である。
【図２】同実施形態における素数生成方法を説明するためのフローチャートである。
【図３】本発明の第２の実施形態における素数生成方法を説明するためのフローチャートである。
【図４】本発明の第３の実施形態における素数生成方法を説明するためのフローチャートである。
【図５】本発明の第４の実施形態における素数生成方法を説明するためのフローチャートである。
【図６】本発明の変形例を説明するためのフローチャートである。
【図７】本発明の変形例を説明するためのフローチャートである。
【図８】本発明の変形例を説明するためのフローチャートである。
【図９】本発明の変形例を説明するためのフローチャートである。
【符号の説明】
【０１８９】
１０…素数生成装置、１１…プログラム記憶部、１２…テーブル記憶部、１３…不揮発性メモリ、１４…入出力Ｉ／Ｆ、１５…ＣＰＵ、１６…乱数生成部、１７…演算部、Ｔ…除算テーブル。
【技術分野】
【０００１】
本発明は、素数生成プログラムに係り、例えば、セーフプライム形の素数に限定されず、本格的素数判定を高速化し得る素数生成プログラムに関する。
【背景技術】
【０００２】
暗号分野においては、ｐを素数としたとき、２ｐ＋１という形の素数が、暗号の安全性を高めるために用いられている。この形の素数はセーフプライム（safe Prime）と呼ばれる。セーフプライムは、ディフィー・ヘルマン（Diffie-Hellman）鍵交換を始めとして、多くの暗号通信プロトコルに用いられている。
【０００３】
このセーフプライムを生成するための効率的な方法は、今のところ知られていない。一般的な生成方法においては、素数候補の乱数ｐを素数判定し、素数であれば、さらにセーフプライム候補の２ｐ＋１を素数判定することにより、セーフプライム形の素数２ｐ＋１を生成している。
【０００４】
しかしながら、この一般的な方法では、乱数ｐの値が大きくなるにつれ、セーフプライム形の素数２ｐ＋１を生成するための時間が、非常に増大するという問題がある。このため、セーフプライム形の素数を生成する素数生成装置を備えた情報システムにおいては、素数生成装置の計算負荷を増大させることにより、システム稼働率が低下してしまう問題がある。
【０００５】
この問題を避ける観点から、セーフプライムを予め生成して保持する方式が知られている。しかしながら、この方式は、情報システムのセキュリティレベルを低下させる場合があるので、根本的な解決にはなっていない。
【０００６】
以上の背景の下で本発明者は、各素数候補の試行割算を予め実行する素数生成方法を提案している（例えば、特許文献１参照）。
【特許文献１】特願２００６−０３６７７９号明細書（未公開先行出願）
【非特許文献１】Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone: ”Handbook of Applied Cryptography”, CRC Press, 1996. p.138 4.2.3 Miller-Rabin test.又は下記ＵＲＬ参照。 http://www.cacr.math.uwaterloo.ca/hac/
【非特許文献２】G.H.Hardy and E.M.Wright: “An Introduction to THE THEORY OF NUMBERS”, Oxford University Press, London, p.80 Theorem103. 又は下記ＵＲＬ参照。 http://primes.utm.edu/notes/proofs/MerDiv2.html
【非特許文献３】ANSI X 9.80, “American National Standard for Financial Services - Prime Number Generation, Primality Testing and Primality Certificates”, American National Standard Institute, 2001.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１記載の素数生成方法は、本発明者の検討によれば、各素数候補の試行割算後の本格的素数判定に関し、高速化を図る余地があると考えられる。
【０００８】
本発明は上記実情を考慮してなされたもので、各素数候補の試行割算後の本格的素数判定に関し、高速化を図り得る素数生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
第１の発明は、Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、前記素数生成装置のコンピュータを、予め複数個の除数が記憶された除数記憶手段、Ｌ−１ビットの第１素数候補ｐとして乱数を生成する乱数生成手段、前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第１素数候補ｐに対し、２である底を用いたミラー-ラビンテストを実行する第１のミラー-ラビンテスト実行手段、前記第１のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュの定理」に基づいて素数判定を実行する素数判定手段、前記素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行手段、前記第２のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、として機能させるための素数生成プログラムである。
【００１０】
第２の発明は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、前記素数生成装置のコンピュータを、予め複数個の除数が記憶された除数記憶手段、前記第１素数候補ｐとして乱数を生成する乱数生成手段、前記第１素数候補ｐに基づいて、前記第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第１素数候補ｐに対し、２である底を用いたミラー-ラビンテストを実行する第１のミラー-ラビンテスト実行手段、前記第１のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法を実行する素数判定手段、前記素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行手段、前記第２のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補ｆ（ｐ）を素数として出力する素数出力手段、として機能させるための素数生成プログラムである。
【００１１】
第３の発明は、Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、前記素数生成装置のコンピュータを、予め複数個の除数が記憶された除数記憶手段、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成手段、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、前記Ｌ／２ビット程度の素数Ｆに応じてＬ−１ビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成手段、前記乱数ｒ、前記素数Ｆ及び前記式ｐ＝２ｒＦ＋１に基づいて、Ｌ−１ビットの第１素数候補ｐを算出する第１素数候補算出手段、前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュの定理」に基づいて素数判定を実行する第１の素数判定手段、前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定手段、前記第２の素数判定手段による判定結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、として機能させるための素数生成プログラムである。
【００１２】
第４の発明は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、前記素数生成装置のコンピュータを、予め複数個の除数が記憶された除数記憶手段、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成手段、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、前記Ｌ／２ビット程度の素数Ｆに応じてＬビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成手段、前記乱数ｒ、前記素数Ｆ及び前記式ｐ＝２ｒＦ＋１に基づいて、Ｌビットの第１素数候補ｐを算出する第１素数候補算出手段、前記第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する第１の素数判定手段、前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定手段、前記第２の素数判定手段による判定結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、として機能させるための素数生成プログラムである。
【００１３】
なお、第１及び第２の各発明は、「ミラー-ラビンテスト」に代えて、当該「ミラー-ラビンテスト」とは異なる確率的素数判定法又は確定的素数判定法を実行してもよい。また、第１及び第２の各発明は、素数判定の対象としての各素数候補ｐ，２ｐ＋１を互いに入れ替えて素数判定を実行してもよい。また、第１及び第３の各発明は、「拡張されたオイラー-ラグランジュの定理」に代えて、当該「拡張されたオイラー-ラグランジュの定理」とは異なる確率的素数判定法又は確定的素数判定法を実行してもよい。また、第３及び第４の各発明は、素数判定の対象としての各素数候補ｐ，ｆ（ｐ）を互いに入れ替えて素数判定を実行してもよい。
【００１４】
また、以上の第１〜第４の各発明は、「プログラム」として表現したが、これに限らず、「装置」、「方法」又は「コンピュータ読取り可能な記憶媒体」として表現してもよいことはいうまでもない。
【００１５】
（作用）
第１の発明においては、第１素数候補ｐについて「ミラー-ラビンテスト」を途中まで実行し、第２素数候補２ｐ＋１について「拡張されたオイラー-ラグランジュの定理」を実行し、第１素数候補ｐについて「ミラー-ラビンテスト」を再開している。
【００１６】
ここで、「ミラー-ラビンテスト」は、１つの底における素数判定が合格の場合、他の底における素数判定も合格する傾向がある。言い換えると、「ミラー-ラビンテスト」は、不合格の場合には、１つの底における素数判定で不合格となる傾向がある。
【００１７】
従って、第１の発明においては、「ミラー-ラビンテスト」を分割して実行し、１つの底における「ミラー-ラビンテスト」が不合格となる場合に、以後の「拡張されたオイラー-ラグランジュの定理」及び他の底における「ミラー-ラビンテスト」を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、以後の「拡張されたオイラー-ラグランジュの定理」による素数判定及び他の底における「ミラー-ラビンテスト」の分だけ高速化を図ることができる。
【００１８】
一方、第３の発明においては、「マウアー法」における「ポクリントンの定理」による素数判定を、「拡張されたオイラー-ラグランジュの定理」の後に実行している。
【００１９】
ここで、「ポクリントンの定理」による素数判定は、２に限らない底のベキ乗算を用いるため、２を底としたベキ乗算を用いる「拡張されたオイラー-ラグランジュの定理」の演算時間よりも長い演算時間を必要とする。
【００２０】
言い換えると、第３の発明においては、短い演算時間の「拡張されたオイラー-ラグランジュの定理」により素数判定が不合格となる場合に、長い演算時間の「ポクリントンの定理」による素数判定を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、ポクリントンの定理による素数判定の分だけ、高速化を図ることができる。
【００２１】
他方、第２又は第４の発明は、第１又は第３の発明における第２素数候補２ｐ＋１に代えて、第２素数候補ｆ（ｐ）を用い、「拡張されたオイラー-ラグランジュの定理」に代えて、「確率的素数判定法又は確定的素数判定法」を用いた構成により、第１又は第３の発明と同様の作用効果を得ることができる。
【発明の効果】
【００２２】
以上説明したように本発明によれば、各素数候補の試行割算後の本格的素数判定に関し、高速化を図ることができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の各実施形態を図面を用いて説明する。なお、以下の説明中、乱数、素数、素数候補、定数項、整数係数、多項式、除数、剰余などの語を用いるが、これらは、乱数データ、素数データ、素数候補データ、定数項データ、整数係数データ、多項式データ、除数データ、剰余データ等のように、「データ」の語を追記して読み替えてもよい。
【００２４】
（第１の実施形態）
図１は本発明の第１の実施形態に係る素数生成装置の構成を示す模式図である。この素数生成装置１０は、具体的には携帯電話又はスマートカードなどの演算機の素数生成部として構成され、ハードウェア及びソフトウェアの組合せにより素数生成処理を行うものである。
【００２５】
例えば素数生成装置１０においては、プログラム記憶部１１、テーブル記憶部１２、不揮発性メモリ１３、入出力Ｉ／Ｆ１４、ＣＰＵ（中央処理装置）１５、乱数生成部１６及び演算部１７が互いにバスを介して接続されている。
【００２６】
プログラム記憶部１１は、ＣＰＵ１５に実行されるプログラムが記憶されるハードウェア資源としてのメモリであり、例えばＲＯＭ（リードオンリーメモリ）が使用可能となっている。ここで、プログラムは、例えば図２に示す素数生成機能を実現させるためのものである。この素数生成機能としては、例えば以下の機能(f11-1)〜(f11-9)を含んでいる。
【００２７】
(f11-1) 複数個の除数が記述された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11-2) 乱数生成部１６の制御により、Ｌ−１ビットの第１素数候補ｐとして乱数を生成する機能。
(f11-3) 演算部１７の制御により、第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出機能。
(f11-4) 演算部１７の制御により、除数テーブルＴ内の除数毎に、各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行機能。
(f11-5) 試行割算実行機能による全ての試行割算の結果が剰余を持つとき、演算部１７の制御により、第１素数候補ｐに対し、２である底を用いたミラー-ラビン（Miller - Rabin）テストを実行する第１のミラー-ラビンテスト実行機能。
【００２８】
ここで、「ミラー-ラビンテスト」について説明する。「ミラー-ラビンテスト」は、ミラー-ラビン法とも呼ばれており、一般的な確率的素数判定法であって、計算効率・誤り確率の両面で優れた素数判定法である。ここで、誤り確率とは、合成数を素数と判定する確率をいう。「ミラー-ラビンテスト」では、素数を合成数と判定する誤りはない。
【００２９】
「ミラー-ラビンテスト」では、判定対象の素数候補に対して、相異なる数個の底（base）に関する素数判定を行う。例えばＡＮＳＩ Ｘ９．８０によれば、５１２ビットの素数判定では、８個の底を用いることが推奨されている。また、「ミラー-ラビンテスト」については、例えば非特許文献１にも記載されている。以下に、ミラー-ラビンテストのステップ（MR-ｉ）〜（MR-iv）を示す。
【００３０】
「ミラー-ラビンテスト」
入力：判定対象の整数ｎ、base（底）
出力：判定結果（「ｎはおそらく素数」、または、「ｎは合成数」）
ステップ：
（MR-ｉ） ｎ−１＝２＾ｓ＊ｔ、ｔは奇数、と分解する（なお、＾はベキ乗を表す）。
（MR-ii） ｂ＝base＾ｔ（ｍｏｄ ｎ）を計算する。
→もしもｂ≡±１（ｍｏｄ ｎ）ならば、「ｎはおそらく素数」を返す。
（MR-iii） 以下の処理をｓ−１回繰り返す。
ｂ＝ｂ＾２（ｍｏｄ ｎ）を計算する。
→もしもｂ≡−１（ｍｏｄ ｎ）ならば、「ｎはおそらく素数」を返す。
（MR-iv） 「ｎは合成数」を返す。
なお、第１のミラー-ラビンテストは、以上のミラー-ラビンテストのうち、baseが２の場合のテストに該当する。また、後述する第２のミラー-ラビンテストは、baseが２でない場合のテストに該当する。
【００３１】
(f11-6) 第１のミラー-ラビンテスト実行機能によるテストの結果が合格のとき、演算部１７の制御により、第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」に基づいて素数判定を実行する素数判定機能。
【００３２】
ここで、「拡張されたオイラー-ラグランジュの定理」について説明する。
「拡張されたオイラー-ラグランジュの定理」
ｐを素数とする。この時、次の２つの主張（EL-ｉ）,（EL-ii）が成り立つ。
【００３３】
（EL-ｉ） ｐ≡１（ｍｏｄ ４）ならば、
２ｐ＋１は素数である ⇔ ２ｐ＋１は２＾ｐ＋１を割り切る。
（Ａ⇔Ｂ：Ａである場合にはＢが成り立つという意味を表す。以下同様）
（EL-ii） ｐ≡３（ｍｏｄ ４）ならば、
２ｐ＋１は素数である ⇔ ２ｐ＋１は２＾ｐ−１を割り切る。
【００３４】
すなわち、ｐがbase＝２のミラー-ラビンテストを通ったなら、他の底に関するミラー-ラビンテストを行う前に、一旦、ｐ（ｍｏｄ ４）の値により、（EL-ｉ）、または、（EL-ii）の方法で、ｐが素数である場合の２ｐ＋１の素数判定を行い、合格した場合は、他の底を用いてｐを素数判定する。
【００３５】
なお、「オイラー-ラグランジュの定理」は、「拡張したオイラー-ラグランジュの定理」における２つの主張（EL-ｉ）（EL-ii）のうち、（EL-ｉ）の主張をいう。また、「オイラー-ラグランジュの定理」については、例えば非特許文献２に記載されている。
【００３６】
(f11-7) 素数判定機能による素数判定の結果が合格のとき、演算部１７の制御により、第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行機能。
【００３７】
(f11-8) 第２のミラー-ラビンテスト実行機能によるテストの結果が合格のとき、第１素数候補ｐに対してルーカス-レーマーテスト（Lucas - Lehmer）を実行する機能。ここで、ルーカス-レーマーテストは、ミラー-ラビンテストと組み合わせることにより、誤り確率を低減可能な素数判定法である。このため、ルーカス-レーマーテストの対象（例、第１素数候補ｐ）と、ミラー-ラビンテストの対象（第１素数候補ｐ）とは同じものとなる。
【００３８】
(f11-9) ルーカス-レーマーテストの結果が合格のとき、第２素数候補２ｐ＋１を素数として出力する素数出力機能。
【００３９】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよい。
【００４０】
テーブル記憶部１２は、ＣＰＵ１５から読出／書込可能なハードウェア資源としてのＲＡＭ（ランダムアクセスメモリ）である。テーブル記憶部１２は、予め除数テーブルＴが記憶されており、さらにＣＰＵ１５により、演算に必要なデータや演算途中のデータ等が記憶される。除数テーブルＴは、試行割算に用いる除数が予め記述されたテーブルである。除数としては、２，３，５，…の如き、素数が小さい順から任意の個数だけ用いられる。このような除数の数列に関する説明は、文献（D. E. Knuth 著（中川圭介訳），“KNUTH 第４分冊 準数値算法／算術演算”，サイエンス社，p.205, 1986.）に記載されている。なお、ここでは、除数テーブルＴにおける除数の最大値を“６５５２１”としている。また、除数テーブルＴは、予めプログラム記憶部１１内のプログラムに含まれていてもよい。
【００４１】
不揮発性メモリ１３は、例えば生成された素数ｐ，２ｐ＋１などがＣＰＵ１５から読出／書込可能に記憶されるハードウェア資源としてのメモリであり、例えば、ＥＥＰＲＯＭ（Electric Erasable Programmable ＲＯＭ）が使用可能となっている。但し、不揮発性メモリ１３は、必須ではなく省略してもよい。
【００４２】
入出力Ｉ／Ｆ１４は、素数生成装置１０と、この素数生成装置１０を保持する情報機器との間のインターフェイス機器であり、例えば、素数生成指令を入力し、得られた素数ｐ，２ｐ＋１を出力する際に用いられる。
【００４３】
ここでいう情報機器としては、何らかの暗号処理を実行するものであれば任意のデバイスが適用可能である。何らかの暗号処理とは、例えば公開鍵暗号方式における暗号処理、復号処理、署名生成処理又は署名検証処理などである。情報機器の例としては、スマートカード又は携帯電話等の如き、ユーザ毎に携帯可能なデバイスが挙げられる。情報機器の用途は任意であり、例えば、非匿名又は匿名のユーザ認証などが挙げられる。
【００４４】
ＣＰＵ１５は、プログラム記憶部１１内のプログラムを実行することにより、例えば図３に示す手順で各部１２〜１７を制御し、素数生成処理を実行する機能を有するものである。
【００４５】
乱数生成部１６は、ＣＰＵ１５により制御されて乱数ｐを生成し、この乱数ｐをバスに送出するハードウェア資源としての乱数生成回路である。ここで、乱数生成部１６により生成される乱数ｐは、真の乱数又は疑似乱数のいずれでもよい。
【００４６】
なお、乱数生成部１６は、独立のハードウェア資源で実現する場合に限らず、ＣＰＵ１５とプログラムで実現してもよい。また、乱数生成部１６を省略し、乱数ｐを外部から入力させる構成としてもよい。
【００４７】
演算部１７は、ＣＰＵ１５により制御され、例えばＣＰＵ１５から入力されたデータに基づいて演算を実行し、演算結果をバスに出力するハードウェア資源としての演算回路である。なお、演算部１７は、処理速度を向上させる観点から独立のハードウェア回路として設けられており、例えばコプロセッサ等の如き、多倍長の演算が可能なものであるが、ハードウェア回路に限らず、ＣＰＵ１５とプログラムで実現してもよい。
【００４８】
なお、このような素数生成装置１０は、ハードウェア及びソフトウェアの組合せに限らず、ハードウェア又はソフトウェアのいずれか一方により構成されてもよい。
【００４９】
次に、以上のように構成された素数生成装置による素数生成方法について図２のフローチャートを参照しながら説明する。
【００５０】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数２ｐ＋１を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【００５１】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、Ｌ−１ビットの第１素数候補ｐとしての乱数を生成する（ＳＴ１）。
【００５２】
次に、素数生成装置１０においては、演算部１７が第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する（ＳＴ２）。
【００５３】
続いて、素数生成装置１０においては、演算部１７が、各素数候補ｐ，２ｐ＋１に対し、除数テーブルＴ内の除数毎に、個別に試行割算を実行する（ＳＴ３）。
【００５４】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数で割り算し、得られた剰余をバスに出力する。
【００５５】
ＣＰＵ１５は、第１素数候補ｐを除数で割り算した剰余が０のとき、又は全ての除数による割り算を終えたとき、第１素数候補ｐに対するステップＳＴ３の試行割算を終了する。なお、ＣＰＵ１５は第２素数候補２ｐ＋１についても同様にステップＳＴ３を実行する。
【００５６】
このステップＳＴ３の実行中、ＣＰＵ１５は、ステップＳＴ３の試行割算を終了したときの剰余が０である場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００５７】
一方、ステップＳＴ３の終了時に、全ての試行割算の結果が剰余を持つ場合（試行割算に成功した場合）には、ＣＰＵ１５は演算部１７を制御し、第１素数候補ｐに対し、２である底を用いたミラー-ラビンテスト（１回目）を実行する（ＳＴ４）。
【００５８】
具体的には、ＣＰＵ１５がミラー-ラビンテストのアルゴリズムに従って演算部１７を制御することにより、２である底を用いた場合のミラー-ラビンテストを実行する。
【００５９】
さてステップＳＴ４のテストの結果、第１素数候補ｐが素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１に戻る。
【００６０】
ステップＳＴ４の素数判定の結果、第１素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御することにより、第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」に基づいて素数判定を実行する。
【００６１】
具体的には、ＣＰＵ１５が「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【００６２】
始めに、素数判定装置１０は、ｐ≡１（ｍｏｄ ４）を計算し（ＳＴ５）、ｐ≡１（ｍｏｄ ４）であれば、２＾ｐ≡−１（ｍｏｄ ２ｐ＋１）か否かを判定する（ＳＴ６：主張(EL-ｉ)対応）。ステップＳＴ６の判定の結果、否の場合（＝主張(EL-ｉ)から２ｐ＋１が素数でない場合）には、素数判定装置１０はステップＳＴ１に戻る。また、ステップＳＴ６の判定の結果、２＾ｐ≡−１（ｍｏｄ ２ｐ＋１）である場合（＝主張(EL-ｉ)から２ｐ＋１が素数である場合）には、素数判定装置１０はステップＳＴ８−１に進む。
【００６３】
一方、ステップ５の判定の結果、ｐ≡３（ｍｏｄ ４）であれば、２＾ｐ≡１（ｍｏｄ ２ｐ＋１）か否かを判定する（ＳＴ７：主張(EL-ii)対応）。ステップＳＴ７の判定の結果、否の場合（＝主張(EL-ii)から２ｐ＋１が素数でない場合）には、素数判定装置１０はステップＳＴ１に戻る。また、ステップＳＴ７の判定の結果、２＾ｐ≡１（ｍｏｄ ２ｐ＋１）である場合（＝主張(EL-ii)から２ｐ＋１が素数である場合）には、素数判定装置１０はステップＳＴ８−１に進む。
【００６４】
次に、ステップＳＴ６又はＳＴ７の判定結果から２ｐ＋１が素数である場合には、素数判定装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、他の７個の底を順次用いてミラー-ラビンテスト（２〜８回目）を実行する（ＳＴ８−１〜ＳＴ８−７）。
【００６５】
ステップＳＴ８−１〜ＳＴ８−７においては、それぞれミラー-ラビンテストの結果が不合格であればステップＳＴ１に戻り、ミラー-ラビンテストの結果が合格であれば次の回のミラー-ラビンテストに進む。
【００６６】
このようにして、ステップＳＴ８−７のミラー-ラビンテストの結果が合格であれば、素数生成装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、ルーカス-レーマーテストを実行し（ＳＴ９）、テストの結果が不合格のときにはステップＳＴ１へ戻る。
【００６７】
一方、ステップＳＴ９のテストの結果が合格のとき（第１素数候補ｐが素数である場合には、素数生成装置１０は、第２素数候補２ｐ＋１と、第１素数候補ｐとをそれぞれ素数２ｐ＋１，ｐとして入出力Ｉ／Ｆ１４から出力する。
【００６８】
上述したように本実施形態によれば、第１素数候補ｐについて「ミラー-ラビンテスト」を途中まで実行し、第２素数候補２ｐ＋１について「拡張されたオイラー-ラグランジュの定理」を実行し、第１素数候補ｐについて「ミラー-ラビンテスト」を再開している。ここで、「ミラー-ラビンテスト」は、１つの底における素数判定が合格の場合、他の底における素数判定も合格する傾向がある。言い換えると、「ミラー-ラビンテスト」は、不合格の場合には、１つの底における素数判定で不合格となる傾向がある。
【００６９】
従って、本実施形態においては、「ミラー-ラビンテスト」を分割して実行し、１つの底における「ミラー-ラビンテスト（ＳＴ４）」が不合格となる場合に、以後の処理（ステップＳＴ５〜ＳＴ９）を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、以後の処理（ＳＴ５〜ＳＴ９）の分だけ高速化を図ることができる。
【００７０】
すなわち、本実施形態は、「ミラー-ラビンテスト」を分割して実行する構成により、「ステップＳＴ４の不合格回数」×「ステップＳＴ５〜ＳＴ９の演算時間」だけ、素数判定処理の時間的高速化を図ることができる（補足すると、特許文献１記載の技術は、試行割算後、「ｐの素数判定」、「２ｐ＋１の素数判定」の順に処理を実行していた。これに対し、本実施形態は、試行割算後、「ｐの素数判定の一部（ＳＴ４）」、「２ｐ＋１の素数判定（ＳＴ５〜ＳＴ７）」、「ｐの素数判定の残り（ＳＴ８−１〜ＳＴ８−７，ＳＴ９）」の順に処理を実行している）。
【００７１】
また、２ｐ＋１の素数判定において、「拡張されたオイラー-ラグランジュの定理」を用いるので、２ｐ＋１の本格的素数判定を確定的かつ高速に実行することができる。
【００７２】
（第２の実施形態）
次に、本発明の第２の実施形態について図１及び図３を参照しながら説明する。
本実施形態は、第１の実施形態を拡張した例であり、具体的には、第１の実施形態のミラー-ラビンテストの分割実行方式を、２ｐ＋１、ｐは素数という形の素数に限定することなく、定数項が０ではない一般的な整数係数の多項式ｆ（Ｘ）に対し、ｆ（Ｘ）、Ｘは素数という形の素数を生成する場合に拡張したものである。
【００７３】
すなわち、本実施形態の素数生成装置１０は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、Ｚは整数Ｘを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成するものである。ここで、第２素数ｆ（ｐ）は、例えば多項式の次数をｎとし、次数毎の整数係数をａn，ａn-1，…，ａ2，ａ1とし、定数項をａ0としたとき、次式に示すように計算される。
【００７４】
ｆ（ｐ）＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0
このような第２素数ｆ（ｐ）は、次数ｎ＝１、整数係数ａ1＝２、定数項ａ0＝１の場合、セーフプライム２ｐ＋１となる。但し、第２素数ｆ（ｐ）は、セーフプライム２ｐ＋１に限定されない。
【００７５】
これに伴い、本実施形態では、「拡張されたオイラー-ラグランジェの定理」に基づく素数判定に代えて、「拡張されたオイラー-ラグランジュの定理」とは異なる確率的素数判定法又は確定的素数判定法を用いている。
【００７６】
具体的には、プログラム記憶部１１に記憶され且つＣＰＵ１５に実行されるプログラムは、図２に示した素数生成機能に代えて、図３に示す素数生成機能を実現させるためのものとなっている。この素数生成機能としては、例えば以下の機能(f11a-1)〜(f11a-9)を含んでいる。
【００７７】
(f11a-1) 複数個の除数が記述された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11a-2) 乱数生成部１６の制御により、第１素数候補ｐとして乱数を生成する機能。
(f11a-3) 演算部１７の制御により、第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する第２素数候補算出機能。
(f11a-4) 演算部１７の制御により、除数テーブルＴ内の除数毎に、各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行機能。
(f11a-5) 試行割算実行機能による全ての試行割算の結果が剰余を持つとき、演算部１７の制御により、第１素数候補ｐに対し、２である底を用いたミラー-ラビン（Miller - Rabin）テストを実行する第１のミラー-ラビンテスト実行機能。
【００７８】
(f11a-6) 第１のミラー-ラビンテスト実行機能によるテストの結果が合格のとき、演算部１７の制御により、第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法を実行する素数判定機能。
【００７９】
ここで、確率的素数判定法又は確定的素数判定法としては、前述した確率的素数判定法（例、フェルマー法、ソロベイ-ストラッセン法、ラビン法など）や確定的素数判定法（例、ミラー法、アドルマン−ルメリ法、コーエン−レンストラ法など）が挙げられる。
【００８０】
(f11a-7) 上記(f11a-6)の素数判定機能による素数判定の結果が合格のとき、演算部１７の制御により、第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行機能。
【００８１】
(f11a-8) 第２のミラー-ラビンテスト実行機能によるテストの結果が合格のとき、第１素数候補ｐに対してルーカス-レーマーテスト（Lucas - Lehmer）を実行する機能。
【００８２】
(f11a-9) ルーカス-レーマーテストの結果が合格のとき、第２素数候補ｆ（ｐ）を素数として出力する素数出力機能。
【００８３】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよいことは前述した通りである。
次に、以上のように構成された素数生成装置による素数生成方法について図３のフローチャートを用いて説明する。
【００８４】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数ｆ（ｐ）を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【００８５】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、第１素数候補ｐとしての乱数を生成する（ＳＴ１１）。
【００８６】
次に、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御し、演算部１７が第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する（ＳＴ１２）。具体的には、ＣＰＵ１５は、第１素数候補ｐと、所定の多項式ｆ（Ｘ）の形とに基づいて、次数n，n-1，…，2，1及び次数毎の整数係数ａn，ａn-1，…，ａ2，ａ1を順次、バスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐと、多項式ｆ（Ｘ）の次数及び次数毎の整数係数とに基づいて、第１素数候補ｐに対する次数のベキ乗を計算し、得られたベキ乗結果と整数係数とを乗算し、得られた多項式の変数項をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。また、ＣＰＵ１５は、ｎ次から１次までの変数項ａn・ｐn，ａn-1・ｐn-1，…，ａ2・ｐ2，ａ1・ｐと、定数項ａ0とをバスを介して演算部１７に入力する。演算部１７は、これら変数項と、定数項とを加算し、得られた多項式ｆ（ｐ）をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。
【００８７】
続いて、素数生成装置１０においては、演算部１７が、各素数候補ｐ，ｆ（ｐ）に対し、除数テーブルＴ内の除数毎に、個別に試行割算を実行する（ＳＴ１３）。
【００８８】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数で割り算し、得られた剰余をバスに出力する。
【００８９】
ＣＰＵ１５は、第１素数候補ｐを除数で割り算した剰余が０のとき、又は全ての除数による割り算を終えたとき、第１素数候補ｐに対するステップＳＴ１３の試行割算を終了する。なお、ＣＰＵ１５は第２素数候補ｆ（ｐ）についても同様にステップＳＴ１３を実行する。
【００９０】
このステップＳＴ１３の実行中、ＣＰＵ１５は、ステップＳＴ１３の試行割算を終了したときの剰余が０である場合（試行割算に失敗した場合）にはステップＳＴ１１に戻る。
【００９１】
一方、ステップＳＴ１３の終了時に、全ての試行割算の結果が剰余を持つ場合（試行割算に成功した場合）には、ＣＰＵ１５は演算部１７を制御し、第１素数候補ｐに対し、２である底を用いたミラー-ラビンテスト（１回目）を実行する（ＳＴ１４）。
【００９２】
具体的には、ＣＰＵ１５がミラー-ラビンテストのアルゴリズムに従って演算部１７を制御することにより、２である底を用いた場合のミラー-ラビンテストを実行する。
【００９３】
さてステップＳＴ１４のテストの結果、第１素数候補ｐが素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１１に戻る。
【００９４】
ステップＳＴ１４の素数判定の結果、第１素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御することにより、第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する。
【００９５】
具体的には、ＣＰＵ１５が「確率的素数判定法又は確定的素数判定法」のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する（ＳＴ１５）。
【００９６】
ステップＳＴ１５の判定の結果、素数でない場合には、素数判定装置１０はステップＳＴ１１に戻る。また、ステップＳＴ１５の判定結果からｆ（ｐ）が素数である場合には、素数判定装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、他の７個の底を順次用いてミラー-ラビンテスト（２〜８回目）を実行する（ＳＴ１６−１〜ＳＴ１６−７）。
【００９７】
ステップＳＴ１６−１〜ＳＴ１６−７においては、それぞれミラー-ラビンテストの結果が不合格であればステップＳＴ１１に戻り、ミラー-ラビンテストの結果が合格であれば次の回のミラー-ラビンテストに進む。
【００９８】
このようにして、ステップＳＴ１６−７のミラー-ラビンテストの結果が合格であれば、素数生成装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、ルーカス-レーマーテストを実行し（ＳＴ１７）、テストの結果が不合格のときにはステップＳＴ１１へ戻る。
【００９９】
一方、ステップＳＴ１７のテストの結果が合格のとき（第１素数候補ｐが素数である場合には、素数生成装置１０は、第２素数候補ｆ（ｐ）と、第１素数候補ｐとをそれぞれ素数ｆ（ｐ），ｐとして入出力Ｉ／Ｆ１４から出力する。
【０１００】
上述したように本実施形態によれば、第１の実施形態と同様に、「ミラー-ラビンテスト」を分割して実行し、１つの底における「ミラー-ラビンテスト（ＳＴ１４）」が不合格となる場合に、以後の処理（ステップＳＴ１５〜ＳＴ１７）を実行せずに済む構成のため、各素数候補ｐ，ｆ（ｐ）の試行割算後の本格的素数判定に関し、以後の処理（ＳＴ１５〜ＳＴ１７）の分だけ高速化を図ることができる。
【０１０１】
すなわち、本実施形態は、「ミラー-ラビンテスト」を分割して実行する構成により、「ステップＳＴ１４の不合格回数」×「ステップＳＴ１５〜ＳＴ１７の演算時間」だけ、素数判定処理の時間的高速化を図ることができる（補足すると、特許文献１記載の技術は、試行割算後、「ｐの素数判定」、「２ｐ＋１の素数判定」の順に処理を実行していた。これに対し、本実施形態は、試行割算後、「ｐの素数判定の一部（ＳＴ１４）」、「２ｐ＋１の素数判定（ＳＴ１５）」、「ｐの素数判定の残り（ＳＴ１６−１〜ＳＴ１６−７，ＳＴ１７）」の順に処理を実行している）。
【０１０２】
また、本実施形態によれば、セーフプライムの形の素数に限らず、第１素数ｐから算出可能で定数項（ａ0）が０ではない多項式ｆ（ｐ）（＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0）の形をもつ第２素数ｆ（ｐ）に対しても、各素数候補の試行割算後の本格的素数判定に関し、高速化を図ることができる。
【０１０３】
（第３の実施形態）
次に、本発明の第３の実施形態について図１及び図４を参照しながら説明する。
本実施形態は、第１の実施形態とは異なり、マウアー法を用いた素数生成法の高速化を図るものである。
【０１０４】
これに伴い、プログラム記憶部１１に記憶され且つＣＰＵ１５に実行されるプログラムは、図２に示した素数生成機能に代えて、図４に示す素数生成機能を実現させるためのものとなっている。この素数生成機能としては、例えば以下の機能(f11b-1)〜(f11b-9)を含んでいる。
【０１０５】
(f11b-1) 複数個の除数が記述された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11b-2) 演算部１７の制御により、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成機能。
【０１０６】
ここで、「マウアー法」について説明する。「マウアー法」とはポクリントン（Pocklington（又はポックリントン））の定理を繰り返し用いて確定的に素数を生成する方法である。より詳しくは、「マウアー法」は、以下に示すポクリントンの定理中の（１）式について、試行割算で求めた小さな素数Ｆからポクリントンの定理により素数Ｆ’を生成し、その素数Ｆ’を素数Ｆに代入して、再びポクリントンの定理を用いて新たにＦ’を生成するという演算を、必要なビット数の素数が得られるまで繰り返し行う素数生成方法である。
【０１０７】
「ポクリントンの定理」は、以下の内容である。
Ｆ’＝２ｒＦ＋１ ・・・（１）
２ｒ＜Ｆ、但しｒは乱数、Ｆは素数。
【０１０８】
この時、ある整数ａが存在して、
ａ＾（Ｆ’−１）≡１（ｍｏｄ Ｆ’）、
g.c.d.（ａ＾｛（Ｆ’−１）／Ｆ｝−１，Ｆ’）＝１
が成り立つならば、Ｆ’は素数である。
【０１０９】
(f11b-3) 乱数生成部１６の制御により、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、Ｌ／２ビット程度の素数Ｆに応じてＬ−１ビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成機能。
(f11b-4) 演算部１７の制御により、乱数ｒ、素数Ｆ及び式ｐ＝２ｒＦ＋１に基づいて、Ｌ−１ビットの第１素数候補ｐを算出する第１素数候補算出機能。
【０１１０】
(f11b-5) 演算部１７の制御により、第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出機能。
【０１１１】
(f11b-6) 演算部１７の制御により、除数テーブルＴ内の除数毎に、各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行機能。
(f11b-7) 試行割算実行機能による全ての試行割算の結果が剰余を持つとき、演算部１７の制御により、第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」に基づいて素数判定を実行する第１の素数判定機能。
【０１１２】
(f11b-8) 第１の素数判定機能による素数判定の結果が合格のとき、演算部１７の制御により、第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定機能。
【０１１３】
(f11b-9) 第２の素数判定機能による素数判定の結果が合格のとき、第２素数候補２ｐ＋１を素数として出力する素数出力機能。
【０１１４】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよい。
【０１１５】
次に、以上のように構成された素数生成装置による素数生成法について図４のフローチャートを用いて説明する。
【０１１６】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数２ｐ＋１を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【０１１７】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が演算部１７を制御し、演算部１７が、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する（ＳＴ２１）。
【０１１８】
続いて、素数生成装置１０においては、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、Ｌ／２ビット程度の素数Ｆに応じてＬ−１ビットの第１素数候補ｐを得られるように、乱数ｒを生成する（ＳＴ２２）。
【０１１９】
次に、素数生成装置１０においては、演算部１７が乱数ｒ、素数Ｆ及び式ｐ＝２ｒＦ＋１に基づいて、Ｌ−１ビットの第１素数候補ｐを算出する（ＳＴ２３）。
【０１２０】
また、素数生成装置１０においては、演算部１７が第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する（ＳＴ２４）。
【０１２１】
続いて、素数生成装置１０においては、演算部１７が、各素数候補ｐ，２ｐ＋１に対し、除数テーブルＴ内の除数毎に、個別に試行割算を実行する（ＳＴ２５）。
【０１２２】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数で割り算し、得られた剰余をバスに出力する。
【０１２３】
ＣＰＵ１５は、第１素数候補ｐを除数で割り算した剰余が０のとき、又は全ての除数による割り算を終えたとき、第１素数候補ｐに対するステップＳＴ２５の試行割算を終了する。なお、ＣＰＵ１５は第２素数候補２ｐ＋１についても同様にステップＳＴ２５を実行する。
【０１２４】
このステップＳＴ２５の実行中、ＣＰＵ１５は、ステップＳＴ２５の試行割算を終了したときの剰余が０である場合（試行割算に失敗した場合）にはステップＳＴ２１に戻る。
【０１２５】
一方、ステップＳＴ２５の終了時に、全ての試行割算の結果が剰余を持つ場合（試行割算に成功した場合）には、ＣＰＵ１５は演算部１７を制御することにより、第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」に基づいて素数判定を実行する。
【０１２６】
具体的には、ＣＰＵ１５が「拡張されたオイラー-ラグランジュ（Euler - Lagrange）の定理」のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【０１２７】
始めに、素数判定装置１０は、ｐ≡１（ｍｏｄ ４）を計算し（ＳＴ２６）、ｐ≡１（ｍｏｄ ４）であれば、２＾ｐ≡−１（ｍｏｄ ２ｐ＋１）か否かを判定する（ＳＴ２７：主張(EL-ｉ)対応）。ステップＳＴ２７の判定の結果、否の場合（＝主張(EL-ｉ)から２ｐ＋１が素数でない場合）には、素数判定装置１０はステップＳＴ２２に戻る。また、ステップＳＴ２７の判定の結果、２＾ｐ≡−１（ｍｏｄ ２ｐ＋１）である場合（＝主張(EL-ｉ)から２ｐ＋１が素数である場合）には、素数判定装置１０はステップＳＴ２９に進む。
【０１２８】
一方、ステップ２６の判定の結果、ｐ≡３（ｍｏｄ ４）であれば、２＾ｐ≡１（ｍｏｄ ２ｐ＋１）か否かを判定する（ＳＴ２８：主張(EL-ii)対応）。ステップＳＴ２８の判定の結果、否の場合（＝主張(EL-ii)から２ｐ＋１が素数でない場合）には、素数判定装置１０はステップＳＴ２２に戻る。また、ステップＳＴ２８の判定の結果、２＾ｐ≡１（ｍｏｄ ２ｐ＋１）である場合（＝主張(EL-ii)から２ｐ＋１が素数である場合）には、素数判定装置１０はステップＳＴ２９に進む。
【０１２９】
次に、ステップＳＴ２７又はＳＴ２８の判定結果から２ｐ＋１が素数である場合には、素数判定装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する（ＳＴ２９）。ステップＳＴ２９の判定の結果、不合格の場合（＝第１素数候補ｐが素数でない場合）には、素数判定装置１０はステップＳＴ２２に戻る。
【０１３０】
一方、ステップＳＴ２９の素数判定の結果が合格のとき（第１素数候補ｐが素数である場合）には、素数生成装置１０は、第２素数候補２ｐ＋１と、第１素数候補ｐとをそれぞれ素数２ｐ＋１，ｐとして入出力Ｉ／Ｆ１４から出力する。
【０１３１】
上述したように本実施形態によれば、「マウアー法」における「ポクリントンの定理」による素数判定を、「拡張されたオイラー-ラグランジュの定理」の後に実行している。
【０１３２】
ここで、「ポクリントンの定理」による素数判定は、２に限らない底のベキ乗算を用いるため、２を底としたベキ乗算を用いる「拡張されたオイラー-ラグランジュの定理」の演算時間よりも長い演算時間を必要とする。
【０１３３】
言い換えると、本実施形態においては、短い演算時間の「拡張されたオイラー-ラグランジュの定理」により素数判定が不合格となる場合に、長い演算時間の「ポクリントンの定理」による素数判定を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、ポクリントンの定理による素数判定（ステップＳＴ２９）の分だけ、高速化を図ることができる。
【０１３４】
補足すると、従来、マウアー法においては、多数の乱数ｒを発生させ、複数回ポクリントンの定理が成り立つかを確かめることで、第１素数ｐを生成させ、その後に第２素数候補２ｐ＋１を素数判定する。しかしながら、従来のマウアー法では、第２素数候補２ｐ＋１の素数判定が不合格の場合には、第１素数候補ｐを素数と確定させる演算が無駄になってしまう。そこで、本実施形態では、ポクリントンの定理による第１素数候補ｐの素数判定を行う前に、拡張されたオイラー-ラグランジュの定理を用いた第２素数候補２ｐ＋１の素数判定を先に実行し、第２素数候補２ｐ＋１の素数判定が合格の場合に、ポクリントンの定理を用いて、第２素数候補２ｐ＋１を素数判定している。
【０１３５】
また、本実施形態では、「マウアー法」を用いた構成により、確定的にセーフプライムを生成することができる。
【０１３６】
（第４の実施形態）
次に、本発明の第４の実施形態について図１及び図５を参照しながら説明する。
本実施形態は、第２及び第３の実施形態を組み合わせた例であり、具体的には、第３の実施形態のマウアー法の分割実行方式を、２ｐ＋１、ｐは素数という形の素数に限定することなく、第２の実施形態に述べた多項式ｆ（Ｘ）、Ｘは素数という形の素数を生成する場合に拡張したものである。
【０１３７】
これに伴い、本実施形態では、「拡張されたオイラー-ラグランジェの定理」に基づく素数判定に代えて、「拡張されたオイラー-ラグランジュの定理」とは異なる確率的素数判定法又は確定的素数判定法を用いている。
【０１３８】
具体的には、プログラム記憶部１１に記憶され且つＣＰＵ１５に実行されるプログラムは、図３又は図４に示した素数生成機能に代えて、図５に示す素数生成機能を実現させるためのものとなっている。この素数生成機能としては、例えば以下の機能(f11c-1)〜(f11c-9)を含んでいる。
【０１３９】
(f11c-1) 複数個の除数が記述された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11c-2) 演算部１７の制御により、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成機能。
【０１４０】
(f11c-3) 乱数生成部１６の制御により、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、Ｌ／２ビット程度の素数Ｆに応じてＬビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成機能。
(f11c-4) 演算部１７の制御により、乱数ｒ、素数Ｆ及び式ｐ＝２ｒＦ＋１に基づいて、Ｌビットの第１素数候補ｐを算出する第１素数候補算出機能。
【０１４１】
(f11c-5) 演算部１７の制御により、第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する第２素数候補算出機能。
【０１４２】
(f11c-6) 演算部１７の制御により、除数テーブルＴ内の除数毎に、各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行機能。
(f11c-7) 試行割算実行機能による全ての試行割算の結果が剰余を持つとき、演算部１７の制御により、第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する第１の素数判定機能。
【０１４３】
(f11c-8) 第１の素数判定機能による素数判定の結果が合格のとき、演算部１７の制御により、第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定機能。
【０１４４】
(f11c-9) 第２の素数判定機能による素数判定の結果が合格のとき、第２素数候補ｆ（ｐ）を素数として出力する素数出力機能。
【０１４５】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよいことは前述した通りである。
【０１４６】
次に、以上のように構成された素数生成装置による素数生成法について図５のフローチャートを用いて説明する。
【０１４７】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数ｆ（ｐ）を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【０１４８】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が演算部１７を制御し、演算部１７が、「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する（ＳＴ３１）。
【０１４９】
続いて、素数生成装置１０においては、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、Ｌ／２ビット程度の素数Ｆに応じてＬビットの第１素数候補ｐを得られるように、乱数ｒを生成する（ＳＴ３２）。
【０１５０】
次に、素数生成装置１０においては、演算部１７が乱数ｒ、素数Ｆ及び式ｐ＝２ｒＦ＋１に基づいて、Ｌビットの第１素数候補ｐを算出する（ＳＴ３３）。
【０１５１】
また、素数生成装置１０においては、演算部１７が第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する（ＳＴ３４）。
【０１５２】
続いて、素数生成装置１０においては、演算部１７が、各素数候補ｐ，ｆ（ｐ）に対し、除数テーブルＴ内の除数毎に、個別に試行割算を実行する（ＳＴ３５）。
【０１５３】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数で割り算し、得られた剰余をバスに出力する。
【０１５４】
ＣＰＵ１５は、第１素数候補ｐを除数で割り算した剰余が０のとき、又は全ての除数による割り算を終えたとき、第１素数候補ｐに対するステップＳＴ３５の試行割算を終了する。なお、ＣＰＵ１５は第２素数候補ｆ（ｐ）についても同様にステップＳＴ３５を実行する。
【０１５５】
このステップＳＴ３５の実行中、ＣＰＵ１５は、ステップＳＴ３５の試行割算を終了したときの剰余が０である場合（試行割算に失敗した場合）にはステップＳＴ３２に戻る。
【０１５６】
一方、ステップＳＴ３５の終了時に、全ての試行割算の結果が剰余を持つ場合（試行割算に成功した場合）には、ＣＰＵ１５は演算部１７を制御することにより、第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する（ＳＴ３６）。具体的には、ＣＰＵ１５が確率的素数判定法又は確定的素数判定法のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【０１５７】
ステップＳＴ３６の判定の結果、不合格の場合（＝第２素数候補ｆ（ｐ）が素数でない場合）には、素数判定装置１０はステップＳＴ３２に戻る。
【０１５８】
一方、ステップＳＴ３６の判定結果から第２素数候補ｆ（ｐ）が素数である場合には、素数判定装置１０は、ＣＰＵ１５が演算部１７を制御することにより、第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する（ＳＴ３７）。ステップＳＴ３７の判定の結果、不合格の場合（＝第１素数候補ｐが素数でない場合）には、素数判定装置１０はステップＳＴ３２に戻る。
【０１５９】
一方、ステップＳＴ３７の素数判定の結果が合格のとき（第１素数候補ｐが素数である場合）には、素数生成装置１０は、第２素数候補ｆ（ｐ）と、第１素数候補ｐとをそれぞれ素数ｆ（ｐ），ｐとして入出力Ｉ／Ｆ１４から出力する。
【０１６０】
上述したように本実施形態によれば、第３の実施形態と同様に、「マウアー法」における「ポクリントンの定理」による素数判定を、確率的素数判定法又は確定的素数判定法の後に実行している。
【０１６１】
ここで、「ポクリントンの定理」による素数判定は、２に限らない底のベキ乗算を用いるため、２を底としたベキ乗算を用いる「確率的素数判定法又は確定的素数判定法」の演算時間よりも長い演算時間を必要とする。
【０１６２】
言い換えると、本実施形態においては、短い演算時間の「確率的素数判定法又は確定的素数判定法」により素数判定が不合格となる場合に、長い演算時間の「ポクリントンの定理」による素数判定を実行せずに済む構成のため、各素数候補の試行割算後の本格的素数判定に関し、ポクリントンの定理による素数判定（ステップＳＴ３７）の分だけ、高速化を図ることができる。
【０１６３】
（他の変形例）
（１）第１及び第３の実施形態は、「ミラー-ラビンテスト（ミラー-ラビン法）」や「マウアー法」に代えて、図６に示すように、数ステップからなる他の確率的素数判定法又は確定的素数判定法を分割した構成の素数生成を行なうように変形してもよい。同様に、第１及び第３の実施形態は、「拡張されたオイラー-ラグランジュの定理」に代えて、他の確率的素数判定法又は確定的素数判定法を用いるように変形してもよい。
【０１６４】
ここで、確率的素数判定法の例としては、フェルマー(Fermat)法、ソロベイ(Solovay)ーストラッセン(Strassen)法、ラビン法などが挙げられる。確定的素数判定法の例としては、ミラー法、アドルマン(Adleman)−ルメリ(Rumely)法、コーエン(Cohen)−レンストラ(Lenstra)法を用いる方法などが挙げられる。これらの例は、文献（池野信一、小山謙二共著、“現代暗号理論”、（社）電子情報通信学会、コロナ社、ｐ２４０−２４１、１９８６）に記載されている。また、ポクリントンの定理を用いる素数生成法である、シャウ(Shawe)−テイラー(Taylor)の方法は、非特許文献３に記載されている。
【０１６５】
また、変形例（１）においては、第１の実施形態を変形した場合、第１素数候補ｐに対し、「ミラー-ラビンテスト」とは異なる第１の確率的素数判定法又は確定的素数判定法を途中まで実行し、この第１の素数判定法による素数判定の結果が合格のとき、第２素数候補２ｐ＋１に対し、第２の確率的素数判定法又は確定的素数判定法を実行し、この第２の素数判定法による素数判定の結果が合格のとき、第１素数候補ｐに対し、第１の素数判定法による素数判定を再開し、この素数判定を最後まで実行して素数判定の結果が合格のとき、各素数候補ｐ，２ｐ＋１を素数として出力する。
【０１６６】
また、変形例（１）においては、第３の実施形態を変形した場合、第１素数候補ｐに対し、「マウアー法」とは異なる第１の確率的素数判定法又は確定的素数判定法を途中まで実行し、この第１の素数判定法による素数判定の結果が合格のとき、第２素数候補２ｐ＋１に対し、第２の確率的素数判定法又は確定的素数判定法を実行し、この第２の素数判定法による素数判定の結果が合格のとき、第１素数候補ｐに対し、第１の素数判定法による素数判定を再開し、この素数判定を最後まで実行して素数判定の結果が合格のとき、各素数候補ｐ，２ｐ＋１を素数として出力する。
【０１６７】
以上のように変形しても、適用した第１又は第３の実施形態と同様の作用効果を得ることができる。
【０１６８】
（２）第２及び第４の実施形態は、「ミラー-ラビンテスト（ミラー-ラビン法）」や「マウアー法」に代えて、図７に示すように、数ステップからなる他の確率的素数判定法又は確定的素数判定法を分割した構成の素数生成を行なうように変形してもよい。このように変形しても、適用した第２又は第４の実施形態と同様の作用効果を得ることができる。
【０１６９】
詳しくは、変形例（２）においては、第２の実施形態を変形した場合、第１素数候補ｐに対し、「ミラー-ラビンテスト」とは異なる第１の確率的素数判定法又は確定的素数判定法を途中まで実行し、この第１の素数判定法による素数判定の結果が合格のとき、第２素数候補ｆ（ｐ）に対し、第２の確率的素数判定法又は確定的素数判定法を実行し、この第２の素数判定法による素数判定の結果が合格のとき、第１素数候補ｐに対し、第１の素数判定法による素数判定を再開し、この素数判定を最後まで実行して素数判定の結果が合格のとき、各素数候補ｐ，ｆ（ｐ）を素数として出力する。
【０１７０】
また、変形例（２）においては、第４の実施形態を変形した場合、第１素数候補ｐに対し、「マウアー法」とは異なる第１の確率的素数判定法又は確定的素数判定法を途中まで実行し、この第１の素数判定法による素数判定の結果が合格のとき、第２素数候補ｆ（ｐ）に対し、第２の確率的素数判定法又は確定的素数判定法を実行し、この第２の素数判定法による素数判定の結果が合格のとき、第１素数候補ｐに対し、第１の素数判定法による素数判定を再開し、この素数判定を最後まで実行して素数判定の結果が合格のとき、各素数候補ｐ，ｆ（ｐ）を素数として出力する。
【０１７１】
（３）上記変形例（１）は、図８に示すように、第１素数候補ｐと、第２素数候補２ｐ＋１との素数判定の順番を逆にするように変形してもよい。このように変形しても、適用した変形例（１）と同様の作用効果を得ることができる。また、第２素数候補２ｐ＋１を最後まで素数判定し、その後、第１素数候補ｐを素数判定してもよい。
【０１７２】
（４）上記変形例（２）は、図９に示すように、第１素数候補ｐと、第２素数候補ｆ（ｐ）との素数判定の順番を逆にするように変形してもよい。このように変形しても、適用した変形例（２）と同様の作用効果を得ることができる。また、第２素数候補ｆ（ｐ）を最後まで素数判定し、その後、第１素数候補ｐを素数判定してもよい。
【０１７３】
変形例（２）、（４）については、次のように処理を効率化することができる。素数pをマウアー法で生成し、偶数kについて、f(p)=kp+1とし、f(p)をポクリントンの定理で判定する際に、kがp及びf(p)へ行う試行割算の最大数のビット数以下程度にとる。このとき、次のステップ(a)-(e)により、確定的にp及びf(p)を素数判定することが出来る。
【０１７４】
(a)素数p=2rF+1となるFをマウアー法で生成する。
【０１７５】
(b)乱数rを生成する。
【０１７６】
(c)pとf(p)へ試行割算を行う。
【０１７７】
(d)f(p)が素数であるかポクリントンの定理で判定するため、下記を検証。
2^{f(p)-1} ≡ 1 (mod f(p))
(e)pを通常のマウアー法で、素数判定する。
【０１７８】
ここで、(d)において、通常のポクリントンの定理に従うならば、
G.C.D.( 2^{(f(p)-1)/F}−1, f(p)) = 1
についても検証しなくてはならないが、これについては(c)の試行割算を通過した時点で、検証を行っているため、この処理を省くことが出来る。
【０１７９】
（５）上記変形例（１）から（４）において、いずれかの素数をポクリントンの定理を用いて素数判定する際に、第１の判定条件を次のように変形してもよい。すなわち、整数nを素数判定する際に、ある整数aが存在して、
a^{n-1} ≡ 1 (mod n)
が成立することを確かめるフェルマー(Fermat)法の代わりに、整数nに対して底aに関するミラー-ラビンテストが成り立つことを確かめる。このように変形しても、検証の誤判定率を低減させることなく、変形例（１）から（４）と同様の作用効果を得ることができる。更には一般にミラー-ラビンテストに要する時間は、フェルマー(Fermat)法に要する時間より短いため、判定時間を低減させることが可能となる。
【０１８０】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０１８１】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１８２】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１８３】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１８４】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１８５】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１８６】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１８７】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１８８】
【図１】本発明の第１の実施形態に係る素数生成装置の構成を示す模式図である。
【図２】同実施形態における素数生成方法を説明するためのフローチャートである。
【図３】本発明の第２の実施形態における素数生成方法を説明するためのフローチャートである。
【図４】本発明の第３の実施形態における素数生成方法を説明するためのフローチャートである。
【図５】本発明の第４の実施形態における素数生成方法を説明するためのフローチャートである。
【図６】本発明の変形例を説明するためのフローチャートである。
【図７】本発明の変形例を説明するためのフローチャートである。
【図８】本発明の変形例を説明するためのフローチャートである。
【図９】本発明の変形例を説明するためのフローチャートである。
【符号の説明】
【０１８９】
１０…素数生成装置、１１…プログラム記憶部、１２…テーブル記憶部、１３…不揮発性メモリ、１４…入出力Ｉ／Ｆ、１５…ＣＰＵ、１６…乱数生成部、１７…演算部、Ｔ…除算テーブル。
【特許請求の範囲】
【請求項１】
Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
Ｌ−１ビットの第１素数候補ｐとして乱数を生成する乱数生成手段、
前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第１素数候補ｐに対し、２である底を用いたミラー-ラビンテストを実行する第１のミラー-ラビンテスト実行手段、
前記第１のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュの定理」に基づいて素数判定を実行する素数判定手段、
前記素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行手段、
前記第２のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項２】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
前記第１素数候補ｐとして乱数を生成する乱数生成手段、
前記第１素数候補ｐに基づいて、前記第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第１素数候補ｐに対し、２である底を用いたミラー-ラビンテストを実行する第１のミラー-ラビンテスト実行手段、
前記第１のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法を実行する素数判定手段、
前記素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行手段、
前記第２のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補ｆ（ｐ）を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項３】
Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成手段、
ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、前記Ｌ／２ビット程度の素数Ｆに応じてＬ−１ビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成手段、
前記乱数ｒ、前記素数Ｆ及び前記式ｐ＝２ｒＦ＋１に基づいて、Ｌ−１ビットの第１素数候補ｐを算出する第１素数候補算出手段、
前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュの定理」に基づいて素数判定を実行する第１の素数判定手段、
前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定手段、
前記第２の素数判定手段による判定結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項４】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成手段、
ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、前記Ｌ／２ビット程度の素数Ｆに応じてＬビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成手段、
前記乱数ｒ、前記素数Ｆ及び前記式ｐ＝２ｒＦ＋１に基づいて、Ｌビットの第１素数候補ｐを算出する第１素数候補算出手段、
前記第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する第１の素数判定手段、
前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定手段、
前記第２の素数判定手段による判定結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項５】
Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
Ｌ−１ビットの第１素数候補ｐとして乱数を生成する乱数生成手段、
前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補２ｐ＋１に対し、「ミラー-ラビンテスト」とは異なる確率的素数判定法又は確定的素数判定法を途中まで実行する第１の素数判定手段、
前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、「拡張されたオイラー-ラグランジュの定理」を用いない確率的素数判定法又は確定的素数判定法に基づいて第２の素数判定を実行する第２の素数判定手段、
前記第２の素数判定手段による素数判定の結果が合格のとき、前記第２素数候補２ｐ＋１に対し、前記第１の素数判定手段による素数判定を再開し、この素数判定を最後まで実行する第３の素数判定手段、
前記第３の素数判定手段による素数判定の結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項６】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
前記第１素数候補ｐとして乱数を生成する乱数生成手段、
前記第１素数候補ｐに基づいて、前記第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補ｆ（ｐ）に対し、「ミラー-ラビンテスト」とは異なる確率的素数判定法又は確定的素数判定法を途中まで実行する第１の素数判定手段、
前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、確率的素数判定法又は確定的素数判定法を実行する第２の素数判定手段、
前記第２の素数判定手段による素数判定の結果が合格のとき、前記第２素数候補ｆ（ｐ）に対し、前記第１の素数判定手段による素数判定を再開し、この素数判定を最後まで実行する第３の素数判定手段、
前記第３の素数判定手段による素数判定の結果が合格のとき、前記第２素数候補ｆ（ｐ）を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項１】
Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
Ｌ−１ビットの第１素数候補ｐとして乱数を生成する乱数生成手段、
前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第１素数候補ｐに対し、２である底を用いたミラー-ラビンテストを実行する第１のミラー-ラビンテスト実行手段、
前記第１のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュの定理」に基づいて素数判定を実行する素数判定手段、
前記素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行手段、
前記第２のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項２】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
前記第１素数候補ｐとして乱数を生成する乱数生成手段、
前記第１素数候補ｐに基づいて、前記第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第１素数候補ｐに対し、２である底を用いたミラー-ラビンテストを実行する第１のミラー-ラビンテスト実行手段、
前記第１のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法を実行する素数判定手段、
前記素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、２でない底を用いたミラー-ラビンテストを実行する第２のミラー-ラビンテスト実行手段、
前記第２のミラー-ラビンテスト実行手段によるテストの結果が合格のとき、前記第２素数候補ｆ（ｐ）を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項３】
Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成手段、
ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、前記Ｌ／２ビット程度の素数Ｆに応じてＬ−１ビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成手段、
前記乱数ｒ、前記素数Ｆ及び前記式ｐ＝２ｒＦ＋１に基づいて、Ｌ−１ビットの第１素数候補ｐを算出する第１素数候補算出手段、
前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補２ｐ＋１に対し、「拡張されたオイラー-ラグランジュの定理」に基づいて素数判定を実行する第１の素数判定手段、
前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定手段、
前記第２の素数判定手段による判定結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項４】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
「マウアー法」に基づいて、Ｌ／２ビット程度の素数Ｆを生成する素数生成手段、
ポクリントンの定理に基づく式ｐ＝２ｒＦ＋１に基づいて、前記Ｌ／２ビット程度の素数Ｆに応じてＬビットの第１素数候補ｐを得られるように、乱数ｒを生成する乱数生成手段、
前記乱数ｒ、前記素数Ｆ及び前記式ｐ＝２ｒＦ＋１に基づいて、Ｌビットの第１素数候補ｐを算出する第１素数候補算出手段、
前記第１素数候補ｐに基づいて、第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補ｆ（ｐ）に対し、確率的素数判定法又は確定的素数判定法に基づいて素数判定を実行する第１の素数判定手段、
前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、ポクリントンの定理に基づいて素数判定を実行する第２の素数判定手段、
前記第２の素数判定手段による判定結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項５】
Ｌビットの素数２ｐ＋１を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
Ｌ−１ビットの第１素数候補ｐとして乱数を生成する乱数生成手段、
前記第１素数候補ｐに基づいて、Ｌビットの第２素数候補２ｐ＋１を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，２ｐ＋１の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補２ｐ＋１に対し、「ミラー-ラビンテスト」とは異なる確率的素数判定法又は確定的素数判定法を途中まで実行する第１の素数判定手段、
前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、「拡張されたオイラー-ラグランジュの定理」を用いない確率的素数判定法又は確定的素数判定法に基づいて第２の素数判定を実行する第２の素数判定手段、
前記第２の素数判定手段による素数判定の結果が合格のとき、前記第２素数候補２ｐ＋１に対し、前記第１の素数判定手段による素数判定を再開し、この素数判定を最後まで実行する第３の素数判定手段、
前記第３の素数判定手段による素数判定の結果が合格のとき、前記第２素数候補２ｐ＋１を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【請求項６】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）から算出可能な第２素数ｆ（ｐ）（∈Ｚ）を生成する素数生成装置に用いられる素数生成プログラムであって、
前記素数生成装置のコンピュータを、
予め複数個の除数が記憶された除数記憶手段、
前記第１素数候補ｐとして乱数を生成する乱数生成手段、
前記第１素数候補ｐに基づいて、前記第２素数候補ｆ（ｐ）を算出する第２素数候補算出手段、
前記除数記憶手段内の除数毎に、前記各素数候補ｐ，ｆ（ｐ）の試行割算を個別に実行する試行割算実行手段、
前記試行割算実行手段による全ての試行割算の結果が剰余を持つとき、前記第２素数候補ｆ（ｐ）に対し、「ミラー-ラビンテスト」とは異なる確率的素数判定法又は確定的素数判定法を途中まで実行する第１の素数判定手段、
前記第１の素数判定手段による素数判定の結果が合格のとき、前記第１素数候補ｐに対し、確率的素数判定法又は確定的素数判定法を実行する第２の素数判定手段、
前記第２の素数判定手段による素数判定の結果が合格のとき、前記第２素数候補ｆ（ｐ）に対し、前記第１の素数判定手段による素数判定を再開し、この素数判定を最後まで実行する第３の素数判定手段、
前記第３の素数判定手段による素数判定の結果が合格のとき、前記第２素数候補ｆ（ｐ）を素数として出力する素数出力手段、
として機能させるための素数生成プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００７−３３４０３８（Ｐ２００７−３３４０３８Ａ）
【公開日】平成１９年１２月２７日（２００７．１２．２７）
【国際特許分類】
【出願番号】特願２００６−１６６２４０（Ｐ２００６−１６６２４０）
【出願日】平成１８年６月１５日（２００６．６．１５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成１９年１２月２７日（２００７．１２．２７）
【国際特許分類】
【出願日】平成１８年６月１５日（２００６．６．１５）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]