JPH10207363A

JPH10207363A - 素数生成装置及び方法

Info

Publication number: JPH10207363A
Application number: JP1396397A
Authority: JP
Inventors: Koichi Sakurai; 幸一櫻井; Yasuyuki Sakai; 康行酒井; Yuichi Ishizuka; 裕一石塚
Original assignee: Mitsubishi Electric Corp
Current assignee: Mitsubishi Electric Corp
Priority date: 1997-01-28
Filing date: 1997-01-28
Publication date: 1998-08-07

Abstract

(57)【要約】【課題】Ｐ−１素因数分解法にもＰ＋１素因数分解法
にも強い素数を生成する素数生成装置及び方法を得るこ
とを課題とする。【解決手段】素数ｒ記憶手段２に記憶された素数ｒを
用いて所定の演算を行い、Ｐ−１素因数分解法に強い素
数Ｐを生成する素数Ｐ生成手段３と、この素数Ｐ生成手
段３により生成された素数Ｐを記憶する素数Ｐ記憶手段
４と、この素数Ｐ記憶手段４に記憶された素数Ｐを取り
出し、この素数ＰがＰ＋１素因数分解法に強いか否かを
判定する判定手段５と、この判定手段５によりＰ＋１素
因数分解法に強いと判定された素数Ｐを出力する出力手
段６とを備えたものである。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、Ｐ−１素因数分解
法にもＰ＋１素因数分解法にも強い素数を生成する素数
生成装置及び方法に関するものであり、本発明の素数生
成装置及び方法は、例えば公開鍵暗号の鍵を生成するた
めに利用することができる。

【０００２】

【従来の技術】従来の素数生成方法について説明する。
従来の素数生成方法には、暗号化電子メールソフトウエ
アであるＰＧＰ（ＰｒｅｔｔｙＧｏｏｄＰｒｉｖａ
ｃｙ）で用いられている素数生成方法がある。ＰＧＰ
は、公開鍵暗号としてＲＳＡを、秘密鍵暗号としてＩＤ
ＥＡを用い、電子メールを暗号化して送るソフトウエア
であり、ＰＧＰの全ソースプログラムは、PhiLip R. Zi
mmermann著“PGP Source Code and Internals”（The M
IT Press、１９９５年発行）に記載されている。ＰＧＰ
では、生成した素数をＲＳＡ暗号の鍵を生成するために
使用している。

【０００３】図３は、ＰＧＰで用いられている素数生成
方法のフローチャートである。図において、ステップＳ
２０１は素数生成の開始、ステップＳ２０２は素数ｒを
生成する処理、ステップＳ２０３は変数ｉを１に初期化
する処理、ステップＳ２０４は目的の素数Ｐの候補をＰ
＝２ｉｒ＋１として計算する処理、ステップＳ２０５は
ステップＳ２０４において計算されたＰが素数であるか
否を判定する処理、ステップＳ２０６はステップＳ２０
５においてＰが素数でないと判定された場合にｉ＝ｉ＋
１とする処理、ステップＳ２０７はステップＳ２０６に
おいて計算されたｉが１００００を超えているか否かを
判定する処理、ステップＳ２０８は素数Ｐを出力する処
理、ステップＳ２０９は処理の終了である。

【０００４】次に図３のフローチャートに基づいて、動
作を詳細に説明する。生成する素数Ｐは２５６ビットの
場合を説明する。まずステップＳ２０２において、約２
５６ビットの素数ｒを生成する。素数ｒの生成方法は、
例えば、まず素数ｒの候補として約２５６ビットの乱数
を生成し、生成された乱数をラビン法などの素数判定法
により素数であるか否かを判定する。生成された乱数が
素数であると判定されればステップＳ２０２の処理は終
了し、素数でないと判定されれば再び素数ｒの候補とし
て乱数を生成する。

