JPH10207363A - Device and method for generating prime number - Google Patents
Device and method for generating prime numberInfo
- Publication number
- JPH10207363A JPH10207363A JP1396397A JP1396397A JPH10207363A JP H10207363 A JPH10207363 A JP H10207363A JP 1396397 A JP1396397 A JP 1396397A JP 1396397 A JP1396397 A JP 1396397A JP H10207363 A JPH10207363 A JP H10207363A
- Authority
- JP
- Japan
- Prior art keywords
- prime
- prime number
- factorization
- strong
- generating
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 167
- 239000002131 composite material Substances 0.000 description 5
- 238000010586 diagram Methods 0.000 description 2
- 238000007873 sieving Methods 0.000 description 2
- 241000282320 Panthera leo Species 0.000 description 1
- 238000000354 decomposition reaction Methods 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
Landscapes
- Complex Calculations (AREA)
Abstract
Description
【０００１】[0001]
【発明の属する技術分野】本発明は、Ｐ−１素因数分解
法にもＰ＋１素因数分解法にも強い素数を生成する素数
生成装置及び方法に関するものであり、本発明の素数生
成装置及び方法は、例えば公開鍵暗号の鍵を生成するた
めに利用することができる。BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus and a method for generating prime numbers that are strong in both the P-1 and P + 1 factorization methods. For example, it can be used to generate a key for public key encryption.
【０００２】[0002]
【従来の技術】従来の素数生成方法について説明する。
従来の素数生成方法には、暗号化電子メールソフトウエ
アであるＰＧＰ（Ｐｒｅｔｔｙ Ｇｏｏｄ Ｐｒｉｖａ
ｃｙ）で用いられている素数生成方法がある。ＰＧＰ
は、公開鍵暗号としてＲＳＡを、秘密鍵暗号としてＩＤ
ＥＡを用い、電子メールを暗号化して送るソフトウエア
であり、ＰＧＰの全ソースプログラムは、PhiLip R. Zi
mmermann著“PGP Source Code and Internals”（The M
IT Press、１９９５年発行）に記載されている。ＰＧＰ
では、生成した素数をＲＳＡ暗号の鍵を生成するために
使用している。2. Description of the Related Art A conventional prime number generating method will be described.
Conventional prime number generation methods include PGP (Pretty Good Private), which is encrypted e-mail software.
There is a prime number generation method used in cy). PGP
Is RSA as public key encryption and ID as secret key encryption
It is software that sends an encrypted email using EA. All PGP source programs are PhiLip R. Zi
mmermann, “PGP Source Code and Internals” (The M
IT Press, 1995). PGP
Uses the generated prime number to generate an RSA encryption key.
【０００３】図３は、ＰＧＰで用いられている素数生成
方法のフローチャートである。図において、ステップＳ
２０１は素数生成の開始、ステップＳ２０２は素数ｒを
生成する処理、ステップＳ２０３は変数ｉを１に初期化
する処理、ステップＳ２０４は目的の素数Ｐの候補をＰ
＝２ｉｒ＋１として計算する処理、ステップＳ２０５は
ステップＳ２０４において計算されたＰが素数であるか
否を判定する処理、ステップＳ２０６はステップＳ２０
５においてＰが素数でないと判定された場合にｉ＝ｉ＋
１とする処理、ステップＳ２０７はステップＳ２０６に
おいて計算されたｉが１００００を超えているか否かを
判定する処理、ステップＳ２０８は素数Ｐを出力する処
理、ステップＳ２０９は処理の終了である。FIG. 3 is a flowchart of a prime number generation method used in PGP. In the figure, step S
201 is a start of prime generation, step S202 is a process for generating a prime r, step S203 is a process for initializing a variable i to 1, and step S204 is a process for generating a target prime P candidate.
= 2ir + 1, step S205 is a step of determining whether or not P calculated in step S204 is a prime number, and step S206 is a step S20.
When it is determined in step 5 that P is not a prime number, i = i +
Step S207 is a step of determining whether or not i calculated in step S206 exceeds 10000, step S208 is a step of outputting a prime number P, and step S209 is the end of the processing.
【０００４】次に図３のフローチャートに基づいて、動
作を詳細に説明する。生成する素数Ｐは２５６ビットの
場合を説明する。まずステップＳ２０２において、約２
５６ビットの素数ｒを生成する。素数ｒの生成方法は、
例えば、まず素数ｒの候補として約２５６ビットの乱数
を生成し、生成された乱数をラビン法などの素数判定法
により素数であるか否かを判定する。生成された乱数が
素数であると判定されればステップＳ２０２の処理は終
了し、素数でないと判定されれば再び素数ｒの候補とし
て乱数を生成する。Next, the operation will be described in detail with reference to the flowchart of FIG. The case where the generated prime number P is 256 bits will be described. First, in step S202, about 2
Generate a 56-bit prime r. The method of generating the prime number r is
For example, first, a random number of about 256 bits is generated as a candidate for the prime number r, and it is determined whether or not the generated random number is a prime number by a prime number determination method such as the Rabin method. If it is determined that the generated random number is a prime number, the process of step S202 ends. If it is determined that the generated random number is not a prime number, a random number is generated again as a candidate for the prime number r.
【０００５】次に、ステップＳ２０３において、変数ｉ
を１に初期化し、ステップＳ２０４において、素数ｒと
変数ｉをもとにＰ＝２ｉｒ＋１を計算する。ステップＳ
２０４において計算されたＰを、ステップＳ２０５にお
いて素数であるか否かを判定する。Ｐが素数であると判
定されれば、ステップＳ２０８で素数Ｐを出力し、ステ
ップＳ２０９で処理を終了する。Ｐが素数でないと判定
されれば、ステップＳ２０６の処理へ進み、ステップＳ
２０６において変数ｉの値に１を加算する。ステップＳ
２０７では、ステップＳ２０６において計算された変数
ｉの値が１００００を超えているか否かを判定する。こ
の判定の目的は、生成したい素数Ｐは２５６ビットであ
り、またＰはＰ＝２ｉｒ＋１としているため、変数ｉが
大きすぎると、素数Ｐが２５６ビットを超えてしまうか
らである。ＰＧＰでは、変数ｉの上限値は１００００と
なっている。ステップＳ２０７において変数ｉが１００
００を超えていないと判定された場合は、ステップＳ２
０４において再びＰ＝２ｉｒ＋１を計算する。ステップ
Ｓ２０７において変数ｉが１００００を超えていると判
定された場合は、ステップＳ２０２において再び素数ｒ
を生成する。Next, in step S203, the variable i
Is initialized to 1 and in step S204, P = 2ir + 1 is calculated based on the prime number r and the variable i. Step S
In step S205, it is determined whether or not the P calculated in 204 is a prime number. If it is determined that P is a prime number, the prime number P is output in step S208, and the process ends in step S209. If it is determined that P is not a prime number, the process proceeds to step S206, and the process proceeds to step S206.
At 206, 1 is added to the value of the variable i. Step S
In 207, it is determined whether or not the value of the variable i calculated in step S206 exceeds 10,000. The purpose of this determination is that the prime number P to be generated is 256 bits, and P is P = 2ir + 1. Therefore, if the variable i is too large, the prime number P will exceed 256 bits. In PGP, the upper limit of the variable i is 10,000. In step S207, the variable i is 100
If it is determined that the value does not exceed 00, step S2
At 04, P = 2ir + 1 is calculated again. If it is determined in step S207 that the variable i exceeds 10,000, the prime number r is again determined in step S202.
Generate
【０００６】以上のような素数生成方法で生成された２
５６ビットの素数Ｐは、Ｐ−１の素因数に、素数Ｐとほ
ぼ同じビット数の素数ｒを有することが保証される。即
ち、生成された素数Ｐは、Ｐ−１素因数分解法に強いと
いう特徴を有する。Ｐ−１素因数分解法は、Ｐ−１の因
数が小さい素数ばかりで構成されている場合に有効な素
因数分解法で、公知の方法であり、例えば和田秀男著、
「コンピュータと素因子分解」（遊星社、１９８７年１
０月２０日発行、７７〜９４頁）に詳しく記載されてい
る。[0006] The 2 generated by the above-described prime number generation method.
The 56-bit prime P is guaranteed to have the same prime r as the prime P in the prime factor of P-1. That is, the generated prime number P has a feature that it is strong against the P-1 prime factorization method. The P-1 prime factorization method is a known factorization method effective when the factor of P-1 is composed of only small prime numbers, and is a known method. For example, Hideo Wada,
"Computer and Elementary Factorization" (Yuseisha, 1987 January
Published on 20th January, pages 77-94).
【０００７】[0007]
【発明が解決しようとする課題】従来の素数生成方法
は、上述のように構成されているため、Ｐ−１素因数分
解法に強い素数を生成した場合、Ｐ＋１素因数分解法に
対する対策は施されておらず、生成された素数Ｐは、Ｐ
＋１素因数分解法には弱いことがあり、素因数分解され
やすいという問題点があった。また、従来の素数生成方
法は、Ｐ−１素因数分解法とＰ＋１素因数分解法の両方
に対して強い素数を生成できないという問題点があっ
た。さらに、従来の素数生成方法は、素因数分解に対す
る強さを目的に応じて可変にできないという問題点があ
った。Since the conventional prime number generation method is configured as described above, when a prime number that is strong against the P-1 prime factorization method is generated, measures are taken against the P + 1 prime factorization method. And the generated prime number P is P
The +1 prime factorization method is weak in some cases, and has a problem that the prime factorization is easily performed. In addition, the conventional prime generation method has a problem that it cannot generate a strong prime number for both the P-1 and P + 1 factorization methods. Further, the conventional prime number generation method has a problem that the strength of the prime factorization cannot be changed according to the purpose.
【０００８】本発明は、係る問題点を解決するためにな
されたもので、Ｐ−１素因数分解法にもＰ＋１素因数分
解法にも強い素数を生成する素数生成装置及び方法を得
ることを目的とする。さらに、本発明は、素数Ｐの素因
数分解に対する強さを目的に応じて可変にできる素数生
成装置及び方法を得ることを目的とする。SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and an object of the present invention is to provide an apparatus and method for generating a prime number which is strong in both the P-1 factorization method and the P + 1 factorization method. I do. Another object of the present invention is to provide an apparatus and method for generating a prime number that can vary the strength of the prime number P with respect to factoring according to the purpose.
【０００９】[0009]
【課題を解決するための手段】本発明の請求項１に係る
素数生成装置は、第１の素数を記憶する第１の記憶手段
と、この第１の記憶手段に記憶された前記第１の素数を
用いて所定の演算を行い、Ｐ−１素因数分解法に強い第
２の素数を生成する生成手段と、この生成手段により生
成された前記第２の素数を記憶する第２の記憶手段と、
この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ＋１素因数分解法に強いか否
かを判定する判定手段と、この判定手段によりＰ＋１素
因数分解法に強いと判定された前記第２の素数を出力す
る出力手段とを備えたものである。According to a first aspect of the present invention, there is provided an apparatus for generating a prime number, comprising: a first storage means for storing a first prime number; and a first storage means for storing the first prime number stored in the first storage means. Generating means for performing a predetermined operation using prime numbers to generate a second prime number resistant to the P-1 prime factorization method; and second storage means for storing the second prime numbers generated by the generating means. ,
The second prime number stored in the second storage means is taken out, a determination means for determining whether or not the second prime number is strong in the P + 1 prime factorization method, and the determination means is strong in the P + 1 prime factorization method. Output means for outputting the second prime number determined as above.
【００１０】本発明の請求項２に係る素数生成装置は、
第１の素数を記憶する第１の記憶手段と、この第１の記
憶手段に記憶された前記第１の素数を用いて所定の演算
を行い、Ｐ＋１素因数分解法に強い第２の素数を生成す
る生成手段と、この生成手段により生成された前記第２
の素数を記憶する第２の記憶手段と、この第２の記憶手
段に記憶された前記第２の素数を取り出し、この第２の
素数がＰ−１素因数分解法に強いか否かを判定する判定
手段と、この判定手段によりＰ−１素因数分解法に強い
と判定された前記第２の素数を出力する出力手段とを備
えたものである。According to a second aspect of the present invention, there is provided an apparatus for generating a prime number,
A first storage unit for storing a first prime number, and a predetermined operation is performed using the first prime number stored in the first storage unit to generate a second prime number resistant to the P + 1 prime factorization method Generating means, and the second means generated by the generating means.
And a second storage unit for storing the prime numbers of the first and second prime numbers, and determining whether or not the second prime number is strong against the P-1 prime factorization method. A determination unit; and an output unit that outputs the second prime number determined to be strong in the P-1 prime factorization method by the determination unit.
【００１１】本発明の請求項３に係る素数生成装置は、
素因数分解を行ないその結果に基づいて判定する判定手
段を備えたものである。[0011] According to a third aspect of the present invention, there is provided a prime number generating apparatus comprising:
It is provided with determination means for performing a factorization and making a determination based on the result.
【００１２】本発明の請求項４に係る素数生成装置は、
計算回数を入力する回数入力手段を備え、前記判定手段
は、前記回数入力手段により入力された前記計算回数の
素因数分解を行ないその結果に基づいて判定するもので
ある。[0012] According to a fourth aspect of the present invention, there is provided a prime number generating apparatus comprising:
The apparatus further includes a number input means for inputting the number of calculations, wherein the determination means performs a factorization of the number of calculations input by the number input means and makes a determination based on the result.
【００１３】本発明の請求項５に係る素数生成方法は、
第１の記憶手段に記憶された第１の素数を用いて所定の
演算を行い、Ｐ−１素因数分解法に強い第２の素数を生
成し、第２の記憶手段に記憶させる生成ステップと、こ
の第２の記憶手段に記憶された前記第２の素数を取り出
し、この第２の素数がＰ＋１素因数分解法に強いか否か
を判定する判定ステップと、この判定ステップによりＰ
＋１素因数分解法に強いと判定された前記第２の素数を
出力する出力ステップとを備えたものである。According to a fifth aspect of the present invention, there is provided a method for generating a prime number,
Performing a predetermined operation using the first prime number stored in the first storage means to generate a second prime number resistant to the P-1 factorization method, and storing the second prime number in the second storage means; A step of fetching the second prime number stored in the second storage means and determining whether the second prime number is strong against the P + 1 prime factorization method;
An output step of outputting the second prime number determined to be strong against the +1 prime factorization method.
【００１４】本発明の請求項６に係る素数生成方法は、
第１の記憶手段に記憶された第１の素数を用いて所定の
演算を行い、Ｐ＋１素因数分解法に強い第２の素数を生
成し、第２の記憶手段に記憶させる生成ステップと、こ
の第２の記憶手段に記憶された前記第２の素数を取り出
し、この第２の素数がＰ−１素因数分解法に強いか否か
を判定する判定ステップと、この判定ステップによりＰ
−１素因数分解法に強いと判定された前記第２の素数を
出力する出力ステップとを備えたものである。According to a sixth aspect of the present invention, there is provided a method for generating a prime number,
Performing a predetermined operation using the first prime number stored in the first storage means to generate a second prime number resistant to the P + 1 factorization method, and storing the generated second prime number in the second storage means; A second prime number stored in the second storage means, and a determination step of determining whether or not the second prime number is strong against the P-1 prime factorization method;
An output step of outputting the second prime number determined to be strong against the -1 prime factorization method.
【００１５】本発明の請求項７に係る素数生成方法は、
素因数分解を行ないその結果に基づいて判定する判定ス
テップを備えたものである。According to a seventh aspect of the present invention, there is provided a method for generating a prime number,
The method includes a determination step of performing a factorization and performing a determination based on the result.
【００１６】本発明の請求項８に係る素数生成方法は、
計算回数を入力する回数入力ステップを備え、前記判定
ステップは、前記回数入力ステップにより入力された前
記計算回数の素因数分解を行ないその結果に基づいて判
定するものである。[0016] The method for generating prime numbers according to claim 8 of the present invention comprises:
The method further includes a number input step of inputting the number of calculations, and the determining step performs a prime factorization of the number of calculations input in the number input step and makes a determination based on the result.
【００１７】[0017]
実施の形態１．本発明の素数生成装置の一実施の形態を
図に基づいて説明する。図１は実施の形態１の素数生成
装置の構成を示す構成図である。図において、１は第１
の素数である素数ｒを生成する素数ｒ生成手段、２は素
数ｒ生成手段１により生成された素数ｒを記憶する素数
ｒ記憶手段、３は素数ｒ記憶手段２に記憶された素数ｒ
を用いて演算を行い、第２の素数である素数Ｐを生成す
る素数Ｐ生成手段、４は素数Ｐ生成手段３により生成さ
れた素数Ｐを記憶する素数Ｐ記憶手段、５は素数Ｐ記憶
手段４に記憶された素数ＰがＰ＋１素因数分解法に強い
か否かを判定する判定手段、６は判定手段５によりＰ＋
１素因数分解法に強いと判定された素数Ｐを出力する出
力手段、７は素数ｒ生成手段１、素数Ｐ生成手段３、判
定手段５及び出力手段６を備えたコンピュータ、８は素
数ｒ記憶手段２及び素数Ｐ記憶手段４を備えたメモリで
ある。Embodiment 1 FIG. An embodiment of a prime number generation device according to the present invention will be described with reference to the drawings. FIG. 1 is a configuration diagram showing a configuration of the prime number generation device according to the first embodiment. In the figure, 1 is the first
A prime number r generating means for generating a prime number r which is a prime number, a prime number r storing means for storing the prime number r generated by the prime number r generating means 1, and a prime number r stored in the prime number r storing means 2
, A prime P generating means for generating a prime P which is a second prime, a prime P storing means for storing the prime P generated by the prime P generating means 3, a prime P storing means 5 4 is a determining means for determining whether or not the prime number P stored in 4 is strong against the P + 1 prime factorization method.
Output means for outputting a prime number P determined to be strong against the one-factor factorization method; 7, a computer provided with a prime r generation means 1, a prime P generation means 3, a determination means 5 and an output means 6; This is a memory including 2 and a prime P storage unit 4.
【００１８】図２は図１に示した素数生成装置の動作を
示すフローチャートである。図において、ステップＳ１
０１は素数生成の開始、ステップＳ１０２は素数ｒを生
成する処理、ステップＳ１０３は変数ｉを１に初期化す
る処理、ステップＳ１０４は目的の素数Ｐの候補をＰ＝
２ｉｒ＋１として計算する処理、ステップＳ１０５はス
テップＳ１０４において計算されたＰが素数であるか否
を判定する処理、ステップＳ１０６はステップＳ１０５
においてＰが素数でないと判定された場合にｉ＝ｉ＋１
とする処理、ステップＳ１０７はステップＳ１０６にお
いて計算されたｉが所定の値、例えば１００００を超え
ているか否かを判定する処理、ステップＳ１０８はステ
ップＳ１０５においてＰが素数であると判定された場合
に、ＰがＰ＋１素因数分解法に強いか否かを判定する処
理、ステップＳ１０９はステップＳ１０８でＰ＋１素因
数分解法に強いと判定された素数Ｐを出力する処理、ス
テップＳ１１０は処理の終了である。ここで、ステップ
Ｓ１０２は素数ｒ生成手段１による処理であり、ステッ
プＳ１０３〜Ｓ１０７は素数Ｐ生成手段３による処理で
あり、ステップＳ１０８は判定手段５による処理であ
り、ステップＳ１０９は出力手段６による処理である。FIG. 2 is a flowchart showing the operation of the prime number generation device shown in FIG. In the figure, step S1
01 is the start of generation of a prime number, step S102 is a process of generating a prime number r, step S103 is a process of initializing a variable i to 1, and step S104 is a process in which a candidate of a target prime number P is
The process of calculating as 2ir + 1, step S105 is a process of determining whether or not P calculated in step S104 is a prime number, and step S106 is step S105.
In the case where it is determined that P is not a prime number, i = i + 1
Step S107 is a step of determining whether or not i calculated in step S106 exceeds a predetermined value, for example, 10,000. Step S108 is a step of determining that P is a prime number in step S105. A process of determining whether P is strong in the P + 1 prime factorization method, a process of outputting a prime number P determined to be strong in the P + 1 prime factorization method in step S108, and an end of the process in step S110. Here, step S102 is processing by the prime number r generating means 1, steps S103 to S107 are processing by the prime number P generating means 3, step S108 is processing by the determining means 5, and step S109 is processing by the output means 6. It is.
【００１９】次に図２のフローチャートに基づいて動作
を詳細に説明する。本実施の形態では、生成する素数Ｐ
は２５６ビットの場合を説明する。まずステップＳ１０
２において、約２５６ビットの素数ｒを生成し、素数ｒ
記憶手段２に記憶させる。素数ｒの生成方法は、例え
ば、まず素数ｒの候補として約２５６ビットの乱数を生
成し、生成された乱数をラビン法などの素数判定法によ
り素数であるか否かを判定する。生成された乱数が素数
であると判定されればステップＳ１０２の処理は終了
し、素数でないと判定されれば再び素数ｒの候補として
乱数を生成する。Next, the operation will be described in detail with reference to the flowchart of FIG. In the present embodiment, the generated prime number P
Describes the case of 256 bits. First, step S10
2, a prime r of about 256 bits is generated, and a prime r
It is stored in the storage means 2. The method of generating the prime number r, for example, first generates a random number of about 256 bits as a candidate for the prime number r, and determines whether or not the generated random number is a prime number by a prime number determination method such as the Rabin method. If it is determined that the generated random number is a prime number, the process of step S102 ends. If it is determined that the generated random number is not a prime number, a random number is generated again as a candidate for the prime number r.
【００２０】次に、ステップＳ１０３において、変数ｉ
を１に初期化し、ステップＳ１０４において、素数ｒ記
憶手段２に記憶された素数ｒを取り出し、この取り出し
た素数ｒと変数ｉをもとにＰ＝２ｉｒ＋１を計算する。
求めたＰは素数Ｐ記憶手段４に記憶させる。ステップＳ
１０４において計算されたＰを素数Ｐ記憶手段４より取
り出し、ステップＳ１０５において素数であるか否かを
判定する。Ｐが素数であると判定されれば、ステップＳ
１０８の処理へ進む。Next, in step S103, the variable i
Is initialized to 1, and in step S104, the prime number r stored in the prime number r storage means 2 is extracted, and P = 2ir + 1 is calculated based on the extracted prime number r and the variable i.
The obtained P is stored in the prime P storage means 4. Step S
The P calculated in 104 is retrieved from the prime P storage means 4, and it is determined in step S105 whether or not the prime is a prime. If P is determined to be a prime number, step S
The process proceeds to 108.
【００２１】Ｐが素数でないと判定されれば、ステップ
Ｓ１０６の処理へ進み、ステップＳ１０６において変数
ｉの値に１を加算する。ステップＳ１０７では、ステッ
プＳ１０６において計算された変数ｉの値が、所定の値
を超えているか否かを判定する。この判定の目的は、生
成したい素数Ｐが２５６ビットであり、またＰはＰ＝２
ｉｒ＋１としているため、変数ｉが大きすぎると、素数
Ｐが２５６ビットを超えてしまうからである。この実施
の形態では、変数ｉの上限値は１００００とした。ステ
ップＳ１０７において変数ｉが所定の値を超えていない
と判定された場合、ステップＳ１０４において再び、素
数ｒ記憶手段２に記憶された素数ｒを取り出し、この取
り出した素数ｒと変数ｉをもとにＰ＝２ｉｒ＋１を計算
する。求めたＰは再び素数Ｐ記憶手段４に記憶させる。
ステップＳ１０７において変数ｉが所定の値を超えてい
ると判定された場合、ステップＳ１０２において再び素
数ｒを生成する。If it is determined that P is not a prime number, the process proceeds to step S106, where 1 is added to the value of the variable i in step S106. In step S107, it is determined whether the value of the variable i calculated in step S106 exceeds a predetermined value. The purpose of this determination is that the prime number P to be generated is 256 bits, and P is P = 2
This is because, since ir + 1 is set, if the variable i is too large, the prime number P will exceed 256 bits. In this embodiment, the upper limit of the variable i is 10,000. If it is determined in step S107 that the variable i does not exceed the predetermined value, the prime r stored in the prime r storage means 2 is extracted again in step S104, and based on the extracted prime r and variable i. Calculate P = 2ir + 1. The obtained P is stored in the prime number P storage means 4 again.
If it is determined in step S107 that the variable i has exceeded a predetermined value, a prime r is generated again in step S102.
【００２２】ステップＳ１０５までの処理で生成された
２５６ビットの素数Ｐは、Ｐ−１の素因数として、素数
Ｐとほぼ同じビット数の素数ｒを有することが保証され
る。即ち、生成された素数Ｐは、Ｐ−１素因数分解法に
強いという特徴を有する。It is guaranteed that the 256-bit prime P generated by the processing up to step S105 has a prime r of substantially the same number of bits as the prime P as a prime factor of P-1. That is, the generated prime number P has a feature that it is strong against the P-1 prime factorization method.
【００２３】次にステップＳ１０８において、ステップ
Ｓ１０４で生成された素数Ｐを素数Ｐ記憶手段４より取
り出し、この取り出した素数Ｐが、Ｐ＋１素因数分解法
に強いか否かを判定する。この判定は、Ｐ＋１の素因数
に、大きな数の素因数が含まれているか否かを調べるこ
とにより行う。Ｐ＋１に大きな素因数が含まれていれ
ば、素数ＰはＰ＋１素因数分解法に強いことになり、Ｐ
＋１が小さな素因数のみで構成されていれば、Ｐ＋１素
因数分解法には弱いことになる。Ｐ＋１素因数分解法
は、Ｐ＋１が小さい素因数のみで構成されている場合に
有効な素因数分解法で、公知の方法であり、例えば前述
の文献「コンピュータと素因子分解」に詳しく記載され
ている。ステップＳ１０８において、素数ＰがＰ＋１素
因数分解法に弱いと判定された場合は、ステップＳ１０
２において再び素数ｒを生成する。素数ＰがＰ＋１素因
数分解法に強いと判定された場合は、ステップＳ１０９
において、素数Ｐ記憶手段４に記憶された素数Ｐを出力
し、ステップＳ１１０で処理を終了する。Next, in step S108, the prime number P generated in step S104 is extracted from the prime number P storage means 4, and it is determined whether or not the extracted prime number P is strong against the P + 1 prime factorization method. This determination is made by examining whether the prime factor of P + 1 includes a large prime factor. If P + 1 contains a large prime factor, the prime number P is strong against the P + 1 prime factorization method, and P
If +1 is composed of only small prime factors, it is weak to the P + 1 prime factorization method. The P + 1 factorization method is a known factorization method effective when P + 1 is composed of only small prime factors, and is a known method, and is described in detail in, for example, the above-mentioned document “Computer and Prime Factorization”. If it is determined in step S108 that the prime number P is weak in the P + 1 prime factorization method, step S10
In step 2, a prime number r is generated again. If it is determined that the prime number P is strong against the P + 1 prime factorization method, step S109
, The prime number P stored in the prime number P storage means 4 is output, and the process ends in step S110.
【００２４】以上のような方法で生成された素数Ｐは、
Ｐ−１素因数分解法にもＰ＋１素因数分解法にも強く、
素因数分解されにくいという特徴を有する。そして、本
実施の形態で生成された素数Ｐをもとに、公開鍵暗号の
鍵を生成すれば、素因数分解されにくい安全な鍵を生成
することができる。The prime number P generated by the above method is
Strong in both P-1 and P + 1 factorization methods,
It has the feature that it is difficult to factorize. Then, if a key for public key encryption is generated based on the prime number P generated in the present embodiment, it is possible to generate a secure key that is difficult to factorize.
【００２５】本実施の形態では、生成する素数Ｐは２５
６ビットとしたが、例えば５１２、７６８、１０２４な
どの他のビット数の素数でも同様な方法で生成できる。In the present embodiment, the generated prime number P is 25
Although 6 bits are used, a prime number having another bit number such as 512, 768, or 1024 can be generated in the same manner.
【００２６】実施の形態２．この実施の形態では、図２
に示したステップＳ１０８の、素数ＰがＰ＋１素因数分
解法に強いか否かを判定する処理として、Ｐ＋１を実際
に素因数分解することにより判定する場合について説明
する。ステップＳ１０８において生成された素数Ｐに対
して、Ｐ＋１を素因数分解すれば、Ｐ＋１の素因数の大
きさを知ることができる。そして、大きな素因数を有し
ていれば、素数Ｐは強いと判定され、小さな素因数だけ
で構成されている場合は、素数Ｐは弱いと判定される。
素因数分解の方法は、Ｐ−１素因数分解法、Ｐ＋１素因
数分解法の他に、ロー法、２次ふるい法、楕円曲線法な
ど様々なものが知られているが、いずれの方法でもよ
い。素因数分解の方法については、前述の文献「コンピ
ュータと素因子分解」に詳しく記載されている。Embodiment 2 FIG. In this embodiment, FIG.
As a process of determining whether or not the prime number P is strong in the P + 1 prime factorization method in step S108 shown in (1), a case in which P + 1 is determined by actually performing a prime factorization will be described. By performing a prime factorization of P + 1 with respect to the prime number P generated in step S108, the magnitude of the prime factor of P + 1 can be known. If it has a large prime factor, the prime number P is determined to be strong, and if it is composed of only small prime factors, the prime number P is determined to be weak.
As a method of the prime factorization, various methods such as a row method, a secondary sieving method, and an elliptic curve method are known in addition to the P-1 prime factorization method and the P + 1 prime factorization method, and any method may be used. The method of prime factorization is described in detail in the aforementioned document "Computer and Prime Factorization".
【００２７】以上のような方法で生成された素数Ｐは、
Ｐ−１素因数分解法にもＰ＋１素因数分解法にも強く、
素因数分解されにくいという特徴を有する。そして、本
実施の形態で生成された素数Ｐをもとに、公開鍵暗号の
鍵を生成すれば、素因数分解されにくい安全な鍵を生成
することができる。The prime number P generated by the above method is
Strong in both P-1 and P + 1 factorization methods,
It has the feature that it is difficult to factorize. Then, if a key for public key encryption is generated based on the prime number P generated in the present embodiment, it is possible to generate a secure key that is difficult to factorize.
【００２８】実施の形態３．この実施の形態では、図２
に示したステップＳ１０８の、素数ＰがＰ＋１素因数分
解法に強いか否かを判定する処理に、Ｐ＋１を素因数分
解する計算量を可変にすることにより、素因数分解に対
する強さを可変にする場合について説明する。Embodiment 3 In this embodiment, FIG.
In the process of determining whether or not the prime number P is strong against the P + 1 prime factorization method in step S108 shown in (1), the case where the strength for the prime factorization is made variable by making the amount of calculation for factorizing P + 1 variable explain.
【００２９】Ｐ＋１を素因数分解する方法として、ロー
法を用いて説明する。まず、ロー法の概要を説明する。
合成数Ｎの素因数Ｐを見つけるために、次の数列を計算
する。なお、合成数とは素数でない数のことである。 Ｘ0＝１、 Ｘj+1＝ Ｘj 2＋１（ｍｏｄＮ） （１） 次に、 Ｘ2mとＸmの最大公約数であるＧＣＤ（ Ｘ2m、
Ｘm ）を計算する。１＜ ＧＣＤ（ Ｘ2m、Ｘm ）＜Ｎと
なれば、ＧＣＤ（ Ｘ2m、Ｘm ）がＮの素因数となる。
このロー法は公知の方法であり、前述の文献「コンピュ
ータと素因子分解」に詳しく記載されている。このロー
法は、前記数列（１）の項数を多く計算すれば、即ち前
記数列（１）のｊを大きくすれば、合成数Ｎの素因数が
多く見つかる可能性が高くなるという性質を有する。こ
の実施の形態は、計算回数を入力する回数入力手段を備
え、この回数入力手段により入力された計算回数まで前
記数列（１）を計算し、上述のようにＮの素因数ＧＣＤ
（ Ｘ2m、Ｘm ）を求めるものである。The method of factorizing P + 1 into prime factors will be described using the Row method. First, an outline of the Law method will be described.
To find the prime factor P of the composite number N, the following sequence is calculated. Note that the composite number is a number that is not a prime number. X 0 = 1, X j + 1 = X j 2 +1 (modN) (1) Next, GCD (X 2m , which is the greatest common divisor of X 2m and X m ,
X m ) is calculated. 1 <GCD if the (X 2m, X m) < N, GCD (X 2m, X m) is the prime factors of N.
This Lowe method is a known method and is described in detail in the above-mentioned document "Computer and elementary factorization". This Row method has a property that if the number of terms of the sequence (1) is calculated to be large, that is, if j of the sequence (1) is increased, there is a high possibility that many prime factors of the composite number N are found. This embodiment includes a number input means for inputting the number of calculations, calculates the sequence (1) up to the number of calculations input by the number input means, and calculates the prime factor GCD of N as described above.
(X 2m , X m ).
【００３０】ステップＳ１０５で生成された素数Ｐに対
して、Ｐ＋１は合成数となる。Ｐ＋１を素因数分解する
ためには、前記ロー法の説明における合成数ＮをＰ＋１
に置き換えればよい。前記数列を第何項まで計算するか
によって、Ｐ＋１の素因数がいくつ見つかるかが変わ
る。即ち、多く計算すれば、素数ＰがＰ＋１素因数分解
法に対する強さをより正確に知ることができ、計算量が
少なければ、Ｐ＋１素因数分解法に対する強さの正確さ
が小さくなる。従って、より強い素数Ｐを得るために
は、前記数列（１）の項数を多く計算すればよい。そし
てこの実施の形態では、上記計算量は回数入力手段によ
り入力された計算回数に従うものである。With respect to the prime number P generated in step S105, P + 1 is a composite number. In order to factor P + 1 into prime factors, the composite number N in the description of the above-mentioned Row method is calculated as P + 1
Can be replaced with The number of terms to be calculated in the sequence changes how many prime factors of P + 1 are found. That is, if the number of calculations is large, the strength of the prime number P with respect to the P + 1 prime factorization method can be known more accurately. If the calculation amount is small, the accuracy of the strength with respect to the P + 1 prime factorization method decreases. Therefore, in order to obtain a stronger prime number P, it is sufficient to calculate a larger number of terms in the sequence (1). In this embodiment, the amount of calculation depends on the number of calculations input by the number-of-times input means.
【００３１】以上のように本実施の形態で生成された素
数Ｐをもとに、公開鍵暗号の鍵を生成すれば、素因数分
解されにくい安全な鍵を生成することができる。さら
に、この実施の形態によれば、暗号を使用する目的に応
じて、素因数分解のされにくさを、自由に設定すること
ができる。As described above, if a public key encryption key is generated based on the prime number P generated in the present embodiment, a secure key that is difficult to be factorized can be generated. Further, according to this embodiment, it is possible to freely set the difficulty of performing the factorization according to the purpose of using the encryption.
【００３２】なお、本実施の形態では、ロー法による素
因数分解をする場合を説明したが、他の素因数分解法を
用いてもよい。In the present embodiment, the case where the prime factorization is performed by the Row method has been described, but another prime factorization method may be used.
【００３３】実施の形態４．実施の形態１〜３では、Ｐ
−１素因数分解法に強い素数Ｐに対して、Ｐ＋１素因数
分解法に強いか否かを判定し、強い素数Ｐを出力する方
法を説明したが、本実施の形態では、Ｐ＋１素因数分解
法に強い素数Ｐに対して、Ｐ−１素因数分解法に強いか
否かを判定し、強い素数Ｐを出力する方法を説明する。Embodiment 4 FIG. In the first to third embodiments, P
Although the method of determining whether or not the prime number P that is strong in the −1 prime factorization method is strong in the P + 1 prime factorization method and outputting the strong prime number P has been described, in the present embodiment, the method is strong in the P + 1 prime factorization method. A method of determining whether or not the prime number P is strong against the P-1 prime factorization method and outputting a strong prime number P will be described.
【００３４】まず、Ｐ＋１素因数分解法に強い素数Ｐを
生成するためには、図２のステップＳ１０４において、
Ｐ＝２ｉｒ−１を計算すればよい。この計算を行えば、
素数Ｐに対してＰ＋１の素因数に、素数Ｐとほぼ同じ大
きさの素数ｒが含まれることになる。即ち、素数ＰはＰ
＋１素因数分解法に対して強い素数となる。次にステッ
プＳ１０８において、ステップＳ１０５で生成された素
数Ｐが、Ｐ−１素因数分解法に強いか否かを判定する。
この判定は、Ｐ−１の素因数に、大きなビット数の素数
が含まれているか否かを調べることにより行う。Ｐ−１
に大きな素因数が含まれていれば、素数ＰはＰ−１素因
数分解法に強いことになり、Ｐ−１が小さな素因数のみ
で構成されていれば、Ｐ−１素因数分解法には弱いこと
になる。First, in order to generate a prime number P that is strong against the P + 1 prime factorization method, in step S104 of FIG.
What is necessary is to calculate P = 2ir-1. With this calculation,
The prime factor of P + 1 with respect to the prime number P includes a prime number r having substantially the same size as the prime number P. That is, the prime number P is P
This is a strong prime number for the +1 prime factorization method. Next, in step S108, it is determined whether the prime number P generated in step S105 is strong against the P-1 prime factorization method.
This determination is made by examining whether the prime factor of P-1 includes a prime number having a large number of bits. P-1
Contains a large prime factor, the prime number P is strong against the P-1 prime factorization method. If P-1 is composed of only small prime factors, it is weak against the P-1 prime factorization method. Become.
【００３５】以上のような方法で生成された素数Ｐは、
Ｐ＋１素因数分解法にもＰ−１素因数分解法にも強く、
素因数分解されにくいという特徴を有する。そして、本
実施の形態で生成された素数Ｐをもとに、公開鍵暗号の
鍵を生成すれば、素因数分解されにくい安全な鍵を生成
することができる。The prime number P generated by the above method is
Strong in both P + 1 and P-1 factorization methods,
It has the feature that it is difficult to factorize. Then, if a key for public key encryption is generated based on the prime number P generated in the present embodiment, it is possible to generate a secure key that is difficult to factorize.
【００３６】実施の形態５．実施の形態４では、Ｐ＋１
素因数分解法に強い素数ＰがＰ−１素因数分解法に強い
か否かを判定することについて説明したが、この実施の
形態では、判定処理としてＰ−１を実際に素因数分解す
ることについて説明する。図２のステップＳ１０５で生
成された素数Ｐに対して、Ｐ−１を素因数分解すれば、
Ｐ−１の素因数の大きさを知ることができる。大きな素
因数を有していれば、素数Ｐは強いと判定され、小さな
素因数だけで構成されている場合は、素数Ｐは弱いと判
定される。素因数分解の方法は、Ｐ−１素因数分解法、
Ｐ＋１素因数分解法の他に、ロー法、２次ふるい法、楕
円曲線法など、いずれの方法でもよい。Embodiment 5 In the fourth embodiment, P + 1
Although it has been described about determining whether a prime number P that is strong in the prime factorization method is strong in the P-1 prime factorization method, in the present embodiment, a description will be given of actually performing a prime factorization of P-1 as a determination process. . For the prime number P generated in step S105 of FIG.
It is possible to know the magnitude of the prime factor of P-1. If it has a large prime factor, the prime number P is determined to be strong, and if it is composed of only small prime factors, the prime number P is determined to be weak. The method of the prime factorization is a P-1 prime factorization method,
In addition to the P + 1 prime factorization method, any method such as the Row method, the secondary sieving method, and the elliptic curve method may be used.
【００３７】以上のような方法で生成された素数Ｐは、
Ｐ＋１素因数分解法にもＰ−１素因数分解法にも強く、
素因数分解されにくいという特徴を有する。そして、本
実施の形態で生成された素数Ｐをもとに、公開鍵暗号の
鍵を生成すれば、素因数分解されにくい安全な鍵を生成
することができる。The prime number P generated by the above method is
Strong in both P + 1 and P-1 factorization methods,
It has the feature that it is difficult to factorize. Then, if a key for public key encryption is generated based on the prime number P generated in the present embodiment, it is possible to generate a secure key that is difficult to factorize.
【００３８】実施の形態６．実施の形態５では、素数Ｐ
がＰ−１素因数分解法に強いか否かを判定する処理に素
因数分解を用いるものを示したが、この実施の形態で
は、Ｐ−１を素因数分解する計算量を可変にすることに
より、素因数分解に対する強さを可変にする場合につい
て説明する。Embodiment 6 FIG. In the fifth embodiment, the prime number P
Has been described using the prime factorization in the process of determining whether or not is strong against the P-1 prime factorization method. However, in this embodiment, the prime factorization of the P-1 A case where the strength against decomposition is made variable will be described.
【００３９】実施の形態３と同様にロー法による素因数
分解を行い、ロー法の前記数列（１）の項数を調整する
ことにより、Ｐ−１素因数分解法に対する強さを調整す
ることができる。調整するためには、実施の形態３と同
様に、計算回数を入力する回数入力手段を備え、この回
数入力手段により入力された計算回数まで前記数列
（１）を計算するようにする。As in the third embodiment, by performing the prime factorization by the row method and adjusting the number of terms in the sequence (1) of the row method, the strength to the P-1 factorization method can be adjusted. . To make the adjustment, similarly to the third embodiment, a number input unit for inputting the number of calculations is provided, and the sequence (1) is calculated up to the number of calculations input by the number input unit.
【００４０】以上のように本実施の形態で生成された素
数Ｐをもとに、公開鍵暗号の鍵を生成すれば、素因数分
解されにくい安全な鍵を生成することができる。さら
に、この実施の形態によれば、暗号を使用する目的に応
じて、素因数分解のされにくさを、自由に設定すること
ができる。As described above, if a public key encryption key is generated based on the prime number P generated in the present embodiment, a secure key that is difficult to be factorized can be generated. Further, according to this embodiment, it is possible to freely set the difficulty of performing the factorization according to the purpose of using the encryption.
【００４１】なお、本実施の形態では、ロー法による素
因数分解をする場合を説明したが、他の素因数分解法を
用いてもよい。In the present embodiment, the case where the prime factorization is performed by the Row method has been described, but another prime factorization method may be used.
【００４２】[0042]
【発明の効果】請求項１又は５の発明によれば、Ｐ−１
素因数分解法に強い第２の素数がＰ＋１素因数分解法に
強いか否かを判定し、強いと判定された第２の素数を出
力するので、Ｐ−１素因数分解法にもＰ＋１素因数分解
法にも強い素数を生成することができる。さらに、本発
明により生成された素数を用いて暗号の鍵を生成するこ
とにより、素因数分解されにくい安全な鍵を生成するこ
とができる。According to the first or fifth aspect of the present invention, P-1
It is determined whether the second prime number that is strong in the prime factorization method is strong in the P + 1 prime factorization method, and the second prime number that is determined to be strong is output. Can also generate strong prime numbers. Further, by generating a cryptographic key using the prime numbers generated according to the present invention, it is possible to generate a secure key that is difficult to be factored into.
【００４３】請求項２又は６の発明によれば、Ｐ＋１素
因数分解法に強い第２の素数がＰ−１素因数分解法に強
いか否かを判定し、強いと判定された第２の素数を出力
するので、Ｐ＋１素因数分解法にもＰ−１素因数分解法
にも強い素数を生成することができる。さらに、本発明
により生成された素数を用いて暗号の鍵を生成すること
により、素因数分解されにくい安全な鍵を生成すること
ができる。According to the second or sixth aspect of the present invention, it is determined whether a second prime number that is strong in the P + 1 prime factorization method is strong in the P-1 prime factorization method, and the second prime number determined as strong is determined. Since the output is performed, a prime number that is strong in both the P + 1 prime factorization method and the P-1 prime factorization method can be generated. Further, by generating a cryptographic key using the prime numbers generated according to the present invention, it is possible to generate a secure key that is difficult to be factored into.
【００４４】請求項３又は７の発明によれば、生成した
素数を実際に素因数分解をすることにより素因数分解に
強いか否かの判定を行なうので、素因数分解に強い素数
を生成することができる。According to the third or seventh aspect of the present invention, it is determined whether or not the generated prime number is strong in the prime factorization by actually performing the factorization, so that a prime number strong in the prime factorization can be generated. .
【００４５】請求項４又は８の発明によれば、入力され
た計算回数の素因数分解を行ないその結果に基づいて判
定するので、生成する素数Ｐの素因数分解に対する強さ
を自由に設定することができる。According to the fourth or eighth aspect of the present invention, since the input number of calculations is factored and the determination is made based on the result, it is possible to freely set the strength of the generated prime number P with respect to the factorization. it can.
【図１】 実施の形態１の素数生成装置の構成を示す構
成図である。FIG. 1 is a configuration diagram showing a configuration of a prime number generation device according to a first embodiment.
【図２】 実施の形態１の素数生成装置の動作を示すフ
ローチャートである。FIG. 2 is a flowchart illustrating an operation of the prime number generation device according to the first embodiment;
【図３】 従来の素数生成方法の動作を示すフローチャ
ートである。FIG. 3 is a flowchart showing an operation of a conventional prime number generation method.
１ 素数ｒ生成手段、２ 素数ｒ記憶手段、３ 素数Ｐ
生成手段、４ 素数Ｐ記憶手段、５ 判定手段、６ 出
力手段、７ コンピュータ、８ メモリ。1 prime r generation means, 2 prime r storage means, 3 prime P
Generation means, 4 prime P storage means, 5 determination means, 6 output means, 7 computer, 8 memory.
Claims (8)
と、 この第１の記憶手段に記憶された前記第１の素数を用い
て所定の演算を行い、Ｐ−１素因数分解法に強い第２の
素数を生成する生成手段と、 この生成手段により生成された前記第２の素数を記憶す
る第２の記憶手段と、 この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ＋１素因数分解法に強いか否
かを判定する判定手段と、 この判定手段によりＰ＋１素因数分解法に強いと判定さ
れた前記第２の素数を出力する出力手段とを備えたこと
を特徴とする素数生成装置。A first storage unit for storing a first prime number; and a predetermined operation using the first prime number stored in the first storage unit. Generating means for generating a strong second prime; second storing means for storing the second prime generated by the generating means; and storing the second prime stored in the second storing means. Determining means for determining whether the second prime is strong in the P + 1 factoring method; and outputting means for outputting the second prime number determined to be strong in the P + 1 factoring method by the determining means. A prime number generation device, comprising:
と、 この第１の記憶手段に記憶された前記第１の素数を用い
て所定の演算を行い、Ｐ＋１素因数分解法に強い第２の
素数を生成する生成手段と、 この生成手段により生成された前記第２の素数を記憶す
る第２の記憶手段と、 この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ−１素因数分解法に強いか否
かを判定する判定手段と、 この判定手段によりＰ−１素因数分解法に強いと判定さ
れた前記第２の素数を出力する出力手段とを備えたこと
を特徴とする素数生成装置。2. A first storage unit for storing a first prime number, a predetermined operation is performed using the first prime number stored in the first storage unit, and a first storage unit that is resistant to the P + 1 prime factorization method. Generating means for generating a prime number of 2; second storing means for storing the second prime number generated by the generating means; extracting the second prime number stored in the second storing means; Determining means for determining whether or not the second prime is strong in the P-1 factoring method; and outputting means for outputting the second prime number determined to be strong in the P-1 factoring method by the determining means And a prime number generation device.
の結果に基づいて判定することを特徴とする請求項１又
は２記載の素数生成装置。3. The prime number generation device according to claim 1, wherein the determination unit performs a prime factorization and determines based on a result of the factorization.
え、 前記判定手段は、前記回数入力手段により入力された前
記計算回数の素因数分解を行ないその結果に基づいて判
定することを特徴とする請求項１又は２記載の素数生成
装置。4. The apparatus according to claim 1, further comprising a number input unit for inputting the number of calculations, wherein said determination unit performs a factorization of said number of calculations input by said number input unit and makes a determination based on the result. Item 3. The prime number generation device according to item 1 or 2.
を用いて所定の演算を行い、Ｐ−１素因数分解法に強い
第２の素数を生成し、第２の記憶手段に記憶させる生成
ステップと、 この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ＋１素因数分解法に強いか否
かを判定する判定ステップと、 この判定ステップによりＰ＋１素因数分解法に強いと判
定された前記第２の素数を出力する出力ステップとを備
えたことを特徴とする素数生成方法。5. A predetermined operation is performed using the first prime number stored in the first storage means to generate a second prime number resistant to the P-1 factorization method, and stored in the second storage means. Generating a second prime number stored in the second storage means, and determining whether or not the second prime number is strong in the P + 1 prime factorization method. Outputting the second prime number determined to be strong in the prime factorization method.
を用いて所定の演算を行い、Ｐ＋１素因数分解法に強い
第２の素数を生成し、第２の記憶手段に記憶させる生成
ステップと、 この第２の記憶手段に記憶された前記第２の素数を取り
出し、この第２の素数がＰ−１素因数分解法に強いか否
かを判定する判定ステップと、 この判定ステップによりＰ−１素因数分解法に強いと判
定された前記第２の素数を出力する出力ステップとを備
えたことを特徴とする素数生成方法。6. A predetermined operation is performed using the first prime number stored in the first storage means to generate a second prime number resistant to the P + 1 prime factorization method and stored in the second storage means. A step of taking out the second prime number stored in the second storage means, and determining whether or not the second prime number is strong in the P-1 prime factorization method; An output step of outputting the second prime number determined to be strong against the -1 prime factorization method.
いその結果に基づいて判定することを特徴とする請求項
５又は６記載の素数生成方法。7. The method for generating a prime number according to claim 5, wherein the determining step performs a prime factorization and determines based on a result of the factorization.
備え、 前記判定ステップは、前記回数入力ステップにより入力
された前記計算回数の素因数分解を行ないその結果に基
づいて判定することを特徴とする請求項５又は６記載の
素数生成方法。8. The method according to claim 1, further comprising a number input step of inputting the number of calculations, wherein the determining step performs a prime factorization of the number of calculations input in the number input step and makes a determination based on the result. Item 5. The prime number generation method according to item 5 or 6.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1396397A JPH10207363A (en) | 1997-01-28 | 1997-01-28 | Device and method for generating prime number |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1396397A JPH10207363A (en) | 1997-01-28 | 1997-01-28 | Device and method for generating prime number |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH10207363A true JPH10207363A (en) | 1998-08-07 |
Family
ID=11847875
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1396397A Pending JPH10207363A (en) | 1997-01-28 | 1997-01-28 | Device and method for generating prime number |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH10207363A (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7043018B1 (en) | 1998-11-27 | 2006-05-09 | Murata Kikai Kabushiki Kaisha | Prime number generation method, prime number generation apparatus, and cryptographic system |
| JP4859933B2 (en) * | 2007-01-19 | 2012-01-25 | 三菱電機株式会社 | Ciphertext generation apparatus, cryptographic communication system, and group parameter generation apparatus |
-
1997
- 1997-01-28 JP JP1396397A patent/JPH10207363A/en active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7043018B1 (en) | 1998-11-27 | 2006-05-09 | Murata Kikai Kabushiki Kaisha | Prime number generation method, prime number generation apparatus, and cryptographic system |
| JP4859933B2 (en) * | 2007-01-19 | 2012-01-25 | 三菱電機株式会社 | Ciphertext generation apparatus, cryptographic communication system, and group parameter generation apparatus |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Renteria-Mejia et al. | High-throughput ring-LWE cryptoprocessors | |
| Pöppelmann et al. | Towards efficient arithmetic for lattice-based cryptography on reconfigurable hardware | |
| Micciancio et al. | Lattice-based cryptography | |
| Bellare et al. | How to sign given any trapdoor permutation | |
| KR20070046778A (en) | Method and apparatus for efficiently performing multiparty multiplication | |
| CN114338025B (en) | A ciphertext equivalence testing method in cloud environment | |
| US20020126838A1 (en) | Modular exponentiation calculation apparatus and modular exponentiation calculation method | |
| CN111159352A (en) | Encryption and decryption method supporting multi-keyword weighted retrieval and result sorting and capable of being verified | |
| Silverman et al. | Timing attacks on NTRUEncrypt via variation in the number of hash calls | |
| JP3833412B2 (en) | Expression data generation apparatus and method in finite field operation | |
| McCurley | Odds and ends from cryptology and computational number theory | |
| CN113708927A (en) | Universal designated verifier signature certification system based on SM2 digital signature | |
| JP3551853B2 (en) | Secure parameter generation apparatus, generation method, and recording medium in algebraic curve cryptography having a definition equation of the form αYa + βXb + 1 = 0 | |
| JPH10207363A (en) | Device and method for generating prime number | |
| CN117786751A (en) | Symmetrical searchable encryption method, device, equipment and medium | |
| Babenko et al. | Euclidean division method for the homomorphic scheme ckks | |
| KR100326226B1 (en) | Method of Generating Matix Group Public Key | |
| KR102006222B1 (en) | Apparatus and Method for Integrated Hardware Implementation of Elliptic Curve Cryptography and RSA Public-key Cryptosystem | |
| EP3419212B1 (en) | Computer implemented method, computer system and computer readable computer program product | |
| Catalano et al. | Algebraic (trapdoor) one-way functions: Constructions and applications | |
| Zhang et al. | Efficient keyword search for public-key setting | |
| Zhou et al. | Efficient privacy-preserving outsourced discrete wavelet transform in the encrypted domain | |
| JP2001154580A (en) | Method and device for generating prime numbers, and storage medium with stored program for generating prime numbers | |
| US20240430087A1 (en) | One-way functions with polynomial computation | |
| CN115001741B (en) | Data encryption method and related components |