(57)【要約】  べき乗算やスラカー倍算などからなる演算を高速で実行可能な演算方法及び演算装置を提供する。  複数の異なる元Ｙを有し、夫々の元Ｙは、複数の異なる元Ｘが演算子により結合される組により表される場合に、夫々の元Ｙを電子計算機により演算する演算方法において、各元Ｘを設定して、各元Ｙに元Ｘを関連付け、各元Ｙが同一の元Ｘを有しているか否かを示す指標となるテンポラリデータを元Ｘごとに設定し、各元Ｙを演算子により結合されるテンポラリデータにより表す、各元Ｙに含まれるテンポラリデータにおいて、複数の元Ｙにおいて共通するテンポラリデータの組み合わせがある場合に、その共通するテンポラリデータを結合して新たなテンポラリデータを設定し、この新たなテンポラリデータを用いて各組からなる各元Ｙを演算する。
2009020216.tif 000002
【特許請求の範囲】
【請求項１】
標数ｐ、拡大次数ｍの拡大体Fpmの元Ａのべき乗算Anを、指数部ｎのｐ進数表現である
【数１】
2009020216.tif 000081
を用いて、フロベニウス写像により
【数２】
2009020216.tif 000082
と表されるべき乗算の演算方法において、
前記指数部ｎのｐの所定次数の項と、この項の次数よりも一次だけ高次の項または一次以上高次の複数の項とを１組として、前記指数部ｎを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、この係数をｐ進数表示として前記係数による元Ａのべき乗算が行われた場合の各組での同一の桁に値が存在しているか否かを示す指標を有するテンポラリデータを桁ごとに設定するステップと、
前記テンポラリデータの値を、このテンポラリデータで値が存在しているとされた桁における乗数を用いて特定するステップと、
所定の前記テンポラリデータどうしを乗算した結果を、各組の前記係数でのべき乗算の結果とするステップと
を有することを特徴とするべき乗算の演算方法。
【請求項２】
請求項１に記載の、べき乗算の演算方法において、
所定の前記テンポラリデータどうしを乗算して、各組の前記係数でのべき乗算の結果を演算する際に、共通して乗算するテンポラリデータの組み合わせを特定するステップと、
前記テンポラリデータの組み合わせを用いて、各組の前記係数でのべき乗算の結果を演算するステップと
を有することを特徴とするべき乗算の演算方法。
【請求項３】
標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数３】
2009020216.tif 000083
任意の有理点Ａは次式を満たし、
【数４】
2009020216.tif 000084
スカラー部[ｎ]をψ進数展開した
【数５】
2009020216.tif 000085
と表されるスカラー倍算において、
前記指数部ｉの写像ψの所定次数の項と、この項の次数よりも１次だけ高次の項または１次以上の高次の項の複数の項とを１組として、前記写像Ｆを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定するステップと、
この係数をψ進数表示として、前記係数による元Ａの加算が行われる場合の各組でのψ進数表示の同一の桁に値が存在しているか否か示す指標を有するテンポラリデータを桁ごとに設定するステップと、
前記各係数を構成するψ進数の各[ｎｉ]Ａを、このテンポラリデータどうしを加算した結果により特定するステップと、を有することを特徴とするスカラー倍算の演算方法。
【請求項４】
複数の異なる元Ｙを有し、夫々の前記元Ｙは、複数の異なる元Ｘが演算子により結合される組により表される場合に、前記夫々の元Ｙを電子計算機により演算する演算方法において、
前記各元Ｘを設定して、前記各元Ｙに前記元Ｘを関連付けるステップと、
前記各元Ｙが同一の元Ｘを有しているか否かを示す指標となるテンポラリデータを前記元Ｘごとに設定し、前記各元Ｙを前記演算子により結合される前記テンポラリデータにより表すステップと、
前記各元Ｙに含まれるテンポラリデータにおいて、複数の元Ｙにおいて共通するテンポラリデータの組み合わせがある場合に、その共通するテンポラリデータを結合して新たなテンポラリデータを設定するステップと、
前記新たなテンポラリデータを用いて前記各組からなる各元Ｙを演算するステップと、を有する演算方法。
【請求項５】
請求項４に記載の演算方法において、
前記共通するテンポラリデータを結合して新たなテンポラリデータを設定するステップにおいて、前記複数の元Ｙを複数のグループに分割し、前記分割されたグループごとに共通するテンポラリデータを結合して新たなテンポラリデータを設定することを特徴とする演算方法。
【請求項６】
請求項４又は５に記載の演算方法において、
標数ｐ、拡大次数ｍの拡大体Ｆｐmの元Ａのべき乗算Ａnを、指数部ｎのｐ進数表現である
【数６】
2009020216.tif 000086
を用いて、フロベニウス写像により
【数７】
2009020216.tif 000087
と表されるべき乗算において、
前記演算子は乗算であり、前記複数の元Ｙは、前記元Ａのｐ進数表現における各係数ｎｉにより定められるべき乗の形式Ａni（注：ＡniはＡの指数ｎｉによるべき乗を意味する。）により与えられ、前記複数の元Ｘは、前記元Ａのべき乗であるＡ,Ａ2,...,Ａ2u（注：Ａ2uはＡの指数２ｕによるべき乗を意味する。）,u=Flr(log2(max(ni)))及びそれらのフロベニウス写像から選ばれることを特徴とする演算方法。
【請求項７】
請求項４又は５に記載の演算方法において、
標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数８】
2009020216.tif 000088
任意の有理点Ａは次式を満たし、
【数９】
2009020216.tif 000089
係数部[ｎｉ]Ａとする写像ψをψ進展開した
【数１０】
2009020216.tif 000090
と表されるスカラー倍算において、
前記演算子は加算であり、前記複数の元Ｙは、前記ψｉ項の係数[ｎｉ]により定められるスカラー倍の形式[ｎｉ]Ａ及びそれらのψ写像により与えられ、前記複数の元Ｘは、Ａのスカラー倍であるＡ,[2]Ａ,...,[2u]Ａ,u=Flr(log2(max(ni)))及びそれらのψ写像から選ばれることを特徴とする演算方法。
【請求項８】
標数ｐ、拡大次数ｍの拡大体Fpmの元Ａのべき乗算Anを、指数部ｎのｐ進数表現である
【数１１】
2009020216.tif 000091
を用いて、フロベニウス写像により
【数１２】
2009020216.tif 000092
と表されるべき乗算の演算装置において、
前記指数部ｎのｐの所定次数の項と、この項の次数よりも一次だけ高次の項または一次以上高次の複数の項とを１組として、前記指数部ｎを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、この係数をｐ進数表示として前記係数による元Ａのべき乗算が行われた場合の各組での同一の桁に値が存在しているか否かを示す指標を有するテンポラリデータを桁ごとに設定して、このテンポラリデータで値が存在しているとされた桁における乗数を用いて特定したテンポラリデータの値を記憶する記憶部と、
所定の前記テンポラリデータどうしを乗算した結果を、各組の前記係数でのべき乗算の結果として記憶する記憶部と
を備えたことを特徴とするべき乗算の演算装置。
【請求項９】
請求項８に記載の、べき乗算の演算装置において、
所定の前記テンポラリデータどうしを乗算して、各組の前記係数でのべき乗算の結果を演算する際に、共通して乗算するテンポラリデータの組み合わせを特定し、このテンポラリデータの組み合わせを用いて、各組の前記係数でのべき乗算の結果を演算して記憶する記憶部を備えたことを特徴とするべき乗算の演算装置。
【請求項１０】
標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数１３】
2009020216.tif 000093
任意の有理点Ａは次式を満たし、
【数１４】
2009020216.tif 000094
スカラー部[ｎ]をψ進数展開した
【数１５】
2009020216.tif 000095
と表されるスカラー倍算を行う演算装置において、
前記指数部ｉの写像ψの所定次数の項と、この項の次数よりも１次だけ高次の項または１次以上の高次の項の複数の項とを１組として、前記写像Ｆを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、
この係数をψ進数表示として、前記係数による元Ａの加算が行われる場合の各組でのψ進数表示の同一の桁に値が存在しているか否か示す指標を有するテンポラリデータを桁ごとに設定し、
前記各係数を構成するψ進数の各[ｎｉ]Ａを、このテンポラリデータどうしを加算した結果により特定すること、を特徴とするスカラー倍算の演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算方法及び演算装置に関し、特にべき乗算又はスカラー倍算の演算方法又はその演算装置に関する。
【背景技術】
【０００２】
従来、公開鍵暗号などの暗号化方法を用いた場合には、暗号化される平文のデータと、暗号化用の鍵との乗算を行って暗号データを生成している。また、暗号データの復号は、暗号データと復号用の鍵との乗算によって行っている。【０００３】
この場合、平文のデータと暗号化用の鍵、及び暗号データと復号用の鍵は、それぞれ拡大体の元としており、拡大体の乗算を行っていることとなっている。【０００４】
例えば、Elgamal暗号では、標数ｐ、拡大次数ｍの拡大体Ｆｐmを用い、特に、暗号データの第三者による解読に対する安全性を確保するために鍵長を2000ビットとしている。この場合、拡大体の非零元Ａに対して、2000ビットの正整数ｎ＜pmを用いて、Anのようなべき乗の演算を行う必要がある。【０００５】
なお、一般的には、拡大体Ｆｐmを構成するために、拡大体Ｆｐ上のｍ次既約多項式f(x)を準備し、その零点をω∈Ｆｐmとして、以下の基底を準備している。
{１，ω，ω2，・・・，ωm-1}【０００６】
この基底は、特に多項式基底と呼ばれ、任意の元Ａ∈Ｆｐmは、次式で表されることとなる。
Ａ＝a0＋a1ω＋・・・＋am-1ωm-1【０００７】
すなわち、元Ａのベクトル表現は、vA＝(a0，a1，...，am-1)となる。【０００８】
また、以下に示すωのＦｐに関する共役元の集合が基底を成すときには、正規基底と呼ばれる。
【数１６】
2009020216.tif 000003
【０００９】
この正規基底は、以下に示すようにフロベニウス写像に適した基底であり、Ｆｐmの任意の元Ａを以下のように考えると、
【数１７】
2009020216.tif 000004
フロベニウス写像が以下のように与えられる。
【数１８】
2009020216.tif 000005
【００１０】
すなわち、正規基底を用いればフロベニウス写像には数学的な計算が必要ないことがわかる。以下において、本発明では、ｉ回のフロベニウス写像を以下のように表記することとする。
【数１９】
2009020216.tif 000006
【００１１】
べき乗の演算は、暗号化及び復号の演算処理に要する時間に大きく影響しており、べき乗の演算の高速化が暗号化及び復号の演算処理の高速化に繋がるため、べき乗の演算を高速に行う様々な方法が提案されている。【００１２】
その一つとして、バイナリ法が知られている（例えば、非特許文献１参照。）。例えば、楕円曲線関数におけるスカラー倍算の「５５Ｐ」（Ｐは楕円曲線上の点）を演算する場合、「５５」が２進数において「１１０１１１」であることから、
(１１０１１１)2Ｐ＝２(２(２2(２Ｐ＋Ｐ)＋Ｐ)＋Ｐ)＋Ｐ
として演算を行うことにより演算回数を削減して高速化しているものである。ここで「(
)2」は２進数表記であることを示している。このバイナリ法では、平均的にFlr(log2(n))回の自乗算と、Flr(log2(n))/2回の乗算が必要になっている。【００１３】
また、Window法と呼ばれる方法が提案されている（例えば、非特許文献２参照。）。Window法では、例えば窓サイズを３とした場合、元Ａに対してあらかじめA2,A3,A4,A5,A6,A7の各コンポーネントを準備しておき、A318を演算する場合には、「３１８」が2進数表記で「１００１１１１１０」であることを利用して、
【数２０】
2009020216.tif 000007
とし、(１００)2＝４，(１１１)2＝７，(１１０)2＝６であるので、A4,A6,A7のコンポーネントを用いて演算を行うものである。ここで、各コンポーネントを準備するための計算を除けば、Window法では、Flr(log2n)-w回の自乗算と、Flr(log2n/w)の乗算が必要になっている。
【非特許文献１】H.Cohen  and  G.Frey  et  al,「Handbook  of  elliptic  and  hyperellipticcurve  cryptography」,published  by  Chapman  &  Hall/CRC,  2006,  p.146．
【非特許文献２】H.Cohen  and  G.Frey  et  al,「Handbook  of  elliptic  and  hyperelliptic  curve  cryptography」,published  by  Chapman  &  Hall/CRC,  2006,  p.149．
【非特許文献３】吉田知輝、加藤英洋、根角健太、野上保之、森川良孝,“ペアリング暗号に効果的な拡大体上べき乗算に関する一考察”,Tech.  Rep.  of  IEICE,  ISEC  vol.  108,  no.  162,  pp.  101-108,  2008．
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、昨今、暗号データの解読を防止するために暗号化鍵及び復号鍵の鍵長がさらに長くなっており、バイナリ法やWindow法ではべき乗算又はスカラー倍算に要する時間の更なる短縮化が困難なことから、暗号化及び復号に要する時間が長くなりすぎているという問題があった。【００１５】
本発明者らは、このような現状に鑑み、べき乗算やスカラー倍算などの演算をより高速で実行可能とすることにより暗号化及び復号の処理時間の短縮化を図るべく研究を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１６】
本発明のべき乗算の演算方法では、標数ｐ、拡大次数ｍの拡大体Ｆｐmの元Ａのべき乗算Anを、指数部ｎのｐ進数表現である
【数２１】
2009020216.tif 000008
を用いて、フロベニウス写像により
【数２２】
2009020216.tif 000009
と表されるべき乗算の演算方法において、前記指数部ｎのｐの所定次数の項と、この項の次数よりも一次だけ高次の項または一次以上高次の複数の項とを１組として、前記指数部ｎを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、この係数をｐ進数表示として前記係数による元Ａのべき乗算が行われた場合の各組での同一の桁に値が存在しているか否かを示す指標を有するテンポラリデータを桁ごとに設定するステップと、前記テンポラリデータの値を、このテンポラリデータで値が存在しているとされた桁における乗数を用いて特定するステップと、所定の前記テンポラリデータどうしを乗算した結果を、各組の前記係数でのべき乗算の結果とするステップを有することとした。これにより、べき乗算の演算を高速に行うことができる。【００１７】
また、本発明のべき乗算の演算方法では、所定の前記テンポラリデータどうしを乗算して、各組の前記係数でのべき乗算の結果を演算する際に、共通して乗算するテンポラリデータの組み合わせを特定するステップと、前記テンポラリデータの組み合わせを用いて、各組の前記係数でのべき乗算の結果を演算するステップとを有することとした。これにより、演算回数を削減し、べき乗算の高速化を図ることができる。【００１８】
また、本発明のスカラー倍算の演算方法では、標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数２３】
2009020216.tif 000010
任意の有理点Ａは次式を満たし、
【数２４】
2009020216.tif 000011
スカラー部[ｎ]をψ進数展開した
【数２５】
2009020216.tif 000012
と表されるスカラー倍算において、前記指数部ｉの写像ψの所定次数の項と、この項の次数よりも１次だけ高次の項または１次以上の高次の項の複数の項とを１組として、前記写像Ｆを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定するステップと、この係数をψ進数表示として、前記係数による元Ａの加算が行われる場合の各組でのψ進数表示の同一の桁に値が存在しているか否か示す指標を有するテンポラリデータを桁ごとに設定するステップと、前記各係数を構成するψ進数の各[ｎｉ]Ａを、このテンポラリデータどうしを加算した結果により特定するステップと、を有することとした。これにより、加算回数を減少させ、スカラー倍算の演算速度の高速化を図ることができる。【００１９】
また、本発明の演算方法では、複数の異なる元Ｙを有し、夫々の前記元Ｙは、複数の異なる元Ｘが演算子により結合される組により表される場合に、前記夫々の元Ｙを電子計算機により演算する演算方法において、前記各元Ｘを設定して、前記各元Ｙに前記元Ｘを関連付けるステップと、前記各元Ｙが同一の元Ｘを有しているか否かを示す指標となるテンポラリデータを前記元Ｘごとに設定し、前記各元Ｙを前記演算子により結合される前記テンポラリデータにより表すステップと、前記各元Ｙに含まれるテンポラリデータにおいて、複数の元Ｙにおいて共通するテンポラリデータの組み合わせがある場合に、その共通するテンポラリデータを結合して新たなテンポラリデータを設定するステップと、前記新たなテンポラリデータを用いて前記各組からなる各元Ｙを演算するステップと、を有することとした。これにより、演算速度の向上を図ることができる。【００２０】
また、本発明の演算方法では、前記共通するテンポラリデータを結合して新たなテンポラリデータを設定するステップにおいて、前記複数の元Ｙを複数のグループに分割し、前記分割されたグループごとに共通するテンポラリデータを結合して新たなテンポラリデータを設定することとした。【００２１】
また、本発明の演算方法では、標数ｐ、拡大次数ｍの拡大体Ｆｐmの元Ａのべき乗算Ａnを、指数部ｎのｐ進数表現である
【数２６】
2009020216.tif 000013
を用いて、フロベニウス写像により
【数２７】
2009020216.tif 000014
と表されるべき乗算において、
前記演算子は乗算であり、前記複数の元Ｙは、前記元Ａのｐ進数表現における各係数ｎｉにより定められるべき乗の形式Ａni（注：ＡniはＡの指数ｎｉによるべき乗を意味する。）により与えられ、前記複数の元Ｘは、前記元Ａのべき乗であるＡ,Ａ2,...,Ａ2u（注：Ａ2uはＡの指数２ｕによるべき乗を意味する。）,u=Flr(log2(max(ni)))及びそれらのフロベニウス写像から選ばれることとした。【００２２】
また、本発明の演算方法では、標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数２８】
2009020216.tif 000015
任意の有理点Ａは次式を満たし、
【数２９】
2009020216.tif 000016
係数部[ｎｉ]Ａとする写像ψをψ進展開した
【数３０】
2009020216.tif 000017
と表されるスカラー倍算において、
前記演算子は加算であり、前記複数の元Ｙは、前記ψｉ項の係数[ｎｉ]により定められるスカラー倍の形式[ｎｉ]Ａ及びそれらのψ写像により与えられ、前記複数の元Ｘは、Ａのスカラー倍であるＡ,[2]Ａ,...,[2u]Ａ,u=Flr(log2(max(ni)))及びそれらのψ写像から選ばれることとした。【００２３】
また、本発明のべき乗算の演算装置では、標数ｐ、拡大次数ｍの拡大体Fpmの元Ａのべき乗算Anを、指数部ｎのｐ進数表現である
【数３１】
2009020216.tif 000018
を用いて、フロベニウス写像により
【数３２】
2009020216.tif 000019
と表されるべき乗算の演算装置において、前記指数部ｎのｐの所定次数の項と、この項の次数よりも一次だけ高次の項または一次以上高次の複数の項とを１組として、前記指数部ｎを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、この係数をｐ進数表示として前記係数による元Ａのべき乗算が行われた場合の各組での同一の桁に値が存在しているか否かを示す指標を有するテンポラリデータを桁ごとに設定して、このテンポラリデータで値が存在しているとされた桁における乗数を用いて特定したテンポラリデータの値を記憶する記憶部と、所定の前記テンポラリデータどうしを乗算した結果を、各組の前記係数でのべき乗算の結果として記憶する記憶部とを備えることとした。このように構成することによりべき乗算の演算を高速に行うことができる。【００２４】
また、本発明のべき乗算の演算装置では、所定の前記テンポラリデータどうしを乗算して、各組の前記係数でのべき乗算の結果を演算する際に、共通して乗算するテンポラリデータの組み合わせを特定し、このテンポラリデータの組み合わせを用いて、各組の前記係数でのべき乗算の結果を演算して記憶する記憶部を備えることとした。【００２５】
また、本発明のスカラー倍算の演算装置では、標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数３３】
2009020216.tif 000020
任意の有理点Ａは次式を満たし、
【数３４】
2009020216.tif 000021
スカラー部[ｎ]をψ進数展開した
【数３５】
2009020216.tif 000022
と表されるスカラー倍算を行う演算装置において、前記指数部ｉの写像ψの所定次数の項と、この項の次数よりも１次だけ高次の項または１次以上の高次の項の複数の項とを１組として、前記写像Ｆを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、この係数をψ進数表示として、前記係数による元Ａの加算が行われる場合の各組でのψ進数表示の同一の桁に値が存在しているか否か示す指標を有するテンポラリデータを桁ごとに設定し、前記各係数を構成するψ進数の各[ｎｉ]Ａを、このテンポラリデータどうしを加算した結果により特定することとした。このように構成することによりスカラー倍算の演算を高速に行うことができる。
【発明の効果】
【００２６】
本発明では、所定次数の項と、この項の次数よりも一次だけ高次の項または一次以上高次の複数の項とを１組として複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、この係数をｐ進数表示として係数による元Ａの演算が行われた場合の各組での同一の桁に値が存在しているか否かを示す指標を有するテンポラリデータを桁ごとに設定して、演算を高速に行うことができる。
【図面の簡単な説明】
【００２７】
【図１】テンポラリデータの説明図である。
【図２】べき乗算の演算プログラムのフローチャートである。
【図３】べき乗算の演算装置のブロック図である。
【図４】他のべき乗算の演算プログラム（段階０の処理）のフローチャートである。
【図５】他のべき乗算の演算プログラム（段階１から段階（Ｈ−１）の処理）のフローチャートである。
【図６】他のべき乗算の演算プログラム（段階Ｈの処理）のフローチャートである。
【図７】計算イメージを表すイメージ図である。
【図８】スカラー倍算の演算プログラムのフローチャートである。
【符号の説明】
【００２８】
10  半導体基板
20  演算部
30  記憶部
40  入出力部
50  データバス
【発明を実施するための最良の形態】
【００２９】
以下の説明において、Floor記号
【数３６】
2009020216.tif 000023
やCeiling記号
【数３７】
2009020216.tif 000024
は、説明の便宜上、
【数３８】
2009020216.tif 000025
として表記することにする。【００３０】
＜べき乗算の実施形態１＞【００３１】
本発明のべき乗算の演算方法及びべき乗算の演算装置では、同じ乗算が必要となる部分を効率よく抽出してテンポラリデータとし、このテンポラリデータの値を別途の乗算によって求めることにより、必要となる乗算回数を大きく削減するものである。【００３２】
特に、標数ｐ、拡大次数ｍの拡大体Ｆｐmの元Ａのべき乗算Anを指数部ｎのｐ進数表現である
【数３９】
2009020216.tif 000026
を用いて、フロベニウス写像により
【数４０】
2009020216.tif 000027
と表されるべき乗算を行うものである。【００３３】
説明の便宜上、ｓ＝Flr(logpn)＝５、Flr(log2(p-1))＝４とする。また、Ａのni乗をA[i]で表すこととする。【００３４】
この場合、指数部ｎを展開して表記すると以下のようになる。
ｎ＝n5p5＋n4p4＋n3p3＋n2p2＋n1p＋n0【００３５】
この指数部ｎに対してｐの偶数次ごとにくくることにより、指数部ｎを以下のように表記することができる。
ｎ＝(n5p＋n4)p4＋(n3p＋n2)p2＋(n1p＋n0)
すなわち、ここでは、ｐの４次と４次より一次だけ高次の５次とを１組とし、ｐの２次と２次より一次だけ高次の３次とを１組とし、残りのｐの０次と０次より一次だけ高次の１次とを１組とした３組に分割している。説明の便宜上、ｐの０次と１次とからなる組を第０組、ｐの２次と３次とからなる組を第１組、ｐの４次と５次とからなる組を第２組と呼ぶこととする。【００３６】
ここで、
r0＝n1p＋n0
r1＝n3p＋n2
r2＝n5p＋n4
とすると、指数部ｎを以下のように表記することができる。
ｎ＝r2p4＋r1p2＋r0
説明の便宜上、r0を第０係数、r1を第１係数、r2を第２係数と呼ぶこととする。【００３７】
したがって、元Ａのべき乗算Anは第０係数r0、第１係数r1、第２係数r2を用いて以下のように表記できる。
【数４１】
2009020216.tif 000028
【００３８】
一方、説明の便宜上、ｐの各次の係数n0,n1,n2,n3,n4,n5を２進数表現で以下の値とする。
n0＝(１１１０)2
n1＝(１００１)2
n2＝(１１１０)2
n3＝(１１０１)2
n4＝(０１０１)2
n5＝(１１１１)2【００３９】
この場合、以下のとおりとなる。
A[0]＝A8A4A2
A[1]＝A8A1
A[2]＝A8A4A2
A[3]＝A8A4A1
A[4]＝A4A1
A[5]＝A8A4A2A1【００４０】
すなわち、以下のように表記できることとなる。
【数４２】
2009020216.tif 000029
【００４１】
本発明では、これを演算するのではなく、図１に示すように、新たなテンポラリデータを導入するものである。すなわち、それぞれ２進数表示とした第０係数r0、第１係数r1、第２係数r2で元Ａのべき乗算が行われた場合の、各組での同一の桁に値が存在しているか否かを示す指標を有するテンポラリデータCefgを桁ごとに設定する。【００４２】
テンポラリデータを示すCefgにおける下付き文字ｅ，ｆ，ｇのうち、ｅは第２組の指標、ｆは第１組の指標、ｇは第０組の指標である。【００４３】
そして、図１の場合、Ψ1(A8)とΨ1(A1)とA4の桁では第０組と第１組と第２組にそれぞれ値が存在するためにC111とし、Ψ1(A4)の桁では第０組に値がなく、第１組と第２組にそれぞれ値が存在するためにC110とし、Ψ1(A2)とA1の桁では第０組と第１組に値がなく、第２組に値が存在するためにC100とし、A8とA2の桁では第０組と第１組にそれぞれ値が存在して、第２組に値が存在しないためにC011としている。【００４４】
理解しやすいようにまとめると、以下のとおりとなる。
C111←Ψ1(A8)，Ψ1(A1)，A4の桁
C110←Ψ1(A4)の桁
C100←Ψ1(A2)，A1の桁
C011←A8，A2の桁【００４５】
そして、各テンポラリデータの値を以下のとおりとする。
C111＝Ψ1(A8A1)A4
C110＝Ψ1(A4)
C100＝Ψ1(A2)A1
C011＝A8A2【００４６】
また、説明に用いたｐの各次の係数n0,n1,n2,n3,n4,n5の関係上、たまたま値が存在しないテンポラリデータであるその他のテンポラリデータは全て「１」とする。すなわち、以下のとおりである。
C101＝C010＝C001＝１【００４７】
このようなテンポラリデータを導入すると、元Ａの第０係数r0によるべき乗、元Ａの第１係数r1によるべき乗、元Ａの第２係数r2によるべき乗を、これらのテンポラリデータを用いてそれぞれ演算することができる。【００４８】
すなわち、元Ａの第０係数r0によるべき乗は、テンポラリデータCefgにおける第０組の指標ｇが「０」でないテンポラリデータの積となっており、以下のとおりである。
【数４３】
2009020216.tif 000030
【００４９】
また、元Ａの第１係数r1によるべき乗は、テンポラリデータCefgにおける第１組の指標ｆが「０」でないテンポラリデータの積となっており、以下のとおりである。
【数４４】
2009020216.tif 000031
【００５０】
また、元Ａの第２係数r2によるべき乗は、テンポラリデータCefgにおける第２組の指標ｅが「０」でないテンポラリデータの積となっており、以下のとおりである。
【数４５】
2009020216.tif 000032
【００５１】
このように、フロベニウス写像における演算回数が異なる他の次数での桁をも対象としてテンポラリデータとしてコンポーネント化し、しかも、テンポラリデータの乗算結果を、各組における係数でのべき乗算の結果として[数４１]によりべき乗算を演算できることによって、鍵長が大きくなった場合の乗算回数の削減効果をWindow法などと比較して大きくすることができる。そのうえ、フロベニウス写像による演算回数の分だけ乗算回数を削減できる。【００５２】
図１に示すように、ここでは、テンポラリデータの設定を、べき乗算を３行８列の行列と見なすことにより行っているが、３行８列に限定するものではなく、適宜の行数と、適宜の列数の行列として、テンポラリデータを設定してよい。【００５３】
すなわち、行数ｒ及び列数ｃを考えて、指数部ｎを以下のように考えてもよい。
【数４６】
2009020216.tif 000033
【００５４】
この場合、以下の計算により元Ａのべき乗算Anを計算できる。
【数４７】
2009020216.tif 000034
【数４８】
2009020216.tif 000035
【数４９】
2009020216.tif 000036
【数５０】
2009020216.tif 000037
【数５１】
2009020216.tif 000038
【００５５】
＜べき乗算の実施形態２＞【００５６】
したがって、図２に示すフローチャートに基づくプログラムにより、パーソナルコンピュータなどの電子計算機で元Ａのべき乗算Anを演算できる。なお、このプログラムは、一般的には、暗号化または復号における拡大体の乗算プログラム中のべき乗算のサブルーチンプログラムとして用いられることとなる。【００５７】
まず、電子計算機は、指数部ｎが零である場合は（ステップＳ１：YES）、「１」を出力して終了し（ステップＳ２）、指数部ｎが零でない場合には（ステップＳ１：NO）、指数部ｎのｐ進数表現を設定する（ステップＳ３）。なお、ｐ進数表現の設定において必要となる数値はデフォルトで設定しており、必要に応じて変更可能としている。【００５８】
また、電子計算機は、べき乗算における初期条件の設定を行う（ステップＳ４）。すなわち、B[0]＝Ａとしてべき乗算される元を設定し、Flr(log2(p-1))＝ｔとしてｐ進数表現におけるｐのべき乗の各係数を２進数表現にした場合の桁数を設定している。【００５９】
次いで、電子計算機は、１≦ｉ≦ｔでB[i-1]・B[i-1]＝B[i]として自乗算を演算し、０＜ｉ≦2rでC[i]＝１とし、０＜ｉ≦ｒでR[i]＝１としている。【００６０】
次いで、電子計算機は、図１に示すように複数組に分けられたべき乗算を想定して、所定の桁におけるテンポラリデータＣの設定を行う（ステップＳ５）。すなわち、Ｍ＝０とした後、０≦ｉ＜ｒでnijの１桁目が「１」であるか判定し、「１」である場合に、ＭにＭ＋2iを代入している。次いで、電子計算機は、nijのビットシフトを行っている。ここで、「nij＆１」の「＆」は、nijと「１」の論理積を取っていることを意味し、「nij》１」は、nijを１ビット分右にずらすビットシフトを意味しており、例えば、(１０１１)2》１は、(１０１)2である。【００６１】
次いで、電子計算機は、設定したテンポラリデータＣの値を、「C[M]←C[M]・B[k]」及び「C[i]←Ψ1(C[i])」として演算する。【００６２】
次いで、電子計算機は、テンポラリデータＣの値を用いて、各組に分けられたべき乗算の各組での乗算を、「R[i]←R[i]・C[j]」として行う（ステップＳ６）。【００６３】
次いで、電子計算機は、R[r-1]＝Ｄとして、r-2≧ｉ≧０で「Ｄ←Ψc(D)，Ｄ←Ｄ・R[i]」を演算することによりべき乗算Anの値としてＤを得て（ステップＳ７）、このＤを出力している（ステップＳ８）。【００６４】
このようにべき乗算Anを演算することにより、乗算回数を削減して演算速度を向上させることができる。【００６５】
さらに、べき乗算の演算は、演算処理回路として半導体基板上に形成して乗算処理用半導体デバイスとすることもできる。【００６６】
すなわち、図３に示すように、半導体基板１０上に、演算回路からなる演算部２０を形成し、演算に必要となる各種データを記憶するレジスタで構成した記憶部３０を形成し、入出力部４０を介して入力された初期条件を記憶部３０の所要のレジスタで記憶して演算を開始し、演算結果を入出力部４０を介して出力させることもできる。図３中、５０はデータバスである。【００６７】
記憶部３０には、テンポラリデータの値を記憶するレジスタや、所定のテンポラリデータどうしを乗算した結果を記憶するレジスタ等を設けており、これら以外にも適宜のデータを記憶するレジスタを設けている。【００６８】
このように、乗算処理用半導体デバイスとすることにより演算速度の更なる高速化を図ることができる。また、乗算処理用半導体デバイスは、これ自体で１つの半導体デバイスとするのではなく、暗号化及び復号の乗算処理用の半導体デバイスなどの他の半導体デバイスの一部分に組み込んでもよい。【００６９】
＜べき乗算の実施形態３＞【００７０】
次に、本発明の実施形態による他のべき乗算の演算方法及びべき乗算の演算装置について説明する。この実施形態は、前記実施形態に比べて、さらに、必要となる乗算回数を削減するものである。具体的には、標数ｐ、拡大次数ｍの拡大体Ｆｐmの元Ａのべき乗算Anを行うに際し、指数部ｎのｐ進数表現である前記[数３９]を用いて、フロベニウス写像により、前記[数４０]にて表されるべき乗算を行うものである。ここで、指数部ｎは、以下のように展開できるものとする。
ｎ＝n3p3＋n2p2＋n1p＋n0
このとき、An0＝Y0，An1＝Y1，An2＝Y2，An3＝Y3とする。（注:An0はAの指数ｎ０によるべき乗、An1はAの指数ｎ１によるべき乗、An2はAの指数ｎ２によるべき乗、An3はAの指数ｎ３によるべき乗をそれぞれ意味する。）【００７１】
いま、Y0，Y1,・・・，Y＃Y-1という＃Y個の元があり、それぞれは集合｛X0，X1，・・・，X＃X-1｝から適当な数だけ与えられた元の全てを演算子・で結合したものとする。ここでは、集合｛X0，X1，・・・，X＃X-1｝からY0，Y1,・・・，Y＃Y-1の全てを高速に求める。【００７２】
以下、一例として、集合｛X0，X1，・・・，X14｝に対して、次式(1a)〜(1d)に示すY0，Y1,Y2，Y3を求める方法について説明する。通常、Y0，Y1，Y2，Y3を求めるには、２６回の乗算が必要となる。これに対し、この実施形態では、乗算回数を、後述するように１８回に削減することができる。【００７３】
【数５２】
2009020216.tif 000039
【００７４】
式(1c)(1d)では、Y2,Y3を求めるにあたって、X0という同じ元を結合している。同様に、Y0，Y1，Y2，Y3の全てを求めるにあたって、同じ元を結合する場合が存在する。そこで、テンポラリデータであるコンポーネントC0001，・・・，C1111を次式(2a)〜(2e)のように定義することにより、Y0，Y1，Y2，Y3は、式(3a)〜(3d)のように求めることができる。ただし、コンポーネントの添字は、下位より順に、Y0，Y1，Y2，Y3を求めるのに必要ならば１、必要でなければ０となっている。【００７５】
【数５３】
2009020216.tif 000040
【００７６】
【数５４】
2009020216.tif 000041
【００７７】
式(3a)(3b)では、Y0，Y1を求めるにあたって、C0011・C0111・C1011・C1111という同じ結合が生じている。このC0011・C0111・C1011・C1111は、Y0，Y1を求めるにあたって、共通して乗算するコンポーネントの組み合わせとなる。他にも同様に、Y2，Y3を求めるにあたって、C1100・C1101・C1110・C1111という同じ結合が生じている。同様に、このC1100・C1101・C1110・C1111は、Y2，Y3を求めるにあたって、共通して乗算するコンポーネントの組み合わせとなる。そこで、コンポーネントの結合を表１に示すように行うことにより、Y0，Y1，Y2，Y3の全てを求めることができる。ただし、＊は、０，１共にマッチする特殊文字とする。【００７８】
【表１】
2009020216.tif 000042
【００７９】
また、式(3a)〜式(3d)で１となっているコンポーネントC0010,C0110,C0111,C1001は結合する必要がない。したがって、実際のコンポーネントの結合は、表２に示すようになる。【００８０】
【表２】
2009020216.tif 000043
【００８１】
以上のように、Y0，Y1，Y2，Y3を求めることにより、乗算回数を２６回から１８回に削減することができる。つまり、本発明の実施形態による他のべき乗算の演算方法及びべき乗算の演算装置によれば、必要となる乗算回数をさらに削減することができる。【００８２】
＜べき乗算の実施形態４＞【００８３】
次に、一般式を用いて説明する。log2(＃Y)が整数(＃Y＝2y，(y：整数))となる場合に、Y0，Y1,・・・，Y＃Y-1は、集合｛X0，X1，・・・，X＃X-1｝及び演算子・から、コンポーネントの結合を表３に示すように各段階に分けて行うことにより、組織的に求めることができる。だたし、Ｈ＝log2(＃X)とする。【００８４】
【表３】
2009020216.tif 000044
【００８５】
表３の段階１において、2＃Y−1＞＃Xの場合は、2＃Y−1個のコンポーネントを作成する必要はなく、＃X個だけを作成すればよい。また、段階０では必要なコンポーネントだけを作成するため、段階１から段階Ｈまでのコンポーネントの結合に要する乗算回数を削減することができる。しかし、＃Xに対して＃Yが大き過ぎる場合、必要なコンポーネントの添字の傾向が分散するため、初期の段階ではほとんど結合が行われず、無駄な処理が増加してしまう。【００８６】
この問題を解決するため、＃Y＝G・E  （log2(G)，log2(E)：整数)として、式(4)のようにグループ分けする。このときのコンポーネントの結合を表４に示す。ただし、Ｈ＝log2(E)とする。【００８７】
【数５５】
2009020216.tif 000045
【００８８】
【表４】
2009020216.tif 000046
【００８９】
＜べき乗算の実施形態５＞【００９０】
したがって、後述するフローチャートに基づくプログラムにより、パーソナルコンピュータなどの電子計算機でべき乗算を演算できる。なお、このプログラムは、一般的には、暗号化または復号における拡大体の乗算プログラム中のべき乗算のサブルーチンプログラムとして用いられることとなる。以下、底の等しい＃Y個のべき乗算のアルゴリズムについて説明する。【００９１】
ここで、等しい底をAとすると、Y0，Y1,・・・，YG・E-1は、
【数５６】
2009020216.tif 000047
となり、X0，X1，・・・，X＃X-1は、A，A2，・・・，A2#X-1（注：A2#X-1はＡの指数2#Ｘ-1によるべき乗を意味する。）となる。ただし、＃X＝Flr(log2(max(ni)))＋1となる。【００９２】
まず、べき乗算の演算プログラムについて、段階０の処理を説明する。図４は、他のべき乗算の演算プログラムのフローチャートであり、表４に示した段階０の処理を示している。図４を参照して、まず、電子計算機は、べき乗算における初期条件の設定を行う（ステップＳ１１）。このステップは準備ステップであり、具体的には、Aから、
【数５７】
2009020216.tif 000048
を準備する。【００９３】
以下の説明において、配列Ｃa,b,cは、コンポーネントを格納するためのバッファとして用いられ、添字であるａは段階番号、ｂはグループ番号、ｃはバッファ番号をそれぞれ示している。また、配列ＩＤは、配列Ｃに値を格納したコンポーネントの添字（ＩＤ）を格納するためのバッファとして用いられる。そのため、Ｃの配列インデックスとＩＤの配列インデックスとは対応している。添字については、配列Ｃと同様である。また、変数Ｓは、配列Ｃに格納されているコンポーネントの総数（配列Ｃのサイズ）をカウントするために用いられる。添字については、配列Ｃと同様である。【００９４】
次いで、電子計算機は、グループ毎の処理（後述するステップＳ１３〜ステップＳ１６）を行うため（ステップＳ１２）、その処理に伴って、段階０及びグループｇで用いるバッファであるＳの初期化を行う（ステップＳ１３）。【００９５】
次いで、電子計算機は、ステップＳ１１の準備ステップにより求めたX0，X1，・・・，X#X-1についての処理を順次行うため（ステップＳ１４）、Xxを結合するコンポーネントのＩＤ（ＮＩＤ：Ｎｅｗ  ＩＤ）を求める（ステップＳ１５）。【００９６】
次いで、電子計算機は、ステップＳ１５において求めたＩＤ（ＮＩＤ）に対応するコンポーネントにXxを結合する（ステップＳ１６）。ただし、ＩＤが０である場合、コンポーネントを生成する必要がないため、処理をスキップする（ステップＳ１６の付番１０）。具体的には、ＮＩＤと同じＩＤをもつコンポーネントが既にバッファに格納されているかどうかを探索し（ステップＳ１６の付番１１〜付番１６のループ）、そのコンポーネントがバッファに格納されている場合（ステップＳ１６の付番１２）、そのＩＤのコンポーネントにXxを結合する（ステップＳ１６の付番１３）。これに対し、そのコンポーネントがバッファに格納されていない場合、バッファのサイズを拡張し（ステップＳ１６の付番１９）、Xxの値を入力した新しいコンポーネント（C0,g,0［S0,g,0］）を作成し（ステップＳ１６の付番１７）、それをバッファに入力する（ステップＳ１６の付番１８）。【００９７】
次に、べき乗算の演算プログラムについて、段階１から段階（Ｈ−１）までの処理を説明する。図５は、他のべき乗算の演算プログラムのフローチャートであり、表４に示した段階１から段階（Ｈ−１）の処理を示している。以下の説明において、変数Ｂは、段階ｇのグループ毎のバッファの総数を保持するために用いられる。また、変数Ｌは、以下に示すように、段階ｇにおけるコンポーネントのＩＤの長さ（＊を除く）を保持するために用いられる。
【数５８】
2009020216.tif 000049
【００９８】
また、変数Ｔは、コンポーネントのＩＤを参照するために用いられる。段階１から最終段階Ｈでは、各段階でのコンポーネントの作成に前段階におけるコンポーネントのＩＤを参照する必要がある。例えば、段階０でC01101110というコンポーネントを作成したとすると、段階１ではC01101110のＩＤを以下に示すように参照することができるため、C****1110を作成する必要がある。
【数５９】
2009020216.tif 000050
さらに、参照位置をＬビットずらして、以下に示すようにＩＤを参照することができるため、C0110****も作成する必要がある。
【数６０】
2009020216.tif 000051
変数Ｔは、このようなＩＤの参照を行うために用いられる。【００９９】
図５を参照して、まず、電子計算機は、Ｂ及びＬの値の初期化を行う（ステップＳ２１）。そして、段階１から段階（Ｈ−１）までの段階毎の処理（後述するステップＳ２３〜ステップＳ２６）を行うため（ステップＳ２２）、その処理に伴ってＢ及びＬの値を更新する（ステップＳ２３）。【０１００】
次いで、電子計算機は、グループ毎の処理（後述するステップＳ２５，ステップＳ２６）を行うため（ステップＳ２４）、その処理に伴って、ＩＤの下位Ｌビットを参照できるようにＴを初期化し（ステップＳ２５）、段階Ｈの各グループ及び各バッファの処理を行う。【０１０１】
また、電子計算機は、ステップ２５において初期化したＴに対し、各バッファの処理（ステップＳ２６の付番７〜付番２３のループ）を行うにあたって、ＩＤの参照位置をＬビットずつずらすために、Ｔの値を更新する（ステップＳ２６の付番２２）。また、段階ｈ、グループｇ、バッファｂにおけるバッファであるＳの初期化を行う（ステップＳ２６の付番８）。また、Ch,g,bを作成するために必要な前段階の全てのコンポーネントを逐次処理する（ステップＳ２６の付番９〜付番２１）。また、Ｔを用いて前段階のコンポーネントのＩＤを参照する（ステップＳ２６の付番１０）。【０１０２】
また、電子計算機は、ステップＳ２６の付番１０において参照したＩＤ（ＮＩＤ）に対応するコンポーネントに結合または入力する（ステップＳ２６の付番１１〜付番２０）。ただし、ＩＤが０である場合、コンポーネントを生成する必要がないため、処理をスキップする（ステップＳ２６の付番１１）。【０１０３】
また、電子計算機は、ステップＳ２６の付番１０〜付番１５のように、ＩＤ（ＮＩＤ）と同じＩＤのコンポーネントが既にバッファに格納されているかどうかを探索する（ステップＳ２６の付番１２〜付番１７のループ）。そのコンポーネントがバッファに格納されている場合（ステップＳ２６の付番１３）、そのＩＤのコンポーネントに前段階のコンポーネントを結合する（ステップＳ２６の付番１４）。これに対し、そのコンポーネントがバッファに格納されていない場合、バッファのサイズを拡張し（ステップＳ２６の付番２０）、Xxの値を入力した新しいコンポーネント（Ch,g,b［Sh,g,b］）を作成し（ステップＳ２６の付番１８）、それをバッファに入力する（ステップＳ２６の付番１９）。【０１０４】
次に、べき乗算の演算プログラムについて、段階Ｈの処理を説明する。図６は、他のべき乗算の演算プログラムのフローチャートであり、表４に示した段階Ｈの処理を示している。電子計算機は、グループ毎の処理（後述するステップＳ３２〜ステップＳ３５）を行うため（ステップＳ３１）、その処理に伴って、Ｔに１を設定する（ステップＳ３２）。【０１０５】
次いで、電子計算機は、各出力の処理（後述するステップＳ３４，ステップＳ３５）を行うため（ステップＳ３３）、フラグｆｌａｇに１を設定する（ステップＳ３４）。最終段階である段階Ｐでは、前段階(Ｈ−１)におけるコンポーネントのＩＤを１ビット参照すればよいので、ステップＳ３２においてＴに１を設定している。また、各バッファの処理（ステップＳ３３〜ステップＳ３５の付番３〜付番１３のループ）を行うにあたって、ＩＤの参照位置を１ビットずつずらすために、Ｔの値を更新している（ステップＳ３５の付番１２）。【０１０６】
最終段階Ｈより前の段階では、入力または結合が行われないコンポーネントは無視することができる。しかし、最終段階Ｈでは、出力Yに値を入力しなければならない。そこで、このアルゴリズムでは出力Yg・E+eに段階（Ｈ−１）のコンポーネントを入力または結合されたかどうかを判別するために、フラグとして変数ｆｌａｇを用いている。ステップＳ３４においてフラグｆｌａｇを初期化し、出力Yg・E+eに入力または結合すべき段階（Ｈ−１）のコンポーネントを探索し（ステップＳ３５の付番５〜付番１０のループ）、そのコンポーネントが存在する場合、コンポーネントの値を出力Yg・E+eに結合し（ステップＳ３５の付番７）、または、コンポーネントの値を入力してフラグｆｌａｇの値を変更する（ステップＳ３５の付番８）。これに対し、そのコンポーネントが存在しない場合（ｆｌａｇの値が初期値である場合）、出力Yg・E+eに１を入力する（ステップＳ３５の付番１１）。【０１０７】
このようにべき乗算を演算することにより、乗算回数を削減して演算速度を向上させることができる。【０１０８】
さらに、この実施形態によるべき乗算の演算は、図３に示したように、演算処理回路として半導体基板上に形成して乗算処理用半導体デバイスとすることもできる。【０１０９】
＜スカラー倍算＞【０１１０】
次に、本発明の実施形態に係るスカラー倍算の演算方法及びスカラー倍算の演算装置について説明する。楕円曲線暗号では、同じ要素を複数回足し合わせるというスカラー倍算なるものを多用する。しかし、スカラー倍算は１回当り２５０ビット級の大きな数値分加算を行うため、普通に加算してはあまりにコストがかかってしまう。本発明では、このスカラー倍算を高速化するアルゴリズムを開示する。以下、楕円加算、スカラー倍算、バイナリ法、楕円曲線上の有理点のフロベニウス写像、有理点が満たす性質を説明し、本発明の実施形態について詳細に説明する。【０１１１】
（楕円加算）
まず、高速なスカラー倍算アルゴリズムについて説明する。一般に有限体Ｆｐ（標数ｐの体）上の楕円曲線は式(5)で定義される。
【数６１】
2009020216.tif 000052
ａ，ｂが属する体Ｆｐを係数体、変数ｘ，ｙが属する体Ｆｐｍを定義体と呼ぶこととし、Ｅ／Ｆｐは係数体がＦｐである楕円曲線を、Ｅ（Ｆｐｍ）は定義体がＦｐｍ（Ｆｐのｍ次拡大体）である楕円曲線をそれぞれ意味することにする。【０１１２】
式（５）を満たす（ｘ，ｙ）の組すべてと無限遠点Ｏを合わせて、楕円曲線Ｅ（ｘ，ｙ）上の有理点といい、有理点Ｐ（ｘ1，ｙ1）とＱ（ｘ2，ｙ2）において、次のような演算を定義する。この演算によって有理点Ｒ（ｘ３，ｙ３）を生成する方法を楕円加算と呼ぶ。
【数６２】
2009020216.tif 000053
このとき、整数の加法でいう“０”のような、任意の有理点Ｐと楕円加算しても結果がＰとなる有理点を無限遠点Ｏとする。すなわち、Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐである。有理点Ｐにおいてｘ軸対称な有理点−Ｐと楕円加算を行うと、無限遠点Ｏになる。この−ＰをＰの逆元という。以下、式(5)の楕円曲線を例にして述べる。【０１１３】
（スカラー倍算）
スカラー倍算とは、同じ有理点を複数回、楕円加算によって足し合わせることを言う。例えば[ｎ]Ａはｎ個のＡを足し合わせることを意味する。また、式(5)の曲線における有理点の総数を＃Ｅ（Ｆｐｍ）とすると、任意の有理点Ａは、次の性質をもつ。
【数６３】
2009020216.tif 000054
この性質(巡回性)を巧みに利用したものが楕円曲線暗号である。【０１１４】
（バイナリ法）
バイナリ法は、[ｎ]Ａというスカラー倍算を以下のように効率よく行う手法である。
【表５】
2009020216.tif 000055
バイナリ法は、Flr(log2(n))回の楕円２倍算（自分に自分を１回楕円加算すること）、{Flr(log2(n))+1}/2回の楕円加算を平均で必要とする。なお、》は右へビットシフト演算子で、例えば(１０１１)２》１は(１０１)２である。また、＆は論理積を表し、例えば(１０１１)２＆１は１、(１１０)２＆１は０である。【０１１５】
（Window法）
Window法は、以下のように効率よくスカラー倍算を行う手法である。ここでは、窓サイズ３の場合を説明する。まず、以下のコンポーネントを準備する。
【数６４】
2009020216.tif 000056
これらは、以下の２進数に対応する。
【数６５】
2009020216.tif 000057
これらを用いて、例えば[３１８]Ａというスカラー倍算を次式のように行う。
【数６６】
2009020216.tif 000058
コンポーネントを準備するための計算を除けば、Window法はFlr(log2(n))-w+1回の楕円２倍算と[{Flr(log2(n))+1}/w]{1-(1/2)w}回の楕円加算を平均で必要とする。【０１１６】
（楕円曲線上の有理点のフロベニウス写像）
Ｅ（Ｆｐｍ）の楕円曲線上の有理点Ｐ＝（ｘ，ｙ）のフロベニウス写像は、φ（Ｐ）のように表現し、次のような演算を行う。
【数６７】
2009020216.tif 000059
つまり、Ｐにおけるｘとｙをそれぞれｐ乗するという演算を行う。なお、ｘとｙは有限体Ｆｐｍ（Ｆｐｍのｍ次拡大体で、ｍは１以上の整数）に含まれていて、この場合のｐｋ乗（ただし、ｋは０以上の整数）は、他の整数でべき乗するよりはるかに高速となっている。【０１１７】
（有理点が満たす性質）
楕円曲線Ｅ（Ｆｐｍ）上の任意の有理点Ｐ＝（ｘ，ｙ）は、必ず次式(12)を満たす。
【数６８】
2009020216.tif 000060
このとき、ｔ＝ｐ＋１−＃Ｅ（Ｆｐ）であり、φ２はフロベニウス写像を２回行う、つまり、
【数６９】
2009020216.tif 000061
という演算を意味している。ここで、式(12)を変形して整理すると次のようになる。
【数７０】
2009020216.tif 000062
【０１１８】
つまり、ｐ個のＰを加算（ｐ倍算）することは、Ｐにフロベニウス写像を施してｔ倍算を行ったものに対して、Ｐに２回フロベニウス写像を施したものの逆元を楕円加算することを意味している。また、楕円曲線Ｅ（Ｆｐｍ）上の任意の有理点Ｐは、必ず次の式（１５）を満たす。
【数７１】
2009020216.tif 000063
これは、
【数７２】
2009020216.tif 000064
となることを意味している。【０１１９】
次に、本発明に係るスカラー倍算[ｎ]Ａ（ただし、ＡはＥ（Ｆｐｍ）上の任意の有理点）を行う場合について説明する。【０１２０】
＜スカラー倍算の実施形態１＞【０１２１】
（ψ進展開による演算）
高速に演算可能である自己準同型写像ψを考慮し、式（１６）のようにｎ倍算と同型写像となる、ψ進展開した演算を求める。
【数７３】
2009020216.tif 000065
これを用いて、次式が与えられる。
【数７４】
2009020216.tif 000066
このとき、ψｉ（Ａ）は演算ψをｉ回実行することを意味していて、この演算は高速であるので、実際に必要な計算は[ｎｉ]Ａの部分となる。【０１２２】
具体的な例として、（有理点が満たす性質）の項で紹介した、フロベニウス写像φを用いたφ進展開がある。これは、ｎをp進展開し、
【数７５】
2009020216.tif 000067
となるので、
【数７６】
2009020216.tif 000068
となる。ここで式（１４）の右辺を代入すると、
【数７７】
2009020216.tif 000069
となり、式(18)の右辺におけるサーメーションの括弧内は
【数７８】
2009020216.tif 000070
となる。【０１２３】
このとき、式(19)におけるｉＣｋ・ｔｋ・ｎｉ’がｐより大きい場合、この係数を再びｐ進展開する。すなわち、
【数７９】
2009020216.tif 000071
とすると
【数８０】
2009020216.tif 000072
となる。さらに、φの指数２（ｉ＋ｊ）−（ｋ＋ｌ）がｍより大きくなったとき、式(15)を用いることで、
【数８１】
2009020216.tif 000073
とすることができ(ただし、Ｔ=Flr({2(i+j)-(k+l)}/m))、これによりφの指数をｍ未満に保つ。【０１２４】
以下、これらのようなｐ進展開と式(15)を用いたψの指数部の減少を繰り返して、φｋ（ただし、ｋは０以上ｍ未満）の係数全てがｐ未満となったとき、式(17)において、ψがφとなっている式が準備できる。すなわち、
【数８２】
2009020216.tif 000074
となる。
式(17)において、[ｎｉ]Ａの部分をＡ[ｉ]で表すと、以下のアルゴリズムが与えられる。
【表６】
2009020216.tif 000075
【０１２５】
この手法はｔ回の楕円２倍算、(ｓ＋１)(ｔ＋１)/２の楕円加算、ｓ回の写像ψによる演算、そしてｓ回の楕円加算を必要とする。写像ψによる演算を用いることで楕円２倍算の回数が減じるが、楕円加算の回数は変わらない。この楕円加算の回数を減らすために、以下に示すような計算法を考える。【０１２６】
（スカラー倍算の実施形態１の具体的な説明）
以下、上記アルゴリズム２を改良する。ｓ＝（ｎをψ進展開した際のψの最大係数）及びｔ＝Flr(log2{max(ni)})をそれぞれ５及び４とする。また、ｎ０、ｎ１、・・・、ｎ５の２進数表現を以下のようにし、
ｎ１＝（１００１）２，ｎ０＝（１１１０）２，                (20a)
ｎ３＝（１１０１）２，ｎ２＝（１１１０）２，                (20b)
ｎ５＝（１１１１）２，ｎ４＝（０１０１）２，                (20c)
スカラー倍算の係数ｎを以下のように分割して考える（図７参照）。
【数８３】
2009020216.tif 000076
そして、Ｇ１＝{[ｎ５]Ａ，[ｎ３]Ａ，[ｎ１]Ａ}及びＧ１＝{[ｎ４]Ａ，[ｎ２]Ａ，[ｎ０]Ａ}の２つのグループを考えながら、以下の計算式をみてみる。【０１２７】
[n１]Ａ＝[８]Ａ＋[１]Ａ，            [n０]Ａ＝[８]Ａ＋[４]Ａ＋[２]Ａ，    (22a)
[n３]Ａ＝[８]Ａ＋[４]Ａ＋[１]Ａ，    [n２]Ａ＝[８]Ａ＋[４]Ａ＋[２]Ａ，    (22b)
[n５]Ａ＝[８]Ａ＋[４]Ａ＋[２]Ａ＋[１]Ａ，  [n４]Ａ＝[４]Ａ＋[１]Ａ        (22c)
式(20)及び式(22)にあるように、Ｇ１のうち、[n５]Ａのみにある計算項は[２]Ａであり、Ｇ２のうち、[n４]Ａのみにある計算項は[１]Ａであるので、これらの演算をまとめてＣ１００とすると、Ｃ１００＝ψ（[２]Ａ）＋[１]Ａとなる。同様にＧ１のうち、[n１]Ａと[n３]Ａにある計算項は存在せず、Ｇ２のうち、[n０]Ａと[n２]Ａのみにある計算項は[８]Ａと[２]Ａであるので、これらの演算をまとめてＣ０１１とすると、Ｃ０１１＝[８]Ａ＋[２]Ａとなる。他の組み合わせについても同様にして、Ｃ００１，Ｃ０１０，・・・，Ｃ１１１を次のように考えれば、
【数８４】
2009020216.tif 000077
【０１２８】
[ｎ]Ａを次式のように計算できる。
【数８５】
2009020216.tif 000078
式(22)を用いた式(17)の計算は、３回の楕円２倍算及び１６回の楕円加算を必要とするが、式(23)及び式(24)の計算は、３回の楕円２倍算及び１４回の楕円加算しか必要としない。このように本発明の実施例では楕円加算の回数を減らすことができる。【０１２９】
（アルゴリズム）
次に、本発明に係る実施形態を、より数学的に説明する。図７にあるように、行数ｒ及び列数ｃを考える。このとき、スカラー倍算の係数ｎを以下のように考える。
【数８６】
2009020216.tif 000079
そして本発明の実施形態では、[ｎ]Ａを以下のように計算する。
【数８７】
2009020216.tif 000080
上記「数８７」は上から順に（26a）、(26b)、(26c)、(26d)、(26e)である。【０１３０】
なお、｜Ｓｊｌ｜≦ｔ及び｜Ｔｉ｜≦２ｒ−１である。（実施形態１の具体的な説明）の項での例においてψ＝φの場合は、式(15)のｍが６、ｃ＝２となっているため、ｒ＝Ceil(ｍ／ｃ)＝３であり、必要となるテンポラリ変数Ｃｌ及びＲｉの個数は、式(26)からわかるように７個（＝２ｒ−１）及び３（＝ｒ）となっている。式（26c）における[２ｉ]Ａ,１≦i＜ｔの準備には、３回（＝ｔ−１）の２倍算を必要とし、Ｃｌ，１≦ｌ＜２ｒの準備には、８回（＝ｃ・ｔ）以下の楕円加算を必要とする。ここで、ｔ＝４＝Flr(log2(max(ｎｉ))である。これらテンポラリデータを用いて、式（26c）、式(26d)及び式(26e)に示されるように、[ｎ]Ａは２３回（＝ｒ（２ｒ−１）＋（ｒ−１））以下の楕円加算で求められる。加えて、９回（＝（ｃ−１）（２ｒ−１）＋（ｒ−１））の写像Ｆによる演算を必要とする。【０１３１】
＜スカラー倍算の実施形態２＞【０１３２】
図８は、本発明の実施形態に係るスカラー倍算の演算プログラムのフローチャートであり、式(25)から式(26e)の演算を行う。電子計算機は、スカラー倍算の係数ｎが０のときは（ステップＳ４１のＹ）、無限遠点Ｏを出力し（ステップＳ４２）、終了する。スカラー倍算の係数ｎが０でないときは（ステップＳ４１のＮ）、式(25)で表される係数ｎのψ進展開の演算を実行する（ステップＳ４３）。【０１３３】
以下、ステップＳ４３に示す式(25)により表されるｎのψ進展開を求める。電子計算機は、Ｂ[0]に有理点Ａを設定し、ψiの係数の最大値Flr(log２(max(ｎｉ))により２進数表現の最大桁数をｔに設定する。有理点Ａの倍数をＢ[ｉ]に設定し、Ｃ[ｉ]とＲ[ｉ]の初期値を無限遠点Ｏに設定する（ステップＳ４４）。【０１３４】
電子計算機は、ステップＳ４５の付番８〜２２においてテンポラリデータＣを求める。電子計算機は、まず、Ｍ＝０に設定し（ステップＳ４５の付番１０）、係数ｎｉｊの論理積ｎｉｊ＆１が１であるか判定し、１である場合に、Ｍに２ｉを加算する（ステップＳ４５の付番１２）。次いで電子計算機は、係数ｎｉｊのビットをｎｉｊ》１により１ビット分右にずらすビットシフトを行う（ステップＳ４５の付番１３）。電子計算機は、以上の演算をｉ＝０〜ｒまで繰り返す（ステップＳ４５の付番１１〜付番１４）。【０１３５】
次いで、電子計算機は、Ｍが０であるか判定し、０でない場合にテンポラリデータＣ[Ｍ]にＢ[ｋ]を加算する演算を実行する（ステップＳ４５の付番１５）。電子計算機は、以上の演算をｋ＝０〜ｔ繰り返して実行する（ステップＳ４５の付番９〜付番１６）。次いで電子計算機は、ｊが０であるかを判定し（ステップＳ４５の付番１７）、ｊが０でない場合に、ψ（Ｃ[ｋ]）をテンポラリデータＣ[ｋ]に代入する演算を、ｋ＝１〜２ｒで繰り返す（ステップＳ４５の付番１８〜付番２０）。電子計算機は、以上の演算をｊ＝ｃ−１〜０まで繰り返して実行する（ステップＳ４５の付番８〜付番２２）。【０１３６】
次いで、電子計算機は、論理積２ｉ＆ｊが０であるか判定し、０でない場合に、Ｒ[ｉ］にＣ[ｊ]を加算する演算を実行する（ステップＳ４６の付番２５）。電子計算機は、この演算をｊ＝１〜２ｒまで繰り返して実行する（ステップＳ４６の付番２４〜付番２６）。次いで、以上の演算をｉ＝０〜ｒで繰り返す（ステップＳ４６の付番２３〜付番２７）。【０１３７】
次いで、電子計算機はＲ[ｒ−１]をＤとし（ステップＳ４７の付番２８）、電子計算機は、ψｃ（Ｄ）をＤに置き換え、ＤにＲ[ｉ]を加算し（ステップＳ４７の付番３０）、この演算をｉ＝ｒ−２〜０まで繰り返す（ステップＳ４７の付番２９〜付番３１）。次いで、電子計算機は、Ｄを出力して（ステップＳ４８の付番３２）終了する。【０１３８】
このように、スカラー倍算処理用半導体デバイスとすることにより演算速度の更なる高速化を図ることができる。また、スカラー倍算処理用半導体デバイスは、これ自体で１つの半導体デバイスとするのではなく、暗号化及び復号化処理用の半導体デバイスなどの他の半導体デバイスの一部分に組み込んでもよい。【０１３９】
なお、以上の説明から明らかに、＜スカラー倍算の実施形態１＞において説明したスカラー倍算の演算方法は、＜べき乗算の実施形態１＞において説明したべき乗算の演算方法に類似している。すなわち、スカラー倍算においてはテンポラリデータが加算＋の演算子により結合される。べき乗演算においてはテンポラリデータが乗算・の演算子により結合されている。テンポラリデータの演算方法は、演算子が異なるだけで、図２及び図８に示すように、べき乗演算もスカラー倍算も計算方法は同様となる。【０１４０】
また、＜べき乗の実施形態３＞の項において、Y0，Y1,・・・，Yn(Y)-1というn(Y)個の元Ｙと、それぞれが集合｛X0，X1，・・・，Xn(X)-1｝から適当な数だけ与えられたn(x)個の元Ｘの全てを演算子・で結合するものとして、各元Ｙを、演算子・により結合されたテンポラリデータにより表した。そして、各元Ｙに含まれるテンポラリデータにおいて、複数の元Ｙにおいて共通するテンポラリデータの組み合わせがある場合に、その共通するテンポラリデータを結合して新たなテンポラリデータを設定し、この新たなテンポラリデータを用いて演算する方法について説明した。【０１４１】
このテンポラリデータの演算は、演算子を乗算・から加算＋に置き換えることにより、そのままスカラー倍算にも適用することができる。すなわち、スカラー倍算におけるＦｉ項の係数[ｎｉ]Ａを元Ｙとし、スカラー倍算における自己準同型写像の展開項であるψ０([ｎｉ]Ａ)、ψ１([ｎ１]Ａ)、・・・、ψＳ([ｎＳ]Ａ)を元Ｘとすればよい。従って、スカラー倍算は、＜べき乗の実施形態４＞、＜べき乗の実施形態５＞及び＜べき乗の実施形態６＞の各項において説明した演算方法に、演算子を乗算・から加算＋に置き換えることにより、適用することができる。【０１４２】
また、図２、図４、図５、図６及び図８のフローチャートは、図３の半導体基板１０上に形成した電子計算機により実行されるものである。演算部２０は、記憶部３０に格納されたプログラムを読み出して、当該プログラムに従って演算処理を実行する。演算部２０は、例えば初期設定の際には、入出力部４０から入力したデータ、或いは記憶部３０の所定領域に格納されたデータを読み出して演算を実行し、演算結果を変数に対応する記憶部３０の所定記憶領域に格納する。演算部２０は、プログラムに従って、乗算処理、加算処理、「for」や「if」で表される演算処理等を実行し、記憶部３０の変数に対応する所定の記憶領域に、或いは出力データとしてその演算結果を格納する。演算部２０は、記憶部３０の所定領域に格納された演算結果を読み出して、入出力部４０に送信して処理結果を出力するものである。
【産業上の利用可能性】
【０１４３】
本発明の演算方法及び演算装置は、例えばべき乗算やスカラー倍算を高速で演算可能であり、平文データの暗号化及び復号化の用途に適用することができる。
【図１】
2009020216.tif 000096
【図２】
2009020216.tif 000097
【図３】
2009020216.tif 000098
【図４】
2009020216.tif 000099
【図５】
2009020216.tif 000100
【図６】
2009020216.tif 000101
【図７】
2009020216.tif 000102
【図８】
2009020216.tif 000103
【手続補正書】
【提出日】平成21年6月3日(2009.6.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
標数ｐ、拡大次数ｍの拡大体Ｆｐｍの元Ａのべき乗算Ａｎを、指数部ｎのｐ進数表現である
【数１】
2009020216.tif 000104
を用いて、フロベニウス写像により
【数２】
2009020216.tif 000105
と表されるべき乗算を、演算回路からなる演算部及び各種データを記憶するレジスタで構成した記憶部を備える電子計算機により演算する演算方法において、
前記演算部が、
前記指数部ｎのｐの所定次数の項と、この項の次数よりも一次だけ高次の項または一次以上高次の複数の項とを１組として、前記指数部ｎを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、この係数をｐ進数表示として前記係数による元Ａのべき乗算が行われた場合の各組での同一の桁に値が存在しているか否かを示す指標を有するテンポラリデータを桁ごとに設定してその記憶領域を前記記憶部に確保するステップと、
前記テンポラリデータの値を、このテンポラリデータで値が存在しているとされた桁における乗数を用いて特定し、前記記憶部に記憶するステップと、
所定の前記テンポラリデータどうしを乗算した結果を、各組の前記係数でのべき乗算の結果として前記記憶部に記憶するステップと
を有することを特徴とするべき乗算の演算方法。
【請求項２】
請求項１に記載の、べき乗算の演算方法において、前記演算部が、
所定の前記テンポラリデータどうしを乗算して、各組の前記係数でのべき乗算の結果を演算する際に、共通して乗算するテンポラリデータの組み合わせを特定するステップと、
前記テンポラリデータの組み合わせを用いて、各組の前記係数でのべき乗算の結果を演算するステップと
を有することを特徴とするべき乗算の演算方法。
【請求項３】
標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数３】
2009020216.tif 000106
任意の有理点Ａは次式を満たし、
【数４】
2009020216.tif 000107
スカラー部［ｎ］をψ進数展開した
【数５】
2009020216.tif 000108
と表されるスカラー倍算を、演算回路からなる演算部及び各種データを記憶するレジスタで構成した記憶部を備える電子計算機により演算する演算方法において、
前記演算部が、
前記指数部ｉの写像ψの所定次数の項と、この項の次数よりも１次だけ高次の項または１次以上の高次の項の複数の項とを１組として、前記写像Ｆを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定するステップと、
この係数をψ進数表示として、前記係数による元Ａの加算が行われる場合の各組でのψ進数表示の同一の桁に値が存在しているか否か示す指標を有するテンポラリデータを桁ごとに設定してその値を前記記憶部に記憶するステップと、
前記各係数を構成するψ進数の各［ｎｉ］Ａを、このテンポラリデータどうしを加算した結果により特定して前記記憶部に記憶するステップと、を有することを特徴とするスカラー倍算の演算方法。
【請求項４】
複数の異なる元Ｙを有し、夫々の前記元Ｙは、複数の異なる元Ｘが演算子により結合される組により表される場合に、前記夫々の元Ｙを、演算回路からなる演算部及び各種データを記憶するレジスタで構成した記憶部を備える電子計算機により演算する演算方法において、
前記演算部が、
前記各元Ｘを設定して、前記各元Ｙに前記元Ｘを関連付けるステップと、
前記各元Ｙが同一の元Ｘを有しているか否かを示す指標となるテンポラリデータを前記元Ｘごとに設定して前記記憶部に記憶し、前記各元Ｙを前記演算子により結合される前記テンポラリデータにより表すステップと、
前記各元Ｙに含まれるテンポラリデータにおいて、複数の元Ｙにおいて共通するテンポラリデータの組み合わせがある場合に、その共通するテンポラリデータを結合して新たなテンポラリデータを設定して前記記憶部に記憶するステップと、
前記新たなテンポラリデータを用いて前記各組からなる各元Ｙを演算し、その演算結果を前記記憶部に記憶するステップと、を有する演算方法。
【請求項５】
請求項４に記載の演算方法において、
前記共通するテンポラリデータを結合して新たなテンポラリデータを設定するステップにおいて、前記複数の元Ｙを複数のグループに分割し、前記分割されたグループごとに共通するテンポラリデータを結合して新たなテンポラリデータを前記記憶部に設定することを特徴とする演算方法。
【請求項６】
請求項４又は５に記載の演算方法において、
標数ｐ、拡大次数ｍの拡大体Ｆｐｍの元Ａのべき乗算Ａｎを、指数部ｎのｐ進数表現である
【数６】
2009020216.tif 000109
を用いて、フロベニウス写像により
【数７】
2009020216.tif 000110
と表されるべき乗算において、
前記演算子は乗算であり、前記複数の元Ｙは、前記元Ａのｐ進数表現における各係数ｎｉにより定められるべき乗の形式Ａｎｉ（注：ＡｎｉはＡの指数ｎｉによるべき乗を意味する。）により与えられ、前記複数の元Ｘは、前記元Ａのべき乗であるＡ，Ａ２，．．．，Ａ２ｕ（注：Ａ２ｕはＡの指数２ｕによるべき乗を意味する。），ｕ＝Ｆｌｒ（ｌｏｇ２（ｍａｘ（ｎｉ）））及びそれらのフロベニウス写像から選ばれることを特徴とする演算方法。
【請求項７】
請求項４又は５に記載の演算方法において、
標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数８】
2009020216.tif 000111
任意の有理点Ａは次式を満たし、
【数９】
2009020216.tif 000112
係数部［ｎｉ］Ａとする写像ψをψ進展開した
【数１０】
2009020216.tif 000113
と表されるスカラー倍算において、
前記演算子は加算であり、前記複数の元Ｙは、前記ψｉ項の係数［ｎｉ］により定められるスカラー倍の形式［ｎｉ］Ａ及びそれらのψ写像により与えられ、前記複数の元Ｘは、Ａのスカラー倍であるＡ，［２］Ａ，．．．，［２ｕ］Ａ，ｕ＝Ｆｌｒ（ｌｏｇ２（ｍａｘ（ｎｉ）））及びそれらのψ写像から選ばれることを特徴とする演算方法。
【請求項８】
標数ｐ、拡大次数ｍの拡大体Ｆｐｍの元Ａのべき乗算Ａｎを、指数部ｎのｐ進数表現である
【数１１】
2009020216.tif 000114
を用いて、フロベニウス写像により
【数１２】
2009020216.tif 000115
と表されるべき乗算の演算装置において、
前記指数部ｎのｐの所定次数の項と、この項の次数よりも一次だけ高次の項または一次以上高次の複数の項とを１組として、前記指数部ｎを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、この係数をｐ進数表示として前記係数による元Ａのべき乗算が行われた場合の各組での同一の桁に値が存在しているか否かを示す指標を有するテンポラリデータを桁ごとに設定して、このテンポラリデータで値が存在しているとされた桁における乗数を用いて特定したテンポラリデータの値を記憶する記憶部と、
所定の前記テンポラリデータどうしを乗算した結果を、各組の前記係数でのべき乗算の結果として記憶する記憶部と
を備えたことを特徴とするべき乗算の演算装置。
【請求項９】
請求項８に記載の、べき乗算の演算装置において、
所定の前記テンポラリデータどうしを乗算して、各組の前記係数でのべき乗算の結果を演算する際に、共通して乗算するテンポラリデータの組み合わせを特定し、このテンポラリデータの組み合わせを用いて、各組の前記係数でのべき乗算の結果を演算して記憶する記憶部を備えたことを特徴とするべき乗算の演算装置。
【請求項１０】
標数ｐ、有限体Ｆｐの次数ｍの拡大体をＦｐｍ、有理点の総数を＃Ｅ（Ｆｐｍ）、無限遠点をＯ、有限体Ｆｐ上の楕円曲線が次式で表され、
【数１３】
2009020216.tif 000116
任意の有理点Ａは次式を満たし、
【数１４】
2009020216.tif 000117
スカラー部［ｎ］をψ進数展開した
【数１５】
2009020216.tif 000118
と表されるスカラー倍算を行う演算回路からなる演算部及び各種データを記憶するレジスタで構成した記憶部を備える電子計算機により演算する演算装置において、
前記指数部ｉの写像ψの所定次数の項と、この項の次数よりも１次だけ高次の項または１次以上の高次の項の複数の項とを１組として、前記写像Ｆを複数の組に分けるとともに、各組内における各項を最低次数でくくってこの最低次数の係数を特定し、
この係数をψ進数表示として、前記係数による元Ａの加算が行われる場合の各組でのψ進数表示の同一の桁に値が存在しているか否か示す指標を有するテンポラリデータを桁ごとに設定して記憶する前記記憶部と、
前記各係数を構成するψ進数の各［ｎｉ］Ａを、このテンポラリデータどうしを加算した結果により特定して記憶する前記記憶部と、を備えたことを特徴とするスカラー倍算の演算装置。
【国際調査報告】
2009020216.tif 000119
2009020216.tif 000120
2009020216.tif 000121
2009020216.tif 000122
2009020216.tif 000123
2009020216.tif 000124
2009020216.tif 000125