【０００５】次に、ステップＳ２０３において、変数ｉ
を１に初期化し、ステップＳ２０４において、素数ｒと
変数ｉをもとにＰ＝２ｉｒ＋１を計算する。ステップＳ
２０４において計算されたＰを、ステップＳ２０５にお
いて素数であるか否かを判定する。Ｐが素数であると判
定されれば、ステップＳ２０８で素数Ｐを出力し、ステ
ップＳ２０９で処理を終了する。Ｐが素数でないと判定
されれば、ステップＳ２０６の処理へ進み、ステップＳ
２０６において変数ｉの値に１を加算する。ステップＳ
２０７では、ステップＳ２０６において計算された変数
ｉの値が１００００を超えているか否かを判定する。こ
の判定の目的は、生成したい素数Ｐは２５６ビットであ
り、またＰはＰ＝２ｉｒ＋１としているため、変数ｉが
大きすぎると、素数Ｐが２５６ビットを超えてしまうか
らである。ＰＧＰでは、変数ｉの上限値は１００００と
なっている。ステップＳ２０７において変数ｉが１００
００を超えていないと判定された場合は、ステップＳ２
０４において再びＰ＝２ｉｒ＋１を計算する。ステップ
Ｓ２０７において変数ｉが１００００を超えていると判
定された場合は、ステップＳ２０２において再び素数ｒ
を生成する。

【０００６】以上のような素数生成方法で生成された２
５６ビットの素数Ｐは、Ｐ−１の素因数に、素数Ｐとほ
ぼ同じビット数の素数ｒを有することが保証される。即
ち、生成された素数Ｐは、Ｐ−１素因数分解法に強いと
いう特徴を有する。Ｐ−１素因数分解法は、Ｐ−１の因
数が小さい素数ばかりで構成されている場合に有効な素
因数分解法で、公知の方法であり、例えば和田秀男著、
「コンピュータと素因子分解」（遊星社、１９８７年１
０月２０日発行、７７〜９４頁）に詳しく記載されてい
る。

【０００７】

【発明が解決しようとする課題】従来の素数生成方法
は、上述のように構成されているため、Ｐ−１素因数分
解法に強い素数を生成した場合、Ｐ＋１素因数分解法に
対する対策は施されておらず、生成された素数Ｐは、Ｐ
＋１素因数分解法には弱いことがあり、素因数分解され
やすいという問題点があった。また、従来の素数生成方
法は、Ｐ−１素因数分解法とＰ＋１素因数分解法の両方
に対して強い素数を生成できないという問題点があっ
た。さらに、従来の素数生成方法は、素因数分解に対す
る強さを目的に応じて可変にできないという問題点があ
った。

【０００８】本発明は、係る問題点を解決するためにな
されたもので、Ｐ−１素因数分解法にもＰ＋１素因数分
解法にも強い素数を生成する素数生成装置及び方法を得
ることを目的とする。さらに、本発明は、素数Ｐの素因
数分解に対する強さを目的に応じて可変にできる素数生
成装置及び方法を得ることを目的とする。

【０００９】

【課題を解決するための手段】本発明の請求項１に係る
素数生成装置は、第１の素数を記憶する第１の記憶手段
と、この第１の記憶手段に記憶された前記第１の素数を
用いて所定の演算を行い、Ｐ−１素因数分解法に強い第
２の素数を生成する生成手段と、この生成手段により生
成された前記第２の素数を記憶する第２の記憶手段と、
この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ＋１素因数分解法に強いか否
かを判定する判定手段と、この判定手段によりＰ＋１素
因数分解法に強いと判定された前記第２の素数を出力す
る出力手段とを備えたものである。

【００１０】本発明の請求項２に係る素数生成装置は、
第１の素数を記憶する第１の記憶手段と、この第１の記
憶手段に記憶された前記第１の素数を用いて所定の演算
を行い、Ｐ＋１素因数分解法に強い第２の素数を生成す
る生成手段と、この生成手段により生成された前記第２
の素数を記憶する第２の記憶手段と、この第２の記憶手
段に記憶された前記第２の素数を取り出し、この第２の
素数がＰ−１素因数分解法に強いか否かを判定する判定
手段と、この判定手段によりＰ−１素因数分解法に強い
と判定された前記第２の素数を出力する出力手段とを備
えたものである。

【００１１】本発明の請求項３に係る素数生成装置は、
素因数分解を行ないその結果に基づいて判定する判定手
段を備えたものである。

【００１２】本発明の請求項４に係る素数生成装置は、
計算回数を入力する回数入力手段を備え、前記判定手段
は、前記回数入力手段により入力された前記計算回数の
素因数分解を行ないその結果に基づいて判定するもので
ある。

