(57)【要約】【課題】暗号計算などに利用される楕円積和演算の高速化を実現する。【解決手段】楕円曲線上の相異なる３点Ｐ，Ｑ，Ｒの積和演算Ｔ＝ａＰ＋ｂＱ＋ｃＲを求める場合、整数ａ，ｂ，ｃを2004233530.tif 000022のように２進数表現し（ｉ≧０の場合、ａｉ，ｂｉ，ｃｉ∈｛０，１｝，ａ−１＝ｂ−１，＝ｃ−１，＝０）、最初、Ｔ＝０とした後、ｉ＝ｋ，ｋ−１，…，１，０の順番に、順次、Ａ２ｉ＋１＝４ａ２ｉ＋１＋２ａ２ｉ＋ａ２ｉ−１，Ｂ２ｉ＋１＝４ｂ２ｉ＋１＋２ｂ２ｉ＋ｂ２ｉ−１，Ｃ２ｉ＋１＝４ｃ２ｉ＋１＋２ｃ２ｉ＋ｃ２ｉ−１を選択し、その値に応じて、楕円演算の種類と演算順序を場合分けし、ｉ＝０のときの演算結果Ｔを求める解とする。【選択図】        図１１
2004233530.tif 000002
【特許請求の範囲】
【請求項１】
ｐを素数とする素体Ｆｐとし、
Ｅｐ：ｙ２≡ｘ３＋αｘ＋β（ｍｏｄ  ｐ），α，β∈Ｆｐ，４α３＋２７β２≠０
で定義される素体Ｆｐ上の楕円曲線Ｅｐ上の相異なるｎ個（ｎ≧３）の点をＰ１〜Ｐｎとし、互いに独立なｎ組の整数ｍｉ（ｉ＝１，２，・・・，ｎ）とした場合、
ｎ組の整数ｍｉを
【数１】
2004233530.tif 000013
のように２進数表現して、任意のｉ（１≦ｉ≦ｎ）に対して
ｍｉ２ｋ＋１＋ｍｉ２ｋ＋ｍｉ２ｋ−１≠０なるような最大のｋを定義して、
楕円積和演算計算
【数２】
2004233530.tif 000014
を、制御回路、記憶回路及び演算回路を含むコンピュータにより自動的に計算する方法において、
Ｍｉ２ｊ＋１＝４ｍｉ２ｊ＋１＋２ｍｉ２ｊ＋ｍｉ２ｊ−１（ｊ≧０）として、ｕｉとｖｉを
【数３】
2004233530.tif 000015
【数４】
2004233530.tif 000016
のように定義し、
ｊ＝ｋにおいて、
【数５】
2004233530.tif 000017
引続き、
【数６】
2004233530.tif 000018
を実行し、更に前記式（４）と（５）の演算をｊ＝ｋ−１，ｋ−２，…，０の順番で繰り返し、実行することで、前記式（１）を計算する楕円積和演算方法であって、
制御回路は、パラメータＰ１〜Ｐｎ、演算結果Ｔの初期値としてＴ＝０を記憶回路に格納し、ｎ組の整数ｍ１〜ｍｎから、ｊ＝ｋ，ｋ−１，ｋ−２，１…，０の順番に、順次、２ビットずつシフトして、（Ｍ１２ｊ＋１，Ｍ２２ｊ＋１，…，Ｍｎ２ｊ＋１）を選択し、該選択した（Ｍ１２ｊ＋１，Ｍ２２ｊ＋１，…，Ｍｎ２ｊ＋１）の値に応じて、前記式（２），（３）で定まる前記式（４），（５）の演算パターンを演算回路に指示し、
演算回路は、前記制御回路からの指示にもとづき、記憶回路からＰ１〜Ｐｎ、Ｔを読み出して、前記指示された演算パターンの演算を実行し、演算結果のＴを記憶回路に戻す、
ことを特徴とする楕円積和演算計算方法。
【請求項２】
ｐを素数とする素体Ｆｐとし、
Ｅｐ：ｙ２≡ｘ３＋αｘ＋β（ｍｏｄ  ｐ），α，β∈Ｆｐ，４α３＋２７β２≠０
で定義される素体Ｆｐ上の楕円曲線Ｅｐ上の相異なる３点をＰ，Ｑ，Ｒとし、互いに独立な３組の整数ａ，ｂ，ｃを、
【数７】
2004233530.tif 000019
のように２進数表現し（ｉ≧０の場合、ａｉ，ｂｉ，ｃｉ∈｛０，１｝，ａ−１＝ｂ−１＝ｃ−１＝０）、
ａ２ｋ＋１＋ａ２ｋ＋ａ２ｋ−１≠０，ｂ２ｋ＋１＋ｂ２ｋ＋ｂ２ｋ−１≠０，
ｃ２ｋ＋１＋ｃ２ｋ＋ｃ２ｋ−１≠０
となるような最大のｋを定義して、楕円積和演算計算
Ｔ＝ａＰ＋ｂＱ＋ｃＲ
を、制御回路、記憶回路及び演算回路を含むコンピュータにより自動的に計算する方法であって、
制御回路は、パラメータＰ，Ｑ，Ｒ、及び、演算結果Ｔの初期値としてＴ＝０を記憶回路に格納し、３組の整数ａ，ｂ，ｃから、ｉ＝ｋ，ｋ−１，…，２，１，０の順番に、順次、２ビットずつシフトして、
Ａ２ｉ＋１＝４ａ２ｉ＋１＋２ａ２ｉ＋ａ２ｉ−１、Ｂ２ｉ＋１＝４ｂ２ｉ＋１＋２ｂ２ｉ＋ｂ２ｉ−１、Ｃ２ｉ＋１＝４ｃ２ｉ＋１＋２ｃ２ｉ＋ｃ２ｉ−１を選択し、前記選択したＡ２ｉ＋１、Ｂ２ｉ＋１、Ｃ２ｉ＋１の値が、
（１）  （０，７）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔの順に実行される演算、
（２）  （０，７）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（３）  （０，７）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔの順に実行される演算、
（４）  （０，７）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔの順に実行される演算、
（５）  （０，７）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（６）  （０，７）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（７）  （０，７）、（１，２）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（８）  （０，７）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（９）  （０，７）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（１０）  （０，７）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（１１）  （０，７）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔの順に実行される演算、
（１２）  （０，７）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（１３）  （０，７）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１４）  （０，７）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１５）  （０，７）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（１６）  （０，７）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔの順に実行される演算、
（１７）  （０，７）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（１８）  （０，７）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１９）  （０，７）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（２０）  （０，７）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（２１）  （０，７）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２２）  （０，７）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（２３）  （０，７）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２４）  （０，７）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２５）  （０，７）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（２６）  （１，２）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（２７）  （１，２）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（２８）  （１，２）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（２９）  （１，２）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３０）  （１，２）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（３１）  （１，２）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３２）  （１，２）、（１，２）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ＋Ｒ）の順に実行される演算、
（３３）  （１，２）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３４）  （１，２）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３５）  （１，２）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ−Ｒ）の順に実行される演算、
（３６）  （１，２）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３７）  （１，２）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（３８）  （１，２）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３９）  （１，２）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４０）  （１，２）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（４１）  （１，２）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４２）  （１，２）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（４３）  （１，２）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４４）  （１，２）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４５）  （１，２）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（４６）  （１，２）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（４７）  （１，２）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ＋Ｒ）の順に実行される演算、
（４８）  （１，２）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（４９）  （１，２）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（５０）  （１，２）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ−Ｒ）の順に実行される演算、
（５１）  （３）、（０，７）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔの順に実行される演算、
（５２）  （３）、（０，７）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（５３）  （３）、（０，７）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（５４）  （３）、（０，７）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（５５）  （３）、（０，７）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（５６）  （３）、（１，２）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（５７）  （３）、（１，２）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（５８）  （３）、（１，２）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（５９）  （３）、（１，２）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（６０）  （３）、（１，２）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（６１）  （３）、（３）、（０，７）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔの順に実行される演算、
（６２）  （３）、（３）、（１，２）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（６３）  （３）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６４）  （３）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６５）  （３）、（３）、（５，６）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（６６）  （３）、（４）、（０，７）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔの順に実行される演算、
（６７）  （３）、（４）、（１，２）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（６８）  （３）、（４）、（３）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６９）  （３）、（４）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（７０）  （３）、（４）、（５，６）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（７１）  （３）、（５，６）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７２）  （３）、（５，６）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（７３）  （３）、（５，６）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７４）  （３）、（５，６）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７５）  （３）、（５，６）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（７６）  （４）、（０，７）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔの順に実行される演算、
（７７）  （４）、（０，７）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（７８）  （４）、（０，７）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（７９）  （４）、（０，７）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（８０）  （４）、（０，７）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（８１）  （４）、（１，２）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８２）  （４）、（１，２）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（８３）  （４）、（１，２）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８４）  （４）、（１，２）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８５）  （４）、（１，２）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（８６）  （４）、（３）、（０，７）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔの順に実行される演算、
（８７）  （４）、（３）、（１，２）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（８８）  （４）、（３）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（８９）  （４）、（３）、（４）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９０）  （４）、（３）、（５，６）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（９１）  （４）、（４）、（０，７）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔの順に実行される演算、
（９２）  （４）、（４）、（１，２）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（９３）  （４）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９４）  （４）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９５）  （４）、（４）、（５，６）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（９６）  （４）、（５，６）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（９７）  （４）、（５，６）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（９８）  （４）、（５，６）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（９９）  （４）、（５，６）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（１００）  （４）、（５，６）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（１０１）  （５，６）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０２）  （５，６）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１０３）  （５，６）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０４）  （５，６）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０５）  （５，６）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１０６）  （５，６）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１０７）  （５，６）、（１，２）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ−Ｒ）の順に実行される演算、
（１０８）  （５，６）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１０９）  （５，６）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１１０）  （５，６）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ＋Ｒ）の順に実行される演算、
（１１１）  （５，６）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１２）  （５，６）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１１３）  （５，６）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１４）  （５，６）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１５）  （５，６）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１１６）  （５，６）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１７）  （５，６）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１１８）  （５，６）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１９）  （５，６）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１２０）  （５，６）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１２１）  （５，６）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１２２）  （５，６）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｑ−Ｒ）の順に実行される演算、
（１２３）  （５，６）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−（Ｐ＋Ｑ）の順に実行される演算、
（１２４）  （５，６）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−（Ｐ＋Ｑ）の順に実行される演算、
（１２５）  （５，６）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｑ＋Ｒ）の順に実行される演算、
のいずれかの演算を演算回路に指示し、
演算回路は、前記制御回路からの指示にもとづき、記憶回路からＰ，Ｑ，Ｒ，Ｔを入力して、前記指示された（１）〜（１２５）のいずれかの演算を実行し、演算結果のＴを記憶回路に戻す、
ことを特徴とする楕円積和演算計算方法。
【請求項３】
ｐを素数とする素体Ｆｐとし、
Ｅｐ：ｙ２≡ｘ３＋αｘ＋β（ｍｏｄ  ｐ），α，β∈Ｆｐ，４α３＋２７β２≠０
で定義される素体Ｆｐ上の楕円曲線Ｅｐ上の相異なる３点をＰ，Ｑ，Ｒとし、互いに独立な３組の整数ａ，ｂ，ｃを、
【数８】
2004233530.tif 000020
のように２進数表現し（ｉ≧０の場合、ａｉ，ｂｉ，ｃｉ∈｛０，１｝，ａ−１＝ｂ−１＝ｃ−１＝０）、
ａ２ｋ＋１＋ａ２ｋ＋ａ２ｋ−１≠０，ｂ２ｋ＋１＋ｂ２ｋ＋ｂ２ｋ−１≠０，
ｃ２ｋ＋１＋ｃ２ｋ＋ｃ２ｋ−１≠０
となるような最大のｋを定義して、楕円積和演算計算
Ｔ＝ａＰ＋ｂＱ＋ｃＲ
を計算する楕円積和演算装置において、
パラメータＰ，Ｑ，Ｒ、演算結果Ｔを格納する記憶手段と、
３組の整数ａ，ｂ，ｃを格納する記憶手段と、
Ａ２ｉ＋１＝４ａ２ｉ＋１＋２ａ２ｉ＋ａ２ｉ−１、Ｂ２ｉ＋１＝４ｂ２ｉ＋１＋２ｂ２ｉ＋ｂ２ｉ−１、Ｃ２ｉ＋１＝４ｃ２ｉ＋１＋２ｃ２ｉ＋ｃ２ｉ−１を選択し、前記選択したＡ２ｉ＋１、Ｂ２ｉ＋１、Ｃ２ｉ＋１の値が、
（１）  （０，７）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔの順に実行される演算、
（２）  （０，７）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（３）  （０，７）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔの順に実行される演算、
（４）  （０，７）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔの順に実行される演算、
（５）  （０，７）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（６）  （０，７）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（７）  （０，７）、（１，２）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（８）  （０，７）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（９）  （０，７）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（１０）  （０，７）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（１１）  （０，７）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔの順に実行される演算、
（１２）  （０，７）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（１３）  （０，７）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１４）  （０，７）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１５）  （０，７）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（１６）  （０，７）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔの順に実行される演算、
（１７）  （０，７）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（１８）  （０，７）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１９）  （０，７）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（２０）  （０，７）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（２１）  （０，７）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２２）  （０，７）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（２３）  （０，７）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２４）  （０，７）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２５）  （０，７）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（２６）  （１，２）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（２７）  （１，２）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（２８）  （１，２）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（２９）  （１，２）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３０）  （１，２）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（３１）  （１，２）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３２）  （１，２）、（１，２）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ＋Ｒ）の順に実行される演算、
（３３）  （１，２）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３４）  （１，２）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３５）  （１，２）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ−Ｒ）の順に実行される演算、
（３６）  （１，２）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３７）  （１，２）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（３８）  （１，２）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３９）  （１，２）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４０）  （１，２）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（４１）  （１，２）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４２）  （１，２）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（４３）  （１，２）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４４）  （１，２）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４５）  （１，２）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（４６）  （１，２）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（４７）  （１，２）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ＋Ｒ）の順に実行される演算、
（４８）  （１，２）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（４９）  （１，２）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（５０）  （１，２）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ−Ｒ）の順に実行される演算、
（５１）  （３）、（０，７）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔの順に実行される演算、
（５２）  （３）、（０，７）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（５３）  （３）、（０，７）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（５４）  （３）、（０，７）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（５５）  （３）、（０，７）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（５６）  （３）、（１，２）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（５７）  （３）、（１，２）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（５８）  （３）、（１，２）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（５９）  （３）、（１，２）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（６０）  （３）、（１，２）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（６１）  （３）、（３）、（０，７）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔの順に実行される演算、
（６２）  （３）、（３）、（１，２）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（６３）  （３）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６４）  （３）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６５）  （３）、（３）、（５，６）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（６６）  （３）、（４）、（０，７）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔの順に実行される演算、
（６７）  （３）、（４）、（１，２）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（６８）  （３）、（４）、（３）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６９）  （３）、（４）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（７０）  （３）、（４）、（５，６）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（７１）  （３）、（５，６）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７２）  （３）、（５，６）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（７３）  （３）、（５，６）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７４）  （３）、（５，６）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７５）  （３）、（５，６）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（７６）  （４）、（０，７）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔの順に実行される演算、
（７７）  （４）、（０，７）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（７８）  （４）、（０，７）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（７９）  （４）、（０，７）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（８０）  （４）、（０，７）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（８１）  （４）、（１，２）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８２）  （４）、（１，２）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（８３）  （４）、（１，２）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８４）  （４）、（１，２）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８５）  （４）、（１，２）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（８６）  （４）、（３）、（０，７）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔの順に実行される演算、
（８７）  （４）、（３）、（１，２）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（８８）  （４）、（３）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（８９）  （４）、（３）、（４）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９０）  （４）、（３）、（５，６）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（９１）  （４）、（４）、（０，７）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔの順に実行される演算、
（９２）  （４）、（４）、（１，２）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（９３）  （４）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９４）  （４）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９５）  （４）、（４）、（５，６）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（９６）  （４）、（５，６）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（９７）  （４）、（５，６）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（９８）  （４）、（５，６）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（９９）  （４）、（５，６）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（１００）  （４）、（５，６）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（１０１）  （５，６）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０２）  （５，６）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１０３）  （５，６）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０４）  （５，６）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０５）  （５，６）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１０６）  （５，６）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１０７）  （５，６）、（１，２）、（１，２  ）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ−Ｒ）の順に実行される演算、
（１０８）  （５，６）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１０９）  （５，６）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１１０）  （５，６）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ＋Ｒ）の順に実行される演算、
（１１１）  （５，６）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１２）  （５，６）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１１３）  （５，６）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１４）  （５，６）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１５）  （５，６）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１１６）  （５，６）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１７）  （５，６）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１１８）  （５，６）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１９）  （５，６）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１２０）  （５，６）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１２１）  （５，６）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１２２）  （５，６）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｑ−Ｒ）の順に実行される演算、
（１２３）  （５，６）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−（Ｐ＋Ｑ）の順に実行される演算、
（１２４）  （５，６）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−（Ｐ＋Ｑ）の順に実行される演算、
（１２５）  （５，６）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｑ＋Ｒ）の順に実行される演算、
を定義した手段と、
最初、Ｔ＝０を記憶手段に初期設定し、以後、前記３組の整数ａ，ｂ，ｃから、ｉ＝ｋ，ｋ−１，…，２，１，０の順番に、順次、２ビットずつシフトして、Ａ２ｉ＋１、Ｂ２ｉ＋１、Ｃ２ｉ＋１を選択し、その値に応じて、上記定義された（１）〜（１２５）の演算の該当する演算を演算手段に指示する制御手段と、
前記制御手段からの指示にもとづき、記憶手段からＰ，Ｑ，Ｒ，Ｔを入力して、前記指示された演算を実行し、演算結果のＴを記憶手段に戻す演算手段と、
を有することを特徴とする楕円積和演算計算装置。
【請求項４】
ｐを素数とする素体Ｆｐとし、
Ｅｐ：ｙ２≡ｘ３＋αｘ＋β（ｍｏｄ  ｐ），α，β∈Ｆｐ，４α３＋２７β２≠０
で定義される素体Ｆｐ上の楕円曲線Ｅｐ上の相異なる３点をＰ，Ｑ，Ｒとし、互いに独立な３組の整数ａ，ｂ，ｃを、
【数９】
2004233530.tif 000021
のように２進数表現し（ｉ≧０の場合、ａｉ，ｂｉ，ｃｉ∈｛０，１｝，ａ−１＝ｂ−１＝ｃ−１＝０）、
ａ２ｋ＋１＋ａ２ｋ＋ａ２ｋ−１≠０，ｂ２ｋ＋１＋ｂ２ｋ＋ｂ２ｋ−１≠０，
ｃ２ｋ＋１＋ｃ２ｋ＋ｃ２ｋ−１≠０
となるような最大のｋを定義して、楕円積和演算計算
Ｔ＝ａＰ＋ｂＱ＋ｃＲ
を、制御回路、記憶回路及び演算回路を含むコンピュータにより自動的に計算するためのプログラムであって、
制御回路が、最初、パラメータＰ，Ｑ，Ｒ、及び、演算結果Ｔの初期値としてＴ＝０を記憶回路に格納し、以後、３組の整数ａ，ｂ，ｃから、ｉ＝ｋ，ｋ−１，…，２，１，０の順番に、順次、２ビットずつシフトして、
Ａ２ｉ＋１＝４ａ２ｉ＋１＋２ａ２ｉ＋ａ２ｉ−１、Ｂ２ｉ＋１＝４ｂ２ｉ＋１＋２ｂ２ｉ＋ｂ２ｉ−１、Ｃ２ｉ＋１＝４ｃ２ｉ＋１＋２ｃ２ｉ＋ｃ２ｉ−１を選択し、前記選択したＡ２ｉ＋１、Ｂ２ｉ＋１、Ｃ２ｉ＋１の値が、
（１）  （０，７）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔの順に実行される演算、
（２）  （０，７）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（３）  （０，７）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔの順に実行される演算、
（４）  （０，７）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔの順に実行される演算、
（５）  （０，７）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（６）  （０，７）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（７）  （０，７）、（１，２）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（８）  （０，７）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（９）  （０，７）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（１０）  （０，７）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（１１）  （０，７）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔの順に実行される演算、
（１２）  （０，７）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（１３）  （０，７）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１４）  （０，７）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１５）  （０，７）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（１６）  （０，７）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔの順に実行される演算、
（１７）  （０，７）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（１８）  （０，７）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（１９）  （０，７）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（２０）  （０，７）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（２１）  （０，７）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２２）  （０，７）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（２３）  （０，７）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２４）  （０，７）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（２５）  （０，７）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（２６）  （１，２）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（２７）  （１，２）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（２８）  （１，２）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（２９）  （１，２）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３０）  （１，２）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（３１）  （１，２）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３２）  （１，２）、（１，２）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ＋Ｒ）の順に実行される演算、
（３３）  （１，２）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３４）  （１，２）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋（Ｐ＋Ｑ）の順に実行される演算、
（３５）  （１，２）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ＋Ｑ−Ｒ）の順に実行される演算、
（３６）  （１，２）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３７）  （１，２）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（３８）  （１，２）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（３９）  （１，２）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４０）  （１，２）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（４１）  （１，２）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４２）  （１，２）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋（Ｐ＋Ｒ）の順に実行される演算、
（４３）  （１，２）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４４）  （１，２）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔ＋Ｐの順に実行される演算、
（４５）  （１，２）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ＋（Ｐ−Ｒ）の順に実行される演算、
（４６）  （１，２）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（４７）  （１，２）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ＋Ｒ）の順に実行される演算、
（４８）  （１，２）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（４９）  （１，２）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ＋（Ｐ−Ｑ）の順に実行される演算、
（５０）  （１，２）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ＋（Ｐ−Ｑ−Ｒ）の順に実行される演算、
（５１）  （３）、（０，７）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔの順に実行される演算、
（５２）  （３）、（０，７）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（５３）  （３）、（０，７）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（５４）  （３）、（０，７）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（５５）  （３）、（０，７）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（５６）  （３）、（１，２）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（５７）  （３）、（１，２）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（５８）  （３）、（１，２）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（５９）  （３）、（１，２）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（６０）  （３）、（１，２）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（６１）  （３）、（３）、（０，７）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔの順に実行される演算、
（６２）  （３）、（３）、（１，２）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（６３）  （３）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６４）  （３）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６５）  （３）、（３）、（５，６）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（６６）  （３）、（４）、（０，７）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔの順に実行される演算、
（６７）  （３）、（４）、（１，２）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（６８）  （３）、（４）、（３）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（６９）  （３）、（４）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（７０）  （３）、（４）、（５，６）の場合、Ｔ←２Ｔ＋（Ｐ−Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（７１）  （３）、（５，６）、（０，７）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７２）  （３）、（５，６）、（１，２）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（７３）  （３）、（５，６）、（３）の場合、Ｔ←２Ｔ＋（Ｐ＋Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７４）  （３）、（５，６）、（４）の場合、Ｔ←２Ｔ＋（Ｐ−Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（７５）  （３）、（５，６）、（５，６）の場合、Ｔ←２Ｔ＋Ｐ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（７６）  （４）、（０，７）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔの順に実行される演算、
（７７）  （４）、（０，７）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（７８）  （４）、（０，７）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（７９）  （４）、（０，７）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（８０）  （４）、（０，７）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−Ｒの順に実行される演算、
（８１）  （４）、（１，２）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８２）  （４）、（１，２）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋（Ｑ＋Ｒ）の順に実行される演算、
（８３）  （４）、（１，２）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８４）  （４）、（１，２）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔ＋Ｑの順に実行される演算、
（８５）  （４）、（１，２）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ＋（Ｑ−Ｒ）の順に実行される演算、
（８６）  （４）、（３）、（０，７）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔの順に実行される演算、
（８７）  （４）、（３）、（１，２）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（８８）  （４）、（３）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（８９）  （４）、（３）、（４）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９０）  （４）、（３）、（５，６）の場合、Ｔ←２Ｔ−（Ｐ−Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（９１）  （４）、（４）、（０，７）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔの順に実行される演算、
（９２）  （４）、（４）、（１，２）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔ＋Ｒの順に実行される演算、
（９３）  （４）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ−Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９４）  （４）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ＋Ｒ）、Ｔ←２Ｔの順に実行される演算、
（９５）  （４）、（４）、（５，６）の場合、Ｔ←２Ｔ−（Ｐ＋Ｑ）、Ｔ←２Ｔ−Ｒの順に実行される演算、
（９６）  （４）、（５，６）、（０，７）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−Ｑの順に実行される演算、
（９７）  （４）、（５，６）、（１，２）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−（Ｑ−Ｒ）の順に実行される演算、
（９８）  （４）、（５，６）、（３）の場合、Ｔ←２Ｔ−（Ｐ−Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（９９）  （４）、（５，６）、（４）の場合、Ｔ←２Ｔ−（Ｐ＋Ｒ）、Ｔ←２Ｔ−Ｑの順に実行される演算、
（１００）  （４）、（５，６）、（５，６）の場合、Ｔ←２Ｔ−Ｐ、Ｔ←２Ｔ−（Ｑ＋Ｒ）の順に実行される演算、
（１０１）  （５，６）、（０，７）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０２）  （５，６）、（０，７）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１０３）  （５，６）、（０，７）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０４）  （５，６）、（０，７）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１０５）  （５，６）、（０，７）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１０６）  （５，６）、（１，２）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１０７）  （５，６）、（１，２）、（１，２  ）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ−Ｒ）の順に実行される演算、
（１０８）  （５，６）、（１，２）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１０９）  （５，６）、（１，２）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−（Ｐ−Ｑ）の順に実行される演算、
（１１０）  （５，６）、（１，２）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ−Ｑ＋Ｒ）の順に実行される演算、
（１１１）  （５，６）、（３）、（０，７）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１２）  （５，６）、（３）、（１，２）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１１３）  （５，６）、（３）、（３）の場合、Ｔ←２Ｔ＋（Ｑ＋Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１４）  （５，６）、（３）、（４）の場合、Ｔ←２Ｔ＋（Ｑ−Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１５）  （５，６）、（３）、（５，６）の場合、Ｔ←２Ｔ＋Ｑ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１１６）  （５，６）、（４）、（０，７）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１７）  （５，６）、（４）、（１，２）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−（Ｐ−Ｒ）の順に実行される演算、
（１１８）  （５，６）、（４）、（３）の場合、Ｔ←２Ｔ−（Ｑ−Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１１９）  （５，６）、（４）、（４）の場合、Ｔ←２Ｔ−（Ｑ＋Ｒ）、Ｔ←２Ｔ−Ｐの順に実行される演算、
（１２０）  （５，６）、（４）、（５，６）の場合、Ｔ←２Ｔ−Ｑ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１２１）  （５，６）、（５，６）、（０，７）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｒ）の順に実行される演算、
（１２２）  （５，６）、（５，６）、（１，２）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｑ−Ｒ）の順に実行される演算、
（１２３）  （５，６）、（５，６）、（３）の場合、Ｔ←２Ｔ＋Ｒ、Ｔ←２Ｔ−（Ｐ＋Ｑ）の順に実行される演算、
（１２４）  （５，６）、（５，６）、（４）の場合、Ｔ←２Ｔ−Ｒ、Ｔ←２Ｔ−（Ｐ＋Ｑ）の順に実行される演算、
（１２５）  （５，６）、（５，６）、（５，６）の場合、Ｔ←２Ｔ、Ｔ←２Ｔ−（Ｐ＋Ｑ＋Ｒ）の順に実行される演算、
のいずれかの演算を演算回路に指示する処理プロセス、
演算回路が、前記制御回路からの指示にもとづき、順次、記憶回路からＰ，Ｑ，Ｒ，Ｔを入力して、前記指示された演算を実行し、演算結果のＴを記憶回路に戻す処理プロセス、
をコンピュータが実行するためのプログラム。
【請求項５】
請求項４記載のプログラムが記録されていることを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号技術などに用いられる、素体Ｆｐ上の３次関数の複数の点の楕円積和演算を高速に実現する方法及び装置、プログラム、並びに、そのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
楕円暗号では、素体（有限体）上の楕円曲線ＥＰ
Ｅｐ：ｙ２≡ｘ３＋αｘ＋β（ｍｏｄ  ｐ），α，β∈Ｆｐ，４α３＋２７β２≠０
上の整数点（ｘ，ｙ）の解集合をメッセージ空間とみなす。つまり、楕円曲線上の点を有限の整数値（０以上ｐ未満）に限定し、演算はこの上限値ｐで割った余りとする（ｍｏｄ演算）。
【０００３】
いま、素体ＦＰ上の楕円曲線ＥＰ上の２点をＰ（ｘ１，ｙ１），Ｑ（ｘ２，ｙ２）とし、Ｔ＝ａＰ＋ｂＱを求める値とする。Ｔ（ｘ３，ｙ３）も楕円曲線ＥＰ上の点である。図１２に、従来の算出手順のフローチャートを示す。ただし、ａとｂは
【０００４】
【数１０】
2004233530.tif 000003
【０００５】
のように２進表現し、ａ，ｂの第ｉビット目の係数を各々ｃＩ，ｄｉ（∈｛０，１｝）とする。ｋはａｋ≠０、またはｂｋ≠０となる最大の整数である。また、楕円曲線上の各種演算の定義を以下の通りとする。
【０００６】
楕円２倍演算Ｔ＝２Ｐは、
１．Ｐ＝（０，０）の場合は、ｘ３＝０，ｙ３＝０
２．Ｐ≠（０，０）の場合は、
【０００７】
【数１１】
2004233530.tif 000004
とする。
【０００８】
また、楕円加算演算Ｔ＝Ｐ＋Ｑは、
３．Ｐ＝（０，０）の場合は、ｘ３＝ｘ２，ｙ３＝ｙ２
４．Ｐ≠（０，０）、かつＱ＝（０，０）の場合は、ｘ３＝ｘ１，ｙ３＝ｙ１
５．Ｐ≠（０，０）、かつＱ＝（０，０）、かつＰ＋Ｑ＝（０，０）の場合は、ｘ３＝０，ｙ３＝０
６．Ｐ≠（０，０）、かつＱ≠（０，０）かつＰ＋Ｑ≠（０，０）の場合は、
【０００９】
【数１２】
2004233530.tif 000005
とする。
【００１０】
図１２のフローチャートは、次の処理を実行するものである。
Ｔ←０
ｆｏｒ（ｉ＝ｋ；ｉ≧０；ｉ−−）｛
ｉｆ（（ｃｉ＝＝０）＆＆（ｄｉ＝＝０））ｔｈｅｎ｛Ｔ←２Ｔ｝
ｉｆ（（ｃｉ＝＝１）＆＆（ｄｉ＝＝０））ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←Ｔ＋Ｐ｝
ｉｆ（（ｃｉ＝＝０）＆＆（ｄｉ＝＝１））ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←Ｔ＋Ｑ｝
ｉｆ（（ｃｉ＝＝１）＆＆（ｄｉ＝＝１））ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←Ｔ＋（Ｐ＋Ｑ）｝
｝
Ｒｅｔｕｒｎ  Ｔ
初期値としてＴに０を設定し、ｉ＝ｋ，ｋ−１，…，２，１，０の順番に、（ａｉ，ｂｉ）の値（００）、（０１）、（１０）、（１１）にしたがって所定の演算を繰り返し実行し、最終結果のＴを求める。
【００１１】
図１２に示した処理手順にしたがって、上記で定義したｋを用いて、従来の算出手順に必要な楕円加減算と楕円２倍算の必要回数を示すと、図１３のようになる。楕円曲線上の対象点が増加すると、この必要回数は更に増大する。
【００１２】
【発明が解決しようとする課題】
本発明の目的は、素体（有限体）上の楕円曲線上の相異なる複数の点を各々整数倍し、かつ、該整数倍した結果を加算する楕円積和演算を、従来技術に比べて高速に行うことを可能とする方法及び装置、プログラム並びに、そのプログラムを記録した記録媒体を提供することにある。
【００１３】
【課題を解決するための手段】
本発明では、ｐを素数とする素体Ｆｐとし、
Ｅｐ：ｙ２≡ｘ３＋αｘ＋β（ｍｏｄ  ｐ），α，β∈Ｆｐ，４α３＋２７β２≠０
で定義される素体Ｆｐ上の楕円曲線Ｅｐ上の相異なるｎ個の点をＰ１〜Ｐｎとし、互いに独立なｎ組の整数ｍｉ（ｉ＝１，２，…，ｎ）として場合、ｎ組の整数ｍｉを、
【数１３】
2004233530.tif 000006
のように２進数表現して、任意のｉ（１≦ｉ≦ｎ）に対して、
ｍｉ２ｋ＋１＋ｍｉ２ｋ＋ｍｉ２ｋ−１≠０，
となるような最大のｋを定義して、楕円積和演算計算
【数１４】
2004233530.tif 000007
を、制御回路、記憶回路及び演算回路を含むコンピュータ等により以下のようにして自動的に計算する。
いま、  Ｍｉ２ｊ＋１＝４ｍｉ２ｊ＋１＋２ｍｉ２ｊ＋ｍｉ２ｊ−１（ｊ≧０）として、ｕｉとｖｉを次のように定義する。
【数１５】
2004233530.tif 000008
【数１６】
2004233530.tif 000009
【００１４】
最初、ｊ＝ｋにおいて、
【数１７】
2004233530.tif 000010
引続き、
【数１８】
2004233530.tif 000011
を実行する。以後、同様に前記式（４）と（５）の演算をｊ＝ｋ−１，ｋ−２，…，０の順番で繰り返し、実行して得られた演算結果のＴを求める解とする。
ここで、式（４）と（５）の楕円２倍算、楕円加減算等の演算パターンはＭ１２ｊ＋１，Ｍ２２ｊ＋１，…，Ｍｎ２ｊ＋１の各値の組み合せで一義的に定まる。そこでＭ１２ｊ＋１，Ｍ２２ｊ＋１，…，Ｍｎ２ｊ＋１の値と式（４）、（５）の演算パターンの取り得る組み合せをあらかじめ決めておく。
制御回路は、パラメータＰ１〜Ｐｎ、演算結果Ｔの初期値としてＴ＝０を記憶回路に格納し、ｎ組の整数ｍ１〜ｍｎから、ｊ＝ｋ，ｋ−１，ｋ−２，１…，０の順番に、順次、２ビットずつシフトして、（Ｍ１２ｊ＋１，Ｍ２２ｊ＋１，…，Ｍｎ２ｊ＋１）を選択し、その値により、式（４）、（５）の演算パターンを演算回路に指示する。
演算回路は、前記制御回路からの指示にもとづき、記憶回路からＰ１〜Ｐｎ、Ｔを読み出して、指示された演算パターンの演算を実行し、演算結果のＴを記憶回路に戻すようにする。
【００１５】
【発明の実施の形態】
以下、本発明の一実施の形態について説明する。
ここでは、ｐを素数とする素体（有限体）上の楕円曲線ＥＰ
Ｅｐ：ｙ２≡ｘ３＋αｘ＋β    （ｍｏｄ  ｐ）
上の３点をＰ（ｘ１，ｙ１）、Ｑ（ｘ２，ｙ２）、Ｒ（ｘ３，ｙ３）とし、楕円積和演算
Ｔ＝ａＰ＋ｂＱ＋ｃＲ
を求める値とする。Ｔ（ｘ４，ｙ４）も楕円曲線ＥＰ上の点である。ただし、ａ，ｂ，ｃは
【００１６】
【数１９】
2004233530.tif 000012
【００１７】
のように２進表現し、ａ，ｂ，ｃの第ｉビット目の係数ａｉ，ｂｉ，ｃｉを、ｉ≧０の場合、ａｉ，ｂｉ，ｃｉ∈｛０，１｝とする。また、ａ−１＝ｂ−１＝ｃ−１＝０とする。ｋはａ２ｋ＋１＋ａ２ｋ＋ａ２ｋ−１≠０、またはｂ２ｋ＋１＋ｂ２ｋ＋ｂ２ｋ−１≠０、またはｃ２ｋ＋１＋ｃ２ｋ＋ｃ２ｋ−１≠０となるような最大の整数とする。更に、Ａ２ｉ＋１＝４ａ２ｉ＋１＋２ａ２ｉ＋ａ２ｉ−１、Ｂ２ｉ＋１＝４ｂ２ｉ＋１＋２ｂ２ｉ＋ｂ２ｉ−１、Ｃ２ｉ＋１＝４ｃ２ｉ＋１＋２ｃ２ｉ＋ｃ２ｉ−１（ｉ≧０）とする。
【００１８】
図１に本楕円積和演算計算装置の構成例を示す。図１において、制御回路（ＣＰＵ）１００は全体の動作の制御を司る。この制御回路１００は、ａとｂとｃを保持するレジスタ、変数ｉをカウントするカウンタなどを内蔵し、整数ａ，ｂ，ｃから、ｉ＝ｋ，ｋ−１，…，２，１，０の順番に２ビットずつシフトして、順次、Ａ２ｉ＋１，Ｂ２ｉ＋１，Ｃ２ｉ＋１を選択し、その値に応じて、記憶回路１１０に対して所定データの読出しを指示し、演算回路１２０に対して演算の種類と実行順序（演算パターン）を指示する。記憶回路１１０は、Ｐ，Ｑ，Ｒ，Ｔ（初期値は０）のデータなどを格納しており、制御回路１００の指示されたデータを読み出して演算回路１２０に与える。演算回路１２０は２倍演算、加算、減算などの演算を行う機能を有し、記憶回路１１０から与えられたデータを入力として、制御回路１００の指示された演算を、指示された順序で実行し、演算結果のＴを記憶回路１１０に戻す。
【００１９】
図２に、本楕円積和演算計算装置の概略処理フローチャートを示す。制御回路１００の制御下で、パラメータＰ，Ｑ，Ｒ，ａ，ｂ，ｃなどを入力し、Ｐ，Ｑ，Ｒは記憶回路１１０に格納し、ａ，ｂ，ｃは制御回路１００の内部レジスタに設定する（ステップ２１０）。次に、制御回路１００により記憶回路１１０、演算回路１２０の動作を制御してＴ＝ａＰ＋ｂＱ＋ｃＲの計算を実行し（ステップ２２０）、その計算結果Ｔを出力する（ステップ２３０）。
【００２０】
図３乃至図７は、図２のＴ＝ａＰ＋ｂＱ＋ｃＲの計算部分（ステップ２２０）の詳細処理フローチャートである。また、図８乃至図１０は、図３〜図７中のケース（Ｃａｓｅ）１〜１２５の内容を示している。図８乃至図１０において、例えば、ケース１は、Ａ２ｉ＋１が０または７、Ｂ２ｉ＋１が０または７、同じくＣ２ｉ＋１が０または７の場合、まず、Ｔ＝２Ｔを演算し、引き続いて、またＴ＝２Ｔを演算することを意味する。他のケースについても同様である。
【００２１】
図３〜図７のフローチャートは、次の処理を実行するものである。なお、実際の演算の実行にあたっては、２倍算と加減算が含まれる場合には、まず、２倍算を行い、次に加減算を行うことになる。
Ｔ←０
ｆｏｒ（ｉ＝ｋ；ｉ≧０；ｉ−−）｛
ｉｆ（Ｃａｓｅ    １）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ    ２）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ    ３）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ    ４）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ    ５）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ    ６）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ    ７）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ    ８）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ    ９）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １０）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １１）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １２）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １３）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｑ＋Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １４）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｑ−Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １５）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ）；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １６）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １７）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １８）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｑ−Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  １９）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｑ＋Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２０）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２１）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２２）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２３）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２４）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２５）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２６）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２７）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｐ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２８）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ２９）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３０）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３１）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｐ＋Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３２）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｐ＋Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３３）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ＋（Ｐ＋Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３４）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ＋（Ｐ＋Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３５）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｐ＋Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３６）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３７）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ；Ｔ←２Ｔ＋（Ｐ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３８）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｑ＋Ｒ）；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ３９）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｑ−Ｒ）；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４０）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ；Ｔ←２Ｔ＋（Ｐ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４１）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４２）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ＋（Ｐ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４３）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｑ−Ｒ）；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４４）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｑ＋Ｒ）；Ｔ←２Ｔ＋Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４５）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ＋（Ｐ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４６）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｐ−Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４７）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｐ−Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４８）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ＋（Ｐ−Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ４９）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ＋（Ｐ−Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５０）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ＋（Ｐ−Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５１）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５２）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５３）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ＋Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５４）ｔｈｅｎ｛Ｔ←２Ｔ（Ｐ−Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５５）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５６）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５７）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ＋（Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５８）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ＋Ｒ）；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ５９）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ−Ｒ）；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６０）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ＋（Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６１）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ＋Ｑ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６２）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ＋Ｑ）；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６３）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ＋Ｑ＋Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６４）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ＋Ｑ−Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６５）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ＋Ｑ）；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６６）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ−Ｑ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６７）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ−Ｑ）；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６８）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ−Ｑ＋Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ６９）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ−Ｑ−Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７０）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ−Ｑ）；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７１）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７２）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ−（Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７３）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ＋Ｒ）；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７４）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｐ−Ｒ）；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７５）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｐ；Ｔ←２Ｔ−（Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７６）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７７）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７８）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ−Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ７９）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ＋Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８０）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８１）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８２）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ＋（Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８３）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ−Ｒ）；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８４）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ＋Ｒ）；Ｔ←２Ｔ＋Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８５）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ＋（Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８６）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ−Ｑ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８７）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ−Ｑ）；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８８）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ−Ｑ−Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ８９）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ−Ｑ＋Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９０）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ−Ｑ）；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９１）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ＋Ｑ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９２）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ＋Ｑ）；Ｔ←２Ｔ＋Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９３）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ＋Ｑ−Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９４）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ＋Ｑ＋Ｒ）；Ｔ←２Ｔ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９５）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ＋Ｑ）；Ｔ←２Ｔ−Ｒ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９６）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９７）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ−（Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９８）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ−Ｒ）；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ  ９９）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｐ＋Ｒ）；Ｔ←２Ｔ−Ｑ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１００）ｔｈｅｎ｛Ｔ←２Ｔ−Ｐ；Ｔ←２Ｔ−（Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０１）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０２）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０３）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０４）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０５）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０６）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ−Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０７）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ−Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０８）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ−（Ｐ−Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１０９）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ−（Ｐ−Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１０）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ−Ｑ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１１）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１２）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ；Ｔ←２Ｔ−（Ｐ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１３）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｑ＋Ｒ）；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１４）ｔｈｅｎ｛Ｔ←２Ｔ＋（Ｑ−Ｒ）；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１５）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｑ；Ｔ←２Ｔ−（Ｐ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１６）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１７）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ−（Ｐ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１８）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｑ−Ｒ）；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１１９）ｔｈｅｎ｛Ｔ←２Ｔ−（Ｑ＋Ｒ）；Ｔ←２Ｔ−Ｐ｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１２０）ｔｈｅｎ｛Ｔ←２Ｔ−Ｑ；Ｔ←２Ｔ−（Ｐ＋Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１２１）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ＋Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１２２）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ＋Ｑ−Ｒ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１２３）ｔｈｅｎ｛Ｔ←２Ｔ＋Ｒ；Ｔ←２Ｔ−（Ｐ＋Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１２４）ｔｈｅｎ｛Ｔ←２Ｔ−Ｒ；Ｔ←２Ｔ−（Ｐ＋Ｑ）｝
ｅｌｓｅ  ｉｆ（Ｃａｓｅ１２５）ｔｈｅｎ｛Ｔ←２Ｔ；Ｔ←２Ｔ−（Ｐ＋Ｑ＋Ｒ）｝
｝
【００２２】
上記処理手順のプログラム（これを楕円積和演算計算プログラムと称す）は、コンピュータが読み取り可能な記録媒体、例えばＦＤやメモリカード、コンパクトディスク（ＣＤ−ＲＯＭ）などに記録して提供することが可能である。制御回路１００が、この記録媒体に記録されたの楕円積和演算計算プログラムを読み込み実行することで、図３〜図７の処理フローが実現する。なお、制御回路１００は、この楕円積和演算計算プログラムを記録したＲＯＭをあらかじめ保持しておくことでもよい。
【００２３】
なお、図３〜図７に示した処理手順において、Ｐ＋Ｑ，Ｐ−Ｑ，Ｐ＋Ｒ，Ｐ−Ｒ，Ｑ＋Ｒ，Ｑ−Ｒ，Ｐ＋Ｑ＋Ｒ，Ｐ＋Ｑ−Ｒ，Ｐ−Ｑ＋Ｒ，Ｐ−Ｑ−Ｒは予め計算して記憶回路１１０に記憶しておき、それを使用することでもよい。この場合、Ｔは楕円２倍算と楕円加減算の２ステップで実施できる。
【００２４】
図１１は、制御回路１００の別の実施形態であり、図３〜図７の処理をハードウェアロックで実現した構成例を示したものである。図１１において、１０１はａ，ｂ，ｃを格納したシフトレジスタであり、シフトロックにより２ビットずつシフトし、ｉ＝ｋ、ｋ−１，…，２，１，０の順番に、順次、Ａ２ｉ＋１，Ｂ２ｉ＋１，Ｃ２ｉ＋１を読み出すことを実現する。デコーダ１０２−１〜１０２−１２５は図８〜図１０のケース１〜１２５に対応し、シフトレジスタ１０１の出力Ａ２ｉ＋１，Ｂ２ｉ＋１，Ｃ２ｉ＋１を並列にデコードし、いずれかで一致した場合、該当デコーダが一致信号を出力する。演算制御テーブル１０３は、ケース１−１２５に対応した演算パターンの演算コマンド群を保持しており、デコーダ１０２−１〜１０２−１２５のデコード出力にもとづいて、対応する演算コマンド群の制御下で、記憶回路１１０に対して所望データの読出しを指示し、演算回路１２０に対しては演算の種類とその実行順序を指示する。
【００２５】
図１１の構成によれば、図３〜図７のケース１〜１２５の場合分けが並列に処理でき、さらに高速化が実現する。また、ハードロジックとすることにより、制御回路１００と記憶回路１１０と演算回路１２０とを一体構成にした半導体集積回路が実現可能である。
【００２６】
以上、本発明の一実施形態を説明したが、本発明は、先の式（１）〜（５）のアルコリズムを適用して、一般に楕円曲線上の相異なる複数の点を対象に楕円積和を実現できることは云うまでもない。例えば、図１１のハードロジックの場合には、シフトレジスタ１０１が一般にｎ個となり、デコーダ１０２と演算制御テーブル１０３は演算パターンの場合分けが増加する分、追加すればよい。
【００２７】
【発明の効果】
以上説明したように、本発明によれば、素体ＦＰ上の楕円曲線ＥＰ上の相異なる複数の点を各々整数倍し、かつ整数倍した結果を加算する楕円積和演算を、高速に実施できる利点がある。
【図面の簡単な説明】
【図１】本発明の一実施形態の楕円積和演算装置の構成例を示すブロック図である。
【図２】図１の楕円積和演算装置の全体的処理フローチャートである。
【図３】図２の積和演算計算部分の詳細処理フローチャートである。
【図４】図３のつづきのフローチャートである。
【図５】図４のつづきのフローチャートである。
【図６】図５のつづきのフローチャートである。
【図７】図６のつづきのフローチャートである。
【図８】図３〜図７の演算種別、実行順序の場合分けを示す図である。
【図９】同じく図３〜図７の演算種別、実行順序の場合わけを示す図である。
【図１０】同じく図３〜図７の演算種別、実行順序の場合わけを示す図である。
【図１１】図１の制御回路の機能をハードロジックで実現した構成例を示す図である。
【図１２】従来手法による楕円積和演の処理フローチャートである。
【図１３】図１２の従来手法の算出処理に必要な楕円加算演算と楕円２倍演算の回数を示す図である。
【符号の説明】
１００  制御回路
１１０  記憶回路
１２０  演算回路
【図１】
2004233530.tif 000023
【図２】
2004233530.tif 000024
【図３】
2004233530.tif 000025
【図４】
2004233530.tif 000026
【図５】
2004233530.tif 000027
【図６】
2004233530.tif 000028
【図７】
2004233530.tif 000029
【図８】
2004233530.tif 000030
【図９】
2004233530.tif 000031
【図１０】
2004233530.tif 000032
【図１１】
2004233530.tif 000033
【図１２】
2004233530.tif 000034
【図１３】
2004233530.tif 000035