スカラー倍算の演算装置及びべき乗算の演算装置
【課題】高速に演算可能なスカラー倍算あるいはべき乗算の演算装置を提供する。
【解決手段】電子計算機で、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算を行うスカラー倍算の演算装置において、Ｇの有理点Ｑに対し、
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑ
が成り立つことにより、スカラーｎをｔ-１進展開して、ｔ-１に換えて有理点に対するフロベニウス自己準同型写像φqを用いる。また、電子計算機で、非負整数ｎに対するＨの元Ａのｎ乗算を行うべき乗算の演算装置において、ｑとｒの差分をｓ＝ｑ−ｒとし、Ｈの非零元Ａに対し、
φq(Ａ)＝Ａq＝Ａs
が成り立つことにより、べき数ｎをｓ進展開して、ｓに換えて元に対するフロベニウス自己準同型写像φqを用いる。
【解決手段】電子計算機で、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算を行うスカラー倍算の演算装置において、Ｇの有理点Ｑに対し、
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑ
が成り立つことにより、スカラーｎをｔ-１進展開して、ｔ-１に換えて有理点に対するフロベニウス自己準同型写像φqを用いる。また、電子計算機で、非負整数ｎに対するＨの元Ａのｎ乗算を行うべき乗算の演算装置において、ｑとｒの差分をｓ＝ｑ−ｒとし、Ｈの非零元Ａに対し、
φq(Ａ)＝Ａq＝Ａs
が成り立つことにより、べき数ｎをｓ進展開して、ｓに換えて元に対するフロベニウス自己準同型写像φqを用いる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有理点Ｑのスカラーｎ倍算のｎを少なくともｔ−１進展開することによりスカラー倍算の演算を高速化したスカラー倍算の演算装置及び元Ａのｎ乗算のｎを少なくとも(ｑ−ｒ)進展開することによりべき乗算の演算を高速化したべき乗算の演算装置に関する。
【背景技術】
【０００２】
昨今、インターネットなどの電気通信回線を利用した情報ネットワーク技術が高度に発展し、インターネットによって様々な情報を取得するだけでなく、インターネットバンキングや行政機関への電子申請などのような各種のサービスが提供されてきている。
【０００３】
このようなサービスを利用する場合には、サービスの利用者が、成りすましや架空の人間などではなく、適正な利用者であることを確認するための認証処理が必要であり、信頼性の高い認証方法として、公開鍵と秘密鍵を用いる公開鍵暗号をベースとした電子認証技術がよく利用されている。
【０００４】
しかしながら、公開鍵暗号方式の電子認証では、公開鍵あるいは秘密鍵が漏洩した場合には直ちに公開鍵と秘密鍵を変更する必要があり、公開鍵及び秘密鍵の管理を慎重に行わなければならないとともに、必要に応じて新たな公開鍵と秘密鍵の設定登録作業が生じるという繁雑さがあるため、最近では、利用者の氏名やメールアドレスのように利用者特有のＩＤを用いて電子認証を行うＩＤベース暗号が用いられることが多くなっている。
【０００５】
また、電子認証を行う認証装置によって利用者の個人認証を行った場合には、認証装置に利用者ごとの履歴が蓄積されることとなり、この履歴情報自体が利用者の個人情報であって、最近では、この履歴情報が漏洩することによる個人情報の漏洩のおそれが指摘されている。
【０００６】
そこで、認証装置では利用者の個人情報を利用して認証を行うのではなく、複数の利用者をひとまとまりのグループとして、このグループに所属していることを示すグループ署名を用いることにより、利用者を特定することなく認証を行うことによって、認証装置に個人情報が蓄積されることなく認証を可能としたグループ署名技術が提案されている。
【０００７】
このようなＩＤベース暗号やグループ署名における所用の演算には、楕円曲線上の有理点の双線形写像を用いるペアリングと呼ばれる手法が用いられている。ペアリングとは、たとえば、Ｐを素体Ｆq上の有理点、Ｑをｋ次拡大体Ｆqk上の有理点として、ＰとＱとを入力して拡大体Ｆ*qkの元ｚが出力されるとき、ａ倍のＰと、ｂ倍のＱを入力するとｚのab乗が出力される演算である。なお、ここで、「ｋ」を埋込み次数と呼び、「Ｆ*qk」は、正しくは、以下の表示であるが、表示の制限上、「Ｆ*qk」と表示している。
【０００８】
【数１３】
【０００９】
ＩＤベース暗号における暗号化あるいは復号の処理や、グループ署名における認証処理では、できるだけ短時間で実行されることが求められている。特に、ペアリングに基づく暗号方式などにおいてはスカラー倍算及びべき乗算が数多く実行されているため、これらの演算を高速に実行することが求められている。
【００１０】
そのため、従来より、スカラー倍算やべき乗算をバイナリ法やWindow法などを用いて高速化することが行われている。
【００１１】
また、拡大体の元Ａ∈Ｆqkのべき乗Ａnを演算する場合には、フロベニウス写像φq：Ａ→Ａqを用いることによって演算回数を削減することにより高速化を図ることも行われている。
【００１２】
また、スカラー倍算においても、写像を利用することにより演算回数を削減して高速化を図る手法が提案されている(例えば、特許文献１、特許文献２参照。)。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００４−２７１７９２号公報
【特許文献２】特開２００７−４１４６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、写像を利用して高速化を図る周知の高速化手段では、スカラー倍算におけるスカラーｎ、またはべき乗算における乗数ｎが位数ｑを大きく上回る場合(ｎ＞＞ｑ)にはきわめて有効であるもの、有限体Ｆqの位数ｑより大きく上回ることのないスカラーｎ及び乗数ｎに対しては、高速化手段を用いずに直接的にスカラー倍算及びべき乗算を実行した場合と比較して顕著な効果が見いだせないものであった。
【００１５】
特に、ＩＤベース暗号における暗号化あるいは復号の処理や、グループ署名における認証処理においては、スカラーｎを用いたスカラー倍算あるいは乗数ｎを用いたべき乗算が必要な場合に、スカラーｎあるいは乗数ｎが、有限体Ｆqの位数ｑより大きく上回ることのない場合が多く、周知の高速化手段を用いても効果的な高速化が期待できなかった。
【００１６】
本発明者らはこのような現状に鑑み、スカラーｎあるいは乗数ｎが有限体Ｆqの位数ｑより大きく上回ることのない場合であっても、スカラー倍算あるいはべき乗算を高速に実行できる演算方法の研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１７】
本発明のスカラー倍算の演算装置では、
楕円曲線をＥ／Ｆq＝ｘ3＋ａｘ＋ｂ−ｙ2＝０，ａ∈Ｆq，ｂ∈Ｆqとし、
Ｅ(Ｆq)を有限体Ｆqで定義される楕円曲線の有理点が成す加法群、
Ｅ(Ｆqk)を有限体Ｆqの拡大体Ｆqkで定義される楕円曲線の有理点が成す加法群、
φqを有限体Ｆqに関する有理点のフロベニウス自己準同型写像、
ｔをフロベニウス自己準同型写像φqのトレース、
ｒをＥ(Ｆq)の位数＃Ｅ(Ｆq)＝ｑ＋１−ｔを割り切る素数位数、
Ｅ[ｒ]を位数が素数ｒである有理点の集合、
[ｊ]を有理点をｊ倍する写像、
Ｇを
Ｇ＝Ｅ[r]∩Ker(φq−[ｑ])
を満たすＥ(Ｆqk)に含まれる有理点の集合として、
非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算を、記憶手段を備えた電子計算機により演算するスカラー倍算の演算装置において、
前記非負整数ｎの値、前記トレースｔの値、及び、Ｑ∈Ｇ⊂Ｅ(Ｆqk)により表される有理点Ｑの値を前記記憶手段に入力して記憶させる入力手段と、
演算結果Ｚを記憶する前記記憶手段を初期化する初期化手段と、
Ｇの有理点Ｑに対し、
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑ
が成り立つことにより、
ｓ＝ｔ−１として、前記ｎをｓ進展開した次式に基づいて、
【数１４】
c[i]←n％s及びn←(n-c[i])/sにより表される代入演算をｉ＝０から所定回繰り返し行って各係数c[i]及び非負整数ｎの値を前記記憶手段に記憶する展開手段と、
前記記憶手段から前記有理点Ｑ及び前記係数ｃ［ｉ］を読み出して、Ｑ［ｉ］＝ｃ［ｉ］Ｑにより表される演算をｉ＝０から所定回繰り返し行って各Ｑ［ｉ］の値を前記記憶手段に記憶する演算手段と、
ｔ-１に換えて有理点に対するフロベニウス自己準同型写像φqを用いて表される次式のスカラー倍算ｎＱに基づいて、
【数１５】
前記記憶手段からＱ［ｉ］及び演算結果Ｚを読み出し、Z←Z+φqi(Q[i])により表される代入演算をｉ＝０から所定回繰り返し行ってスカラー倍算の演算結果Ｚを前記記憶手段に記憶する合成手段と、
を有するものである。
【００１８】
さらに、本発明のスカラー倍算の演算装置では、
前記楕円曲線の有限体Ｆqの位数ｑ、＃Ｅ(Ｆq)を割り切る素数位数ｒ、フロベニウス自己準同型写像φqのトレースｔが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｔ(χ)で与えられている場合に、
前記ｑ(χ)、ｒ(χ)、ｔ(χ)の各値を入力して前記記憶手段に記憶する補助入力手段と、
前記記憶手段からｒ(χ)及びｔ(χ)の値を読み出して、前記ｓ（χ）＝ｔ（χ）−１として、ｒ(χ)をｓ（χ）進展開した次式に基づいて、
【数１６】
Di(χ)←r(χ)％s(χ)及びr(χ)←(r(χ)-Di(χ))/s(χ)により表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返し行って、各係数Ｄｉ（χ）及びｒ（χ）の値を前記記憶手段に記憶する補助展開手段と、
前記記憶された係数Ｄｉ（χ）のうち、deg（Ｄｉ（χ））が最大のものをＤｄｍａｘ（χ）として抽出し、前記記憶手段に記憶する補助抽出手段と、
前記記憶手段からＤdmax(χ)、Ｄi(χ)、Ｑの値を読み出して、
φqdmax([Ｄdmax(χ)]Ｑ)＝Σφqi([Ｄi(χ)]Ｑ)−φqdmax([Ｄdmax(χ)]Ｑ)
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)を用い、φqkＱ＝Ｑに基づいて
[Ｄdmax(χ)]Ｑ＝[ｆ(φq,χ)φq-dmax]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、前記多項式ｈ(φq,χ)の値を前記記憶手段に記憶する補助特定手段と、
前記ｓ進展開をχ＝ａとしてｓ＝Ｄdmax(ａ)からなるＤdmax(ａ)進展開に置換え、前記Ｄdmax(ａ)に換えて前記多項式ｈ(φq,ａ)を用いる手段と、を有するものである。
【００１９】
しかも、本発明のスカラー倍算の演算装置では、
前記係数Ｄｉ（χ）において最高次数dmaxとなる係数Ｄｉ（χ）が複数存在する場合に、
前記補助入力手段は、ｒ（χ）｜ｍ（χ）を満たすｍ（χ）の値を入力して前記記憶手段に記憶する手段を更に含み、
deg（Ｄｉ(χ)）の最高次数dmaxの項であるχdmaxの係数をＴdmax(φq)として、前記記憶手段から係数Ｄｉ（χ）を読み出し、前記記憶手段にT(φq,χ)及びU(φq,χ)を初期値を０として割り当て、deg(Di(χ))=dmaxとなる場合にT(φq,χ)←T(φq,χ)+Di(χ)φqi、その他の場合にU(φq,χ)←U(φq,χ)+Di(χ)φqiにより表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返し行って、Ｔ(φq,χ)及びＵ(φq,χ)の値を前記記憶手段に記憶し、最高次数係数Ｔdmax(φq)を特定する第２の補助特定手段と、
前記記憶手段からｍ（χ）及びＲ（χ）の値を読み出して、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を、W(φq)←gcd(Tdmax(φq),m(φq))及びV(φq)←W(φq)により表される代入演算を行って特定し、前記Ｖ(φq)の値を前記記憶手段に記憶する第３の補助特定手段と、
前記記憶手段からＶ(φq)及びｍ(φq)の値を読み出して、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たす整数のスカラーｖ及びｇ(φq)を拡張ユークリッドの互除法により特定し、前記スカラーｖ及びｇ(φq)の値を前記記憶手段に記憶する第４の補助特定手段と、
前記補助特定手段に代えて、前記記憶手段からＴdmax(φq)、χdmax、Ｄi(χ)、Ｑの各値を読み出して、
[Ｔdmax(φq)χdmax]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)−[Ｔdmax(φq)χdmax]Ｑ
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)と、前記ｇ(φq)を用い、φqkＱ＝Ｑに基づいて、
[ｖχdmax]Ｑ＝[ｇ(φq)ｆ(φq,χ)]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、前記多項式ｈ(φq,χ)の値を前記記憶手段に記憶する第５の補助特定手段と、
前記記憶手段から前記ｈ(φq,χ)の値を読み出して、
このｈ(φq,χ)のφqに関する定数項ｈ(０,χ)が、
[ｖχdmax−ｈ(０,χ)]Ｑ＝[ｈ(φq,χ)−ｈ(０,χ)]Ｑ
を満たすことを用いて、
χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)により表される演算を行ってｓ'、ｈ'(φq)の値を前記記憶手段に記憶し、
ｔ-１進展開した前記ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(φq,ａ)−ｈ(０,ａ)を用いる手段と、を有するものである。
【００２０】
また、本発明のべき乗算の演算装置では、
Ｆqkを位数ｑの有限体Ｆqのｋ次拡大体、
ＨをＦqkの素数位数ｒの部分乗法群、
φqを有限体Ｆqに関する元のフロベニウス自己準同型写像として、
非負整数ｎに対するＨの元Ａのｎ乗算を行うべき乗算を、記憶手段を備えた電子計算機により演算する演算装置において、
前記非負整数nの値、前記位数ｑの値、前記Ｆqkの素数位数ｒの値、Ａ∈Ｈ⊂Ｆqkにより表される元Ａの値を入力して前記記憶手段に記憶する入力手段と、
演算結果Ｚを記憶する前記記憶手段を初期化する初期化手段と、
前記位数ｑ、前記元Ａの値を前記記憶手段から読み出して、前記ｑとｒの差分をｓ＝ｑ−ｒとし、T[j]←A及びA←A*Aにより表される代入演算を、j＝０からj<「log2s」まで繰り返して行って前記T[j]及び前記Aの値を前記記憶手段に記憶する第１の演算手段と、
前記記憶手段から前記ｎ及び差分ｓの値を読み出して、差分ｓにより展開した次式に基づいて、
【数１７】
c[i]←n％s及びn←(n-c[i])/sにより表される代入演算をｉ＝０から所定回繰り返して行い、各係数c[i]及び非負整数ｎの値を前記記憶手段に記憶する展開手段と、
前記記憶手段からc[i]及び前記ｎの値を読み出して、Ａ［ｉ］＝Ａｃ［ｉ］に基づいて、Ａ［ｉ］＝１に初期化し、c[i]＆1である場合にA[i]←A[i]*T[j]、c[i]←c[i]/2により表される代入演算を、ｉ＝０から所定回繰り返して行い、前記記憶手段にA[i]及びc[i]の値を記憶する第２の演算手段と、
前記記憶手段から各Ａ［ｉ］を読み出し、次式に基づいて、
【数１８】
Z←Z＊φqi(A[i])により表されるべき乗演算を、ｉ＝０から所定回繰り返して行い、計算結果Ｚとして前記記憶手段に記憶する合成手段と、を有するものである。
【００２１】
さらに、本発明のべき乗算の演算装置では、
Ｘ^{Ｙ}はＸＹであることを表すこととし、
前記位数ｑ、前記素数位数ｒ、前記ｓが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｓ(χ)で与えられている場合に、
前記ｑ(χ)、ｒ(χ)、ｓ(χ)の各値を入力して前記記憶手段に記憶する補助入力手段と、
前記記憶手段からｒ(χ)及びｓ(χ)を読み出して、前記ｓ（χ）を用いて前記ｒ（χ）をｓ（χ）進展開した次式に基づいて、
【数１９】
Di(χ)←r(χ)％s(χ)及びr(χ)←(r(χ)-Di(χ))/s(χ)により表される代入演算を、ｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返して行い、前記係数Di(χ)及びr(χ)を前記記憶手段に記憶する補助展開手段と、
前記記憶された係数Ｄｉ（χ）のうち、deg（Ｄｉ（χ））が最大のものをＤｄｍａｘ（χ）として抽出し、前記記憶手段に記憶する補助抽出手段と、
前記記憶手段から前記Ｄｄｍａｘ（χ）、Ｄi(χ)、ｑの値を読み出して、
(Ａ^{Ｄdmax(χ)})^{ｑdmax}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi}＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)を用い、φqk(Ａ)＝Ａに基づいて
Ａ^{Ｄdmax(χ)}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi−ｑdmax}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、前記多項式ｈ(ｑ,χ)の値を前記記憶手段に記憶する補助特定手段と、
前記ｓ進展開した前記ｎを、χ＝ａとしてｓ＝Ｄdmax(ａ)からなるＤdmax(ａ)進展開に置き換え、前記Ｄdmax(ａ)に換えて前記多項式ｈ(ｑ,ａ)を用いる手段と、を有するものである。
【００２２】
しかも、本発明のべき乗算の演算装置では、
前記係数Ｄｉ（χ）において最高次数dmaxとなる係数Ｄｉ（χ）が複数存在する場合に、
前記補助記憶手段は、ｒ（χ）｜ｍ（χ）を満たすｍ（χ）の値を入力して前記記憶手段に記憶する手段を更に含み、
deg（Ｄi(χ)）の最高次数dmaxの項であるχdmaxの係数をＴdmax(ｑ)として、前記記憶手段から係数Ｄｉ（χ）を読み出し、前記記憶手段にT(ｑ,χ)及びU(ｑ,χ)を初期値を０として割り当て、deg(Di(χ))=dmaxとなる場合にT(ｑ,χ)←T(ｑ,χ)+Di(χ)ｑi、その他の場合にU(ｑ,χ)←U(ｑ,χ)+Di(χ)ｑiにより表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返して行ってＴ(ｑ,χ)及びＵ(ｑ,χ)の値を前記記憶手段に記憶し、最高次数係数Ｔdmax(ｑ)を特定する第２の補助特定手段と、
前記記憶手段からｍ（χ）及びＲ（χ）の値を読み出して、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を、W(ｑ)←gcd(Tdmax(ｑ),m(ｑ))及びV(ｑ)←W(ｑ)により表される演算を行って特定し、前記Ｖ(ｑ)の値を前記記憶手段に記憶する第３の補助特定手段と、
前記記憶手段からＶ(ｑ)及びｍ(ｑ)の値を読み出して、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たす整数のスカラーｖ及びｇ(ｑ)を拡張ユークリッドの互除法により特定し、前記スカラーｖ及びｇ(ｑ)の値を前記記憶手段に記憶する第４の補助特定手段と、
前記補助特定手段に代えて、前記記憶手段からＴdmax(ｑ)、χdmax、Ｄi(χ)、Ｑの各値を読み出して、
Ａ^{Ｔdmax(ｑ)χdmax}＝Ａ^{ΣＤi(χ)ｑi−Ｔdmax(ｑ)χdmax}
＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)と、前記ｇ(ｑ)を用い、φqk(Ａ)＝Ａに基づいて、
Ａ^{ｖχdmax}＝Ａ^{ｇ(ｑ)ｆ(ｑ,χ)}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、前記多項式ｈ(ｑ,χ)の値を前記記憶手段に記憶する第５の補助特定手段と、
前記記憶手段から前記ｈ(ｑ,χ)の値を読み出して、
このｈ(ｑ,χ)のｑに関する定数項ｈ(０,χ)が、
Ａ^{ｖχdmax−ｈ(０,χ)}＝Ａ^{ｈ(ｑ,χ)−ｈ(０,χ)}
を満たすことを用いて、
χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ) により表される演算を行ってｓ'、ｈ'(ｑ)の値を前記記憶手段に記憶し、ｓ進展開した前記ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(ｑ,ａ)−ｈ(０,ａ)を用いる手段と、を有するものである。
【発明の効果】
【００２３】
本発明は、フロベニウス自己準同型写像φｑ用いて演算回数を削減すものであって、特に、スカラー倍算の場合には、Ｇの有理点Ｑに対し、
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑ
が成り立つことにより、また、べき乗算の場合には、ｑとｒの差分をｓ＝ｑ−ｒとし、Ｈの非零元Ａに対し、
φq(Ａ)＝Ａq＝Ａs
が成り立つことにより、スカラーｎをｔ-１進展開、またはべき数ｎをｓ進展開して、ｔ-１に換えて有理点に対するフロベニウス自己準同型写像φqを用い、またはｓに換えて元に対するフロベニウス自己準同型写像φqを用いることにより、スカラー倍算におけるスカラーｎ、またはべき乗算における乗数ｎが位数ｑを大きく上回ることのない場合でも、演算回数を削減可能として演算速度を向上させることができる。
【００２４】
特に、ペアリングをベースとしたＩＤベース暗号やグループ署名などでは、ペアリングフレンドリ曲線と呼ばれるペアリングを利用可能な楕円曲線が用いられ、このペアリングフレンドリ曲線を用いる場合には、整数変数χを用いて位数ｑ(χ)、＃Ｅ(Ｆq)を割り切る素数位数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)があらかじめ与えられており、スカラー倍算の場合には、ｒ(χ)をｔ(χ)−１進展開するとともに、このｔ(χ)−１進展開の際に導入した係数Ｄi(χ)のうちでもっとも次数の高い係数Ｄi(χ)をＤdmax(χ)とし、このＤdmax(χ)を多項式ｈ(φq,χ)に置き換えることにより演算回数をさらに削減し、また、べき乗算の場合には、ｒ(χ)をｓ(χ)＝ｑ(χ)−ｒ(χ)進展開するとともに、このｓ(χ)進展開の際に導入した係数Ｄi(χ)のうちでもっとも次数の高い係数Ｄi(χ)をＤdmax(χ)とし、このＤdmax(χ)を多項式ｈ(φq,χ)に置き換えることにより演算回数をさらに削減し、それぞれ演算速度を向上させることができる。
【００２５】
しかも、最高次数dmaxとなるＤi(χ)が複数存在する場合には、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を特定するとともに、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たす整数のスカラーｖを用い、スカラー倍算の場合には、ｔ-１進展開したスカラーｎをＤdmax(χ)進展開する換わりにｖχdmax−ｈ(０,χ)進展開して、ｖχdmax−ｈ(０,χ)の換わりにｈ(ｑ,χ)−ｈ(０,χ)を用いることにより演算回数をさらに削減し、また、べき乗算の場合には、ｓ進展開したべき数ｎをＤdmax(χ)進展開する換わりにｖχdmax−ｈ(０,χ)進展開して、ｖχdmax−ｈ(０,χ)の換わりにｈ(ｑ,χ)−ｈ(０,χ)を用いることにより演算回数をさらに削減し、それぞれ演算速度を向上させることができる。
【図面の簡単な説明】
【００２６】
【図１】スカラー倍算の演算プログラム及びべき乗算の演算プログラムを備えた電子計算機の説明図。
【図２】スカラー倍算の演算プログラムのフローチャートである。
【図３】スカラー倍算の演算プログラムのフローチャートである。
【図４】Ｄdmax(χ)及び多項式ｈ(φq,χ)を求める補助プログラムのフローチャートである。
【図５】スカラー倍算の演算プログラムのフローチャートである。
【図６】多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)を求める補助プログラムのフローチャートである。
【図７】べき乗算の演算プログラムのフローチャートである。
【図８】べき乗算の演算プログラムのフローチャートである。
【図９】Ｄdmax(χ)及び多項式ｈ(ｑ,χ)を求める補助プログラムのフローチャートである。
【図１０】べき乗算の演算プログラムのフローチャートである。
【図１１】多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)を求める補助プログラムのフローチャートである。
【発明を実施するための形態】
【００２７】
本発明は、スカラー倍算の演算の高速化及びべき乗算の演算の高速化を目的としたものであり、スカラー倍算とべき乗算というように演算自体は異なるが、高速化のための手法は同じであり、それぞれ同じように演算回数が削減されることにより、演算の高速化を可能としているものである。最初にスカラー倍算について説明し、次いでべき乗算について説明する。
【００２８】
まず、楕円曲線をＥ／Ｆq＝ｘ3＋ａｘ＋ｂ−ｙ2＝０，ａ∈Ｆq，ｂ∈Ｆqとし、
Ｅ(Ｆq)：有限体Ｆqで定義される楕円曲線の有理点が成す加法群
Ｅ(Ｆqk)：有限体Ｆqの拡大体Ｆqkで定義される楕円曲線の有理点が成す加法群
φq：有限体Ｆqに関する有理点のフロベニウス自己準同型写像
ｔ：フロベニウス自己準同型写像φqのトレース
ｒ：Ｅ(Ｆq)の位数＃Ｅ(Ｆq)＝ｑ＋１−ｔを割り切る素数位数
Ｅ[ｒ]：位数が素数ｒである有理点の集合
[ｊ]：有理点をｊ倍する写像
Ｇ：Ｇ＝Ｅ[r]∩Ker(φq−[ｑ])を満たすＥ(Ｆqk)に含まれる有理点の集合
と定義する。
【００２９】
そして、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、すなわちｎＱを演算する。なお、本実施形態で想定するスカラー倍算はペアリングの演算の際に行われるものであり、一般的にスカラーｎは位数ｒを大きく超えるものではない。
【００３０】
また、ｒ＝ｑ＋１−ｔであることから、０≡ｑ＋１−ｔ(mod ｒ)である。
【００３１】
ここで、スカラーｎをｔ−１進展開すると、スカラーｎが位数ｒを大きく超えるものではないことから、
ｎ＝Ｃ1(ｔ−１)＋Ｃ0
または、
ｎ＝(ｔ−１)2＋Ｃ1(ｔ−１)＋Ｃ0
となる。
【００３２】
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑであるので、ｎ＝Ｃ1(ｔ−１)＋Ｃ0の場合、ｎＱは以下のようになる。
ｎＱ＝[Ｃ1(ｔ−１)＋Ｃ0]Ｑ
＝[Ｃ1ｑ]Ｑ＋[Ｃ0]Ｑ
＝φq([Ｃ1]Ｑ)＋[Ｃ0]Ｑ
【００３３】
また、ｎ＝(ｔ−１)2＋Ｃ1(ｔ−１)＋Ｃ0場合には、ｎＱは以下のようになる。
ｎＱ＝[(ｔ−１)2＋Ｃ1(ｔ−１)＋Ｃ0]Ｑ
＝[ｑ][ｑ]Ｑ＋[Ｃ1ｑ]Ｑ＋[Ｃ0]Ｑ
＝φq(φq(Ｑ))＋φq([Ｃ1]Ｑ)＋[Ｃ0]Ｑ
【００３４】
ここで、Ｃ1及びＣ0はｔ−１と同程度あるいはそれよりも小さくなり、しかも有理点のフロベニウス自己準同型写像を用いることができることによって演算回数を削減できる。したがって、スカラー倍算を高速化することができる。
【００３５】
また、通常、ペアリングの演算を行う場合には、既知のペアリングフレンドリ曲線が用いられており、特に、整数変数χを用いて位数ｑ(χ)、＃Ｅ(Ｆq)を割り切る素数位数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)があらかじめ与えられていることが多い。
【００３６】
ここで、[ｒ]Ｑ＝[ｑ＋１−ｔ]Ｑ＝Ｏであることを考慮しながら、ｒ(χ)をｔ(χ)−１で剰余をとる、すなわち、ｒ(χ)を、
[ｒ(χ)]Ｑ＝Σ[Ｄi(χ)(ｔ(χ)−１)i]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)
とｔ(χ)−１進展開して、Ｄi(χ)のうちでもっとも次数の高いものをＤdmax(χ)とする。
【００３７】
そして、
φqdmax([Ｄdmax(χ)]Ｑ)＝Σφqi([Ｄi(χ)]Ｑ)−φqdmax([Ｄdmax(χ)]Ｑ)
＝[ｆ(φq,χ)]Ｑ
として定義されるφqとχを変数とする２変数の多項式ｆ(φq,χ)を導入する。
【００３８】
さらに、φqkＱ＝Ｑに基づいて、
[Ｄdmax(χ)]Ｑ＝[ｆ(φq,χ)φq-dmax]Ｑ＝[ｈ(φq,χ)]Ｑ
として定義されるφqとχを変数とする２変数の多項式ｈ(φq,χ)を導入する。すなわち、この多項式ｈ(φq,χ)は、Ｄi(χ)のうちの最高次数のＤdmax(χ)を、φqとχを変数とする多項式ｈ(φq,χ)に置き換え可能であることを示しており、最高次数よりも小さい次数までの演算に抑えることができ、特に、χ＝ａとした場合には、ｔ-１進展開したスカラーｎをさらにＤdmax(ａ)進展開して、Ｄdmax(ａ)に換えてｈ(φq,ａ)を用いることによって演算回数を大きく削減でき、スカラー倍算を高速化することができる。
【００３９】
また、Ｄi(χ)のうちでもっとも次数の高いものが複数存在する場合には、最高次数をdmaxで表すものとし、最高次数dmaxの項であるχdmaxの係数をＴdmax(φq)として、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を特定する。ここで、多項式ｍ(χ)には円周等分多項式などを用いることができる。
【００４０】
そして、拡張ユークリッドの互除法を用いて、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たす整数のスカラーｖ及びｇ(φq)を特定し、
[Ｔdmax(φq)χdmax]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)−[Ｔdmax(φq)χdmax]Ｑ
＝[ｆ(φq,χ)]Ｑ
としてφqとχを変数とする２変数の多項式ｆ(φq,χ)を導入する。
【００４１】
さらに、ｇ(φq)を用い、φqkＱ＝Ｑに基づいて、
[ｖχdmax]Ｑ＝[ｇ(φq)ｆ(φq,χ)]Ｑ＝[ｈ(φq,χ)]Ｑ
としてφqとχを変数とする２変数の多項式ｈ(φq,χ)を導入する。
【００４２】
そして、このｈ(φq,χ)のφqに関する定数項ｈ(０,χ)が、
[ｖχdmax−ｈ(０,χ)]Ｑ＝[ｈ(φq,χ)−ｈ(０,χ)]Ｑ
を満たすことを用いて、χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)とし、ｔ-１進展開したスカラーｎをＤdmax(ａ)進展開する換わりに{ｖａdmax−ｈ(０,ａ)}進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(φq,ａ)−ｈ(０,ａ)を用いることにより演算回数を減できるので、スカラー倍算を高速化することができる。ここで、ｈ'(φq)は、φqとχの２変数の多項式ｈ(φq,χ)において、χ＝ａとしたことによりφqの１変数となっていることを示している。
【００４３】
ここまでスカラー倍算について説明したが、べき乗算の場合には、
Ｆqk：位数ｑの有限体Ｆqのｋ次拡大体
Ｈ：Ｆqkの素数位数ｒの部分乗法群
φq：有限体Ｆqに関する元のフロベニウス自己準同型写像
と定義して、非負整数ｎに対するＨの元Ａのｎ乗算を行うものであり、ｑとｒの差分をｓ＝ｑ−ｒとし、このｓをスカラー倍算におけるｔ−１に置き換えて上述の説明をべき乗算として読み換えるだけであり、詳細な説明は省略する。べき乗算の場合でも、最高次数部分の演算がより低い次数の演算に置き換えられることにより、演算回数を減してべき乗算を高速化することができる。
【００４４】
以下において、既知のペアリングフレンドリ曲線を用いながら具体例を説明する。
【００４５】
埋め込み次数８のペアリングフレンドリ曲線として、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が、
ｒ(χ)＝χ４−８χ２＋２５
ｔ(χ)＝(２χ３−１１χ＋１５)／１５
と与えられるものが知られている。
【００４６】
この場合、ｒ(χ)をｔ(χ)−１進展開して、フロベニウス準同型写像φqを用いることにより、
２ｒ(χ)＝(１５χ)φq＋(−５χ２＋５０)
０≡(１５χ)φq＋(−５χ２＋５０) (mod ｒ(χ))
となる。
【００４７】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝−５χ２＋５０
Ｄ1(χ)＝１５χ
となる。
【００４８】
このうち、Ｄ0(χ)が最も次数が高いので、Ｄ0(χ)以外を右辺に移すことにより、
−５χ２＋５０＝１５χφq
となり、式を整理することにより、
χ２−１０＝３χφq
が得られる。
【００４９】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらにχ２−１０進展開して、χ２−１０に換えて１５χφqを用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００５０】
他の具体体の埋め込み次数８のペアリングフレンドリ曲線として、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が
ｒ(χ)＝χ８−χ４＋１
ｔ(χ)＝χ５−χ＋１
と与えられた場合には、ｒ(χ)をｔ(χ)−１進展開し、フロベニウス準同型写像φqを用いることにより、
ｒ(χ)＝χ３φq＋１
０≡３φq＋１ (mod ｒ(χ))
となる。
【００５１】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝−１
Ｄ1(χ)＝χ３
となる。
【００５２】
このうち、Ｄ1(χ)が最も次数が高いので、Ｄ1(χ)φq以外を右辺に移すことにより、
χ３φq＝−１
となり、両辺にφ-1を掛けることで
χ３＝−φq-1
が得られる。
【００５３】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらにχ３進展開して、χ３に換えて−φq-1を用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００５４】
また、埋め込み次数１０のペアリングフレンドリ曲線の場合には、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が、
ｒ(χ)＝２５χ４＋２５χ３＋１５χ２＋５χ＋１
ｔ(χ)＝１０χ２＋５χ＋３
と与えられるものが知られている。
【００５５】
この場合、ｒ(χ)をｔ(χ)−１進展開して、フロベニウス準同型写像φqを用いることにより、
８ｒ(χ)＝２φq２−φq＋(５χ＋２)
０≡２φq２−φq＋(５χ＋２) (mod ｒ(χ))
となる。
【００５６】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝５χ＋２
Ｄ1(χ)＝−１
Ｄ2(χ)＝２
となる。
【００５７】
このうち、Ｄ0(χ)が最も次数が高いので、Ｄ0(χ)以外を右辺に移すことにより
５χ＋２＝−２φq２＋φq
が得られる。
【００５８】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらに５χ＋２進展開して、５χ＋２に換えて−２φq２＋φqを用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００５９】
また、埋め込み次数１２のペアリングフレンドリ曲線の場合には、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が、
ｒ(χ)＝３６χ４−３６χ３＋１８χ２−６χ＋１
ｔ(χ)＝６χ２＋１
と与えられるものが知られている。
【００６０】
この場合、ｒ(χ)をｔ(χ)−１進展開して、フロベニウス準同型写像φqを用いることにより、
ｒ(χ)＝φq２＋(−６χ＋３)φq＋(−６χ＋１)
０≡φq２＋(−６χ＋３)φq＋(−６χ＋１) (mod ｒ(χ))
となる。
【００６１】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝−６χ＋１
Ｄ1(χ)＝−６χ＋３
Ｄ2(χ)＝１
となる。
【００６２】
ここで、Ｄ0(χ)とＤ1(χ)が共に最も次数が高いので、Ｄ0(χ)とＤ1(χ)φqの最高次数を与えるχの項以外を右辺に移すことにより、
６χ(φq＋１)＝φq２＋３φq＋１
となる。
【００６３】
ここで、ｇ(φq)＝φq４−φq２＋１とすると、gcd(φq＋１,ｇ(φq))＝１を満たし、拡張ユークリッドの互除法より
(φq＋１)−１≡φq２(１−φq) (mod ｇ(φq))
が得られる。
【００６４】
したがって、両辺にφq２(１−φq)を乗じることにより、
６χ＝φq２(１−φq)(φq２＋３φq＋１)
が得られる。
【００６５】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらに６χ進展開して、６χに換えてφq２(１−φq)(φq２＋３φq＋１)を用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００６６】
より具体的な例として、χ＝８２５(１０ビット)とする。このとき、
ｒ＝１６６５６８１１７４６３０１(４４ビット)
ｔ＝４０８３７５１(２２ビット)
である。
【００６７】
この場合、
６χ＝４９５０(１３ビット)＝φq２(１−φq)(φq２＋３φq＋１)
となるので、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を行う場合には、有理点に対するフロベニウス自己準同型写像φｑを用いて１３ビット程度のスカラー倍算またはべき乗算に変換してから演算を行うこととなり、演算回数の大幅な削減が可能となっている
【００６８】
また、埋め込み次数１８のペアリングフレンドリ曲線の場合には、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が、
ｒ(χ)＝χ６＋３７χ３＋３４３
ｔ(χ)＝(χ４＋１６χ＋７)／７
と与えられるものが知られている。
【００６９】
この場合、ｒ(χ)をｔ(χ)−１進展開して、フロベニウス準同型写像φqを用いることにより、
ｒ(χ)＝（７χ２)φq＋(２１χ３＋３４３)
０≡（７χ２)φq＋(２１χ３＋３４３) (mod ｒ(χ))
となる。
【００７０】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝２１χ３−３４３
Ｄ1(χ)＝７χ２
となる。
【００７１】
このうち、Ｄ0(χ)が最も次数が高いので、Ｄ0(χ)以外を右辺に移すことにより、
２１χ３−３４３＝７χ２φq
となり、式を整理することによって、
χ３−４９＝χ２φq
が得られる。
【００７２】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらにχ３−４９進展開して、χ３−４９に換えてχ２φqを用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００７３】
最後に、スカラー倍算の演算プログラム及びべき乗算の演算プログラムについて詳説する。なお、スカラー倍算の演算プログラム及びべき乗算の演算プログラムは、本実施形態では、ＩＤベース暗号やグループ署名などを電子計算機で実行している際に、サブルーチンの一つとしてそれぞれ実行されるものである。
【００７４】
図１に示すように、スカラー倍算の演算プログラム及びべき乗算の演算プログラムを実行する電子計算機10は、演算処理を実行するＣＰＵ11と、所要のプログラムやデータを記憶したハードディスクなどの記憶装置12と、所要のプログラムを展開して実行可能とするとともに、演算にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置13を備えている。図１中、14はバスである。本実施形態では、記憶装置12には、メインルーチンのプログラムやスカラー倍算の演算プログラム及びべき乗算の演算プログラムなどの各種プログラム、及びこれらのプログラムが使用するデータを記憶させている。
【００７５】
電子計算機10が、例えばグループ署名における認証装置として機能する場合には、インターネットなどの電気通信回線20に接続して、この電気通信回線20に接続されたクライアント装置30から送信されたグループ署名の署名データを受信し、メモリ装置13に一次的に記憶して、グループ署名用のプログラムに基づいて署名データの正当性を判定して認証処理を行っている。図１中、15は電子計算機10の入出力制御部である。
【００７６】
スカラー倍算の演算プログラム及びべき乗算の演算プログラムは、それぞれ署名データの正当性を判定する処理を行う際に数多く実行されるものであり、以下においては、スカラー倍算の演算プログラム、及びべき乗算の演算プログラムについてのみ説明する。なお、スカラー倍算の演算プログラム及びべき乗算の演算プログラムは、グループ署名の処理において用いられるものではなく、多種多様な用途で用いられるものであり、しかも、記憶装置12に記憶可能な形態である場合だけでなく、半導体回路として構成することによりいわゆるハードウェア実装される形態であってもよい。
【００７７】
まず、ｔ−１進展開によるスカラー倍算ｎＱについて説明する。
【００７８】
スカラー倍算の演算プログラムを実行させて電子計算機をスカラー倍算機として機能させる際に、図２に示すように、はじめに、スカラーｎと、Ｅ(Ｆq)のフロベニウス自己準同型写像のトレースｔと、有理点Ｑ∈Ｇ⊂Ｅ(Ｆqk)が入力される（ステップＳ１０１）。この場合、電子計算機は、入力手段として機能する。
【００７９】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←Ｏ）する（ステップＳ１０２）。そして、第１の演算手段として機能し、入力されたＱに対して、２jＱをあらかじめ演算しておく（ステップＳ１０３）。
【００８０】
ステップＳ１０３では、Ｔ[ｊ]＝２jＱとして、電子計算機は、以下のアルゴリズムを実行している。
（１）for(j=0;J<「log2s」;j++)
（２） T[j]←Q
（３） Q←Q+Q
（４）End for
ここで、(1)の「log2s」は、厳密には、
【００８１】
【数２６】
であるが、表記上の制限のため、「」を用いている。以下において、アルゴリズム中の「」は同じ意味に用いる。
【００８２】
次いで、ｔ−１＝ｓとして、電子計算機は、展開手段として機能し、スカラーｎを、
【００８３】
【数２７】
とｓ進展開する（ステップＳ１０４）。ここで、ｉの大きさは、ｎの大きさによって決定するものである。
【００８４】
ステップＳ１０４では、ｓ進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） c[i]←n％s
（３） n←(n-c[i])/s
（４）End for
ここで、「％」は、剰余をとっていることを表している。
【００８５】
次いで、本実施形態では、電子計算機は、第２の演算手段として機能し、Ｑ[ｉ]＝ｃ[ｉ]Ｑの演算を行う（ステップＳ１０５）。
【００８６】
ステップＳ１０５では、バイナリ法を用いており、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） Q[i]←O
（３） for(j=0;c[i]!=0;i++)
（４） if(c[i]＆1)
（５） Q[i]←Q[i]+T[j]
（６） End if
（７） c[i]←c[i]/2
（８） End for
（９）End for
【００８７】
次いで、電子計算機は、合成手段として機能し、ステップＳ１０５で演算したＱ[ｉ]を用いて、スカラー倍算ｎＱを、
【００８８】
【数２８】
によって合成する（ステップＳ１０６）。
【００８９】
ステップＳ１０６では、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） Z←Z+φqi(Q[i])
（３）End for
【００９０】
そして、電子計算機は、出力手段として機能し、スカラー倍算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ１０７）、スカラー倍算の演算プログラムを終了している。
【００９１】
また、楕円曲線の有限体Ｆqの位数ｑ、＃Ｅ(Ｆq)を割り切る素数位数ｒ、フロベニウス自己準同型写像φqのトレースｔが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｔ(χ)とあらかじめ特定されている場合には、ｒ(χ)をｔ(χ)−１進展開することにより
[ｒ(χ)]Ｑ＝Σ[Ｄi(χ)(ｔ(χ)−１)i]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)
として表されるＤi(χ)のうちでもっとも次数の高いものをＤdmax(χ)とし、
φqdmax([Ｄdmax(χ)]Ｑ)＝Σφqi([Ｄi(χ)]Ｑ)−φqdmax([Ｄdmax(χ)]Ｑ)
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)を用い、φqkＱ＝Ｑに基づいて
[Ｄdmax(χ)]Ｑ＝[ｆ(φq,χ)φq-dmax]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)と、Ｄdmax(χ)を用いることにより、スカラー倍算ｎＱをより高速化することができる。
【００９２】
すなわち、Ｄdmax(χ)及び多項式ｈ(φq,χ)が特定されている場合には、χ＝ａとしてスカラーｎをＤdmax(ａ)進展開して、Ｄdmax(ａ)に換えてｈ(φq,ａ)を用いることにより、演算回数を削減している。
【００９３】
Ｄdmax(χ)及び多項式ｈ(φq,χ)が特定されている場合のスカラー倍算ｎＱでは、スカラー倍算の演算プログラムを実行させて電子計算機をスカラー倍算機として機能させる際に、図３に示すように、はじめに、スカラーｎと、χ＝ａとしてｓ＝Ｄdmax(ａ)及びｈ'(φq)＝ｈ(φq,ａ)と、有理点Ｑ∈Ｇ⊂Ｅ(Ｆqk)が入力される（ステップＳ２０１）。この場合、電子計算機は、入力手段として機能する。
【００９４】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←Ｏ）する（ステップＳ２０２）。そして、第１の演算手段として機能し、入力されたＱに対して、２jＱをあらかじめ演算しておく（ステップＳ２０３）。ステップＳ２０３の演算はステップＳ１０３の演算とアルゴリズムは同じであるので、説明は省略する。
【００９５】
次いで、電子計算機は、第１の展開手段として機能し、スカラーｎを、
【００９６】
【数２９】
とｓ進展開する（ステップＳ２０４）。ステップＳ２０４でのｓ進展開は、ステップＳ１０４でのｓ進展開とアルゴリズムは同じであるので、説明は省略する。
【００９７】
次いで、電子計算機は、第２の展開手段として機能し、スカラーｎを、ｈ'(φq)及びｃ[ｉ]を用いながら、
【００９８】
【数３０】
とφq進展開する（ステップＳ２０５）。
【００９９】
ステップＳ２０５では、φq進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）T(φq)←１
（２）for(i=0;i<「logsn」;i++)
（３） d[i]←c[i]
（４） if(d[i]≧s)
（５） for(j=0;j<「logsd[i]」;j++)
（６） e[j]←d[i]％s
（７） d[i]←(d[i]-e[j])％s
（８） End for
（９） U(φq)←１
（10） for(j=0;j<「logsd[i]」;j++)
（11） U(φq)←{U(φq)*e[j]*h'(φq)j}％(φqk-1)
（12） End for
（13） T(φq)←{T(φq)+U(φq)*h'(φq)i}％(φqk-1)
（14） End if
（15） else
（16） T(φq)←{T(φq)+d[i]*h'(φq)i}％(φqk-1)
（17） End else
（18）End for
【０１００】
なお、スカラーｎをφq進展開した場合に、φq進展開の係数がｓよりも大きくなることがある。このように、φq進展開の係数がｓよりも大きい場合（ステップＳ２０６：ＮＯ）には、φq進展開の係数に対してｓの剰余をとることにより、φq進展開の係数がｓよりも小さくなるように調整している（ステップＳ２０７）。この場合、電子計算機は、ステップＳ２０６において比較手段として機能し、ステップＳ２０７において調整手段として機能する。
【０１０１】
ステップＳ２０７では、電子計算機は、以下のアルゴリズムを実行している。
（１）until(∀d[i]＜ｓ)
（２） for(i=0;i<k-1;i++)
（３） d[i]←the i-th coefficient of T(φq)
（４） if(d[i]≧s)
（５） the i-th coefficient of T(φq)←0
（６） for(j=0;j<「logsd[i]」;j++)
（７） e[j]←d[i]％s
（８） d[i]←(d[i]-e[j])％s
（９） End for
（10） U(φq)←１
（11） for(j=0;j<「logsd[i]」;j++)
（12） U(φq)←{U(φq)*e[j]*h'(φq)j}％(φqk-1)
（13） End for
（14） T(φq)←{T(φq)+U(φq)*φqi}％(φqk-1)
（15） End if
（16） End for
（17）End until
【０１０２】
次いで、電子計算機は、第２の演算手段として機能し、Ｑ[ｉ]＝ｄ[ｉ]Ｑの演算を行う（ステップＳ２０８）。
【０１０３】
ステップＳ２０８でも、バイナリ法を用いており、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<k;i++)
（２） Q[i]←O
（３） for(j=0;d[i]!=0;i++)
（４） if(d[i]＆1)
（５） Q[i]←Q[i]+T[j]
（６） End if
（７） d[i]←d[i]/2
（８） End for
（９）End for
【０１０４】
次いで、電子計算機は、合成手段として機能し、ステップＳ２０８で演算したＱ[ｉ]を用いて、スカラー倍算ｎＱを、
【０１０５】
【数３１】
によって合成する（ステップＳ２０９）。
【０１０６】
ステップＳ２０９では、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<k;i++)
（２） Z←Z+φqi(Q[i])
（３）End for
【０１０７】
そして、電子計算機は、出力手段として機能し、スカラー倍算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ２１０）、スカラー倍算の演算プログラムを終了している。
【０１０８】
Ｄdmax(χ)及び多項式ｈ(φq,χ)は、楕円曲線の有限体Ｆqの位数ｑ(χ)、＃Ｅ(Ｆq)を割り切る素数位数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)があらかじめ与えられていることから、あらかじめ特定でき、ｑ(χ)、ｒ(χ)及びｔ(χ)とともに、Ｄdmax(χ)と多項式ｈ(φq,χ)をスカラー倍算の演算プログラムに組み込んでもよいし、ｒ(χ)及びｔ(χ)を用いて以下の補助プログラムによって、Ｄdmax(χ)と多項式ｈ(φq,χ)を求めてもよい。
【０１０９】
電子計算機は、補助プログラムを起動させると、図４に示すように、はじめに、入力手段として機能し、ｒ(χ)とｔ(χ)が入力される（ステップＳ２２１）。
【０１１０】
次いで、電子計算機は、展開手段として機能し、入力されたｔ(χ)を用いて、ｔ(χ)−１＝ｓ(χ)として、ｒ(χ)を、
【０１１１】
【数３２】
とｓ(χ)進展開する（ステップＳ２２２）。ここで、ｉの大きさは、ｒ(χ)及びｓ(χ)から自動的に決定される。ステップＳ２２２では、ｓ(χ)進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） Di(χ)←r(χ)％s(χ)
（３） r(χ)←(r(χ)-Di(χ))/s(χ)
（４）End for
【０１１２】
次いで、電子計算機は、抽出手段として機能し、deg(Ｄi(χ))が最大のものを抽出して、Ｄdmax(χ)として出力する（ステップＳ２２３）。
【０１１３】
次いで、電子計算機は、演算手段として機能し、
【０１１４】
【数３３】
の演算を行って多項式ｈ(φq,χ)を特定し、出力している（ステップＳ２２４）。このようにして、電子計算機では、補助プログラムを用いてＤdmax(χ)及び多項式ｈ(φq,χ)を求めることができる。
【０１１５】
また、楕円曲線の有限体Ｆqの位数ｑ、＃Ｅ(Ｆq)を割り切る素数位数ｒ、フロベニウス自己準同型写像φqのトレースｔが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｔ(χ)とあらかじめ特定されているとともに、ｒ(χ)をｔ(χ)−１進展開することにより
[ｒ(χ)]Ｑ＝Σ[Ｄi(χ)(ｔ(χ)−１)i]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)
として表されるＤi(χ)において最高次数dmaxとなるＤi(χ)が複数存在する場合には、最高次数dmaxの項であるχdmaxの係数をＴdmax(φq)として、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を特定し、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たす整数のスカラーｖ及びｇ(φq)を拡張ユークリッドの互除法により特定し、
[Ｔdmax(φq)χdmax]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)−[Ｔdmax(φq)χdmax]Ｑ
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)と、ｇ(φq)を用い、φqkＱ＝Ｑに基づいて、
[ｖχdmax]Ｑ＝[ｇ(φq)ｆ(φq,χ)]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、このｈ(φq,χ)のφqに関する定数項ｈ(０,χ)が、
[ｖχdmax−ｈ(０,χ)]Ｑ＝[ｈ(φq,χ)−ｈ(０,χ)]Ｑ
を満たすことを用いることにより、スカラー倍算ｎＱをより高速化することができる。
【０１１６】
すなわち、χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)とし、スカラーｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(φq,ａ)−ｈ(０,ａ)を用いることにより、演算回数を削減している。
【０１１７】
ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)が特定されている場合のスカラー倍算ｎＱでは、スカラー倍算の演算プログラムを実行させて電子計算機をスカラー倍算機として機能させる際に、図５に示すように、はじめに、スカラーｎと、χ＝ａとしてスカラーｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)と、有理点Ｑ∈Ｇ⊂Ｅ(Ｆqk)が入力される（ステップＳ３０１）。この場合、電子計算機は、入力手段として機能する。
【０１１８】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←Ｏ）する（ステップＳ３０２）。そして、第１の演算手段として機能し、入力されたＱに対して、２jＱをあらかじめ演算しておく（ステップＳ３０３）。ステップＳ３０３の演算はステップＳ１０３の演算とアルゴリズムは同じであるので、説明は省略する。
【０１１９】
次いで、電子計算機は、第１の展開手段として機能し、スカラーｎを、
【０１２０】
【数３４】
とｓ'進展開する（ステップＳ３０４）。ステップＳ３０４でのｓ'進展開は、ステップＳ２０４でのｓ進展開とアルゴリズムは同じであるので、説明は省略する。
【０１２１】
次いで、電子計算機は、第２の展開手段として機能し、スカラーｎを、ｈ'(φq)及びｃ[ｉ]を用いながら、
【０１２２】
【数３５】
とφq進展開する（ステップＳ３０５）。ステップＳ３０５でのφq進展開は、スカラーｓ'(＝ｖａdmax−ｈ(０,ａ)）が、ステップＳ２０５でのスカラーｓ(＝Ｄdmax(ａ))とは異なる点以外では、ステップＳ２０５でのｓ進展開とアルゴリズムは同じであるため、詳細な説明は省略する。
【０１２３】
ステップＳ３０５でのφq進展開でも、φq進展開の係数がｓ'よりも大きくなることがある。このように、φq進展開の係数がｓ'よりも大きい場合（ステップＳ３０６：ＮＯ）には、φq進展開の係数に対してｓ'の剰余をとることにより、φq進展開の係数がｓ'よりも小さくなるように調整している（ステップＳ３０７）。このステップＳ３０７での演算も、スカラーｓ'(＝ｖａdmax−ｈ(０,ａ)）が、ステップＳ２０７でのスカラーｓ(＝Ｄdmax(ａ))とは異なる点以外では、ステップＳ２０７での演算とアルゴリズムは同じであるため、詳細な説明は省略する。この場合、電子計算機は、ステップＳ３０６において比較手段として機能し、ステップＳ３０７において調整手段として機能する。
【０１２４】
次いで、電子計算機は、第２の演算手段として機能し、Ｑ[ｉ]＝ｄ[ｉ]Ｑの演算を行う（ステップＳ３０８）。ステップＳ３０８でも、バイナリ法を用いており、ステップＳ３０８の演算もステップＳ２０８の演算とアルゴリズムは同じであるので、説明は省略する。
【０１２５】
次いで、電子計算機は、合成手段として機能し、ステップＳ３０８で演算したＱ[ｉ]を用いて、スカラー倍算ｎＱを、
【０１２６】
【数３６】
によって合成する（ステップＳ３０９）。ステップＳ３０９の演算もステップＳ２０９の演算とアルゴリズムは同じであるので、説明は省略する。
【０１２７】
そして、電子計算機は、出力手段として機能し、スカラー倍算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ３１０）、スカラー倍算の演算プログラムを終了している。
【０１２８】
多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)は、楕円曲線の有限体Ｆqの位数ｑ(χ)、＃Ｅ(Ｆq)を割り切る素数位数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)があらかじめ与えられていることから、あらかじめ特定できるので、ｑ(χ)、ｒ(χ)及びｔ(χ)とともに、多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)をスカラー倍算の演算プログラムに組み込んでもよいし、ｒ(χ)及びｔ(χ)を用いて以下の補助プログラムによって、多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)を求めてもよい。
【０１２９】
電子計算機は、補助プログラムを起動させると、図６に示すように、はじめに、入力手段として機能し、ｒ(χ)、ｔ(χ)及びｍ(χ)が入力される（ステップＳ３２１）。ここで、ｍ(χ)はｒ(χ)｜ｍ(χ)を満たす最小次数の多項式であり、一般的には円周等分多項式が用いられる。
【０１３０】
次いで、電子計算機は、展開手段として機能し、入力されたｔ(χ)を用いて、ｔ(χ)−１＝ｓ(χ)として、ｒ(χ)を、
【０１３１】
【数３７】
とｓ(χ)進展開する（ステップＳ３２２）。ここで、ｉの大きさは、ｒ(χ)及びｓ(χ)から自動的に決定される。ステップＳ３２２では、ｓ(χ)進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） Di(χ)←r(χ)％s(χ)
（３） r(χ)←(r(χ)-Di(χ))/s(χ)
（４）End for
【０１３２】
次いで、電子計算機は、第１の特定手段として機能し、deg(Ｄi(χ))の最大の次数dmaxの項であるχdmaxの係数を抽出して、抽出された係数の和をＴ(φq,χ)とし、それ以外の和をＵ(φq,χ)とする（ステップＳ３２３）。ステップＳ３２３では、電子計算機は、具体的に以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） T(φq,χ)←0,U(φq,χ)←0
（３） if(deg(Di(χ))=dmax)
（４） T(φq,χ)←T(φq,χ)+Di(χ)φqi
（５） End if
（６） else
（７） U(φq,χ)←U(φq,χ)+Di(χ)φqi
（８） End else
（９）End for
【０１３３】
次いで、電子計算機は、第２の特定手段として機能し、ステップＳ３２３で特定したＴ(φq,χ)の最高次数係数Ｔdmax(φq)を特定する（ステップＳ３２４）。
【０１３４】
次いで、電子計算機は、第３の特定手段として機能し、ステップＳ３２４で特定した最高次数係数Ｔdmax(φq)を用い、
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を特定する（ステップＳ３２５）。ステップＳ３２５では、電子計算機は、具体的に以下のアルゴリズムを実行している。
（１）W(φq)←gcd(Tdmax(φq),m(φq))
（２）V(φq)←W(φq)
【０１３５】
次いで、電子計算機は、第４の特定手段として機能し、ステップＳ３２５で特定したＶ(φq)を用い、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たすスカラーｖ及びｇ(φq)を、拡張ユークリッドの互除法によって特定する（ステップＳ３２６）。この拡張ユークリッドの互除法は、一般的なライブラリにおいて準備されている既知のプログラムに基づいて実行されるものであり、特に、ｇ(φq)の係数及びスカラーｖが小さくなるようにしておくことが望ましい。
【０１３６】
次いで、電子計算機は、ステップＳ３２６で特定したｇ(φq)を用い、
【０１３７】
【数３８】
の演算を行って多項式ｈ(φq,χ)を特定し（ステップＳ３２７）、多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)を出力している（ステップＳ３２８）。このようにして、電子計算機では、補助プログラムを用いて多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)を求めることができる。この場合、電子計算機は、ステップＳ３２７において演算手段として機能し、ステップＳ３２８において出力手段として機能する。
【０１３８】
以下において、べき乗算の演算プログラムについて説明する。まず、ｔ−１進展開によるべき乗算Ａnについて説明する。
【０１３９】
べき乗算の演算プログラムを実行させて電子計算機をべき乗算として機能させる際に、図７に示すように、はじめに、べき数ｎと、位数ｑとＦqkの素数位数ｒとの差分ｓと、元Ａ∈Ｈ⊂Ｆqkが入力される（ステップＳ４０１）。この場合、電子計算機は、入力手段として機能する。
【０１４０】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←１）する（ステップＳ４０２）。そして、第１の演算手段として機能し、Ｘ^{Ｙ}はＸＹを表すものとして、入力された元Ａに対して、Ａ^{２j}をあらかじめ演算しておく（ステップＳ４０３）。
【０１４１】
ステップＳ４０３では、Ｔ[ｊ]＝Ａ^{２j}として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(j=0;J<「log2s」;j++)
（２） T[j]←A
（３） A←A*A
（４）End for
【０１４２】
次いで、電子計算機は、展開手段として機能し、べき数ｎを、差分ｓにより
【０１４３】
【数３９】
とｓ進展開する（ステップＳ４０４）。ここで、ｉの大きさは、ｎの大きさによって決定するものである。
【０１４４】
ステップＳ４０４では、ｓ進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） c[i]←n％s
（３） n←(n-c[i])/s
（４）End for
ここで、「％」は、剰余をとっていることを表している。
【０１４５】
次いで、本実施形態では、電子計算機は、第２の演算手段として機能し、Ａ[ｉ]＝Ａｃ[ｉ]の演算を行う（ステップＳ４０５）。
【０１４６】
ステップＳ４０５では、バイナリ法を用いており、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） A[i]←1
（３） for(j=0;c[i]!=0;i++)
（４） if(c[i]＆1)
（５） A[i]←A[i]*T[j]
（６） End if
（７） c[i]←c[i]/2
（８） End for
（９）End for
【０１４７】
次いで、電子計算機は、合成手段として機能し、ステップＳ４０５で演算したＡ[ｉ]を用いて、べき乗算Ａnを、
【０１４８】
【数４０】
によって合成する（ステップＳ４０６）。
【０１４９】
ステップＳ４０６では、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） Z←Z＊φqi(A[i])
（３）End for
【０１５０】
そして、電子計算機は、出力手段として機能し、べき乗算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ４０７）、べき乗算の演算プログラムを終了している。
【０１５１】
また、位数ｑ、素数位数ｒ、差分ｓが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｓ(χ)で与えられている場合には、ｒ(χ)をｓ(χ)進展開することにより
Ａ^{ｒ(χ)}＝ΠＡ^{Ｄi(χ)ｓ(χ)i}＝Ａ^{ΣＤi(χ)ｑi}
として表されるＤi(χ)のうちでもっとも次数の高いものをＤdmax(χ)とし、
(Ａ^{Ｄdmax(χ)})^{ｑdmax}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi}＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(φq,χ)を用い、φqk(Ａ)＝Ａに基づいて、
Ａ^{Ｄdmax(χ)}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi−ｑdmax}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(φq,χ)と、Ｄdmax(χ)を用いることにより、スカラー倍算ｎＱをより高速化することができる。
【０１５２】
すなわち、Ｄdmax(χ)及び多項式ｈ(φq,χ)が特定されている場合には、χ＝ａとしてべき数ｎをＤdmax(ａ)進展開して、Ｄdmax(ａ)に換えてｈ(φq,ａ)を用いることにより、演算回数を削減している。
【０１５３】
Ｄdmax(χ)及び多項式ｈ(φq,χ)が特定されている場合のべき乗算ｎＱでは、べき乗算の演算プログラムを実行させて電子計算機をべき乗算機として機能させる際に、図８に示すように、はじめに、べき数ｎと、χ＝ａとしてｓ＝Ｄdmax(ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)と、元Ａ∈Ｈ⊂Ｆqkが入力される（ステップＳ５０１）。この場合、電子計算機は、入力手段として機能する。
【０１５４】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←１）する（ステップＳ５０２）。そして、第１の演算機能として、入力されたＡに対して、Ａ^{２j}をあらかじめ演算しておく（ステップＳ５０３）。ステップＳ５０３の演算はステップＳ４０３の演算とアルゴリズムは同じであるので、説明は省略する。
【０１５５】
次いで、電子計算機は、第１の展開手段として機能し、べき数ｎを、
【０１５６】
【数４１】
とｓ進展開する（ステップＳ５０４）。ステップＳ５０４でのｓ進展開は、ステップＳ４０４でのｓ進展開とアルゴリズムは同じであるので、説明は省略する。
【０１５７】
次いで、電子計算機は、第２の展開手段として機能し、べき数ｎを、ｈ'(ｑ)及びｃ[ｉ]を用いながら、
【０１５８】
【数４２】
とｑ進展開する（ステップＳ５０５）。
【０１５９】
ステップＳ５０５では、ｑ進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）T(q)←１
（２）for(i=0;i<「logsn」;i++)
（３） d[i]←c[i]
（４） if(d[i]≧s)
（５） for(j=0;j<「logsd[i]」;j++)
（６） e[j]←d[i]％s
（７） d[i]←(d[i]-e[j])％s
（８） End for
（９） U(q)←１
（10） for(j=0;j<「logsd[i]」;j++)
（11） U(q)←{U(q)*e[j]*h'(q)j}％(qk-1)
（12） End for
（13） T(q)←{T(q)+U(q)*h'(q)i}％(qk-1)
（14） End if
（15） else
（16） T(q)←{T(q)+d[i]*h'(q)i}％(qk-1)
（17） End else
（18）End for
【０１６０】
なお、べき数ｎをｑ進展開した場合に、ｑ進展開の係数がｓよりも大きくなることがある。このように、ｑ進展開の係数がｓよりも大きい場合（ステップＳ５０６：ＮＯ）には、ｑ進展開の係数に対してｓの剰余をとることにより、ｑ進展開の係数がｓよりも小さくなるように調整している（ステップＳ５０７）。この場合、電子計算機は、ステップＳ５０６において比較手段として機能し、ステップＳ５０７において調整手段として機能する。
【０１６１】
ステップＳ５０７では、電子計算機は、以下のアルゴリズムを実行している。
（１）until(∀d[i]＜ｓ)
（２） for(i=0;i<k-1;i++)
（３） d[i]←the i-th coefficient of T(q)
（４） if(d[i]≧s)
（５） the i-th coefficient of T(q)←0
（６） for(j=0;j<「logsd[i]」;j++)
（７） e[j]←d[i]％s
（８） d[i]←(d[i]-e[j])％s
（９） End for
（10） U(q)←１
（11） for(j=0;j<「logsd[i]」;j++)
（12） U(q)←{U(q)*e[j]*h'(q)j}％(qk-1)
（13） End for
（14） T(q)←{T(q)+U(q)*qi}％(qk-1)
（15） End if
（16） End for
（17）End until
【０１６２】
次いで、電子計算機は、第２の演算手段として機能し、Ａ[ｉ]＝Ａｄ[ｉ]の演算を行う（ステップＳ５０８）。
【０１６３】
ステップＳ５０８でも、バイナリ法を用いており、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<k;i++)
（２） A[i]←O
（３） for(j=0;d[i]!=0;i++)
（４） if(d[i]＆1)
（５） A[i]←A[i]*T[j]
（６） End if
（７） d[i]←d[i]/2
（８） End for
（９）End for
【０１６４】
次いで、電子計算機は、合成手段として機能し、ステップＳ５０８で演算したＡ[ｉ]を用いて、べき乗算Ａｎを、
【０１６５】
【数４３】
によって合成する（ステップＳ５０９）。
【０１６６】
ステップＳ５０９では、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<k;i++)
（２） Z←Z*φqi(A[i])
（３）End for
【０１６７】
そして、電子計算機は、出力手段として機能し、べき乗算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ５１０）、べき乗算の演算プログラムを終了している。
【０１６８】
Ｄdmax(χ)及び多項式ｈ(ｑ,χ)は、ｑ(χ)、ｒ(χ)及びｓ(χ)があらかじめ与えられていることから、あらかじめ特定でき、ｑ(χ)、ｒ(χ)及びｓ(χ)とともに、Ｄdmax(χ)と多項式ｈ(ｑ,χ)をべき乗算の演算プログラムに組み込んでもよいし、ｒ(χ)及びｓ(χ)を用いて以下の補助プログラムによって、Ｄdmax(χ)と多項式ｈ(ｑ,χ)を求めてもよい。
【０１６９】
電子計算機は、補助プログラムを起動させると、図９に示すように、はじめに、入力手段として機能し、ｒ(χ)とｓ(χ)が入力される（ステップＳ５２１）。
【０１７０】
次いで、電子計算機は、展開手段として機能し、入力されたｓ(χ)を用いて、ｒ(χ)を、
【０１７１】
【数４４】
とｓ(χ)進展開する（ステップＳ５２２）。ここで、ｉの大きさは、ｒ(χ)及びｓ(χ)から自動的に決定される。ステップＳ５２２では、ｓ(χ)進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） Di(χ)←r(χ)％s(χ)
（３） r(χ)←(r(χ)-Di(χ))/s(χ)
（４）End for
【０１７２】
次いで、電子計算機は、抽出手段として機能し、deg(Ｄi(χ))が最大のものを抽出して、Ｄdmax(χ)として出力する（ステップＳ５２３）。
【０１７３】
次いで、電子計算機は、演算手段として機能し、
【０１７４】
【数４５】
の演算を行って多項式ｈ(ｑ,χ)を特定し、出力している（ステップＳ５２４）。このようにして、電子計算機では、補助プログラムを用いてＤdmax(χ)及び多項式ｈ(ｑ,χ)を求めることができる。
【０１７５】
また、位数ｑ、素数位数ｒ及び差分ｓが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)及びｓ(χ)とあらかじめ特定されているとともに、ｒ(χ)をｓ(χ)進展開することにより
Ａ^{ｒ(χ)}＝ΠＡ^{Ｄi(χ)ｓ(χ)i}＝Ａ^{ΣＤi(χ)ｑi}
として表されるＤi(χ)において最高次数dmaxとなるＤi(χ)が複数存在する場合には、最高次数dmaxの項であるχdmaxの係数をＴdmax(ｑ)として、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を特定し、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たす整数のスカラーｖ及びｇ(ｑ)を拡張ユークリッドの互除法により特定し、
Ａ^{Ｔdmax(ｑ)χdmax}＝Ａ^{ΣＤi(χ)ｑi−Ｔdmax(ｑ)χdmax}
＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)と、ｇ(ｑ)を用い、φqk(Ａ)＝Ａに基づいて、
Ａ^{ｖχdmax}＝Ａ^{ｇ(ｑ)ｆ(ｑ,χ)}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、このｈ(ｑ,χ)のｑに関する定数項ｈ(０,χ)が、
Ａ^{ｖχdmax−ｈ(０,χ)}＝Ａ^{ｈ(ｑ,χ)−ｈ(０,χ)}
を満たすことを用いることにより、べき乗算Ａｎをより高速化することができる。
【０１７６】
すなわち、χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ)とし、べき数ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(ｑ,ａ)−ｈ(０,ａ)を用いることにより、演算回数を削減している。
【０１７７】
ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ)が特定されている場合のべき乗算Ａｎでは、べき乗算の演算プログラムを実行させて電子計算機をべき乗算機として機能させる際に、図１０に示すように、はじめに、べき数ｎと、χ＝ａとしてスカラーｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ)と、元Ａ∈Ｈ⊂Ｆqkが入力される（ステップＳ６０１）。この場合、電子計算機は、入力手段として機能する。
【０１７８】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←１）する（ステップＳ６０２）。そして、第１の演算手段として機能し、入力された元Ａに対して、Ａ^{２j}をあらかじめ演算しておく（ステップＳ６０３）。ステップＳ６０３の演算はステップＳ４０３の演算とアルゴリズムは同じであるので、説明は省略する。
【０１７９】
次いで、電子計算機は、第１の展開手段として機能し、スカラーｎを、
【０１８０】
【数４６】
とｓ'進展開する（ステップＳ６０４）。ステップＳ６０４でのｓ'進展開は、ステップＳ４０４でのｓ進展開とアルゴリズムは同じであるので、説明は省略する。
【０１８１】
次いで、電子計算機は、第２の展開手段として機能し、べき数ｎを、ｈ'(ｑ)及びｃ[ｉ]を用いながら、
【０１８２】
【数４７】
とｑ進展開する（ステップＳ６０５）。ステップＳ６０５でのｑ進展開は、スカラーｓ'(＝ｖａdmax−ｈ(０,ａ)）が、ステップＳ５０５でのスカラーｓ(＝Ｄdmax(ａ))とは異なる点以外では、ステップＳ５０５でのｓ進展開とアルゴリズムは同じであるため、詳細な説明は省略する。
【０１８３】
ステップＳ６０５でのｑ進展開でも、ｑ進展開の係数がｓ'よりも大きくなることがある。このように、ｑ進展開の係数がｓ'よりも大きい場合（ステップＳ６０６：ＮＯ）には、ｑ進展開の係数に対してｓ'の剰余をとることにより、ｑ進展開の係数がｓ'よりも小さくなるように調整している（ステップＳ６０７）。このステップＳ６０７での演算も、スカラーｓ'(＝ｖａdmax−ｈ(０,ａ)）が、ステップＳ５０７でのスカラーｓ(＝Ｄdmax(ａ))とは異なる点以外では、ステップＳ５０７での演算とアルゴリズムは同じであるため、詳細な説明は省略する。ここで、電子計算機は、ステップＳ６０６において比較手段と
して機能し、ステップＳ６０７において調整手段として機能する。
【０１８４】
次いで、電子計算機は、第２の演算手段として機能し、Ａ[ｉ]＝Ａｄ[ｉ]の演算を行う（ステップＳ６０８）。ステップＳ６０８でも、バイナリ法を用いており、ステップＳ６０８の演算もステップＳ５０８の演算とアルゴリズムは同じであるので、説明は省略する。
【０１８５】
次いで、電子計算機は、合成手段として機能し、ステップＳ６０８で演算したＡ[ｉ]を用いて、べき乗算Ａｎを、
【０１８６】
【数４８】
によって合成する（ステップＳ６０９）。ステップＳ６０９の演算もステップＳ５０９の演算とアルゴリズムは同じであるので、説明は省略する。
【０１８７】
そして、電子計算機は、出力手段として機能し、べき乗算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ６１０）、べき乗算の演算プログラムを終了している。
【０１８８】
多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)は、位数ｑ(χ)、素数位数ｒ(χ)及び差分ｓ(χ)があらかじめ与えられていることから、あらかじめ特定できるので、ｑ(χ)、ｒ(χ)及びｓ(χ)とともに、多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)をべき乗算の演算プログラムに組み込んでもよいし、ｒ(χ)及びｓ(χ)を用いて以下の補助プログラムによって、多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)を求めてもよい。
【０１８９】
電子計算機は、補助プログラムを起動させると、図１１に示すように、はじめに、入力手段として機能し、ｒ(χ)、ｓ(χ)及びｍ(χ)が入力される（ステップＳ６２１）。ここで、ｍ(χ)はｒ(χ)｜ｍ(χ)を満たす最小次数の多項式であり、一般的には円周等分多項式が用いられる。
【０１９０】
次いで、電子計算機は、展開手段として機能し、入力されたｓ(χ)を用いて、ｒ(χ)を、
【０１９１】
【数４９】
とｓ(χ)進展開する（ステップＳ６２２）。ここで、ｉの大きさは、ｒ(χ)及びｓ(χ)から自動的に決定される。ステップＳ６２２では、ｓ(χ)進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） Di(χ)←r(χ)％s(χ)
（３） r(χ)←(r(χ)-Di(χ))/s(χ)
（４）End for
【０１９２】
次いで、電子計算機は、第１の特定手段として機能し、deg(Ｄi(χ))の最大の次数dmaxの項であるχdmaxの係数を抽出して、抽出された係数の和をＴ(ｑ,χ)とし、それ以外の和をＵ(ｑ,χ)とする（ステップＳ６２３）。ステップＳ６２３では、電子計算機は、具体的に以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） T(q,χ)←0,U(q,χ)←0
（３） if(deg(Di(χ))=dmax)
（４） T(q,χ)←T(q,χ)+Di(χ)qi
（５） End if
（６） else
（７） U(q,χ)←U(q,χ)+Di(χ)qi
（８） End else
（９）End for
【０１９３】
次いで、電子計算機は、第２の特定手段として機能し、ステップＳ６２３で特定したＴ(ｑ,χ)の最高次数係数Ｔdmax(ｑ)を特定する（ステップＳ６２４）。
【０１９４】
次いで、電子計算機は、第３の特定手段として機能し、ステップＳ６２４で特定した最高次数係数Ｔdmax(ｑ)を用い、
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を特定する（ステップＳ６２５）。ステップＳ６２５では、電子計算機は、具体的に以下のアルゴリズムを実行している。
（１）W(q)←gcd(Tdmax(q),m(q))
（２）V(q)←W(q)
【０１９５】
次いで、電子計算機は、第４の特定手段として機能し、ステップＳ６２５で特定したＶ(ｑ)を用い、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たすスカラーｖ及びｇ(ｑ)を、拡張ユークリッドの互除法によって特定する（ステップＳ６２６）。この拡張ユークリッドの互除法は、一般的なライブラリにおいて準備されている既知のプログラムに基づいて実行されるものであり、特に、ｇ(ｑ)の係数及びスカラーｖが小さくなるようにしておくことが望ましい。
【０１９６】
次いで、電子計算機は、ステップＳ６２６で特定したｇ(ｑ)を用い、
【０１９７】
【数５０】
の演算を行って多項式ｈ(ｑ,χ)を特定し（ステップＳ６２７）、多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)を出力している（ステップＳ６２８）。このようにして、電子計算機では、補助プログラムを用いて多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)を求めることができる。この場合、電子計算機は、ステップＳ６２７において演算手段として機能し、ステップＳ６２８において出力手段として機能する。
【符号の説明】
【０１９８】
10 電子計算機
11 ＣＰＵ
12 記憶装置
13 メモリ装置
14 バス
15 入出力制御部
20 電気通信回線
30 クライアント装置
【技術分野】
【０００１】
本発明は、有理点Ｑのスカラーｎ倍算のｎを少なくともｔ−１進展開することによりスカラー倍算の演算を高速化したスカラー倍算の演算装置及び元Ａのｎ乗算のｎを少なくとも(ｑ−ｒ)進展開することによりべき乗算の演算を高速化したべき乗算の演算装置に関する。
【背景技術】
【０００２】
昨今、インターネットなどの電気通信回線を利用した情報ネットワーク技術が高度に発展し、インターネットによって様々な情報を取得するだけでなく、インターネットバンキングや行政機関への電子申請などのような各種のサービスが提供されてきている。
【０００３】
このようなサービスを利用する場合には、サービスの利用者が、成りすましや架空の人間などではなく、適正な利用者であることを確認するための認証処理が必要であり、信頼性の高い認証方法として、公開鍵と秘密鍵を用いる公開鍵暗号をベースとした電子認証技術がよく利用されている。
【０００４】
しかしながら、公開鍵暗号方式の電子認証では、公開鍵あるいは秘密鍵が漏洩した場合には直ちに公開鍵と秘密鍵を変更する必要があり、公開鍵及び秘密鍵の管理を慎重に行わなければならないとともに、必要に応じて新たな公開鍵と秘密鍵の設定登録作業が生じるという繁雑さがあるため、最近では、利用者の氏名やメールアドレスのように利用者特有のＩＤを用いて電子認証を行うＩＤベース暗号が用いられることが多くなっている。
【０００５】
また、電子認証を行う認証装置によって利用者の個人認証を行った場合には、認証装置に利用者ごとの履歴が蓄積されることとなり、この履歴情報自体が利用者の個人情報であって、最近では、この履歴情報が漏洩することによる個人情報の漏洩のおそれが指摘されている。
【０００６】
そこで、認証装置では利用者の個人情報を利用して認証を行うのではなく、複数の利用者をひとまとまりのグループとして、このグループに所属していることを示すグループ署名を用いることにより、利用者を特定することなく認証を行うことによって、認証装置に個人情報が蓄積されることなく認証を可能としたグループ署名技術が提案されている。
【０００７】
このようなＩＤベース暗号やグループ署名における所用の演算には、楕円曲線上の有理点の双線形写像を用いるペアリングと呼ばれる手法が用いられている。ペアリングとは、たとえば、Ｐを素体Ｆq上の有理点、Ｑをｋ次拡大体Ｆqk上の有理点として、ＰとＱとを入力して拡大体Ｆ*qkの元ｚが出力されるとき、ａ倍のＰと、ｂ倍のＱを入力するとｚのab乗が出力される演算である。なお、ここで、「ｋ」を埋込み次数と呼び、「Ｆ*qk」は、正しくは、以下の表示であるが、表示の制限上、「Ｆ*qk」と表示している。
【０００８】
【数１３】
【０００９】
ＩＤベース暗号における暗号化あるいは復号の処理や、グループ署名における認証処理では、できるだけ短時間で実行されることが求められている。特に、ペアリングに基づく暗号方式などにおいてはスカラー倍算及びべき乗算が数多く実行されているため、これらの演算を高速に実行することが求められている。
【００１０】
そのため、従来より、スカラー倍算やべき乗算をバイナリ法やWindow法などを用いて高速化することが行われている。
【００１１】
また、拡大体の元Ａ∈Ｆqkのべき乗Ａnを演算する場合には、フロベニウス写像φq：Ａ→Ａqを用いることによって演算回数を削減することにより高速化を図ることも行われている。
【００１２】
また、スカラー倍算においても、写像を利用することにより演算回数を削減して高速化を図る手法が提案されている(例えば、特許文献１、特許文献２参照。)。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００４−２７１７９２号公報
【特許文献２】特開２００７−４１４６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、写像を利用して高速化を図る周知の高速化手段では、スカラー倍算におけるスカラーｎ、またはべき乗算における乗数ｎが位数ｑを大きく上回る場合(ｎ＞＞ｑ)にはきわめて有効であるもの、有限体Ｆqの位数ｑより大きく上回ることのないスカラーｎ及び乗数ｎに対しては、高速化手段を用いずに直接的にスカラー倍算及びべき乗算を実行した場合と比較して顕著な効果が見いだせないものであった。
【００１５】
特に、ＩＤベース暗号における暗号化あるいは復号の処理や、グループ署名における認証処理においては、スカラーｎを用いたスカラー倍算あるいは乗数ｎを用いたべき乗算が必要な場合に、スカラーｎあるいは乗数ｎが、有限体Ｆqの位数ｑより大きく上回ることのない場合が多く、周知の高速化手段を用いても効果的な高速化が期待できなかった。
【００１６】
本発明者らはこのような現状に鑑み、スカラーｎあるいは乗数ｎが有限体Ｆqの位数ｑより大きく上回ることのない場合であっても、スカラー倍算あるいはべき乗算を高速に実行できる演算方法の研究開発を行って、本発明を成すに至ったものである。
【課題を解決するための手段】
【００１７】
本発明のスカラー倍算の演算装置では、
楕円曲線をＥ／Ｆq＝ｘ3＋ａｘ＋ｂ−ｙ2＝０，ａ∈Ｆq，ｂ∈Ｆqとし、
Ｅ(Ｆq)を有限体Ｆqで定義される楕円曲線の有理点が成す加法群、
Ｅ(Ｆqk)を有限体Ｆqの拡大体Ｆqkで定義される楕円曲線の有理点が成す加法群、
φqを有限体Ｆqに関する有理点のフロベニウス自己準同型写像、
ｔをフロベニウス自己準同型写像φqのトレース、
ｒをＥ(Ｆq)の位数＃Ｅ(Ｆq)＝ｑ＋１−ｔを割り切る素数位数、
Ｅ[ｒ]を位数が素数ｒである有理点の集合、
[ｊ]を有理点をｊ倍する写像、
Ｇを
Ｇ＝Ｅ[r]∩Ker(φq−[ｑ])
を満たすＥ(Ｆqk)に含まれる有理点の集合として、
非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算を、記憶手段を備えた電子計算機により演算するスカラー倍算の演算装置において、
前記非負整数ｎの値、前記トレースｔの値、及び、Ｑ∈Ｇ⊂Ｅ(Ｆqk)により表される有理点Ｑの値を前記記憶手段に入力して記憶させる入力手段と、
演算結果Ｚを記憶する前記記憶手段を初期化する初期化手段と、
Ｇの有理点Ｑに対し、
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑ
が成り立つことにより、
ｓ＝ｔ−１として、前記ｎをｓ進展開した次式に基づいて、
【数１４】
c[i]←n％s及びn←(n-c[i])/sにより表される代入演算をｉ＝０から所定回繰り返し行って各係数c[i]及び非負整数ｎの値を前記記憶手段に記憶する展開手段と、
前記記憶手段から前記有理点Ｑ及び前記係数ｃ［ｉ］を読み出して、Ｑ［ｉ］＝ｃ［ｉ］Ｑにより表される演算をｉ＝０から所定回繰り返し行って各Ｑ［ｉ］の値を前記記憶手段に記憶する演算手段と、
ｔ-１に換えて有理点に対するフロベニウス自己準同型写像φqを用いて表される次式のスカラー倍算ｎＱに基づいて、
【数１５】
前記記憶手段からＱ［ｉ］及び演算結果Ｚを読み出し、Z←Z+φqi(Q[i])により表される代入演算をｉ＝０から所定回繰り返し行ってスカラー倍算の演算結果Ｚを前記記憶手段に記憶する合成手段と、
を有するものである。
【００１８】
さらに、本発明のスカラー倍算の演算装置では、
前記楕円曲線の有限体Ｆqの位数ｑ、＃Ｅ(Ｆq)を割り切る素数位数ｒ、フロベニウス自己準同型写像φqのトレースｔが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｔ(χ)で与えられている場合に、
前記ｑ(χ)、ｒ(χ)、ｔ(χ)の各値を入力して前記記憶手段に記憶する補助入力手段と、
前記記憶手段からｒ(χ)及びｔ(χ)の値を読み出して、前記ｓ（χ）＝ｔ（χ）−１として、ｒ(χ)をｓ（χ）進展開した次式に基づいて、
【数１６】
Di(χ)←r(χ)％s(χ)及びr(χ)←(r(χ)-Di(χ))/s(χ)により表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返し行って、各係数Ｄｉ（χ）及びｒ（χ）の値を前記記憶手段に記憶する補助展開手段と、
前記記憶された係数Ｄｉ（χ）のうち、deg（Ｄｉ（χ））が最大のものをＤｄｍａｘ（χ）として抽出し、前記記憶手段に記憶する補助抽出手段と、
前記記憶手段からＤdmax(χ)、Ｄi(χ)、Ｑの値を読み出して、
φqdmax([Ｄdmax(χ)]Ｑ)＝Σφqi([Ｄi(χ)]Ｑ)−φqdmax([Ｄdmax(χ)]Ｑ)
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)を用い、φqkＱ＝Ｑに基づいて
[Ｄdmax(χ)]Ｑ＝[ｆ(φq,χ)φq-dmax]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、前記多項式ｈ(φq,χ)の値を前記記憶手段に記憶する補助特定手段と、
前記ｓ進展開をχ＝ａとしてｓ＝Ｄdmax(ａ)からなるＤdmax(ａ)進展開に置換え、前記Ｄdmax(ａ)に換えて前記多項式ｈ(φq,ａ)を用いる手段と、を有するものである。
【００１９】
しかも、本発明のスカラー倍算の演算装置では、
前記係数Ｄｉ（χ）において最高次数dmaxとなる係数Ｄｉ（χ）が複数存在する場合に、
前記補助入力手段は、ｒ（χ）｜ｍ（χ）を満たすｍ（χ）の値を入力して前記記憶手段に記憶する手段を更に含み、
deg（Ｄｉ(χ)）の最高次数dmaxの項であるχdmaxの係数をＴdmax(φq)として、前記記憶手段から係数Ｄｉ（χ）を読み出し、前記記憶手段にT(φq,χ)及びU(φq,χ)を初期値を０として割り当て、deg(Di(χ))=dmaxとなる場合にT(φq,χ)←T(φq,χ)+Di(χ)φqi、その他の場合にU(φq,χ)←U(φq,χ)+Di(χ)φqiにより表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返し行って、Ｔ(φq,χ)及びＵ(φq,χ)の値を前記記憶手段に記憶し、最高次数係数Ｔdmax(φq)を特定する第２の補助特定手段と、
前記記憶手段からｍ（χ）及びＲ（χ）の値を読み出して、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を、W(φq)←gcd(Tdmax(φq),m(φq))及びV(φq)←W(φq)により表される代入演算を行って特定し、前記Ｖ(φq)の値を前記記憶手段に記憶する第３の補助特定手段と、
前記記憶手段からＶ(φq)及びｍ(φq)の値を読み出して、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たす整数のスカラーｖ及びｇ(φq)を拡張ユークリッドの互除法により特定し、前記スカラーｖ及びｇ(φq)の値を前記記憶手段に記憶する第４の補助特定手段と、
前記補助特定手段に代えて、前記記憶手段からＴdmax(φq)、χdmax、Ｄi(χ)、Ｑの各値を読み出して、
[Ｔdmax(φq)χdmax]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)−[Ｔdmax(φq)χdmax]Ｑ
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)と、前記ｇ(φq)を用い、φqkＱ＝Ｑに基づいて、
[ｖχdmax]Ｑ＝[ｇ(φq)ｆ(φq,χ)]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、前記多項式ｈ(φq,χ)の値を前記記憶手段に記憶する第５の補助特定手段と、
前記記憶手段から前記ｈ(φq,χ)の値を読み出して、
このｈ(φq,χ)のφqに関する定数項ｈ(０,χ)が、
[ｖχdmax−ｈ(０,χ)]Ｑ＝[ｈ(φq,χ)−ｈ(０,χ)]Ｑ
を満たすことを用いて、
χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)により表される演算を行ってｓ'、ｈ'(φq)の値を前記記憶手段に記憶し、
ｔ-１進展開した前記ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(φq,ａ)−ｈ(０,ａ)を用いる手段と、を有するものである。
【００２０】
また、本発明のべき乗算の演算装置では、
Ｆqkを位数ｑの有限体Ｆqのｋ次拡大体、
ＨをＦqkの素数位数ｒの部分乗法群、
φqを有限体Ｆqに関する元のフロベニウス自己準同型写像として、
非負整数ｎに対するＨの元Ａのｎ乗算を行うべき乗算を、記憶手段を備えた電子計算機により演算する演算装置において、
前記非負整数nの値、前記位数ｑの値、前記Ｆqkの素数位数ｒの値、Ａ∈Ｈ⊂Ｆqkにより表される元Ａの値を入力して前記記憶手段に記憶する入力手段と、
演算結果Ｚを記憶する前記記憶手段を初期化する初期化手段と、
前記位数ｑ、前記元Ａの値を前記記憶手段から読み出して、前記ｑとｒの差分をｓ＝ｑ−ｒとし、T[j]←A及びA←A*Aにより表される代入演算を、j＝０からj<「log2s」まで繰り返して行って前記T[j]及び前記Aの値を前記記憶手段に記憶する第１の演算手段と、
前記記憶手段から前記ｎ及び差分ｓの値を読み出して、差分ｓにより展開した次式に基づいて、
【数１７】
c[i]←n％s及びn←(n-c[i])/sにより表される代入演算をｉ＝０から所定回繰り返して行い、各係数c[i]及び非負整数ｎの値を前記記憶手段に記憶する展開手段と、
前記記憶手段からc[i]及び前記ｎの値を読み出して、Ａ［ｉ］＝Ａｃ［ｉ］に基づいて、Ａ［ｉ］＝１に初期化し、c[i]＆1である場合にA[i]←A[i]*T[j]、c[i]←c[i]/2により表される代入演算を、ｉ＝０から所定回繰り返して行い、前記記憶手段にA[i]及びc[i]の値を記憶する第２の演算手段と、
前記記憶手段から各Ａ［ｉ］を読み出し、次式に基づいて、
【数１８】
Z←Z＊φqi(A[i])により表されるべき乗演算を、ｉ＝０から所定回繰り返して行い、計算結果Ｚとして前記記憶手段に記憶する合成手段と、を有するものである。
【００２１】
さらに、本発明のべき乗算の演算装置では、
Ｘ^{Ｙ}はＸＹであることを表すこととし、
前記位数ｑ、前記素数位数ｒ、前記ｓが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｓ(χ)で与えられている場合に、
前記ｑ(χ)、ｒ(χ)、ｓ(χ)の各値を入力して前記記憶手段に記憶する補助入力手段と、
前記記憶手段からｒ(χ)及びｓ(χ)を読み出して、前記ｓ（χ）を用いて前記ｒ（χ）をｓ（χ）進展開した次式に基づいて、
【数１９】
Di(χ)←r(χ)％s(χ)及びr(χ)←(r(χ)-Di(χ))/s(χ)により表される代入演算を、ｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返して行い、前記係数Di(χ)及びr(χ)を前記記憶手段に記憶する補助展開手段と、
前記記憶された係数Ｄｉ（χ）のうち、deg（Ｄｉ（χ））が最大のものをＤｄｍａｘ（χ）として抽出し、前記記憶手段に記憶する補助抽出手段と、
前記記憶手段から前記Ｄｄｍａｘ（χ）、Ｄi(χ)、ｑの値を読み出して、
(Ａ^{Ｄdmax(χ)})^{ｑdmax}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi}＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)を用い、φqk(Ａ)＝Ａに基づいて
Ａ^{Ｄdmax(χ)}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi−ｑdmax}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、前記多項式ｈ(ｑ,χ)の値を前記記憶手段に記憶する補助特定手段と、
前記ｓ進展開した前記ｎを、χ＝ａとしてｓ＝Ｄdmax(ａ)からなるＤdmax(ａ)進展開に置き換え、前記Ｄdmax(ａ)に換えて前記多項式ｈ(ｑ,ａ)を用いる手段と、を有するものである。
【００２２】
しかも、本発明のべき乗算の演算装置では、
前記係数Ｄｉ（χ）において最高次数dmaxとなる係数Ｄｉ（χ）が複数存在する場合に、
前記補助記憶手段は、ｒ（χ）｜ｍ（χ）を満たすｍ（χ）の値を入力して前記記憶手段に記憶する手段を更に含み、
deg（Ｄi(χ)）の最高次数dmaxの項であるχdmaxの係数をＴdmax(ｑ)として、前記記憶手段から係数Ｄｉ（χ）を読み出し、前記記憶手段にT(ｑ,χ)及びU(ｑ,χ)を初期値を０として割り当て、deg(Di(χ))=dmaxとなる場合にT(ｑ,χ)←T(ｑ,χ)+Di(χ)ｑi、その他の場合にU(ｑ,χ)←U(ｑ,χ)+Di(χ)ｑiにより表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返して行ってＴ(ｑ,χ)及びＵ(ｑ,χ)の値を前記記憶手段に記憶し、最高次数係数Ｔdmax(ｑ)を特定する第２の補助特定手段と、
前記記憶手段からｍ（χ）及びＲ（χ）の値を読み出して、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を、W(ｑ)←gcd(Tdmax(ｑ),m(ｑ))及びV(ｑ)←W(ｑ)により表される演算を行って特定し、前記Ｖ(ｑ)の値を前記記憶手段に記憶する第３の補助特定手段と、
前記記憶手段からＶ(ｑ)及びｍ(ｑ)の値を読み出して、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たす整数のスカラーｖ及びｇ(ｑ)を拡張ユークリッドの互除法により特定し、前記スカラーｖ及びｇ(ｑ)の値を前記記憶手段に記憶する第４の補助特定手段と、
前記補助特定手段に代えて、前記記憶手段からＴdmax(ｑ)、χdmax、Ｄi(χ)、Ｑの各値を読み出して、
Ａ^{Ｔdmax(ｑ)χdmax}＝Ａ^{ΣＤi(χ)ｑi−Ｔdmax(ｑ)χdmax}
＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)と、前記ｇ(ｑ)を用い、φqk(Ａ)＝Ａに基づいて、
Ａ^{ｖχdmax}＝Ａ^{ｇ(ｑ)ｆ(ｑ,χ)}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、前記多項式ｈ(ｑ,χ)の値を前記記憶手段に記憶する第５の補助特定手段と、
前記記憶手段から前記ｈ(ｑ,χ)の値を読み出して、
このｈ(ｑ,χ)のｑに関する定数項ｈ(０,χ)が、
Ａ^{ｖχdmax−ｈ(０,χ)}＝Ａ^{ｈ(ｑ,χ)−ｈ(０,χ)}
を満たすことを用いて、
χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ) により表される演算を行ってｓ'、ｈ'(ｑ)の値を前記記憶手段に記憶し、ｓ進展開した前記ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(ｑ,ａ)−ｈ(０,ａ)を用いる手段と、を有するものである。
【発明の効果】
【００２３】
本発明は、フロベニウス自己準同型写像φｑ用いて演算回数を削減すものであって、特に、スカラー倍算の場合には、Ｇの有理点Ｑに対し、
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑ
が成り立つことにより、また、べき乗算の場合には、ｑとｒの差分をｓ＝ｑ−ｒとし、Ｈの非零元Ａに対し、
φq(Ａ)＝Ａq＝Ａs
が成り立つことにより、スカラーｎをｔ-１進展開、またはべき数ｎをｓ進展開して、ｔ-１に換えて有理点に対するフロベニウス自己準同型写像φqを用い、またはｓに換えて元に対するフロベニウス自己準同型写像φqを用いることにより、スカラー倍算におけるスカラーｎ、またはべき乗算における乗数ｎが位数ｑを大きく上回ることのない場合でも、演算回数を削減可能として演算速度を向上させることができる。
【００２４】
特に、ペアリングをベースとしたＩＤベース暗号やグループ署名などでは、ペアリングフレンドリ曲線と呼ばれるペアリングを利用可能な楕円曲線が用いられ、このペアリングフレンドリ曲線を用いる場合には、整数変数χを用いて位数ｑ(χ)、＃Ｅ(Ｆq)を割り切る素数位数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)があらかじめ与えられており、スカラー倍算の場合には、ｒ(χ)をｔ(χ)−１進展開するとともに、このｔ(χ)−１進展開の際に導入した係数Ｄi(χ)のうちでもっとも次数の高い係数Ｄi(χ)をＤdmax(χ)とし、このＤdmax(χ)を多項式ｈ(φq,χ)に置き換えることにより演算回数をさらに削減し、また、べき乗算の場合には、ｒ(χ)をｓ(χ)＝ｑ(χ)−ｒ(χ)進展開するとともに、このｓ(χ)進展開の際に導入した係数Ｄi(χ)のうちでもっとも次数の高い係数Ｄi(χ)をＤdmax(χ)とし、このＤdmax(χ)を多項式ｈ(φq,χ)に置き換えることにより演算回数をさらに削減し、それぞれ演算速度を向上させることができる。
【００２５】
しかも、最高次数dmaxとなるＤi(χ)が複数存在する場合には、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を特定するとともに、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たす整数のスカラーｖを用い、スカラー倍算の場合には、ｔ-１進展開したスカラーｎをＤdmax(χ)進展開する換わりにｖχdmax−ｈ(０,χ)進展開して、ｖχdmax−ｈ(０,χ)の換わりにｈ(ｑ,χ)−ｈ(０,χ)を用いることにより演算回数をさらに削減し、また、べき乗算の場合には、ｓ進展開したべき数ｎをＤdmax(χ)進展開する換わりにｖχdmax−ｈ(０,χ)進展開して、ｖχdmax−ｈ(０,χ)の換わりにｈ(ｑ,χ)−ｈ(０,χ)を用いることにより演算回数をさらに削減し、それぞれ演算速度を向上させることができる。
【図面の簡単な説明】
【００２６】
【図１】スカラー倍算の演算プログラム及びべき乗算の演算プログラムを備えた電子計算機の説明図。
【図２】スカラー倍算の演算プログラムのフローチャートである。
【図３】スカラー倍算の演算プログラムのフローチャートである。
【図４】Ｄdmax(χ)及び多項式ｈ(φq,χ)を求める補助プログラムのフローチャートである。
【図５】スカラー倍算の演算プログラムのフローチャートである。
【図６】多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)を求める補助プログラムのフローチャートである。
【図７】べき乗算の演算プログラムのフローチャートである。
【図８】べき乗算の演算プログラムのフローチャートである。
【図９】Ｄdmax(χ)及び多項式ｈ(ｑ,χ)を求める補助プログラムのフローチャートである。
【図１０】べき乗算の演算プログラムのフローチャートである。
【図１１】多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)を求める補助プログラムのフローチャートである。
【発明を実施するための形態】
【００２７】
本発明は、スカラー倍算の演算の高速化及びべき乗算の演算の高速化を目的としたものであり、スカラー倍算とべき乗算というように演算自体は異なるが、高速化のための手法は同じであり、それぞれ同じように演算回数が削減されることにより、演算の高速化を可能としているものである。最初にスカラー倍算について説明し、次いでべき乗算について説明する。
【００２８】
まず、楕円曲線をＥ／Ｆq＝ｘ3＋ａｘ＋ｂ−ｙ2＝０，ａ∈Ｆq，ｂ∈Ｆqとし、
Ｅ(Ｆq)：有限体Ｆqで定義される楕円曲線の有理点が成す加法群
Ｅ(Ｆqk)：有限体Ｆqの拡大体Ｆqkで定義される楕円曲線の有理点が成す加法群
φq：有限体Ｆqに関する有理点のフロベニウス自己準同型写像
ｔ：フロベニウス自己準同型写像φqのトレース
ｒ：Ｅ(Ｆq)の位数＃Ｅ(Ｆq)＝ｑ＋１−ｔを割り切る素数位数
Ｅ[ｒ]：位数が素数ｒである有理点の集合
[ｊ]：有理点をｊ倍する写像
Ｇ：Ｇ＝Ｅ[r]∩Ker(φq−[ｑ])を満たすＥ(Ｆqk)に含まれる有理点の集合
と定義する。
【００２９】
そして、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、すなわちｎＱを演算する。なお、本実施形態で想定するスカラー倍算はペアリングの演算の際に行われるものであり、一般的にスカラーｎは位数ｒを大きく超えるものではない。
【００３０】
また、ｒ＝ｑ＋１−ｔであることから、０≡ｑ＋１−ｔ(mod ｒ)である。
【００３１】
ここで、スカラーｎをｔ−１進展開すると、スカラーｎが位数ｒを大きく超えるものではないことから、
ｎ＝Ｃ1(ｔ−１)＋Ｃ0
または、
ｎ＝(ｔ−１)2＋Ｃ1(ｔ−１)＋Ｃ0
となる。
【００３２】
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑであるので、ｎ＝Ｃ1(ｔ−１)＋Ｃ0の場合、ｎＱは以下のようになる。
ｎＱ＝[Ｃ1(ｔ−１)＋Ｃ0]Ｑ
＝[Ｃ1ｑ]Ｑ＋[Ｃ0]Ｑ
＝φq([Ｃ1]Ｑ)＋[Ｃ0]Ｑ
【００３３】
また、ｎ＝(ｔ−１)2＋Ｃ1(ｔ−１)＋Ｃ0場合には、ｎＱは以下のようになる。
ｎＱ＝[(ｔ−１)2＋Ｃ1(ｔ−１)＋Ｃ0]Ｑ
＝[ｑ][ｑ]Ｑ＋[Ｃ1ｑ]Ｑ＋[Ｃ0]Ｑ
＝φq(φq(Ｑ))＋φq([Ｃ1]Ｑ)＋[Ｃ0]Ｑ
【００３４】
ここで、Ｃ1及びＣ0はｔ−１と同程度あるいはそれよりも小さくなり、しかも有理点のフロベニウス自己準同型写像を用いることができることによって演算回数を削減できる。したがって、スカラー倍算を高速化することができる。
【００３５】
また、通常、ペアリングの演算を行う場合には、既知のペアリングフレンドリ曲線が用いられており、特に、整数変数χを用いて位数ｑ(χ)、＃Ｅ(Ｆq)を割り切る素数位数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)があらかじめ与えられていることが多い。
【００３６】
ここで、[ｒ]Ｑ＝[ｑ＋１−ｔ]Ｑ＝Ｏであることを考慮しながら、ｒ(χ)をｔ(χ)−１で剰余をとる、すなわち、ｒ(χ)を、
[ｒ(χ)]Ｑ＝Σ[Ｄi(χ)(ｔ(χ)−１)i]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)
とｔ(χ)−１進展開して、Ｄi(χ)のうちでもっとも次数の高いものをＤdmax(χ)とする。
【００３７】
そして、
φqdmax([Ｄdmax(χ)]Ｑ)＝Σφqi([Ｄi(χ)]Ｑ)−φqdmax([Ｄdmax(χ)]Ｑ)
＝[ｆ(φq,χ)]Ｑ
として定義されるφqとχを変数とする２変数の多項式ｆ(φq,χ)を導入する。
【００３８】
さらに、φqkＱ＝Ｑに基づいて、
[Ｄdmax(χ)]Ｑ＝[ｆ(φq,χ)φq-dmax]Ｑ＝[ｈ(φq,χ)]Ｑ
として定義されるφqとχを変数とする２変数の多項式ｈ(φq,χ)を導入する。すなわち、この多項式ｈ(φq,χ)は、Ｄi(χ)のうちの最高次数のＤdmax(χ)を、φqとχを変数とする多項式ｈ(φq,χ)に置き換え可能であることを示しており、最高次数よりも小さい次数までの演算に抑えることができ、特に、χ＝ａとした場合には、ｔ-１進展開したスカラーｎをさらにＤdmax(ａ)進展開して、Ｄdmax(ａ)に換えてｈ(φq,ａ)を用いることによって演算回数を大きく削減でき、スカラー倍算を高速化することができる。
【００３９】
また、Ｄi(χ)のうちでもっとも次数の高いものが複数存在する場合には、最高次数をdmaxで表すものとし、最高次数dmaxの項であるχdmaxの係数をＴdmax(φq)として、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を特定する。ここで、多項式ｍ(χ)には円周等分多項式などを用いることができる。
【００４０】
そして、拡張ユークリッドの互除法を用いて、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たす整数のスカラーｖ及びｇ(φq)を特定し、
[Ｔdmax(φq)χdmax]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)−[Ｔdmax(φq)χdmax]Ｑ
＝[ｆ(φq,χ)]Ｑ
としてφqとχを変数とする２変数の多項式ｆ(φq,χ)を導入する。
【００４１】
さらに、ｇ(φq)を用い、φqkＱ＝Ｑに基づいて、
[ｖχdmax]Ｑ＝[ｇ(φq)ｆ(φq,χ)]Ｑ＝[ｈ(φq,χ)]Ｑ
としてφqとχを変数とする２変数の多項式ｈ(φq,χ)を導入する。
【００４２】
そして、このｈ(φq,χ)のφqに関する定数項ｈ(０,χ)が、
[ｖχdmax−ｈ(０,χ)]Ｑ＝[ｈ(φq,χ)−ｈ(０,χ)]Ｑ
を満たすことを用いて、χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)とし、ｔ-１進展開したスカラーｎをＤdmax(ａ)進展開する換わりに{ｖａdmax−ｈ(０,ａ)}進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(φq,ａ)−ｈ(０,ａ)を用いることにより演算回数を減できるので、スカラー倍算を高速化することができる。ここで、ｈ'(φq)は、φqとχの２変数の多項式ｈ(φq,χ)において、χ＝ａとしたことによりφqの１変数となっていることを示している。
【００４３】
ここまでスカラー倍算について説明したが、べき乗算の場合には、
Ｆqk：位数ｑの有限体Ｆqのｋ次拡大体
Ｈ：Ｆqkの素数位数ｒの部分乗法群
φq：有限体Ｆqに関する元のフロベニウス自己準同型写像
と定義して、非負整数ｎに対するＨの元Ａのｎ乗算を行うものであり、ｑとｒの差分をｓ＝ｑ−ｒとし、このｓをスカラー倍算におけるｔ−１に置き換えて上述の説明をべき乗算として読み換えるだけであり、詳細な説明は省略する。べき乗算の場合でも、最高次数部分の演算がより低い次数の演算に置き換えられることにより、演算回数を減してべき乗算を高速化することができる。
【００４４】
以下において、既知のペアリングフレンドリ曲線を用いながら具体例を説明する。
【００４５】
埋め込み次数８のペアリングフレンドリ曲線として、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が、
ｒ(χ)＝χ４−８χ２＋２５
ｔ(χ)＝(２χ３−１１χ＋１５)／１５
と与えられるものが知られている。
【００４６】
この場合、ｒ(χ)をｔ(χ)−１進展開して、フロベニウス準同型写像φqを用いることにより、
２ｒ(χ)＝(１５χ)φq＋(−５χ２＋５０)
０≡(１５χ)φq＋(−５χ２＋５０) (mod ｒ(χ))
となる。
【００４７】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝−５χ２＋５０
Ｄ1(χ)＝１５χ
となる。
【００４８】
このうち、Ｄ0(χ)が最も次数が高いので、Ｄ0(χ)以外を右辺に移すことにより、
−５χ２＋５０＝１５χφq
となり、式を整理することにより、
χ２−１０＝３χφq
が得られる。
【００４９】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらにχ２−１０進展開して、χ２−１０に換えて１５χφqを用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００５０】
他の具体体の埋め込み次数８のペアリングフレンドリ曲線として、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が
ｒ(χ)＝χ８−χ４＋１
ｔ(χ)＝χ５−χ＋１
と与えられた場合には、ｒ(χ)をｔ(χ)−１進展開し、フロベニウス準同型写像φqを用いることにより、
ｒ(χ)＝χ３φq＋１
０≡３φq＋１ (mod ｒ(χ))
となる。
【００５１】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝−１
Ｄ1(χ)＝χ３
となる。
【００５２】
このうち、Ｄ1(χ)が最も次数が高いので、Ｄ1(χ)φq以外を右辺に移すことにより、
χ３φq＝−１
となり、両辺にφ-1を掛けることで
χ３＝−φq-1
が得られる。
【００５３】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらにχ３進展開して、χ３に換えて−φq-1を用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００５４】
また、埋め込み次数１０のペアリングフレンドリ曲線の場合には、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が、
ｒ(χ)＝２５χ４＋２５χ３＋１５χ２＋５χ＋１
ｔ(χ)＝１０χ２＋５χ＋３
と与えられるものが知られている。
【００５５】
この場合、ｒ(χ)をｔ(χ)−１進展開して、フロベニウス準同型写像φqを用いることにより、
８ｒ(χ)＝２φq２−φq＋(５χ＋２)
０≡２φq２−φq＋(５χ＋２) (mod ｒ(χ))
となる。
【００５６】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝５χ＋２
Ｄ1(χ)＝−１
Ｄ2(χ)＝２
となる。
【００５７】
このうち、Ｄ0(χ)が最も次数が高いので、Ｄ0(χ)以外を右辺に移すことにより
５χ＋２＝−２φq２＋φq
が得られる。
【００５８】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらに５χ＋２進展開して、５χ＋２に換えて−２φq２＋φqを用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００５９】
また、埋め込み次数１２のペアリングフレンドリ曲線の場合には、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が、
ｒ(χ)＝３６χ４−３６χ３＋１８χ２−６χ＋１
ｔ(χ)＝６χ２＋１
と与えられるものが知られている。
【００６０】
この場合、ｒ(χ)をｔ(χ)−１進展開して、フロベニウス準同型写像φqを用いることにより、
ｒ(χ)＝φq２＋(−６χ＋３)φq＋(−６χ＋１)
０≡φq２＋(−６χ＋３)φq＋(−６χ＋１) (mod ｒ(χ))
となる。
【００６１】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝−６χ＋１
Ｄ1(χ)＝−６χ＋３
Ｄ2(χ)＝１
となる。
【００６２】
ここで、Ｄ0(χ)とＤ1(χ)が共に最も次数が高いので、Ｄ0(χ)とＤ1(χ)φqの最高次数を与えるχの項以外を右辺に移すことにより、
６χ(φq＋１)＝φq２＋３φq＋１
となる。
【００６３】
ここで、ｇ(φq)＝φq４−φq２＋１とすると、gcd(φq＋１,ｇ(φq))＝１を満たし、拡張ユークリッドの互除法より
(φq＋１)−１≡φq２(１−φq) (mod ｇ(φq))
が得られる。
【００６４】
したがって、両辺にφq２(１−φq)を乗じることにより、
６χ＝φq２(１−φq)(φq２＋３φq＋１)
が得られる。
【００６５】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらに６χ進展開して、６χに換えてφq２(１−φq)(φq２＋３φq＋１)を用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００６６】
より具体的な例として、χ＝８２５(１０ビット)とする。このとき、
ｒ＝１６６５６８１１７４６３０１(４４ビット)
ｔ＝４０８３７５１(２２ビット)
である。
【００６７】
この場合、
６χ＝４９５０(１３ビット)＝φq２(１−φq)(φq２＋３φq＋１)
となるので、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を行う場合には、有理点に対するフロベニウス自己準同型写像φｑを用いて１３ビット程度のスカラー倍算またはべき乗算に変換してから演算を行うこととなり、演算回数の大幅な削減が可能となっている
【００６８】
また、埋め込み次数１８のペアリングフレンドリ曲線の場合には、＃Ｅ(Ｆq)を割り切る素数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)が、
ｒ(χ)＝χ６＋３７χ３＋３４３
ｔ(χ)＝(χ４＋１６χ＋７)／７
と与えられるものが知られている。
【００６９】
この場合、ｒ(χ)をｔ(χ)−１進展開して、フロベニウス準同型写像φqを用いることにより、
ｒ(χ)＝（７χ２)φq＋(２１χ３＋３４３)
０≡（７χ２)φq＋(２１χ３＋３４３) (mod ｒ(χ))
となる。
【００７０】
したがって、Ｄi(χ)は、
Ｄ0(χ)＝２１χ３−３４３
Ｄ1(χ)＝７χ２
となる。
【００７１】
このうち、Ｄ0(χ)が最も次数が高いので、Ｄ0(χ)以外を右辺に移すことにより、
２１χ３−３４３＝７χ２φq
となり、式を整理することによって、
χ３−４９＝χ２φq
が得られる。
【００７２】
したがって、非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算、または非負整数ｎに対するＨの元Ａのｎ乗算を行わせるべき乗算を行う場合には、非負整数ｎに対してｎをｔ−１進展開し、さらにχ３−４９進展開して、χ３−４９に換えてχ２φqを用いることにより、Ｇの有理点のスカラーｎ倍算またはＨの元Ａのｎ乗算を、有理点に対するフロベニウス自己準同型写像φqを用いて演算を行うことができ、演算回数を減してべき乗算を高速化することができる。
【００７３】
最後に、スカラー倍算の演算プログラム及びべき乗算の演算プログラムについて詳説する。なお、スカラー倍算の演算プログラム及びべき乗算の演算プログラムは、本実施形態では、ＩＤベース暗号やグループ署名などを電子計算機で実行している際に、サブルーチンの一つとしてそれぞれ実行されるものである。
【００７４】
図１に示すように、スカラー倍算の演算プログラム及びべき乗算の演算プログラムを実行する電子計算機10は、演算処理を実行するＣＰＵ11と、所要のプログラムやデータを記憶したハードディスクなどの記憶装置12と、所要のプログラムを展開して実行可能とするとともに、演算にともなって生成されたデータを一時的に記憶するＲＡＭなどで構成されたメモリ装置13を備えている。図１中、14はバスである。本実施形態では、記憶装置12には、メインルーチンのプログラムやスカラー倍算の演算プログラム及びべき乗算の演算プログラムなどの各種プログラム、及びこれらのプログラムが使用するデータを記憶させている。
【００７５】
電子計算機10が、例えばグループ署名における認証装置として機能する場合には、インターネットなどの電気通信回線20に接続して、この電気通信回線20に接続されたクライアント装置30から送信されたグループ署名の署名データを受信し、メモリ装置13に一次的に記憶して、グループ署名用のプログラムに基づいて署名データの正当性を判定して認証処理を行っている。図１中、15は電子計算機10の入出力制御部である。
【００７６】
スカラー倍算の演算プログラム及びべき乗算の演算プログラムは、それぞれ署名データの正当性を判定する処理を行う際に数多く実行されるものであり、以下においては、スカラー倍算の演算プログラム、及びべき乗算の演算プログラムについてのみ説明する。なお、スカラー倍算の演算プログラム及びべき乗算の演算プログラムは、グループ署名の処理において用いられるものではなく、多種多様な用途で用いられるものであり、しかも、記憶装置12に記憶可能な形態である場合だけでなく、半導体回路として構成することによりいわゆるハードウェア実装される形態であってもよい。
【００７７】
まず、ｔ−１進展開によるスカラー倍算ｎＱについて説明する。
【００７８】
スカラー倍算の演算プログラムを実行させて電子計算機をスカラー倍算機として機能させる際に、図２に示すように、はじめに、スカラーｎと、Ｅ(Ｆq)のフロベニウス自己準同型写像のトレースｔと、有理点Ｑ∈Ｇ⊂Ｅ(Ｆqk)が入力される（ステップＳ１０１）。この場合、電子計算機は、入力手段として機能する。
【００７９】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←Ｏ）する（ステップＳ１０２）。そして、第１の演算手段として機能し、入力されたＱに対して、２jＱをあらかじめ演算しておく（ステップＳ１０３）。
【００８０】
ステップＳ１０３では、Ｔ[ｊ]＝２jＱとして、電子計算機は、以下のアルゴリズムを実行している。
（１）for(j=0;J<「log2s」;j++)
（２） T[j]←Q
（３） Q←Q+Q
（４）End for
ここで、(1)の「log2s」は、厳密には、
【００８１】
【数２６】
であるが、表記上の制限のため、「」を用いている。以下において、アルゴリズム中の「」は同じ意味に用いる。
【００８２】
次いで、ｔ−１＝ｓとして、電子計算機は、展開手段として機能し、スカラーｎを、
【００８３】
【数２７】
とｓ進展開する（ステップＳ１０４）。ここで、ｉの大きさは、ｎの大きさによって決定するものである。
【００８４】
ステップＳ１０４では、ｓ進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） c[i]←n％s
（３） n←(n-c[i])/s
（４）End for
ここで、「％」は、剰余をとっていることを表している。
【００８５】
次いで、本実施形態では、電子計算機は、第２の演算手段として機能し、Ｑ[ｉ]＝ｃ[ｉ]Ｑの演算を行う（ステップＳ１０５）。
【００８６】
ステップＳ１０５では、バイナリ法を用いており、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） Q[i]←O
（３） for(j=0;c[i]!=0;i++)
（４） if(c[i]＆1)
（５） Q[i]←Q[i]+T[j]
（６） End if
（７） c[i]←c[i]/2
（８） End for
（９）End for
【００８７】
次いで、電子計算機は、合成手段として機能し、ステップＳ１０５で演算したＱ[ｉ]を用いて、スカラー倍算ｎＱを、
【００８８】
【数２８】
によって合成する（ステップＳ１０６）。
【００８９】
ステップＳ１０６では、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） Z←Z+φqi(Q[i])
（３）End for
【００９０】
そして、電子計算機は、出力手段として機能し、スカラー倍算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ１０７）、スカラー倍算の演算プログラムを終了している。
【００９１】
また、楕円曲線の有限体Ｆqの位数ｑ、＃Ｅ(Ｆq)を割り切る素数位数ｒ、フロベニウス自己準同型写像φqのトレースｔが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｔ(χ)とあらかじめ特定されている場合には、ｒ(χ)をｔ(χ)−１進展開することにより
[ｒ(χ)]Ｑ＝Σ[Ｄi(χ)(ｔ(χ)−１)i]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)
として表されるＤi(χ)のうちでもっとも次数の高いものをＤdmax(χ)とし、
φqdmax([Ｄdmax(χ)]Ｑ)＝Σφqi([Ｄi(χ)]Ｑ)−φqdmax([Ｄdmax(χ)]Ｑ)
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)を用い、φqkＱ＝Ｑに基づいて
[Ｄdmax(χ)]Ｑ＝[ｆ(φq,χ)φq-dmax]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)と、Ｄdmax(χ)を用いることにより、スカラー倍算ｎＱをより高速化することができる。
【００９２】
すなわち、Ｄdmax(χ)及び多項式ｈ(φq,χ)が特定されている場合には、χ＝ａとしてスカラーｎをＤdmax(ａ)進展開して、Ｄdmax(ａ)に換えてｈ(φq,ａ)を用いることにより、演算回数を削減している。
【００９３】
Ｄdmax(χ)及び多項式ｈ(φq,χ)が特定されている場合のスカラー倍算ｎＱでは、スカラー倍算の演算プログラムを実行させて電子計算機をスカラー倍算機として機能させる際に、図３に示すように、はじめに、スカラーｎと、χ＝ａとしてｓ＝Ｄdmax(ａ)及びｈ'(φq)＝ｈ(φq,ａ)と、有理点Ｑ∈Ｇ⊂Ｅ(Ｆqk)が入力される（ステップＳ２０１）。この場合、電子計算機は、入力手段として機能する。
【００９４】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←Ｏ）する（ステップＳ２０２）。そして、第１の演算手段として機能し、入力されたＱに対して、２jＱをあらかじめ演算しておく（ステップＳ２０３）。ステップＳ２０３の演算はステップＳ１０３の演算とアルゴリズムは同じであるので、説明は省略する。
【００９５】
次いで、電子計算機は、第１の展開手段として機能し、スカラーｎを、
【００９６】
【数２９】
とｓ進展開する（ステップＳ２０４）。ステップＳ２０４でのｓ進展開は、ステップＳ１０４でのｓ進展開とアルゴリズムは同じであるので、説明は省略する。
【００９７】
次いで、電子計算機は、第２の展開手段として機能し、スカラーｎを、ｈ'(φq)及びｃ[ｉ]を用いながら、
【００９８】
【数３０】
とφq進展開する（ステップＳ２０５）。
【００９９】
ステップＳ２０５では、φq進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）T(φq)←１
（２）for(i=0;i<「logsn」;i++)
（３） d[i]←c[i]
（４） if(d[i]≧s)
（５） for(j=0;j<「logsd[i]」;j++)
（６） e[j]←d[i]％s
（７） d[i]←(d[i]-e[j])％s
（８） End for
（９） U(φq)←１
（10） for(j=0;j<「logsd[i]」;j++)
（11） U(φq)←{U(φq)*e[j]*h'(φq)j}％(φqk-1)
（12） End for
（13） T(φq)←{T(φq)+U(φq)*h'(φq)i}％(φqk-1)
（14） End if
（15） else
（16） T(φq)←{T(φq)+d[i]*h'(φq)i}％(φqk-1)
（17） End else
（18）End for
【０１００】
なお、スカラーｎをφq進展開した場合に、φq進展開の係数がｓよりも大きくなることがある。このように、φq進展開の係数がｓよりも大きい場合（ステップＳ２０６：ＮＯ）には、φq進展開の係数に対してｓの剰余をとることにより、φq進展開の係数がｓよりも小さくなるように調整している（ステップＳ２０７）。この場合、電子計算機は、ステップＳ２０６において比較手段として機能し、ステップＳ２０７において調整手段として機能する。
【０１０１】
ステップＳ２０７では、電子計算機は、以下のアルゴリズムを実行している。
（１）until(∀d[i]＜ｓ)
（２） for(i=0;i<k-1;i++)
（３） d[i]←the i-th coefficient of T(φq)
（４） if(d[i]≧s)
（５） the i-th coefficient of T(φq)←0
（６） for(j=0;j<「logsd[i]」;j++)
（７） e[j]←d[i]％s
（８） d[i]←(d[i]-e[j])％s
（９） End for
（10） U(φq)←１
（11） for(j=0;j<「logsd[i]」;j++)
（12） U(φq)←{U(φq)*e[j]*h'(φq)j}％(φqk-1)
（13） End for
（14） T(φq)←{T(φq)+U(φq)*φqi}％(φqk-1)
（15） End if
（16） End for
（17）End until
【０１０２】
次いで、電子計算機は、第２の演算手段として機能し、Ｑ[ｉ]＝ｄ[ｉ]Ｑの演算を行う（ステップＳ２０８）。
【０１０３】
ステップＳ２０８でも、バイナリ法を用いており、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<k;i++)
（２） Q[i]←O
（３） for(j=0;d[i]!=0;i++)
（４） if(d[i]＆1)
（５） Q[i]←Q[i]+T[j]
（６） End if
（７） d[i]←d[i]/2
（８） End for
（９）End for
【０１０４】
次いで、電子計算機は、合成手段として機能し、ステップＳ２０８で演算したＱ[ｉ]を用いて、スカラー倍算ｎＱを、
【０１０５】
【数３１】
によって合成する（ステップＳ２０９）。
【０１０６】
ステップＳ２０９では、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<k;i++)
（２） Z←Z+φqi(Q[i])
（３）End for
【０１０７】
そして、電子計算機は、出力手段として機能し、スカラー倍算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ２１０）、スカラー倍算の演算プログラムを終了している。
【０１０８】
Ｄdmax(χ)及び多項式ｈ(φq,χ)は、楕円曲線の有限体Ｆqの位数ｑ(χ)、＃Ｅ(Ｆq)を割り切る素数位数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)があらかじめ与えられていることから、あらかじめ特定でき、ｑ(χ)、ｒ(χ)及びｔ(χ)とともに、Ｄdmax(χ)と多項式ｈ(φq,χ)をスカラー倍算の演算プログラムに組み込んでもよいし、ｒ(χ)及びｔ(χ)を用いて以下の補助プログラムによって、Ｄdmax(χ)と多項式ｈ(φq,χ)を求めてもよい。
【０１０９】
電子計算機は、補助プログラムを起動させると、図４に示すように、はじめに、入力手段として機能し、ｒ(χ)とｔ(χ)が入力される（ステップＳ２２１）。
【０１１０】
次いで、電子計算機は、展開手段として機能し、入力されたｔ(χ)を用いて、ｔ(χ)−１＝ｓ(χ)として、ｒ(χ)を、
【０１１１】
【数３２】
とｓ(χ)進展開する（ステップＳ２２２）。ここで、ｉの大きさは、ｒ(χ)及びｓ(χ)から自動的に決定される。ステップＳ２２２では、ｓ(χ)進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） Di(χ)←r(χ)％s(χ)
（３） r(χ)←(r(χ)-Di(χ))/s(χ)
（４）End for
【０１１２】
次いで、電子計算機は、抽出手段として機能し、deg(Ｄi(χ))が最大のものを抽出して、Ｄdmax(χ)として出力する（ステップＳ２２３）。
【０１１３】
次いで、電子計算機は、演算手段として機能し、
【０１１４】
【数３３】
の演算を行って多項式ｈ(φq,χ)を特定し、出力している（ステップＳ２２４）。このようにして、電子計算機では、補助プログラムを用いてＤdmax(χ)及び多項式ｈ(φq,χ)を求めることができる。
【０１１５】
また、楕円曲線の有限体Ｆqの位数ｑ、＃Ｅ(Ｆq)を割り切る素数位数ｒ、フロベニウス自己準同型写像φqのトレースｔが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｔ(χ)とあらかじめ特定されているとともに、ｒ(χ)をｔ(χ)−１進展開することにより
[ｒ(χ)]Ｑ＝Σ[Ｄi(χ)(ｔ(χ)−１)i]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)
として表されるＤi(χ)において最高次数dmaxとなるＤi(χ)が複数存在する場合には、最高次数dmaxの項であるχdmaxの係数をＴdmax(φq)として、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を特定し、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たす整数のスカラーｖ及びｇ(φq)を拡張ユークリッドの互除法により特定し、
[Ｔdmax(φq)χdmax]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)−[Ｔdmax(φq)χdmax]Ｑ
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)と、ｇ(φq)を用い、φqkＱ＝Ｑに基づいて、
[ｖχdmax]Ｑ＝[ｇ(φq)ｆ(φq,χ)]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、このｈ(φq,χ)のφqに関する定数項ｈ(０,χ)が、
[ｖχdmax−ｈ(０,χ)]Ｑ＝[ｈ(φq,χ)−ｈ(０,χ)]Ｑ
を満たすことを用いることにより、スカラー倍算ｎＱをより高速化することができる。
【０１１６】
すなわち、χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)とし、スカラーｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(φq,ａ)−ｈ(０,ａ)を用いることにより、演算回数を削減している。
【０１１７】
ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)が特定されている場合のスカラー倍算ｎＱでは、スカラー倍算の演算プログラムを実行させて電子計算機をスカラー倍算機として機能させる際に、図５に示すように、はじめに、スカラーｎと、χ＝ａとしてスカラーｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)と、有理点Ｑ∈Ｇ⊂Ｅ(Ｆqk)が入力される（ステップＳ３０１）。この場合、電子計算機は、入力手段として機能する。
【０１１８】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←Ｏ）する（ステップＳ３０２）。そして、第１の演算手段として機能し、入力されたＱに対して、２jＱをあらかじめ演算しておく（ステップＳ３０３）。ステップＳ３０３の演算はステップＳ１０３の演算とアルゴリズムは同じであるので、説明は省略する。
【０１１９】
次いで、電子計算機は、第１の展開手段として機能し、スカラーｎを、
【０１２０】
【数３４】
とｓ'進展開する（ステップＳ３０４）。ステップＳ３０４でのｓ'進展開は、ステップＳ２０４でのｓ進展開とアルゴリズムは同じであるので、説明は省略する。
【０１２１】
次いで、電子計算機は、第２の展開手段として機能し、スカラーｎを、ｈ'(φq)及びｃ[ｉ]を用いながら、
【０１２２】
【数３５】
とφq進展開する（ステップＳ３０５）。ステップＳ３０５でのφq進展開は、スカラーｓ'(＝ｖａdmax−ｈ(０,ａ)）が、ステップＳ２０５でのスカラーｓ(＝Ｄdmax(ａ))とは異なる点以外では、ステップＳ２０５でのｓ進展開とアルゴリズムは同じであるため、詳細な説明は省略する。
【０１２３】
ステップＳ３０５でのφq進展開でも、φq進展開の係数がｓ'よりも大きくなることがある。このように、φq進展開の係数がｓ'よりも大きい場合（ステップＳ３０６：ＮＯ）には、φq進展開の係数に対してｓ'の剰余をとることにより、φq進展開の係数がｓ'よりも小さくなるように調整している（ステップＳ３０７）。このステップＳ３０７での演算も、スカラーｓ'(＝ｖａdmax−ｈ(０,ａ)）が、ステップＳ２０７でのスカラーｓ(＝Ｄdmax(ａ))とは異なる点以外では、ステップＳ２０７での演算とアルゴリズムは同じであるため、詳細な説明は省略する。この場合、電子計算機は、ステップＳ３０６において比較手段として機能し、ステップＳ３０７において調整手段として機能する。
【０１２４】
次いで、電子計算機は、第２の演算手段として機能し、Ｑ[ｉ]＝ｄ[ｉ]Ｑの演算を行う（ステップＳ３０８）。ステップＳ３０８でも、バイナリ法を用いており、ステップＳ３０８の演算もステップＳ２０８の演算とアルゴリズムは同じであるので、説明は省略する。
【０１２５】
次いで、電子計算機は、合成手段として機能し、ステップＳ３０８で演算したＱ[ｉ]を用いて、スカラー倍算ｎＱを、
【０１２６】
【数３６】
によって合成する（ステップＳ３０９）。ステップＳ３０９の演算もステップＳ２０９の演算とアルゴリズムは同じであるので、説明は省略する。
【０１２７】
そして、電子計算機は、出力手段として機能し、スカラー倍算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ３１０）、スカラー倍算の演算プログラムを終了している。
【０１２８】
多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)は、楕円曲線の有限体Ｆqの位数ｑ(χ)、＃Ｅ(Ｆq)を割り切る素数位数ｒ(χ)、フロベニウス自己準同型写像φqのトレースｔ(χ)があらかじめ与えられていることから、あらかじめ特定できるので、ｑ(χ)、ｒ(χ)及びｔ(χ)とともに、多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)をスカラー倍算の演算プログラムに組み込んでもよいし、ｒ(χ)及びｔ(χ)を用いて以下の補助プログラムによって、多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)を求めてもよい。
【０１２９】
電子計算機は、補助プログラムを起動させると、図６に示すように、はじめに、入力手段として機能し、ｒ(χ)、ｔ(χ)及びｍ(χ)が入力される（ステップＳ３２１）。ここで、ｍ(χ)はｒ(χ)｜ｍ(χ)を満たす最小次数の多項式であり、一般的には円周等分多項式が用いられる。
【０１３０】
次いで、電子計算機は、展開手段として機能し、入力されたｔ(χ)を用いて、ｔ(χ)−１＝ｓ(χ)として、ｒ(χ)を、
【０１３１】
【数３７】
とｓ(χ)進展開する（ステップＳ３２２）。ここで、ｉの大きさは、ｒ(χ)及びｓ(χ)から自動的に決定される。ステップＳ３２２では、ｓ(χ)進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） Di(χ)←r(χ)％s(χ)
（３） r(χ)←(r(χ)-Di(χ))/s(χ)
（４）End for
【０１３２】
次いで、電子計算機は、第１の特定手段として機能し、deg(Ｄi(χ))の最大の次数dmaxの項であるχdmaxの係数を抽出して、抽出された係数の和をＴ(φq,χ)とし、それ以外の和をＵ(φq,χ)とする（ステップＳ３２３）。ステップＳ３２３では、電子計算機は、具体的に以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） T(φq,χ)←0,U(φq,χ)←0
（３） if(deg(Di(χ))=dmax)
（４） T(φq,χ)←T(φq,χ)+Di(χ)φqi
（５） End if
（６） else
（７） U(φq,χ)←U(φq,χ)+Di(χ)φqi
（８） End else
（９）End for
【０１３３】
次いで、電子計算機は、第２の特定手段として機能し、ステップＳ３２３で特定したＴ(φq,χ)の最高次数係数Ｔdmax(φq)を特定する（ステップＳ３２４）。
【０１３４】
次いで、電子計算機は、第３の特定手段として機能し、ステップＳ３２４で特定した最高次数係数Ｔdmax(φq)を用い、
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を特定する（ステップＳ３２５）。ステップＳ３２５では、電子計算機は、具体的に以下のアルゴリズムを実行している。
（１）W(φq)←gcd(Tdmax(φq),m(φq))
（２）V(φq)←W(φq)
【０１３５】
次いで、電子計算機は、第４の特定手段として機能し、ステップＳ３２５で特定したＶ(φq)を用い、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たすスカラーｖ及びｇ(φq)を、拡張ユークリッドの互除法によって特定する（ステップＳ３２６）。この拡張ユークリッドの互除法は、一般的なライブラリにおいて準備されている既知のプログラムに基づいて実行されるものであり、特に、ｇ(φq)の係数及びスカラーｖが小さくなるようにしておくことが望ましい。
【０１３６】
次いで、電子計算機は、ステップＳ３２６で特定したｇ(φq)を用い、
【０１３７】
【数３８】
の演算を行って多項式ｈ(φq,χ)を特定し（ステップＳ３２７）、多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)を出力している（ステップＳ３２８）。このようにして、電子計算機では、補助プログラムを用いて多項式ｈ(φq,χ)及びｖχdmax−ｈ(０,χ)を求めることができる。この場合、電子計算機は、ステップＳ３２７において演算手段として機能し、ステップＳ３２８において出力手段として機能する。
【０１３８】
以下において、べき乗算の演算プログラムについて説明する。まず、ｔ−１進展開によるべき乗算Ａnについて説明する。
【０１３９】
べき乗算の演算プログラムを実行させて電子計算機をべき乗算として機能させる際に、図７に示すように、はじめに、べき数ｎと、位数ｑとＦqkの素数位数ｒとの差分ｓと、元Ａ∈Ｈ⊂Ｆqkが入力される（ステップＳ４０１）。この場合、電子計算機は、入力手段として機能する。
【０１４０】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←１）する（ステップＳ４０２）。そして、第１の演算手段として機能し、Ｘ^{Ｙ}はＸＹを表すものとして、入力された元Ａに対して、Ａ^{２j}をあらかじめ演算しておく（ステップＳ４０３）。
【０１４１】
ステップＳ４０３では、Ｔ[ｊ]＝Ａ^{２j}として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(j=0;J<「log2s」;j++)
（２） T[j]←A
（３） A←A*A
（４）End for
【０１４２】
次いで、電子計算機は、展開手段として機能し、べき数ｎを、差分ｓにより
【０１４３】
【数３９】
とｓ進展開する（ステップＳ４０４）。ここで、ｉの大きさは、ｎの大きさによって決定するものである。
【０１４４】
ステップＳ４０４では、ｓ進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） c[i]←n％s
（３） n←(n-c[i])/s
（４）End for
ここで、「％」は、剰余をとっていることを表している。
【０１４５】
次いで、本実施形態では、電子計算機は、第２の演算手段として機能し、Ａ[ｉ]＝Ａｃ[ｉ]の演算を行う（ステップＳ４０５）。
【０１４６】
ステップＳ４０５では、バイナリ法を用いており、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） A[i]←1
（３） for(j=0;c[i]!=0;i++)
（４） if(c[i]＆1)
（５） A[i]←A[i]*T[j]
（６） End if
（７） c[i]←c[i]/2
（８） End for
（９）End for
【０１４７】
次いで、電子計算機は、合成手段として機能し、ステップＳ４０５で演算したＡ[ｉ]を用いて、べき乗算Ａnを、
【０１４８】
【数４０】
によって合成する（ステップＳ４０６）。
【０１４９】
ステップＳ４０６では、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「logsn」;i++)
（２） Z←Z＊φqi(A[i])
（３）End for
【０１５０】
そして、電子計算機は、出力手段として機能し、べき乗算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ４０７）、べき乗算の演算プログラムを終了している。
【０１５１】
また、位数ｑ、素数位数ｒ、差分ｓが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｓ(χ)で与えられている場合には、ｒ(χ)をｓ(χ)進展開することにより
Ａ^{ｒ(χ)}＝ΠＡ^{Ｄi(χ)ｓ(χ)i}＝Ａ^{ΣＤi(χ)ｑi}
として表されるＤi(χ)のうちでもっとも次数の高いものをＤdmax(χ)とし、
(Ａ^{Ｄdmax(χ)})^{ｑdmax}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi}＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(φq,χ)を用い、φqk(Ａ)＝Ａに基づいて、
Ａ^{Ｄdmax(χ)}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi−ｑdmax}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(φq,χ)と、Ｄdmax(χ)を用いることにより、スカラー倍算ｎＱをより高速化することができる。
【０１５２】
すなわち、Ｄdmax(χ)及び多項式ｈ(φq,χ)が特定されている場合には、χ＝ａとしてべき数ｎをＤdmax(ａ)進展開して、Ｄdmax(ａ)に換えてｈ(φq,ａ)を用いることにより、演算回数を削減している。
【０１５３】
Ｄdmax(χ)及び多項式ｈ(φq,χ)が特定されている場合のべき乗算ｎＱでは、べき乗算の演算プログラムを実行させて電子計算機をべき乗算機として機能させる際に、図８に示すように、はじめに、べき数ｎと、χ＝ａとしてｓ＝Ｄdmax(ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)と、元Ａ∈Ｈ⊂Ｆqkが入力される（ステップＳ５０１）。この場合、電子計算機は、入力手段として機能する。
【０１５４】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←１）する（ステップＳ５０２）。そして、第１の演算機能として、入力されたＡに対して、Ａ^{２j}をあらかじめ演算しておく（ステップＳ５０３）。ステップＳ５０３の演算はステップＳ４０３の演算とアルゴリズムは同じであるので、説明は省略する。
【０１５５】
次いで、電子計算機は、第１の展開手段として機能し、べき数ｎを、
【０１５６】
【数４１】
とｓ進展開する（ステップＳ５０４）。ステップＳ５０４でのｓ進展開は、ステップＳ４０４でのｓ進展開とアルゴリズムは同じであるので、説明は省略する。
【０１５７】
次いで、電子計算機は、第２の展開手段として機能し、べき数ｎを、ｈ'(ｑ)及びｃ[ｉ]を用いながら、
【０１５８】
【数４２】
とｑ進展開する（ステップＳ５０５）。
【０１５９】
ステップＳ５０５では、ｑ進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）T(q)←１
（２）for(i=0;i<「logsn」;i++)
（３） d[i]←c[i]
（４） if(d[i]≧s)
（５） for(j=0;j<「logsd[i]」;j++)
（６） e[j]←d[i]％s
（７） d[i]←(d[i]-e[j])％s
（８） End for
（９） U(q)←１
（10） for(j=0;j<「logsd[i]」;j++)
（11） U(q)←{U(q)*e[j]*h'(q)j}％(qk-1)
（12） End for
（13） T(q)←{T(q)+U(q)*h'(q)i}％(qk-1)
（14） End if
（15） else
（16） T(q)←{T(q)+d[i]*h'(q)i}％(qk-1)
（17） End else
（18）End for
【０１６０】
なお、べき数ｎをｑ進展開した場合に、ｑ進展開の係数がｓよりも大きくなることがある。このように、ｑ進展開の係数がｓよりも大きい場合（ステップＳ５０６：ＮＯ）には、ｑ進展開の係数に対してｓの剰余をとることにより、ｑ進展開の係数がｓよりも小さくなるように調整している（ステップＳ５０７）。この場合、電子計算機は、ステップＳ５０６において比較手段として機能し、ステップＳ５０７において調整手段として機能する。
【０１６１】
ステップＳ５０７では、電子計算機は、以下のアルゴリズムを実行している。
（１）until(∀d[i]＜ｓ)
（２） for(i=0;i<k-1;i++)
（３） d[i]←the i-th coefficient of T(q)
（４） if(d[i]≧s)
（５） the i-th coefficient of T(q)←0
（６） for(j=0;j<「logsd[i]」;j++)
（７） e[j]←d[i]％s
（８） d[i]←(d[i]-e[j])％s
（９） End for
（10） U(q)←１
（11） for(j=0;j<「logsd[i]」;j++)
（12） U(q)←{U(q)*e[j]*h'(q)j}％(qk-1)
（13） End for
（14） T(q)←{T(q)+U(q)*qi}％(qk-1)
（15） End if
（16） End for
（17）End until
【０１６２】
次いで、電子計算機は、第２の演算手段として機能し、Ａ[ｉ]＝Ａｄ[ｉ]の演算を行う（ステップＳ５０８）。
【０１６３】
ステップＳ５０８でも、バイナリ法を用いており、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<k;i++)
（２） A[i]←O
（３） for(j=0;d[i]!=0;i++)
（４） if(d[i]＆1)
（５） A[i]←A[i]*T[j]
（６） End if
（７） d[i]←d[i]/2
（８） End for
（９）End for
【０１６４】
次いで、電子計算機は、合成手段として機能し、ステップＳ５０８で演算したＡ[ｉ]を用いて、べき乗算Ａｎを、
【０１６５】
【数４３】
によって合成する（ステップＳ５０９）。
【０１６６】
ステップＳ５０９では、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<k;i++)
（２） Z←Z*φqi(A[i])
（３）End for
【０１６７】
そして、電子計算機は、出力手段として機能し、べき乗算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ５１０）、べき乗算の演算プログラムを終了している。
【０１６８】
Ｄdmax(χ)及び多項式ｈ(ｑ,χ)は、ｑ(χ)、ｒ(χ)及びｓ(χ)があらかじめ与えられていることから、あらかじめ特定でき、ｑ(χ)、ｒ(χ)及びｓ(χ)とともに、Ｄdmax(χ)と多項式ｈ(ｑ,χ)をべき乗算の演算プログラムに組み込んでもよいし、ｒ(χ)及びｓ(χ)を用いて以下の補助プログラムによって、Ｄdmax(χ)と多項式ｈ(ｑ,χ)を求めてもよい。
【０１６９】
電子計算機は、補助プログラムを起動させると、図９に示すように、はじめに、入力手段として機能し、ｒ(χ)とｓ(χ)が入力される（ステップＳ５２１）。
【０１７０】
次いで、電子計算機は、展開手段として機能し、入力されたｓ(χ)を用いて、ｒ(χ)を、
【０１７１】
【数４４】
とｓ(χ)進展開する（ステップＳ５２２）。ここで、ｉの大きさは、ｒ(χ)及びｓ(χ)から自動的に決定される。ステップＳ５２２では、ｓ(χ)進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） Di(χ)←r(χ)％s(χ)
（３） r(χ)←(r(χ)-Di(χ))/s(χ)
（４）End for
【０１７２】
次いで、電子計算機は、抽出手段として機能し、deg(Ｄi(χ))が最大のものを抽出して、Ｄdmax(χ)として出力する（ステップＳ５２３）。
【０１７３】
次いで、電子計算機は、演算手段として機能し、
【０１７４】
【数４５】
の演算を行って多項式ｈ(ｑ,χ)を特定し、出力している（ステップＳ５２４）。このようにして、電子計算機では、補助プログラムを用いてＤdmax(χ)及び多項式ｈ(ｑ,χ)を求めることができる。
【０１７５】
また、位数ｑ、素数位数ｒ及び差分ｓが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)及びｓ(χ)とあらかじめ特定されているとともに、ｒ(χ)をｓ(χ)進展開することにより
Ａ^{ｒ(χ)}＝ΠＡ^{Ｄi(χ)ｓ(χ)i}＝Ａ^{ΣＤi(χ)ｑi}
として表されるＤi(χ)において最高次数dmaxとなるＤi(χ)が複数存在する場合には、最高次数dmaxの項であるχdmaxの係数をＴdmax(ｑ)として、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を特定し、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たす整数のスカラーｖ及びｇ(ｑ)を拡張ユークリッドの互除法により特定し、
Ａ^{Ｔdmax(ｑ)χdmax}＝Ａ^{ΣＤi(χ)ｑi−Ｔdmax(ｑ)χdmax}
＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)と、ｇ(ｑ)を用い、φqk(Ａ)＝Ａに基づいて、
Ａ^{ｖχdmax}＝Ａ^{ｇ(ｑ)ｆ(ｑ,χ)}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、このｈ(ｑ,χ)のｑに関する定数項ｈ(０,χ)が、
Ａ^{ｖχdmax−ｈ(０,χ)}＝Ａ^{ｈ(ｑ,χ)−ｈ(０,χ)}
を満たすことを用いることにより、べき乗算Ａｎをより高速化することができる。
【０１７６】
すなわち、χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ)とし、べき数ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(ｑ,ａ)−ｈ(０,ａ)を用いることにより、演算回数を削減している。
【０１７７】
ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ)が特定されている場合のべき乗算Ａｎでは、べき乗算の演算プログラムを実行させて電子計算機をべき乗算機として機能させる際に、図１０に示すように、はじめに、べき数ｎと、χ＝ａとしてスカラーｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ)と、元Ａ∈Ｈ⊂Ｆqkが入力される（ステップＳ６０１）。この場合、電子計算機は、入力手段として機能する。
【０１７８】
次いで、電子計算機は、初期化手段として機能し、演算結果を格納するレジスタＺを初期化（Ｚ←１）する（ステップＳ６０２）。そして、第１の演算手段として機能し、入力された元Ａに対して、Ａ^{２j}をあらかじめ演算しておく（ステップＳ６０３）。ステップＳ６０３の演算はステップＳ４０３の演算とアルゴリズムは同じであるので、説明は省略する。
【０１７９】
次いで、電子計算機は、第１の展開手段として機能し、スカラーｎを、
【０１８０】
【数４６】
とｓ'進展開する（ステップＳ６０４）。ステップＳ６０４でのｓ'進展開は、ステップＳ４０４でのｓ進展開とアルゴリズムは同じであるので、説明は省略する。
【０１８１】
次いで、電子計算機は、第２の展開手段として機能し、べき数ｎを、ｈ'(ｑ)及びｃ[ｉ]を用いながら、
【０１８２】
【数４７】
とｑ進展開する（ステップＳ６０５）。ステップＳ６０５でのｑ進展開は、スカラーｓ'(＝ｖａdmax−ｈ(０,ａ)）が、ステップＳ５０５でのスカラーｓ(＝Ｄdmax(ａ))とは異なる点以外では、ステップＳ５０５でのｓ進展開とアルゴリズムは同じであるため、詳細な説明は省略する。
【０１８３】
ステップＳ６０５でのｑ進展開でも、ｑ進展開の係数がｓ'よりも大きくなることがある。このように、ｑ進展開の係数がｓ'よりも大きい場合（ステップＳ６０６：ＮＯ）には、ｑ進展開の係数に対してｓ'の剰余をとることにより、ｑ進展開の係数がｓ'よりも小さくなるように調整している（ステップＳ６０７）。このステップＳ６０７での演算も、スカラーｓ'(＝ｖａdmax−ｈ(０,ａ)）が、ステップＳ５０７でのスカラーｓ(＝Ｄdmax(ａ))とは異なる点以外では、ステップＳ５０７での演算とアルゴリズムは同じであるため、詳細な説明は省略する。ここで、電子計算機は、ステップＳ６０６において比較手段と
して機能し、ステップＳ６０７において調整手段として機能する。
【０１８４】
次いで、電子計算機は、第２の演算手段として機能し、Ａ[ｉ]＝Ａｄ[ｉ]の演算を行う（ステップＳ６０８）。ステップＳ６０８でも、バイナリ法を用いており、ステップＳ６０８の演算もステップＳ５０８の演算とアルゴリズムは同じであるので、説明は省略する。
【０１８５】
次いで、電子計算機は、合成手段として機能し、ステップＳ６０８で演算したＡ[ｉ]を用いて、べき乗算Ａｎを、
【０１８６】
【数４８】
によって合成する（ステップＳ６０９）。ステップＳ６０９の演算もステップＳ５０９の演算とアルゴリズムは同じであるので、説明は省略する。
【０１８７】
そして、電子計算機は、出力手段として機能し、べき乗算の演算プログラムの実行結果として、Ｚを出力し（ステップＳ６１０）、べき乗算の演算プログラムを終了している。
【０１８８】
多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)は、位数ｑ(χ)、素数位数ｒ(χ)及び差分ｓ(χ)があらかじめ与えられていることから、あらかじめ特定できるので、ｑ(χ)、ｒ(χ)及びｓ(χ)とともに、多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)をべき乗算の演算プログラムに組み込んでもよいし、ｒ(χ)及びｓ(χ)を用いて以下の補助プログラムによって、多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)を求めてもよい。
【０１８９】
電子計算機は、補助プログラムを起動させると、図１１に示すように、はじめに、入力手段として機能し、ｒ(χ)、ｓ(χ)及びｍ(χ)が入力される（ステップＳ６２１）。ここで、ｍ(χ)はｒ(χ)｜ｍ(χ)を満たす最小次数の多項式であり、一般的には円周等分多項式が用いられる。
【０１９０】
次いで、電子計算機は、展開手段として機能し、入力されたｓ(χ)を用いて、ｒ(χ)を、
【０１９１】
【数４９】
とｓ(χ)進展開する（ステップＳ６２２）。ここで、ｉの大きさは、ｒ(χ)及びｓ(χ)から自動的に決定される。ステップＳ６２２では、ｓ(χ)進展開の演算として、電子計算機は、以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） Di(χ)←r(χ)％s(χ)
（３） r(χ)←(r(χ)-Di(χ))/s(χ)
（４）End for
【０１９２】
次いで、電子計算機は、第１の特定手段として機能し、deg(Ｄi(χ))の最大の次数dmaxの項であるχdmaxの係数を抽出して、抽出された係数の和をＴ(ｑ,χ)とし、それ以外の和をＵ(ｑ,χ)とする（ステップＳ６２３）。ステップＳ６２３では、電子計算機は、具体的に以下のアルゴリズムを実行している。
（１）for(i=0;i<「degr(χ)/degs(χ)」;i++)
（２） T(q,χ)←0,U(q,χ)←0
（３） if(deg(Di(χ))=dmax)
（４） T(q,χ)←T(q,χ)+Di(χ)qi
（５） End if
（６） else
（７） U(q,χ)←U(q,χ)+Di(χ)qi
（８） End else
（９）End for
【０１９３】
次いで、電子計算機は、第２の特定手段として機能し、ステップＳ６２３で特定したＴ(ｑ,χ)の最高次数係数Ｔdmax(ｑ)を特定する（ステップＳ６２４）。
【０１９４】
次いで、電子計算機は、第３の特定手段として機能し、ステップＳ６２４で特定した最高次数係数Ｔdmax(ｑ)を用い、
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を特定する（ステップＳ６２５）。ステップＳ６２５では、電子計算機は、具体的に以下のアルゴリズムを実行している。
（１）W(q)←gcd(Tdmax(q),m(q))
（２）V(q)←W(q)
【０１９５】
次いで、電子計算機は、第４の特定手段として機能し、ステップＳ６２５で特定したＶ(ｑ)を用い、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たすスカラーｖ及びｇ(ｑ)を、拡張ユークリッドの互除法によって特定する（ステップＳ６２６）。この拡張ユークリッドの互除法は、一般的なライブラリにおいて準備されている既知のプログラムに基づいて実行されるものであり、特に、ｇ(ｑ)の係数及びスカラーｖが小さくなるようにしておくことが望ましい。
【０１９６】
次いで、電子計算機は、ステップＳ６２６で特定したｇ(ｑ)を用い、
【０１９７】
【数５０】
の演算を行って多項式ｈ(ｑ,χ)を特定し（ステップＳ６２７）、多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)を出力している（ステップＳ６２８）。このようにして、電子計算機では、補助プログラムを用いて多項式ｈ(ｑ,χ)及びｖχdmax−ｈ(０,χ)を求めることができる。この場合、電子計算機は、ステップＳ６２７において演算手段として機能し、ステップＳ６２８において出力手段として機能する。
【符号の説明】
【０１９８】
10 電子計算機
11 ＣＰＵ
12 記憶装置
13 メモリ装置
14 バス
15 入出力制御部
20 電気通信回線
30 クライアント装置
【特許請求の範囲】
【請求項１】
楕円曲線をＥ／Ｆq＝ｘ3＋ａｘ＋ｂ−ｙ2＝０，ａ∈Ｆq，ｂ∈Ｆqとし、
Ｅ(Ｆq)を有限体Ｆqで定義される楕円曲線の有理点が成す加法群、
Ｅ(Ｆqk)を有限体Ｆqの拡大体Ｆqkで定義される楕円曲線の有理点が成す加法群、
φqを有限体Ｆqに関する有理点のフロベニウス自己準同型写像、
ｔをフロベニウス自己準同型写像φqのトレース、
ｒをＥ(Ｆq)の位数＃Ｅ(Ｆq)＝ｑ＋１−ｔを割り切る素数位数、
Ｅ[ｒ]を位数が素数ｒである有理点の集合、
[ｊ]を有理点をｊ倍する写像、
Ｇを
Ｇ＝Ｅ[r]∩Ker(φq−[ｑ])
を満たすＥ(Ｆqk)に含まれる有理点の集合として、
非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算を、記憶手段を備えた電子計算機により演算するスカラー倍算の演算装置において、
前記非負整数ｎの値、前記トレースｔの値、及び、Ｑ∈Ｇ⊂Ｅ(Ｆqk)により表される有理点Ｑの値を前記記憶手段に入力して記憶させる入力手段と、
演算結果Ｚを記憶する前記記憶手段を初期化する初期化手段と、
Ｇの有理点Ｑに対し、
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑ
が成り立つことにより、
ｓ＝ｔ−１として、前記ｎをｓ進展開した次式に基づいて、
【数１】
c[i]←n％s及びn←(n-c[i])/sにより表される代入演算をｉ＝０から所定回繰り返し行って各係数c[i]及び非負整数ｎの値を前記記憶手段に記憶する展開手段と、
前記記憶手段から前記有理点Ｑ及び前記係数ｃ［ｉ］を読み出して、Ｑ［ｉ］＝ｃ［ｉ］Ｑにより表される演算をｉ＝０から所定回繰り返し行って各Ｑ［ｉ］の値を前記記憶手段に記憶する演算手段と、
ｔ-１に換えて有理点に対するフロベニウス自己準同型写像φqを用いて表される次式のスカラー倍算ｎＱに基づいて、
【数２】
前記記憶手段からＱ［ｉ］及び演算結果Ｚを読み出し、Z←Z+φqi(Q[i])により表される代入演算をｉ＝０から所定回繰り返し行ってスカラー倍算の演算結果Ｚを前記記憶手段に記憶する合成手段と、
を有することを特徴とするスカラー倍算の演算装置。
【請求項２】
前記楕円曲線の有限体Ｆqの位数ｑ、＃Ｅ(Ｆq)を割り切る素数位数ｒ、フロベニウス自己準同型写像φqのトレースｔが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｔ(χ)で与えられている場合に、
前記ｑ(χ)、ｒ(χ)、ｔ(χ)の各値を入力して前記記憶手段に記憶する補助入力手段と、
前記記憶手段からｒ(χ)及びｔ(χ)の値を読み出して、前記ｓ（χ）＝ｔ（χ）−１として、ｒ(χ)をｓ（χ）進展開した次式に基づいて、
【数３】
Di(χ)←r(χ)％s(χ)及びr(χ)←(r(χ)-Di(χ))/s(χ)により表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返し行って、各係数Ｄｉ（χ）及びｒ（χ）の値を前記記憶手段に記憶する補助展開手段と、
前記記憶された係数Ｄｉ（χ）のうち、deg（Ｄｉ（χ））が最大のものをＤｄｍａｘ（χ）として抽出し、前記記憶手段に記憶する補助抽出手段と、
前記記憶手段からＤdmax(χ)、Ｄi(χ)、Ｑの値を読み出して、
φqdmax([Ｄdmax(χ)]Ｑ)＝Σφqi([Ｄi(χ)]Ｑ)−φqdmax([Ｄdmax(χ)]Ｑ)
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)を用い、φqkＱ＝Ｑに基づいて
[Ｄdmax(χ)]Ｑ＝[ｆ(φq,χ)φq-dmax]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、前記多項式ｈ(φq,χ)の値を前記記憶手段に記憶する補助特定手段と、
前記ｓ進展開をχ＝ａとしてｓ＝Ｄdmax(ａ)からなるＤdmax(ａ)進展開に置換え、前記Ｄdmax(ａ)に換えて前記多項式ｈ(φq,ａ)を用いる手段と、を有することを特徴とする請求項１に記載のスカラー倍算の演算装置。
【請求項３】
前記係数Ｄｉ（χ）において最高次数dmaxとなる係数Ｄｉ（χ）が複数存在する場合に、
前記補助入力手段は、ｒ（χ）｜ｍ（χ）を満たすｍ（χ）の値を入力して前記記憶手段に記憶する手段を更に含み、
deg（Ｄｉ(χ)）の最高次数dmaxの項であるχdmaxの係数をＴdmax(φq)として、前記記憶手段から係数Ｄｉ（χ）を読み出し、前記記憶手段にT(φq,χ)及びU(φq,χ)を初期値を０として割り当て、deg(Di(χ))=dmaxとなる場合にT(φq,χ)←T(φq,χ)+Di(χ)φqi、その他の場合にU(φq,χ)←U(φq,χ)+Di(χ)φqiにより表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返し行って、Ｔ(φq,χ)及びＵ(φq,χ)の値を前記記憶手段に記憶し、最高次数係数Ｔdmax(φq)を特定する第２の補助特定手段と、
前記記憶手段からｍ（χ）及びＲ（χ）の値を読み出して、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を、W(φq)←gcd(Tdmax(φq),m(φq))及びV(φq)←W(φq)により表される代入演算を行って特定し、前記Ｖ(φq)の値を前記記憶手段に記憶する第３の補助特定手段と、
前記記憶手段からＶ(φq)及びｍ(φq)の値を読み出して、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たす整数のスカラーｖ及びｇ(φq)を拡張ユークリッドの互除法により特定し、前記スカラーｖ及びｇ(φq)の値を前記記憶手段に記憶する第４の補助特定手段と、
前記補助特定手段に代えて、前記記憶手段からＴdmax(φq)、χdmax、Ｄi(χ)、Ｑの各値を読み出して、
[Ｔdmax(φq)χdmax]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)−[Ｔdmax(φq)χdmax]Ｑ
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)と、前記ｇ(φq)を用い、φqkＱ＝Ｑに基づいて、
[ｖχdmax]Ｑ＝[ｇ(φq)ｆ(φq,χ)]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、前記多項式ｈ(φq,χ)の値を前記記憶手段に記憶する第５の補助特定手段と、
前記記憶手段から前記ｈ(φq,χ)の値を読み出して、
このｈ(φq,χ)のφqに関する定数項ｈ(０,χ)が、
[ｖχdmax−ｈ(０,χ)]Ｑ＝[ｈ(φq,χ)−ｈ(０,χ)]Ｑ
を満たすことを用いて、
χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)により表される演算を行ってｓ'、ｈ'(φq)の値を前記記憶手段に記憶し、
ｔ-１進展開した前記ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(φq,ａ)−ｈ(０,ａ)を用いる手段と、を有することを特徴とする請求項２に記載のスカラー倍算の演算装置。
【請求項４】
Ｆqkを位数ｑの有限体Ｆqのｋ次拡大体、
ＨをＦqkの素数位数ｒの部分乗法群、
φqを有限体Ｆqに関する元のフロベニウス自己準同型写像として、
非負整数ｎに対するＨの元Ａのｎ乗算を行うべき乗算を、記憶手段を備えた電子計算機により演算する演算装置において、
前記非負整数nの値、前記位数ｑの値、前記Ｆqkの素数位数ｒの値、Ａ∈Ｈ⊂Ｆqkにより表される元Ａの値を入力して前記記憶手段に記憶する入力手段と、
演算結果Ｚを記憶する前記記憶手段を初期化する初期化手段と、
前記位数ｑ、前記元Ａの値を前記記憶手段から読み出して、前記ｑとｒの差分をｓ＝ｑ−ｒとし、T[j]←A及びA←A*Aにより表される代入演算を、j＝０からj<「log2s」まで繰り返して行って前記T[j]及び前記Aの値を前記記憶手段に記憶する第１の演算手段と、
前記記憶手段から前記ｎ及び差分ｓの値を読み出して、差分ｓにより展開した次式に基づいて、
【数４】
c[i]←n％s及びn←(n-c[i])/sにより表される代入演算をｉ＝０から所定回繰り返して行い、各係数c[i]及び非負整数ｎの値を前記記憶手段に記憶する展開手段と、
前記記憶手段からc[i]及び前記ｎの値を読み出して、Ａ［ｉ］＝Ａｃ［ｉ］に基づいて、Ａ［ｉ］＝１に初期化し、c[i]＆1である場合にA[i]←A[i]*T[j]、c[i]←c[i]/2により表される代入演算を、ｉ＝０から所定回繰り返して行い、前記記憶手段にA[i]及びc[i]の値を記憶する第２の演算手段と、
前記記憶手段から各Ａ［ｉ］を読み出し、次式に基づいて、
【数５】
Z←Z＊φqi(A[i])により表されるべき乗演算を、ｉ＝０から所定回繰り返して行い、計算結果Ｚとして前記記憶手段に記憶する合成手段と、を有することを特徴とするべき乗算の演算装置。
【請求項５】
Ｘ^{Ｙ}はＸＹであることを表すこととし、
前記位数ｑ、前記素数位数ｒ、前記ｓが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｓ(χ)で与えられている場合に、
前記ｑ(χ)、ｒ(χ)、ｓ(χ)の各値を入力して前記記憶手段に記憶する補助入力手段と、
前記記憶手段からｒ(χ)及びｓ(χ)を読み出して、前記ｓ（χ）を用いて前記ｒ（χ）をｓ（χ）進展開した次式に基づいて、
【数６】
Di(χ)←r(χ)％s(χ)及びr(χ)←(r(χ)-Di(χ))/s(χ)により表される代入演算を、ｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返して行い、前記係数Di(χ)及びr(χ)を前記記憶手段に記憶する補助展開手段と、
前記記憶された係数Ｄｉ（χ）のうち、deg（Ｄｉ（χ））が最大のものをＤｄｍａｘ（χ）として抽出し、前記記憶手段に記憶する補助抽出手段と、
前記記憶手段から前記Ｄｄｍａｘ（χ）、Ｄi(χ)、ｑの値を読み出して、
(Ａ^{Ｄdmax(χ)})^{ｑdmax}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi}＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)を用い、φqk(Ａ)＝Ａに基づいて
Ａ^{Ｄdmax(χ)}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi−ｑdmax}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、前記多項式ｈ(ｑ,χ)の値を前記記憶手段に記憶する補助特定手段と、
前記ｓ進展開した前記ｎを、χ＝ａとしてｓ＝Ｄdmax(ａ)からなるＤdmax(ａ)進展開に置き換え、前記Ｄdmax(ａ)に換えて前記多項式ｈ(ｑ,ａ)を用いる手段と、を有することを特徴とする請求項４に記載のべき乗算の演算装置。
【請求項６】
前記係数Ｄｉ（χ）において最高次数dmaxとなる係数Ｄｉ（χ）が複数存在する場合に、
前記補助記憶手段は、ｒ（χ）｜ｍ（χ）を満たすｍ（χ）の値を入力して前記記憶手段に記憶する手段を更に含み、
deg（Ｄi(χ)）の最高次数dmaxの項であるχdmaxの係数をＴdmax(ｑ)として、前記記憶手段から係数Ｄｉ（χ）を読み出し、前記記憶手段にT(ｑ,χ)及びU(ｑ,χ)を初期値を０として割り当て、deg(Di(χ))=dmaxとなる場合にT(ｑ,χ)←T(ｑ,χ)+Di(χ)ｑi、その他の場合にU(ｑ,χ)←U(ｑ,χ)+Di(χ)ｑiにより表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返して行ってＴ(ｑ,χ)及びＵ(ｑ,χ)の値を前記記憶手段に記憶し、最高次数係数Ｔdmax(ｑ)を特定する第２の補助特定手段と、
前記記憶手段からｍ（χ）及びＲ（χ）の値を読み出して、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を、W(ｑ)←gcd(Tdmax(ｑ),m(ｑ))及びV(ｑ)←W(ｑ)により表される演算を行って特定し、前記Ｖ(ｑ)の値を前記記憶手段に記憶する第３の補助特定手段と、
前記記憶手段からＶ(ｑ)及びｍ(ｑ)の値を読み出して、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たす整数のスカラーｖ及びｇ(ｑ)を拡張ユークリッドの互除法により特定し、前記スカラーｖ及びｇ(ｑ)の値を前記記憶手段に記憶する第４の補助特定手段と、
前記補助特定手段に代えて、前記記憶手段からＴdmax(ｑ)、χdmax、Ｄi(χ)、Ｑの各値を読み出して、
Ａ^{Ｔdmax(ｑ)χdmax}＝Ａ^{ΣＤi(χ)ｑi−Ｔdmax(ｑ)χdmax}
＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)と、前記ｇ(ｑ)を用い、φqk(Ａ)＝Ａに基づいて、
Ａ^{ｖχdmax}＝Ａ^{ｇ(ｑ)ｆ(ｑ,χ)}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、前記多項式ｈ(ｑ,χ)の値を前記記憶手段に記憶する第５の補助特定手段と、
前記記憶手段から前記ｈ(ｑ,χ)の値を読み出して、
このｈ(ｑ,χ)のｑに関する定数項ｈ(０,χ)が、
Ａ^{ｖχdmax−ｈ(０,χ)}＝Ａ^{ｈ(ｑ,χ)−ｈ(０,χ)}
を満たすことを用いて、
χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ) により表される演算を行ってｓ'、ｈ'(ｑ)の値を前記記憶手段に記憶し、ｓ進展開した前記ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(ｑ,ａ)−ｈ(０,ａ)を用いる手段と、を有することを特徴とする請求項５に記載のべき乗算の演算装置。
【請求項１】
楕円曲線をＥ／Ｆq＝ｘ3＋ａｘ＋ｂ−ｙ2＝０，ａ∈Ｆq，ｂ∈Ｆqとし、
Ｅ(Ｆq)を有限体Ｆqで定義される楕円曲線の有理点が成す加法群、
Ｅ(Ｆqk)を有限体Ｆqの拡大体Ｆqkで定義される楕円曲線の有理点が成す加法群、
φqを有限体Ｆqに関する有理点のフロベニウス自己準同型写像、
ｔをフロベニウス自己準同型写像φqのトレース、
ｒをＥ(Ｆq)の位数＃Ｅ(Ｆq)＝ｑ＋１−ｔを割り切る素数位数、
Ｅ[ｒ]を位数が素数ｒである有理点の集合、
[ｊ]を有理点をｊ倍する写像、
Ｇを
Ｇ＝Ｅ[r]∩Ker(φq−[ｑ])
を満たすＥ(Ｆqk)に含まれる有理点の集合として、
非負整数ｎに対するＧの有理点Ｑのスカラーｎ倍算を、記憶手段を備えた電子計算機により演算するスカラー倍算の演算装置において、
前記非負整数ｎの値、前記トレースｔの値、及び、Ｑ∈Ｇ⊂Ｅ(Ｆqk)により表される有理点Ｑの値を前記記憶手段に入力して記憶させる入力手段と、
演算結果Ｚを記憶する前記記憶手段を初期化する初期化手段と、
Ｇの有理点Ｑに対し、
φq(Ｑ)＝[ｑ]Ｑ＝[ｔ−１]Ｑ
が成り立つことにより、
ｓ＝ｔ−１として、前記ｎをｓ進展開した次式に基づいて、
【数１】
c[i]←n％s及びn←(n-c[i])/sにより表される代入演算をｉ＝０から所定回繰り返し行って各係数c[i]及び非負整数ｎの値を前記記憶手段に記憶する展開手段と、
前記記憶手段から前記有理点Ｑ及び前記係数ｃ［ｉ］を読み出して、Ｑ［ｉ］＝ｃ［ｉ］Ｑにより表される演算をｉ＝０から所定回繰り返し行って各Ｑ［ｉ］の値を前記記憶手段に記憶する演算手段と、
ｔ-１に換えて有理点に対するフロベニウス自己準同型写像φqを用いて表される次式のスカラー倍算ｎＱに基づいて、
【数２】
前記記憶手段からＱ［ｉ］及び演算結果Ｚを読み出し、Z←Z+φqi(Q[i])により表される代入演算をｉ＝０から所定回繰り返し行ってスカラー倍算の演算結果Ｚを前記記憶手段に記憶する合成手段と、
を有することを特徴とするスカラー倍算の演算装置。
【請求項２】
前記楕円曲線の有限体Ｆqの位数ｑ、＃Ｅ(Ｆq)を割り切る素数位数ｒ、フロベニウス自己準同型写像φqのトレースｔが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｔ(χ)で与えられている場合に、
前記ｑ(χ)、ｒ(χ)、ｔ(χ)の各値を入力して前記記憶手段に記憶する補助入力手段と、
前記記憶手段からｒ(χ)及びｔ(χ)の値を読み出して、前記ｓ（χ）＝ｔ（χ）−１として、ｒ(χ)をｓ（χ）進展開した次式に基づいて、
【数３】
Di(χ)←r(χ)％s(χ)及びr(χ)←(r(χ)-Di(χ))/s(χ)により表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返し行って、各係数Ｄｉ（χ）及びｒ（χ）の値を前記記憶手段に記憶する補助展開手段と、
前記記憶された係数Ｄｉ（χ）のうち、deg（Ｄｉ（χ））が最大のものをＤｄｍａｘ（χ）として抽出し、前記記憶手段に記憶する補助抽出手段と、
前記記憶手段からＤdmax(χ)、Ｄi(χ)、Ｑの値を読み出して、
φqdmax([Ｄdmax(χ)]Ｑ)＝Σφqi([Ｄi(χ)]Ｑ)−φqdmax([Ｄdmax(χ)]Ｑ)
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)を用い、φqkＱ＝Ｑに基づいて
[Ｄdmax(χ)]Ｑ＝[ｆ(φq,χ)φq-dmax]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、前記多項式ｈ(φq,χ)の値を前記記憶手段に記憶する補助特定手段と、
前記ｓ進展開をχ＝ａとしてｓ＝Ｄdmax(ａ)からなるＤdmax(ａ)進展開に置換え、前記Ｄdmax(ａ)に換えて前記多項式ｈ(φq,ａ)を用いる手段と、を有することを特徴とする請求項１に記載のスカラー倍算の演算装置。
【請求項３】
前記係数Ｄｉ（χ）において最高次数dmaxとなる係数Ｄｉ（χ）が複数存在する場合に、
前記補助入力手段は、ｒ（χ）｜ｍ（χ）を満たすｍ（χ）の値を入力して前記記憶手段に記憶する手段を更に含み、
deg（Ｄｉ(χ)）の最高次数dmaxの項であるχdmaxの係数をＴdmax(φq)として、前記記憶手段から係数Ｄｉ（χ）を読み出し、前記記憶手段にT(φq,χ)及びU(φq,χ)を初期値を０として割り当て、deg(Di(χ))=dmaxとなる場合にT(φq,χ)←T(φq,χ)+Di(χ)φqi、その他の場合にU(φq,χ)←U(φq,χ)+Di(χ)φqiにより表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返し行って、Ｔ(φq,χ)及びＵ(φq,χ)の値を前記記憶手段に記憶し、最高次数係数Ｔdmax(φq)を特定する第２の補助特定手段と、
前記記憶手段からｍ（χ）及びＲ（χ）の値を読み出して、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(φq)｜ｍ(φq),gcd(Ｔdmax(φq),Ｖ(φq))＝１
を満たすＶ(φq)を、W(φq)←gcd(Tdmax(φq),m(φq))及びV(φq)←W(φq)により表される代入演算を行って特定し、前記Ｖ(φq)の値を前記記憶手段に記憶する第３の補助特定手段と、
前記記憶手段からＶ(φq)及びｍ(φq)の値を読み出して、
ｇ(φq)Ｖ(φq)≡ｖ(mod ｍ(φq))
を満たす整数のスカラーｖ及びｇ(φq)を拡張ユークリッドの互除法により特定し、前記スカラーｖ及びｇ(φq)の値を前記記憶手段に記憶する第４の補助特定手段と、
前記補助特定手段に代えて、前記記憶手段からＴdmax(φq)、χdmax、Ｄi(χ)、Ｑの各値を読み出して、
[Ｔdmax(φq)χdmax]Ｑ＝Σφqi([Ｄi(χ)]Ｑ)−[Ｔdmax(φq)χdmax]Ｑ
＝[ｆ(φq,χ)]Ｑ
となる多項式ｆ(φq,χ)と、前記ｇ(φq)を用い、φqkＱ＝Ｑに基づいて、
[ｖχdmax]Ｑ＝[ｇ(φq)ｆ(φq,χ)]Ｑ＝[ｈ(φq,χ)]Ｑ
となる多項式ｈ(φq,χ)を特定し、前記多項式ｈ(φq,χ)の値を前記記憶手段に記憶する第５の補助特定手段と、
前記記憶手段から前記ｈ(φq,χ)の値を読み出して、
このｈ(φq,χ)のφqに関する定数項ｈ(０,χ)が、
[ｖχdmax−ｈ(０,χ)]Ｑ＝[ｈ(φq,χ)−ｈ(０,χ)]Ｑ
を満たすことを用いて、
χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(φq)＝ｈ(φq,ａ)−ｈ(０,ａ)により表される演算を行ってｓ'、ｈ'(φq)の値を前記記憶手段に記憶し、
ｔ-１進展開した前記ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(φq,ａ)−ｈ(０,ａ)を用いる手段と、を有することを特徴とする請求項２に記載のスカラー倍算の演算装置。
【請求項４】
Ｆqkを位数ｑの有限体Ｆqのｋ次拡大体、
ＨをＦqkの素数位数ｒの部分乗法群、
φqを有限体Ｆqに関する元のフロベニウス自己準同型写像として、
非負整数ｎに対するＨの元Ａのｎ乗算を行うべき乗算を、記憶手段を備えた電子計算機により演算する演算装置において、
前記非負整数nの値、前記位数ｑの値、前記Ｆqkの素数位数ｒの値、Ａ∈Ｈ⊂Ｆqkにより表される元Ａの値を入力して前記記憶手段に記憶する入力手段と、
演算結果Ｚを記憶する前記記憶手段を初期化する初期化手段と、
前記位数ｑ、前記元Ａの値を前記記憶手段から読み出して、前記ｑとｒの差分をｓ＝ｑ−ｒとし、T[j]←A及びA←A*Aにより表される代入演算を、j＝０からj<「log2s」まで繰り返して行って前記T[j]及び前記Aの値を前記記憶手段に記憶する第１の演算手段と、
前記記憶手段から前記ｎ及び差分ｓの値を読み出して、差分ｓにより展開した次式に基づいて、
【数４】
c[i]←n％s及びn←(n-c[i])/sにより表される代入演算をｉ＝０から所定回繰り返して行い、各係数c[i]及び非負整数ｎの値を前記記憶手段に記憶する展開手段と、
前記記憶手段からc[i]及び前記ｎの値を読み出して、Ａ［ｉ］＝Ａｃ［ｉ］に基づいて、Ａ［ｉ］＝１に初期化し、c[i]＆1である場合にA[i]←A[i]*T[j]、c[i]←c[i]/2により表される代入演算を、ｉ＝０から所定回繰り返して行い、前記記憶手段にA[i]及びc[i]の値を記憶する第２の演算手段と、
前記記憶手段から各Ａ［ｉ］を読み出し、次式に基づいて、
【数５】
Z←Z＊φqi(A[i])により表されるべき乗演算を、ｉ＝０から所定回繰り返して行い、計算結果Ｚとして前記記憶手段に記憶する合成手段と、を有することを特徴とするべき乗算の演算装置。
【請求項５】
Ｘ^{Ｙ}はＸＹであることを表すこととし、
前記位数ｑ、前記素数位数ｒ、前記ｓが、整数変数χを用いてそれぞれｑ(χ)、ｒ(χ)、ｓ(χ)で与えられている場合に、
前記ｑ(χ)、ｒ(χ)、ｓ(χ)の各値を入力して前記記憶手段に記憶する補助入力手段と、
前記記憶手段からｒ(χ)及びｓ(χ)を読み出して、前記ｓ（χ）を用いて前記ｒ（χ）をｓ（χ）進展開した次式に基づいて、
【数６】
Di(χ)←r(χ)％s(χ)及びr(χ)←(r(χ)-Di(χ))/s(χ)により表される代入演算を、ｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返して行い、前記係数Di(χ)及びr(χ)を前記記憶手段に記憶する補助展開手段と、
前記記憶された係数Ｄｉ（χ）のうち、deg（Ｄｉ（χ））が最大のものをＤｄｍａｘ（χ）として抽出し、前記記憶手段に記憶する補助抽出手段と、
前記記憶手段から前記Ｄｄｍａｘ（χ）、Ｄi(χ)、ｑの値を読み出して、
(Ａ^{Ｄdmax(χ)})^{ｑdmax}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi}＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)を用い、φqk(Ａ)＝Ａに基づいて
Ａ^{Ｄdmax(χ)}＝Ａ^{Σi≠dmax−Ｄi(χ)ｑi−ｑdmax}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、前記多項式ｈ(ｑ,χ)の値を前記記憶手段に記憶する補助特定手段と、
前記ｓ進展開した前記ｎを、χ＝ａとしてｓ＝Ｄdmax(ａ)からなるＤdmax(ａ)進展開に置き換え、前記Ｄdmax(ａ)に換えて前記多項式ｈ(ｑ,ａ)を用いる手段と、を有することを特徴とする請求項４に記載のべき乗算の演算装置。
【請求項６】
前記係数Ｄｉ（χ）において最高次数dmaxとなる係数Ｄｉ（χ）が複数存在する場合に、
前記補助記憶手段は、ｒ（χ）｜ｍ（χ）を満たすｍ（χ）の値を入力して前記記憶手段に記憶する手段を更に含み、
deg（Ｄi(χ)）の最高次数dmaxの項であるχdmaxの係数をＴdmax(ｑ)として、前記記憶手段から係数Ｄｉ（χ）を読み出し、前記記憶手段にT(ｑ,χ)及びU(ｑ,χ)を初期値を０として割り当て、deg(Di(χ))=dmaxとなる場合にT(ｑ,χ)←T(ｑ,χ)+Di(χ)ｑi、その他の場合にU(ｑ,χ)←U(ｑ,χ)+Di(χ)ｑiにより表される代入演算をｉ＝０からi<「degr(χ)/degs(χ)」まで繰り返して行ってＴ(ｑ,χ)及びＵ(ｑ,χ)の値を前記記憶手段に記憶し、最高次数係数Ｔdmax(ｑ)を特定する第２の補助特定手段と、
前記記憶手段からｍ（χ）及びＲ（χ）の値を読み出して、ｒ(χ)｜ｍ(χ)を満たす最小次数の多項式ｍ(χ)を用いて
Ｖ(ｑ)｜ｍ(ｑ),gcd(Ｔdmax(ｑ),Ｖ(ｑ))＝１
を満たすＶ(ｑ)を、W(ｑ)←gcd(Tdmax(ｑ),m(ｑ))及びV(ｑ)←W(ｑ)により表される演算を行って特定し、前記Ｖ(ｑ)の値を前記記憶手段に記憶する第３の補助特定手段と、
前記記憶手段からＶ(ｑ)及びｍ(ｑ)の値を読み出して、
ｇ(ｑ)Ｖ(ｑ)≡ｖ(mod ｍ(ｑ))
を満たす整数のスカラーｖ及びｇ(ｑ)を拡張ユークリッドの互除法により特定し、前記スカラーｖ及びｇ(ｑ)の値を前記記憶手段に記憶する第４の補助特定手段と、
前記補助特定手段に代えて、前記記憶手段からＴdmax(ｑ)、χdmax、Ｄi(χ)、Ｑの各値を読み出して、
Ａ^{Ｔdmax(ｑ)χdmax}＝Ａ^{ΣＤi(χ)ｑi−Ｔdmax(ｑ)χdmax}
＝Ａ^{ｆ(ｑ,χ)}
となる多項式ｆ(ｑ,χ)と、前記ｇ(ｑ)を用い、φqk(Ａ)＝Ａに基づいて、
Ａ^{ｖχdmax}＝Ａ^{ｇ(ｑ)ｆ(ｑ,χ)}＝Ａ^{ｈ(ｑ,χ)}
となる多項式ｈ(ｑ,χ)を特定し、前記多項式ｈ(ｑ,χ)の値を前記記憶手段に記憶する第５の補助特定手段と、
前記記憶手段から前記ｈ(ｑ,χ)の値を読み出して、
このｈ(ｑ,χ)のｑに関する定数項ｈ(０,χ)が、
Ａ^{ｖχdmax−ｈ(０,χ)}＝Ａ^{ｈ(ｑ,χ)−ｈ(０,χ)}
を満たすことを用いて、
χ＝ａとして、ｓ'＝ｖａdmax−ｈ(０,ａ)及びｈ'(ｑ)＝ｈ(ｑ,ａ)−ｈ(０,ａ) により表される演算を行ってｓ'、ｈ'(ｑ)の値を前記記憶手段に記憶し、ｓ進展開した前記ｎをＤdmax(ａ)進展開する換わりにｖａdmax−ｈ(０,ａ)進展開して、ｖａdmax−ｈ(０,ａ)の換わりにｈ(ｑ,ａ)−ｈ(０,ａ)を用いる手段と、を有することを特徴とする請求項５に記載のべき乗算の演算装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００９−３０１０７０（Ｐ２００９−３０１０７０Ａ）
【公開日】平成２１年１２月２４日（２００９．１２．２４）
【国際特許分類】
【出願番号】特願２００９−２２９１５０（Ｐ２００９−２２９１５０）
【出願日】平成２１年９月３０日（２００９．９．３０）
【分割の表示】特願２００８−４３４６２（Ｐ２００８−４３４６２）の分割
【原出願日】平成２０年２月２５日（２００８．２．２５）
【出願人】（５０４１４７２４３）国立大学法人 岡山大学 (444)
【Ｆターム（参考）】
【公開日】平成２１年１２月２４日（２００９．１２．２４）
【国際特許分類】
【出願日】平成２１年９月３０日（２００９．９．３０）
【分割の表示】特願２００８−４３４６２（Ｐ２００８−４３４６２）の分割
【原出願日】平成２０年２月２５日（２００８．２．２５）
【出願人】（５０４１４７２４３）国立大学法人 岡山大学 (444)
【Ｆターム（参考）】
[ Back to top ]