JPH0721761B2 - 素数判定器 - Google Patents
素数判定器Info
- 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
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は素数判定器に関し、特に暗号通信においてキー
として使用される素数の発生に利用される素数判定器に
関する。
として使用される素数の発生に利用される素数判定器に
関する。
暗号方式の中で、リベスト（Rivest）等が提案した、い
わゆるアールエスエー（RSA）公開鍵暗号系は暗号化キ
ーを秘密にしておく必要がなく、暗号通信におけるキー
の配送に有望視されている。RSA公開鍵暗号系はコミュ
ニケーションズ・オブ・ザ・エーシーエム（Communicat
ions of the ACM）（以下文献（１））の1978年21巻
２号の120頁から126頁に記載される。このRSA公開鍵暗
号系においてはキーを作るにあたり100桁程度の大きな
素数が必要である。大きな素数を生成するには、ランダ
ムに奇数を生成してその奇数が素数であるか否かを判定
することによって行われる。上記文献（１）によれば、
100桁の素数を生成するときには、１つの素数を得るま
でに約115回ぐらい素数候補を生成する必要がある。
わゆるアールエスエー（RSA）公開鍵暗号系は暗号化キ
ーを秘密にしておく必要がなく、暗号通信におけるキー
の配送に有望視されている。RSA公開鍵暗号系はコミュ
ニケーションズ・オブ・ザ・エーシーエム（Communicat
ions of the ACM）（以下文献（１））の1978年21巻
２号の120頁から126頁に記載される。このRSA公開鍵暗
号系においてはキーを作るにあたり100桁程度の大きな
素数が必要である。大きな素数を生成するには、ランダ
ムに奇数を生成してその奇数が素数であるか否かを判定
することによって行われる。上記文献（１）によれば、
100桁の素数を生成するときには、１つの素数を得るま
でに約115回ぐらい素数候補を生成する必要がある。
従来から知られる素数判定法としては、上記文献（１）
に記載されるソロベイ・ストラッセンの方法や、ヌース
（Knuth）著、ジ・アート・オブ・コンピュータ・プロ
グラミング（The Art of Computer Programming）（以
下文献（２））の第２巻改訂版の374頁から380頁に記載
されるラビンの方法がある。
に記載されるソロベイ・ストラッセンの方法や、ヌース
（Knuth）著、ジ・アート・オブ・コンピュータ・プロ
グラミング（The Art of Computer Programming）（以
下文献（２））の第２巻改訂版の374頁から380頁に記載
されるラビンの方法がある。
ここで上記ソロベイ・ストラッセンの方法を説明する。
下記にソロベイ・ストラッセンの方法のアルゴリズムを
示す。
下記にソロベイ・ストラッセンの方法のアルゴリズムを
示す。
ステップ101 Ｎ←素数候補（奇数）、Ｉ←０ ステップ102 乱数Ａを生成 ステップ103 gcd（A,N）≠１ならば終了、Ｎは合成数 ステップ104 ならば終了、Ｎは合成数 ステップ105 Ｉ＜Ｄならば、Ｉ←Ｉ＋１としてステッ
プ102へ I≧Ｄならば終了、Ｎは素数 上記アルゴリズムにおいて、N,Iは変数、Ｄは100程度の
値、（A/N）はヤコビの記号、ｘ≡ｙ（mod n）はｘ−ｙ
がｎで割切れることを意味する。詳細については文献
（１）に記述されている。
プ102へ I≧Ｄならば終了、Ｎは素数 上記アルゴリズムにおいて、N,Iは変数、Ｄは100程度の
値、（A/N）はヤコビの記号、ｘ≡ｙ（mod n）はｘ−ｙ
がｎで割切れることを意味する。詳細については文献
（１）に記述されている。
かかるソロベイ・ストラッセンの方法においては、 Ｎが合成数のときは、小さい素数を因数に持つことが
多い、 素数でないのに 又は になることは非常に少ない、という特長を利用していな
い。
多い、 素数でないのに 又は になることは非常に少ない、という特長を利用していな
い。
その結果、ソロベイ・ストラッセンの方法で素数を判定
する場合には多くの計算処理を行う必要があり、時間を
要するという問題を有していた。この問題は上記のラビ
ンの方法においても同様に発生する。
する場合には多くの計算処理を行う必要があり、時間を
要するという問題を有していた。この問題は上記のラビ
ンの方法においても同様に発生する。
本発明の目的は、上記特長，を考慮して、計算処理
を少なくし素数判定時間を短縮した素数判定器を提供す
ることにある。
を少なくし素数判定時間を短縮した素数判定器を提供す
ることにある。
本発明の第１発明は、与えられた正整数Ｎが素数である
か否かを判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対して が１でもＮ−１でもなければＮは素数でないと判定する
第２判定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段、 とから構成したことを特徴としている。
か否かを判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対して が１でもＮ−１でもなければＮは素数でないと判定する
第２判定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段、 とから構成したことを特徴としている。
また本発明の第２発明は、与えられた正整数Ｎが素数で
あるか否かを判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対してAN-1（mo
d N）が１でなければＮは素数でないと判定する第２判
定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段と、 から構成したことを特徴としている。
あるか否かを判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対してAN-1（mo
d N）が１でなければＮは素数でないと判定する第２判
定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段と、 から構成したことを特徴としている。
以下に、図面を用いて本発明の実施例を説明する。
第１図は本発明に係る素数判定器の装置構成を示すブロ
ック図である。この図において、乱数発生回路１は整数
の乱数Ａを発生し、gcd（最大公約数）計算回路２は２
つの整数の最大公約数を計算し、巾乗剰余回路３は巾乗
剰余を計算する機能を有する。ROM4はプログラムや定数
を記憶し、RAM5は上記計算で得たデータを一時的に記憶
し、プロセッサ６はデータの授受や各回路の動作の制
御、判断等を行うものである。上記のような装置構成は
例えば計算機システムによって実現される。
ック図である。この図において、乱数発生回路１は整数
の乱数Ａを発生し、gcd（最大公約数）計算回路２は２
つの整数の最大公約数を計算し、巾乗剰余回路３は巾乗
剰余を計算する機能を有する。ROM4はプログラムや定数
を記憶し、RAM5は上記計算で得たデータを一時的に記憶
し、プロセッサ６はデータの授受や各回路の動作の制
御、判断等を行うものである。上記のような装置構成は
例えば計算機システムによって実現される。
第２図、第３図は本発明における第１発明、第２発明の
素数判定器の動作を説明するためのフローチャートであ
り、いずれの素数判定器も第１図で示した構成を有す
る。
素数判定器の動作を説明するためのフローチャートであ
り、いずれの素数判定器も第１図で示した構成を有す
る。
まず第２図のフローチャートによって第１発明に係る素
数判定器の動作について説明する。第１図において、バ
ス７を通して外部から与えられた素数候補（奇数の正整
数）を変数Ｎに置き、且つカウンタをなす変数Ｉを０に
置くと共にROM4内に記憶されている小さい素数の積（正
整数）を変数Ｎに置く（ステップ201）。この場合Ｍは
例えば100以下の素数の積である。上記ＮとＭはgcd計算
回路２に送られる。gcd計算回路２はＮとＭの最大公約
数gcd（M,N）を求め、gcd（M,N）を変数Ｇに置く（ステ
ップ202）。プロセッサ６はgcd計算回路２で求められた
Ｇが１でなければＮは素数ではない、すなわち合成数で
あると判断する（ステップ203）。一方Ｇが１であれ
ば、プロセッサ６は、乱数発生回路１によって乱数Ａを
発生させ（ステップ204）、この発生した乱数Ａと上記
Ｎとを巾乗剰余回路３に送り、この巾乗剰余回路３にお
いて なるＢを計算させる（ステップ205）。求めたＢが１で
もＮ−１でもなければ、プロセッサ６はＮは合成数であ
ると判断する（ステップ206）。一方Ｂが１又はＮ−１
であるときには、Ｉ＝Ｉ＋１として（ステップ207）、
ステップ204に戻り、乱数発生回路１で再び新しい乱数
Ａを発生し、上記処理を繰返す。そしてＩが予め定めら
れた定数Ｄと等しくなるまでＮが合成数と判断されなか
ったならば（ステップ208）、プロセッサ６は、Ｎは素
数であると判断する（ステップ209）。この場合Ｄは例
えば20程度に定められるが、前記の性質上５程度に定
めることができる。このようにして得られたプロセッサ
６の判断結果はバス７を通じて外部回路に通知される。
数判定器の動作について説明する。第１図において、バ
ス７を通して外部から与えられた素数候補（奇数の正整
数）を変数Ｎに置き、且つカウンタをなす変数Ｉを０に
置くと共にROM4内に記憶されている小さい素数の積（正
整数）を変数Ｎに置く（ステップ201）。この場合Ｍは
例えば100以下の素数の積である。上記ＮとＭはgcd計算
回路２に送られる。gcd計算回路２はＮとＭの最大公約
数gcd（M,N）を求め、gcd（M,N）を変数Ｇに置く（ステ
ップ202）。プロセッサ６はgcd計算回路２で求められた
Ｇが１でなければＮは素数ではない、すなわち合成数で
あると判断する（ステップ203）。一方Ｇが１であれ
ば、プロセッサ６は、乱数発生回路１によって乱数Ａを
発生させ（ステップ204）、この発生した乱数Ａと上記
Ｎとを巾乗剰余回路３に送り、この巾乗剰余回路３にお
いて なるＢを計算させる（ステップ205）。求めたＢが１で
もＮ−１でもなければ、プロセッサ６はＮは合成数であ
ると判断する（ステップ206）。一方Ｂが１又はＮ−１
であるときには、Ｉ＝Ｉ＋１として（ステップ207）、
ステップ204に戻り、乱数発生回路１で再び新しい乱数
Ａを発生し、上記処理を繰返す。そしてＩが予め定めら
れた定数Ｄと等しくなるまでＮが合成数と判断されなか
ったならば（ステップ208）、プロセッサ６は、Ｎは素
数であると判断する（ステップ209）。この場合Ｄは例
えば20程度に定められるが、前記の性質上５程度に定
めることができる。このようにして得られたプロセッサ
６の判断結果はバス７を通じて外部回路に通知される。
上記の素数判定器の動作のアルゴリズムを示すと下記の
如くなる。
如くなる。
ステップ201 Ｎ←素数候補、Ｉ←０、Ｍ←小さい素数
の積 ステップ202,203 gcd（M,N）≠１ならば終了、Ｎは合
成数 ステップ204 乱数Ａを生成 ステップ205,206 ならば終了、Ｎは合成数 ステップ207,208 Ｉ＜Ｄならば、Ｉ←Ｉ＋１としてス
テップ204へ I≧Ｄならば終了、Ｎは素数 かかるアルゴリズムはROM4に記憶されたプログラムに基
づきプロセッサ６が乱数発生回路１等の構成要素を動作
させて実行する。
の積 ステップ202,203 gcd（M,N）≠１ならば終了、Ｎは合
成数 ステップ204 乱数Ａを生成 ステップ205,206 ならば終了、Ｎは合成数 ステップ207,208 Ｉ＜Ｄならば、Ｉ←Ｉ＋１としてス
テップ204へ I≧Ｄならば終了、Ｎは素数 かかるアルゴリズムはROM4に記憶されたプログラムに基
づきプロセッサ６が乱数発生回路１等の構成要素を動作
させて実行する。
上記アルゴリズムを従来のソロベイ・ストラッセン法の
アルゴリズムと比較すると、前記を考慮してステップ
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を除いても素数判定能力は変
わらない。
アルゴリズムと比較すると、前記を考慮してステップ
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を除いても素数判定能力は変
わらない。
以上により、上記実施例における素数判定器のアルゴリ
ズムは従来法のアルゴリズムに比べて、計算処理量が少
なくなり、高速に動作する。
ズムは従来法のアルゴリズムに比べて、計算処理量が少
なくなり、高速に動作する。
上記の如く動作する素数判定器を機能ブロック図で示す
と第４図のようになる。第４図において、８は第１判定
手段で、gcd計算回路２とROM4とRAM5とプロセッサ６か
ら構成され、前記ステップ201,202,203を実行する。９
は乱数発生手段で、乱数発生回路１で構成され、ステッ
プ204を実行する。10は第２判定手段で、巾乗剰余回路
３とRAM5とプロセッサ６とから構成され、前記ステップ
205,206を実行する。11は第３判定手段で、ROM4とROM5
とプロセッサ６から構成され、前記ステップ207,208を
実行する。このように本実施例では第１、第２、第３の
判定手段を備え、第１判定手段８においてＮは非合成数
であると判定されたときに、第２判定手段10と第３判定
手段11による判定動作を繰返すように構成した。
と第４図のようになる。第４図において、８は第１判定
手段で、gcd計算回路２とROM4とRAM5とプロセッサ６か
ら構成され、前記ステップ201,202,203を実行する。９
は乱数発生手段で、乱数発生回路１で構成され、ステッ
プ204を実行する。10は第２判定手段で、巾乗剰余回路
３とRAM5とプロセッサ６とから構成され、前記ステップ
205,206を実行する。11は第３判定手段で、ROM4とROM5
とプロセッサ６から構成され、前記ステップ207,208を
実行する。このように本実施例では第１、第２、第３の
判定手段を備え、第１判定手段８においてＮは非合成数
であると判定されたときに、第２判定手段10と第３判定
手段11による判定動作を繰返すように構成した。
次に第３図のフローチャートによって第２発明に係る素
数判定器について説明する。この第２発明は第１発明を
改良したものである。第３図において、ステップ301,30
2,303,304,307,308,309は、第２図で説明したステップ2
01,202,203,204,207,208,209と全く同じであるため説明
を省略する。この第２発明に係る素数判定器では、ステ
ップ305において、巾乗剰余回路３を用いてＢ＝AN-1（m
od N）なるＢを計算で求め、このＢが１であるか否かに
よってＮが合成数であるか否かを判断するように構成さ
れる（ステップ306）。
数判定器について説明する。この第２発明は第１発明を
改良したものである。第３図において、ステップ301,30
2,303,304,307,308,309は、第２図で説明したステップ2
01,202,203,204,207,208,209と全く同じであるため説明
を省略する。この第２発明に係る素数判定器では、ステ
ップ305において、巾乗剰余回路３を用いてＢ＝AN-1（m
od N）なるＢを計算で求め、このＢが１であるか否かに
よってＮが合成数であるか否かを判断するように構成さ
れる（ステップ306）。
ここで上記素数判定器の動作のアルゴリズムを示すと、 ステップ301 Ｎ←素数候補、Ｉ←０、Ｍ←小さい素数
の積 ステップ302,303 gcd（M,N）≠１ならば終了、Ｎは合
成数 ステップ304 乱数Ａを生成 ステップ305,306 ならば終了、Ｎは合成数 ステップ307,308 Ｉ＜ＤならばＩ←Ｉ＋１としてステ
ップ304へ I≧Ｄならば終了、Ｎは素数 となる。従って前記第１発明に係る素数判定器と同様
に、且つ前記を考慮してステップ305,306を設けるよ
うにしたため、計算処理量を少なくし、高速に素数の判
定動作を行うことができる。
の積 ステップ302,303 gcd（M,N）≠１ならば終了、Ｎは合
成数 ステップ304 乱数Ａを生成 ステップ305,306 ならば終了、Ｎは合成数 ステップ307,308 Ｉ＜ＤならばＩ←Ｉ＋１としてステ
ップ304へ I≧Ｄならば終了、Ｎは素数 となる。従って前記第１発明に係る素数判定器と同様
に、且つ前記を考慮してステップ305,306を設けるよ
うにしたため、計算処理量を少なくし、高速に素数の判
定動作を行うことができる。
また第２発明に係る素数判定器を機能ブロック図で表わ
すと前記第１発明と同様に第４図に示すようになる。た
だしこの場合の第２判定手段10は上記ステップ305,306
を実行することになる。
すと前記第１発明と同様に第４図に示すようになる。た
だしこの場合の第２判定手段10は上記ステップ305,306
を実行することになる。
上記各発明に係る素数判定器において、乱数発生回路１
で発生する乱数は、自然乱数、疑似乱数であってもよ
い。またgcd計算回路２については前記文献（２）の316
頁〜339頁に記載され、巾乗余剰回路３は例えば情報処
理学会論文誌第24巻６号764頁〜771頁（1983）に記載さ
れているものを用いることができる。更に乱数発生回路
１、gcd計算回路２、巾乗剰余回路３はプロセッサ６、
又は別の専用プロセッサで実行させることもできる。
で発生する乱数は、自然乱数、疑似乱数であってもよ
い。またgcd計算回路２については前記文献（２）の316
頁〜339頁に記載され、巾乗余剰回路３は例えば情報処
理学会論文誌第24巻６号764頁〜771頁（1983）に記載さ
れているものを用いることができる。更に乱数発生回路
１、gcd計算回路２、巾乗剰余回路３はプロセッサ６、
又は別の専用プロセッサで実行させることもできる。
なお、上記各素数判定器は、乱数発生回路１で発生され
る乱数を素数候補として用いて上記素数判定を行うよう
に構成すれば、容易に素数発生器として構成し直すこと
ができる。
る乱数を素数候補として用いて上記素数判定を行うよう
に構成すれば、容易に素数発生器として構成し直すこと
ができる。
以上説明した通り本発明によれば、従来の素数判定器に
対してその数及び計算上の特長を考慮して若干の改良を
施すことによって計算処理量を著しく少なくすることが
でき、これによって高速に素数判定を行うことができ
る。
対してその数及び計算上の特長を考慮して若干の改良を
施すことによって計算処理量を著しく少なくすることが
でき、これによって高速に素数判定を行うことができ
る。
第１図は素数判定器の装置構成図、 第２図は第１発明に係る素数判定器の判定動作を示すフ
ローチャート、 第３図は第２発明に係る素数判定器の判定動作を示すフ
ローチャート、 第４図は第１発明及び第２発明に係る素数判定器の機能
ブロック図である。 １……乱数発生回路 ２……gcd計算回路 ３……巾乗剰余回路 ４……ROM ５……RAM ６……プロセッサ ８……第１判定手段 ９……乱数発生手段 10……第２判定手段 11……第３判定手段
ローチャート、 第３図は第２発明に係る素数判定器の判定動作を示すフ
ローチャート、 第４図は第１発明及び第２発明に係る素数判定器の機能
ブロック図である。 １……乱数発生回路 ２……gcd計算回路 ３……巾乗剰余回路 ４……ROM ５……RAM ６……プロセッサ ８……第１判定手段 ９……乱数発生手段 10……第２判定手段 11……第３判定手段
Claims (2)
- 【請求項１】与えられた正整数Ｎが素数であるか否かを
判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対して が１でもＮ−１でもなければＮは素数でないと判定する
第２判定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段、 とから成ることを特徴とする素数判定器。 - 【請求項２】与えられた正整数Ｎが素数であるか否かを
判定する素数判定器において、 前記Ｎが予め定められた正整数Ｍと互いに素でなければ
Ｎは素数でないと判定する第１判定手段と、 正整数の乱数を発生する乱数発生手段と、 前記第１判定手段がＮは素数でないと判定しなかったと
き前記乱数発生手段の生成した整数Ａに対してAN-1（mo
d N）が１でなければＮは素数でないと判定する第２判
定手段と、 前記乱数発生手段が生成した任意の個数の乱数に対して
前記第２判定手段がＮは素数でないと判定しなかったと
きに、Ｎを素数であると判定する第３判定手段と、 から成ることを特徴とする素数判定器。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60122685A JPH0721761B2 (ja) | 1985-06-07 | 1985-06-07 | 素数判定器 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60122685A JPH0721761B2 (ja) | 1985-06-07 | 1985-06-07 | 素数判定器 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61281333A JPS61281333A (ja) | 1986-12-11 |
| JPH0721761B2 true JPH0721761B2 (ja) | 1995-03-08 |
Family
ID=14842089
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60122685A Expired - Lifetime JPH0721761B2 (ja) | 1985-06-07 | 1985-06-07 | 素数判定器 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0721761B2 (ja) |
-
1985
- 1985-06-07 JP JP60122685A patent/JPH0721761B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPS61281333A (ja) | 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 (ja) | 公開鍵および秘密鍵による暗号化方法 | |
| 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 (ja) | 離散対数をベースとした公開キーによる暗号化方法 | |
| 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 (ja) | 素数判定器 | |
| JPH0766322B2 (ja) | 素数判定器 | |
| US20040028223A1 (en) | Generation of a random number that is non-divisible by a set of prime numbers | |
| CN101243388A (zh) | 用于在加密计算中执行求逆运算的电路结构和方法 | |
| Moldovyan et al. | Short signatures from the difficulty of factoring problem |