素数生成装置、プログラム及び方法
【課題】セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を高速に生成する。
【解決手段】第１素数ｐと、この第１素数ｐから算出可能で定数項（ａ0）が０ではない多項式ｆ（ｐ）（＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0）の形をもつ第２素数ｆ（ｐ）とを生成する構成により、セーフプライム形の素数（２ｐ＋１）に限定されず、第１素数ｐの多項式の形をもつ第２素数ｆ（ｐ）を生成できる。これに加え、高速に計算可能な試行割算を先に行った後に、フェルマーの小定理を含む本格的な素数判定法を行う構成により、時間のかかる本格的な素数判定法の実行割合を減少できるので、前述した第１及び第２素数ｐ，ｆ（ｐ）を高速に生成できる。
【解決手段】第１素数ｐと、この第１素数ｐから算出可能で定数項（ａ0）が０ではない多項式ｆ（ｐ）（＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0）の形をもつ第２素数ｆ（ｐ）とを生成する構成により、セーフプライム形の素数（２ｐ＋１）に限定されず、第１素数ｐの多項式の形をもつ第２素数ｆ（ｐ）を生成できる。これに加え、高速に計算可能な試行割算を先に行った後に、フェルマーの小定理を含む本格的な素数判定法を行う構成により、時間のかかる本格的な素数判定法の実行割合を減少できるので、前述した第１及び第２素数ｐ，ｆ（ｐ）を高速に生成できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、素数を生成するための素数生成装置、プログラム及び方法に係り、例えば、セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を高速に生成し得る素数生成装置、プログラム及び方法に関する。
【背景技術】
【０００２】
暗号分野においては、ｐを素数としたとき、２ｐ＋１という形の素数が、暗号の安全性を高めるために用いられている。この形の素数はセーフプライム（safe prime）と呼ばれる。セーフプライムは、ディフィー−へルマン（Diffie-Hellman）鍵交換を始めとして、多くの暗号通信プロトコルで用いられている。
【０００３】
このセーフプライムを生成するための効率的な方法は、今のところ知られていない。一般的な素数生成方法においては、素数候補の乱数ｐを素数判定し、素数であれば、さらにセーフプライム候補の数２ｐ＋１を素数判定することにより、セーフプライム形の素数２ｐ＋１を生成している。
【０００４】
図８は一般的な素数生成方法を説明するためのフローチャートである。この素数生成方法は、素数候補ｐの簡易素数判定（ＳＴ１〜ＳＴ４）、素数候補ｐの本格的素数判定（ＳＴ５）、セーフプライム候補２ｐ＋１の簡易素数判定（ＳＴ６〜ＳＴ９）、セーフプライム候補２ｐ＋１の本格的素数判定（ＳＴ１０）から構成されている。具体的には、この素数判定方法は、例えばコンピュータからなる素数生成装置に実行される。
【０００５】
始めに、素数生成装置は、除数識別情報ｉをｉ＝０として初期化する（ＳＴ１）。続いて、素数生成装置は、素数候補としての乱数ｐを生成する（ＳＴ２）。なお、ステップＳＴ１，ＳＴ２の順序は逆でもよい。
【０００６】
次に、素数生成装置は、素数候補ｐに対し、予め保持しておいた除数テーブルを用い、除数識別情報ｉ＝１から順次、試行割算を行う（ＳＴ３）。
【０００７】
ここで、除数識別情報ｉは、除数テーブルから除数primes[i]を読み出すために用いられる。なお、除数テーブルは、除数識別情報ｉ及び除数primes[i]が互いに関連付けて記述されている。除数識別情報ｉは、１，２，…，PRIMES_NUM−１，PRIMES_NUM、のように、自然数としている。
【０００８】
素数生成装置は、素数候補ｐを除数primes[i]で割り算した剰余が０のとき（p÷primes[i]=0）、又は除数識別情報ｉが最大値PRIMES_NUMの場合の割り算を終えたとき（i＝PRIMES_NUM）、ステップＳＴ３の試行割算を終了する。
【０００９】
素数生成装置は、ステップＳＴ３の試行割算を終了したときの除数識別情報ｉが最大値PRIMES_NUMであるか否かを判定し（ＳＴ４）、否の場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００１０】
一方、ステップＳＴ４の判定の結果、除数識別情報ｉが最大値PRIMES_NUMの場合（試行割算に成功した場合）、素数生成装置は、素数候補ｐに対し、フェルマー(Fermat)法、ミラー−ラビン(Miller-Rabin)法などの、本格的な素数判定を行う（ＳＴ５）。
【００１１】
ステップＳＴ５の素数判定の結果、素数候補ｐが素数ではない場合（ＮＧの場合）には、ステップＳＴ１に戻る。
【００１２】
ステップＳＴ５の素数判定の結果、素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置は、除数識別情報ｉをｉ＝０として初期化する（ＳＴ６）。続いて、素数生成装置は、セーフプライム候補としての数２ｐ＋１を計算する（ＳＴ７）。なお、ステップＳＴ６，ＳＴ７の順序は逆でもよい。
【００１３】
次に、素数生成装置は、セーフプライム候補２ｐ＋１に対し、前述同様に、除数テーブルを用いて試行割算を行う（ＳＴ８）。素数生成装置は、セーフプライム候補２ｐ＋１を除数primes[i]で割り算した剰余が０のとき（(2p+1)÷primes[i]=0）、又は除数識別情報ｉが最大値PRIMES_NUMの場合の割り算を終えたとき（i＝PRIMES_NUM）、ステップＳＴ８の試行割算を終了する。
【００１４】
素数生成装置は、ステップＳＴ８の試行割算を終了したときの除数識別情報ｉが最大値PRIMES_NUMであるか否かを判定し（ＳＴ９）、否の場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００１５】
一方、ステップＳＴ９の判定の結果、除数識別情報ｉが最大値PRIMES_NUMの場合（試行割算に成功した場合）、素数生成装置は、セーフプライム候補２ｐ＋１に対し、フェルマー(Fermat)法、ミラー−ラビン(Miller-Rabin)法などの、本格的な素数判定を行う（ＳＴ１０）。
【００１６】
ステップＳＴ１０の素数判定の結果、セーフプライム候補２ｐ＋１が素数ではない場合（ＮＧの場合）には、ステップＳＴ１へ戻る。
【００１７】
ステップＳＴ１０の素数判定の結果、セーフプライム候補２ｐ＋１が素数である場合（ＯＫの場合）には、素数生成装置は、セーフプライム形の素数２ｐ＋１と、素数ｐとを出力する。
【００１８】
なお、以上のような一般的な素数生成方法に限らず、セーフプライムを生成する方法には種々の方式がある（例えば非特許文献１，２参照）。ここで、非特許文献１には、セーフプライムｑを生成するために、（ｑ−１）／２を乱数として生成し、この乱数を素数判定し、素数判定に合格したら、ｑを素数判定する方式が開示されている。
【００１９】
非特許文献２には、セーフプライムｑを生成するために、（ｑ−１）／２を乱数として生成し、ある定数以下の小さな奇素数ｒに対して、（ｑ−１）／２≡（ｒ−１）／２ (mod r)なる乱数（ｑ−１）／２を除去し、残った乱数（ｑ−１）／２を素数判定し、素数判定に合格したら、ｑを素数判定する方式が開示されている。
【非特許文献１】“Handbook of applied cryptography p.164” http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf
【非特許文献２】“Safe Prime Generation with a Combined Sieve” http://eprint.iacr.org/2003/186.pdf
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、以上のような素数生成方法では、次のような問題がある。
例えば、図８に示した方法では、乱数ｐの値が大きくなるにつれ、セーフプライム形の素数２ｐ＋１を生成するための時間が、非常に増大するという問題がある。このため、素数生成装置を備えた情報機器や、このような情報機器を複数台備えた情報システム（以下、情報機器等という）においては、素数生成装置の計算負荷を増大させ、システム稼働率を低下させる問題がある。
【００２１】
このような問題を解決する観点から、情報機器等では、セーフプライムを予め生成して保持する方式や、セーフプライムではない、一般的な素数を用いた暗号通信を行う方式が知られている。しかしながら、これらの方式は、情報機器等のセキュリティレベルを低下させる場合があるので、上記問題を実際に解決したとは言えない。なお、非特許文献１に記載の方法は、前述した図８に示した方法と同様の問題があると考えられる。
【００２２】
一方、非特許文献２に記載の方法は、予め奇素数ｒを法として、（ｒ−１）／２に合同な乱数をセーフプライム候補から除去した後に、残ったセーフプライム候補を素数判定するので、素数生成装置の計算負荷を減少できる。
【００２３】
補足すると、素数生成装置の計算負荷は、試行割算よりも本格的素数判定の方がはるかに大きい。そこで、非特許文献２に記載の方法は、本格的素数判定の前に簡単な合成数を除去するので、素数生成装置の計算負荷を減少できる。この非特許文献２に記載の方法によれば、上記問題を解決することができる。
【００２４】
但し、非特許文献２に記載の方法は、特に問題は無いものの、本発明者の検討によれば、セーフプライム形の素数２ｐ＋１に限定されている不都合があると考えられる。
【００２５】
本発明は上記実情を考慮してなされたもので、セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を高速に生成し得る素数生成装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００２６】
第１の発明は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置であって、予め除数識別情報毎に除数が記憶された除数記憶手段と、前記第１素数の候補ｐとして乱数を生成する乱数生成手段と、前記第１素数の候補ｐに基づいて、前記第２素数の候補ｆ（ｐ）を算出する第２素数候補算出手段と、前記各素数の候補ｐ，ｆ（ｐ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行手段と、前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段とを備えた素数生成装置である。
【００２７】
第２の発明は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置であって、予め除数識別情報毎に除数が記憶されており、試行割算結果の剰余が前記除数識別情報に関連付けて記憶される除数記憶手段と、前記第１素数の候補ｐとして乱数を生成する乱数生成手段と、前記第１素数の候補ｐに対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行手段と、前記第１割算実行手段による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを前記除数記憶手段に書き込む剰余書込手段と、前記剰余書込手段により書き込まれた剰余ｋに基づいて、前記多項式ｆ（ｋ）を計算する多項式計算手段と、前記多項式ｆ（ｋ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第２割算実行手段と、前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記第１素数の候補ｐ及び前記第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段とを備えた素数生成装置である。
【００２８】
（作用）
第１の発明によれば、第１素数ｐと、この第１素数ｐから算出可能で定数項が０ではない多項式の形をもつ第２素数ｆ（ｐ）とを生成する構成により、セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を生成することができる。
【００２９】
これに加え、第１の発明によれば、高速に計算可能な試行割算を先に行った後に、本格的な素数判定法（フェルマーの小定理を含む素数判定法）を行う構成により、時間のかかる本格的な素数判定法の実行割合を減少できるので、前述した第１及び第２素数ｐ，ｆ（ｐ）を高速に生成することができる。
【００３０】
第２の発明によれば、第１の発明の作用効果に加え、第２素数の候補ｆ（ｐ）に関する試行割算を、剰余ｋの多項式ｆ（ｋ）に関する試行割算により行う構成により、従来とは異なり、試行割算をワードサイズで実行できるので、第１及び第２素数ｐ，ｆ（ｐ）をより一層高速に生成することができる。
【００３１】
なお、第１及び第２の各発明は「装置」として表現したが、これに限らず、「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」として表現してもよい。
【発明の効果】
【００３２】
以上説明したように本発明によれば、セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を高速に生成できる。
【発明を実施するための最良の形態】
【００３３】
以下、本発明の各実施形態を図面を用いて説明する。なお、以下の説明中、乱数、素数、素数候補、定数項、整数係数、多項式、除数、剰余などの語を用いるが、これらは、乱数データ、素数データ、素数候補データ、定数項データ、整数係数データ、多項式データ、除数データ、剰余データ等のように、「データ」の語を追記して読み替えてもよい。
【００３４】
（第１の実施形態）
図１は本発明の第１の実施形態に係る素数生成装置の構成を示す模式図である。この素数生成装置１０は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、Ｚは整数Ｘを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成するものである。ここで、第２素数ｆ（ｐ）は、例えば多項式の次数をｎとし、次数毎の整数係数をａn，ａn-1，…，ａ2，ａ1とし、定数項をａ0としたとき、次式に示すように計算される。
【００３５】
ｆ（ｐ）＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0
このような第２素数ｆ（ｐ）は、次数ｎ＝１、整数係数ａ1＝２、定数項ａ0＝１の場合、セーフプライム２ｐ＋１となる。但し、第２素数ｆ（ｐ）は、セーフプライム２ｐ＋１に限定されない。
【００３６】
この素数生成装置１０は、具体的には携帯電話又はスマートカードなどの演算機の素数生成部として構成され、ハードウェア及びソフトウェアの組合せにより素数生成処理を行うものである。
【００３７】
例えば素数生成装置１０においては、プログラム記憶部１１、テーブル記憶部１２、ＲＡＭ１３、入出力Ｉ／Ｆ１４、ＣＰＵ（中央処理装置）１５、乱数生成部１６及び演算部１７が互いにバスを介して接続されている。
【００３８】
プログラム記憶部１１は、ＣＰＵ１５に実行されるプログラムが記憶されるハードウェア資源としてのメモリであり、例えばＲＯＭ（リードオンリーメモリ）が使用可能となっている。ここで、プログラムは、例えば図３又は図４に示す素数生成機能を実現させるためのものである。この素数生成機能としては、例えば以下の機能(f11-1)〜(f11-5)を含んでいる。
【００３９】
(f11-1) 除数識別情報毎に除数が記憶された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11-2) 乱数生成部１６の制御により、第１素数の候補ｐとして乱数を生成する機能。
(f11-3) 演算部１７の制御により、第１素数の候補ｐに基づいて、第２素数の候補ｆ（ｐ）を算出する第２素数候補算出機能。
(f11-4) 演算部１７の制御により、各素数の候補ｐ，ｆ（ｐ）に対し、除数テーブルＴ内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行機能。
(f11-5) 演算部１７の制御により、除数テーブルＴ内の全ての除数による全ての試行割算の結果が剰余を持つとき、各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定機能。
【００４０】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよい。
【００４１】
テーブル記憶部１２は、ＣＰＵ１５から読出／書込可能なハードウェア資源としてのＲＡＭ（ランダムアクセスメモリ）である。テーブル記憶部１２は、予め除数テーブルＴが記憶されており、さらにＣＰＵ１５により、演算に必要なデータや演算途中のデータ等が記憶される。除数テーブルＴは、図２に示すように、予め除数識別情報ｉ毎に除数primes[i]が記述されたものである。
【００４２】
除数識別情報ｉは、前述同様に、１，２，…，PRIMES_NUM−１，PRIMES_NUM、のように、自然数としている。なお、ここでは、除数識別情報ｉの最大値PRIMES_NUMを６５４２としている。
【００４３】
除数primes[i]は、小さい順に数えてｉ番目の素数である。このような除数の数列に関する説明は、文献（D. E. Knuth 著（中川圭介訳），“KNUTH 第４分冊 準数値算法／算術演算”，サイエンス社，p.205, 1986.）に記載されている。なお、ここでは、除数テーブルＴにおける除数の最大値を“６５５２１”としている。また、除数テーブルＴは、予めプログラム記憶部１１内のプログラムに含まれていてもよい。
【００４４】
不揮発性メモリ１３は、例えば生成された素数ｐ，ｆ（ｐ）などがＣＰＵ１５から読出／書込可能に記憶されるハードウェア資源としてのメモリであり、例えば、ＥＥＰＲＯＭ（Electric Erasable Programmable ＲＯＭ）が使用可能となっている。但し、不揮発性メモリ１３は、必須ではなく省略してもよい。
【００４５】
入出力Ｉ／Ｆ１４は、素数生成装置１０と、この素数生成装置１０を保持する情報機器との間のインターフェイス機器であり、例えば、素数生成指令を入力し、得られた素数ｐ，ｆ（ｐ）を出力する際に用いられる。
【００４６】
ここでいう情報機器としては、何らかの暗号処理を実行するものであれば任意のデバイスが適用可能である。何らかの暗号処理とは、例えば公開鍵暗号方式における暗号処理、復号処理、署名生成処理又は署名検証処理などである。情報機器の例としては、スマートカード又は携帯電話等の如き、ユーザ毎に携帯可能なデバイスが挙げられる。情報機器の用途は任意であり、例えば、非匿名又は匿名のユーザ認証などが挙げられる。
【００４７】
ＣＰＵ１５は、プログラム記憶部１１内のプログラムを実行することにより、例えば図３に示す手順で各部１２〜１７を制御し、素数生成処理を実行する機能を有するものである。
【００４８】
乱数生成部１６は、ＣＰＵ１５により制御されて乱数ｐを生成し、この乱数ｐをバスに送出するハードウェア資源としての乱数生成回路である。ここで、乱数生成部１６により生成される乱数ｐは、真の乱数又は疑似乱数のいずれでもよい。
【００４９】
なお、乱数生成部１６は、独立のハードウェア資源で実現する場合に限らず、ＣＰＵ１５とプログラムで実現してもよい。また、乱数生成部１６を省略し、乱数ｐを外部から入力させる構成としてもよい。
【００５０】
演算部１７は、ＣＰＵ１５により制御され、例えばＣＰＵ１５から入力されたデータに基づいて演算を実行し、演算結果をバスに出力するハードウェア資源としての演算回路である。なお、演算部１７は、処理速度を向上させる観点から独立のハードウェア回路として設けられており、例えばコプロセッサ等の如き、多倍長の演算が可能なものであるが、ハードウェア回路に限らず、ＣＰＵ１５とプログラムで実現してもよい。
【００５１】
なお、このような素数生成装置１０は、ハードウェア及びソフトウェアの組合せに限らず、ハードウェア又はソフトウェアのいずれか一方により構成されてもよい。
【００５２】
次に、以上のように構成された素数生成装置による素数生成方法を図３及び図４のフローチャートを用いて述べる。始めに、図３により従来との大きな違いを簡単に述べ、しかる後、図４により素数生成方法を説明する。なお、図４による説明は、多項式ｆ（ｐ）を２ｐ＋１の形に規定すると、図３による説明に読み替えることができる。
【００５３】
従来との違いは、図３に示すように、第１素数候補ｐの本格的素数判定ステップＳＴ５を、第１及び第２素数候補ｐ，ｆ（ｐ）の簡易素数判定ステップ（ＳＴ１〜ＳＴ４及びＳＴ６〜ＳＴ９）の後に実行することである。これに加え、図４に示すように、従来の第２素数２ｐ＋１に代えて第２素数ｆ（ｐ）を生成するため、第２素数ｆ（ｐ）に関連するステップＳＴ７’，ＳＴ８’，ＳＴ１０’にはダッシュ記号’を付している。以下、図４を参照しながら順次説明する。
【００５４】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数ｆ（ｐ）を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【００５５】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が除数識別情報ｉをｉ＝０として初期化する（ＳＴ１）。
【００５６】
続いて、素数生成装置１０においては、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、第１素数候補としての乱数ｐを生成する（ＳＴ２）。なお、ステップＳＴ１，ＳＴ２の順序は逆でもよい。
【００５７】
次に、素数生成装置１０においては、第１素数候補ｐに対し、予め保持しておいた除数テーブルＴを用い、除数識別情報ｉ＝１から順次、試行割算を行う（ＳＴ３）。
【００５８】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数識別情報ｉ毎の除数primes[i]とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数primes[i]で割り算し、得られた剰余をバスに出力する。
【００５９】
ＣＰＵ１５は、第１素数候補ｐを除数primes[i]で割り算した剰余が０のとき（p÷primes[i]=0）、又は除数識別情報ｉが最大値PRIMES_NUMの場合の割り算を終えたとき（i＝PRIMES_NUM）、ステップＳＴ３の試行割算を終了する。
【００６０】
ＣＰＵ１５は、ステップＳＴ３の試行割算を終了したときの除数識別情報ｉが最大値PRIMES_NUMであるか否かを判定し（ＳＴ４）、否の場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００６１】
一方、ステップＳＴ４の判定の結果、除数識別情報ｉが最大値PRIMES_NUMの場合（試行割算に成功した場合）には、ＣＰＵ１５は、除数識別情報ｉをｉ＝０として初期化する（ＳＴ６）。
【００６２】
続いて、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御し、演算部１７が第２素数候補としての多項式ｆ（ｐ）を計算する（ＳＴ７’）。具体的には、ＣＰＵ１５は、第１素数候補ｐと、所定の多項式ｆ（Ｘ）の形とに基づいて、次数n，n-1，…，2，1及び次数毎の整数係数ａn，ａn-1，…，ａ2，ａ1を順次、バスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐと、多項式ｆ（Ｘ）の次数及び次数毎の整数係数とに基づいて、第１素数候補ｐに対する次数のベキ乗を計算し、得られたベキ乗結果と整数係数とを乗算し、得られた多項式の変数項をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。また、ＣＰＵ１５は、ｎ次から１次までの変数項ａn・ｐn，ａn-1・ｐn-1，…，ａ2・ｐ2，ａ1・ｐと、定数項ａ0とをバスを介して演算部１７に入力する。演算部１７は、これら変数項と、定数項とを加算し、得られた多項式ｆ（ｐ）をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。なお、ステップＳＴ６，ＳＴ７’の順序は逆でもよい。
【００６３】
次に、素数生成装置１０においては、この多項式ｆ（ｐ）からなる第２素数候補ｆ（ｐ）に対し、前述同様に、除数テーブルＴを用いて試行割算を行う（ＳＴ８’）。
【００６４】
素数生成装置１０のＣＰＵ１５は、第２素数候補ｆ（ｐ）を除数primes[i]で割り算した剰余が０のとき（f(p)÷primes[i]＝0）、又は除数識別情報ｉが最大値PRIMES_NUMの場合の割り算を終えたとき（i＝PRIMES_NUM）、ステップＳＴ８’の試行割算を終了する。
【００６５】
ＣＰＵ１５は、ステップＳＴ８’の試行割算を終了したときの除数識別情報ｉが最大値PRIMES_NUMであるか否かを判定し（ＳＴ９）、否の場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００６６】
一方、ステップＳＴ９の判定の結果、除数識別情報ｉが最大値PRIMES_NUMの場合（試行割算に成功した場合）、ＣＰＵ１５は、ｐ，ｆ（ｐ）の簡易素数判定（ＳＴ１〜ＳＴ４，ＳＴ６〜ＳＴ９）を終了する。換言すると、ＣＰＵ１５は、除数テーブルＴ内の全ての除数による全ての試行割算の結果が剰余を持つとき、ｐ，ｆ（ｐ）の簡易素数判定（ＳＴ１〜ＳＴ４，ＳＴ６〜ＳＴ９）を終了する。
【００６７】
次に、素数生成装置１０は、第１素数候補ｐに対し、フェルマー法などのように、フェルマーの小定理を含む本格的な素数判定法を実行する（ＳＴ５）。具体的には、ＣＰＵ１５が所定の素数判定法のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【００６８】
ここで、所定の素数判定法としては、高速な判定の観点から、フェルマー(Fermat)の小定理を利用した素数判定法を改良して、あるところまで調べれば、素数候補が素数であることを確率的又は確定的に判定できるようにしたものを用いている。このような素数判定法のうち、確率的な素数判定法の例としては、フェルマー法、ソロベイ(Solovay)ーストラッセン(Strassen)法、ラビン法などが挙げられる。確定的な素数判定法の例としては、ミラー法、アドルマン(Adleman)−ルメリ(Rumely)法、コーエン(Cohen)−レンストラ(Lenstra)法などが挙げられる。ここで述べた素数判定法に関する説明は、文献（池野信一、小山謙二共著、“現代暗号理論”、（社）電子情報通信学会、コロナ社、ｐ２４０−２４１、１９８６）に記載されている。
【００６９】
さてステップＳＴ５の素数判定の結果、第１素数候補ｐが素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１に戻る。
【００７０】
ステップＳＴ５の素数判定の結果、第１素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置１０は、第２素数候補ｆ（ｐ）に対し、前述同様に、フェルマー法又はミラー−ラビン法などの、本格的な素数判定を行う（ＳＴ１０’）。
【００７１】
ステップＳＴ１０’の素数判定の結果、第２素数候補ｆ（ｐ）が素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１へ戻る。
【００７２】
ステップＳＴ１０’の素数判定の結果、第２素数候補ｆ（ｐ）が素数である場合（ＯＫの場合）には、素数生成装置１０は、第２素数ｆ（ｐ）と、第１素数ｐとを入出力Ｉ／Ｆ１４から出力する。
【００７３】
上述したように本実施形態によれば、第１素数ｐと、この第１素数ｐから算出可能で定数項（ａ0）が０ではない多項式ｆ（ｐ）（＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0）の形をもつ第２素数ｆ（ｐ）とを生成する構成により、セーフプライム形の素数（２ｐ＋１）に限定されず、第１素数ｐの多項式の形をもつ第２素数ｆ（ｐ）を生成することができる。
【００７４】
これに加え、本実施形態によれば、高速に計算可能な試行割算を先に行った後に、本格的な素数判定法（フェルマーの小定理を含む素数判定法）を行う構成により、時間のかかる本格的な素数判定法の実行割合を減少できるので、前述した第１及び第２素数ｐ，ｆ（ｐ）を高速に生成することができる。
【００７５】
（第２の実施形態）
次に、本発明の第２の実施形態について前述した図１を参照しながら説明する。すなわち、本実施形態は、第１の実施形態の変形例であり、試行割算のサイズを低減して素数生成の高速化を図る観点から、第２素数の候補ｆ（ｐ）に関する試行割算を、剰余ｋの多項式ｆ（ｋ）に関する試行割算により行うものである。
【００７６】
これに伴い、除数テーブルＴは、図５に示すように、予め除数識別情報ｉ毎に除数primes[i]が記憶されており、試行割算結果の剰余ｋ[i]が除数識別情報ｉに関連付けて記憶されるものとなっている。
【００７７】
また、プログラム記憶部１１内のプログラムとしては、以下の機能(f11-1’)〜(f11-5)を含むものとなっている。
(f11-1’) 予め除数識別情報毎に除数が記憶されており、試行割算結果の剰余が除数識別情報に関連付けて記憶される除数テーブルＴをテーブル記憶部１２に書込む機能。
(f11-2) 乱数生成部１６の制御により、第１素数の候補ｐとして乱数を生成する機能。
(f11-6) 演算部１７の制御により、第１素数の候補ｐに対し、除数テーブルＴ内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行機能。
(f11-7) 演算部１７の制御により、第１割算実行機能による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを除数テーブルＴに書き込む剰余書込機能。
(f11-8) 演算部１７の制御により、剰余書込機能により書き込まれた剰余ｋに基づいて、多項式ｆ（ｋ）を計算する多項式計算機能。
(f11-9) 演算部１７の制御により、多項式ｆ（ｋ）に対し、除数テーブルＴ内の除数識別情報毎の除数により個別に試行割算を実行する第２割算実行機能。
(f11-5) 演算部１７の制御により、除数テーブルＴ内の全ての除数による全ての試行割算の結果が剰余を持つとき、第１素数の候補ｐ及び第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定機能。
【００７８】
次に、以上のように構成された素数生成装置による素数生成方法を図６及び図７のフローチャートを用いて述べる。始めに、図６により従来との大きな違いを簡単に述べ、しかる後、図７により素数生成方法を説明する。なお、図７による説明は、前述同様に多項式ｆ（ｐ）を２ｐ＋１の形に規定すると、図６による説明に読み替えることができる。
【００７９】
従来との違いは、図６に示すように、第１素数候補ｐの本格的素数判定ステップＳＴ５を、第２素数候補ｆ（ｐ）の本格的素数判定ステップＳＴ１０の直前に実行することと、多倍長精度（素数候補ｐの２倍）の簡易素数判定ステップ（ＳＴ１〜ＳＴ４及びＳＴ６〜ＳＴ９）に代えて、ワードサイズ（剰余ｋの２倍、除数primes[i]）の簡易素数判定ステップ（ＳＴ２０）を実行することとである。これに加え、図７に示すように、従来の第２素数２ｐ＋１に代えて多項式ｆ（ｐ）又はｆ（ｋ）を生成するため、多項式ｆ（ｐ），ｆ（ｋ）に関連するステップＳＴ１０’，ＳＴ２３’及びＳＴ２４’にはダッシュ記号’を付している。以下、図７を参照しながら順次説明する。
【００８０】
今、前述同様に、素数生成装置１０においては、除数識別情報ｉをｉ＝０として初期化し（ＳＴ１）、第１素数候補としての乱数ｐを生成したとする（ＳＴ２）。なお、前述同様に、ステップＳＴ１，ＳＴ２の順序は逆でもよい。
【００８１】
次に、素数生成装置１０においては、以下のステップＳＴ２１〜ＳＴ２５からなる試行割算を実行する（ＳＴ２０’）。
【００８２】
すなわち、素数生成装置１０においては、第１素数候補ｐに対し、予め保持しておいた除数テーブルＴを用い、除数識別情報ｉ＝１から順次、試行割算を行って剰余ｋを求める（ＳＴ２１）。具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数識別情報ｉ毎の除数primes[i]とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数primes[i]で割り算し、得られた剰余ｋ（＝ｐ÷primes[i]）をバスに出力する。
【００８３】
ＣＰＵ１５は、この剰余ｋが零でない（ｋ≠０）か否かを判定し（ＳＴ２２）、否の場合（ｋ＝０の場合）、ステップＳＴ１に戻る。
【００８４】
一方、ステップＳＴ２２の判定の結果、剰余ｋが零でない場合（ｋ≠０の場合）には、ＣＰＵ１５は、剰余ｋを対応する除数識別情報ｉに関連付けて除数テーブルＴに書き込む。
【００８５】
しかる後、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御し、演算部１７が剰余ｋに基づいて多項式ｆ（ｋ）を計算する（ＳＴ２３’）。具体的には、ＣＰＵ１５は、剰余ｋと、所定の多項式ｆ（Ｘ）の形とに基づいて、次数n，n-1，…，2，1及び次数毎の整数係数ａn，ａn-1，…，ａ2，ａ1を順次、バスを介して演算部１７に入力する。演算部１７は、剰余ｋと、多項式ｆ（Ｘ）の次数及び次数毎の整数係数とに基づいて、剰余ｋに対する次数のベキ乗を計算し、得られたベキ乗結果と整数係数とを乗算し、得られた多項式の変数項をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。また、ＣＰＵ１５は、ｎ次から１次までの変数項ａn・ｋn，ａn-1・ｋn-1，…，ａ2・ｋ2，ａ1・ｋと、定数項ａ0とをバスを介して演算部１７に入力する。演算部１７は、これら変数項と、定数項とを加算し、得られた多項式ｆ（ｋ）をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。
【００８６】
次に、素数生成装置１０においては、この多項式ｆ（ｋ）に対し、前述同様に、除数テーブルＴを用いて試行割算を行う。なお、この多項式ｆ（ｋ）を試行割算して得られる剰余は、前述した多項式ｆ（ｐ）を試行割算して得られる剰余と同じ値になる。このため、本実施形態の試行割算の方が演算サイズを低減できる利点がある。
【００８７】
試行割算の後、素数生成装置１０のＣＰＵ１５は、多項式ｆ（ｋ）を除数primes[i]で割り算した剰余が零でない（f(k)÷primes[i]≠0）か否かを判定する（ＳＴ２４’）。
【００８８】
ステップＳＴ２４’の判定の結果、否の場合（f(k)÷primes[i]＝０の場合）、ステップＳＴ１に戻る。
【００８９】
一方、ステップＳＴ２４’の判定の結果、零でない場合（f(k)÷primes[i]≠０の場合）には、ＣＰＵ１５は、除数識別情報ｉを＋１だけ更新し（ＳＴ２５）、ステップＳＴ２１に戻って処理を継続する。
【００９０】
このステップＳＴ２１〜ＳＴ２５までの処理（ＳＴ２０’）は、除数識別情報ｉが最大値PRIMES_NUMである場合のＳＴ２４’の処理を終了するまで継続される。
【００９１】
ＣＰＵ１５は、ステップＳＴ２４’の処理を終了したときの除数識別情報ｉが最大値PRIMES_NUMである場合には、ステップＳＴ２０’の処理を終了する。換言すると、ＣＰＵ１５は、除数テーブルＴ内の全ての除数による全ての試行割算の結果が剰余を持つとき、ｐ，ｆ（ｐ）の簡易素数判定（ＳＴ２０’）を終了する。
【００９２】
続いて、素数生成装置１０は、第１素数候補ｐに対し、フェルマー法などのように、フェルマーの小定理を含む本格的な素数判定法を実行する（ＳＴ５）。具体的には、ＣＰＵ１５が、前述した所定の素数判定法のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【００９３】
さてステップＳＴ５の素数判定の結果、第１素数候補ｐが素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１に戻る。
【００９４】
ステップＳＴ５の素数判定の結果、第１素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置１０は、第２素数候補ｆ（ｐ）を計算する。しかる後、素数生成装置１０は、この第２素数候補ｆ（ｐ）に対し、前述同様に、フェルマー法又はミラー−ラビン法などの、本格的な素数判定法を実行する（ＳＴ１０’）。
【００９５】
ステップＳＴ１０’の素数判定の結果、第２素数候補ｆ（ｐ）が素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１へ戻る。
【００９６】
ステップＳＴ１０’の素数判定の結果、第２素数候補ｆ（ｐ）が素数である場合（ＯＫの場合）には、素数生成装置１０は、第２素数ｆ（ｐ）と、第１素数ｐとを入出力Ｉ／Ｆ１４から出力する。
【００９７】
上述したように本実施形態によれば、第１の実施形態の効果に加え、第２素数の候補ｆ（ｐ）に関する試行割算を、剰余ｋの多項式ｆ（ｋ）に関する試行割算により行う構成により、従来の多倍長精度の試行割算とは異なり、ワードサイズの試行割算を実行できるので、第１及び第２素数ｐ，ｆ（ｐ）をより一層高速に生成することができる。
【００９８】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【００９９】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１００】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１０１】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１０２】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１０３】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１０４】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１０５】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１０６】
【図１】本発明の第１の実施形態に係る素数生成装置の構成を示す模式図である。
【図２】同実施形態における除数テーブルの構成を説明するための模式図である。
【図３】同実施形態における素数生成方法を説明するためのフローチャートである。
【図４】同実施形態における素数生成方法を説明するためのフローチャートである。
【図５】本発明の第２の実施形態における除数テーブルの構成を説明するための模式図である。
【図６】同実施形態における素数生成方法を説明するためのフローチャートである。
【図７】同実施形態における素数生成方法を説明するためのフローチャートである。
【図８】一般的な素数生成方法を説明するためのフローチャートである。
【符号の説明】
【０１０７】
１０…素数生成装置、１１…プログラム記憶部、１２…テーブル記憶部、１３…不揮発性メモリ、１４…入出力Ｉ／Ｆ、１５…ＣＰＵ、１６…乱数生成部、１７…演算部、Ｔ…除算テーブル。
【技術分野】
【０００１】
本発明は、素数を生成するための素数生成装置、プログラム及び方法に係り、例えば、セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を高速に生成し得る素数生成装置、プログラム及び方法に関する。
【背景技術】
【０００２】
暗号分野においては、ｐを素数としたとき、２ｐ＋１という形の素数が、暗号の安全性を高めるために用いられている。この形の素数はセーフプライム（safe prime）と呼ばれる。セーフプライムは、ディフィー−へルマン（Diffie-Hellman）鍵交換を始めとして、多くの暗号通信プロトコルで用いられている。
【０００３】
このセーフプライムを生成するための効率的な方法は、今のところ知られていない。一般的な素数生成方法においては、素数候補の乱数ｐを素数判定し、素数であれば、さらにセーフプライム候補の数２ｐ＋１を素数判定することにより、セーフプライム形の素数２ｐ＋１を生成している。
【０００４】
図８は一般的な素数生成方法を説明するためのフローチャートである。この素数生成方法は、素数候補ｐの簡易素数判定（ＳＴ１〜ＳＴ４）、素数候補ｐの本格的素数判定（ＳＴ５）、セーフプライム候補２ｐ＋１の簡易素数判定（ＳＴ６〜ＳＴ９）、セーフプライム候補２ｐ＋１の本格的素数判定（ＳＴ１０）から構成されている。具体的には、この素数判定方法は、例えばコンピュータからなる素数生成装置に実行される。
【０００５】
始めに、素数生成装置は、除数識別情報ｉをｉ＝０として初期化する（ＳＴ１）。続いて、素数生成装置は、素数候補としての乱数ｐを生成する（ＳＴ２）。なお、ステップＳＴ１，ＳＴ２の順序は逆でもよい。
【０００６】
次に、素数生成装置は、素数候補ｐに対し、予め保持しておいた除数テーブルを用い、除数識別情報ｉ＝１から順次、試行割算を行う（ＳＴ３）。
【０００７】
ここで、除数識別情報ｉは、除数テーブルから除数primes[i]を読み出すために用いられる。なお、除数テーブルは、除数識別情報ｉ及び除数primes[i]が互いに関連付けて記述されている。除数識別情報ｉは、１，２，…，PRIMES_NUM−１，PRIMES_NUM、のように、自然数としている。
【０００８】
素数生成装置は、素数候補ｐを除数primes[i]で割り算した剰余が０のとき（p÷primes[i]=0）、又は除数識別情報ｉが最大値PRIMES_NUMの場合の割り算を終えたとき（i＝PRIMES_NUM）、ステップＳＴ３の試行割算を終了する。
【０００９】
素数生成装置は、ステップＳＴ３の試行割算を終了したときの除数識別情報ｉが最大値PRIMES_NUMであるか否かを判定し（ＳＴ４）、否の場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００１０】
一方、ステップＳＴ４の判定の結果、除数識別情報ｉが最大値PRIMES_NUMの場合（試行割算に成功した場合）、素数生成装置は、素数候補ｐに対し、フェルマー(Fermat)法、ミラー−ラビン(Miller-Rabin)法などの、本格的な素数判定を行う（ＳＴ５）。
【００１１】
ステップＳＴ５の素数判定の結果、素数候補ｐが素数ではない場合（ＮＧの場合）には、ステップＳＴ１に戻る。
【００１２】
ステップＳＴ５の素数判定の結果、素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置は、除数識別情報ｉをｉ＝０として初期化する（ＳＴ６）。続いて、素数生成装置は、セーフプライム候補としての数２ｐ＋１を計算する（ＳＴ７）。なお、ステップＳＴ６，ＳＴ７の順序は逆でもよい。
【００１３】
次に、素数生成装置は、セーフプライム候補２ｐ＋１に対し、前述同様に、除数テーブルを用いて試行割算を行う（ＳＴ８）。素数生成装置は、セーフプライム候補２ｐ＋１を除数primes[i]で割り算した剰余が０のとき（(2p+1)÷primes[i]=0）、又は除数識別情報ｉが最大値PRIMES_NUMの場合の割り算を終えたとき（i＝PRIMES_NUM）、ステップＳＴ８の試行割算を終了する。
【００１４】
素数生成装置は、ステップＳＴ８の試行割算を終了したときの除数識別情報ｉが最大値PRIMES_NUMであるか否かを判定し（ＳＴ９）、否の場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００１５】
一方、ステップＳＴ９の判定の結果、除数識別情報ｉが最大値PRIMES_NUMの場合（試行割算に成功した場合）、素数生成装置は、セーフプライム候補２ｐ＋１に対し、フェルマー(Fermat)法、ミラー−ラビン(Miller-Rabin)法などの、本格的な素数判定を行う（ＳＴ１０）。
【００１６】
ステップＳＴ１０の素数判定の結果、セーフプライム候補２ｐ＋１が素数ではない場合（ＮＧの場合）には、ステップＳＴ１へ戻る。
【００１７】
ステップＳＴ１０の素数判定の結果、セーフプライム候補２ｐ＋１が素数である場合（ＯＫの場合）には、素数生成装置は、セーフプライム形の素数２ｐ＋１と、素数ｐとを出力する。
【００１８】
なお、以上のような一般的な素数生成方法に限らず、セーフプライムを生成する方法には種々の方式がある（例えば非特許文献１，２参照）。ここで、非特許文献１には、セーフプライムｑを生成するために、（ｑ−１）／２を乱数として生成し、この乱数を素数判定し、素数判定に合格したら、ｑを素数判定する方式が開示されている。
【００１９】
非特許文献２には、セーフプライムｑを生成するために、（ｑ−１）／２を乱数として生成し、ある定数以下の小さな奇素数ｒに対して、（ｑ−１）／２≡（ｒ−１）／２ (mod r)なる乱数（ｑ−１）／２を除去し、残った乱数（ｑ−１）／２を素数判定し、素数判定に合格したら、ｑを素数判定する方式が開示されている。
【非特許文献１】“Handbook of applied cryptography p.164” http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf
【非特許文献２】“Safe Prime Generation with a Combined Sieve” http://eprint.iacr.org/2003/186.pdf
【発明の開示】
【発明が解決しようとする課題】
【００２０】
しかしながら、以上のような素数生成方法では、次のような問題がある。
例えば、図８に示した方法では、乱数ｐの値が大きくなるにつれ、セーフプライム形の素数２ｐ＋１を生成するための時間が、非常に増大するという問題がある。このため、素数生成装置を備えた情報機器や、このような情報機器を複数台備えた情報システム（以下、情報機器等という）においては、素数生成装置の計算負荷を増大させ、システム稼働率を低下させる問題がある。
【００２１】
このような問題を解決する観点から、情報機器等では、セーフプライムを予め生成して保持する方式や、セーフプライムではない、一般的な素数を用いた暗号通信を行う方式が知られている。しかしながら、これらの方式は、情報機器等のセキュリティレベルを低下させる場合があるので、上記問題を実際に解決したとは言えない。なお、非特許文献１に記載の方法は、前述した図８に示した方法と同様の問題があると考えられる。
【００２２】
一方、非特許文献２に記載の方法は、予め奇素数ｒを法として、（ｒ−１）／２に合同な乱数をセーフプライム候補から除去した後に、残ったセーフプライム候補を素数判定するので、素数生成装置の計算負荷を減少できる。
【００２３】
補足すると、素数生成装置の計算負荷は、試行割算よりも本格的素数判定の方がはるかに大きい。そこで、非特許文献２に記載の方法は、本格的素数判定の前に簡単な合成数を除去するので、素数生成装置の計算負荷を減少できる。この非特許文献２に記載の方法によれば、上記問題を解決することができる。
【００２４】
但し、非特許文献２に記載の方法は、特に問題は無いものの、本発明者の検討によれば、セーフプライム形の素数２ｐ＋１に限定されている不都合があると考えられる。
【００２５】
本発明は上記実情を考慮してなされたもので、セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を高速に生成し得る素数生成装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００２６】
第１の発明は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置であって、予め除数識別情報毎に除数が記憶された除数記憶手段と、前記第１素数の候補ｐとして乱数を生成する乱数生成手段と、前記第１素数の候補ｐに基づいて、前記第２素数の候補ｆ（ｐ）を算出する第２素数候補算出手段と、前記各素数の候補ｐ，ｆ（ｐ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行手段と、前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段とを備えた素数生成装置である。
【００２７】
第２の発明は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置であって、予め除数識別情報毎に除数が記憶されており、試行割算結果の剰余が前記除数識別情報に関連付けて記憶される除数記憶手段と、前記第１素数の候補ｐとして乱数を生成する乱数生成手段と、前記第１素数の候補ｐに対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行手段と、前記第１割算実行手段による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを前記除数記憶手段に書き込む剰余書込手段と、前記剰余書込手段により書き込まれた剰余ｋに基づいて、前記多項式ｆ（ｋ）を計算する多項式計算手段と、前記多項式ｆ（ｋ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第２割算実行手段と、前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記第１素数の候補ｐ及び前記第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段とを備えた素数生成装置である。
【００２８】
（作用）
第１の発明によれば、第１素数ｐと、この第１素数ｐから算出可能で定数項が０ではない多項式の形をもつ第２素数ｆ（ｐ）とを生成する構成により、セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を生成することができる。
【００２９】
これに加え、第１の発明によれば、高速に計算可能な試行割算を先に行った後に、本格的な素数判定法（フェルマーの小定理を含む素数判定法）を行う構成により、時間のかかる本格的な素数判定法の実行割合を減少できるので、前述した第１及び第２素数ｐ，ｆ（ｐ）を高速に生成することができる。
【００３０】
第２の発明によれば、第１の発明の作用効果に加え、第２素数の候補ｆ（ｐ）に関する試行割算を、剰余ｋの多項式ｆ（ｋ）に関する試行割算により行う構成により、従来とは異なり、試行割算をワードサイズで実行できるので、第１及び第２素数ｐ，ｆ（ｐ）をより一層高速に生成することができる。
【００３１】
なお、第１及び第２の各発明は「装置」として表現したが、これに限らず、「プログラム」、「方法」又は「コンピュータ読み取り可能な記憶媒体」として表現してもよい。
【発明の効果】
【００３２】
以上説明したように本発明によれば、セーフプライム形の素数に限定されず、第１素数の多項式の形をもつ第２素数を高速に生成できる。
【発明を実施するための最良の形態】
【００３３】
以下、本発明の各実施形態を図面を用いて説明する。なお、以下の説明中、乱数、素数、素数候補、定数項、整数係数、多項式、除数、剰余などの語を用いるが、これらは、乱数データ、素数データ、素数候補データ、定数項データ、整数係数データ、多項式データ、除数データ、剰余データ等のように、「データ」の語を追記して読み替えてもよい。
【００３４】
（第１の実施形態）
図１は本発明の第１の実施形態に係る素数生成装置の構成を示す模式図である。この素数生成装置１０は、定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、Ｚは整数Ｘを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成するものである。ここで、第２素数ｆ（ｐ）は、例えば多項式の次数をｎとし、次数毎の整数係数をａn，ａn-1，…，ａ2，ａ1とし、定数項をａ0としたとき、次式に示すように計算される。
【００３５】
ｆ（ｐ）＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0
このような第２素数ｆ（ｐ）は、次数ｎ＝１、整数係数ａ1＝２、定数項ａ0＝１の場合、セーフプライム２ｐ＋１となる。但し、第２素数ｆ（ｐ）は、セーフプライム２ｐ＋１に限定されない。
【００３６】
この素数生成装置１０は、具体的には携帯電話又はスマートカードなどの演算機の素数生成部として構成され、ハードウェア及びソフトウェアの組合せにより素数生成処理を行うものである。
【００３７】
例えば素数生成装置１０においては、プログラム記憶部１１、テーブル記憶部１２、ＲＡＭ１３、入出力Ｉ／Ｆ１４、ＣＰＵ（中央処理装置）１５、乱数生成部１６及び演算部１７が互いにバスを介して接続されている。
【００３８】
プログラム記憶部１１は、ＣＰＵ１５に実行されるプログラムが記憶されるハードウェア資源としてのメモリであり、例えばＲＯＭ（リードオンリーメモリ）が使用可能となっている。ここで、プログラムは、例えば図３又は図４に示す素数生成機能を実現させるためのものである。この素数生成機能としては、例えば以下の機能(f11-1)〜(f11-5)を含んでいる。
【００３９】
(f11-1) 除数識別情報毎に除数が記憶された除数テーブルＴをテーブル記憶部１２に予め記憶させる機能。
(f11-2) 乱数生成部１６の制御により、第１素数の候補ｐとして乱数を生成する機能。
(f11-3) 演算部１７の制御により、第１素数の候補ｐに基づいて、第２素数の候補ｆ（ｐ）を算出する第２素数候補算出機能。
(f11-4) 演算部１７の制御により、各素数の候補ｐ，ｆ（ｐ）に対し、除数テーブルＴ内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行機能。
(f11-5) 演算部１７の制御により、除数テーブルＴ内の全ての除数による全ての試行割算の結果が剰余を持つとき、各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定機能。
【００４０】
係るプログラムは、外部の記憶媒体又はネットワークから予めプログラム記憶部１１にインストールされてもよい。
【００４１】
テーブル記憶部１２は、ＣＰＵ１５から読出／書込可能なハードウェア資源としてのＲＡＭ（ランダムアクセスメモリ）である。テーブル記憶部１２は、予め除数テーブルＴが記憶されており、さらにＣＰＵ１５により、演算に必要なデータや演算途中のデータ等が記憶される。除数テーブルＴは、図２に示すように、予め除数識別情報ｉ毎に除数primes[i]が記述されたものである。
【００４２】
除数識別情報ｉは、前述同様に、１，２，…，PRIMES_NUM−１，PRIMES_NUM、のように、自然数としている。なお、ここでは、除数識別情報ｉの最大値PRIMES_NUMを６５４２としている。
【００４３】
除数primes[i]は、小さい順に数えてｉ番目の素数である。このような除数の数列に関する説明は、文献（D. E. Knuth 著（中川圭介訳），“KNUTH 第４分冊 準数値算法／算術演算”，サイエンス社，p.205, 1986.）に記載されている。なお、ここでは、除数テーブルＴにおける除数の最大値を“６５５２１”としている。また、除数テーブルＴは、予めプログラム記憶部１１内のプログラムに含まれていてもよい。
【００４４】
不揮発性メモリ１３は、例えば生成された素数ｐ，ｆ（ｐ）などがＣＰＵ１５から読出／書込可能に記憶されるハードウェア資源としてのメモリであり、例えば、ＥＥＰＲＯＭ（Electric Erasable Programmable ＲＯＭ）が使用可能となっている。但し、不揮発性メモリ１３は、必須ではなく省略してもよい。
【００４５】
入出力Ｉ／Ｆ１４は、素数生成装置１０と、この素数生成装置１０を保持する情報機器との間のインターフェイス機器であり、例えば、素数生成指令を入力し、得られた素数ｐ，ｆ（ｐ）を出力する際に用いられる。
【００４６】
ここでいう情報機器としては、何らかの暗号処理を実行するものであれば任意のデバイスが適用可能である。何らかの暗号処理とは、例えば公開鍵暗号方式における暗号処理、復号処理、署名生成処理又は署名検証処理などである。情報機器の例としては、スマートカード又は携帯電話等の如き、ユーザ毎に携帯可能なデバイスが挙げられる。情報機器の用途は任意であり、例えば、非匿名又は匿名のユーザ認証などが挙げられる。
【００４７】
ＣＰＵ１５は、プログラム記憶部１１内のプログラムを実行することにより、例えば図３に示す手順で各部１２〜１７を制御し、素数生成処理を実行する機能を有するものである。
【００４８】
乱数生成部１６は、ＣＰＵ１５により制御されて乱数ｐを生成し、この乱数ｐをバスに送出するハードウェア資源としての乱数生成回路である。ここで、乱数生成部１６により生成される乱数ｐは、真の乱数又は疑似乱数のいずれでもよい。
【００４９】
なお、乱数生成部１６は、独立のハードウェア資源で実現する場合に限らず、ＣＰＵ１５とプログラムで実現してもよい。また、乱数生成部１６を省略し、乱数ｐを外部から入力させる構成としてもよい。
【００５０】
演算部１７は、ＣＰＵ１５により制御され、例えばＣＰＵ１５から入力されたデータに基づいて演算を実行し、演算結果をバスに出力するハードウェア資源としての演算回路である。なお、演算部１７は、処理速度を向上させる観点から独立のハードウェア回路として設けられており、例えばコプロセッサ等の如き、多倍長の演算が可能なものであるが、ハードウェア回路に限らず、ＣＰＵ１５とプログラムで実現してもよい。
【００５１】
なお、このような素数生成装置１０は、ハードウェア及びソフトウェアの組合せに限らず、ハードウェア又はソフトウェアのいずれか一方により構成されてもよい。
【００５２】
次に、以上のように構成された素数生成装置による素数生成方法を図３及び図４のフローチャートを用いて述べる。始めに、図３により従来との大きな違いを簡単に述べ、しかる後、図４により素数生成方法を説明する。なお、図４による説明は、多項式ｆ（ｐ）を２ｐ＋１の形に規定すると、図３による説明に読み替えることができる。
【００５３】
従来との違いは、図３に示すように、第１素数候補ｐの本格的素数判定ステップＳＴ５を、第１及び第２素数候補ｐ，ｆ（ｐ）の簡易素数判定ステップ（ＳＴ１〜ＳＴ４及びＳＴ６〜ＳＴ９）の後に実行することである。これに加え、図４に示すように、従来の第２素数２ｐ＋１に代えて第２素数ｆ（ｐ）を生成するため、第２素数ｆ（ｐ）に関連するステップＳＴ７’，ＳＴ８’，ＳＴ１０’にはダッシュ記号’を付している。以下、図４を参照しながら順次説明する。
【００５４】
始めに、図示しない情報機器では、何らかの暗号処理中に、第１素数ｐ及び第２素数ｆ（ｐ）を生成する必要が生じたとする。ここで、情報機器においては、保持する素数生成装置１０に入出力Ｉ／Ｆ１４を介して素数生成指令を入力する。
【００５５】
素数生成装置１０においては、素数生成指令を受けると、ＣＰＵ１５が除数識別情報ｉをｉ＝０として初期化する（ＳＴ１）。
【００５６】
続いて、素数生成装置１０においては、ＣＰＵ１５が乱数生成部１６を制御し、乱数生成部１６が、第１素数候補としての乱数ｐを生成する（ＳＴ２）。なお、ステップＳＴ１，ＳＴ２の順序は逆でもよい。
【００５７】
次に、素数生成装置１０においては、第１素数候補ｐに対し、予め保持しておいた除数テーブルＴを用い、除数識別情報ｉ＝１から順次、試行割算を行う（ＳＴ３）。
【００５８】
具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数識別情報ｉ毎の除数primes[i]とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数primes[i]で割り算し、得られた剰余をバスに出力する。
【００５９】
ＣＰＵ１５は、第１素数候補ｐを除数primes[i]で割り算した剰余が０のとき（p÷primes[i]=0）、又は除数識別情報ｉが最大値PRIMES_NUMの場合の割り算を終えたとき（i＝PRIMES_NUM）、ステップＳＴ３の試行割算を終了する。
【００６０】
ＣＰＵ１５は、ステップＳＴ３の試行割算を終了したときの除数識別情報ｉが最大値PRIMES_NUMであるか否かを判定し（ＳＴ４）、否の場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００６１】
一方、ステップＳＴ４の判定の結果、除数識別情報ｉが最大値PRIMES_NUMの場合（試行割算に成功した場合）には、ＣＰＵ１５は、除数識別情報ｉをｉ＝０として初期化する（ＳＴ６）。
【００６２】
続いて、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御し、演算部１７が第２素数候補としての多項式ｆ（ｐ）を計算する（ＳＴ７’）。具体的には、ＣＰＵ１５は、第１素数候補ｐと、所定の多項式ｆ（Ｘ）の形とに基づいて、次数n，n-1，…，2，1及び次数毎の整数係数ａn，ａn-1，…，ａ2，ａ1を順次、バスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐと、多項式ｆ（Ｘ）の次数及び次数毎の整数係数とに基づいて、第１素数候補ｐに対する次数のベキ乗を計算し、得られたベキ乗結果と整数係数とを乗算し、得られた多項式の変数項をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。また、ＣＰＵ１５は、ｎ次から１次までの変数項ａn・ｐn，ａn-1・ｐn-1，…，ａ2・ｐ2，ａ1・ｐと、定数項ａ0とをバスを介して演算部１７に入力する。演算部１７は、これら変数項と、定数項とを加算し、得られた多項式ｆ（ｐ）をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。なお、ステップＳＴ６，ＳＴ７’の順序は逆でもよい。
【００６３】
次に、素数生成装置１０においては、この多項式ｆ（ｐ）からなる第２素数候補ｆ（ｐ）に対し、前述同様に、除数テーブルＴを用いて試行割算を行う（ＳＴ８’）。
【００６４】
素数生成装置１０のＣＰＵ１５は、第２素数候補ｆ（ｐ）を除数primes[i]で割り算した剰余が０のとき（f(p)÷primes[i]＝0）、又は除数識別情報ｉが最大値PRIMES_NUMの場合の割り算を終えたとき（i＝PRIMES_NUM）、ステップＳＴ８’の試行割算を終了する。
【００６５】
ＣＰＵ１５は、ステップＳＴ８’の試行割算を終了したときの除数識別情報ｉが最大値PRIMES_NUMであるか否かを判定し（ＳＴ９）、否の場合（試行割算に失敗した場合）にはステップＳＴ１に戻る。
【００６６】
一方、ステップＳＴ９の判定の結果、除数識別情報ｉが最大値PRIMES_NUMの場合（試行割算に成功した場合）、ＣＰＵ１５は、ｐ，ｆ（ｐ）の簡易素数判定（ＳＴ１〜ＳＴ４，ＳＴ６〜ＳＴ９）を終了する。換言すると、ＣＰＵ１５は、除数テーブルＴ内の全ての除数による全ての試行割算の結果が剰余を持つとき、ｐ，ｆ（ｐ）の簡易素数判定（ＳＴ１〜ＳＴ４，ＳＴ６〜ＳＴ９）を終了する。
【００６７】
次に、素数生成装置１０は、第１素数候補ｐに対し、フェルマー法などのように、フェルマーの小定理を含む本格的な素数判定法を実行する（ＳＴ５）。具体的には、ＣＰＵ１５が所定の素数判定法のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【００６８】
ここで、所定の素数判定法としては、高速な判定の観点から、フェルマー(Fermat)の小定理を利用した素数判定法を改良して、あるところまで調べれば、素数候補が素数であることを確率的又は確定的に判定できるようにしたものを用いている。このような素数判定法のうち、確率的な素数判定法の例としては、フェルマー法、ソロベイ(Solovay)ーストラッセン(Strassen)法、ラビン法などが挙げられる。確定的な素数判定法の例としては、ミラー法、アドルマン(Adleman)−ルメリ(Rumely)法、コーエン(Cohen)−レンストラ(Lenstra)法などが挙げられる。ここで述べた素数判定法に関する説明は、文献（池野信一、小山謙二共著、“現代暗号理論”、（社）電子情報通信学会、コロナ社、ｐ２４０−２４１、１９８６）に記載されている。
【００６９】
さてステップＳＴ５の素数判定の結果、第１素数候補ｐが素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１に戻る。
【００７０】
ステップＳＴ５の素数判定の結果、第１素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置１０は、第２素数候補ｆ（ｐ）に対し、前述同様に、フェルマー法又はミラー−ラビン法などの、本格的な素数判定を行う（ＳＴ１０’）。
【００７１】
ステップＳＴ１０’の素数判定の結果、第２素数候補ｆ（ｐ）が素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１へ戻る。
【００７２】
ステップＳＴ１０’の素数判定の結果、第２素数候補ｆ（ｐ）が素数である場合（ＯＫの場合）には、素数生成装置１０は、第２素数ｆ（ｐ）と、第１素数ｐとを入出力Ｉ／Ｆ１４から出力する。
【００７３】
上述したように本実施形態によれば、第１素数ｐと、この第１素数ｐから算出可能で定数項（ａ0）が０ではない多項式ｆ（ｐ）（＝ａn・ｐn ＋ ａn-1・ｐn-1 ＋ … ＋ ａ2・ｐ2 ＋ ａ1・ｐ ＋ ａ0）の形をもつ第２素数ｆ（ｐ）とを生成する構成により、セーフプライム形の素数（２ｐ＋１）に限定されず、第１素数ｐの多項式の形をもつ第２素数ｆ（ｐ）を生成することができる。
【００７４】
これに加え、本実施形態によれば、高速に計算可能な試行割算を先に行った後に、本格的な素数判定法（フェルマーの小定理を含む素数判定法）を行う構成により、時間のかかる本格的な素数判定法の実行割合を減少できるので、前述した第１及び第２素数ｐ，ｆ（ｐ）を高速に生成することができる。
【００７５】
（第２の実施形態）
次に、本発明の第２の実施形態について前述した図１を参照しながら説明する。すなわち、本実施形態は、第１の実施形態の変形例であり、試行割算のサイズを低減して素数生成の高速化を図る観点から、第２素数の候補ｆ（ｐ）に関する試行割算を、剰余ｋの多項式ｆ（ｋ）に関する試行割算により行うものである。
【００７６】
これに伴い、除数テーブルＴは、図５に示すように、予め除数識別情報ｉ毎に除数primes[i]が記憶されており、試行割算結果の剰余ｋ[i]が除数識別情報ｉに関連付けて記憶されるものとなっている。
【００７７】
また、プログラム記憶部１１内のプログラムとしては、以下の機能(f11-1’)〜(f11-5)を含むものとなっている。
(f11-1’) 予め除数識別情報毎に除数が記憶されており、試行割算結果の剰余が除数識別情報に関連付けて記憶される除数テーブルＴをテーブル記憶部１２に書込む機能。
(f11-2) 乱数生成部１６の制御により、第１素数の候補ｐとして乱数を生成する機能。
(f11-6) 演算部１７の制御により、第１素数の候補ｐに対し、除数テーブルＴ内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行機能。
(f11-7) 演算部１７の制御により、第１割算実行機能による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを除数テーブルＴに書き込む剰余書込機能。
(f11-8) 演算部１７の制御により、剰余書込機能により書き込まれた剰余ｋに基づいて、多項式ｆ（ｋ）を計算する多項式計算機能。
(f11-9) 演算部１７の制御により、多項式ｆ（ｋ）に対し、除数テーブルＴ内の除数識別情報毎の除数により個別に試行割算を実行する第２割算実行機能。
(f11-5) 演算部１７の制御により、除数テーブルＴ内の全ての除数による全ての試行割算の結果が剰余を持つとき、第１素数の候補ｐ及び第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定機能。
【００７８】
次に、以上のように構成された素数生成装置による素数生成方法を図６及び図７のフローチャートを用いて述べる。始めに、図６により従来との大きな違いを簡単に述べ、しかる後、図７により素数生成方法を説明する。なお、図７による説明は、前述同様に多項式ｆ（ｐ）を２ｐ＋１の形に規定すると、図６による説明に読み替えることができる。
【００７９】
従来との違いは、図６に示すように、第１素数候補ｐの本格的素数判定ステップＳＴ５を、第２素数候補ｆ（ｐ）の本格的素数判定ステップＳＴ１０の直前に実行することと、多倍長精度（素数候補ｐの２倍）の簡易素数判定ステップ（ＳＴ１〜ＳＴ４及びＳＴ６〜ＳＴ９）に代えて、ワードサイズ（剰余ｋの２倍、除数primes[i]）の簡易素数判定ステップ（ＳＴ２０）を実行することとである。これに加え、図７に示すように、従来の第２素数２ｐ＋１に代えて多項式ｆ（ｐ）又はｆ（ｋ）を生成するため、多項式ｆ（ｐ），ｆ（ｋ）に関連するステップＳＴ１０’，ＳＴ２３’及びＳＴ２４’にはダッシュ記号’を付している。以下、図７を参照しながら順次説明する。
【００８０】
今、前述同様に、素数生成装置１０においては、除数識別情報ｉをｉ＝０として初期化し（ＳＴ１）、第１素数候補としての乱数ｐを生成したとする（ＳＴ２）。なお、前述同様に、ステップＳＴ１，ＳＴ２の順序は逆でもよい。
【００８１】
次に、素数生成装置１０においては、以下のステップＳＴ２１〜ＳＴ２５からなる試行割算を実行する（ＳＴ２０’）。
【００８２】
すなわち、素数生成装置１０においては、第１素数候補ｐに対し、予め保持しておいた除数テーブルＴを用い、除数識別情報ｉ＝１から順次、試行割算を行って剰余ｋを求める（ＳＴ２１）。具体的には、ＣＰＵ１５は、第１素数候補ｐと、除数テーブルＴ内の除数識別情報ｉ毎の除数primes[i]とをバスを介して演算部１７に入力する。演算部１７は、第１素数候補ｐを除数primes[i]で割り算し、得られた剰余ｋ（＝ｐ÷primes[i]）をバスに出力する。
【００８３】
ＣＰＵ１５は、この剰余ｋが零でない（ｋ≠０）か否かを判定し（ＳＴ２２）、否の場合（ｋ＝０の場合）、ステップＳＴ１に戻る。
【００８４】
一方、ステップＳＴ２２の判定の結果、剰余ｋが零でない場合（ｋ≠０の場合）には、ＣＰＵ１５は、剰余ｋを対応する除数識別情報ｉに関連付けて除数テーブルＴに書き込む。
【００８５】
しかる後、素数生成装置１０においては、ＣＰＵ１５が演算部１７を制御し、演算部１７が剰余ｋに基づいて多項式ｆ（ｋ）を計算する（ＳＴ２３’）。具体的には、ＣＰＵ１５は、剰余ｋと、所定の多項式ｆ（Ｘ）の形とに基づいて、次数n，n-1，…，2，1及び次数毎の整数係数ａn，ａn-1，…，ａ2，ａ1を順次、バスを介して演算部１７に入力する。演算部１７は、剰余ｋと、多項式ｆ（Ｘ）の次数及び次数毎の整数係数とに基づいて、剰余ｋに対する次数のベキ乗を計算し、得られたベキ乗結果と整数係数とを乗算し、得られた多項式の変数項をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。また、ＣＰＵ１５は、ｎ次から１次までの変数項ａn・ｋn，ａn-1・ｋn-1，…，ａ2・ｋ2，ａ1・ｋと、定数項ａ0とをバスを介して演算部１７に入力する。演算部１７は、これら変数項と、定数項とを加算し、得られた多項式ｆ（ｋ）をバスを介してＲＡＭ（テーブル記憶部１２）に書き込む。
【００８６】
次に、素数生成装置１０においては、この多項式ｆ（ｋ）に対し、前述同様に、除数テーブルＴを用いて試行割算を行う。なお、この多項式ｆ（ｋ）を試行割算して得られる剰余は、前述した多項式ｆ（ｐ）を試行割算して得られる剰余と同じ値になる。このため、本実施形態の試行割算の方が演算サイズを低減できる利点がある。
【００８７】
試行割算の後、素数生成装置１０のＣＰＵ１５は、多項式ｆ（ｋ）を除数primes[i]で割り算した剰余が零でない（f(k)÷primes[i]≠0）か否かを判定する（ＳＴ２４’）。
【００８８】
ステップＳＴ２４’の判定の結果、否の場合（f(k)÷primes[i]＝０の場合）、ステップＳＴ１に戻る。
【００８９】
一方、ステップＳＴ２４’の判定の結果、零でない場合（f(k)÷primes[i]≠０の場合）には、ＣＰＵ１５は、除数識別情報ｉを＋１だけ更新し（ＳＴ２５）、ステップＳＴ２１に戻って処理を継続する。
【００９０】
このステップＳＴ２１〜ＳＴ２５までの処理（ＳＴ２０’）は、除数識別情報ｉが最大値PRIMES_NUMである場合のＳＴ２４’の処理を終了するまで継続される。
【００９１】
ＣＰＵ１５は、ステップＳＴ２４’の処理を終了したときの除数識別情報ｉが最大値PRIMES_NUMである場合には、ステップＳＴ２０’の処理を終了する。換言すると、ＣＰＵ１５は、除数テーブルＴ内の全ての除数による全ての試行割算の結果が剰余を持つとき、ｐ，ｆ（ｐ）の簡易素数判定（ＳＴ２０’）を終了する。
【００９２】
続いて、素数生成装置１０は、第１素数候補ｐに対し、フェルマー法などのように、フェルマーの小定理を含む本格的な素数判定法を実行する（ＳＴ５）。具体的には、ＣＰＵ１５が、前述した所定の素数判定法のアルゴリズムに従って演算部１７を制御することにより、素数判定を実行する。
【００９３】
さてステップＳＴ５の素数判定の結果、第１素数候補ｐが素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１に戻る。
【００９４】
ステップＳＴ５の素数判定の結果、第１素数候補ｐが素数である場合（ＯＫの場合）には、素数生成装置１０は、第２素数候補ｆ（ｐ）を計算する。しかる後、素数生成装置１０は、この第２素数候補ｆ（ｐ）に対し、前述同様に、フェルマー法又はミラー−ラビン法などの、本格的な素数判定法を実行する（ＳＴ１０’）。
【００９５】
ステップＳＴ１０’の素数判定の結果、第２素数候補ｆ（ｐ）が素数ではない場合（ＮＧの場合）には、素数生成装置１０はステップＳＴ１へ戻る。
【００９６】
ステップＳＴ１０’の素数判定の結果、第２素数候補ｆ（ｐ）が素数である場合（ＯＫの場合）には、素数生成装置１０は、第２素数ｆ（ｐ）と、第１素数ｐとを入出力Ｉ／Ｆ１４から出力する。
【００９７】
上述したように本実施形態によれば、第１の実施形態の効果に加え、第２素数の候補ｆ（ｐ）に関する試行割算を、剰余ｋの多項式ｆ（ｋ）に関する試行割算により行う構成により、従来の多倍長精度の試行割算とは異なり、ワードサイズの試行割算を実行できるので、第１及び第２素数ｐ，ｆ（ｐ）をより一層高速に生成することができる。
【００９８】
なお、上記実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【００９９】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０１００】
また、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０１０１】
さらに、本発明における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０１０２】
また、記憶媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０１０３】
尚、本発明におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０１０４】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０１０５】
なお、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。
【図面の簡単な説明】
【０１０６】
【図１】本発明の第１の実施形態に係る素数生成装置の構成を示す模式図である。
【図２】同実施形態における除数テーブルの構成を説明するための模式図である。
【図３】同実施形態における素数生成方法を説明するためのフローチャートである。
【図４】同実施形態における素数生成方法を説明するためのフローチャートである。
【図５】本発明の第２の実施形態における除数テーブルの構成を説明するための模式図である。
【図６】同実施形態における素数生成方法を説明するためのフローチャートである。
【図７】同実施形態における素数生成方法を説明するためのフローチャートである。
【図８】一般的な素数生成方法を説明するためのフローチャートである。
【符号の説明】
【０１０７】
１０…素数生成装置、１１…プログラム記憶部、１２…テーブル記憶部、１３…不揮発性メモリ、１４…入出力Ｉ／Ｆ、１５…ＣＰＵ、１６…乱数生成部、１７…演算部、Ｔ…除算テーブル。
【特許請求の範囲】
【請求項１】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置であって、
予め除数識別情報毎に除数が記憶された除数記憶手段と、
前記第１素数の候補ｐとして乱数を生成する乱数生成手段と、
前記第１素数の候補ｐに基づいて、前記第２素数の候補ｆ（ｐ）を算出する第２素数候補算出手段と、
前記各素数の候補ｐ，ｆ（ｐ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行手段と、
前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段と、
を備えたことを特徴とする素数生成装置。
【請求項２】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置であって、
予め除数識別情報毎に除数が記憶されており、試行割算結果の剰余が前記除数識別情報に関連付けて記憶される除数記憶手段と、
前記第１素数の候補ｐとして乱数を生成する乱数生成手段と、
前記第１素数の候補ｐに対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行手段と、
前記第１割算実行手段による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを前記除数記憶手段に書き込む剰余書込手段と、
前記剰余書込手段により書き込まれた剰余ｋに基づいて、前記多項式ｆ（ｋ）を計算する多項式計算手段と、
前記多項式ｆ（ｋ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第２割算実行手段と、
前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記第１素数の候補ｐ及び前記第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段と、
を備えたことを特徴とする素数生成装置。
【請求項３】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置のプログラムであって、
前記素数生成装置のコンピュータを、
予め除数識別情報毎に除数が記憶された除数記憶手段、
前記第１素数の候補ｐとして乱数を生成する乱数生成手段、
前記第１素数の候補ｐに基づいて、前記第２素数の候補ｆ（ｐ）を算出する第２素数候補算出手段、
前記各素数の候補ｐ，ｆ（ｐ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行手段、
前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段、
として機能させるためのプログラム。
【請求項４】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置のプログラムであって、
前記素数生成装置のコンピュータを、
予め除数識別情報毎に除数が記憶されており、試行割算結果の剰余が前記除数識別情報に関連付けて記憶される除数記憶手段、
前記第１素数の候補ｐとして乱数を生成する乱数生成手段、
前記第１素数の候補ｐに対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行手段、
前記第１割算実行手段による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを前記除数記憶手段に書き込む剰余書込手段、
前記剰余書込手段により書き込まれた剰余ｋに基づいて、前記多項式ｆ（ｋ）を計算する多項式計算手段、
前記多項式ｆ（ｋ）に対し、前記除数記憶手段内の除数により個別に試行割算を実行する第２割算実行手段、
前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記第１素数の候補ｐ及び前記第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段、
として機能させるためのプログラム。
【請求項５】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置が実行する素数生成方法であって、
予め除数識別情報毎に除数をメモリに記憶する除数記憶工程と、
前記第１素数の候補ｐとして乱数を生成する乱数生成工程と、
前記第１素数の候補ｐに基づいて、前記第２素数の候補ｆ（ｐ）を算出する第２素数候補算出工程と、
前記各素数の候補ｐ，ｆ（ｐ）に対し、前記メモリ内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行工程と、
前記メモリ内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定工程と、
を備えたことを特徴とする素数生成方法。
【請求項６】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置が実行する素数生成方法であって、
予め除数識別情報毎に除数をメモリに記憶する除数記憶工程と、
前記第１素数の候補ｐとして乱数を生成する乱数生成工程と、
前記第１素数の候補ｐに対し、前記メモリ内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行工程と、
前記第１割算実行工程による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを前記除数識別情報に関連付けて前記メモリに書き込む剰余書込工程と、
前記メモリに書き込まれた剰余ｋに基づいて、前記多項式ｆ（ｋ）を計算する多項式計算工程と、
前記多項式ｆ（ｋ）に対し、前記メモリ内の除数識別情報毎の除数により個別に試行割算を実行する第２割算実行工程と、
前記メモリ内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記第１素数の候補ｐ及び前記第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定工程と、
を備えたことを特徴とする素数生成方法。
【請求項１】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置であって、
予め除数識別情報毎に除数が記憶された除数記憶手段と、
前記第１素数の候補ｐとして乱数を生成する乱数生成手段と、
前記第１素数の候補ｐに基づいて、前記第２素数の候補ｆ（ｐ）を算出する第２素数候補算出手段と、
前記各素数の候補ｐ，ｆ（ｐ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行手段と、
前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段と、
を備えたことを特徴とする素数生成装置。
【請求項２】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置であって、
予め除数識別情報毎に除数が記憶されており、試行割算結果の剰余が前記除数識別情報に関連付けて記憶される除数記憶手段と、
前記第１素数の候補ｐとして乱数を生成する乱数生成手段と、
前記第１素数の候補ｐに対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行手段と、
前記第１割算実行手段による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを前記除数記憶手段に書き込む剰余書込手段と、
前記剰余書込手段により書き込まれた剰余ｋに基づいて、前記多項式ｆ（ｋ）を計算する多項式計算手段と、
前記多項式ｆ（ｋ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第２割算実行手段と、
前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記第１素数の候補ｐ及び前記第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段と、
を備えたことを特徴とする素数生成装置。
【請求項３】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置のプログラムであって、
前記素数生成装置のコンピュータを、
予め除数識別情報毎に除数が記憶された除数記憶手段、
前記第１素数の候補ｐとして乱数を生成する乱数生成手段、
前記第１素数の候補ｐに基づいて、前記第２素数の候補ｆ（ｐ）を算出する第２素数候補算出手段、
前記各素数の候補ｐ，ｆ（ｐ）に対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行手段、
前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段、
として機能させるためのプログラム。
【請求項４】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置のプログラムであって、
前記素数生成装置のコンピュータを、
予め除数識別情報毎に除数が記憶されており、試行割算結果の剰余が前記除数識別情報に関連付けて記憶される除数記憶手段、
前記第１素数の候補ｐとして乱数を生成する乱数生成手段、
前記第１素数の候補ｐに対し、前記除数記憶手段内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行手段、
前記第１割算実行手段による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを前記除数記憶手段に書き込む剰余書込手段、
前記剰余書込手段により書き込まれた剰余ｋに基づいて、前記多項式ｆ（ｋ）を計算する多項式計算手段、
前記多項式ｆ（ｋ）に対し、前記除数記憶手段内の除数により個別に試行割算を実行する第２割算実行手段、
前記除数記憶手段内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記第１素数の候補ｐ及び前記第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定手段、
として機能させるためのプログラム。
【請求項５】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置が実行する素数生成方法であって、
予め除数識別情報毎に除数をメモリに記憶する除数記憶工程と、
前記第１素数の候補ｐとして乱数を生成する乱数生成工程と、
前記第１素数の候補ｐに基づいて、前記第２素数の候補ｆ（ｐ）を算出する第２素数候補算出工程と、
前記各素数の候補ｐ，ｆ（ｐ）に対し、前記メモリ内の除数識別情報毎の除数により個別に試行割算を実行する試行割算実行工程と、
前記メモリ内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記各素数の候補ｐ，ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定工程と、
を備えたことを特徴とする素数生成方法。
【請求項６】
定数項が０ではない、整数係数の多項式ｆ（Ｘ）∈Ｚ［Ｘ］に対し（但し、Ｘは任意の整数、ＺはＸを要素とする集合）、第１素数ｐ（∈Ｚ）と、この第１素数ｐから算出可能な第２素数ｆ（ｐ）（∈Ｚ）とを生成する素数生成装置が実行する素数生成方法であって、
予め除数識別情報毎に除数をメモリに記憶する除数記憶工程と、
前記第１素数の候補ｐとして乱数を生成する乱数生成工程と、
前記第１素数の候補ｐに対し、前記メモリ内の除数識別情報毎の除数により個別に試行割算を実行する第１割算実行工程と、
前記第１割算実行工程による試行割算の結果が剰余ｋを持つとき、当該剰余ｋを前記除数識別情報に関連付けて前記メモリに書き込む剰余書込工程と、
前記メモリに書き込まれた剰余ｋに基づいて、前記多項式ｆ（ｋ）を計算する多項式計算工程と、
前記多項式ｆ（ｋ）に対し、前記メモリ内の除数識別情報毎の除数により個別に試行割算を実行する第２割算実行工程と、
前記メモリ内の全ての除数による全ての試行割算の結果が剰余を持つとき、前記第１素数の候補ｐ及び前記第２素数の候補ｆ（ｐ）に対し、フェルマーの小定理を含む素数判定法を実行する素数判定工程と、
を備えたことを特徴とする素数生成方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００７−２１８９９７（Ｐ２００７−２１８９９７Ａ）
【公開日】平成１９年８月３０日（２００７．８．３０）
【国際特許分類】
【出願番号】特願２００６−３６７７９（Ｐ２００６−３６７７９）
【出願日】平成１８年２月１４日（２００６．２．１４）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
【公開日】平成１９年８月３０日（２００７．８．３０）
【国際特許分類】
【出願日】平成１８年２月１４日（２００６．２．１４）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３０１０６３４９６）東芝ソリューション株式会社 (1,478)
【Ｆターム（参考）】
[ Back to top ]