【００１３】本発明の請求項５に係る素数生成方法は、
第１の記憶手段に記憶された第１の素数を用いて所定の
演算を行い、Ｐ−１素因数分解法に強い第２の素数を生
成し、第２の記憶手段に記憶させる生成ステップと、こ
の第２の記憶手段に記憶された前記第２の素数を取り出
し、この第２の素数がＰ＋１素因数分解法に強いか否か
を判定する判定ステップと、この判定ステップによりＰ
＋１素因数分解法に強いと判定された前記第２の素数を
出力する出力ステップとを備えたものである。

【００１４】本発明の請求項６に係る素数生成方法は、
第１の記憶手段に記憶された第１の素数を用いて所定の
演算を行い、Ｐ＋１素因数分解法に強い第２の素数を生
成し、第２の記憶手段に記憶させる生成ステップと、こ
の第２の記憶手段に記憶された前記第２の素数を取り出
し、この第２の素数がＰ−１素因数分解法に強いか否か
を判定する判定ステップと、この判定ステップによりＰ
−１素因数分解法に強いと判定された前記第２の素数を
出力する出力ステップとを備えたものである。

【００１５】本発明の請求項７に係る素数生成方法は、
素因数分解を行ないその結果に基づいて判定する判定ス
テップを備えたものである。

【００１６】本発明の請求項８に係る素数生成方法は、
計算回数を入力する回数入力ステップを備え、前記判定
ステップは、前記回数入力ステップにより入力された前
記計算回数の素因数分解を行ないその結果に基づいて判
定するものである。

【００１７】

【発明の実施の形態】

実施の形態１．本発明の素数生成装置の一実施の形態を
図に基づいて説明する。図１は実施の形態１の素数生成
装置の構成を示す構成図である。図において、１は第１
の素数である素数ｒを生成する素数ｒ生成手段、２は素
数ｒ生成手段１により生成された素数ｒを記憶する素数
ｒ記憶手段、３は素数ｒ記憶手段２に記憶された素数ｒ
を用いて演算を行い、第２の素数である素数Ｐを生成す
る素数Ｐ生成手段、４は素数Ｐ生成手段３により生成さ
れた素数Ｐを記憶する素数Ｐ記憶手段、５は素数Ｐ記憶
手段４に記憶された素数ＰがＰ＋１素因数分解法に強い
か否かを判定する判定手段、６は判定手段５によりＰ＋
１素因数分解法に強いと判定された素数Ｐを出力する出
力手段、７は素数ｒ生成手段１、素数Ｐ生成手段３、判
定手段５及び出力手段６を備えたコンピュータ、８は素
数ｒ記憶手段２及び素数Ｐ記憶手段４を備えたメモリで
ある。

【００１８】図２は図１に示した素数生成装置の動作を
示すフローチャートである。図において、ステップＳ１
０１は素数生成の開始、ステップＳ１０２は素数ｒを生
成する処理、ステップＳ１０３は変数ｉを１に初期化す
る処理、ステップＳ１０４は目的の素数Ｐの候補をＰ＝
２ｉｒ＋１として計算する処理、ステップＳ１０５はス
テップＳ１０４において計算されたＰが素数であるか否
を判定する処理、ステップＳ１０６はステップＳ１０５
においてＰが素数でないと判定された場合にｉ＝ｉ＋１
とする処理、ステップＳ１０７はステップＳ１０６にお
いて計算されたｉが所定の値、例えば１００００を超え
ているか否かを判定する処理、ステップＳ１０８はステ
ップＳ１０５においてＰが素数であると判定された場合
に、ＰがＰ＋１素因数分解法に強いか否かを判定する処
理、ステップＳ１０９はステップＳ１０８でＰ＋１素因
数分解法に強いと判定された素数Ｐを出力する処理、ス
テップＳ１１０は処理の終了である。ここで、ステップ
Ｓ１０２は素数ｒ生成手段１による処理であり、ステッ
プＳ１０３〜Ｓ１０７は素数Ｐ生成手段３による処理で
あり、ステップＳ１０８は判定手段５による処理であ
り、ステップＳ１０９は出力手段６による処理である。

