(57)【特許請求の範囲】
【請求項１】
多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行う楕円曲線演算装置であって、
外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得手段と、
取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換手段とを備え、
前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、
多項式Ｘ（α）＝ｆ（α）×φ（α）、
多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び
多項式Ｚ（α）＝１により変換して
Ｊａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、
さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算手段
を備えることを特徴とする楕円曲線演算装置。
【請求項２】
前記取得手段は、楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを取得し、
前記変換手段は、取得した１個又は２個のアフィン座標に対して、前記座標変換を施して、それぞれ１個又は２個のＪａｃｏｂｉａｎ座標を生成し、
前記演算手段は、前記生成された１個又は２個のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される２倍算又は加算をそれぞれ施す
ことを特徴とする請求項１に記載の楕円曲線演算装置。
【請求項３】
前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は加算であり、
前記取得手段は、楕円曲線Ｅ上の２個の異なる点のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））並び
に加算を示す演算情報を取得し、
前記変換手段は、前記２個のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））に対して、
前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標
（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び
（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、
前記演算手段は、
演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、
演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、
演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、
演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、
演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び
演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、
次に、
演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、
演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び
演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、
次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出する
ことを特徴とする請求項２に記載の楕円曲線演算装置。
【請求項４】
前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は２倍算であり、
前記取得手段は、楕円曲線Ｅ上の１個の点のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、
前記変換手段は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、
１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、
前記演算手段は、
演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、
演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び
演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、
次に、
演算Ｘ３（α）＝Ｔ（α）、
演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び
演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、
次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出する
ことを特徴とする請求項２に記載の楕円曲線演算装置。
【請求項５】
前記取得手段は、
楕円曲線Ｅ上の２個の異なる点のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、
又は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、
前記変換手段は、
前記２個のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び
（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、
又は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、
１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、
前記演算手段は、
取得した前記演算情報が加算を示す場合には、
演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、
演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、
演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、
演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、
演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び
演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、
次に、
演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、
演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び
演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、
次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出し、
取得した前記演算情報が２倍算を示す場合には、
演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、
演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び
演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、
次に、
演算Ｘ３（α）＝Ｔ（α）、
演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び
演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、
次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出する
ことを特徴とする請求項２に記載の楕円曲線演算装置。
【請求項６】
ＳＥＡアルゴリズムにより楕円曲線の位数計算を行う楕円曲線位数計算装置であって、
前記楕円曲線位数計算装置は、請求項１に記載の楕円曲線演算装置を含む
ことを特徴とする楕円曲線位数計算装置。
【請求項７】
前記楕円曲線位数計算装置は、請求項２に記載の楕円曲線演算装置を含む
ことを特徴とする請求項６に記載の楕円曲線位数計算装置。
【請求項８】
前記楕円曲線位数計算装置は、請求項５に記載の楕円曲線演算装置を含む
ことを特徴とする請求項７に記載の楕円曲線位数計算装置。
【請求項９】
ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定する楕円曲線構成装置であって、
乱数を生成する乱数生成手段と、
楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成手段と、
前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定手段と、
前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算手段と、
前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定手段と、
前記安全性判定手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成手段、前記パラメタ生成手段、前記有限性判定手段、前記位数計算手段及び前記安全性判定手段に対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように制御する繰返制御手段と、
前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力手段と
を備えることを特徴とする楕円曲線構成装置。
【請求項１０】
前記楕円曲線Ｅは、ｙ＾２＝ｘ＾３＋ａｘ＋ｂにより示され、ここで、パラメタａ及びパラメタｂは定数であり、
前記パラメタ生成手段は、パラメタａ＝−３とし、パラメタｂを前記生成された乱数として選択することにより、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、パラメタを選択する
ことを特徴とする請求項９に記載の楕円曲線構成装置。
【請求項１１】
前記有限性判定手段は、楕円曲線Ｅを有理数体上の楕円曲線ＥＱとみなし、２個の素数ｐ１、ｐ２をあらかじめ有し、ｐ１≠ｐ２であり、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出し、算出された位数ｍ１、ｍ２が互いに素であることを判定し、互いに素であると判定する場合に、楕円曲線Ｅが有理数体上において有限位数の点を持たないと判定する
ことを特徴とする請求項１０に記載の楕円曲線構成装置。
【請求項１２】
前記有限性判定手段は、素数ｐ１＝５及び素数ｐ２＝７をあらかじめ有し、２個の素数ｐ１＝５、ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出する
ことを特徴とする請求項１１に記載の楕円曲線構成装置。
【請求項１３】
前記位数計算手段は、ＳＥＡアルゴリズムにより楕円曲線の位数計算を行い、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の点に対して２倍算又は加算を施す楕円曲線演算手段を含み、
前記楕円曲線演算手段は、請求項１に記載の楕円曲線演算装置を含む
ことを特徴とする請求項１１に記載の楕円曲線構成装置。
【請求項１４】
前記楕円曲線演算手段は、請求項２に記載の楕円曲線演算装置を含む
ことを特徴とする請求項１３に記載の楕円曲線構成装置。
【請求項１５】
前記楕円曲線演算手段は、請求項５に記載の楕円曲線演算装置を含む
ことを特徴とする請求項１４に記載の楕円曲線構成装置。
【請求項１６】
楕円曲線を用いて処理を行う楕円曲線応用装置であって、
前記楕円曲線応用装置は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定する楕円曲線構成手段を含み、
前記楕円曲線構成手段は、請求項９に記載の楕円曲線構成装置を備える
ことを特徴とする楕円曲線応用装置。
【請求項１７】
前記楕円曲線構成手段は、請求項１０に記載の楕円曲線構成装置を備える
ことを特徴とする請求項１６に記載の楕円曲線応用装置。
【請求項１８】
前記楕円曲線構成手段は、請求項１１に記載の楕円曲線構成装置を備える
ことを特徴とする請求項１７に記載の楕円曲線応用装置。
【請求項１９】
前記楕円曲線構成手段は、請求項１２に記載の楕円曲線構成装置を備える
ことを特徴とする請求項１８に記載の楕円曲線応用装置。
【請求項２０】
前記楕円曲線構成手段は、請求項１３に記載の楕円曲線構成装置を備える
ことを特徴とする請求項１８に記載の楕円曲線応用装置。
【請求項２１】
前記楕円曲線構成手段は、請求項１４に記載の楕円曲線構成装置を備える
ことを特徴とする請求項２０に記載の楕円曲線応用装置。
【請求項２２】
前記楕円曲線構成手段は、請求項１５に記載の楕円曲線構成装置を備える
ことを特徴とする請求項２１に記載の楕円曲線応用装置。
【請求項２３】
多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行い、取得手段と変換手段と演算手段とを備える装置で用いられる楕円曲線演算方法であって、
前記取得手段により、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得ステップと、
前記変換手段により、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換ステップとを含み、
前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、
多項式Ｘ（α）＝ｆ（α）×φ（α）、
多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び
多項式Ｚ（α）＝１により変換して
Ｊａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、
さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記演算手段により、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算ステップ
を含むことを特徴とする楕円曲線演算方法。
【請求項２４】
ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定し、乱数生成手段とパラメタ生成手段と有限性判定手段と位数計算手段と安全性判定手段と繰返制御手段とパラメタ出力手段とを備える楕円曲線構成装置で用いられる楕円曲線構成方法であって、
前記乱数生成手段により、乱数を生成する乱数生成ステップと、
前記パラメタ生成手段により、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成ステップと、
前記有限性判定手段により、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定ステップと、
前記位数計算手段により、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算ステップと、
前記安全性判定手段により、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定ステップと、
前記安全性判定ステップにより、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成ステップ、前記パラメタ生成ステップ、前記有限性判定ステップ、前記位数計算ステップ及び前記安全性判定ステップに対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように、前記繰返制御手段により、制御する繰返制御ステップと、
前記パラメタ出力手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力ステップと
を含むことを特徴とする楕円曲線構成方法。
【請求項２５】
多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行い、取得手段と変換手段と演算手段とを備える楕円曲線演算装置で用いられる楕円曲線演算プログラムを記録しているコンピュータ読み取り可能な記録媒体であって、
前記プログラムは、
前記取得手段により、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得ステップと
前記変換手段により、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換ステップとを含み、
前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、
多項式Ｘ（α）＝ｆ（α）×φ（α）、
多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び
多項式Ｚ（α）＝１により変換して
Ｊａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、
さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記演算手段により、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算ステップ
を含むことを特徴とする記録媒体。
【請求項２６】
前記取得ステップは、楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを取得し、
前記変換ステップは、取得した１個又は２個のアフィン座標に対して、前記座標変換を施して、それぞれ１個又は２個のＪａｃｏｂｉａｎ座標を生成し、
前記演算ステップは、前記生成された１個又は２個のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される２倍算又は加算をそれぞれ施す
ことを特徴とする請求項２５に記載の記録媒体。
【請求項２７】
前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は加算であり、
前記取得ステップは、楕円曲線Ｅ上の２個の異なる点のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））並び
に加算を示す演算情報を取得し、
前記変換ステップは、前記２個のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））に対して、
前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標
（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び
（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、
前記演算ステップは、
演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、
演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、
演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、
演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、
演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び
演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、
次に、
演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、
演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び
演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、
次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出する
ことを特徴とする請求項２６に記載の記録媒体。
【請求項２８】
前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は２倍算であり、
前記取得ステップは、楕円曲線Ｅ上の１個の点のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、
前記変換ステップは、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、
１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、
前記演算ステップは、
演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、
演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び
演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、
次に、
演算Ｘ３（α）＝Ｔ（α）、
演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び
演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、
次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出する
ことを特徴とする請求項２６に記載の記録媒体。
【請求項２９】
前記取得ステップは、
楕円曲線Ｅ上の２個の異なる点のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、
又は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、
前記変換ステップは、
前記２個のアフィン座標
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び
（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、
又は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、
１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、
前記演算ステップは、
取得した前記演算情報が加算を示す場合には、
演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、
演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、
演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、
演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、
演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び
演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、
次に、
演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、
演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び
演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、
次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出し、
取得した前記演算情報が２倍算を示す場合には、
演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、
演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び
演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、
次に、
演算Ｘ３（α）＝Ｔ（α）、
演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び
演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、
次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出する
ことを特徴とする請求項２６に記載の記録媒体。
【請求項３０】
ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定し、乱数生成手段とパラメタ生成手段と有限性判定手段と位数計算手段と安全性判定手段と繰返制御手段とパラメタ出力手段とを備えている楕円曲線構成装置で用いられる楕円曲線構成プログラムを記録しているコンピュータ読み取り可能な記録媒体あって、
前記プログラムは、
前記乱数生成手段により、乱数を生成する乱数生成ステップと、
前記パラメタ生成手段により、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成ステップと、
前記有限性判定手段により、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定ステップと、
前記位数計算手段により、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算ステップと、
前記安全性判定手段により、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定ステップと、
前記安全性判定ステップにより、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成ステップ、前記パラメタ生成ステップ、前記有限性判定ステップ、前記位数計算ステップ及び前記安全性判定ステップに対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように、前記繰返制御手段により、制御する繰返制御ステップと、
前記パラメタ出力手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力ステップと
を含むことを特徴とする記録媒体。
【請求項３１】
前記楕円曲線Ｅは、ｙ＾２＝ｘ＾３＋ａｘ＋ｂにより示され、ここで、パラメタａ及びパラメタｂは定数であり、
前記パラメタ生成ステップは、パラメタａ＝−３とし、パラメタｂを前記生成された乱数として選択することにより、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるようにパラメタを選択する
ことを特徴とする請求項３０に記載の記録媒体。
【請求項３２】
前記有限性判定ステップは、楕円曲線Ｅを有理数体上の楕円曲線ＥＱとみなし、２個の素数ｐ１、ｐ２をあらかじめ有し、ｐ１≠ｐ２であり、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出し、算出された位数ｍ１、ｍ２が互いに素であることを判定し、互いに素であると判定する場合に、楕円曲線Ｅが有理数体上において有限位数の点を持たないと判定する
ことを特徴とする請求項３１に記載の記録媒体。
【請求項３３】
前記有限性判定ステップは、素数ｐ１＝５及び素数ｐ２＝７をあらかじめ有し、２個の素数ｐ１＝５、ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出する
ことを特徴とする請求項３２に記載の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線についての演算技術及び楕円曲線の応用技術に関する。
【０００２】
【従来の技術】
近年、暗号通信技術において、楕円曲線が用いられている。その暗号通信における安全性の根拠は、離散対数問題である。
離散対数問題には、代表的なものとして、有限体上定義されるもの及び楕円曲線上定義されるものがある。これらについては、「A Course in Number theory and Cryptography」（Neal Koblitz著、Springer-Verlag、１９８７年）に詳しく述べられている。楕円曲線上の離散対数問題について以下に説明する。
（楕円曲線上の離散対数問題）
楕円曲線上の離散対数問題とは、
Ｅ（ＧＦ（ｐ））を有限体ＧＦ（ｐ）上において定義される楕円曲線とし、楕円曲線Ｅの位数が大きな素数で割り切れる場合に、楕円曲線Ｅ上の元Ｇをベースポイントとする。ここで、楕円曲線の位数とは、座標の成分がＧＦ（ｐ）に属する楕円曲線上の点の個数を示している。このとき、楕円曲線Ｅ上の与えられた元Ｙに対して、
Ｙ＝ｘＧ
となる整数ｘが存在するならば、整数ｘを求めよ、という問題である。
【０００３】
ここで、ｐは素数であり、有限体ＧＦ（ｐ）は、ｐ個の元を有する。
（安全な楕円曲線の条件）
楕円曲線上の離散対数問題には様々な解読法が提案されているので、これらの解読法に対して、安全な楕円曲線を構成する必要がある。
なお、この明細書において「楕円曲線を構成する」とは、楕円曲線を、
ｙ＾２  ＝  ｘ＾３  ＋  ａｘ  ＋  ｂ
で表現する場合に、パラメタａ、ｂの値を決定することである。また、この明細書において、記号＾は、べき乗による演算を示すものとし、例えば、ｘ＾３はｘの３乗を示す。
【０００４】
現存するすべての解読法に対して安全な楕円曲線の条件は、有限体ＧＦ（ｐ）上の楕円曲線の場合、
（ａ）楕円曲線の位数がｐ−１、ｐ及びｐ＋１のいずれでもないこと、及び
（ｂ）この楕円曲線の位数が大きい素因数をもつことである。
このように、楕円曲線の安全性は、その楕円曲線の位数を調べることにより確認できる。
【０００５】
「暗号・ゼロ知識証明、数論」（１５５ページ〜１５６ページ、情報処理学会監修、岡本龍明・太田和夫共編、共立出版、１９９５年）によると、これらの条件を満たす場合に、解読するために必要な計算時間は、前記位数の最大素因数に関する指数関数時間である。
（楕円曲線の構成方法）
楕円曲線の構成方法として、
（１）ＣＭ（Ｃｏｍｐｌｅｘ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）法を用いる構成法
（２）位数計算アルゴリズムを用いる構成法
がある。
【０００６】
（１）に示す構成法は、楕円曲線を簡単に構成できるという特徴を有しているが、一方で、ランダムに楕円曲線を構成できないという性質を有している。この構成法については、「On Ordinary Elliptic Curve Cryptosystems」（A.Miyaji著、ASIACRYPT'91、Springer-Verlag 、１９９１年、４６０ページ〜４６９ページ）に詳しく説明されている。また、（２）に示す構成法は、ランダムに楕円曲線を構成できるが、楕円曲線の構成に要する時間が長いという特徴を有している。
（従来例１：位数計算アルゴリズムによる楕円曲線の構成）
位数計算アルゴリズムによる楕円曲線の構成方法について、図１に示すフローチャートを用いて説明する。なお、この構成方法については、「Ellitpic Curve Implementation of Zero-Knowledge Blobs」（N.Koblitz著、J.Cryptology、vol.4 No.3、１９９１年、２０７ページ〜２１３ページ）に詳しく説明されている。
【０００７】
この構成方法によると、乱数を生成し（ステップＳ９０１）、生成した乱数を用いて楕円曲線を決定するパラメタを生成し（ステップＳ９０２）、生成したパラメタを用いて、楕円曲線の位数を計算する（ステップＳ９０３）。次に、計算された位数を用いて、与えられた安全な楕円曲線の条件を満たすか否かを判定することにより、楕円曲線の安全性を判定する。与えられた条件を満たす場合のみ（ステップＳ９０４）、前記生成された楕円曲線のパラメ−タを出力する。満たさない場合は（ステップＳ９０４）、ステップＳ９０１へ戻って、前記条件を満たすようになるまで、乱数の生成と、楕円曲線のパラメタの生成と、楕円曲線の位数の計算と、楕円曲線の判定とを繰り返す。
【０００８】
上記で述べた位数計算アルゴリズムによる構成方法では、計算時間が長い。特に、長い計算時間を要するのは、楕円曲線の位数計算である。
楕円曲線の位数を計算するアルゴリズムの一つにＳｃｈｏｏｆのアルゴリズムがある。このアルゴリズムは多項式時間アルゴリズムで構成される。ここで、多項式時間アルゴリズムとは、計算時間が多項式のオーダであるアルゴリズムである。このＳｃｈｏｏｆのアルゴリズムによる計算時間は、実用的な計算時間ではない。
（従来例２：ＳＥＡアルゴリズムによる楕円曲線の位数計算方法）
Ｓｃｈｏｏｆのアルゴリズムは、Ｅｌｋｉｅｓ、Ａｔｋｉｎによって、ＳＥＡアルゴリズムとして改良されている。
【０００９】
なお、この位数計算方法については、「Counting the number of points on elliptic curves over finite fields: strategies performances」（R.Lercier、F.Morain著、EUROCRYPT'95、Springer-Verlag、１９９５年、７９ページ〜９４ページ）に詳しく説明されている。
ＳＥＡアルゴリズムにおいては、ｔ  ｍｏｄ  Ｌ＾ｎ（ｎ＝１，２，３，．．．）を求めるが、この計算は、これはフロベニウス写像と呼ばれる写像の固有値を計算することによってできる。具体的には楕円曲線Ｅ上のＬ等分点（α，β）を用いて、以下の式のｋを求める。
【００１０】
（α＾ｐ，β＾ｐ）＝ｋ（α，β）
ここで、ｋ（α，β）は点（α，β）の楕円曲線上のｋ倍点である。上式の計算は、α，βを変数とし、ＧＦ（ｐ）上の元を係数とする多項式β＾２−ｆ（α）を法とするα，βに関する多項式剰余環上の楕円曲線演算によって行う。この演算において、多項式の逆元の計算量は乗算の計算量に比べ大きいため、３項組座標が用いられる。従来、３項組座標はプロジェクティブ座標が用いられる。このプロジェクティブ座標の使用は従来の有限体上の楕円曲線のプロジェクティブ座標の使用から自然に類推できるものである。従来のプロジェクティブ座標については、「Efficient elliptic curve exponentiation 」（Miyaji、Ono 、Cohen 著、Advances in cryptology-proceedings of ICICS'97、Lecture notes in computer science、１９９７年、Springer-verlag、２８２ページ〜２９０ページ）に詳しく述べられている。
（従来例３：楕円曲線上の点（α、β）のｋ倍点の演算方法）
楕円曲線上の点（α、β）のｋ倍点の演算は、ｋ倍点の演算を加算及び２倍算に分解し、次に示すようにして、加算及び２倍算により、行う。
【００１１】
（α、β）を（α：β：１）に変換し、（Ｘ（α）：β×Ｙ（α）：Ｚ（α））（Ｘ（α）＝α，Ｙ（α）＝Ｚ（α）＝１）と考える。
ここで、「（  、  ）」は、アフィン座標を示し、「（  ：  ：  ）」は、射影座標を示す。
このようにおいたとき、楕円曲線演算は次のようになる。
【００１２】
ここで、
Ｐ１＝（Ｘ１（α）：β×Ｙ１（α）：Ｚ１（α））、
Ｐ２＝（Ｘ２（α）：β×Ｙ２（α）：Ｚ２（α））、
Ｐ３＝Ｐ１＋Ｐ２＝（Ｘ３（α）：β×Ｙ３（α）：Ｚ３（α））
とおく。
【００１３】
なお、この明細書において、加算公式又は２倍算公式における演算子×及び演算子＊は、ともに同じ乗算を示すものとする。加算公式又は２倍算公式における乗算の回数を評価する場合において、初めて現れる乗算を演算子＊で示し、それ以外の乗算を演算子×で示す。各公式において、演算子＊が出現する個数を数えることにより、乗算の回数が算出できる。
（１）加算公式
Ｐ１≠±Ｐ２の場合、加算の演算となり、加算公式は、次のようになる。
【００１４】
Ｘ３＝ｖ＊Ａ
Ｙ３＝ｕ＊（ｖ＾２×Ｘ１×Ｚ２−Ａ）−ｖ＾３＊（Ｙ１×Ｚ２）
Ｚ３＝ｖ＾３＊（Ｚ１×Ｚ２）
ここで、
ｕ＝Ｙ２＊Ｚ１−Ｙ１＊Ｚ２、
ｖ＝Ｘ２＊Ｚ１−Ｘ１＊Ｚ２、
Ａ＝ｕ＾２×ｆ（α）×Ｚ１×Ｚ２−ｖ＾３−２×ｖ＾２×Ｘ１×Ｚ２
＝（（ｕ＊ｕ）＊ｆ（α））＊（Ｚ１＊Ｚ２）
−（ｖ＊ｖ）＊ｖ−２×ｖ＾２＊（Ｘ１×Ｚ２）
である。
【００１５】
なお、上記に示す各演算式において、Ｘ１、Ｙ１、Ｚ１、Ｘ２、Ｙ２、Ｚ２、Ｘ３、Ｙ３、Ｚ３、ｕ、ｖ、Ａは、それぞれ変数αに関する多項式であるので、Ｘ１（α）、Ｙ１（α）、Ｚ１（α）などと表記すべきであるが、表記を簡単にするために、（α）を省略して記載しているので、注意を要する。
（２）２倍算公式
Ｐ１＝Ｐ２の場合、２倍算の演算となり、２倍算公式は、次のようになる。
【００１６】
Ｘ３＝２×ｈ＊（ｓ×ｆ（α））
Ｙ３＝ｗ×（４×Ｂ−ｈ）−８×Ｙ１＾２×ｓ＾２×ｆ（α）＾２
＝ｗ＊（４×Ｂ−ｈ）
−８×（Ｙ１×ｓ×ｆ（α））＊（Ｙ１×ｓ×ｆ（α））
Ｚ３＝８×ｓ＾３×ｆ（α）＾２
＝８×ｓ＊（ｓ×ｆ（α））＊（ｓ×ｆ（α））
ここで、
ｗ＝ａ×Ｚ１＾２＋３×Ｘ１＾２
＝ａ×（Ｚ１＊Ｚ１）＋３×（Ｘ１＊Ｘ１）、
ｓ＝Ｙ１＊Ｚ１、
Ｂ＝Ｘ１＊（Ｙ１＊（ｓ＊ｆ（α）））、
ｈ＝ｗ＾２−８×Ｂ
＝ｗ＊ｗ−８×Ｂ
である。
【００１７】
ここで、ｆ（ｘ）＝ｘ＾３＋ａｘ＋ｂである。
なお、上記に示す各演算式においても、加算公式の場合と同様に、Ｘ１、Ｙ１、Ｚ１、Ｘ３、Ｙ３、Ｚ３、ｗ、ｓ、Ｂ、ｈは、それぞれ変数αに関する多項式であるが、表記を簡単にするために、（α）を省略して記載している。
前記加算公式及び前記２倍算公式における乗算の回数は、演算子＊の出現回数を数えると分かるように、それぞれ、１５回、１２回である。多項式乗算の計算量をＰＭｕｌとするとき、前記加算公式及び前記２倍算公式による計算量はそれぞれ、１５×ＰＭｕｌ、１２×ＰＭｕｌである。
【００１８】
なお、乗算の回数の計数において、ａ×（Ｚ１＾２）や３×（Ｘ１＾２）などのように、（定数）×（多項式）の乗算による計算量は、（多項式）×（多項式）の乗算による計算量と比較すると、小さいので、前記の乗算の回数の計数においては、無視している。また、同じ乗算を２回以上繰り返す場合において、２回目以降の乗算は、１回目の乗算結果を用いることができるので、行う必要がない。このため、２回目以降の乗算については、前記の乗算の回数の計数において、計数しない。
（従来例４：ＳＥＡアルゴリズムを用いる楕円曲線の構成方法）
Ｌｅｒｃｉｅｒは、「Finding Good Random Elliptic Curves for Cryptosystems Defined over F(2^n)」（R.Lercier 、EUROCRYPT'97、Springer-Verlag、１９９７年、３７９ページ〜３９２ページ）において、ＳＥＡアルゴリズムを用いる楕円曲線構成方法を提案している。この楕円曲線構成方法では、従来例１に示す楕円曲線構成方法における前記与えられる条件を「楕円曲線の位数が素数であること」と設定している。
【００１９】
ＬｅｒｃｉｅｒによるＳＥＡアルゴリズムを用いる楕円曲線構成方法について、図２〜図３に示すフローチャートを用いて説明する。
ここで、ｐを素数とし、これを入力値とする。有限体ＧＦ（ｐ）上の楕円曲線をＥ、楕円曲線ＥのｔｗｉｓｔをＥ’とする。この場合、Ｅの位数をｐ＋１−ｔとすると、Ｅ’の位数はｐ＋１＋ｔとなるという関係がある。
【００２０】
有限体ＧＦ（ｐ）の元ｕをランダムに選び（ステップＳ９３１）、元ｕを基にして、楕円曲線Ｅのパラメタを決定し（ステップＳ９３２）、初期値としてフラグｆｌａｇ＃ｅｌｌ及びフラグｆｌａｇ＃ｔｗｉｓｔを１に設定する（ステップＳ９３３）。
次に、ＳＥＡアルゴリズムを用いて楕円曲線Ｅ、Ｅ’のそれぞれの位数を計算する（ステップＳ９３４）。
【００２１】
Ｅの位数がＬで割り切れるとき（ステップＳ９３５）、ｆｌａｇ＃ｅｌｌ＝０とし（ステップＳ９３６）、Ｅ’の位数がＬで割り切れるとき（ステップＳ９３７）、ｆｌａｇ＃ｔｗｉｓｔ＝０とし（ステップＳ９３８）、ｆｌａｇ＃ｅｌｌ＝０であり、かつｆｌａｇ＃ｔｗｉｓｔ＝０である場合（ステップＳ９４０）、ステップＳ９３１に戻る。そうでない場合（ステップＳ９４０）、次のステップＳ９４１へ進む。
【００２２】
次に、ｆｌａｇ＃ｅｌｌ＝１であるとき（ステップＳ９４１）、Ｅの位数を素数判定し、Ｅの位数が素数でなければ（ステップＳ９４２）、ステップＳ９４３へ進む。素数であれば（ステップＳ９４２）、次のステップＳ９４５へ進む。また、ｆｌａｇ＃ｔｗｉｓｔ＝１であるとき（ステップＳ９４３）、Ｅ’の位数を素数判定し、Ｅ’の位数が素数でなければ（ステップＳ９４４）、ステップＳ９３１へ戻る。素数であれば（ステップＳ９４４）、次のステップＳ９４５へ進む。ｆｌａｇ＃ｔｗｉｓｔ＝１でないとき（ステップＳ９４３）、ステップＳ９３１へ進む。
【００２３】
位数＝ｐであるか否かを判定し、位数＝ｐであるとき（ステップＳ９４５）、ステップＳ９３１へ戻る。位数＝ｐでないとき（ステップＳ９４５）、楕円曲線のパラメタを出力する（ステップＳ９４６）。
Ｌｅｒｃｉｅｒによる楕円曲線構成方法において、ステップＳ９３３の操作は計算時間を短縮するために用いる手法である。これを行うことにより、ＳＥＡアルゴリズムに要する時間が短縮される。しかし、ステップＳ９３２において、楕円曲線Ｅの位数が素数である可能性の低い場合も含めて、楕円曲線のパラメタを決定しているため、ＳＥＡアルゴリズムによる計算処理を含むステップＳ９３４を繰り返す回数が増える。このため、全体の計算量が大きくなる。
【００２４】
【発明が解決しようとする課題】
以上説明したように、楕円曲線の構成において用いられるＳｃｈｏｏｆの位数計算アルゴリズムは、ＳＥＡアルゴリズムにより改良され、また、Ｌｅｒｃｉｅｒにより、さらにＳＥＡアルゴリズムに要する計算量を少なくする方法が提案されているが、さらに、楕円曲線の計算量を少なくしたいという要望がある。
【００２５】
本発明は、第１に、少ない計算量により楕円曲線上の点の演算ができる楕円曲線演算装置を提供することを目的とする。
本発明は、第２に、少ない計算量により楕円曲線の位数計算ができる楕円曲線位数計算装置を提供することを目的とする。
本発明は、第３に、少ない計算量により安全性の高い楕円曲線を構成することができる楕円曲線構成装置を提供することを目的とする。
【００２６】
本発明は、第４に、少ない計算量により安全性が高くなるように構成された楕円曲線を応用する楕円曲線応用装置を提供することを目的とする。
【００２７】
【課題を解決するための手段】
上記の目的を達成するために、本発明は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行う楕円曲線演算装置であって、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得手段と、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換手段とを備え、前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、多項式Ｘ（α）＝ｆ（α）×φ（α）、多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び多項式Ｚ（α）＝１により変換してＪａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算手段を備えることを特徴とする。
【００２８】
ここで、前記取得手段は、楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを取得し、前記変換手段は、取得した１個又は２個のアフィン座標に対して、前記座標変換を施して、それぞれ１個又は２個のＪａｃｏｂｉａｎ座標を生成し、前記演算手段は、前記生成された１個又は２個のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される２倍算又は加算をそれぞれ施すように構成してもよい。
【００２９】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は加算であり、前記取得手段は、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、前記変換手段は、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、前記演算手段は、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【００３０】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は２倍算であり、前記取得手段は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換手段は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算手段は、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【００３１】
また、本発明は、ＳＥＡアルゴリズムにより楕円曲線の位数計算を行う楕円曲線位数計算装置であって、前記楕円曲線位数計算装置は、上記の楕円曲線演算装置を含むことを特徴とする。
また、本発明は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定する楕円曲線構成装置であって、乱数を生成する乱数生成手段と、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成手段と、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定手段と、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算手段と、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定手段と、前記安全性判定手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成手段、前記パラメタ生成手段、前記有限性判定手段、前記位数計算手段及び前記安全性判定手段に対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように制御する繰返制御手段と、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力手段とを備えることを特徴とする。
【００３２】
ここで、前記楕円曲線Ｅは、ｙ＾２＝ｘ＾３＋ａｘ＋ｂにより示され、ここで、パラメタａ及びパラメタｂは定数であり、前記パラメタ生成手段は、パラメタａ＝−３とし、パラメタｂを前記生成された乱数として選択することにより、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、パラメタを選択するように構成してもよい。
【００３３】
ここで、前記有限性判定手段は、楕円曲線Ｅを有理数体上の楕円曲線ＥＱとみなし、２個の素数ｐ１、ｐ２をあらかじめ有し、ｐ１≠ｐ２であり、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出し、算出された位数ｍ１、ｍ２が互いに素であることを判定し、互いに素であると判定する場合に、楕円曲線Ｅが有理数体上において有限位数の点を持たないと判定するように構成してもよい。
【００３４】
ここで、前記有限性判定手段は、素数ｐ１＝５及び素数ｐ２＝７をあらかじめ有し、２個の素数ｐ１＝５、ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出するように構成してもよい。
また、本発明は、楕円曲線を用いて処理を行う楕円曲線応用装置であって、前記楕円曲線応用装置は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定する楕円曲線構成手段を含み、前記楕円曲線構成手段は、上記の楕円曲線構成装置を備えることを特徴とする。
【００３５】
【発明の実施の形態】
本発明に係る１の実施の形態としての楕円曲線構成装置５００について説明する。
１  楕円曲線構成装置５００の構成
楕円曲線構成装置５００は、素数ｐが与えられたとき、有限体ＧＦ（ｐ）上で定義され、素数である位数（位数≠ｐ）を有する楕円曲線を構成するパラメタを出力する。ここで、構成される前記楕円曲線の安全性は高い。
【００３６】
楕円曲線構成装置５００は、図４に示すように、乱数生成部５０１、楕円曲線設定部５０２、楕円曲線有限性判定部５０３、楕円曲線位数計算部５０４、楕円曲線条件判定部５０５、制御部５０６、情報記憶部５０７、入力部５０８、出力部５０９及びパラメタ記憶部５１０から構成される。楕円曲線構成装置５００は、具体的には、図５に示すように、マイクロプロセッサ１１、ＲＯＭ（ＲｅａｄＯｎｌｙ  Ｍｅｍｏｒｙ）１２、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１３、ハードディスク１４、キーボード１５、ディスプレィ１６などから構成され、ハードディスク１４には、コンピュータプログラムが記憶されている。乱数生成部５０１、楕円曲線設定部５０２、楕円曲線有限性判定部５０３、楕円曲線位数計算部５０４、楕円曲線条件判定部５０５、制御部５０６、入力部５０８及び出力部５０９は、ハードディスク１４に記憶されている前記コンピュータプログラムをマイクロプロセッサ１１により実行することにより、その機能を達成する。
１．１  入力部５０８
入力部５０８は、具体的には、キーボード１５などから構成され、楕円曲線を構成する旨の構成指示を利用者から受け付け、また同時に素数ｐ（ｐ≠２）の入力を受け付ける。ここで、素数ｐは、１６０ビットのビット数を有する。
【００３７】
入力部５０８は、前記構成指示を受け付けると、前記構成指示と前記素数ｐを制御部５０６へ出力する。
１．２  情報記憶部５０７
情報記憶部５０７は、図６に示すように、素数ｐ、乱数ｔ、パラメタａ、パラメタｂ、位数ｍをそれぞれ記憶するための領域を有し、各領域は、１６０ビットのビット数を有している。情報記憶部５０７は、具体的には、ＲＡＭ１３から構成されている。
【００３８】
ここで、パラメタａ及びｂは、有限体ＧＦ（ｐ）上で定義された楕円曲線Ｅを示す式  ｙ＾２＝ｘ＾３＋ａｘ＋ｂ  における係数である。
１．３  乱数生成部５０１
乱数生成部５０１は、制御部５０６より乱数生成の指示を受け取る。
乱数生成部５０１は、乱数生成の指示を受け取ると、１６０ビットのビット数を有する乱数ｔを生成し、生成した乱数ｔを情報記憶部５０７へ書き込む。
１．４  楕円曲線設定部５０２
（１）楕円曲線設定部５０２の機能及び構成
楕円曲線設定部５０２は、情報記憶部５０７から乱数ｔを読み出す。また、楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂ  におけるパラメタａ、ｂについて
パラメタａ＝−３と設定し、
パラメタｂ＝乱数ｔと設定する。
【００３９】
従って、楕円曲線Ｅは、ｙ＾２＝ｘ＾３−３ｘ＋ｔ  と表現される。
楕円曲線設定部５０２は、設定したパラメタａ及びｂを情報記憶部５０７へ書き込む。
（２）楕円曲線をｙ＾２＝ｘ＾３−３ｘ＋ｔとする理由
楕円曲線Ｅ：ｙ＾２＝ｘ＾３−３ｘ＋ｔは、以下に説明するように、素数位数を持つ確率が高いので、楕円曲線設定部５０２により設定される楕円曲線Ｅは、安全な楕円曲線である確率が高い。
【００４０】
次に、楕円曲線Ｅ：ｙ＾２＝ｘ＾３−３ｘ＋ｔが素数位数を持つ確率が高い理由について、以下に説明する。
有理数体上の曲線
Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂ（ａ、ｂは整数）
に対して、判別式ＴＤを次のように定義する。
ＴＤ＝４×ａ＾３＋２７×ｂ＾２
この場合において、Ｅが楕円曲線であることと、この判別式ＴＤが０でないこととは同値である。このことは、「The Arithmetic of Elliptic Curves」（J.H.Silverman著、ＧＴＭ１０６、Springer-verlag、１９８６年。以下、文献１と称する。）の５０ページに示されている。
【００４１】
以下においては、判別式ＴＤは０でない、すなわち、Ｅは楕円曲線であるとする。
文献１の２２１ページに以下の定理が示されている。
［定理１］楕円曲線Ｅ上に有限位数をもつ点が存在するとき、その座標（ｘ、ｙ）は整数であり、判別式ＴＤはｙ＾２で割り切れる。
【００４２】
この定理１より、楕円曲線Ｅ上の点Ｐ＝（ｘ、ｙ）において、判別式ＴＤがｙ＾２で割り切れないとき、点Ｐは有限位数を持たないと言える。ゆえに、判別式ＴＤが平方因子を持たず、かつ、楕円曲線Ｅ上に有限位数を持つ点（ｘ、ｙ）が存在する場合、ｙ＝１でなければならない。よって、１＝ｘ＾３＋ａｘ＋ｂのｍｏｄ  ｐでの解を持たない場合は、楕円曲線Ｅ上に有限位数を持つ点が存在しない。このように定理１より、以下の事実が導かれる。
［事実１］判別式ＴＤが平方因子を持つ確率が低い場合は、楕円曲線Ｅ上に有限位数を持つ点が存在する確率が低い。
【００４３】
楕円曲線Ｅのパラメタａ、ｂをＧＦ（ｐ）の元であるとし、楕円曲線Ｅ上の点の座標をＧＦ（ｐ）の元であるとして、得られる楕円曲線をＥｐとする。これらの操作を法ｐで還元するという。楕円曲線Ｅ上の有限位数ｒの点Ｐ＝（ｘ、ｙ）は、法ｐで還元するとＥｐ上の点Ｐｐ＝（ｘ  ｍｏｄ  ｐ、ｙ  ｍｏｄ  ｐ）になる。点Ｐｐは、楕円曲線Ｅｐの零元Ｏに移ることがなく、点Ｐｐは、ｒ以下の位数を持つことになる。
【００４４】
群の理論より、以下の命題１が成り立つ。
［命題１］楕円曲線Ｅｐ上の点Ｐｐの位数がｒであるとき、楕円曲線Ｅｐの位数はｒで割り切れる。
楕円曲線Ｅｐの位数をｍとする。有理数体上の楕円曲線Ｅ上に有限位数の点が存在し、その位数をｒとする。位数ｒがｍに比べて小さいとき、ｍがｒによって割り切られる。よって、Ｅｐの位数は素数でないことになる。このことを逆に考えると、以下の事実が導かれる。
［事実２］有限位数の点を持たない有理数体上の楕円曲線Ｅをｐで還元した楕円曲線Ｅｐは、素数位数を持つ確率が高い。
【００４５】
事実１と事実２とを組み合わせると以下の事実が導かれる。
［事実３］楕円曲線Ｅの判別式ＴＤが平方因子をもつ確率が低い場合、Ｅをｐで還元した楕円曲線Ｅｐは、素数位数をもつ確率が高い。
以下において、楕円曲線
Ｅ１：ｙ＾２＝ｘ＾３＋３ｕｘ＋２ｕ、
Ｅ２：ｙ＾２＝ｘ＾３−３ｘ＋ｔ（ｔ＞０）
について、それぞれの判別式ＴＤの値を調べる。Ｅ１、Ｅ２の判別式ＴＤをそれぞれ、ＴＤ（Ｅ１）、ＴＤ（Ｅ２）とする。このとき、
ＴＤ（Ｅ１）＝２＾２×３＾３×ｕ＾２×（ｕ＋１）
ＴＤ（Ｅ２）＝３＾３×（ｔ＾２−４）
である。
【００４６】
ＴＤ（Ｅ１）の平方因子は少なくとも２、３、６、ｕ、２×３×ｕである。
ＴＤ（Ｅ２）の平方因子については、以下の証明より、ｔ＾２−４が平方数でないことがわかる。
（証明）
ｔをｔ≠０である整数とする。
【００４７】
ｔ≠０より、ｔ＞１とする。なぜなら、ｔ＝１のとき、ｔ＾２−４＝−３となるからである。
この場合、ｔ＾２−４が平方数であると仮定する。すなわち、ある正整数ｎ＞０に対して、ｔ＾２−４＝ｎ＾２とする。
このとき、（ｔ−ｎ）（ｔ＋ｎ）＝４となる。４の約数は１、２、４であり、ｔ−ｎ＜ｔ＋ｎより、ｔ−ｎとｔ＋ｎの組合せは（ｔ−ｎ、ｔ＋ｎ）＝（１、４）、（２、２）、（４、１）である。どの組合せを取っても、ｔ、ｎが整数とならない。（証明終）
上記のように、ｔ＾２−４が平方数でないため、ＴＤ（Ｅ２）は平方因子をもつ確率が低い。よって、ＴＤ（Ｅ１）よりＴＤ（Ｅ２）の方が平方因子をもつ確率が低い。楕円曲線Ｅ１、Ｅ２をｐで還元して得られる楕円曲線をそれぞれ楕円曲線Ｅ１ｐ、Ｅ２ｐとすると、事実３から、楕円曲線Ｅ１ｐより楕円曲線Ｅ２ｐの方が素数位数をもつ確率が高いことがわかる。
【００４８】
以上により、楕円曲線Ｅ２ｐが素数位数をもつ確率が高いことが分かる。
このように、楕円曲線設定部５０２は、楕円曲線の判別式ＴＤが平方因子を持つ確率が所定のしきい値より小さくなるように、パラメタａ、ｂを設定すればよい。
こうして、楕円曲線設定部５０２は、あらかじめ、安全性の高い楕円曲線を選択するので、楕円曲線構成装置５００は、楕円曲線を選択しその安全性を判定するステップを何度も繰り返すことがなく、楕円曲線構成装置５００における計算量が減少する。
１．５  楕円曲線有限性判定部５０３
（１）楕円曲線有限性判定部５０３の機能及び構成
楕円曲線有限性判定部５０３は、情報記憶部５０７から楕円曲線Ｅのパラメタａ及びｂを読み出す。
【００４９】
楕円曲線有限性判定部５０３は、読み出した有限体ＧＦ（ｐ）上の楕円曲線Ｅのパラメタａ、ｂを整数とみなし、楕円曲線Ｅを有理数体上の楕円曲線とみなす。
楕円曲線有限性判定部５０３は、素数ｐより小さい素数ｐ１、ｐ２を選択する。ここで、ｐ１≠ｐ２である。なお、一例として、素数ｐ１＝５、素数ｐ２＝７とする。次に、前記有理数体上の楕円曲線を素数ｐ１、ｐ２を法として還元した楕円曲線をそれぞれＥｐ１、Ｅｐ２とし、楕円曲線Ｅｐ１、Ｅｐ２のそれぞれの位数ｍ１、ｍ２を、次に示すようにして計算する。ここで、楕円曲線の方程式を、ｙ＾２＝ｘ＾３＋ａｘ＋ｂとする。
【００５０】
【数１】
0004510201.tif 000002
【００５１】
ここで、（ｃ／ｐ）は、平方剰余記号であり、
ｃがｐを法とする平方剰余であるとき、  （ｃ／ｐ）＝＋１、
ｃがｐを法とする非平方剰余であるとき、（ｃ／ｐ）＝−１、
ｃ＝０のとき、                        （ｃ／ｐ）＝０である。
次に、上記の位数計算式について、簡単に説明する。
【００５２】
１個の値ｎ（０〜ｐ１−１）について、ｎ＾３＋ａ＊ｎ＋ｂが０でない平方数である場合、楕円曲線上の点は２個存在する。ｎ＾３＋ａ＊ｎ＋ｂが０である場合、楕円曲線上の点は１個存在する。ｎ＾３＋ａ＊ｎ＋ｂが平方数でない場合、楕円曲線上の点は存在しない。楕円曲線：ｙ＾２＝ｘ＾３＋ａｘ＋ｂ上において、値ｎ（０〜ｐ１−１）をｘ座標とする点の数は、
【００５３】
【数２】
0004510201.tif 000003
【００５４】
と表現できる。
従って、０〜ｐ１−１のｐ１個の値について、楕円曲線上の点の数の合計は、
【００５５】
【数３】
0004510201.tif 000004
【００５６】
と表現できる。これにより、前記位数計算式が得られる。ここで、この計算式の最初の１は零点Ｏの数を表している。
なお、この位数の算出方法については、「Ｃｏｕｎｔｉｎｇ  ｐｏｉｎｔｓ  ｏｎ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅ  ｏｖｅｒ  ｆｉｎｉｔｅ  ｆｉｅｌｄｓ」（Ｒ．  Ｓｃｈｏｏｆ著、Ｊｏｒｎａｌ  ｄｅ  Ｔｈｅｏｒｉｅ  ｄｅｓ  Ｎｏｍｂｒｅｓ  ｄｅ  Ｂｏｒｄｅａｕｘ  ７、１９９５年、以下文献Ｓｃｈ２と呼ぶ。）の２１９〜２２０ページに示されている。
【００５７】
次に、楕円曲線有限性判定部５０３は、計算した位数ｍ１と位数ｍ２とを用いて、位数ｍ１とｍ２が互いに素であるか判定し、位数ｍ１とｍ２が互いに素であるか否かを示す位数判定情報を制御部５０６へ出力する。
なお、素数ｐ１及びｐ２は、小さい値であるので、前記位数計算式を用いて位数を計算する場合において、その計算量は、実用的な範囲内である。
（２）位数ｍ１とｍ２が互いに素であることを判定する理由
有理数体上の楕円曲線Ｅについて以下の定理が成り立つ。この定理は、文献１の１７６ページに示されている。
［定理３］有理数体上の楕円曲線Ｅを素数ｐ１、ｐ２（ｐ１≠ｐ２）によって還元した楕円曲線をそれぞれＥｐ１、Ｅｐ２とする。楕円曲線Ｅｐ１、Ｅｐ２の位数をそれぞれｍ１、ｍ２とする。位数ｍ１と位数ｍ２が互いに素であるとき、楕円曲線Ｅは有限位数の点をもたない。
【００５８】
楕円曲線Ｅｐ１とＥｐ２の位数が互いに素である場合、Ｅが有限位数の点を持たないため、上記の事実２により、Ｅｐは素数位数を持つ楕円曲線になる確率が高い。逆に、楕円曲線Ｅｐ１とＥｐ２の位数が互いに素でない場合、Ｅが有限位数の点を持つため、上記の事実２により、Ｅｐは素数位数を持たない楕円曲線になる確率が高く、この楕円曲線の安全性は低くなる。このため、楕円曲線Ｅｐ１とＥｐ２の位数が互いに素でない場合には、この楕円曲線の採用は棄却する。
【００５９】
こうして、位数計算を行う前に、安全性の低い楕円曲線を棄却し、安全性の低い楕円曲線の位数計算を行わないようにすることができ、位数計算の計算量を削減することが可能となる。
なお、素数ｐ１、ｐ２は素数ｐより小さい素数であれば何でもよいが、上記に示すように、素数ｐ１＝５、素数ｐ２＝７とすればよい。この組合せが最も小さい素数の組合せであるので、このとき、位数の計算量が最も小さくなる。
【００６０】
また、素数ｐ１（又は素数ｐ２）を３としたとき、楕円曲線の判別式ＴＤが、ｍｏｄ  ３を取れば、０になるので、Ｅｐ１（又はＥｐ２）が楕円曲線でなくなる。そのため、素数ｐ１（又は素数ｐ２）を３としてはならない。
１．６  楕円曲線位数計算部５０４
楕円曲線位数計算部５０４は、次に示すようにして、有限体ＧＦ（ｐ）上の楕円曲線Ｅの位数を計算する。
１．６．１  ＳＥＡアルゴリズムによる位数の算出
楕円曲線位数計算部５０４は、ＳＥＡアルゴリズムにより楕円曲線の位数計算を行う。
【００６１】
楕円曲線Ｅの位数をｍとし、ｔを
ｍ＝ｐ＋１−ｔ
を満たすものとする。また、
ｆ（ｘ）＝ｘ＾３＋ａｘ＋ｂ
とする。
【００６２】
楕円曲線位数計算部５０４は、初期値として、整数変数Ｌ＝２とする。
楕円曲線位数計算部５０４は、Ｍｏｄｕｌａｒ多項式ΦＬ（Ｔ，ｊ（Ｅ））の一変数Ｔの多項式環ＧＦ（ｐ）［Ｔ］における因数分解の一次因子の数を算出する。
次に、楕円曲線位数計算部５０４は、算出した一次因子の数が２のとき、ｔ  ｍｏｄ  Ｌを求め、Ｉｓｏｇｅｎｙ  ｃｙｃｌｅ法により、ｔ  ｍｏｄ  Ｌ＾ｎを求める。
【００６３】
算出した一次因子の数が１またはＬ＋１のとき、ｔ  ｍｏｄ  Ｌを求め、Ｉｓｏｇｅｎｙ  ｃｙｃｌｅ法を適用可能であるか判定し、適用可能なら、Ｉｓｏｇｅｎｙ  ｃｙｃｌｅ法により、ｔ  ｍｏｄ  Ｌ＾ｎ（ｎ＝２，３，．．．）を求める。
算出した一次因子の数が０のとき、ｔ  ｍｏｄ  Ｌの取り得る値を集合［０、１、・・・、Ｌ−１］から絞り込む。
【００６４】
次に、楕円曲線位数計算部５０４は、
Ｌ１＾（ｎ１）×Ｌ２＾（ｎ２）×・・・×Ｌｋ＾（ｎｋ）
＜  ４×ｐ＾（１／２）
（ここで、Ｌ１、Ｌ２、・・・、Ｌｋは素数であり、Ｌｋ＝Ｌ）
であるとき、Ｌ＝（Ｌの次に大きい素数）とし、再度前記一次因子の数の算出、一次因子の数毎の処理を、前記条件式を満たさなくなるまで繰り返す。
【００６５】
次に、前記条件式を満たさないとき、楕円曲線位数計算部５０４は、ｍａｔｃｈ＆ｓｏｒｔアルゴリズムにより、位数ｍを確定し、位数ｍを情報記憶部５０７へ書き込む。
なお、この位数計算方法については、「Counting the number of points on elliptic curves over finite fields: strategies performances」（R.Lercier、F.Morain著、EUROCRYPT'95、Springer-Verlag、１９９５年、７９ページ〜９４ページ）に詳しく説明されている。
【００６６】
また、ｍａｔｃｈ＆ｓｏｒｔアルゴリズムについては、「Algorithmique des courbes elliptiques dans les corps finis」（ Thesis, Ecole Polytechnique-LIX, (1997), in French, 195〜202ページ）、又は、「Elliptic Curves in Cryptography", London Mathematical Society, Lecture Note Series 265, CAMBRIDGE UNIVERSITY PRESS,(1999), 142〜144ページ)に説明されている。
１．６．２  ＳＥＡアルゴリズムによる位数の算出方法についての補足説明
ＳＥＡアルゴリズムによる位数の算出方法について、補足的に説明する。楕円曲線位数計算部５０４は、以下に説明する位数の算出を行う。
【００６７】
位数計算を行う対象となる楕円曲線をGF(p)上の楕円曲線を、
Ｅ：ｙ＾２＝ｆ（ｘ）
とする。ここで、ｆ（ｘ）＝ｘ＾３＋ａｘ＋ｂ  である。
（１）固有方程式
（１−１）ＧＦ（ｐ）の代数的閉包Ｋ
ＧＦ（ｐ）の代数的閉包（ａｌｇｅｂｒａｉｃ  ｃｌｏｓｕｒｅ）をＫとする。代数的閉包Ｋは、ＧＦ（ｐ）を含む体であり、Ｋの係数をもつ多項式は必ず、一次式に分解できる。
【００６８】
なお、他の代数的閉包の例として、実数体の代数的閉包である複素数体がある。複素数の係数をもつ多項式は必ず、一次式に分解できる。
（１−２）フロベニウス写像（Ｆｒｏｂｅｎｉｕｓ  ｍａｐ）φｐ
楕円曲線上の点Ｐ＝（α、β）（α、β∈Ｋ）に対して、フロベニウス写像φｐを以下のように定義する。
【００６９】
φｐ：（α、β）  →  （α＾ｐ、β＾ｐ）
（α、β）は、Ｅ上の点であるので、
β＾２＝α＾３＋ａα＋ｂ
が成り立つ。両辺をｐ乗すると、
β＾（２ｐ）＝（α＾３＋ａα＋ｂ）＾ｐ
であり、この式の右辺は、「代数概論」（森田康夫著、数学選書９、裳華房、１９８７年）の１９３ページの記述により、
0004510201.tif 000005
となる。なお、ａ、ｂがＧＦ（ｐ）の元であるので、ａ＝ａ＾ｐ、ｂ＝ｂ＾ｐである。
【００７０】
従って、
（β＾ｐ）＾２＝（α＾ｐ）＾３＋ａ（α＾ｐ）＋ｂ
となり、（α＾ｐ、β＾ｐ）も楕円曲線上の点となる。
（１−３）固有多項式（ｃｈａｒａｃｔｅｒｉｓｔｉｃ  ｐｏｌｙｎｏｍｉａｌ）
「Elliptic curves over finite fields and the computation of square roots mod p」（Ｒ．Ｓｃｈｏｏｆ著、Ｍａｔｈ．Ｃｏｍｐ．Ｖｏｌ４４、１９８５年）の４８５ぺージの記述によると、
楕円曲線上の点Ｐ＝（α、β）（α、β∈Ｋ）に対して、以下の式が成り立つ。
【００７１】
（φｐ）＾２（Ｐ）  −  ｔφｐ（Ｐ）  ＋  ｐＰ  ＝  Ｏ
ここで、Ｏは楕円曲線の群の零元である。また、ｔはトレースと呼ばれ、上式の＋、−は、楕円曲線上の加算、減算を示す記号である。
Ｈａｓｓｅの定理より、ｔから位数は以下の式より求められる。
位数＝ｐ＋１−ｔ
よって、トレースｔを求めることにより、位数を計算することができる。
【００７２】
点ＰをＥ上のＬ等分点（Ｌ：素数）、すなわち、ＬＰ＝Ｏを満たす点とするとき、以下の式が成り立つ。
（φｐ）＾２（Ｐ）  −  （ｔ  ｍｏｄ  Ｌ）φｐ（Ｐ）
＋  （ｐ  ｍｏｄ  Ｌ）Ｐ  ＝  Ｏ
ＳＥＡアルゴリズムでは、この方程式から、ｔ  ｍｏｄ  Ｌを計算する。
【００７３】
ここで、φｐが固有値ｋをもつとは、あるＥ上のＬ等分点Ｐに対し、
φｐ（Ｐ）  ＝  ｋＰ
が成り立つことである。ここで、ｋＰは、楕円曲線上の冪倍点である。
このとき、φｐの固有多項式は、
ｋ＾２  Ｐ  −  （ｔ  ｍｏｄ  Ｌ）ｋＰ
＋  （ｐ  ｍｏｄ  Ｌ）Ｐ  ＝  Ｏ
となる。よって、固有値ｋが存在するとき、φｐの固有多項式は、
ｋ＾２  −  （ｔ  ｍｏｄ  Ｌ）ｋ  ＋  （ｐ  ｍｏｄ  Ｌ）  ＝  ０
の形の変数ｋの２次方程式と考えられる。ＳＥＡアルゴリズムでは、この方程式のＧＦ（Ｌ）の根の有無により、以下の場合に分ける。
【００７４】
前記２次方程式が、異なる根ｋ１、ｋ２をもつ場合（Ｃａｓｅ１）
前記２次方程式が、重根をもつ場合（Ｃａｓｅ２）
前記２次方程式が、根をもたない場合（Ｃａｓｅ３）
以下において、３つのケースの処理について説明する。
（Ｃａｓｅ１）前記２次方程式が、異なる根ｋ１、ｋ２をもつ場合
前記２次方程式が、異なる根ｋ１、ｋ２をもつ場合には、
ｋ＾２  −  （ｔ  ｍｏｄ  Ｌ）ｋ  ＋（ｐ  ｍｏｄ  Ｌ）
＝  （ｋ−ｋ１）（ｋ−ｋ２）
とおくことができ、
ｋ１＋ｋ２  ＝  ｔ  ｍｏｄ  Ｌ、ｋ１＊ｋ２＝ｐ  ｍｏｄ  Ｌ
となる。したがって、ｋ１が求まれば、
ｔ  ＝  ｋ１  ＋  ｐ／ｋ１  ＝  （ｋ１＾２＋ｐ）／ｋ１  ｍｏｄ  Ｌ
より、ｔを求められる。
（Ｃａｓｅ２）前記２次方程式が、重根をもつ場合
前記２次方程式が、重根をもつ場合には、
ｋ１＾２＝ｐ  ｍｏｄ  Ｌ
であるので、ｋ  は
±  √（ｐ）  ｍｏｄ  Ｌ
のどちらかの値をもつ。これは、
φｐ  Ｐ  ＝  ±（√（ｐ）  ｍｏｄ  Ｌ）  Ｐ
のどちらが成り立つかによりで確定する。
【００７５】
φｐの固有値によって、ｔは、
±２  √（ｐ）  ｍｏｄ  Ｌ
のどちらかの値になる。
（Ｃａｓｅ３）前記２次方程式が、根をもたない場合
前記２次方程式が、根をもたない場合には、
（（φｐ）＾２＋（ｐ  ｍｏｄ  Ｌ））Ｐと
（ｔ’  ｍｏｄ  Ｌ）φｐＰとの座標比較を行い、一致する場合のｔ’を正しいｔ  ｍｏｄ  Ｌとする。
（１−４）ケースの判定
上記のＣａｓｅ１、Ｃａｓｅ２、Ｃａｓｅ３は、ｔ  ｍｏｄ  Ｌが分からないので、どのケースに該当するか本来は分からない。
【００７６】
しかしながら、Ｍｏｄｕｌａｒ多項式とよばれる多項式のＧＦ（ｐ）の根の数により、判定することができる。
Ｍｏｄｕｌａｒ多項式ΦＬ（Ｔ，ｊ（Ｅ））のＧＦ（ｐ）の根の数が２個の場合は、Ｃａｓｅ１に該当する。根の数が１個又はＬ＋１個の場合は、Ｃａｓｅ２に該当する。根の数が０個の場合は、Ｃａｓｅ３に該当する。
【００７７】
なお、詳細については、「Counting points on elliptic curve over finite fields」（R. Schoof 著、Jornal de Theorie des Nombres de Bordeaux 7 、1995年）の２３９ページに記載されているので、説明を省略する。
（１−５）Ｃａｓｅ３の場合の固有方程式の解き方
Ｃａｓｅ３の場合について、固有方程式の解き方について、説明する。
【００７８】
Ｌ等分点、すなわち、ＬＰ＝Ｏを満たすＥ上の点Ｐ全体のｘ座標を根としてもつ多項式を、Ｌ等分多項式といい、ｆＬ（α）で表す。このとき、「Ｐ＝（α，β）がＬ等分点である」と「ｆＬ（α）＝０」とは同値である。
ｆＬ（α）は漸化式を使用して求められる。なお、詳細については、「Elliptic curves over finite fields and the computation of square roots mod p」（Ｒ．Ｓｃｈｏｏｆ著、Ｍａｔｈ．Ｃｏｍｐ．、Ｖｏｌ４４、１９８５年）の４８５ページに記載されているので、説明を省略する。
（１−６）固有方程式の多項式表現
固有方程式から
（式１）
（φｐ）＾２（Ｐ）＋（ｐ  ｍｏｄ  Ｌ）Ｐ＝（ｔ  ｍｏｄ  Ｌ）φｐＰ
であることが分かる。点Ｐの座標を（α，β）とすると、点Ｐ（α，β）は、楕円曲線上の点であるので、
β＾２−α＾３−ａα−ｂ＝０
を満たし、Ｌ等分点であるので、
ｆＬ（α）＝０  を満たす。
【００７９】
ここで、式１の点Ｐの座標を、α，βを変数とする多項式剰余環
Ｒ＝ＧＦ（ｐ）［α，β］／（β＾２−α＾３−ａα−ｂ，ｆＬ（α））
で表す。
多項式剰余環Ｒでの演算は、「β＾２」を、「α＾３＋ａα＋ｂ」に書き換え、「ｆＬ（α）」を「０」にして行う。
【００８０】
以下において、ｉｎ  Ｒと明記した場合、この多項式剰余環Ｒでの演算を行うものとする。
このとき、式１より、
（式２）
（α＾（ｐ＾２）、β＾（ｐ＾２））  ＋  （ｐ  ｍｏｄ  Ｌ）（α、β）
＝  （ｔ  ｍｏｄ  Ｌ）  （α＾ｐ、β＾ｐ）  ｉｎ  Ｒ
が成り立つ。
（１−７）Ｃａｓｅ１の場合の固有方程式の解き方
Ｃａｓｅ１の場合の固有方程式の解き方について説明する。
【００８１】
Ｃａｓｅ１では、φｐ  Ｐ  ＝  ｋ  Ｐ  を満たす  ｋ  を求める。
このとき、前記Ｌ等分多項式ｆＬ（α）の因子ｈ（α）を用いる。すなわち、ｈ（α）はｆＬ（α）を割り切る。ｈ（α）の求め方については、「Counting points on elliptic curve over finite fields」（Ｒ．Ｓｃｈｏｏｆ著、Jornal de Theorie des Nombres de Bordeaux 7、１９９５年）の２４２〜２５３ページに記載されているので、説明を省略する。
（１−８）Ｃａｓｅ２の場合の固有方程式の解き方
Ｃａｓｅ２の場合の固有方程式の解き方について説明する。
【００８２】
Ｃａｓｅ２では、ｋ  が  ±√ｐ  まで分かっているので、ｙ座標の比較を行い、符号を決定する。
なお、Ｃａｓｅ１、Ｃａｓｅ２の計算量に比べ、Ｃａｓｅ３の計算量が大きいため、Ｃａｓｅ３では、ｔ  ｍｏｄ  Ｌを求めない。ｔ  ｍｏｄ  Ｌの取りうる値の候補に絞り込む計算を行う。このようにすると、Ｃａｓｅ３の計算量は、Ｃａｓｅ１又はＣａｓｅ２の計算量とほぼ同じになる。
【００８３】
ただし、Ｌが小さい場合（Ｌ＜＝５）には、計算量が小さいため、正しいｔ  ｍｏｄ  Ｌを求める。
なお、絞り込み計算については、「Counting points on elliptic curve over finite fields」（Ｒ．Ｓｃｈｏｏｆ著、Jornal de Theorie des Nombres de Bordeaux 7、１９９５年）の２３９〜２４１ページに詳しく説明されている。
１．６．３  ｔ ｍｏｄ Ｌ＾ｎの算出
楕円曲線位数計算部５０４は、次に示すようにして、ｔ ｍｏｄ Ｌ＾ｎを算出する。
（１）ｔ ｍｏｄ Ｌ の算出
楕円曲線位数計算部５０４は、ｈ（α）を入力として、以下に示すようにして、ｔ ｍｏｄ Ｌを計算し、ｔ ｍｏｄ Ｌを出力する。
【００８４】
多項式剰余環Ｒを
Ｒ＝ＧＦ（ｐ）[α，β]／（β＾２−α＾３−ａα―ｂ，ｈ（α））
とする。ｔ ｍｏｄ Ｌを求めるには、
φｐ（（α，β））＝ｋ（α，β） ｉｎ Ｒ
を満たすｋを求める必要がある。
【００８５】
楕円曲線位数計算部５０４は、ｋ'を、０の値から（Ｌ−１）／２の値まで、順に変化させて、
φｐ（（α，β）） ｉｎ Ｒ のｘ座標と、
ｋ'（α，β）  ｉｎ Ｒ  のｘ座表とを算出し、
それぞれのｋ'について、
算出した φｐ（（α，β））  ｉｎ Ｒ のｘ座標と、
算出した ｋ'（α，β） ｉｎ Ｒ のｘ座標とを比較し、
初めて一致する場合に、
φｐ（（α，β）） ｉｎ Ｒ のｙ座標と、
ｋ'（α，β） ｉｎ Ｒ のｙ座標とを算出し、
φｐ（（α，β）） ｉｎ Ｒ のｙ座標と、
ｋ'（α，β） ｉｎ Ｒ のｙ座標とが一致する場合に、ｋ＝ｋ' ｍｏｄ Ｌとし、一致しない場合に、ｋ＝Ｌ−ｋ’ ｍｏｄ Ｌとする。
【００８６】
さらに、ｔ＝（ｋ＾２＋ｐ）／ｋ ｍｏｄ Ｌとし、ｔを出力する。
（２）Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法によるｔ ｍｏｄ Ｌ＾ｎの算出
楕円曲線位数計算部５０４は、Ｉｓｏｇｅｎｙ ｃｙｃｌｅ法によりｔ ｍｏｄＬ＾ｎを求める。
Ｃａｓｅ１では、まず、楕円曲線位数計算部５０４は、ｎ＝２とし、ｋ ｍｏｄ Ｌとｈ（α）を基に多項式Ｈ（α）を求め、それを改めて、ｈ（α）とする。その多項式ｈ（α）を用いて、ｋ ｍｏｄ Ｌ＾ｎを求める。次に、多項式ｈ（α）の次数により、次に進むか否かを判定する。ｈ（α）の次数をｄｅｇ（ｈ（α））とする。そのとき、
（ｄｅｇ（ｈ）＾２）＊Ｌ＾２＊（Ｌ＾（２＊ｎ））
＞ （｜ｐ｜）＾３／１３５ であるか否かを判断する。ここで、｜ｐ｜はｐのビット数である。前記判断式が真であれば、
ｔ＝（ｋ＾２＋ｐ）／ｋ ｍｏｄ Ｌ＾ｎ
として、Ｉｓｏｇｅｎｙ ｃｙｃｌｅを終了する。偽であれば、ｎに１を加算して、前記不等式を満たすまで、前記処理を繰り返す。こうして、楕円曲線位数計算部５０４は、ｔ ｍｏｄ Ｌ＾ｎを求める。
【００８７】
なお、Ｃａｓｅ２の場合も、楕円曲線位数計算部５０４は、Ｃａｓｅ１と同様に行うが、必ずしもＩｓｏｇｅｎｙ ｃｙｃｌｅが行えるとは限らない。したがって、楕円曲線位数計算部５０４は、Ｉｓｏｇｅｎｙ ｃｙｃｌｅを行えるか否かの判定を行う。
次に、ｋ ｍｏｄ Ｌ＾ｎ（ｎ＞１の場合）の算出について、説明する。
【００８８】
ここで、ｋ＿ｉ＝ｋ ｍｏｄ Ｌ＾ｉ （１≦ｔ≦ｎ） とする。
楕円曲線位数計算部５０４は、ｋ ｍｏｄ Ｌ＾（ｎ−１）とｈ（α）を入力として、次に示すようにして、ｋ ｍｏｄ Ｌ＾ｎを算出する。
多項式剰余環Ｒを
Ｒ＝ＧＦ（ｐ）[α，β]／（β＾２−α＾３−ａα―ｂ，ｈ（α））
とする。ｋ ｍｏｄ Ｌ＾ｎを求めるには、
φｐ（（α，β））
＝ （ｋ＿（ｎ−１）＋Ｌ＾（ｎ−１）＊κ） （α，β） ｉｎ Ｒ
を満たすκを求める必要がある。
【００８９】
楕円曲線位数計算部５０４は、κ’を、０の値から（Ｌ−１）／２の値まで、順に変化させて、
φｐ（（α，β）） ｉｎ Ｒ のｘ座標と、
（ｋ＿（ｎ−１）＋Ｌ＾（ｎ−１）＊κ’） （α，β）  ｉｎ Ｒ  のｘ座表とを算出し、
それぞれのκ’について、
算出した φｐ（（α，β））  ｉｎ Ｒ のｘ座標と、
算出した （ｋ＿（ｎ−１）＋Ｌ＾（ｎ−１）＊κ’） （α，β） ｉｎ Ｒ のｘ座標とを比較し、
初めて一致する場合に、
ｋ＿ｎ＝ｋ＿（ｎ−１）＋Ｌ＾（ｎ−１）＊κ’ ｍｏｄ Ｌ＾ｎ
とし、ｋ＿ｎをｋ ｍｏｄ Ｌ＾ｎとする。
【００９０】
なお、これらの処理については、「Isogeny cycles and the Schoof-Elkies-Atkin algorithm」（J.M.Couveignes、L.Dewaghe及びF.Morain著、ＬＩＸ／ＲＲ／９６／０３、１９９６年）に詳しく説明されている。
１．６．４  楕円曲線位数計算部５０４による終了判定
楕円曲線位数計算部５０４は、すでに説明したように、ΠＬｋ＾（ｎｋ）  が４  √ｐ  を超えるとき、ＳＥＡアルゴリズムによる繰返し計算の終了と判定し、位数を確定し、楕円曲線位数計算部５０４による計算を終了する。
【００９１】
しかしながら、楕円曲線位数計算部５０４は、楕円曲線条件判定部５０５により、安全な楕円曲線でないと判定される楕円曲線を予め排除して、計算時間を削減するために、楕円曲線位数計算部５０４内部において、楕円曲線の判定を行う。
具体的には、楕円曲線位数計算部５０４は、ｔ  ｍｏｄ  Ｌが確定した時点で、ｐ＋１−ｔ  ｍｏｄ  Ｌを算出し、ｐ＋１−ｔ  ｍｏｄ  Ｌ  ＝  ０であるか否かを判断し、ｐ＋１−ｔ  ｍｏｄ  Ｌ  ＝  ０である場合は、楕円曲線の位数が素数になり得ないので、当該楕円曲線の採用を棄却するために、楕円曲線棄却情報を制御部５０６へ出力し、楕円曲線位数計算部５０４による計算を終了する。
【００９２】
このように、楕円曲線位数計算部５０４において、ｔ  ｍｏｄ  Ｌが確定した時点で、安全性の低い楕円曲線を棄却するので、楕円曲線位数計算部５０４において、無駄な処理を行わないようにすることができる。
なお、この方法については、「Finding Good Random Elliptic Curves for Cryptosystems Defined over F_{2^n}」（Ｒ．  Ｌｅｒｃｉｅｒ著、Advances in Cryptology-Proceedings of Eurocrypt'97、Lecture Notes in Computer Science、１２３３、１９９７年、Springer-Verlag）に記載されている。
１．６．５  冪倍点の計算
上記に説明したように、φpの固有値を求めるには、楕円曲線の冪倍点演算が必要になる。以下では、冪倍点の計算方法について説明する。
（１）等分多項式を用いる方法
楕円曲線位数計算部５０４は、上記のｔ  ｍｏｄ  Ｌの算出において、次に示すようにして、冪倍点を計算する。
【００９３】
等分多項式ｆ＿ｎを用いると、ｎ  （α，β）は以下のようになる。
ｎが偶数の場合、
0004510201.tif 000006
ｎが奇数の場合、
0004510201.tif 000007
これについては、「Elliptic curves over finite fields and the computation of square roots mod p」（R.Schoof著、Math.Comp.、４４、１９８５）の４８５〜４８６ページについて、記載されている。
（２）楕円曲線演算を用いる方法
楕円曲線位数計算部５０４は、上記のｔ  ｍｏｄ  Ｌ＾ｎの算出において、次に示すようにして、冪倍点を計算する。
【００９４】
ここで、前記等分多項式を用いると、ｆ＿１からｆ＿（Ｌ＾（ｎ−２））のような必要のない等分多項式を求める必要があり、効率的でない。そこで、楕円曲線位数計算部５０４は、楕円曲線演算によって、求める方法を採用する。
まず、有限体上の楕円曲線演算を適用することを考える。有限体上の演算の場合、２項組座標を用いた演算を採用すれば、除算が必要となる。しかし、除算は乗算に比べ、一般に計算量が大きいため（１０倍程度）、除算を使用しない３項組の演算について考える。多項式剰余環の場合も同様に３項組の場合を考える。
【００９５】
ここで、２項組の座標の第１、２成分をそれぞれ、ｘ座標，ｙ座標と呼ぶ。また、３項組の座標の第１、２、３成分をそれぞれ、Ｘ座標，Ｙ座標，Ｚ座標と呼ぶ。
有限体上のJacobian座標を適用する。入力と出力が同じ形をしていた方が計算しやすいので、多項式剰余環R上の楕円曲線を考え、その上の点の座標を、
(X(α):β*Y(α):Z(α))
として、入力と出力はこの形をしていると設定する。
【００９６】
さらに、以下の変換を使用し、入力と出力の形を変える。この場合にも、Jacobian座標である。
(X'(α):β*Y'(α):Z'(α))  → (β^2*X'(α):β^4*Y'(α):β*Z'(α))
ここで、β^2=f(α)であるので、
X(α)=f(α)*X'(α)
Y(α)=f(α)^2*Y'(α)
Z(α)=Z'(α)
とすると、変換先の点は、
(X(α):Y(α):β*Z(α))
の形をしている。
（２−１）楕円曲線上の点の射影
楕円曲線位数計算部５０４は、楕円曲線Ｅ上の点のアフィン座標
（φ（α）、β×ψ（α））を、
多項式Ｘ（α）＝ｆ（α）×φ（α）、
多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び
多項式Ｚ（α）＝１
により変換して射影座標
（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成する。
【００９７】
ここで、φ（α）及びψ（α）は多項式である。また、「（  ：  ：  ）」は、射影座標を示す。
（２−２）楕円曲線の演算（加算と２倍算）
次に、多項式剰余環上で定義された楕円曲線上の点の演算について説明する。
楕円曲線上の点の演算は、２倍算及び加算に分解することができる。例えば、楕円曲線上の点Ｐについて、１００×Ｐの計算は、
１００×Ｐ＝２（２（Ｐ＋２（２（２（Ｐ＋２Ｐ）））））と表すと、楕円曲線上の点による６回の２倍算と２回の加算により行える。
【００９８】
なお、２倍算及び加算への分解については、Signed Binary 法を用いて行う。
Signed Binary 法については、「Speeding up Elliptic Curve Cryptosystems by Using a Signed Binary Window Method」（K.Koyama, Y.Tsuruoka 著、Advances in Cryptology - CRYPTO'92, Lecture Notes in Computer Science, Vol. 740, Springer-Verlag, (1993), 345〜357ページ）に説明されている。
【００９９】
この楕円曲線の演算において、楕円曲線位数計算部５０４は、α、βを変数とし、有限体ＧＦ（ｐ）上の元を係数とする多項式
β＾２−ｆ（α）
と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする多項式剰余環上の楕円曲線
Ｅ：ｙ＾２＝ｆ（ｘ）
に対して、楕円曲線Ｅ上の点の座標を入力として演算を行い、演算結果として楕円曲線Ｅ上の点の座標を算出する。
（２−２−１）加算
ここでは、加算について説明する。
【０１００】
楕円曲線位数計算部５０４は、楕円曲線Ｅ上の点Ｐ、Ｑ（Ｐ≠±Ｑ）
Ｐ＝（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））、
Ｑ＝（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））
を入力とし、
0004510201.tif 000008
を計算し、次に、
0004510201.tif 000009
を計算する。
【０１０１】
次に、楕円曲線位数計算部５０４は、
β×Ｚ３
を計算し、
Ｐ＋Ｑ＝（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））
を楕円曲線Ｅ上の点ＰとＱとの加算結果とする。
【０１０２】
なお、上記に示す各演算式において、Ｘ１、Ｙ１、Ｚ１、Ｘ２、Ｙ２、Ｚ２、Ｘ３、Ｙ３、Ｚ３、Ｕ１、Ｕ２、Ｓ１、Ｓ２、Ｈ、ｒは、それぞれ変数αに関する多項式であるので、Ｘ１（α）、Ｙ１（α）、Ｚ１（α）などと表記すべきであるが、表記を簡単にするために、（α）を省略して記載しているので、注意を要する。
（２−２−２）２倍算
ここでは、２倍算について説明する。
【０１０３】
楕円曲線位数計算部５０４は、楕円曲線Ｅ上の点
Ｐ＝（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））
を入力とし、
0004510201.tif 000010
を計算し、次に、
0004510201.tif 000011
を計算する。
【０１０４】
次に、楕円曲線位数計算部５０４は、
β×Ｚ３
を計算し、
２Ｐ＝（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））
を楕円曲線Ｅ上の点Ｐの２倍算の結果とする。
【０１０５】
なお、上記に示す各演算式において、Ｘ１、Ｙ１、Ｚ１、Ｘ３、Ｙ３、Ｚ３、Ｓ、Ｍ、Ｔは、それぞれ変数αに関する多項式であるので、Ｘ１（α）、Ｙ１（α）、Ｚ１（α）などと表記すべきであるが、表記を簡単にするために、（α）を省略して記載しているので、注意を要する。
前記加算公式及び前記２倍算公式における乗算の回数は、演算子＊の出現回数を数えると分かるように、それぞれ、１６回、１０回である。多項式乗算の計算量をＰＭｕｌとするとき、前記加算公式及び前記２倍算公式による計算量はそれぞれ、１６×ＰＭｕｌ、１０×ＰＭｕｌである。
【０１０６】
このように、従来例３に示す加算公式の計算量と比較すると、多項式乗算の計算量は、１ＰＭｕｌ増加しており、従来例３に示す２倍算公式の計算量と比較すると、多項式乗算の計算量は２ＰＭｕｌ減少している。
通常、２倍算の演算回数は、加算の演算回数より多いので、２倍算の計算量の減少は、全体の計算量の減少に大きく貢献する。
（２−３）加算公式及び２倍算公式の導出
ここでは、前記加算公式及び前記２倍算公式の導出について説明する。
【０１０７】
有限体上のＪａｃｏｂｉａｎ座標の演算は以下のようになる。
ここで、Ｐ＝（ｘ１：ｙ１：ｚ１），Ｑ＝（ｘ２：ｙ２：ｚ２），Ｐ＋Ｑ＝Ｒ＝（ｘ３：ｙ３：ｚ３）とする。
（加算）（Ｐ≠±Ｑの場合）
加算は、次のようになる。
【０１０８】
ｘ３＝−Ｈ＾３−２＊Ｕ１＊Ｈ＾２＋ｒ＾２，
ｙ３＝−Ｓ１＊Ｈ＾３＋ｒ＊（Ｕ１＊Ｈ＾２−ｘ３），
ｚ３＝ｚ１＊ｚ２＊Ｈ
ここで、Ｕ１＝ｘ１＊ｚ２＾２，Ｕ２＝ｘ２＊ｚ１＾２，Ｓ１＝ｙ１＊ｚ２＾３，Ｓ２＝ｙ２＊ｚ１＾３，Ｈ＝Ｕ２−Ｕ１，ｒ＝Ｓ２−Ｓ１  である。
（２倍算）（Ｐ＝Ｑの場合）
２倍算は、次のようになる。
【０１０９】
ｘ３＝Ｔ，
ｙ３＝−８＊ｙ１＾４＋Ｍ＊（Ｓ−Ｔ），
ｚ３＝２＊ｙ１＊ｚ１
ここで、Ｓ＝４＊ｘ１＊ｙ１＾２，Ｍ＝３＊ｘ１＾２＋ａ＊ｚ１＾４，Ｔ＝−２＊Ｓ＋Ｍ＾２である。
【０１１０】
次に、この演算を多項式剰余環Ｒ上に適用する。
ここで、Ｐ＝（Ｘ１（α）：Ｙ１（α）：β＊Ｚ１（α）），Ｑ＝（Ｘ２（α）：Ｙ２（α）：β＊Ｚ２（α）），Ｐ＋Ｑ＝Ｒ＝（Ｘ３（α）：Ｙ３（α）：β＊Ｚ３（α））とする。
また、上記の演算に適用するため、
ｘ１＝Ｘ１（α），ｙ１＝Ｙ１（α），ｚ１＝β＊Ｚ１（α）
ｘ２＝Ｘ２（α），ｙ２＝Ｙ２（α），ｚ２＝β＊Ｚ２（α）
ｘ３＝Ｘ３（α），ｙ３＝Ｙ３（α），ｚ３＝β＊Ｚ３（α）
とおく。
（多項式剰余環Ｒ上の楕円曲線のＪａｃｏｂｉａｎ座標の加算）
多項式剰余環Ｒ上の楕円曲線のＪａｃｏｂｉａｎ座標の加算は、次のようになる。
【０１１１】
Ｕ１＝Ｘ１＊β＾２＊Ｚ２＾２，
Ｕ２＝Ｘ２＊β＾２＊Ｚ１＾２，
Ｓ１＝Ｙ１＊β＾３＊Ｚ２＾３，
Ｓ２＝Ｙ２＊β＾３＊Ｚ１＾３
ここで、Ｕ１’＝Ｕ１／β＾２，Ｕ２’＝Ｕ２／β＾２，Ｓ１’＝Ｓ１／β＾３，Ｓ２’＝Ｓ２／β＾３とすると、
Ｈ＝（Ｕ２’―Ｕ１’）＊β＾２，ｒ＝（Ｓ２’―Ｓ１’）＊β＾３  である。
【０１１２】
0004510201.tif 000012
である。ここで、ｘ３’＝ｘ３／β＾６とおくと、
0004510201.tif 000013
である。ここで、ｙ３’＝ｙ３／β＾９とおくと、
ｙ３’＝−Ｓ１’＊Ｈ’＾３＋ｒ’＊（Ｕ１’＊Ｈ’＾２−ｘ３’）  であり、
ｚ３＝Ｚ１＊β＊Ｚ２＊β＊Ｈ’＊β＾２  である。
【０１１３】
ここで、ｚ３’＝ｚ３／β＾４とする。
このとき、
Ｘ３＝ｘ３’＊β＾６
Ｙ３＝ｙ３’＊β＾９
β＊Ｚ３＝ｚ３’＊β＾４
である。
【０１１４】
（Ｘ３：Ｙ３：β＊Ｚ３）＝（Ｘ３／β＾６：Ｙ３／β＾９：β＊Ｚ３／β＾４）
であるので、
（Ｘ３：Ｙ３：β＊Ｚ３）＝（ｘ３’：ｙ３’：β＊ｚ３’）
である。
【０１１５】
ここで、改めてｘ３’，ｙ３’，ｚ３’，Ｕ１’，Ｕ２’，Ｓ１’，Ｓ２’，Ｈ’，ｒ’を
それぞれ、Ｘ３，Ｙ３，Ｚ３，Ｕ１，Ｕ２，Ｓ１，Ｓ２，Ｈ，ｒとおくと、本発明の加算公式が導き出せる。
（多項式剰余環Ｒ上の楕円曲線のＪａｃｏｂｉａｎ座標の２倍算）
多項式剰余環Ｒ上の楕円曲線のＪａｃｏｂｉａｎ座標の２倍算は、次のようになる。
【０１１６】
Ｓ＝４＊Ｘ１＊Ｙ１＾２
Ｍ＝３＊Ｘ１＾２＋ａ＊Ｚ１＾４＊β＾４
である。β＾２＝ｆ（α）であるので、Ｍ＝３＊Ｘ１＾２＋ａ＊Ｚ１＾４＊ｆ（α）＾２  である。また、
ｘ３＝Ｔ
ｙ３＝−８＊Ｙ１＾４＋Ｍ＊（Ｓ−Ｔ）
ｚ３＝２＊Ｙ１＊Ｚ１＊β
である。
【０１１７】
Ｘ３＝ｘ３，Ｙ３＝ｙ３，Ｚ３＝ｚ３／β＝２＊Ｙ１＊Ｚ１であるので、本発明の２倍算公式が導き出せる。
１．７  楕円曲線条件判定部５０５
楕円曲線条件判定部５０５は、情報記憶部５０７から、素数ｐ及び位数ｍを読み出し、読み出した位数ｍが素数であり、かつ位数ｍ≠素数ｐであるか否かを判定する。次に、読み出した位数ｍが素数であり、かつ位数ｍ≠素数ｐであるか否かを示す安全性判定情報を制御部５０６へ出力する。
１．８  制御部５０６
制御部５０６は、入力部５０８から楕円曲線を構成する旨を示す構成指示と素数ｐを受け取る。
【０１１８】
制御部５０６は、前記構成指示を受け付けると、素数ｐを情報記憶部５０７へ書き込み、乱数生成部５０１に対して乱数生成の指示を出力する。
制御部５０６は、乱数生成部５０１、楕円曲線設定部５０２、楕円曲線有限性判定部５０３、楕円曲線位数計算部５０４、楕円曲線条件判定部５０５に対して、この順序で各構成部の処理を実行するように制御する。
【０１１９】
制御部５０６は、楕円曲線有限性判定部５０３から位数判定情報を受け取る。受け取った前記位数判定情報が、位数ｍ１とｍ２が互いに素であることを示す場合には、次に、楕円曲線位数計算部５０４に対してその処理を実行するように制御する。受け取った前記位数判定情報が、位数ｍ１とｍ２が互いに素でないことを示す場合には、次に、楕円曲線位数計算部５０４に対してその処理を中止し、乱数生成部５０１に対してその処理を実行するように制御する。
【０１２０】
制御部５０６は、楕円曲線位数計算部５０４から楕円曲線棄却情報を受け取る。制御部５０６は、楕円曲線棄却情報を受け取ると、楕円曲線条件判定部５０５に対してその処理を中止し、乱数生成部５０１に対してその処理を実行するように制御する。
制御部５０６は、楕円曲線条件判定部５０５から安全性判定情報を受け取る。受け取った安全性判定情報が、位数ｍが素数であり、かつ位数ｍ≠素数ｐであることを示す場合には、情報記憶部５０７からパラメタａ及びｂを読み出し、読み出したパラメタａ及びｂを出力部５０９へ出力する。受け取った安全性判定情報が、位数ｍが素数であり、かつ位数ｍ≠素数ｐであることを示さない場合には、再度、乱数生成部５０１に対してその処理を実行するように制御する。
１．９  出力部５０９
出力部５０９は、制御部５０６からパラメタａ及びｂを受け取り、受け取ったパラメタａ及びｂをパラメタ記憶部５１０へ書き込む。
１．１０  パラメタ記憶部５１０
パラメタ記憶部５１０は、具体的には、ハードディスク１４から構成され、パラメタａ及びｂを記憶する。
２  楕円曲線構成装置５００の動作
ここでは、楕円曲線構成装置５００の動作について説明する。
２．１  楕円曲線構成装置５００の全体の動作
楕円曲線構成装置５００の全体の動作について、図７に示すフローチャートを用いて説明する。
【０１２１】
入力部５０８は、利用者から構成指示と素数ｐの入力を受け付け、制御部５０６は、前記構成指示と素数ｐとを受け取る（ステップＳ１００）。
制御部５０６は、乱数生成部５０１に対して乱数生成の指示を出力し、乱数生成部５０１は、乱数ｔを生成し、生成した乱数ｔを情報記憶部５０７へ書き込む（ステップＳ１０１）。
【０１２２】
楕円曲線設定部５０２は、乱数ｔを読み出し、パラメタａ＝−３と設定し、パラメタｂ＝乱数ｔと設定する（ステップＳ１０２）。
楕円曲線有限性判定部５０３は、素数ｐ１、ｐ２を選択し、有理数体上の楕円曲線を素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２のそれぞれの位数ｍ１、ｍ２を計算、位数ｍ１とｍ２が互いに素であるか判定し（ステップＳ１０３）、制御部５０６は、位数ｍ１とｍ２が互いに素でない場合に（ステップＳ１０４）、ステップＳ１０１へ制御を戻す。
【０１２３】
制御部５０６は、位数ｍ１とｍ２が互いに素である場合に（ステップＳ１０４）、楕円曲線位数計算部５０４に対して位数計算をするように制御し、楕円曲線位数計算部５０４は位数計算をする（ステップＳ１０５）。
制御部５０６は、楕円曲線棄却情報を受け取った場合には（ステップＳ１０６）、ステップＳ１０１へ制御を戻す。
【０１２４】
制御部５０６が、楕円曲線棄却情報を受け取らない場合には（ステップＳ１０６）、
楕円曲線条件判定部５０５は、位数ｍが素数であり、かつ位数ｍ≠素数ｐであるか否かを判定し、「位数ｍが素数であり、かつ位数ｍ≠素数ｐ」である場合に（ステップＳ１０７）、制御部５０６は、出力部５０９に対してパラメタａ、ｂを出力するように制御し、出力部５０９はパラメタａ、ｂを出力する（ステップＳ１０８）。
【０１２５】
「位数ｍが素数であり、かつ位数ｍ≠素数ｐ」でない場合に（ステップＳ１０７）、制御部５０６は、ステップＳ１０１へ制御を戻す。
２．２  楕円曲線位数計算部５０４の動作
楕円曲線位数計算部５０４の動作について、図８に示すフローチャートを用いて説明する。
【０１２６】
楕円曲線Ｅの位数をｍとし、ｔを
ｍ＝ｐ＋１−ｔ
を満たすものとする。また、
ｆ（ｘ）＝ｘ＾３＋ａｘ＋ｂ
とする。
【０１２７】
楕円曲線位数計算部５０４は、初期値として、整数変数Ｌ＝２とする（ステップＳ９１０）。
楕円曲線位数計算部５０４は、Ｍｏｄｕｌａｒ多項式ΦＬ（Ｔ，ｊ（Ｅ））の一変数Ｔの多項式環ＧＦ（ｐ）［Ｔ］における因数分解の一次因子の数を算出する（ステップＳ９１１）。
【０１２８】
楕円曲線位数計算部５０４は、算出した一次因子の数が２のとき（ステップＳ９１２）、ｔ  ｍｏｄ  Ｌを求め（ステップＳ９１３）、Ｉｓｏｇｅｎｙ  ｃｙｃｌｅ法により、ｔ  ｍｏｄ  Ｌ＾ｎ（ｎ＝２、３、・・・）を求める（ステップＳ９１４）。
算出した一次因子の数が１またはＬ＋１のとき（ステップＳ９１２）、ｔ  ｍｏｄ  Ｌを求め（ステップＳ９１５）、Ｉｓｏｇｅｎｙ  ｃｙｃｌｅ法を適用可能であるか判定し、適用可能なら（ステップＳ９１６）、Ｉｓｏｇｅｎｙ  ｃｙｃｌｅ法により、ｔ  ｍｏｄ  Ｌ＾ｎ（ｎ＝２，３，．．．）を求める（ステップＳ９１７）。
【０１２９】
算出した一次因子の数が０のとき（ステップＳ９１２）、ｔ  ｍｏｄ  Ｌの取り得る値を集合［０、１、・・・、Ｌ−１］から絞り込む（ステップＳ９１８）。
次に、楕円曲線位数計算部５０４は、
Ｌ１＾（ｎ１）×Ｌ２＾（ｎ２）×・・・×Ｌｋ＾（ｎｋ）
＜  ４×ｐ＾（１／２）
（ここで、Ｌ１、Ｌ２、・・・、Ｌｋは素数であり、Ｌｋ＝Ｌ）
であるとき（ステップＳ９１９）、Ｌ＝（Ｌの次に大きい素数）とし（ステップＳ９２１）、ステップＳ９１１に戻る。
【０１３０】
そうでないとき（ステップＳ９１９）、楕円曲線位数計算部５０４は、ｍａｔｃｈ＆ｓｏｒｔアルゴリズムにより、位数ｍを確定し、位数ｍを情報記憶部５０７へ書き込む（ステップＳ９２０）。
２．３  楕円曲線位数計算部５０４のｔ  ｍｏｄ  Ｌ＾ｎの算出の動作
楕円曲線位数計算部５０４のｔ  ｍｏｄ  Ｌ＾ｎの算出の動作について図９に示すフローチャートを用いて説明する。
【０１３１】
Ｃａｓｅ１では、まず、楕円曲線位数計算部５０４は、ｎ＝２とし（ステップＳ１３１）、ｋ ｍｏｄ Ｌとｈ（α）を基に多項式Ｈ（α）を求め（ステップＳ１３２）、それを改めて、ｈ（α）とする（ステップＳ１３３）。その多項式ｈ（α）を用いて、ｋ ｍｏｄ Ｌ＾ｎを求める（ステップＳ１３４）。次に、多項式ｈ（α）の次数により、次に進むか否かを判定する。ｈ（α）の次数をｄｅｇ（ｈ（α））とする。そのとき、
（ｄｅｇ（ｈ）＾２）＊Ｌ＾２＊（Ｌ＾（２＊ｎ））
＞ （｜ｐ｜）＾３／１３５ であるか否かを判断する。ここで、｜ｐ｜はｐのビット数である。前記判断式が真であれば（ステップＳ１３５）、
ｔ＝（ｋ＾２＋ｐ）／ｋ ｍｏｄ Ｌ＾ｎ
として（ステップＳ１３７）、Ｉｓｏｇｅｎｙ ｃｙｃｌｅを終了する。偽であれば（ステップＳ１３５）、ｎに１を加算して（ステップＳ１３６）、前記不等式を満たすまで、前記処理を繰り返す。
【０１３２】
こうして、楕円曲線位数計算部５０４は、ｔ ｍｏｄ Ｌ＾ｎを求める。
なお、Ｃａｓｅ２の場合も、楕円曲線位数計算部５０４は、Ｃａｓｅ１と同様に行うが、必ずしもＩｓｏｇｅｎｙ  ｃｙｃｌｅが行えるとは限らない。したがって、楕円曲線位数計算部５０４は、Ｉｓｏｇｅｎｙ  ｃｙｃｌｅを行えるか否かの判定を行う。
２．４  楕円曲線位数計算部５０４による楕円曲線上の点の２倍算又は加算の動作
楕円曲線位数計算部５０４は、楕円曲線の冪倍点ｋＰの演算を行う場合、冪倍点ｋＰの演算を、楕円曲線上の点の２倍算又は加算に分解し、分解された２倍算又は加算を行うときに、以下に示す手順による。このとき、２倍算又は加算の種類と、２倍算又は加算の対象となる１個又は２個の楕円曲線上の点のアフィン座標とを以下の手順に対して出力し、下記手順を実施する。分解された２倍算又は加算について、下記手順を繰り返し実施することにより、楕円曲線の冪倍点ｋＰの演算が行われる。
【０１３３】
楕円曲線位数計算部５０４による楕円曲線上の点の２倍算又は加算の動作について、図１０に示すフローチャートを用いて説明する。
楕円曲線位数計算部５０４は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行う。
【０１３４】
楕円曲線位数計算部５０４は、２倍算の演算対象となる楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、加算の演算対象となる楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを受け取る。ここで、楕円曲線Ｅ上の２個の異なる点のアフィン座標は、
（Ｘ１（α）、β×Ｙ１（α））及び
（Ｘ２（α）、β×Ｙ２（α））であり、
楕円曲線Ｅ上の１個の点のアフィン座標は、
（Ｘ１（α）、β×Ｙ１（α））である（ステップＳ１２１）。
【０１３５】
次に、楕円曲線位数計算部５０４は、受け取った１個又は２個のアフィン座標に対して、座標変換を施して、それぞれ１個又は２個の射影座標を生成する。前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、
多項式Ｘ（α）＝ｆ（α）×φ（α）、
多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び
多項式Ｚ（α）＝１により変換して
射影座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成する。ここで、生成された２個の射影座標は、
（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び
（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））であり、
生成された１個の射影座標は、
（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））である（ステップＳ１２２）。
【０１３６】
次に、楕円曲線位数計算部５０４は、演算情報が加算であるか２倍算であるかを判定し、加算である場合に（ステップＳ１２３）、
演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、
演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、
演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、
演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、
演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び
演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い（ステップＳ１２４）、
次に、
演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、
演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び
演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行う（ステップＳ１２５）。
【０１３７】
楕円曲線位数計算部５０４は、２倍算である場合に（ステップＳ１２３）、
演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、
演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び
演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い（ステップＳ１２６）、次に、
演算Ｘ３（α）＝Ｔ（α）、
演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び
演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行う（ステップＳ１２７）。
【０１３８】
次に、楕円曲線位数計算部５０４は、射影座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出して出力する（ステップＳ１２８）。
３  まとめ
楕円曲線設定部は、あらかじめ安全性の高い楕円曲線を選択する確率が高いので、楕円曲線を選択しその安全性を判定するステップを何度も繰り返すことがなく、楕円曲線構成装置における計算量が減少する。
【０１３９】
また、楕円曲線有限性判定部により、位数計算を行う前に、楕円曲線が有限位数を有する点を持つか否かを判定することにより、前記楕円曲線の安全性が高いか否かを判定するので、位数計算を行うことなく、安全性の低い楕円曲線を棄却することができ、無駄な位数計算を省略して、楕円曲線構成装置における計算量が減少する。
【０１４０】
また、楕円曲線位数計算部における楕円曲線の冪倍点ｋＰの演算は、加算に比べ、２倍算の繰り返し回数が多い。一般に、ｋＰの計算量は、楕円曲線の加算演算の計算量をＥＡ、２倍算演算の計算量をＥＤとすると
｜ｋ｜×（ＥＤ＋ＥＡ／３）
で与えられる。ここで、｜ｋ｜はｋのビット数である。なお、これはＳｉｇｎｅｄ  Ｂｉｎａｒｙ  ｍｅｔｈｏｄという計算法を用いた場合である。この計算法を用いると、従来例３によるｋＰの計算量は１７×ＰＭｕｌ×｜ｋ｜であり、本発明によるｋＰの計算量は１５．３×ＰＭｕｌ×｜ｋ｜である。したがって、本発明によるｋＰの計算量の減少の効果は大きい。
４  その他の変形例
以上、本発明に係る楕円曲線構成装置について、実施の形態に基づいて説明したが、本発明はこれらの実施の形態に限られないことは勿論である。次のように構成してもよい。
（１）本発明は、上記に説明した楕円曲線構成装置を備える楕円曲線応用装置であるとしてもよい。楕円曲線応用装置の具体的な例は、暗号化装置及び暗号解読装置からなる暗号通信システム、デジタル署名装置及び署名検証装置からなるデジタル署名システム、誤り訂正符号送信装置及び誤り訂正装置誤りからなる訂正通信システムである。
【０１４１】
前記暗号通信システムは、楕円曲線を利用して、特定の通信相手以外に通信内容を漏らすことなく通信を行なう。前記デジタル署名システムは、楕円曲線を利用して、通信相手に通信内容の正当性を示したり、本人であることを証明する。前記誤り訂正通信システムは、楕円曲線を利用して、通信回線上で欠落した情報、変化した情報を回復して、元の情報を生成する。
（２）楕円曲線設定部５０２は、楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂにおけるパラメタａ、ｂについて、ａ＝−３と設定し、ｂ＝ｔと設定しているが、次のようにしてもよい。
【０１４２】
楕円曲線設定部５０２は、有理数体上の曲線Ｅ：ｙ＾２＝ｘ＾３＋ａｘ＋ｂ（ａ、ｂは整数）に対して、前述の判別式ＴＤを定義し、判別式ＴＤが平方因子を持つ確率が所定のしきい値より小さくなるように、パラメタａ、ｂを選択する。ここで、一例として、前記所定のしきい値は、０．００１である。この場合に、上記の実施の形態で説明したように、楕円曲線の安全性が高くなると期待できる。
（３）本発明は、楕円曲線位数計算部５０４に示す多項式剰余環上で定義された楕円曲線上の点の演算を行う楕円曲線演算装置であるとしてもよい。
（４）本発明は、楕円曲線位数計算部５０４に示す楕円曲線の位数を計算する楕円曲線位数計算装置であるとしてもよい。
（５）本発明は、本実施の形態に示す楕円曲線演算方法、楕円曲線位数計算方法及び楕円曲線構成方法であるとしてもよい。
【０１４３】
また、これらの楕円曲線演算方法、楕円曲線位数計算方法及び楕円曲線構成方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フロッピーディスク、ハードディスク、ＣＤ―ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、半導体メモリなど、に記録したものとしてもよい。また、これらの記録媒体に記録されている前記コンピュータプログラム又は前記デジタル信号であるとしてもよい。
【０１４４】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号を、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク等を経由して伝送するものとしてもよい。
（６）本発明は、上記に示す実施の形態、複数の変形例、又は上記実施の形態及び複数の変形例の一部を組み合わせるとしてもよい。
【０１４５】
【発明の効果】
上記に説明したように、本発明は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行う楕円曲線演算装置であって、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得手段と、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換手段とを備え、前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、多項式Ｘ（α）＝ｆ（α）×φ（α）、多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び多項式Ｚ（α）＝１により変換してＪａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算手段を備える。
【０１４６】
ここで、前記取得手段は、楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを取得し、前記変換手段は、取得した１個又は２個のアフィン座標に対して、前記座標変換を施して、それぞれ１個又は２個のＪａｃｏｂｉａｎ座標を生成し、前記演算手段は、前記生成された１個又は２個のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される２倍算又は加算をそれぞれ施すように構成してもよい。
【０１４７】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は加算であり、前記取得手段は、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、前記変換手段は、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、前記演算手段は、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１４８】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は２倍算であり、前記取得手段は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換手段は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算手段は、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１４９】
ここで、前記取得手段は、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、又は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換手段は、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、又は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算手段は、取得した前記演算情報が加算を示す場合には、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出し、取得した前記演算情報が２倍算を示す場合には、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１５０】
これらの構成によると、従来例と比較して、加算公式の多項式乗算の計算量は、１ＰＭｕｌ増加し、２倍算公式の計算量は、２ＰＭｕｌ減少する。通常、２倍算の演算回数は、加算の演算回数より多いので、２倍算の計算量の減少は、全体の計算量の減少に大きく貢献し、楕円曲線演算装置における計算量が減少するという効果がある。
【０１５１】
また、本発明は、ＳＥＡアルゴリズムにより楕円曲線の位数計算を行う楕円曲線位数計算装置であって、前記楕円曲線位数計算装置は、上記の楕円曲線演算装置を含む。
ここで、前記楕円曲線位数計算装置は、上記の楕円曲線演算装置を含むように構成してもよい。
【０１５２】
ここで、前記楕円曲線位数計算装置は、上記の楕円曲線演算装置を含むように構成してもよい。
これらの構成によると、従来例と比較して、加算公式の多項式乗算の計算量は、１ＰＭｕｌ増加し、２倍算公式の計算量は、２ＰＭｕｌ減少する。通常、２倍算の演算回数は、加算の演算回数より多いので、２倍算の計算量の減少は、全体の計算量の減少に大きく貢献し、楕円曲線位数計算装置における計算量が減少するという効果がある。
【０１５３】
また、本発明は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定する楕円曲線構成装置であって、乱数を生成する乱数生成手段と、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成手段と、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定手段と、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算手段と、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定手段と、前記安全性判定手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成手段、前記パラメタ生成手段、前記有限性判定手段、前記位数計算手段及び前記安全性判定手段に対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように制御する繰返制御手段と、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力手段とを備える。
【０１５４】
この構成によると、パラメタ生成手段により、あらかじめ安全性の高い楕円曲線が選択される確率が高いので、楕円曲線を選択しその安全性を判定するステップを何度も繰り返すことがなく、楕円曲線構成装置における計算量が減少するという効果がある。
また、有限性判定手段により、位数計算を行う前に、楕円曲線が有限位数を有する点を持つか否かを判定することにより、前記楕円曲線の安全性が高いか否かを判定するので、位数計算を行うことなく、安全性の低い楕円曲線を棄却することができ、無駄な位数計算を省略し、楕円曲線構成装置における計算量が減少するという効果がある。
【０１５５】
ここで、前記楕円曲線Ｅは、ｙ＾２＝ｘ＾３＋ａｘ＋ｂにより示され、ここで、パラメタａ及びパラメタｂは定数であり、前記パラメタ生成手段は、パラメタａ＝−３とし、パラメタｂを前記生成された乱数として選択することにより、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、パラメタを選択するように構成してもよい。
【０１５６】
この構成によると、パラメタ生成手段は、あらかじめ安全性の高い楕円曲線として、楕円曲線Ｅ：ｙ＾２＝ｘ＾３−３ｘ＋ｂを選択するので、楕円曲線を選択しその安全性を判定するステップを何度も繰り返すことがなく、楕円曲線構成装置における計算量が減少するという効果がある。
ここで、前記有限性判定手段は、楕円曲線Ｅを有理数体上の楕円曲線ＥＱとみなし、２個の素数ｐ１、ｐ２をあらかじめ有し、ｐ１≠ｐ２であり、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出し、算出された位数ｍ１、ｍ２が互いに素であることを判定し、互いに素であると判定する場合に、楕円曲線Ｅが有理数体上において有限位数の点を持たないと判定するように構成してもよい。
【０１５７】
この構成によると、有限性判定手段により、位数計算を行う前に、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２が互いに素であることを判定することにより、前記楕円曲線の安全性が高いか否かを判定するので、位数計算を行うことなく、安全性の低い楕円曲線を棄却することができるので、無駄な位数計算を省略することができ、楕円曲線構成装置における計算量が減少するという効果がある。
【０１５８】
ここで、前記有限性判定手段は、素数ｐ１＝５及び素数ｐ２＝７をあらかじめ有し、２個の素数ｐ１＝５、ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出するように構成してもよい。
この構成によると、有限性判定手段は、素数ｐ１＝５及び素数ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２が互いに素であることを判定するので、判定に要する計算量を最も少なくすることができるという効果がある。
【０１５９】
ここで、前記位数計算手段は、ＳＥＡアルゴリズムにより楕円曲線の位数計算を行い、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の点に対して２倍算又は加算を施す楕円曲線演算手段を含み、前記楕円曲線演算手段は、上記の楕円曲線演算装置を含むように構成してもよい。
【０１６０】
これらの構成によると、従来例と比較して、加算公式の多項式乗算の計算量は、１ＰＭｕｌ増加し、２倍算公式の計算量は、２ＰＭｕｌ減少する。通常、２倍算の演算回数は、加算の演算回数より多いので、２倍算の計算量の減少は、全体の計算量の減少に大きく貢献し、楕円曲線構成装置における計算量が減少するという効果がある。
【０１６１】
また、本発明は、楕円曲線を用いて処理を行う楕円曲線応用装置であって、前記楕円曲線応用装置は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定する楕円曲線構成手段を含み、前記楕円曲線構成手段は、上記の楕円曲線構成装置を備えるように構成してもよい。
【０１６２】
この構成によると、楕円曲線応用装置は、前記楕円曲線構成装置と同様の効果を奏する。こうして、高速に安全な暗号方式や署名方式を可能にする楕円曲線応用装置を提供することができ，その実用的価値は大きい。
また、本発明は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行い、取得手段と変換手段と演算手段とを備える装置で用いられる楕円曲線演算方法であって、前記取得手段により、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得ステップと、前記変換手段により、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換ステップとを含み、前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、多項式Ｘ（α）＝ｆ（α）×φ（α）、多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び多項式Ｚ（α）＝１により変換してＪａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記演算手段により、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算ステップを含む。
【０１６３】
この方法を用いると、前記楕円曲線演算装置と同様の効果を奏する。
また、本発明は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定し、乱数生成手段とパラメタ生成手段と有限性判定手段と位数計算手段と安全性判定手段と繰返制御手段とパラメタ出力手段とを備える楕円曲線構成装置で用いられる楕円曲線構成方法であって、前記乱数生成手段により、乱数を生成する乱数生成ステップと、前記パラメタ生成手段により、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成ステップと、前記有限性判定手段により、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定ステップと、前記位数計算手段により、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算ステップと、前記安全性判定手段により、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定ステップと、前記安全性判定ステップにより、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成ステップ、前記パラメタ生成ステップ、前記有限性判定ステップ、前記位数計算ステップ及び前記安全性判定ステップに対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように、前記繰返制御手段により、制御する繰返制御ステップと、前記パラメタ出力手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力ステップとを含む。
【０１６４】
この方法を用いると、前記楕円曲線構成装置と同様の効果を奏する。
また、本発明は、多項式β＾２−ｆ（α）（ここで、ｆ（α）＝α＾３＋ａα＋ｂであり、ａ及びｂは定数である）と多項式ｈ（α）（ここで、ｈ（α）は、αに関する多項式である）とを法とする変数α、βに関する２変数多項式剰余環上の楕円曲線Ｅ：ｙ＾２＝ｆ（ｘ）上の２倍算又は加算を行い、取得手段と変換手段と演算手段とを備える楕円曲線演算装置で用いられる楕円曲線演算プログラムを記録しているコンピュータ読み取り可能な記録媒体であって、前記プログラムは、前記取得手段により、外部から楕円曲線Ｅ上の１個以上の点のアフィン座標と、２倍算又は加算の種類を示す演算情報とを取得する取得ステップと  前記変換手段により、取得した１個以上のアフィン座標に対して、次に示す座標変換を施して、１個以上のＪａｃｏｂｉａｎ座標を生成する変換ステップとを含み、前記座標変換は、楕円曲線Ｅ上の点のアフィン座標（φ（α）、β×ψ（α））（ここで、φ（α）及びψ（α）は多項式である）を、多項式Ｘ（α）＝ｆ（α）×φ（α）、多項式Ｙ（α）＝ｆ（α）＾２×ψ（α）及び多項式Ｚ（α）＝１により変換してＪａｃｏｂｉａｎ座標（Ｘ（α）：Ｙ（α）：β×Ｚ（α））を生成し、さらに、前記Ｊａｃｏｂｉａｎ座標上における２倍算及び加算を有し、前記演算手段により、前記生成された１個以上のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される前記２倍算又は前記加算を施して楕円曲線Ｅ上の１個のＪａｃｏｂｉａｎ座標を算出する演算ステップを含む。
【０１６５】
ここで、前記取得ステップは、楕円曲線Ｅ上の１個の点のアフィン座標と２倍算を示す演算情報とを取得し、又は、楕円曲線Ｅ上の２個の異なる点のアフィン座標と、加算を示す演算情報とを取得し、前記変換ステップは、取得した１個又は２個のアフィン座標に対して、前記座標変換を施して、それぞれ１個又は２個のＪａｃｏｂｉａｎ座標を生成し、前記演算ステップは、前記生成された１個又は２個のＪａｃｏｂｉａｎ座標に対して、取得した前記演算情報により示される２倍算又は加算をそれぞれ施すように構成してもよい。
【０１６６】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は加算であり、前記取得ステップは、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、前記変換ステップは、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、前記演算ステップは、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１６７】
ここで、前記楕円曲線演算装置が楕円曲線Ｅ上の点に対して施す演算は２倍算であり、前記取得ステップは、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換ステップは、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算ステップは、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１６８】
ここで、前記取得ステップは、楕円曲線Ｅ上の２個の異なる点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））並びに加算を示す演算情報を取得し、又は、楕円曲線Ｅ上の１個の点のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び２倍算を示す演算情報を取得し、前記変換ステップは、前記２個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））及び（Ｘ２（α）、β×Ｙ２（α））に対して、前記座標変換を施して、２個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））及び（Ｘ２（α）：Ｙ２（α）：β×Ｚ２（α））を生成し、又は、前記１個のアフィン座標（Ｘ１（α）、β×Ｙ１（α））に対して、前記座標変換を施して、１個のＪａｃｏｂｉａｎ座標（Ｘ１（α）：Ｙ１（α）：β×Ｚ１（α））を生成し、前記演算ステップは、取得した前記演算情報が加算を示す場合には、演算Ｕ１（α）＝Ｘ１（α）×Ｚ２（α）＾２、演算Ｕ２（α）＝Ｘ２（α）×Ｚ１（α）＾２、演算Ｓ１（α）＝Ｙ１（α）×Ｚ２（α）＾３、演算Ｓ２（α）＝Ｙ２（α）×Ｚ１（α）＾３、演算Ｈ（α）＝Ｕ２（α）−Ｕ１（α）及び演算ｒ（α）＝Ｓ２（α）−Ｓ１（α）を行い、次に、演算Ｘ３（α）＝−Ｈ（α）＾３−２×Ｕ１（α）×Ｈ（α）＾２＋ｒ（α）＾２、演算Ｙ３（α）＝−Ｓ１（α）×Ｈ（α）＾３＋ｒ（α）×（Ｕ１（α）×Ｈ（α）＾２−Ｘ３（α））及び演算Ｚ３（α）＝Ｚ１（α）×Ｚ２（α）×Ｈ（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出し、取得した前記演算情報が２倍算を示す場合には、演算Ｓ（α）＝４×Ｘ１（α）×Ｙ１（α）＾２、演算Ｍ（α）＝３×Ｘ１（α）＾２＋ａ×Ｚ１（α）＾４×ｆ（α）＾２及び演算Ｔ（α）＝−２×Ｓ（α）＋Ｍ（α）＾２を行い、次に、演算Ｘ３（α）＝Ｔ（α）、演算Ｙ３（α）＝−８×Ｙ１（α）＾４＋Ｍ（α）×（Ｓ（α）−Ｔ（α））及び演算Ｚ３（α）＝２×Ｙ１（α）×Ｚ１（α）を行い、次に、Ｊａｃｏｂｉａｎ座標（Ｘ３（α）：Ｙ３（α）：β×Ｚ３（α））を算出するように構成してもよい。
【０１６９】
このプログラムをコンピュータにより実行することにより、前記楕円曲線演算装置と同様の効果を奏する。
また、本発明は、ｐは素数であり、有限体ＧＦ（ｐ）上において定義され、高い安全性を有する楕円曲線Ｅのパラメタを決定し、乱数生成手段とパラメタ生成手段と有限性判定手段と位数計算手段と安全性判定手段と繰返制御手段とパラメタ出力手段とを備えている楕円曲線構成装置で用いられる楕円曲線構成プログラムを記録しているコンピュータ読み取り可能な記録媒体あって、前記プログラムは、前記乱数生成手段により、乱数を生成する乱数生成ステップと、前記パラメタ生成手段により、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるように、前記乱数を含む楕円曲線Ｅのパラメタを選択するパラメタ生成ステップと、前記有限性判定手段により、前記選択されたパラメタにより特定される楕円曲線Ｅが有理数体上において有限位数を有する点を持つか否かを判定する有限性判定ステップと、前記位数計算手段により、前記楕円曲線Ｅが有限位数を有する点を持たないと判定された場合に、前記楕円曲線Ｅの位数ｍを計算する位数計算ステップと前記安全性判定手段により、前記位数ｍが計算された場合に、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであるという条件を満たすか否かを判定する安全性判定ステップと、前記安全性判定ステップにより、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定されるまで、前記乱数生成ステップ、前記パラメタ生成ステップ、前記有限性判定ステップ、前記位数計算ステップ及び前記安全性判定ステップに対して、それぞれ、乱数生成、パラメタ生成、有限性判定、位数計算及び安全性判定をするように、前記繰返制御手段により、制御する繰返制御ステップと、前記パラメタ出力手段により、前記位数ｍが素数であり、かつ、前記位数ｍ≠素数ｐであると判定された場合に、前記選択されたパラメタを出力するパラメタ出力ステップとを含む。
【０１７０】
ここで、前記楕円曲線Ｅは、ｙ＾２＝ｘ＾３＋ａｘ＋ｂにより示され、ここで、パラメタａ及びパラメタｂは定数であり、前記パラメタ生成ステップは、パラメタａ＝−３とし、パラメタｂを前記生成された乱数として選択することにより、楕円曲線Ｅの判別式が平方因子を持つ確率が所定のしきい値より小さくなるようにパラメタを選択するように構成してもよい。
【０１７１】
ここで、前記有限性判定ステップは、楕円曲線Ｅを有理数体上の楕円曲線ＥＱとみなし、２個の素数ｐ１、ｐ２をあらかじめ有し、ｐ１≠ｐ２であり、２個の素数ｐ１、ｐ２を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出し、算出された位数ｍ１、ｍ２が互いに素であることを判定し、互いに素であると判定する場合に、楕円曲線Ｅが有理数体上において有限位数の点を持たないと判定するように構成してもよい。
【０１７２】
ここで、前記有限性判定ステップは、素数ｐ１＝５及び素数ｐ２＝７をあらかじめ有し、２個の素数ｐ１＝５、ｐ２＝７を法として還元した楕円曲線Ｅｐ１、Ｅｐ２の位数ｍ１、ｍ２をそれぞれ算出するように構成してもよい。
このプログラムをコンピュータにより実行することにより、前記楕円曲線構成装置と同様の効果を奏する。
【図面の簡単な説明】
【図１】従来の楕円曲線の構成方法を示すフローチャートである。
【図２】従来のＬｅｒｃｉｅｒによる楕円曲線の構成方法を示すフローチャートである。図３へ続く。
【図３】従来のＬｅｒｃｉｅｒによる楕円曲線の構成方法を示すフローチャートである。図２から続く。
【図４】本発明に係る１の実施の形態としての楕円曲線構成装置５００の構成を示すブロック図である。
【図５】楕円曲線構成装置５００の具体的な構成を示すブロック図である。
【図６】楕円曲線構成装置５００の情報記憶部５０７に記憶されているデータの一例を示す。
【図７】楕円曲線構成装置５００の楕円曲線の構成の手順を示すフローチャートである。
【図８】楕円曲線構成装置５００の楕円曲線位数計算部５０４による楕円曲線の位数計算の手順を示すフローチャートである。
【図９】楕円曲線構成装置５００の楕円曲線位数計算部５０４によるｔ  ｍｏｄ  Ｌ＾ｎの算出の手順を示すフローチャートである。
【図１０】楕円曲線構成装置５００の楕円曲線上の点の加算又は２倍算の手順を示すフローチャートである。
【符号の説明】
５００  楕円曲線構成装置
５０１  乱数生成部
５０２  楕円曲線設定部
５０３  楕円曲線有限性判定部
５０４  楕円曲線位数計算部
５０５  楕円曲線条件判定部
５０６  制御部
５０７  情報記憶部
５０８  入力部
５０９  出力部
５１０  パラメタ記憶部５１０
【図１】
0004510201.tif 000014
【図２】
0004510201.tif 000015
【図３】
0004510201.tif 000016
【図４】
0004510201.tif 000017
【図５】
0004510201.tif 000018
【図６】
0004510201.tif 000019
【図７】
0004510201.tif 000020
【図８】
0004510201.tif 000021
【図９】
0004510201.tif 000022
【図１０】
0004510201.tif 000023