(57)【特許請求の範囲】
【請求項１】
楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂ（modｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号鍵生成装置において、
ａ＝０とおいて、曲線の係数ｂ＝±１を入力する手段と、
与えられた一組の合同式を満たす乱数Ｕ，Ｖを生成する手段と、
ｐ＝Ｕ2−ＵＶ＋Ｖ2 を計算する手段と、
ｐの素数判定を行う手段と、
ｑ＝（ｐ＋１−ｂ（Ｕ＋Ｖ））／（８＋４ｂ）を計算する手段と、
ｑの素数判定を行う手段と、
上記乱数生成、上記計算及び素数判定を繰り返す手段と、
上記両素数判定手段が共に素数と判定されるとその時のｐを出力する手段と、を有し、
λ≡２（ｍｏｄｕｌｏ ３）〔λ＝Ｕ＋Ｖω，ω＝（−１＋√（−３））／２〕を満たすＵ，Ｖがそれぞれ満たす合同式の組が複数組定まり、当該合同式の組ごとに、当該合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓが満たす合同式が定まり、
上記与えられた一組の合同式は、上記λ≡２（ｍｏｄｕｌｏ ３）を満たすＵ，Ｖがそれぞれ満たす合同式の組の何れかであり、
上記与えられた一組の合同式をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数は、それ以外の何れかの上記合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数よりも確率的に大きいことを特徴とする楕円曲線暗号鍵生成装置。
【請求項２】
請求項１記載の装置において、
上記与えられた一組の合同式は
Ｕ≡２（mod ６）かつＶ≡３（mod ６）、
Ｕ≡５（mod ６）かつＶ≡３（mod ６）または
Ｕ≡５（mod ６）かつＶ≡０（mod ６）であることを特徴とする楕円曲線暗号鍵生成装置。
【請求項３】
請求項２記載の装置において、
上記与えられた一組の合同式は更にＵ≡５（mod １２）かつＶ≡３（mod １２）またはＵ≡１１（mod １２）かつＶ≡９（mod １２）を満たすことを特徴とする楕円曲線暗号鍵生成装置。
【請求項４】
楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂ（modｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号の鍵生成装置において、
ａ＝０とおいて、平方数でない曲線の係数ｂを入力する手段と、
与えられた一組の合同式を満たす乱数Ｕ，Ｖを生成する手段と、
ｐ＝Ｕ2−ＵＶ＋Ｖ2を計算する手段と、
ｐの素数判定を行う手段と、
ω＝（−１＋√−３）／２とおいてｒ＝（４ｂ）(p-1)/6（modulo Ｕ＋Ｖω）を計算する手段と、
ｒ∈｛−ω* ，−１，−ω｝を判定する手段と、
楕円曲線の位数Ｓを計算する手段と、
Ｓの素数判定を行う手段と、
上記乱数生成、上記計算及び上記各判定を繰り返す手段と、
上記両素数判定手段が共に素数と判定し、かつｒが−ω* ，−１，−ωの何れかであると判定されるとその時のｐを出力する手段と、を有し、
λ≡２（ｍｏｄｕｌｏ ３）〔λ＝Ｕ＋Ｖω，ω＝（−１＋√（−３））／２〕を満たすＵ，Ｖがそれぞれ満たす合同式の組が複数組定まり、当該合同式の組ごとに、当該合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓが満たす合同式が定まり、
上記与えられた一組の合同式は、上記λ≡２（ｍｏｄｕｌｏ ３）を満たすＵ，Ｖがそれぞれ満たす合同式の組の何れかであり、
上記与えられた一組の合同式をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数は、それ以外の何れかの上記合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数よりも確率的に大きいことを特徴とする楕円曲線暗号鍵生成装置。
【請求項５】
請求項４記載の装置において、
上記与えられた一組の合同式は
Ｕ≡２（mod ６）かつＶ≡３（mod ６）、
Ｕ≡５（mod ６）かつＶ≡３（mod ６）または
Ｕ≡５（mod ６）かつＶ≡０（mod ６）であることを特徴とする楕円曲線暗号鍵生成装置。
【請求項６】
請求項５記載の装置において、
上記与えられた一組の合同式は更に
Ｕ≡８（mod １２）かつＶ≡３（mod １２）、
Ｕ≡５（mod １２）かつＶ≡９（mod １２）または
Ｕ≡１１（mod １２）かつＶ≡０（mod １２）を満たすことを特徴とする楕円曲線暗号鍵生成装置。
【請求項７】
コンピュータを、乱数生成部とｐ計算部とｑ計算部と第１，２素数判定部と制御部とを有する楕円曲線暗号鍵生成装置として機能させて実行する、楕円曲線ｙ2 ＝ｘ3 ＋ａｘ＋ｂ（modｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号鍵生成方法において、
ａ＝０として、ｂ＝±１が上記ｑ計算部に入力され、
上記乱数生成部が、与えられた一組の合同式
Ｕ≡２（mod ６）かつＶ≡３（mod ６）、
Ｕ≡５（mod ６）かつＶ≡３（mod ６）または
Ｕ≡５（mod ６）かつＶ≡０（mod ６）を満たす乱数Ｕ，Ｖを生成し、
上記ｐ計算部が、ｐ＝Ｕ2−ＵＶ＋Ｖ2を計算し、
上記第１素数判定部が、ｐが素数か否かを判定し、
上記ｑ計算部が、ｑ＝（ｐ＋１−ｂ（Ｕ＋Ｖ））／（８＋４ｂ）を計算し、
上記第２素数判定部が、ｑが素数か否かを判定し、
上記制御部が、上記乱数生成、上記各計算及び上記各判定を繰り返し実行させ、上記判定が共に素数と判定されるとその時の上記ｐを出力し、
λ≡２（ｍｏｄｕｌｏ ３）〔λ＝Ｕ＋Ｖω，ω＝（−１＋√（−３））／２〕を満たすＵ，Ｖがそれぞれ満たす合同式の組が複数組定まり、当該合同式の組ごとに、当該合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓが満たす合同式が定まり、
上記与えられた一組の合同式は、上記λ≡２（ｍｏｄｕｌｏ ３）を満たすＵ，Ｖがそれぞれ満たす合同式の組の何れかであり、
上記与えられた一組の合同式をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数は、それ以外の何れかの上記合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数よりも確率的に大きいことを特徴とする楕円曲線暗号鍵生成方法。
【請求項８】
請求項７記載の方法において、
上記乱数Ｕ，Ｖの生成は
Ｕ≡５（mod １２）かつＶ≡３（mod １２）または
Ｕ≡１１（mod １２）かつＶ≡９（mod １２）を満たすものを生成することを特徴とする楕円曲線暗号鍵生成方法。
【請求項９】
コンピュータを、乱数生成部とｐ計算部とｒ計算部と第１，２素数判定部と真偽判定部と位数計算部と制御部とを有する楕円曲線暗号鍵生成装置として機能させて実行する、楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂ（modｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号鍵生成方法において、
ａ＝０とし、平方数でないｂが上記ｒ計算部に入力され、
上記乱数生成部が、与えられた一組の合同式Ｕ≡２（mod ６）かつＶ≡３（mod ６）、Ｕ≡５（mod ６）かつＶ≡３（mod ６）またはＵ≡５（mod ６）かつＶ≡０（mod ６）を満たす整数Ｕ，Ｖを生成し、
上記ｐ計算部が、ｐ＝Ｕ2−ＵＶ＋Ｖ2を計算し、
上記第１素数判定部が、ｐが素数か否かを判定し、
上記ｒ計算部が、ｒ＝（４ｂ）(p-1)/6（ｍｏｄｕｌｏ Ｕ＋Ｖω）を計算し、
上記真偽判定部が、ｒが−ω* ，−１，−ωであるか否かを判定し、
上記位数計算部が、楕円曲線の位数を計算し、
上記第２素数判定部が、上記位数が素数か否かを判定し、
上記制御部が、上記乱数生成、上記各計算、上記各判定を繰り返し実行させ、上記判定でｒが上記の何れかであると判定され、かつ上記両判定が共に素数と判定されるとそのときのｐを出力し、
λ≡２（ｍｏｄｕｌｏ ３）〔λ＝Ｕ＋Ｖω，ω＝（−１＋√（−３））／２〕を満たすＵ，Ｖがそれぞれ満たす合同式の組が複数組定まり、当該合同式の組ごとに、当該合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓが満たす合同式が定まり、
上記与えられた一組の合同式は、上記λ≡２（ｍｏｄｕｌｏ ３）を満たすＵ，Ｖがそれぞれ満たす合同式の組の何れかであり、
上記与えられた一組の合同式をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数は、それ以外の何れかの上記合同式の組をそれぞれ満たすＵ，Ｖによって定まる上記楕円曲線の位数Ｓの最大素因数よりも確率的に大きいことを特徴とする楕円曲線暗号鍵生成方法。
【請求項１０】
請求項９記載の方法において、
上記乱数Ｕ，Ｖの生成は
Ｕ≡８（mod １２）かつＶ≡３（mod １２）、
Ｕ≡５（mod １２）かつＶ≡９（mod １２）または
Ｕ≡１１（mod １２）かつＶ≡０（mod １２）を満たすことを特徴とする楕円曲線暗号鍵生成方法。
【請求項１１】
請求項７から１０の何れかの楕円曲線暗号鍵生成方法の各手順をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は楕円曲線ｙ2 ＝ｘ3 ＋ａｘ＋ｂ（mod ｐ）のモジュラスｐと係数ａ，ｂを決定する楕円曲線暗号の鍵生成装置、その生成方法及びプログラム記録媒体に関するものである。
【０００２】
【従来の技術】
合同式ｙ2 ≡ｘ3 ＋ａｘ＋ｂ（mod ｐ）を満たす点（ｘ，ｙ）の集合に無限遠点Ｏを加えた集合を楕円曲線と呼びＥp ［ａ，ｂ］と表す。ただしｐは２，３でない素数、４ａ3 ＋２７ｂ2 ≠０とする。Ｅp ［ａ，ｂ］の要素数（点の個数）を楕円曲線の位数と呼び＃Ｅp ［ａ，ｂ］と表す。安全な楕円曲線暗号を構成するためには＃Ｅp ［ａ，ｂ］が十分大きな素因数を持つようモジュラスｐ、曲線の係数（以下、係数）ａ，ｂを決める必要がある。これらｐ，ａ，ｂは楕円曲線暗号の鍵であり、鍵生成法として以下の二つが従来提案されていた。
【０００３】
（１）位数計算による方法
モジュラスｐと係数ａ，ｂを選び、これらより位数＃Ｅp ［ａ，ｂ］を計算する。＃Ｅp ［ａ，ｂ］が安全性の条件を満たすまで、以上を繰り返す。位数計算にはＳｃｈｏｏｆのアルゴリズム（Ｒ．Ｓｃｈｏｏｆ“ Elliptic curves over finite fields and the computation of square roots mod p ”, Math. Comp.,Vol.44, No.170, pp.483-494(1985)) 等を用いる。
【０００４】
（２）虚数乗法に基づく方法
先に適切な位数とモジュラスｐを選び、曲線がその位数を持つよう係数ａ，ｂを計算する方法（たとえばＡ．Ｏ．Atkin and F. Morain,“Elliptic curves and primality proving ”, Math. Comp. Vol.61, pp.29-68,(1993) など）。
（１）の特殊な場合として、Ｅp ［ａ，０］やＥp ［０，ｂ］を用いた方法がある。これらの曲線は位数計算が高速に行なえる。＃Ｅp ［０，ｂ］は以下のとおりである。ｐ≡２（mod ３）のとき＃Ｅp ［０，ｂ］＝ｐ＋１となる。ただし位数がｐ＋１となる曲線を用いた楕円曲線暗号にはＭＯＶ−reduction による攻撃が適用できるため、この曲線は用いない。またｐ≡１（mod ３）のとき
＃Ｅp ［０，ｂ］＝ｐ＋１＋（４ｂ／λ）* 6 λ＋（４ｂ／λ）6 λ* （１）
となる（Ireland, Rosen, “ A Classical Introduction to Modern Number Theory ”, 2nd ed. Springer Verlag(ＧＴＭ８４））。
【０００５】
ただしｂ≠０，（４ｂ／λ）6 ＝（４ｂ）(p-1)/6 （ｍｏｄｕｌｏ  λ）、Ａ* はＡの複素共役を表わし、またλ＝Ｕ＋Ｖω（ω＝（−１＋√（−３））／２）はｐ＝λλ* ＝Ｕ2 −ＵＶ＋Ｖ2 ，λ≡２（ｍｏｄｕｌｏ  ３）を満たすものとする。
なお整数ｍ，ｎによりｍ＋ｎωと表せる数全体の集合をＺ［ω］と表す。整数と同様に、Ｚ［ω］上にも商と余りが定義できる。すなわちα，β∈Ｚ［ω］に対してα＝γβ＋δ，Ｎ（δ）＜Ｎ（β）を満たす商γと余りδがＺ［ω］の中に存在する。ここでＮ（δ）＝δδ* はδのノルムである。上記において「ｍｏｄｕｌｏ」はＺ［ω］上の割算による余りを表し、整数上の割算による余りを表す「ｍｏｄ」と区別する。ところで
（４ｂ／λ）6 の値は｛−ω* ，ω，−１，ω* ，−ω，１｝のいずれかと合同となる。よってｐ≡１（mod ３）のとき位数＃Ｅp ［０，ｂ］は（４ｂ／λ）6 の値により６通りのうちの１つに定まる。
【０００６】
【発明が解決しようとする課題】
従来方法（１），（２）は鍵生成に多くの計算時間がかかることが問題であった。Ｅp ［０，ｂ］を用いた方法は方法（１），（２）に比べて高速であるが、位数が大きな素因数を持つ曲線を効率的に生成する手順が明らかでなかった。
【０００７】
【課題を解決するための手段】
この発明は楕円曲線の係数ａを０に限定した場合、安全な曲線を高速に生成する、つまり与えた係数ｂに対して位数が大きな素因数を持つようモジュラスｐを決定する手段を提供する。
この発明の特徴は、モジュラスｐを選ぶ際に、ｐ＝Ｕ2 −ＵＶ＋Ｖ2 を満たすＵ，Ｖを先に決めることおよび以下に述べる位数がどのような約数をもつかについての考察に基づくことで、位数の最大素因数が大きな（安全な）曲線を効率的に見つけ出す点にある。
作用
位数を与える式（１）においてλ≡２（ｍｏｄｕｌｏ  ３）の条件を満たすのは以下のいずれかである。
【０００８】
（Ｉ）Ｕ≡２（mod ６）かつＶ≡３（mod ６）
（II）Ｕ≡５（mod ６）かつＶ≡３（mod ６）
（III)Ｕ≡５（mod ６）かつＶ≡０（mod ６）
なおＵ≡２（mod ６）かつＶ≡０（mod ６）の場合は２｜ｐ＝Ｕ2 −ＵＶ＋Ｖ2 （ｐが２で割り切れることを表わす）となり、ｐは３で割って１余る素数になりえない。また（Ｉ）（II）（III)はモジュロ６をそれぞれモジュロ１２でおきかえると、さらに４とおりに分かれ、全体で１２とおりのそれぞれについては図１に示す合同式を満たす。図１においてＳは位数＃Ｅp ［０，ｂ］，Ｓ≡１（６）はＳ≡１（mod ６）の意味である。
【０００９】
たとえば、（４ｂ／λ）6 ＝１かつ（Ｉａ）の場合、＃Ｅp ［０，ｂ］＝ｐ＋１＋（２Ｕ−Ｖ）となり＃Ｅp ［０，ｂ］は３６で割って９余る、すなわち９で割り切れる。このとき＃Ｅp ［０，ｂ］／９が素数なら位数の最大素因数が最も大きくなり、Ｅp ［０，ｂ］は（４ｂ／λ）6 ＝１かつ（Ｉａ）の条件のもとで最も安全な曲線となる。他の場合も同様である。この発明は、Ｕ，Ｖをランダムに選び、ｐ＝Ｕ2 −ＵＶ＋Ｖ2 が素数かつ位数の最大素因数が最大となるまでこれを繰り返すものである。
【００１０】
【発明の実施の形態】
実施例１
実施例１は曲線の係数ｂを±１に限定した場合の鍵生成法である。ｂ＝１の場合は以下のとおりである。（Ｉ）のとき（４／λ）6 ＝ω、（II）のとき（４／λ）6 ＝ω* 、（III)のとき（４／λ）6 ＝１である。図１から（Ｉ）かつ（４／λ）6 ＝ω及び（II）かつ（４／λ）6 ＝ω* のときはそれぞれ１２｜＃Ｅp ［０，１］となり、（III)のとき３６｜＃Ｅp ［０，１］となり、（III)より（Ｉ）（II）のほうが位数の最大素因数を大きくできる。
【００１１】
ｂ＝−１の場合は以下の通りである。（−４／λ）6 ＝（−１／λ）6 （４／λ）6 、また（−１／λ）6 ＝（−１）(p-1)/6 ＝１−（ｐ−１mod １２）／３。よって図１に示すようにｐを１２で割った余りは１か７であるからｐ≡１（mod １２）のときｐ＝１mod １２を（−１／λ）6 ＝１−（ｐ−１mod １２）／３に代入すると（−１／λ）6 ＝１となるから＃Ｅp ［０，−１］＝＃Ｅp ［０，１］となりｂ＝１の場合と同じである。ｐ≡７（mod １２）のときｐ＝７を１−（ｐ−１mod １２）／３に代入すると（−１／λ）6 ＝−１となり、ｂ＝１の時の（Ｉ）で（４／λ）6 ＝ω、（II）で（４／λ）6 ＝ω* 、（III)で（４／λ）6 ＝１が（Ｉ）で−ω、（II）で−ω* 、（III)  で−１となるから、図１を見ると、（Ｉａ），（Ｉｂ），（Ｉｃ），（Ｉｄ）で−ωの時のＳはそれぞれ４、４、４、１６、（IIａ），（IIｂ），（IIｃ），（IIｄ）で−ω* の時のＳはそれぞれ４、４、１６、４、(IIIａ) ，(IIIｂ) ，(IIIｃ) ，(IIIｄ) で−１の時のＳはそれぞれ１６、４、４、４であり、これらは何れも４で割り切れる値であって、４｜＃Ｅp ［０，ｂ］となり位数の最大素因数を最大にできる。
【００１２】
以上よりｂ＝±１の場合、ｂ＝１の時は、（Ｉａ），（Ｉｂ），（Ｉｄ），（IIａ），（IIｃ），（IIｄ）からＵ，Ｖを選べばよく、ｂ＝−１の時はｐ＝７、つまり図１から（Ｉａ），（Ｉｂ），（IIａ）,（IIｄ），(IIIｂ），(IIIｄ）からＵ，Ｖを選べばよい。これらの共通なものは、（Ｉａ），（Ｉｂ），（IIａ），（IIｄ）であるが（Ｉ）と（II）とで位数が異なるから、例えば（IIａ）（IIｄ）からＵ，Ｖを選べば、ｂ＝１のとき（４／λ）6 ＝ω* であってＳ＝ｐ＋１−（Ｕ＋Ｖ）であり、ｂ＝−１では（−４／λ）6 ＝−ω* であって、Ｓ＝ｐ＋１＋（Ｕ＋Ｖ）であるから、これらを合わせて、＃Ｅp［０，ｂ］＝ｐ＋１−ｂ（Ｕ＋Ｖ）とかける。また、図１より（IIａ），（IIｄ）でω* の時、共にＳ＝１２（７２）であり、−ω* の時、共にＳ＝４（２４）であるから、ｂ＝±１にて（８＋４ｂ）｜＃Ｅp［０，ｂ］と表わせる。
【００１３】
図２は実施例１の構成図であり、処理手順は以下のとおりである。ｂ（＝±１）を入力し、乱数生成部１１で（IIａ），（IIｄ）の何れか、つまりＵ≡５（mod １２）かつＶ≡３（mod １２）、またはＵ≡１１（mod １２）かつＶ≡９（mod １２）を満たす乱数Ｕ，Ｖを生成し、これらＵ，Ｖについてｐ計算部１２でｐ＝Ｕ2 −ＵＶ＋Ｖ2 を計算し、素数判定部１３でそのｐの素数判定を行ない素数でなければ乱数生成部１１においてＵ，Ｖを再生成する。また位数計算部１４でＳ＝ｐ＋１−ｂ（Ｕ＋Ｖ）を計算し、ｑ計算部１５でｑ＝Ｓ／（８＋４ｂ）を計算し、素数判定部１６でｑの素数判定を行ない素数でなければ乱数生成部１１においてＵ，Ｖを再生成する。すなわち、制御部１７は各判定部１３，１６の判定結果に応じた制御を行いｐ，ｑがともに素数ならばｐを出力して終了する。
実施例２
実施例２は曲線の係数ｂを、ｂが平方数とならないよう選んだ場合の鍵生成法である。位数＃Ｅp ［０，ｂ］が素数となる場合が最も安全であるが、ｂが平方数のときは（４ｂ／（Ｕ＋Ｖω））6 ∈｛ω，ω* ，１｝となり、図１からわかるように＃Ｅp ［０，ｂ］は３で割りきれるため最も安全な曲線にはならない。この理由によりｂが平方数となるようなｂを除外する。図１より（Ｉｃ）（IIｂ）（III ｃ）のときに＃Ｅp ［０，ｂ］が素数となる場合が多い。
【００１４】
図３は実施例２の構成図であり、処理手順は以下のとおりである。平方数でない適当なｂを入力し乱数生成部２１で（Ｉｃ），（IIｂ），（IIIｃ）、つまりＵ≡８（mod １２）かつＶ≡３（mod １２）、またはＵ≡５（mod １２）かつＶ≡９（mod １２）またはＵ≡１１（mod １２）かつＶ≡０（mod １２）を満たす乱数Ｕ，Ｖを生成し、ｐ計算部２２でこれらＵ，Ｖについてｐ＝Ｕ2−ＵＶ＋Ｖ2を計算し、素数判定部２３でそのｐの素数判定を行ない、素数でなければ乱数生成部２１においてＵ，Ｖを再生成する。またｒ計算部２４でｒ＝（４ｂ／（Ｕ＋Ｖω））6 を計算し、真偽判定部２５でｒ∈｛−ω* ，−１，−ω｝の真偽を判定し、偽なら乱数生成部２１においてＵ，Ｖを再生成する。また位数計算部２６でＳ＝＃Ｅp ［０，ｂ］を計算し、素数判定部２７でＳの素数判定を行ない、素数でなければｂを再入力し、乱数生成部２１においてＵ，Ｖを再生成する。すなわち判定部２３，２７でｐ，Ｓがともに素数と判定し、かつ、判定部２５でｒ∈｛−ω* ，−１，−ω｝が真であると判定すると、その時のｐを出力して終了する。制御部２８は各判定部２３，２５，２７の判定結果に応じた制御を行なう。ここで判定部２５の判定はｑの素数判定より先にする。つまり位数Ｓが素数であればｒ∈｛−ω* ，−１，−ω｝に必ずなるから、ｒの真偽判定をまず行い、真と判定されると、その後、ｑが素数か否かの判定を行う。このようにすればｑの素数判定を簡単にかつ高速に行える。
【００１５】
実施例１ではＵ，Ｖを（IIａ），（IIｄ）から選んだが、（Ｉａ）（Ｉｂ）から選んでもよい。この場合の位数計算はｐ＋１＋ｂ（２Ｖ−Ｕ）によればよい。上述において、コンピュータによりプログラムを読出し、解読実行させて、各機能を動作させることもできる。
【００１６】
【発明の効果】
鍵生成に必要な時間を比較すると、改良したＳｃｈｏｏｆアルゴリズムを用いた位数計算による方法が（ｌｏｇ  ｐ）7 のオーダ、虚数乗法に基づく方法が（ｌｏｇ  ｐ）6 のオーダ、この発明が（ｌｏｇ  ｐ）5 のオーダとなり、この発明が最も高速に鍵を生成できる。
【図面の簡単な説明】
【図１】（４ｂ／λ）6 の値とＵ，Ｖの値と位数Ｓの値との関係を示す図。
【図２】この発明の実施例１の機能構成を示す図。
【図３】この発明の実施例２の機能構成を示す図。
【図１】
0004344033.tif 000002
【図２】
0004344033.tif 000003
【図３】
0004344033.tif 000004