【００１９】次に図２のフローチャートに基づいて動作
を詳細に説明する。本実施の形態では、生成する素数Ｐ
は２５６ビットの場合を説明する。まずステップＳ１０
２において、約２５６ビットの素数ｒを生成し、素数ｒ
記憶手段２に記憶させる。素数ｒの生成方法は、例え
ば、まず素数ｒの候補として約２５６ビットの乱数を生
成し、生成された乱数をラビン法などの素数判定法によ
り素数であるか否かを判定する。生成された乱数が素数
であると判定されればステップＳ１０２の処理は終了
し、素数でないと判定されれば再び素数ｒの候補として
乱数を生成する。

【００２０】次に、ステップＳ１０３において、変数ｉ
を１に初期化し、ステップＳ１０４において、素数ｒ記
憶手段２に記憶された素数ｒを取り出し、この取り出し
た素数ｒと変数ｉをもとにＰ＝２ｉｒ＋１を計算する。
求めたＰは素数Ｐ記憶手段４に記憶させる。ステップＳ
１０４において計算されたＰを素数Ｐ記憶手段４より取
り出し、ステップＳ１０５において素数であるか否かを
判定する。Ｐが素数であると判定されれば、ステップＳ
１０８の処理へ進む。

【００２１】Ｐが素数でないと判定されれば、ステップ
Ｓ１０６の処理へ進み、ステップＳ１０６において変数
ｉの値に１を加算する。ステップＳ１０７では、ステッ
プＳ１０６において計算された変数ｉの値が、所定の値
を超えているか否かを判定する。この判定の目的は、生
成したい素数Ｐが２５６ビットであり、またＰはＰ＝２
ｉｒ＋１としているため、変数ｉが大きすぎると、素数
Ｐが２５６ビットを超えてしまうからである。この実施
の形態では、変数ｉの上限値は１００００とした。ステ
ップＳ１０７において変数ｉが所定の値を超えていない
と判定された場合、ステップＳ１０４において再び、素
数ｒ記憶手段２に記憶された素数ｒを取り出し、この取
り出した素数ｒと変数ｉをもとにＰ＝２ｉｒ＋１を計算
する。求めたＰは再び素数Ｐ記憶手段４に記憶させる。
ステップＳ１０７において変数ｉが所定の値を超えてい
ると判定された場合、ステップＳ１０２において再び素
数ｒを生成する。

【００２２】ステップＳ１０５までの処理で生成された
２５６ビットの素数Ｐは、Ｐ−１の素因数として、素数
Ｐとほぼ同じビット数の素数ｒを有することが保証され
る。即ち、生成された素数Ｐは、Ｐ−１素因数分解法に
強いという特徴を有する。

【００２３】次にステップＳ１０８において、ステップ
Ｓ１０４で生成された素数Ｐを素数Ｐ記憶手段４より取
り出し、この取り出した素数Ｐが、Ｐ＋１素因数分解法
に強いか否かを判定する。この判定は、Ｐ＋１の素因数
に、大きな数の素因数が含まれているか否かを調べるこ
とにより行う。Ｐ＋１に大きな素因数が含まれていれ
ば、素数ＰはＰ＋１素因数分解法に強いことになり、Ｐ
＋１が小さな素因数のみで構成されていれば、Ｐ＋１素
因数分解法には弱いことになる。Ｐ＋１素因数分解法
は、Ｐ＋１が小さい素因数のみで構成されている場合に
有効な素因数分解法で、公知の方法であり、例えば前述
の文献「コンピュータと素因子分解」に詳しく記載され
ている。ステップＳ１０８において、素数ＰがＰ＋１素
因数分解法に弱いと判定された場合は、ステップＳ１０
２において再び素数ｒを生成する。素数ＰがＰ＋１素因
数分解法に強いと判定された場合は、ステップＳ１０９
において、素数Ｐ記憶手段４に記憶された素数Ｐを出力
し、ステップＳ１１０で処理を終了する。

【００２４】以上のような方法で生成された素数Ｐは、
Ｐ−１素因数分解法にもＰ＋１素因数分解法にも強く、
素因数分解されにくいという特徴を有する。そして、本
実施の形態で生成された素数Ｐをもとに、公開鍵暗号の
鍵を生成すれば、素因数分解されにくい安全な鍵を生成
することができる。

【００２５】本実施の形態では、生成する素数Ｐは２５
６ビットとしたが、例えば５１２、７６８、１０２４な
どの他のビット数の素数でも同様な方法で生成できる。

