JPH0721761B2 - Prime number determiner - Google Patents
Prime number determinerInfo
- Publication number
- JPH0721761B2 JPH0721761B2 JP60122685A JP12268585A JPH0721761B2 JP H0721761 B2 JPH0721761 B2 JP H0721761B2 JP 60122685 A JP60122685 A JP 60122685A JP 12268585 A JP12268585 A JP 12268585A JP H0721761 B2 JPH0721761 B2 JP H0721761B2
- Authority
- JP
- Japan
- Prior art keywords
- prime number
- prime
- determining
- random
- random number
- 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.)
- Expired - Lifetime
Links
- 239000002131 composite material Substances 0.000 description 16
- 238000004364 calculation method Methods 0.000 description 15
- 238000000034 method Methods 0.000 description 9
- 238000010586 diagram Methods 0.000 description 5
- RRLHMJHRFMHVNM-BQVXCWBNSA-N [(2s,3r,6r)-6-[5-[5-hydroxy-3-(4-hydroxyphenyl)-4-oxochromen-7-yl]oxypentoxy]-2-methyl-3,6-dihydro-2h-pyran-3-yl] acetate Chemical compound C1=C[C@@H](OC(C)=O)[C@H](C)O[C@H]1OCCCCCOC1=CC(O)=C2C(=O)C(C=3C=CC(O)=CC=3)=COC2=C1 RRLHMJHRFMHVNM-BQVXCWBNSA-N 0.000 description 3
- 101100524644 Toxoplasma gondii ROM4 gene Proteins 0.000 description 2
- 101100524645 Toxoplasma gondii ROM5 gene Proteins 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 150000002500 ions Chemical class 0.000 description 1
Landscapes
- Complex Calculations (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は素数判定器に関し、特に暗号通信においてキー
として使用される素数の発生に利用される素数判定器に
関する。Description: TECHNICAL FIELD The present invention relates to a prime number determiner, and more particularly to a prime number determiner used for generating a prime number used as a key in cryptographic communication.
暗号方式の中で、リベスト（Rivest）等が提案した、い
わゆるアールエスエー（RSA）公開鍵暗号系は暗号化キ
ーを秘密にしておく必要がなく、暗号通信におけるキー
の配送に有望視されている。RSA公開鍵暗号系はコミュ
ニケーションズ・オブ・ザ・エーシーエム（Communicat
ions of the ACM）（以下文献（１））の1978年21巻
２号の120頁から126頁に記載される。このRSA公開鍵暗
号系においてはキーを作るにあたり100桁程度の大きな
素数が必要である。大きな素数を生成するには、ランダ
ムに奇数を生成してその奇数が素数であるか否かを判定
することによって行われる。上記文献（１）によれば、
100桁の素数を生成するときには、１つの素数を得るま
でに約115回ぐらい素数候補を生成する必要がある。Among the cryptosystems, the so-called RSA public key cryptosystem proposed by Rivest etc. does not require keeping the encryption key secret, and is considered promising for key distribution in cryptographic communication. . The RSA public key cryptosystem is based on Communications of the ACM.
ions of the ACM) (hereinafter referred to as Reference (1)), Vol. 21, No. 2, 1978, pp. 120-126. In this RSA public key cryptosystem, a large prime number of about 100 digits is required to create a key. Generating a large prime number is performed by randomly generating an odd number and determining whether the odd number is a prime number. According to the above document (1),
When generating a 100-digit prime number, it is necessary to generate the prime number candidate about 115 times before obtaining one prime number.
従来から知られる素数判定法としては、上記文献（１）
に記載されるソロベイ・ストラッセンの方法や、ヌース
（Knuth）著、ジ・アート・オブ・コンピュータ・プロ
グラミング（The Art of Computer Programming）（以
下文献（２））の第２巻改訂版の374頁から380頁に記載
されるラビンの方法がある。As a conventionally known method of determining a prime number, the above-mentioned document (1) is used.
The Solobay Strassen method described in, and Knuth, The Art of Computer Programming (Reference (2)), Volume 2, revised page 374. To the Rabin method described on page 380.
ここで上記ソロベイ・ストラッセンの方法を説明する。
下記にソロベイ・ストラッセンの方法のアルゴリズムを
示す。Here, the method of Solobay Strassen will be described.
The algorithm of Solobay-Strassen's method is shown below.
ステップ101 Ｎ←素数候補（奇数）、Ｉ←０ ステップ102 乱数Ａを生成 ステップ103 gcd（A,N）≠１ならば終了、Ｎは合成数 ステップ104 ならば終了、Ｎは合成数 ステップ105 Ｉ＜Ｄならば、Ｉ←Ｉ＋１としてステッ
プ102へ I≧Ｄならば終了、Ｎは素数 上記アルゴリズムにおいて、N,Iは変数、Ｄは100程度の
値、（A/N）はヤコビの記号、ｘ≡ｙ（mod n）はｘ−ｙ
がｎで割切れることを意味する。詳細については文献
（１）に記述されている。Step 101 N ← prime number candidate (odd number), I ← 0 Step 102 Generate random number A Step 103 End if gcd (A, N) ≠ 1, N is composite number Step 104 If so, N is a composite number. Step 105 If I <D, set I ← I + 1 and go to step 102. If I ≧ D, end. N is a prime number. In the above algorithm, N and I are variables, D is a value of about 100, (A / N) is the Jacobi symbol, x≡y (mod n) is xy
Means divisible by n. Details are described in Reference (1).
かかるソロベイ・ストラッセンの方法においては、 Ｎが合成数のときは、小さい素数を因数に持つことが
多い、 素数でないのに 又は になることは非常に少ない、という特長を利用していな
い。In such a Solobaye-Strassen method, when N is a composite number, it often has a small prime number as a factor. Or It does not take advantage of the fact that it is very rare.
その結果、ソロベイ・ストラッセンの方法で素数を判定
する場合には多くの計算処理を行う必要があり、時間を
要するという問題を有していた。この問題は上記のラビ
ンの方法においても同様に発生する。As a result, there is a problem in that it is necessary to perform a lot of calculation processing when determining a prime number by the Solobaye-Strassen method, which requires time. This problem also occurs in the Rabin method described above.
本発明の目的は、上記特長，を考慮して、計算処理
を少なくし素数判定時間を短縮した素数判定器を提供す
ることにある。SUMMARY OF THE INVENTION An object of the present invention is to provide a prime number determiner in which the calculation process is reduced and the prime number determination time is shortened in consideration of the above features.
本発明の第１発明は、与えられた正整数Ｎが素数である
か否かを判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対して が１でもＮ−１でもなければＮは素数でないと判定する
第２判定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段、 とから構成したことを特徴としている。A first aspect of the present invention is a prime number determiner that determines whether or not a given positive integer N is a prime number, wherein N is not a prime number unless N is coprime to a predetermined positive integer M. First determining means for determining, random number generating means for generating random numbers of positive integers, and when the first determining means does not determine that N is not a prime number, for the integer A generated by the random number generating means Is not 1 or N−1, N is not a prime number, and the second judgment unit determines that N is not a prime number for an arbitrary number of random numbers generated by the random number generation unit. The third determination means determines that N is a prime number when there is no such information.
また本発明の第２発明は、与えられた正整数Ｎが素数で
あるか否かを判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対してAN-1（mo
d N）が１でなければＮは素数でないと判定する第２判
定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段と、 から構成したことを特徴としている。A second aspect of the present invention is a prime number determiner that determines whether or not a given positive integer N is a prime number, and N is not a prime number unless N is coprime to a predetermined positive integer M. A first determination means for determining that the random number is a positive integer, and a random number generation means for generating a random number of a positive integer; and when the first determination means does not determine that N is not a prime number, the integer A generated by the random number generation means is A N-1 (mo
If d N) is not 1, second determining means determines that N is not a prime number, and the second determining means does not determine that N is not a prime number for an arbitrary number of random numbers generated by the random number generating means. And a third determining means for determining N to be a prime number.
以下に、図面を用いて本発明の実施例を説明する。 Embodiments of the present invention will be described below with reference to the drawings.
第１図は本発明に係る素数判定器の装置構成を示すブロ
ック図である。この図において、乱数発生回路１は整数
の乱数Ａを発生し、gcd（最大公約数）計算回路２は２
つの整数の最大公約数を計算し、巾乗剰余回路３は巾乗
剰余を計算する機能を有する。ROM4はプログラムや定数
を記憶し、RAM5は上記計算で得たデータを一時的に記憶
し、プロセッサ６はデータの授受や各回路の動作の制
御、判断等を行うものである。上記のような装置構成は
例えば計算機システムによって実現される。FIG. 1 is a block diagram showing a device configuration of a prime number judging device according to the present invention. In this figure, a random number generation circuit 1 generates an integer random number A, and a gcd (greatest common divisor) calculation circuit 2 generates 2
The greatest common divisor of two integers is calculated, and the power-residue circuit 3 has a function of calculating the power-residue. The ROM 4 stores programs and constants, the RAM 5 temporarily stores the data obtained by the above calculation, and the processor 6 exchanges data, controls the operation of each circuit, and makes decisions. The device configuration as described above is realized by, for example, a computer system.
第２図、第３図は本発明における第１発明、第２発明の
素数判定器の動作を説明するためのフローチャートであ
り、いずれの素数判定器も第１図で示した構成を有す
る。2 and 3 are flow charts for explaining the operation of the prime number discriminators of the first and second aspects of the present invention, and each of the prime number discriminators has the configuration shown in FIG.
まず第２図のフローチャートによって第１発明に係る素
数判定器の動作について説明する。第１図において、バ
ス７を通して外部から与えられた素数候補（奇数の正整
数）を変数Ｎに置き、且つカウンタをなす変数Ｉを０に
置くと共にROM4内に記憶されている小さい素数の積（正
整数）を変数Ｎに置く（ステップ201）。この場合Ｍは
例えば100以下の素数の積である。上記ＮとＭはgcd計算
回路２に送られる。gcd計算回路２はＮとＭの最大公約
数gcd（M,N）を求め、gcd（M,N）を変数Ｇに置く（ステ
ップ202）。プロセッサ６はgcd計算回路２で求められた
Ｇが１でなければＮは素数ではない、すなわち合成数で
あると判断する（ステップ203）。一方Ｇが１であれ
ば、プロセッサ６は、乱数発生回路１によって乱数Ａを
発生させ（ステップ204）、この発生した乱数Ａと上記
Ｎとを巾乗剰余回路３に送り、この巾乗剰余回路３にお
いて なるＢを計算させる（ステップ205）。求めたＢが１で
もＮ−１でもなければ、プロセッサ６はＮは合成数であ
ると判断する（ステップ206）。一方Ｂが１又はＮ−１
であるときには、Ｉ＝Ｉ＋１として（ステップ207）、
ステップ204に戻り、乱数発生回路１で再び新しい乱数
Ａを発生し、上記処理を繰返す。そしてＩが予め定めら
れた定数Ｄと等しくなるまでＮが合成数と判断されなか
ったならば（ステップ208）、プロセッサ６は、Ｎは素
数であると判断する（ステップ209）。この場合Ｄは例
えば20程度に定められるが、前記の性質上５程度に定
めることができる。このようにして得られたプロセッサ
６の判断結果はバス７を通じて外部回路に通知される。First, the operation of the prime number determiner according to the first aspect of the invention will be described with reference to the flowchart of FIG. In FIG. 1, a prime number candidate (odd positive integer) given from the outside through the bus 7 is set in a variable N, a variable I forming a counter is set at 0, and a product of small prime numbers stored in the ROM 4 ( Place a positive integer in the variable N (step 201). In this case, M is a product of prime numbers less than 100, for example. The N and M are sent to the gcd calculation circuit 2. The gcd calculation circuit 2 finds the greatest common divisor gcd (M, N) of N and M, and puts gcd (M, N) in the variable G (step 202). The processor 6 determines that N is not a prime number, that is, a composite number, unless G obtained by the gcd calculation circuit 2 is 1 (step 203). On the other hand, if G is 1, the processor 6 causes the random number generation circuit 1 to generate a random number A (step 204), sends the generated random number A and the above N to the power-residue circuit 3, and the power-residue circuit. In three B is calculated (step 205). If the obtained B is neither 1 nor N-1, the processor 6 determines that N is a composite number (step 206). On the other hand, B is 1 or N-1
If, then I = I + 1 (step 207),
Returning to step 204, the random number generating circuit 1 again generates a new random number A, and the above processing is repeated. If N is not determined to be a composite number until I becomes equal to a predetermined constant D (step 208), the processor 6 determines that N is a prime number (step 209). In this case, D is set to, for example, about 20, but can be set to about 5 due to the above-mentioned property. The judgment result of the processor 6 thus obtained is notified to the external circuit through the bus 7.
上記の素数判定器の動作のアルゴリズムを示すと下記の
如くなる。The algorithm of the operation of the above prime number judging device is as follows.
ステップ201 Ｎ←素数候補、Ｉ←０、Ｍ←小さい素数
の積 ステップ202,203 gcd（M,N）≠１ならば終了、Ｎは合
成数 ステップ204 乱数Ａを生成 ステップ205,206 ならば終了、Ｎは合成数 ステップ207,208 Ｉ＜Ｄならば、Ｉ←Ｉ＋１としてス
テップ204へ I≧Ｄならば終了、Ｎは素数 かかるアルゴリズムはROM4に記憶されたプログラムに基
づきプロセッサ６が乱数発生回路１等の構成要素を動作
させて実行する。Step 201 N ← prime candidate, I ← 0, M ← product of small primes Step 202,203 End if gcd (M, N) ≠ 1, N is composite number Step 204 Generate random number A Steps 205,206 If so, N is a composite number. Step 207,208 If I <D, I ← I + 1 and go to step 204. If I ≧ D, then end. N is a prime number. The algorithm is based on the program stored in ROM4. Operate and execute components such as 1.
上記アルゴリズムを従来のソロベイ・ストラッセン法の
アルゴリズムと比較すると、前記を考慮してステップ
202,203を入れて高速化を図っている。また前記ステッ
プ104において、（A/N）が±１に限られることから、こ
れを用いて か否かを調べるようにする。そうすると前記に基づい
てＮが合成数であるならばこれをほとんど検出すること
ができる。従ってＤ個の乱数Ａすべてに対して であるならば、Ｎは素数と判断することができる。この
結果、前記ステップ104はステップ205,206に置き換えら
れ、（A/N）を計算する必要がなくなる。またステップ1
03はステップ202,203を設けると、その必要性が少なく
なる。このことは、もしgcd（A,N）≠１であるならば、
前記によりＮは小さい因数を含むことが多く、そのと
きはステップ202,203でＮは合成数であると判定される
からである。そこで、ステップ103を除いてステップ20
2,203を設けると、本来ステップ103はステップ202,203
よりもアルゴリズム上通過回数が多いので、全体として
計算処理量が少なくなる。なおステップ103で合成数と
判定されるＮは、必ずステップ205,206で合成数と判定
されるので、ステップ103を除いても素数判定能力は変
わらない。Comparing the above algorithm with the conventional Solobay-Strassen algorithm, in consideration of the above,
202 and 203 are put in to achieve high speed. In step 104, (A / N) is limited to ± 1. Try to check whether or not. Then, based on the above, if N is a composite number, this can be almost detected. Therefore, for all D random numbers A , N can be determined to be a prime number. As a result, step 104 is replaced by steps 205 and 206, and it is not necessary to calculate (A / N). Also step 1
If step 203 and step 203 are provided in 03, the necessity thereof is reduced. This means that if gcd (A, N) ≠ 1, then
This is because N often includes a small factor as described above, and in that case, N is determined to be a composite number in steps 202 and 203. Therefore, except step 103, step 20
If 2,203 is provided, step 103 is originally step 202,203
Since the number of passing times is larger than that in the algorithm, the amount of calculation processing is reduced as a whole. Note that N, which is determined to be a composite number in step 103, is always determined to be a composite number in steps 205 and 206, so the prime number determination capability does not change even if step 103 is excluded.
以上により、上記実施例における素数判定器のアルゴリ
ズムは従来法のアルゴリズムに比べて、計算処理量が少
なくなり、高速に動作する。As described above, the algorithm of the prime number determiner in the above embodiment has a smaller amount of calculation processing and operates faster than the conventional algorithm.
上記の如く動作する素数判定器を機能ブロック図で示す
と第４図のようになる。第４図において、８は第１判定
手段で、gcd計算回路２とROM4とRAM5とプロセッサ６か
ら構成され、前記ステップ201,202,203を実行する。９
は乱数発生手段で、乱数発生回路１で構成され、ステッ
プ204を実行する。10は第２判定手段で、巾乗剰余回路
３とRAM5とプロセッサ６とから構成され、前記ステップ
205,206を実行する。11は第３判定手段で、ROM4とROM5
とプロセッサ６から構成され、前記ステップ207,208を
実行する。このように本実施例では第１、第２、第３の
判定手段を備え、第１判定手段８においてＮは非合成数
であると判定されたときに、第２判定手段10と第３判定
手段11による判定動作を繰返すように構成した。A functional block diagram of the prime number determiner that operates as described above is as shown in FIG. In FIG. 4, reference numeral 8 is a first judging means, which is composed of a gcd calculating circuit 2, a ROM 4, a RAM 5 and a processor 6, and executes the steps 201, 202 and 203. 9
Is a random number generating means, which is constituted by the random number generating circuit 1, and executes step 204. Reference numeral 10 is a second determination means, which is composed of a power-residue circuit 3, a RAM 5, and a processor 6, and
Execute 205 and 206. 11 is the third judging means, ROM4 and ROM5
And the processor 6, and executes the steps 207 and 208. As described above, the present embodiment is provided with the first, second, and third determination means, and when the first determination means 8 determines that N is a non-composite number, the second determination means 10 and the third determination means. The determination operation by means 11 is repeated.
次に第３図のフローチャートによって第２発明に係る素
数判定器について説明する。この第２発明は第１発明を
改良したものである。第３図において、ステップ301,30
2,303,304,307,308,309は、第２図で説明したステップ2
01,202,203,204,207,208,209と全く同じであるため説明
を省略する。この第２発明に係る素数判定器では、ステ
ップ305において、巾乗剰余回路３を用いてＢ＝AN-1（m
od N）なるＢを計算で求め、このＢが１であるか否かに
よってＮが合成数であるか否かを判断するように構成さ
れる（ステップ306）。Next, the prime number judging device according to the second aspect of the invention will be described with reference to the flowchart of FIG. The second invention is an improvement of the first invention. In FIG. 3, steps 301, 30
2,303,304,307,308,309 are step 2 explained in FIG.
Since it is exactly the same as 01, 202, 203, 204, 207, 208, 209, its explanation is omitted. In the prime number judging device according to the second aspect of the present invention, in step 305, B = A N-1 (m
od N) is calculated, and whether or not N is a composite number is determined depending on whether or not B is 1 (step 306).
ここで上記素数判定器の動作のアルゴリズムを示すと、 ステップ301 Ｎ←素数候補、Ｉ←０、Ｍ←小さい素数
の積 ステップ302,303 gcd（M,N）≠１ならば終了、Ｎは合
成数 ステップ304 乱数Ａを生成 ステップ305,306 ならば終了、Ｎは合成数 ステップ307,308 Ｉ＜ＤならばＩ←Ｉ＋１としてステ
ップ304へ I≧Ｄならば終了、Ｎは素数 となる。従って前記第１発明に係る素数判定器と同様
に、且つ前記を考慮してステップ305,306を設けるよ
うにしたため、計算処理量を少なくし、高速に素数の判
定動作を行うことができる。Here, the algorithm of the operation of the above-mentioned prime number judging device is as follows: Step 301 N ← prime number candidate, I ← 0, M ← product of small prime numbers Step 302,303 end if gcd (M, N) ≠ 1, N is a composite number step 304 Generate random number A Step 305,306 If so, N is a composite number. Steps 307 and 308 If I <D, I ← I + 1 and go to step 304. If I ≧ D, end. N is a prime number. Therefore, similar to the prime number judging device according to the first aspect of the present invention, and since the steps 305 and 306 are provided in consideration of the above, it is possible to reduce the calculation processing amount and perform the prime number judging operation at high speed.
また第２発明に係る素数判定器を機能ブロック図で表わ
すと前記第１発明と同様に第４図に示すようになる。た
だしこの場合の第２判定手段10は上記ステップ305,306
を実行することになる。Further, the prime number judging device according to the second invention is shown in a functional block diagram as shown in FIG. 4 as in the first invention. However, in this case, the second determination means 10 performs the above steps 305 and 306.
Will be executed.
上記各発明に係る素数判定器において、乱数発生回路１
で発生する乱数は、自然乱数、疑似乱数であってもよ
い。またgcd計算回路２については前記文献（２）の316
頁〜339頁に記載され、巾乗余剰回路３は例えば情報処
理学会論文誌第24巻６号764頁〜771頁（1983）に記載さ
れているものを用いることができる。更に乱数発生回路
１、gcd計算回路２、巾乗剰余回路３はプロセッサ６、
又は別の専用プロセッサで実行させることもできる。In the prime number judging device according to each of the above inventions, the random number generating circuit 1
The random number generated in step 1 may be a natural random number or a pseudo random number. Further, regarding the gcd calculation circuit 2, 316 of the above-mentioned document (2)
For example, the exponentiation surplus circuit 3 described in pages 339 to 339 can be used as described in IPSJ Journal, Volume 24, No. 6, pages 764 to 771 (1983). Further, the random number generation circuit 1, the gcd calculation circuit 2, the exponentiation remainder circuit 3, the processor 6,
Alternatively, it may be executed by another dedicated processor.
なお、上記各素数判定器は、乱数発生回路１で発生され
る乱数を素数候補として用いて上記素数判定を行うよう
に構成すれば、容易に素数発生器として構成し直すこと
ができる。It should be noted that each of the prime number determining devices can be easily reconfigured as a prime number generating device if it is configured to perform the above-mentioned prime number determination using a random number generated by the random number generating circuit 1 as a prime number candidate.
以上説明した通り本発明によれば、従来の素数判定器に
対してその数及び計算上の特長を考慮して若干の改良を
施すことによって計算処理量を著しく少なくすることが
でき、これによって高速に素数判定を行うことができ
る。As described above, according to the present invention, the amount of calculation processing can be remarkably reduced by slightly improving the conventional prime number determiner in consideration of the number and the characteristic of calculation, and thereby the high speed operation can be achieved. The prime number can be determined.
第１図は素数判定器の装置構成図、 第２図は第１発明に係る素数判定器の判定動作を示すフ
ローチャート、 第３図は第２発明に係る素数判定器の判定動作を示すフ
ローチャート、 第４図は第１発明及び第２発明に係る素数判定器の機能
ブロック図である。 １……乱数発生回路 ２……gcd計算回路 ３……巾乗剰余回路 ４……ROM ５……RAM ６……プロセッサ ８……第１判定手段 ９……乱数発生手段 10……第２判定手段 11……第３判定手段FIG. 1 is a device configuration diagram of a prime number determiner, FIG. 2 is a flowchart showing a determination operation of a prime number determiner according to the first invention, and FIG. 3 is a flowchart showing a determination operation of a prime number determiner according to the second invention, FIG. 4 is a functional block diagram of a prime number determiner according to the first invention and the second invention. 1 ... Random number generation circuit 2 ... gcd calculation circuit 3 ... Exponentiation remainder circuit 4 ... ROM 5 ... RAM 6 ... Processor 8 ... First determination means 9 ... Random number generation means 10 ... Second determination Means 11 ... Third judging means
Claims (2)
判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対して が１でもＮ−１でもなければＮは素数でないと判定する
第２判定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段、 とから成ることを特徴とする素数判定器。1. A prime number determiner for determining whether or not a given positive integer N is a prime number, wherein N is not a prime number unless said N is coprime to a predetermined positive integer M. 1 determination means, a random number generation means for generating a random number of a positive integer, and the integer A generated by the random number generation means when the first determination means does not determine that N is not a prime number. Is not 1 or N−1, N is not a prime number, and the second judgment unit determines that N is not a prime number for an arbitrary number of random numbers generated by the random number generation unit. And a third determining means for determining that N is a prime number when there is no such number, and a prime number determining device.
判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対してAN-1（mo
d N）が１でなければＮは素数でないと判定する第２判
定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段と、 から成ることを特徴とする素数判定器。2. A prime number determiner for determining whether or not a given positive integer N is a prime number, wherein N is not a prime number unless said N is relatively prime to a predetermined positive integer M. 1 determination means, random number generation means for generating random numbers of positive integers, and A N-1 (for the integer A generated by the random number generation means when the first determination means does not determine that N is not a prime number) mo
If d N) is not 1, second determining means determines that N is not a prime number, and the second determining means does not determine that N is not a prime number for an arbitrary number of random numbers generated by the random number generating means. And a third determining means for determining that N is a prime number when
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60122685A JPH0721761B2 (en) | 1985-06-07 | 1985-06-07 | Prime number determiner |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60122685A JPH0721761B2 (en) | 1985-06-07 | 1985-06-07 | Prime number determiner |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61281333A JPS61281333A (en) | 1986-12-11 |
| JPH0721761B2 true JPH0721761B2 (en) | 1995-03-08 |
Family
ID=14842089
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60122685A Expired - Lifetime JPH0721761B2 (en) | 1985-06-07 | 1985-06-07 | Prime number determiner |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0721761B2 (en) |
-
1985
- 1985-06-07 JP JP60122685A patent/JPH0721761B2/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS61281333A (en) | 1986-12-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Comba | Exponentiation cryptosystems on the IBM PC | |
| Khalique et al. | Implementation of elliptic curve digital signature algorithm | |
| Odlyzko | Discrete logarithms in finite fields and their cryptographic significance | |
| Handschuh et al. | Smart card crypto-coprocessors for public-key cryptography | |
| US6266688B1 (en) | Scheme for arithmetic operations in finite field and group operations over elliptic curves realizing improved computational speed | |
| Robshaw et al. | Elliptic curve cryptosystems | |
| US6795553B1 (en) | Method and apparatus for modular inversion for information security and recording medium with a program for implementing the method | |
| JP4137385B2 (en) | Encryption method using public and private keys | |
| US7000110B1 (en) | One-way function generation method, one-way function value generation device, proving device, authentication method, and authentication device | |
| Bernstein et al. | On the correct use of the negation map in the Pollard rho method | |
| US20070064930A1 (en) | Modular exponentiation with randomized exponent | |
| US20020041683A1 (en) | Method for selecting optimal number of prime factors of a modulus for use in a cryptographic system | |
| EP1038371A1 (en) | Transformation methods for optimizing elliptic curve cryptographic computations | |
| EP0952697B1 (en) | Elliptic curve encryption method and system | |
| US7346637B2 (en) | Polynomial time deterministic method for testing primality of numbers | |
| JPH10500502A (en) | Public key encryption method based on discrete logarithm | |
| Moon et al. | Fast VLSI arithmetic algorithms for high-security elliptic curve cryptographic applications | |
| US20070206789A1 (en) | Elliptic curve cryptosystem optimization using two phase key generation | |
| Nikolay | Digital signature scheme based on a new hard problem | |
| US6609141B1 (en) | Method of performing modular inversion | |
| JPH0721761B2 (en) | Prime number determiner | |
| JPH0766322B2 (en) | Prime number determiner | |
| US20040028223A1 (en) | Generation of a random number that is non-divisible by a set of prime numbers | |
| CN101243388A (en) | Circuit arrangement and method for performing an inversion operation in cryptographic calculations | |
| Moldovyan et al. | Short signatures from the difficulty of factoring problem |