(57)【特許請求の範囲】
【請求項１】
データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成方法において、
ｋを正の整数とし、ｍをｋ未満の正の整数とし、ｗを２m 未満の正の整数とし、ｋビットとｍビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｍビットの記憶領域に予め与えられた初期値を設定し、
周期がｗで値域が｛１，２，…，２m −１｝である数列を計算し、
外部から通信手段を介して素数生成の要求を受けた場合、ｍビットの記憶領域を入力値として前記数列における入力値の次の値を計算し、ｍビットの値を、ｋビットの記憶領域の所定の場所へコピーし、
ｋ−ｍビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、そのｋビットデータを通信手段を介して外部へ返却し、素数でなければ、再び乱数発生を行うことを特徴とする素数生成方法。
【請求項２】
ｎをｋ以下の正の整数とし、ｍ＋ｎ＜ｋを満たすものとし、ｋビットのｍビットとｎビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｎビットの記憶領域に予め与えられた初期値を設定し、
計算されたｎビットの値を、ｋビットの記憶領域の所定の場所にコピーし、
ｋ−ｍ−ｎビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍ−ｎビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、該ｋビットデータを通信部を介して外部へ返却し、素数でなければ再び乱数発生を行う請求項１記載の素数生成方法。
【請求項３】
データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成装置であって、
ｋを正の整数とし、ｍをｋ未満の正の整数とし、ｗを２m 未満の正の整数とし、ｋビットとｍビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｍビットの記憶領域に予め与えられた初期値を設定する初期値設定手段と、
周期がｗで値域が｛１，２，…，２m −１｝である数列を計算する計算手段と、
外部から通信手段を介して素数生成の要求を受けた場合、ｍビットの記憶領域を入力値として上記の数列における入力値の次の値を計算し、ｍビットの値を、ｋビットの記憶領域の所定の場所へコピーするコピー手段と、
ｋ−ｍビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、そのｋビットデータを通信手段を介して外部へ返却し、素数でなければ、再び乱数発生を行う乱数発生手段とを有することを特徴とする素数生成装置。
【請求項４】
データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成装置であって、
ｎをｋ以下の正の整数とし、ｍ＋ｎ＜ｋを満たすものとし、ｋビットのｍビットとｎビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｎビットの記憶領域に予め与えられた初期値を設定する初期値設定手段と、
計算されたｎビットの値を、ｋビットの記憶領域の所定の場所にコピーするコピー手段と、
ｋ−ｍ−ｎビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍ−ｎビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、該ｋビットデータを通信部を介して外部へ返却し、素数でなければ再び乱数発生を行う乱数発生手段とを有することを特徴とする素数生成装置。
【請求項５】
データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成プログラムを格納した記憶媒体であって、
ｋを正の整数とし、ｍをｋ未満の正の整数とし、ｗを２m 未満の正の整数とし、ｋビットとｍビットの長さを持つ記憶領域をそれぞれ用意する場合において、ｍビットの記憶領域に、予め与えられた初期値を設定する初期値設定プロセスと、
周期がｗで値域が｛１，２，…，２m −１｝である数列を計算する計算プロセスと、
外部から通信プロセスを介して素数生成の要求を受けた場合、ｍビットの記憶領域を入力値として上記の数列における入力値の次の値を計算し、ｍビットの値を、ｋビットの記憶領域の所定の場所へコピーするコピープロセスと、
ｋ−ｍビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、そのｋビットデータを通信プロセスを介して外部へ返却し、素数でなければ、再び乱数発生を行う乱数発生プロセスとを有することを特徴とする素数生成プログラムを格納した記憶媒体。
【請求項６】
データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成プログラムを格納した記憶媒体であって、
ｎをｋ以下の正の整数とし、ｍ＋ｎ＜ｋを満たすものとし、ｋビットのｍビットとｎビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｎビットの記憶領域に予め与えられた初期値を設定する初期値設定プロセスと、
計算されたｎビットの値を、ｋビットの記憶領域の所定の場所にコピーするコピープロセスと、
ｋ−ｍ−ｎビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍ−ｎビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、該ｋビットデータを通信部を介して外部へ返却し、素数でなければ再び乱数発生を行う乱数発生プロセスとを有することを特徴とする素数生成プログラムを格納した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、素数生成方法及び装置及び素数生成プログラムを格納した記憶媒体に係り、特に、暗号技術で用いられる素数生成方法及び装置及び素数生成プログラムを格納した記憶媒体に関する。
【０００２】
【従来の技術】
データを秘匿するためには暗号化技術が有効である。データの暗号化には、共通鍵暗号と公開鍵暗号がある。公開鍵暗号ではデータを暗号化する鍵と復号化する鍵が異なっており、通常は暗号化に用いる鍵を一般に公開し、復号化に用いる鍵は利用者が秘密に保持する。公開される暗号化に用いる鍵から復号化に用いる鍵を求めることは、現在の数学的理論及び計算機の計算能力をもってしても現実的な時間には完了しないものと信じられている。
【０００３】
上記性質をもつ公開鍵暗号の具体的な実現にはいくつか方法があるが、最も有名な方法として、ＲＳＡ暗号がある。ＲＳＡ暗号は初めて公開鍵暗号として１９７７年に発表されたもので、素因数分解の困難性を安全性の根拠にしている（岡本、山本、「現代暗号」、産業図書、p.110 ，1997を参照）。素因数分解の困難性とは、素数ｐとｑがあった場合、乗算ｎ＝ｑｐを行うことは簡単であるが、逆にｎからｐとｑを求めることは難しいことをいう。ｎの桁数が大きくなるにつれて必要な計算時間は増大し、例えば、６４桁と６５桁の素数の乗算結果である１２９桁の数を素因数分解するために、１９９４年に６００台の計算機を８カ月用いたことが報告されている（岡本、太田編、「暗号・ゼロ知識証明・数論」、共立出版、p.150, 1995 を参照）。他には、離散対数の問題の困難性に基づく公開鍵暗号も提案されているが、扱いが簡単であることから素因数分解の困難性に基づく公開鍵暗号が最も利用されており、その中でもＲＳＡ暗号が最も多く利用されている。
【０００４】
ＲＳＡ暗号は、上述の通り素因数分解の安全性に根拠をおいているために、もしｎの素因数分解に成功したならば、そのｎを用いた暗号文が第三者によって解読されてしまう。従って、ｎの素因数分解が困難であるようにしなければならない。既存の素因数分解法のうち、ＲＳＡ暗号を破るために用いられる可能性のある方法は、その多くが素因数のビットサイズに比例して処理時間がかかる。そのため、ｎが１０２４ビットであったとしても、ｐが２４ビットでｑが１０００ビットであったとするならば、ｐのサイズが小さいために素因数分解される可能性が高い。よって、ｎのサイズが１０２４ビットであれば、ｐとｑはそれぞれ５１２ビット程度にしておくことが推奨される。
【０００５】
一般に、ｐ，ｑを素数としてｎ＝ｐｑのビットサイズをｌ（エル）として「ｌ（エル）ビットＲＳＡ暗号」と呼ばれる。現在商用目的には、１０２４ビットが推奨され、軍事目的などさらに高度な安全性が必要な場面では、２０４８ビットが推奨されている。従って、素数としては、５１２ビットや１０２４ビットの長さを持たせることが求められる。
【０００６】
素数を生成するためには、まず、乱数を発生させ、必要なビットサイズを持つ奇数を取得し、その値が素数であるかどうかを検査する。もし、素数判定に失敗すれば、別の奇数を再び乱数によって発生させ、検査を続ける。
素数判定にはいくつか方法があり、例えば、Rabin 法がある（Rabin, M.O.,"Probabilistic Algorithm for Testing Primality," J.Number Theory 12, pp.128-138, 1980 を参照）。
【０００７】
また、素数は、無限に存在することが素数定理によって保証されており、判定に失敗したときの次の候補を適切に選択すれば有限回で処理は終了する（素数定理については「数学セミナーリーティングス、数の世界、日本評論社、p.97,1982 」を参照）。ここで、乱数の発生には、多くの場合決定論的な方法が用いられる。即ち、乱数系列の初期値を設定し、その値とある関数ｆを用いて系列｛ｒn ｝を生成する。
【０００８】
【発明が解決しようとする課題】
しかしながら、上記のような方法で素数を生成し、暗号鍵を作成する場合、次のような問題がある。
即ち、あるネットワークシステムにおいて大量に暗号鍵を作成しなければならない場合、その暗号鍵の一意性の保証が必要となる。もし同じ素数が生成された場合、その過程で用いられた乱数が同じである可能性があり、また、乱数生成が決定論的であればその後に生成される素数も同じである可能性があるため、結果としてＲＳＡ暗号鍵が同じになることが考えられる。このような事態において、鍵が暗号処理に利用された場合には他人に暗号文を復号される危険があること、また、署名処理に利用された場合には他人へのなりすましが結果として可能となる。特に、署名鍵がシステム内部で重複すると、本人性確認の手段として暗号処理を用いたとしても、その信頼性が満足されない。電子商取引などを行うには確実な本人性確認が必要とされ、即ち、鍵の重複を避けることがシステムに求められる。
【０００９】
本発明は、上記の点に鑑みなされたもので、大量に生成される素数の一意性を保証し、かつそのためのメモリ使用量を低減させることが可能な素数生成方法及び装置及び素数生成プログラムを格納した記憶媒体を提供することを目的とする。
【００１０】
【課題を解決するための手段】
図１は、本発明の原理を説明するための図である。
本発明（請求項１）は、データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成方法において、
ｋを正の整数とし、ｍをｋ未満の正の整数とし、ｗを２m 未満の正の整数とし、ｋビットとｍビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｍビットの記憶領域に予め与えられた初期値を設定し（ステップ１）、
周期がｗで値域が｛１，２，…，２m −１｝である数列を計算し（ステップ２）、
外部から通信手段を介して素数生成の要求を受けた場合（ステップ３）、ｍビットの記憶領域を入力値として数列における入力値の次の値を計算し（ステップ４）、ｍビットの値を、ｋビットの記憶領域の所定の場所へコピーし（ステップ５）、
ｋ−ｍビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍビットにコピーし（ステップ６）、ｋビットの整数とみなして素数判定を行い（ステップ７）、素数であれば、そのｋビットデータを通信手段を介して外部へ返却し（ステップ８）、素数でなければ、再び乱数発生を行う（ステップ６）。
【００１１】
本発明（請求項２）は、ｎをｋ以下の正の整数とし、ｍ＋ｎ＜ｋを満たすものとし、ｋビットのｍビットとｎビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｎビットの記憶領域に予め与えられた初期値を設定し、
計算されたｎビットの値を、ｋビットの記憶領域の所定の場所にコピーし、
ｋ−ｍ−ｎビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍ−ｎビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、該ｋビットデータを通信部を介して外部へ返却し、素数でなければ再び乱数発生を行う処理を繰り返す。
【００１２】
図２は、本発明の原理構成図である。
本発明（請求項３）は、データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成装置であって、
ｋを正の整数とし、ｍをｋ未満の正の整数とし、ｗを２m 未満の正の整数とし、ｋビットとｍビットの長さを持つ記憶領域１1 、１2 をそれぞれ用意する場合において、
ｍビットの記憶領域１2 に予め与えられた初期値を設定する初期値設定手段２と、
周期がｗで、値域が｛１，２，…，２m −１｝である数列を計算する計算手段３と、
外部から通信手段を介して素数生成の要求を受けた場合、ｍビットの記憶領域を入力値として上記の数列における入力値の次の値を計算し、ｍビットの値を、ｋビットの記憶領域１1 の所定の場所へコピーするコピー手段４と、
ｋ−ｍビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、そのｋビットデータを通信手段を介して外部へ返却し、素数でなければ、再び乱数発生を行う乱数発生手段５とを有する。
【００１３】
本発明（請求項４）は、データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成装置であって、
ｎをｋ以下の正の整数とし、ｍ＋ｎ＜ｋを満たすものとし、ｋビットのｍビットとｎビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｎビットの記憶領域に予め与えられた初期値を設定する初期値設定手段と、
計算されたｎビットの値を、ｋビットの記憶領域の所定の場所にコピーするコピー手段と、
ｋ−ｍ−ｎビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍ−ｎビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、該ｋビットデータを通信部を介して外部へ返却し、素数でなければ再び乱数発生を行う乱数発生手段とを有する。
【００１４】
本発明（請求項５）は、データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成プログラムを格納した記憶媒体であって、
ｋを正の整数とし、ｍをｋ未満の正の整数とし、ｗを２m 未満の正の整数とし、ｋビットとｍビットの長さを持つ記憶領域をそれぞれ用意する場合において、ｍビットの記憶領域に予め与えられた初期値を設定する初期値設定プロセスと、
周期がｗで値域が｛１，２，…，２m −１｝である数列を計算する計算プロセスと、
外部から通信プロセスを介して素数生成の要求を受けた場合、ｍビットの記憶領域を入力値として上記の数列における入力値の次の値を計算し、ｍビットの値を、ｋビットの記憶領域の所定の場所へコピーするコピープロセスと、
ｋ−ｍビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、そのｋビットデータを通信プロセスを介して外部へ返却し、素数でなければ、再び乱数発生を行う乱数発生プロセスとを有する。
【００１５】
本発明（請求項６）は、データを秘匿化するための暗号技術で用いられる素数を生成するための素数生成プログラムを格納した記憶媒体であって、
ｎをｋ以下の正の整数とし、ｍ＋ｎ＜ｋを満たすものとし、ｋビットのｍビットとｎビットの長さを持つ記憶領域をそれぞれ用意する場合において、
ｎビットの記憶領域に予め与えられた初期値を設定する初期値設定プロセスと、
計算されたｎビットの値を、ｋビットの記憶領域の所定の場所にコピーするコピープロセスと、
ｋ−ｍ−ｎビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍ−ｎビットにコピーし、ｋビットの整数とみなして素数判定を行い、素数であれば、該ｋビットデータを通信部を介して外部へ返却し、素数でなければ再び乱数発生を行う乱数発生プロセスとを有する。
【００１６】
上記のように、数列｛ｓi ｝としてｍビットの数列を用いた場合、個々の値としては、０から２m −１までの２m 通りが考えられる。この数列の周期をｗとする。このとき、初期値ｓ1 を用いて生成した数列は、ｉ番目の値をｓi とおくと、ｓw までの値は全て異なる値である。各ｓi を素数の一部として考慮することにより、この装置が返却する値に重複がないことが最初のｗ個について保証できる。
【００１７】
次に、記憶容量については、この数列は、直前の値ｓi-1 を用いれば、次の値ｓi が得られる。従って、直前の数列の値ｓi-1 を記憶しておけばよい。よって、素数生成の個数にかかわらず、記憶領域としてはｍビットで充分である。
一般に一意性を確保するためには、以前に生成された素数や、素数から生成される暗号鍵を記憶装置に保持しておき、過去に生成したものと比較させることにより、一意性の判断を行うことができるが、記憶する数が多くなるに従い、記憶装置の増大化、検索時間の増大化を招くが、本発明によれば、周期が非常に長く、かつ、直前の値から次の値を求めることができる数列の値を素数の一部とすることによって、過去に生成した素数を記憶することなく、一意性を確保し、記憶装置や、生成時間の増大を防ぐことが可能となる。
【００１８】
【発明の実施の形態】
図３は、本発明の素数生成装置の構成を示す。
同図に示す素数生成装置は、制御部１０、データ記憶部２０、通信部３０、５０、算術演算部４０から構成される。
同図において、点線枠は、制御部１０において本発明の処理における各処理部のコントロールを行う範囲である。
【００１９】
算術演算部４０は、乱数の発生、ＬＦＳＲの計算、素数判定を行うRabin 法の計算処理を行う。
算術演算部４０で行う数列の生成には、線形フィードバックシフトレジスタ（以下、ＬＦＳＲ）を用いる。ＬＦＳＲは、数列を生成するアルゴリズムであり、数列における直前の値を入力として次の値を出力する。また、ｍビットの数を入出力するＬＦＳＲは、１から２m −１までの値を出力し、その周期は、２m −１となる。なお、ＬＦＳＲの構造については、「Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, p.372, 1996 」に示されている。
【００２０】
データ記憶部２０には、予めＬＦＳＲの直前の出力値あるいは初期値であるｓi-1 が格納され、処理終了時には、出力データｓi を格納する。
上記の構成における算術演算部４０は、図２における初期値設定手段２、計算手段３、コピー手段４、乱数発生手段５の各手段を含む。当該算術演算部４０では、ｋを正の整数とし、ｍをｋ未満の正の整数とし、ｗを２m 未満の正の整数とし、ｕを０以上の整数とし、ｖを０以上の整数とし、ｕ＋ｖ＝ｋ−ｍを満たすものとする。ｍビットの数ｓ1 を数列の初期値とし、システムを最初に起動する際に、初期値ｓ1 を設定しておく。また、数列のそれぞれの値は、ｍビットの長さとする。
【００２１】
算術演算部４０が素数生成の要求を通信部３０を介して取得すると、まず、直前の数列の値ｓi-1 から次の値であるｍビットの数ｓi を得る。次に、ｕビットの乱数ｒu とｖビットの乱数ｒv を生成する。そして、ｋビットの数として、
Ｒ＝ｒu ２m+v ＋ｓi ２v ＋ｒv 
とする。右辺のそれぞれの値は、ｕ，ｍ，ｖビットであることと、
ｕ＋ｖ＋ｍ＝ｋ
とする。
【００２２】
最後に、Ｒが素数であるか否かをRabin 法を用いて検証する。もし、Ｒが合成数である場合には、乱数ｒv の生成、あるいは、乱数ｒu の生成に戻って上記の処理を再度行う。但し、ｓi の再生成は行わない。Ｒが素数であるならば、この値を通信部５０を介して外部に返却する。
【００２３】
【実施例】
以下、図面と共に本発明の実施例を説明する。
図４は、本発明の一実施例のｋビット素数の内部構成を示し、図５は、本発明の一実施例のｋビット素数の内部構成（固有の値を含む）を示す。
図４では、ＬＦＳＲの出力値を乱数の一部に埋め込んだ場合の構成を示している。一般に、ｋビットの素数を生成する場合には、真にｋビットの長さを持つ値、即ち最上位ビットに１が立っている値を求められる。従って、図４、図５では、それぞれ最上位ビットに１を置いている。
【００２４】
ＬＦＳＲの出力値を、素数Ｒのどの部分に埋め込むかについては、特に制限はない。また、一つの纏まった部分として埋め込むのではなく、いくつかの部分に分解してＲの中に埋め込んでもよい。但し、最下位ビット付近には、図中のｖビット文の乱数部（ｒv ）が示すように一つのまとまった部分として乱数成分を埋め込む形を採った方が確実な素数生成として推奨される。即ち、素数定理によると、例えば、５１２ビットの場合、素数である確率は約５００分の１であって、ｖを比較的多く採ってある値ｒ0 v を中心として、ｒ0 v ±Ｍの範囲を探索すれば（ここでＭは、ある正の整数）、その検索範囲中に素数が入る確率が結果として大きくなるからである。
【００２５】
図５では、ＬＦＳＲの出力だけでなく、固有の値もＲの中に埋め込まれている。これは、素数及び素数から構成される暗号鍵を生成するサーバが、あるネットワークシステム内に複数台存在し、かつシステムとして素数や暗号鍵の一意性を保証しなければならない場合に有効である。固有の値としては、例えば、サーバの製造ＩＤなどを割り当てればよい。この場合も、上記のように、固有の値を一つのまとまった部分として埋め込むのではなく、いくつかの部分に分解してＲの中に埋め込んでもよい。
【００２６】
例として、ｋ＝５１２，ｍ＝６４，ｎ＝３２，ｖ＝３５２とし、ＬＦＳＲは、６４ビットの入出力を行うものとする。これにより、まず、固有の値として
【００２７】
【数１】
0003711821.tif 000002
【００２８】
を入れることができる。このフィールドには、例えば、サーバの製造ＩＤなどを入れることが可能となる。また、ＬＦＳＲの出力ビットはｍ＝６４ビットとなる。従って、
【００２９】
【数２】
0003711821.tif 000003
【００３０】
個の異なる素数を生成することが保証できる。
システム起動時に、初期値ｓ1 を定めて指定しておく。素数生成の要求があると、まず、ＬＦＳＲを用いて直前の出力値ｓi-1 から新しい出力値ｓi を得る。これをデータ記憶部２０にて記憶しておくと同時に、ｓi をＲの然るべき位置に複写する。また、３２ビットの固有の値を、同じＲの然るべき位置へ複写しておく。
【００３１】
残ったｕビット分の領域とｖビット分の領域に対し、それぞれｕビットとｖビットの乱数（ｒu ，ｒv ）を生成して然るべき位置に複写する。ここでは、図５にあるように、ｒv を複写する領域は一つの纏まった部分としてＲの最下位を含んだ領域であるとする。但し、これらの過程において、Ｒの最上位ビットは１が立つようにしておく。また、２を除いて素数は奇数であるから、同様に最下位ビットも１が立つようにしておく。
【００３２】
従って、ｖビット分の領域に複写される乱数ｒv の最下位ビットは、常に１が立っているものと仮定してよい。
こうして得られたＲに対して、Rabin 法を用いて素数検査を行う。合成数と判断された場合には、ｒv に２を足す、あるいは、２を減じて隣の奇数を表すようにして再びｖビット分の領域に複写し、得られたＲに対して、Rabin 法による素数判定を行うことを繰り返す。ここで、Ｒそのものに２を足したり、２を減じたりすると、繰り上がりあるいは、繰り下がりによってｍビット分の領域やｎビット分の領域に影響を及ぼす可能性があるため、ここでの操作はｖビット分の領域に限定するべきである。また、このような操作を行った結果、ｒv がｖビットを超えたり、負の値になった場合には、２v を減じる、あるいは、２v を足すなどの操作を行って１から２v −１の範囲内に値を保持しておく。素数検査に合格した場合には、Ｒを返却する。
【００３３】
また、本発明では、算術演算部４０の動作を図１のフローチャートに示すように、ｋビット、ｍビットの記憶領域に初期値を設定するプロセス、周期がｗで値域が｛１，２，…，２m −１｝である数列を計算するプロセス、素数生成要求時に、ｍビットの記憶領域を入力値として計算された数列における入力値の次の値を計算して、ｍビットの記憶領域へ格納するプロセス、計算されたｍビットの値を、ｋビットの記憶領域へコピーするプロセス、ｋ−ｍビットの乱数を発生させ、ｋビットの記憶領域のうち、残ったｋ−ｍビットの領域にコピーするプロセス、素数判定の結果、素数である場合には、ｋビットデータを素数として外部に出力するプロセス、素数でない場合には再度乱数を発生させるプロセスからなるプログラムを構築する。さらに、当該プログラムを素数生成装置として利用されるコンピュータに接続されるディスク装置や、フロッピーディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、本発明を実施する際にインストールすることにより、容易に本発明を実現することができる。
【００３４】
なお、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【００３５】
【発明の効果】
上述のように、本発明によれば、主に暗号技術で用いられる素数生成処理において、生成された素数の一意性を容易に保証しつつ、使用記憶領域を削減することができる。
【図面の簡単な説明】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の素数生成装置の構成図である。
【図４】本発明の一実施例のｋビット素数の内部構造を示す。
【図５】本発明の一実施例のｋビット素数の内部構造（固有の値を含む）を示す。
【符号の説明】
１  記憶領域
１1   ｋビット記憶領域
１2   ｍビット記憶領域
２  初期値設定手段
３  計算手段
４  コピー手段
５  乱数発生手段
１０  制御部
２０  データ記憶部
３０、５０    通信部
４０  算術演算部
【図１】
0003711821.tif 000004
【図２】
0003711821.tif 000005
【図３】
0003711821.tif 000006
【図４】
0003711821.tif 000007
【図５】
0003711821.tif 000008