【００２６】実施の形態２．この実施の形態では、図２
に示したステップＳ１０８の、素数ＰがＰ＋１素因数分
解法に強いか否かを判定する処理として、Ｐ＋１を実際
に素因数分解することにより判定する場合について説明
する。ステップＳ１０８において生成された素数Ｐに対
して、Ｐ＋１を素因数分解すれば、Ｐ＋１の素因数の大
きさを知ることができる。そして、大きな素因数を有し
ていれば、素数Ｐは強いと判定され、小さな素因数だけ
で構成されている場合は、素数Ｐは弱いと判定される。
素因数分解の方法は、Ｐ−１素因数分解法、Ｐ＋１素因
数分解法の他に、ロー法、２次ふるい法、楕円曲線法な
ど様々なものが知られているが、いずれの方法でもよ
い。素因数分解の方法については、前述の文献「コンピ
ュータと素因子分解」に詳しく記載されている。

【００２７】以上のような方法で生成された素数Ｐは、
Ｐ−１素因数分解法にもＰ＋１素因数分解法にも強く、
素因数分解されにくいという特徴を有する。そして、本
実施の形態で生成された素数Ｐをもとに、公開鍵暗号の
鍵を生成すれば、素因数分解されにくい安全な鍵を生成
することができる。

【００２８】実施の形態３．この実施の形態では、図２
に示したステップＳ１０８の、素数ＰがＰ＋１素因数分
解法に強いか否かを判定する処理に、Ｐ＋１を素因数分
解する計算量を可変にすることにより、素因数分解に対
する強さを可変にする場合について説明する。

【００２９】Ｐ＋１を素因数分解する方法として、ロー
法を用いて説明する。まず、ロー法の概要を説明する。
合成数Ｎの素因数Ｐを見つけるために、次の数列を計算
する。なお、合成数とは素数でない数のことである。Ｘ₀＝１、Ｘ_j+1＝Ｘ_j ²＋１（ｍｏｄＮ）（１）次に、Ｘ_2mとＸ_mの最大公約数であるＧＣＤ（Ｘ_2m、
Ｘ_m ）を計算する。１＜ＧＣＤ（Ｘ_2m、Ｘ_m ）＜Ｎと
なれば、ＧＣＤ（Ｘ_2m、Ｘ_m ）がＮの素因数となる。
このロー法は公知の方法であり、前述の文献「コンピュ
ータと素因子分解」に詳しく記載されている。このロー
法は、前記数列（１）の項数を多く計算すれば、即ち前
記数列（１）のｊを大きくすれば、合成数Ｎの素因数が
多く見つかる可能性が高くなるという性質を有する。こ
の実施の形態は、計算回数を入力する回数入力手段を備
え、この回数入力手段により入力された計算回数まで前
記数列（１）を計算し、上述のようにＮの素因数ＧＣＤ
（Ｘ_2m、Ｘ_m ）を求めるものである。

【００３０】ステップＳ１０５で生成された素数Ｐに対
して、Ｐ＋１は合成数となる。Ｐ＋１を素因数分解する
ためには、前記ロー法の説明における合成数ＮをＰ＋１
に置き換えればよい。前記数列を第何項まで計算するか
によって、Ｐ＋１の素因数がいくつ見つかるかが変わ
る。即ち、多く計算すれば、素数ＰがＰ＋１素因数分解
法に対する強さをより正確に知ることができ、計算量が
少なければ、Ｐ＋１素因数分解法に対する強さの正確さ
が小さくなる。従って、より強い素数Ｐを得るために
は、前記数列（１）の項数を多く計算すればよい。そし
てこの実施の形態では、上記計算量は回数入力手段によ
り入力された計算回数に従うものである。

【００３１】以上のように本実施の形態で生成された素
数Ｐをもとに、公開鍵暗号の鍵を生成すれば、素因数分
解されにくい安全な鍵を生成することができる。さら
に、この実施の形態によれば、暗号を使用する目的に応
じて、素因数分解のされにくさを、自由に設定すること
ができる。

【００３２】なお、本実施の形態では、ロー法による素
因数分解をする場合を説明したが、他の素因数分解法を
用いてもよい。

【００３３】実施の形態４．実施の形態１〜３では、Ｐ
−１素因数分解法に強い素数Ｐに対して、Ｐ＋１素因数
分解法に強いか否かを判定し、強い素数Ｐを出力する方
法を説明したが、本実施の形態では、Ｐ＋１素因数分解
法に強い素数Ｐに対して、Ｐ−１素因数分解法に強いか
否かを判定し、強い素数Ｐを出力する方法を説明する。

【００３４】まず、Ｐ＋１素因数分解法に強い素数Ｐを
生成するためには、図２のステップＳ１０４において、
Ｐ＝２ｉｒ−１を計算すればよい。この計算を行えば、
素数Ｐに対してＰ＋１の素因数に、素数Ｐとほぼ同じ大
きさの素数ｒが含まれることになる。即ち、素数ＰはＰ
＋１素因数分解法に対して強い素数となる。次にステッ
プＳ１０８において、ステップＳ１０５で生成された素
数Ｐが、Ｐ−１素因数分解法に強いか否かを判定する。
この判定は、Ｐ−１の素因数に、大きなビット数の素数
が含まれているか否かを調べることにより行う。Ｐ−１
に大きな素因数が含まれていれば、素数ＰはＰ−１素因
数分解法に強いことになり、Ｐ−１が小さな素因数のみ
で構成されていれば、Ｐ−１素因数分解法には弱いこと
になる。

【００３５】以上のような方法で生成された素数Ｐは、
Ｐ＋１素因数分解法にもＰ−１素因数分解法にも強く、
素因数分解されにくいという特徴を有する。そして、本
実施の形態で生成された素数Ｐをもとに、公開鍵暗号の
鍵を生成すれば、素因数分解されにくい安全な鍵を生成
することができる。

【００３６】実施の形態５．実施の形態４では、Ｐ＋１
素因数分解法に強い素数ＰがＰ−１素因数分解法に強い
か否かを判定することについて説明したが、この実施の
形態では、判定処理としてＰ−１を実際に素因数分解す
ることについて説明する。図２のステップＳ１０５で生
成された素数Ｐに対して、Ｐ−１を素因数分解すれば、
Ｐ−１の素因数の大きさを知ることができる。大きな素
因数を有していれば、素数Ｐは強いと判定され、小さな
素因数だけで構成されている場合は、素数Ｐは弱いと判
定される。素因数分解の方法は、Ｐ−１素因数分解法、
Ｐ＋１素因数分解法の他に、ロー法、２次ふるい法、楕
円曲線法など、いずれの方法でもよい。

【００３７】以上のような方法で生成された素数Ｐは、
Ｐ＋１素因数分解法にもＰ−１素因数分解法にも強く、
素因数分解されにくいという特徴を有する。そして、本
実施の形態で生成された素数Ｐをもとに、公開鍵暗号の
鍵を生成すれば、素因数分解されにくい安全な鍵を生成
することができる。

【００３８】実施の形態６．実施の形態５では、素数Ｐ
がＰ−１素因数分解法に強いか否かを判定する処理に素
因数分解を用いるものを示したが、この実施の形態で
は、Ｐ−１を素因数分解する計算量を可変にすることに
より、素因数分解に対する強さを可変にする場合につい
て説明する。

【００３９】実施の形態３と同様にロー法による素因数
分解を行い、ロー法の前記数列（１）の項数を調整する
ことにより、Ｐ−１素因数分解法に対する強さを調整す
ることができる。調整するためには、実施の形態３と同
様に、計算回数を入力する回数入力手段を備え、この回
数入力手段により入力された計算回数まで前記数列
（１）を計算するようにする。

【００４０】以上のように本実施の形態で生成された素
数Ｐをもとに、公開鍵暗号の鍵を生成すれば、素因数分
解されにくい安全な鍵を生成することができる。さら
に、この実施の形態によれば、暗号を使用する目的に応
じて、素因数分解のされにくさを、自由に設定すること
ができる。

【００４１】なお、本実施の形態では、ロー法による素
因数分解をする場合を説明したが、他の素因数分解法を
用いてもよい。

【００４２】

【発明の効果】請求項１又は５の発明によれば、Ｐ−１
素因数分解法に強い第２の素数がＰ＋１素因数分解法に
強いか否かを判定し、強いと判定された第２の素数を出
力するので、Ｐ−１素因数分解法にもＰ＋１素因数分解
法にも強い素数を生成することができる。さらに、本発
明により生成された素数を用いて暗号の鍵を生成するこ
とにより、素因数分解されにくい安全な鍵を生成するこ
とができる。

【００４３】請求項２又は６の発明によれば、Ｐ＋１素
因数分解法に強い第２の素数がＰ−１素因数分解法に強
いか否かを判定し、強いと判定された第２の素数を出力
するので、Ｐ＋１素因数分解法にもＰ−１素因数分解法
にも強い素数を生成することができる。さらに、本発明
により生成された素数を用いて暗号の鍵を生成すること
により、素因数分解されにくい安全な鍵を生成すること
ができる。

【００４４】請求項３又は７の発明によれば、生成した
素数を実際に素因数分解をすることにより素因数分解に
強いか否かの判定を行なうので、素因数分解に強い素数
を生成することができる。

【００４５】請求項４又は８の発明によれば、入力され
た計算回数の素因数分解を行ないその結果に基づいて判
定するので、生成する素数Ｐの素因数分解に対する強さ
を自由に設定することができる。

【図面の簡単な説明】

【図１】実施の形態１の素数生成装置の構成を示す構
成図である。

【図２】実施の形態１の素数生成装置の動作を示すフ
ローチャートである。

【図３】従来の素数生成方法の動作を示すフローチャ
ートである。

【符号の説明】

１素数ｒ生成手段、２素数ｒ記憶手段、３素数Ｐ
生成手段、４素数Ｐ記憶手段、５判定手段、６出
力手段、７コンピュータ、８メモリ。

Claims

【特許請求の範囲】

【請求項１】第１の素数を記憶する第１の記憶手段
と、この第１の記憶手段に記憶された前記第１の素数を用い
て所定の演算を行い、Ｐ−１素因数分解法に強い第２の
素数を生成する生成手段と、この生成手段により生成された前記第２の素数を記憶す
る第２の記憶手段と、この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ＋１素因数分解法に強いか否
かを判定する判定手段と、この判定手段によりＰ＋１素因数分解法に強いと判定さ
れた前記第２の素数を出力する出力手段とを備えたこと
を特徴とする素数生成装置。
【請求項２】第１の素数を記憶する第１の記憶手段
と、この第１の記憶手段に記憶された前記第１の素数を用い
て所定の演算を行い、Ｐ＋１素因数分解法に強い第２の
素数を生成する生成手段と、この生成手段により生成された前記第２の素数を記憶す
る第２の記憶手段と、この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ−１素因数分解法に強いか否
かを判定する判定手段と、この判定手段によりＰ−１素因数分解法に強いと判定さ
れた前記第２の素数を出力する出力手段とを備えたこと
を特徴とする素数生成装置。
【請求項３】前記判定手段は、素因数分解を行ないそ
の結果に基づいて判定することを特徴とする請求項１又
は２記載の素数生成装置。
【請求項４】計算回数を入力する回数入力手段を備
え、前記判定手段は、前記回数入力手段により入力された前
記計算回数の素因数分解を行ないその結果に基づいて判
定することを特徴とする請求項１又は２記載の素数生成
装置。
【請求項５】第１の記憶手段に記憶された第１の素数
を用いて所定の演算を行い、Ｐ−１素因数分解法に強い
第２の素数を生成し、第２の記憶手段に記憶させる生成
ステップと、この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ＋１素因数分解法に強いか否
かを判定する判定ステップと、この判定ステップによりＰ＋１素因数分解法に強いと判
定された前記第２の素数を出力する出力ステップとを備
えたことを特徴とする素数生成方法。
【請求項６】第１の記憶手段に記憶された第１の素数
を用いて所定の演算を行い、Ｐ＋１素因数分解法に強い
第２の素数を生成し、第２の記憶手段に記憶させる生成
ステップと、この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ−１素因数分解法に強いか否
かを判定する判定ステップと、この判定ステップによりＰ−１素因数分解法に強いと判
定された前記第２の素数を出力する出力ステップとを備
えたことを特徴とする素数生成方法。
【請求項７】前記判定ステップは、素因数分解を行な
いその結果に基づいて判定することを特徴とする請求項
５又は６記載の素数生成方法。
【請求項８】計算回数を入力する回数入力ステップを
備え、前記判定ステップは、前記回数入力ステップにより入力
された前記計算回数の素因数分解を行ないその結果に基
づいて判定することを特徴とする請求項５又は６記載の
素数生成方法。