(57)【要約】  表現変換部５１は、n次代数的トーラスTn(Fp^m)（n：正整数、p：素数、m：正整数）の元gを射影表現で表したn個の要素の組  (h0,  h1,・・・,  hn-1)（hi：有限体Fp^mの元、0≦i≦n-1）、n個のうち少なくとも一つの要素を零元0または単位元1とするn個の要素の組  (h’0,  h’1,・・・,  h’n-1)  （h’i：前記有限体Fp^mの元、0≦i≦n-1）で表される制限射影表現に変換する。演算部５２は、有限体Fp^mnにおける演算であるFp^mn演算を有限体Fp^mにおける演算であるFp^m演算の組み合わせで実行する際に、表現変換部５１が変換した制限射影表現h’で表されるn個の要素の組(h’0,  h’1,・・・,  h’n-1)のある要素が零元0または単位元1であることに応じて、Fp^m演算の一部を省略する。
2011010383.tif 000002
【特許請求の範囲】
【請求項１】
n次代数的トーラスTn(Fp^m)（n：正整数、p：素数、m：正整数）の元gを射影表現で表したn個の要素の組(h0,  h1,・・・,  hn-1)（hi：有限体Fp^mの元、0≦i≦n-1）
または
アフィン表現で表されたφ(n)個の要素の組  (c0,  c1,・・・,  cφ(n)-1)（ci：前記有限体Fp^mの元、0≦i≦φ(n)-1、φ(x)：オイラー関数）
のいずれか一つの組が入力されて代数的トーラス演算を実行する演算装置であって、
前記n個の要素の組(h0,  h1,・・・,  hn-1)
または
前記φ(n)個の要素の組(c0,  c1,・・・,  cφ(n)-1)
のいずれか一つの組を、前記n次代数的トーラスTn(Fp^m)の同じ元gを制限射影表現で表されるn個のうち少なくとも一つの要素を零元  “0”または単位元“1”とするn個の要素の組  (h’0,  h’1,・・・,  h’n-1)  （h’i：前記有限体Fp^mの元、0≦i≦n-1）に変換する表現変換部と、
有限体Fp^mnにおける演算であるFp^mn演算を有限体Fp^mにおける演算であるFp^m演算の組み合わせで実行する際に、制限射影表現で表される前記n個の要素の組(h’0,  h’1,・・・,  h’n-1)のある要素が零元“0”または単位元  “1”であることに応じて、前記Fp^m演算の一部を省略する演算部とを備える
ことを特徴とする演算装置。
【請求項２】
n=L*r（L：正整数、r：正整数）であって、
前記表現変換部は、前記n次代数的トーラスTn(Fp^m)の同じ元gを制限射影表現で表されるn個のうち少なくとも(r-1)個の要素を零元  “0”とするn個の要素の組(h’0,  h’1,・・・,  h’n-1)に変換する
ことを特徴とする請求項１に記載の演算装置。
【請求項３】
前記表現変換部は、前記n次代数的トーラスTn(Fp^m)の同じ元gを制限射影表現で表されるn個のうち少なくとも一つの要素を単位元“1”とするn個の要素の組(h’0,  h’1,・・・,  h’n-1)に変換する
ことを特徴とする請求項２に記載の演算装置。
【請求項４】
前記演算部は、
制限射影表現である前記n個の要素の組(h’0,  h’1,・・・,  h’n-1)を入力とし、有限体Fp^mnにおけるFrobenius写像の一部を省略した制限Fp^mnFrobenius写像を実行する写像部と、
前記制限Fp^mn  Frobenius写像の実行結果であり制限射影表現で表されたn個の要素の組(k’0,  k’1,・・・,  k’n-1)を少なくとも一つの入力とし、有限体Fp^mnにおける乗算の一部を省略した制限Fp^mn乗算を実行する乗算部とを有する
ことを特徴とする請求項３に記載の演算装置。
【請求項５】
前記演算部は、制限Fp^mn乗算を実行する
ことを特徴とする請求項４に記載の演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、代数的トーラス演算に関する。
【背景技術】
【０００２】
近年、事前の鍵共有なしに安全な通信を実現する公開鍵暗号技術では、暗号系サイズの増大が問題になっている。このような背景から、公開鍵暗号における暗号系サイズを圧縮する方法が提案されている（例えば非特許文献１参照）。この方法では、代数的トーラスを用いる。代数的トーラスを表現する方法には、アフィン表現、射影表現及び拡大体表現がある（例えば非特許文献２参照）。代数的トーラスにおいて伸長写像とは、代数的トーラスの元をアフィン表現から射影表現に変換したり、射影表現から拡大体表現に変換したり、アフィン表現から拡大体表現に変換したりすることであり、圧縮写像とは、代数的トーラスの元を拡大体表現から射影表現に変換したり、射影表現からアフィン表現に変換したり、拡大体表現からアフィン表現に変換したりすることである。代数的トーラス公開鍵暗号において、鍵生成、暗号化および復号の各ステップで、入出力にはアフィン表現、演算には拡大体表現が用いられた（例えば非特許文献１参照）。計算コストの観点から、演算には射影表現を用いると圧縮写像や伸長写像の計算コストが少なく済むことが知られている（例えば非特許文献３参照）。しかしながら、射影表現における演算は基本的に拡大体表現における演算と同様に行われていた（例えば非特許文献４参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】K.  Rubin  and  A.  Silverberg,  “Torus-Based  Cryptography”,  CRYPTO  2003,  LNCS  2729,  pp.  349-365,  2003.
【非特許文献２】S.  Galbraith,  “Disguising  Tori  and  Elliptic  Curves”,  IACR  e-print  Archive  2006/248,  http://eprint.iacr.org/2006/248.
【非特許文献３】米村智子ほか、「代数的トーラス上の暗号系〜Cramer-Shoup暗号の構成法〜」、コンピュータ・セキュリティ・シンポジウム予稿集、2008
【非特許文献４】磯谷泰知ほか、「代数的トーラス上のべき乗演算の性能評価」、暗号と情報セキュリティ・シンポジウム予稿集、2009
【発明の概要】
【発明が解決しようとする課題】
【０００４】
代数的トーラスを用いて実現される公開鍵暗号方式、鍵共有方式及びデジタル署名方式において、代数的トーラスの元の演算は必須である。演算とは具体的には、乗算、平方、Frobenius写像、逆元、べき乗などである。特に、べき乗の計算には時間がかかる。非特許文献４の技術では、射影表現を用いて、乗算、平方及びFrobenius写像を組み合わせることによりべき乗の計算を実行しているが、べき乗の計算コストの大部分を占める乗算の計算コストが多いという欠点があった。【０００５】
本発明は、上記に鑑みてなされたものであって、計算コストを抑えて代数的トーラスにおける演算を高速に実行することが可能な演算装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上述した課題を解決し、目的を達成するために、本発明は、n次代数的トーラスTn(Fp^m)（n：正整数、p：素数、m：正整数）の元gを射影表現で表したn個の要素の組(h0,  h1,・・・,  hn-1)（hi：有限体Fp^mの元、0≦i≦n-1）またはアフィン表現で表されたφ(n)個の要素の組  (c0,  c1,・・・,  cφ(n)-1)（ci：前記有限体Fp^mの元、0≦i≦φ(n)-1、φ(x)：オイラー関数）のいずれか一つの組が入力されて代数的トーラス演算を実行する演算装置であって、前記n個の要素の組(h0,  h1,・・・,  hn-1)または前記φ(n)個の要素の組(c0,  c1,・・・,  cφ(n)-1)のいずれか一つの組を、前記n次代数的トーラスTn(Fp^m)の同じ元gを制限射影表現で表されるn個のうち少なくとも一つの要素を零元  “0”または単位元“1”とするn個の要素の組  (h’0,  h’1,・・・,  h’n-1)  （h’i：前記有限体Fp^mの元、0≦i≦n-1）に変換する表現変換部と、有限体Fp^mnにおける演算であるFp^mn演算を有限体Fp^mにおける演算であるFp^m演算の組み合わせで実行する際に、制限射影表現で表される前記n個の要素の組(h’0,  h’1,・・・,  h’n-1)のある要素が零元“0”または単位元  “1”であることに応じて、前記Fp^m演算の一部を省略する演算部とを備えることを特徴とする。
【発明の効果】
【０００７】
本発明によれば、計算コストを抑えて代数的トーラスにおける演算を高速に行うことが可能になる。
【図面の簡単な説明】
【０００８】
【図１】第１の実施の形態の演算装置５０の機能的構成を例示する図。
【図２】第１の実施の形態の演算処理の手順を示すフローチャート。
【図３】第２の実施の形態の演算処理の手順を示すフローチャート。
【図４】第３の実施の形態の演算処理の手順を示すフローチャート。
【図５】第４の実施の形態の演算装置５０の機能的構成を例示する図。
【図６】第４の実施の形態の演算処理の手順を示すフローチャート。
【図７】第５の実施の形態の演算処理の手順を示すフローチャート。
【図８】第６の実施の形態の演算処理の手順を示すフローチャート。
【図９】第７実施の形態の演算処理の手順を示すフローチャート。
【図１０】第８の実施の形態の演算処理の手順を示すフローチャート。
【図１１】第９の実施の形態の演算処理の手順を示すフローチャート。
【図１２】第１０の実施の形態のテーブル作成装置７０の機能的構成を例示する図。
【図１３】第１０の実施の形態の演算装置５０の機能的構成を例示する図。
【図１４】第１０の実施の形態の演算処理の手順を示すフローチャート。
【図１５】第１１の実施の形態のテーブル作成装置７０の機能的構成を例示する図。
【図１６】第１１の実施の形態の演算装置５０の機能的構成を例示する図。
【発明を実施するための形態】
【０００９】
以下に添付図面を参照して、この発明にかかる演算装置の一実施の形態を詳細に説明する。
【００１０】
[第１の実施の形態]
まず、本実施の形態にかかる代数的トーラスにおける演算の数学的準備について説明する。代数的トーラスTnが定義される有限体をFp^mとする。ここで、pは素数、nとmは正整数とする。記号「^」はべき乗を表し、p^mはpのm乗を表す。Fp^mは要素数がp^mの有限体を表す。代数的トーラスTn(Fp^m)は要素数がΦn(p^m)の群である。ここで、Φn(X)は第n円分多項式（円周n等分多項式）である。
【００１１】
代数的トーラスTn(Fp^m)のアフィン表現はφ(n)個のFp^mの元の組で表される。ここで、φ(x)はオイラー関数である。代数的トーラスTn(Fp^m)の元gの射影表現は、Fp^mnのある元hを用いて以下の式１または式１の逆元として表される。
【００１２】
【数１】
2011010383.tif 000003
【００１３】
ここで、σはGalois群Gal(Fp^mn/Fp^mr)の生成元であり、Frobenius写像π:  x  →x^(p^m)とi=0,  1,…,  n/r-1からあるiを用いてσ=π^ir、rはnの約数とする。一般に射影表現hはn個のFp^mの元の組で表される。
【００１４】
式１の意味を説明する。Hilbertの定理90より、Fp^mn  の元gのFp^mrに関するノルム写像が1であることと、数１を満たすFp^mnの元hが存在することは同値である。一方、代数的トーラスTn(Fp^m)の元gの定義は、dをnの約数としてgのFp^mdに関するノルム写像が全て1となることである（例えば非特許文献１参照）。式１はFp^mnの元gのd=rなる特定のノルム写像が1であることを示しているので、代数的トーラスTn(Fp^m)の元gとなるためにはd≠rなるノルム写像が全て1となる条件をhに課さなければならない。
【００１５】
例えば、n=2*r、rが2と異なる素数の場合を考える。2次拡大の基底を{1,  x}、Fp^mrのある元をα,  βとすると、h=α+βxと表される。Gal(Fp^mn/Fp^mr)={1,π}となるので、σ=πである。Fp^mrの元は、このσを作用させても不変である。この場合、射影表現は以下の式２又は式２の逆元となる。
【００１６】
【数２】
2011010383.tif 000004
【００１７】
代数的トーラスTn(Fp^m)の元gとなるためには、Fp^m2に関するノルム写像が1となる条件をhに課す。そのような(α,  β)についてFp^mrの元δをそれぞれにかけた(αδ,  βδ)も同じ代数的トーラスの元gを表す。この性質が射影表現と呼ばれる理由である。同様にして、2とrの役割を入れ替えた射影表現や、n=2*r  と表されないnに対しても射影表現が構成できる。
【００１８】
Fp^mの逆元、Fp^mの乗算、Fp^mの平方、Fp^mのFrobenius写像の計算コストを、それぞれI,  M,  S,  Fと表すことにする。Fp^mに属する定数とFp^mの元の間の乗算の計算コストをBと表すことにする。Bの数や計算コストはパラメータの取り方によって異なる。
【００１９】
次に、本実施の形態にかかる演算装置の構成について説明する。演算装置は、装置全体を制御するＣＰＵ（Central  Processing  Unit）等の制御部と、各種データや各種プログラムを記憶するＲＯＭ（Read  Only  Memory）やＲＡＭ（Random  Access  Memory）等の主記憶部と、各種データや各種プログラムを記憶するＨＤＤ（Hard  Disk  Drive）やＣＤ（Compact  Disk）ドライブ装置等の補助記憶部と、外部装置の通信を制御する通信Ｉ／Ｆ（interface）と、これらを接続するバスとを備えており、通常のコンピュータを利用したハードウェア構成となっている。
【００２０】
このようなハードウェア構成において、演算装置の備えるＣＰＵが主記憶部や補助記憶部に記憶された各種プログラムを実行することにより実現される各種機能について具体的に説明する。図１は、本実施の形態にかかる演算装置５０の機能的構成を例示する図である。同図に示されるように、演算装置５０は、表現変換部５１と、演算部５２とを有する。表現変換部５１には、代数的トーラスの元であり射影表現で表される元ｇが入力され、表現変換部５１は、入力された射影表現を演算の計算コストの少ない射影表現（制限射影表現という）に変換する。表現変換部５１に入力される代数的トーラスTn(Fp^m)  （n：正整数、p：素数、m：正整数）の元をgとし、gに対応する射影表現をhとし、制限射影表現をh’とする。射影表現hは一般にFp^mnの元である。射影表現hは、n個の要素を含む(h0,  h1,・・・,  hn-1)（hi：有限体Fp^mの元、0≦i≦n-1、r：nの約数）で表され、Fp^mnのFp^md（d：nの約数）に関するノルム写像が全て1となる条件を満たす。制限射影表現h’は、制限射影表現h’をn個のFp^mの元の組で表す際に、少なくとも一つの要素を部分体Fp^m’の元として定義する。ここで、m’はmの約数でありmと異なる。このような制限射影表現h’は射影表現hにFp^mrのある元δを乗算することにより得られ、n個の要素を含む射影表現(h’0,  h’1,・・・,  h’n-1)として表される。制限射影表現h’も、Fp^mnのFp^mdに関するノルム写像が全て1となる条件を満たす。例えば、表現変換部５１は、n次代数的トーラスTn(Fp^m)（n：正整数、p：素数、m：正整数）の元gを射影表現で表したn個の要素の組  (h0,  h1,・・・,  hn-1)（hi：有限体Fp^mの元、0≦i≦n-1）、n個のうち少なくとも一つの要素を零元0または単位元1とするn個の要素の組  (h’0,  h’1,・・・,  h’n-1)  （h’i：前記有限体Fp^mの元、0≦i≦n-1）で表される制限射影表現に変換する。
【００２１】
演算部５２は、表現変換部５１が変換した制限射影表現h’の一部の要素又は部分体Fp^m’の元を含む全ての要素を用いて、部分体Fp^m’の元に制限された演算を実行する。例えば、演算部５２は、表現変換部５１が変換した制限射影表現h’を用いて、有限体Fp^mnにおける演算であるFp^mn演算を有限体Fp^mにおける演算であるFp^m演算の組み合わせで実行する際に、制限射影表現h’のn個の要素の組(h’0,  h’1,・・・,  h’n-1)のある要素が零元0または単位元1であることに応じて、Fp^m演算の一部を省略する。演算とは、例えば、乗算、Frobenius写像、べき乗などである。
【００２２】
次に、本実施の形態にかかる演算装置５０の行う演算処理の手順について説明する。図２は、本実施の形態にかかる演算処理の手順を示すフローチャートである。ステップＳ１で、表現変換部５１が、代数的トーラスTn(Fp^m)の元gを表す式１の射影表現hを、射影表現h’に変換する。ステップＳ２では、演算部５２が、ステップＳ１で変換された制限射影表現h’を用いて、Fp^mn演算をFp^m演算の組み合わせで実行する際に、制限射影表現h’のn個の要素の組(h’0,  h’1,・・・,  h’n-1)のある要素が零元0または単位元1であることに応じて、Fp^m演算の一部を省略する。
【００２３】
以上のように、入力された射影表現を制限射影表現に変換することにより、代数的トーラスにおける演算の計算コストを減らすことができる。例えば、非特許文献４の技術では、射影表現での演算は一般のFp^mnの演算を実行していため、計算コストを減らすことは困難であった。しかし、本実施の形態によれば、特に、以降の実施の形態で説明するように、本計算である演算を実行する前に、射影表現から制限射影表現への変換を事前計算として行う場合、本計算の計算コストを減らすことができる。従って、代数的トーラスの元の演算装置を用いて実現される公開鍵暗号、鍵共有及びデジタル署名の高速化が可能となる。
【００２４】
[第２の実施の形態]
次に、演算装置の第２の実施の形態について説明する。なお、上述の第１の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００２５】
本実施の形態においては、上述の第１の実施の形態で説明した代数的トーラスにおいて、n=2*r、rが2と異なる素数である場合について説明する。また、演算として乗算の例について説明する。本実施の形態にかかる演算装置５０の機能的構成は図１に示されるものと略同様である。表現変換部５１に入力される代数的トーラスTn(Fp^m)の元は、g1とg2とし、式２の射影表現であり元g1,g2に対応する射影表現をh1，h2とし、h1=α1+β1  xとh2=α2+β2  xとする。射影表現h1，h2をそれぞれ(α1,  β1)と(α2,  β2)と書く。射影表現h1,  h2は各々n個の要素を有する。表現変換部５１は、このような射影表現h1，h2のうち少なくとも１つを、演算の計算コストが少ない制限射影表現h1’又はh2’に変換する。ここでは、射影表現h1，h2の２つをそれぞれ制限射影表現h1’,h2’に変換する例について説明する。即ち、表現変換部５１は、射影表現h1を、少なくとも一つの要素を零元0または単位元1とするn個の要素の組の制限射影表現h1’に変換し、射影表現h2を、少なくとも一つの要素を零元0または単位元1とするn個の要素の組の制限射影表現h2’に変換する。演算部５２は、元g1,g2の乗算として、制限射影表現h1’,h2’を用いて、n個の要素うちある要素が零元0または単位元1であることに応じて、Fp^m演算の一部を省略した乗算（制限Fp^mn乗算という）を実行する。
【００２６】
ここで乗算を例とした演算について従来の技術と比較しながら説明する。従来の技術では、元g1,g2の乗算を、Karatsuba法又はx=0,  1,  ∞としたToom-Cook法を用いて式３，４により実行して、乗算結果(α3,  β3)を得ていた。式３，４は、2次拡大の法多項式がf2(x)=x^2-dである場合の例である。以降の例で、特に断りのない場合は同じ法多項式を用いる。代数的トーラスにおける乗算の計算コストの主要部分はFp^mrの乗算3回とFp^mrの定数の乗算1回である。
【００２７】
【数３】
2011010383.tif 000005
【００２８】
図３は、本実施の形態にかかる演算処理の手順を示すフローチャートである。本施の形態においては、ステップＳ１０で、表現変換部５１が、入力された射影表現h1，h2を、式５，６により、制限射影表現h1’,h2’に変換する。制限射影表現h1’は、(α1’,1)=  (α1/β1,1)であり、制限射影表現h2’は、(α2’,1)=  (α2/β2,1)である。ステップＳ１１では、演算部５２が、ステップS１０で変換された射影表現h1’,h2’を用いて、元g1,g2の乗算を式７，８により実行することによって制限Fp^mn乗算を実行し、乗算結果(α3,  β3)を得る。
【００２９】
このような代数的トーラスにおける乗算の計算コストの主要部分は、Fp^mrの乗算1回となり、上述した従来の計算コストであるFp^mrの乗算3回とFp^mrの定数の乗算1回に比べて減少した。ただし、表現変換の計算コストの主要部分がFp^mrの逆元2回とFp^mrの乗算2回となる。代数的トーラスにおける乗算を事前計算と本計算とに分割して行なう場合、即ち、表現変換を事前計算として行い乗算を本計算として行なう場合、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストが増加する一方で、本計算の計算コストは3分の1程度に減少する。
【００３０】
【数４】
2011010383.tif 000006
【００３１】
尚、上述の例では、表現変換部５１は、式５，６により、射影表現h1,h2の両方を制限射影表現に変換するようにした。しかし、表現変換部５１がどちらか一方のみを制限射影表現に変換する場合でも、演算部５２は、元g1,g2の乗算として、入力された２つの射影表現のうち表現変換部５１が変換した制限射影表現と変換していない射影表現とを用いて、制限Fp^mn乗算を実行することができる。また、射影表現h1，h2の両方を同じ変換式で変換したが、これに限らず、異なる変換式で変換しても良い。異なる変換式の例としては、ノルム写像Nを用いて、射影表現h1  を、(α1’,b1)=(α1×N(β1)/β1,  N(β1))に変換しても良い。ここで、N(β1)/β1はノルム写像を計算する途中で得られ、逆元を計算する必要はない。このように、変換対象の射影表現の第2要素を1ではなく部分体の元とすると、第2要素を1とした場合に比べ、表現変換の計算コストが小さくなると同時に演算の計算コストは大きくなる。また、式５，６では、第1要素と第2要素の役割を入れ替えても良い。即ち、例えば、射影表現hについては、(1,  β1)=(  1,β1/α1)としても良い。
【００３２】
[第３の実施の形態]
次に、演算装置の第３の実施の形態について説明する。なお、上述の第１の実施の形態又は第２の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００３３】
本実施の形態においては、上述の第１の実施の形態で説明した代数的トーラスにおいて、n=2*r、rが2と異なる素数である場合について説明する。また、演算としてFrobenius写像φ^u:  x→x^(p^u)の例について説明する。本実施の形態にかかる演算装置５０の機能的構成は図１に示されるものと略同様である。表現変換部５１に入力される代数的トーラスTn(Fp^m)の元はg1とし、元g1に対応する射影表現をh1とし、h1=α1+β1  xとし、正整数uとする。射影表現h1を(α1,  β1)と書く。射影表現h1は、n個の要素を有する。表現変換部５１は、このような射影表現h1を、少なくとも一つの要素を単位元1とするn個の要素の組の制限射影表現h1’に変換する。演算部５２は、元g1のFrobenius写像として、制限射影表現h1’を用いて、n個の要素うちある要素が単位元1であることに応じて、Fp^m演算の一部を省略したFrobenius写像（制限Fp^mnFrobenius写像という）を実行する。
【００３４】
ここでFrobenius写像を例とした演算について従来の技術と比較しながら説明する。従来の技術では、元g1のFrobenius写像φ^u(g1)を式９，１０により計算して、写像結果(α3,  β3)を得ていた。代数的トーラスにおけるFrobenius写像の計算コストの主要部分はFp^mrのFrobenius写像2回とFp^mrの定数の乗算1回である。
【００３５】
【数５】
2011010383.tif 000007
【００３６】
図４は、本実施の形態にかかる演算処理の手順を示すフローチャートである。本実施の形態においては、ステップＳ２０で、表現変換部５１が、入力された射影表現h1を、式１１により、制限射影表現h1’に変換する。制限射影表現h1’は、(α1’,1)=(α1/β1,1)である。ステップＳ２１では、演算部５２は、ステップＳ２０で変換された制限射影表現h1’を用いて、元g1のFrobenius写像を式１２，１３により計算することによって、制限Fp^mnFrobenius写像を実行し、写像結果(α3,  β3)を得る。
【００３７】
このような代数的トーラスにおけるFrobenius写像の計算コストの主要部分はFp^mrのFrobenius写像1回となり、上述した従来の計算コストであるFp^mrのFrobenius写像2回とFp^mrの定数の乗算1回に比べて減少した。ただし、表現変換の計算コストの主要部分がFp^mrの逆元1回とFp^mrの乗算1回となる。代数的トーラスにおけるFrobenius写像を事前計算と本計算とに分割して行なう場合、即ち、表現変換を事前計算として行いFrobenius写像の計算を本計算として行なう場合、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストが増加する一方で、本計算の計算コストは減少する。
【００３８】
【数６】
2011010383.tif 000008
【００３９】
尚、上述の例では、表現変換部５１は、式１１により射影表現h1を制限射影表現h1’に変換したが、これに限らず、例えば、ノルム写像Nを用いて、射影表現h1  を、(α1’,b1)=(α1×N(β1)/β1,  N(β1))に変換しても良い。ここで、N(β1)/β1はノルム写像を計算する途中で得られ、逆元を計算する必要はない。このように変換対象の射影表現の第2要素を1ではなく部分体の元とすると、第2要素を1とした場合に比べ表現変換の計算コストが小さくなると同時に演算の計算コストは大きくなる。また、式１１では、第1要素と第2要素の役割を入れ替えても良い。
【００４０】
[第４の実施の形態]
次に、演算装置の第４の実施の形態について説明する。なお、上述の第１の実施の形態乃至第３の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００４１】
本実施の形態においては、上述の第１の実施の形態で説明した代数的トーラスにおいて、n=2*r、rが2と異なる素数である場合について説明する。また、演算として(1+p^u)乗の例について説明する。図５は、本実施の形態にかかる演算装置５０の機能的構成を例示する図である。演算装置５０の演算部５２は、制限写像部５３と、制限乗算部５４とを有する。表現変換部５１に入力される代数的トーラスTn(Fp^m)の元はg1とし、元g1に対応する射影表現をh1とし、h1=α1+β1  xとし、非負整数uとする。射影表現h1を(α1,  β1)と書く。(1+p^u)乗は、元g1の(1+p^u)乗をFrobenius写像φ^u(g1)とg1の乗算とする。ここで、g2=φ^u(g1)とする。元g2に対応する射影表現をh2とし、h2=α2+β2  xとする。射影表現h1,  h2は各々n個の要素を有する。表現変換部５１は、このような射影表現h1を、少なくとも一つの要素を単位元1とするn個の要素の組の制限射影表現h1’に変換する。演算部５２は、元g1の(1+p^u)乗をFrobenius写像φ^u(g1)とg1の乗算として、制限射影表現h1’,h2’を用いて、Fp^m演算の一部を省略した演算を実行する。具体的には、演算部５２の有する制限写像部５３は、制限射影表現h1’を用いて、Fp^m演算の一部を省略したFrobenius写像（制限Fp^mnFrobenius写像）を実行することにより元g1のFrobenius写像φ^u(g1)を計算し、制限射影表現h2’を得る。制限乗算部５４は、制限射影表現h1’,h2’を用いて、Fp^m演算の一部を省略した乗算（制限Fp^mn乗算）を実行する。
【００４２】
ここで(1+p^u)乗を例とした演算について従来の技術と比較しながら説明する。従来の技術では、元g1のFrobenius写像φ^u(g1)を、式９，１０を用いて計算して、写像結果(α3,  β3)を得て、更に、g2=φ^u(g1)として乗算を式３，４により実行して、乗算結果(α3,  β3)を得ていた。代数的トーラスにおける(1+p^u)乗の計算コストの主要部分はFp^mrの乗算3回とFp^mrの定数の乗算2回とFp^mrのFrobenius写像2回である。
【００４３】
図６は、本実施の形態にかかる演算処理の手順を示すフローチャートである。本実施の形態においては、ステップＳ３０で、表現変換部５１が、入力された射影表現h1を、式５により、制限射影表現h1’に変換する。ステップＳ３１では、演算部５２の制限写像部５３が、Frobenius写像を式１２，１３により計算することによって、制限Fp^mnFrobenius写像を実行する。ステップＳ３２では、制限乗算部５３が、g2=φ^u(g1)として乗算を式７，８により実行することによって、制限Fp^mn乗算を実行し、乗算結果(α3,  β3)を得る。ここで、式１２，１３により得られるFrobenius写像結果(α3,  β3)において、第2要素が1ならば、式７，８を用いて計算を実行する際の式５，６による表現変換は行わなくても良い。
【００４４】
このような代数的トーラスにおける(1+p^u)乗の計算コストの主要部分はFp^mrの乗算1回とFp^mrのFrobenius写像1回となり、上述した従来の計算コストであるFp^mrの乗算3回とFp^mrの定数の乗算2回とFp^mrのFrobenius写像2回に比べて減少した。ただし、表現変換の計算コストの主要部分がFp^mrの逆元1回とFp^mrの乗算1回となる。代数的トーラスにおける(1+p^u)乗を事前計算と本計算とに分割して行なう場合、即ち、表現変換を事前計算として行い(1+p^u)乗の計算を本計算として行なう場合、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストが増加する一方で、本計算の計算コストは3分の1程度に減少する。
【００４５】
尚、上述の計算コストは、表現変換部５１が、射影表現h1,h2の両方を制限射影表現に変換する場合のものであるが、どちらか一方のみを制限射影表現に変換する場合でも、演算部５２は、元g1,g2の演算として、入力された２つの射影表現のうち表現変換部５１が変換した制限射影表現と変換していない射影表現とを用いて、Fp^m演算の一部を省略した演算を実行することができる。また、射影表現h1，h2の両方を同じ変換式で変換したが、これに限らず、異なる変換式で制限射影表現に変換しても良い。異なる変換式の例としては、ノルム写像Nを用いて、射影表現h1  を、(α1’,b1)=(α1×N(β1)/β1,  N(β1))に変換しても良い。ここで、N(β1)/β1はノルム写像を計算する途中で得られ、逆元を計算する必要はない。このように、変換対象の射影表現の第2要素を1ではなく部分体の元とすると、第2要素を1とした場合に比べ、表現変換の計算コストが小さくなると同時に演算の計算コストは大きくなる。また、式５，６では、第1要素と第2要素の役割を入れ替えても良い。
【００４６】
[第５の実施の形態]
次に、演算装置の第５の実施の形態について説明する。なお、上述の第１の実施の形態乃至第４の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００４７】
本実施の形態においては、上述の第１の実施の形態で説明した代数的トーラスにおいて、n=2*r、rが2と異なる素数である場合について説明する。また、演算として(p^u1+p^u2+・・・+p^uk)乗の例について説明する。本実施の形態にかかる演算装置５０の機能的構成は図５に示されるものと略同様である。尚、表現変換部５１に入力される代数的トーラスTn(Fp^m)の元はg1とし、元g1に対応する射影表現をh1とし、h1=α1+β1  xとし、非負整数u1,  u2,  ・・・,  ukとする。射影表現h1を(α1,  β1)と書く。(p^u1+p^u2+・・・+p^uk)乗は、Frobenius写像φ^u1,  φ^u2,  ・・・,  φ^ukと乗算とを組み合わせて計算する。射影表現h1はn個の要素を有する。表現変換部５１は、このような射影表現h1を、少なくとも一つの要素を単位元1とするn個の要素の組の制限射影表現h1’に変換する。演算部５２は、元g1の(p^u1+p^u2+・・・+p^uk)乗として、制限射影表現h1’を用いて、Fp^m演算の一部を省略した演算を実行する。具体的には、演算部５２の有する制限写像部５３は、制限射影表現h1’を用いて、制限Fp^mnFrobenius写像を実行することにより元g1のFrobenius写像φ^u1,  φ^u2,  ・・・,  φ^ukを計算して、制限射影表現h2’を得る。制限乗算部５４は、制限射影表現h2’を用いて、Fp^m演算の一部を省略した乗算（制限Fp^mn乗算）を実行する。
【００４８】
ここで(p^u1+p^u2+・・・+p^uk)乗を例とした演算について従来の技術と比較しながら説明する。従来の技術では、元g1の(p^u1+p^u2+・・・+p^uk)乗を式９，１０,３，４により計算して、べき乗結果(α3,  β3)を得ていた。代数的トーラスにおける(p^u1+p^u2+・・・+p^uk)乗の計算コストの主要部分はFp^mrの乗算3(k-1)回とFp^mrの定数の乗算2(k-1)回とFp^mrのFrobenius写像2k回である。
【００４９】
図７は、本実施の形態にかかる演算処理の手順を示すフローチャートである。本実施の形態においては、ステップＳ４０で、表現変換部５１が、入力された射影表現h1を、式１１により、制限射影表現h1’に変換する。射影表現h1’は、(α1’,1)=(α1/β1,1)である。ステップＳ４１〜Ｓ４２では、演算部５２が、このような制限射影表現h1’を用いて、元g1の(p^u1+p^u2+・・・+p^uk)乗について１回目の乗算として式１２，１３,７，８により計算し、乗算結果(α3,  β3)を得る。ここで、式１２，１３により得られるFrobenius写像結果(α3,  β3)において、第2要素が1ならば、式７，８を用いて計算を実行する際の式５，６による表現変換は行わなくても良い。２回目以降の乗算では２入力のうちFrobenius写像の出力から得られる入力は表現変換を行わなくても良い。また、乗算の出力から得られる入力の表現変換を行わなくても計算コストは減少する。
【００５０】
このような代数的トーラスにおける  (p^u1+p^u2+・・・+p^uk)乗の計算コストの主要部分はFp^mrの乗算(2k-3)回とFp^mrの定数の乗算(k-2)回とFp^mrのFrobenius写像k回となり、上述した従来の計算コストであるFp^mrの乗算3(k-1)回とFp^mrの定数の乗算2(k-1)回とFp^mrのFrobenius写像2k回に比べて減少した。但し、表現変換の変換コストの主要部分がFp^mrの逆元1回とFp^mrの乗算1回となる。代数的トーラスにおける(p^u1+p^u2+・・・+p^uk)乗を事前計算と本計算とに分割して行なう場合、即ち、表現変換を事前計算として行い(p^u1+p^u2+・・・+p^uk)乗の計算を本計算として行なう場合、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストはFp^mrの逆元1回-{  Fp^mrの乗算(k-1)回+  Fp^mrの定数の乗算k回+  Fp^mrのFrobenius写像k回}だけ増加する。つまり、Fp^mrの逆元1回＜{  Fp^mrの乗算(k-1)回+  Fp^mrの定数の乗算k}回+  Fp^mrのFrobenius写像k回}なるkでは総計算コストが減少すると同時に、本計算の計算コストも3分の2程度に減少する。
【００５１】
尚、上述の計算コストは、表現変換部５１が、Fp^mnの乗算に際し式５,６のいずれか一方により射影表現を制限射影表現に変換する場合のものであるが、乗算結果を表現変換し両方を制限射影表現に変換する場合でも、演算部５２は、Fp^m演算の一部を省略した演算を実行することができる。また、表現変換部５１は、射影表現h1を式５，６とは異なる変換式で制限射影表現に変換しても良い。異なる変換式の例としては、ノルム写像Nを用いて、射影表現h1を、(α1’,b1)=(α1×N(β1)/β1,N(β1))に変換しても良い。ここで、N(β1)/β1はノルム写像を計算する途中で得られ、逆元を計算する必要はない。このように、変換対象の射影表現の第2要素を1ではなく部分体の元とすると、第2要素を1とした場合に比べ、表現変換の計算コストが小さくなると同時に演算の計算コストは大きくなる。また、式５，６では、第1要素と第2要素の役割を入れ替えても良い。
【００５２】
[第６の実施の形態]
次に、演算装置の第６の実施の形態について説明する。なお、上述の第１の実施の形態乃至第５の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００５３】
本実施の形態においては、上述の第１の実施の形態で説明した代数的トーラスにおいて、n=2*r、r=3であり、3次拡大の法多項式をf3(y)=y^2-wとする場合について説明する。この場合、アフィン表現(c0,  c1)から射影表現hへの表現変換は例えば式１４で表される。
【００５４】
【数７】
2011010383.tif 000009
【００５５】
このような代数的トーラスにおける演算を実行する演算装置には、代数的トーラスの元が少なくとも一つ入力され、演算装置は、射影表現で演算を実行する。代数的トーラス公開鍵暗号においては、鍵生成、暗号化及び復号の各ステップで公開鍵又は暗号文は圧縮された表現即ちアフィン表現で入出力される。この場合、入力は代数的トーラスTn(Fp^m)の元gに対応するアフィン表現(c0,  c1)で与えられる。従来の技術では、このアフィン表現(c0,  c1)を元gに対応する射影表現h=c0*c1+c1^2  y+(c0^2+d/3)/w  y^2+c1  xに変換する。射影表現hを(c0*c1,  c1^2,  (c0^2+d/3)/w,  c1,  0,  0)と書く。得られた射影表現hはn(=6)個のFp^mの元の組で表され、うち2つの要素が0となっており、演算の計算コストが既に少ない射影表現となっている。
【００５６】
一方、本実施の形態では、演算装置５０は、アフィン表現(c0,  c1)を射影表現hに変換するのではなく、計算コストがより少ない制限射影表現h’に変換する。この表現変換は例えば式１５で表される。式１４との違いはxの係数を1とするために、式１４の射影表現全体にc1の逆元をかけたことである。尚、式１５では、射影表現の第1要素と第2要素とを用いて第3要素を表しているが、第2要素と第3要素との役割を入れ替えても良い。
【００５７】
【数８】
2011010383.tif 000010
【００５８】
尚、本実施の形態にかかる演算装置５０の機能的構成は図１に示されるものと略同様である。演算装置５０の表現変換部５１が、以上で説明した表現変換を実行する。即ち、表現変換部５１は、n次代数的トーラスTn(Fp^m)（n：正整数、p：素数、m：正整数）の元gをアフィン表現で表されたφ(n)個の要素の組  (c0,  c1,・・・,  cφ(n)-1)（ci：前記有限体Fp^mの元、0≦i≦φ(n)-1、φ(x)：オイラー関数）を、n個のうち少なくとも一つの要素を零元0または単位元1とするn個の要素の組  (h’0,  h’1,・・・,  h’n-1)  （h’i：前記有限体Fp^mの元、0≦i≦n-1）に変換する。演算部５２は、Fp^mn演算をFp^m演算の組み合わせで実行する際に、表現変換部５１が変換した制限射影表現h’を用いて、n個の要素の組(h’0,  h’1,・・・,  h’n-1)のある要素が零元0または単位元1であることに応じて、Fp^m演算の一部を省略した演算を実行する。
【００５９】
次に、本実施の形態にかかる演算装置５０の行う演算処理の手順について説明する。図８は、本実施の形態にかかる演算処理の手順を示すフローチャートである。ステップＳ５０で、表現変換部５１が、代数的トーラスTn(Fp^m)の元gを表すアフィン表現を、式１５により制限射影表現h’に変換する。ステップＳ５１では、演算部５２が、ステップＳ５０で変換された制限射影表現h’の一部の要素又は部分体Fp^m’の元を含む全ての要素を用いて、n個の要素の組(h’0,  h’1,・・・,  h’n-1)のある要素が零元0または単位元1であることに応じて、Fp^m演算の一部を省略した演算を実行する。
【００６０】
以上のように、入力されたアフィン表現を従来の射影表現に比べて計算コストがより少ない制限射影表現に変換することにより、代数的トーラスにおける演算の計算コストを減らすことができる。特に、以降の実施の形態で説明するように、本計算である演算を実行する前に、射影表現から制限射影表現への変換を事前計算として行う場合、本計算の計算コストを減らすことができる。従って、代数的トーラスの元の演算装置を用いて実現される公開鍵暗号、鍵共有及びデジタル署名の高速化が可能となる。
【００６１】
[第７の実施の形態]
次に、演算装置の第７の実施の形態について説明する。なお、上述の第１の実施の形態乃至第６の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００６２】
本実施の形態においては、上述の第６の実施の形態で説明した代数的トーラスにおいて、n=2*r、r=3であり、3次拡大の法多項式をf3(y)=y^2-wとする場合について説明する。また、演算として乗算の例について説明する。本実施の形態にかかる演算装置５０の機能的構成は図１に示されるものと略同様である。表現変換部５１に入力される代数的トーラスTn(Fp^m)の元は、g1とg2とし、元g1,g2に対応するアフィン表現を(c0,  c1)と(d0,d1)とする。射影表現h1,  h2は各々n個の要素を有する。表現変換部５１は、このようなアフィン表現(c0,  c1),(d0,d1)をそれぞれ射影表現に変換するが、このうち少なくとも一方を演算の計算コストが少ない制限射影表現h1’又はh2’に変換する。ここでは、アフィン表現(c0,  c1),(d0,d1)の２つをそれぞれ制限射影表現h1’,h2’に変換する例について説明する。即ち、表現変換部５１は、射影表現h1を、n個のうち少なくとも(r-1)個の要素を零元0とし且つn個のうち少なくとも1個の要素を単位元1とするn個の要素の組の制限射影表現h1’に変換し、射影表現h2を、n個のうち少なくとも(r-1)個の要素を零元0とし且つn個のうち少なくとも1個の要素を単位元1とするn個の要素の組の制限射影表現h2’に変換する。演算部５２は、元g1,g2の乗算として、制限射影表現h1’,h2’を用いて、n個のうち少なくとも(r-1)個の要素が零元0でありn個のうち少なくとも1個の要素が単位元1であることに応じて、Fp^m演算の一部を省略した乗算（制限Fp^mn乗算）を実行する。
【００６３】
ここで乗算を例とした演算について従来の技術と比較しながら説明する。従来の技術では、元g1,g2の乗算について、式１４による表現変換を実行して、式１６，１７による射影表現を用いて式１８，１９により、乗算結果(α3,  β3)を得ていた。代数的トーラスにおける乗算の計算コストの主要部分は10M+3Bであり、表現変換の計算コストの主要部分は2M+4S+2Bである。数９におけるt3の計算にはt1の結果の一部を再利用することに注意する。
【００６４】
【数９】
2011010383.tif 000011
【００６５】
図９は、本実施の形態にかかる演算処理の手順を示すフローチャートである。本実施の形態においては、ステップＳ６０で、表現変換部５１が、入力されたアフィン表現(c0,  c1),(d0,d1)をそれぞれ式２０Ａ，２０Ｂにより制限射影表現h1’,h2’に変換する。制限射影表現h1’は、(α1’,1)であり、制限射影表現h2’は、(α2’,1)である。ステップＳ６１では、演算部５２が、ステップＳ６０で変換された制限射影表現h1’,h2’を用いて、元g1,g2の乗算を式２１，２２により実行して、乗算結果(α3,  β3)を得る。
【００６６】
このような代数的トーラスにおける乗算の計算コストの主要部分は、主要部分は6M+2Bとなり、上述した従来の計算コストである10M+3Bに比べて減少した。ただし、表現変換の計算コストの主要部分が2I+2M+2S+2Bとなり、2M+4S+2Bに比べて増加した。代数的トーラスにおける乗算を事前計算と本計算とに分割して行なう場合、即ち、表現変換を事前計算として行い乗算を本計算として行なう場合、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストが増加する一方で、本計算の計算コストは60%程度に減少する。
【００６７】
【数１０】
2011010383.tif 000012
【００６８】
尚、上述の例では、表現変換部５１は、式２０Ａ，２０Ｂにより、アフィン表現(c0,  c1),(d0,d1)の両方を本実施の形態にかかる制限射影表現h1’,h2’に変換するようにした。しかし、表現変換部５１がどちらか一方のみを制限射影表現に変換し他方を従来と同様の射影表現に変換する場合でも、演算部５２は、元g1,g2の乗算として、表現変換部５１が変換した制限射影表現及び射影表現を用いて、Fp^m演算の一部を省略した演算を実行することができる。また、射影表現h1，h2の両方を同じ変換式で制限射影表現に変換したが、これに限らず、異なる変換式で変換しても良い。尚、式１５では、射影表現の第1要素と第2要素とを用いて第3要素を表しているが、第2要素と第3要素との役割を入れ替えても良い。
【００６９】
[第８の実施の形態]
次に、演算装置の第８の実施の形態について説明する。なお、上述の第１の実施の形態乃至第７の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００７０】
本実施の形態においては、上述の第６の実施の形態で説明した代数的トーラスにおいて、n=2*r、r=3であり、3次拡大の法多項式をf3(y)=y^2-wとする場合について説明する。また、演算として乗算の例について説明する。本実施の形態にかかる演算装置５０の機能的構成は図１に示されるものと略同様である。表現変換部５１に入力される代数的トーラスTn(Fp^m)の元はg1とg2とし、元g1,g2に対応するアフィン表現を(c0,  c1)と(d0,d1)とする。表現変換部５１は、このようなアフィン表現(c0,  c1),(d0,d1)をそれぞれ射影表現に変換するが、このうち少なくとも一方を演算の計算コストが少ない制限射影表現h1’又はh2’に変換する。ここでは、アフィン表現(c0,  c1),(d0,d1)の２つをそれぞれ制限射影表現h1’,h2’に変換する例について説明する。即ち、表現変換部５１は、射影表現h1を、n個のうち少なくとも(r-1)個の要素を零元0とし且つn個のうち少なくとも1個の要素を単位元1とするn個の要素の組の制限射影表現h1’に変換し、射影表現h2を、n個のうち少なくとも(r-1)個の要素を零元0とし且つn個のうち少なくとも1個の要素を単位元1とするn個の要素の組の制限射影表現h2’に変換する。演算部５２は、元g1,g2の乗算として、制限射影表現h1’,h2’を用いて、n個のうち少なくとも(r-1)個の要素が零元0でありn個のうち少なくとも1個の要素が単位元1であることに応じて、Fp^m演算の一部を省略した乗算（制限Fp^mn乗算）を実行する。尚、元g1，g2の乗算にはToom-Cook法を用いる。
【００７１】
従来の技術では、式７の表現変換を用いた代数的トーラスにおける乗算の計算コストの主要部分は8M+3Bであり、表現変換の計算コストの主要部分は2M+4S+2Bである。
【００７２】
図１０は、本実施の形態にかかる演算処理の手順を示すフローチャートである。本実施の形態においては、ステップＳ７０で、表現変換部５１が、元g1，g2を各々表すアフィン表現(c0,  c1),(d0,d1)を、式１５を変形した式２３により、制限射影表現h1’  ,h2’に各々変換する。式１５との違いは定数を1とするために、式１５の射影表現全体にc0の逆元をかけたことである。定数を1とするためには他にd^(-1)×xをかけても良い。ステップＳ７１では、演算部５２が、元g1,g2の乗算として、ステップS７０で変換された制限射影表現h1’,h2’を用いて、部分体Fp^m’の元に制限された演算を実行する。
【００７３】
【数１１】
2011010383.tif 000013
【００７４】
このような制限射影表現h1’,h2’を用いた代数的トーラスにおける乗算の計算コストの主要部分は5M+3Bとなり、表現変換の計算コストの主要部分は2I+8M+4S+2Bとなる。Toom-Cook法における基底は3次拡大の2次拡大ではなく、6次拡大に変換する。例えば、xとyの多項式基底もしくは疑多項式基底ならばs  =  xy  の多項式基底もしくは疑多項式基底に要素の入れ替えと定数との乗算で変換される。代数的トーラス乗算を事前計算と本計算とに分割して行なう場合、即ち、表現変換を事前計算として行い乗算を本計算として行なう場合、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストが増加する一方で、本計算の計算コストは63%程度に減少する。
【００７５】
尚、上述の計算コストは、表現変換部５１が、アフィン表現(c0,  c1),(d0,d1)の両方を、式２３により、制限射影表現h1’,h2’に変換する場合のものであるが、どちらか一方のみを制限射影表現に変換し他方を従来と同様の射影表現に変換する場合でも、演算部５２は、元g1,g2の乗算として、表現変換部５１が変換した制限射影表現及び射影表現を用いて、Fp^m演算の一部を省略した演算を実行することができる。また、射影表現h1，h2の両方を同じ変換式で制限射影表現に変換したが、これに限らず、異なる変換式で変換しても良い。尚、式２３では、射影表現の第1要素と第2要素とを用いて第3要素を表しているが、第2要素と第3要素との役割を入れ替えても良い。また、6次拡大体の基底はs  =  xyの他の多項式基底もしくは疑多項式基底でも良い。
【００７６】
[第９の実施の形態]
次に、演算装置の第９の実施の形態について説明する。なお、上述の第１の実施の形態乃至第８の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００７７】
本実施の形態においては、上述の第６の実施の形態で説明した代数的トーラスにおいて、n=2*r、r=3であり、3次拡大の法多項式をf3(y)=y^2-wとする場合について説明する。また、演算としてFrobenius写像φ^u:  x→x^(p^u)の例について説明する。本実施の形態にかかる演算装置５０の機能的構成は図１に示されるものと略同様である。表現変換部５１に入力される代数的トーラスTn(Fp^m)の元はg1とし、元g1に対応するアフィン表現を(c0,  c1)とし、正整数uとする。表現変換部５１が、元g1を表すアフィン表現(c0,  c1)を式１５によって、n個のうち少なくとも(r-1)個の要素を零元0とし且つn個のうち少なくとも1個の要素を単位元1とするn個の要素の組の制限射影表現h1’に変換する。演算部５２は、元g1のFrobenius写像として、制限射影表現h1’を用いて、Fp^m演算の一部を省略したFrobenius写像（制限Fp^mnFrobenius写像）を実行する。
【００７８】
ここでFrobenius写像を例とした演算について従来の技術と比較しながら説明する。従来の技術では、元g1のFrobenius写像φ^u(g1)について、式１４による表現変換を実行して、式２４による射影表現を用いて式２５，２６により、写像結果(α3,  β3)を得ていた。このような代数的トーラスにおけるFrobenius写像の計算コストの主要部分は4F+3Bであり、表現変換の計算コストの主要部分はM+2S+Bである。
【００７９】
【数１２】
2011010383.tif 000014
【００８０】
図１１は、本実施の形態にかかる演算処理の手順を示すフローチャートである。本実施の形態においては、ステップＳ８０で、表現変換部５１が、元g1を表すアフィン表現(c0,  c1)を式１５によって制限射影表現h1’に変換する。ステップＳ８１では、演算部５２が、式２７によって表される制限射影表現h1’を用いて式２８，２９により制限Fp^mnFrobenius写像を実行して、写像結果(α3,  β3)を得る。
【００８１】
このような代数的トーラスにおけるFrobenius写像の計算コストの主要部分は3F+2Bとなり、従来の計算コストである4F+3Bに比べて減少した。ただし、表現変換の計算コストの主要部分がI+M+S+Bとなり、従来の表現変換の計算コストであるM+2S+Bに比べて増加した。代数的トーラスにおけるFrobenius写像を事前計算と本計算とに分割して行なう場合、即ち、表現変換を事前計算として行いFrobenius写像の計算を本計算として行なう場合、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストが増加する一方で、本計算の計算コストは減少する。
【００８２】
【数１３】
2011010383.tif 000015
【００８３】
尚、上述の計算コストは、表現変換部５１が、元g1を表すアフィン表現(c0,  c1)を式１５により制限射影表現に変換した場合の例であるが、例えば式２３など他の式により制限射影表現に変換する場合でも、演算部５２は、元g1,g2の乗算として、表現変換部５１が変換した制限射影表現を用いて、Fp^m演算の一部を省略した演算を実行することができる。また、式１５や式２３において第2要素と第3要素との役割を入れ替えても良い。
【００８４】
[第１０の実施の形態]
次に、演算装置の第１０の実施の形態について説明する。なお、上述の第１の実施の形態乃至第９の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【００８５】
本実施の形態においては、上述の第６の実施の形態で説明した代数的トーラスにおいて、n=2*r、r=3であり、3次拡大の法多項式をf3(y)=y^2-wとする場合について説明する。また、演算としてべき乗の例について説明する。図１２は、本実施の形態にかかるテーブル作成装置７０の機能的構成を例示する図である。尚、テーブル作成装置７０のハードウェア構成は演算装置５０と略同様である。図１３は、本実施の形態にかかる演算装置５０の機能的構成を例示する図である。テーブル作成装置７０は、表現変換部７１と、制限写像部７２と、制限乗算部７３と、制御部７４と、テーブル７５とを有する。演算装置５０は、第１演算部５５と、第２演算部５６とを有する。第１演算部５５は、制限写像部５７と、制限乗算部５８と、制御部５９と、テーブル６０とを有する。第２演算部５６は、平方部６１と、乗算部６２とを有する。このような構成により、本実施の形態においては、テーブル作成装置７０がテーブル７５を作成して、当該テーブル７５を用いて、演算装置５０が、べき乗を計算する。べき乗の計算は、乗算、平方及びFrobenius写像を組み合わせて行なう（例えば非特許文献４参照）。また、このようなべき乗の計算をKaratsuba法を用いて行なう。尚、テーブル作成装置７０と演算装置５０とを別体で構成したが、これらを一体的に構成するようにしても良い。
【００８６】
テーブル作成装置７０の表現変換部７１に入力される代数的トーラスTn(Fp^m)の元はg1とし、元g1に対応するアフィン表現を(c0,  c1)とする。正整数winと正整数aとする。表現変換部７１は、入力されたアフィン表現(c0,  c1)を演算の計算コストが少ない射影表現h1’に変換する。制御部７４には、正整数winが入力され、制御部７４は、正整数winと表現変換部７１が変換した射影表現h1’とを用いて、テーブル７５にエントリを記憶させる。制限写像部７２は、テーブル７５に記憶されたエントリを参照して、制限Fp^mnFrobenius写像を実行する。制限乗算部７３は、制限写像部７２が実行した制限Fp^mnFrobenius写像の結果と、テーブル７５に記憶されたエントリとを用いて、制限Fp^mn乗算を実行する。
【００８７】
第１演算部５５のテーブル６０は、テーブル作成装置７０で作成されたテーブル７５と同様のものである。制御部５９には、正整数aが入力され、制御部５９は、テーブル６０に記憶されたエントリを参照して、制限Fp^mnFrobenius写像を制限写像部５７が実行する際に用いるエントリを選択する。制限写像部５７は、制御部５９が選択したエントリを用いて、制限Fp^mnFrobenius写像を実行する。制限乗算部５８は、制限写像部５７が実行した制限Fp^mnFrobenius写像の結果と、テーブル６０に記憶されたエントリとを用いて、制限Fp^mn乗算を実行する。この結果得られる射影表現が第２演算部５６の平方部６１に入力される。
【００８８】
平方部６１は、入力された射影表現を用いて平方の計算を実行する。乗算部６２は、平方部６１が実行した計算の結果を用いて、乗算を実行する。この結果得られる射影表現が、べき乗の計算結果である。
【００８９】
ここでべき乗g^aを計算する演算について従来の技術と比較しながら説明する。指数aはp進表現で入力されるか、aのp進展開を計算してp進表現を得る。次に、p進表現された指数aの各桁の2進表現を得る。指数aのp進表現の各桁において、2進表現の同一桁を並べた系列を得る。得られた長さ2m、ceil(log2(p))個の系列について、ウィンドウ幅win以内の1で始まり1で終わる系列を全て抽出しテーブルのエントリとする。または、テーブルのエントリとしてウィンドウ幅win以内の全ての可能性を事前計算しておく。テーブル作成部は、例えば、第3番の系列11に対してはT11=g×φ(g)、第11番の系列1101に対してはT1101=g×φ^1(g)×φ^3(g)を計算してテーブルに保持する。尚、系列の表記では、先頭がp^0に対応しp^1,  p^2,・・・として通常と逆に表記しているので注意が必要である。つまり、第k番の系列B0  B1  B2B3・・・Bi・・・Bwin-1に対してTB0  B1  B2  B3・・・Bi・・・Bwin-1=Πiφ^(Bi*i)(g)と計算して保持する。ここでBwin-1はBの添え字がwin-1の意味とする。
【００９０】
本計算では、まず、指数aの各桁において2進表現における2^j桁を並べた系列をテーブルのエントリの連結で表現する。ここでjは非負整数である。例えば系列11001101を11・00・1101と表現する。系列の各桁はp進の各桁に対応する。第１演算部は、例えば、11・00・1101に対してはT11×φ^4(T1101)を計算する。2^j桁の系列に対応する計算結果をAjとする。第２演算部は、jの大きい方からAjの平方を計算し、Aj^2と次のAj-1を乗算しその結果の平方を計算し、(Aj^2*Aj-1)^2と次のAj-2を乗算しその結果の平方を計算することを繰り返す。0≦j≦ceil(log2(p))-1、ceil(x)はx以上の最小の整数を返す天井関数である。
【００９１】
計算コストについて、テーブルの生成の計算コストの最大値の主要部分は、
［Ｔ１］入力された元gと元gのFrobenius写像に対する(win-1)回の代数的トーラスにおける乗算、
［Ｔ２］入力された元gとテーブルに既にあるエントリのFrobenius写像に対する(2^(win-1)-win)回の代数的トーラスにおける乗算
である。
【００９２】
本計算の計算コストの主要部分は、指数aとウィンドウ幅winと基礎体の拡大次数mで決まる。f(a,  win,  m)回の代数的トーラスにおける乗算の内訳として、
［Ｍ１］テーブルのエントリ同士の代数的トーラスにおける乗算ceil(log2(p))回、
［Ｍ２］中間結果とテーブルのエントリの代数的トーラスにおける乗算(f(a,  win,  m)-2ceil(log2(p))+1)回、
［Ｍ３］の乗算回数はAjを掛け合わせる操作に対応する、
［Ｍ４］(ceil(log2(p))-1)回の中間結果の代数的トーラスにおける平方
である。
【００９３】
従来の技術では、入力されたアフィン表現を式１４により射影表現に変換してから、テーブルの作成を実行し、得られた乗算の結果の値をそのままテーブルに保持していた。従来の技術でKaratsuba法を用いてべき乗の計算を実行する場合の計算コストについて説明する。
［Ｔ０］入力された元gの表現変換の計算コストはM+2S+B、
［Ｔ１］入力された元gと元gのFrobenius写像に対する代数的トーラスにおける乗算の計算コストは、6個のFp^mの元のうち2要素を0とする射影表現同士の代数的トーラスにおける乗算なので実施の形態８で説明した従来の技術と同様に1回あたり10M+3B、
［Ｔ２］入力された元gとテーブルに既にあるエントリのFrobenius写像に対する代数的トーラスにおける乗算は、6個のFp^mの元のうち2要素を0とする射影表現と一般の射影表現との代数的トーラスにおける乗算なので1回あたり15M+7Bの計算コスト
である。テーブルのエントリはT1を除き一般の射影表現である。簡単のため、全てのエントリが一般の射影表現として本計算の計算コストを見積もる。
［Ｍ１］〜［Ｍ３］一般の射影表現同士の代数的トーラスにおける乗算なので1回あたり18M+9Bの計算コスト、
［Ｍ４］一般の射影表現同士の代数的トーラス平方なのでComplex法（後述）を用いると1回あたり12M+10Bの計算コスト
である。以上をまとめて、従来の技術における代数的トーラスにおけるべき乗の計算コストを算出すると、テーブルの作成の計算コストは式３０により求められ、本計算の計算コストは式３１により求められる。
【００９４】
【数１４】
2011010383.tif 000016
【００９５】
【数１５】
2011010383.tif 000017
【００９６】
次に、本実施の形態にかかる演算処理の手順について説明する。図１４は、本実施の形態にかかる演算処理の手順を示すフローチャートである。ステップＳ９０では、テーブル作成装置７０の表現変換部７１が、元gを表すアフィン表現を、式１５により制限射影表現に変換し、また、テーブル７５のエントリに対して、第７の実施の形態乃至第９の実施の形態における制限射影表現へ変換する。そして、制御部７４が、テーブル７５にエントリを記憶させることにより、テーブル７５を作成する。このようなテーブル７５のエントリは演算装置５０のテーブル６０に記憶される。ステップＳ９１では、第１演算部５５が、ステップＳ９０で変換された制限射影表現を用いて、制限Fp^mnFrobenius写像及び制限Fp^mn乗算を実行する。ステップＳ９２では、ステップＳ９１の演算の結果得られる制限射影表現を用いて、第２演算部５６が、平方及び乗算を実行する。
【００９７】
次に、本実施の形態でKaratsuba法を用いてべき乗の計算を実行する場合の計算コストの例について説明する。
［Ｔ０］入力された元gの表現変換の計算コストはI+M+S+B、
［Ｔ１］〜［Ｔ２］代数的トーラスにおける乗算は第８の実施の形態と同様に1回あたり6M+2Bの計算コスト、
［Ｔ３］テーブル７５のエントリの表現変換の計算コストは最大(2^(win-1)-1)回で、1回あたりFp^mrの逆元1回とFp^mrの乗算1回、逆元計算にItoh-Tsujii法（後述）を用いるとI+24M
である。テーブル７５のエントリは全て、6個のFp^mの元のうち2要素を0、1要素を1とする射影表現とする。
［Ｍ１］テーブル６０のエントリ同士の代数的トーラスにおける乗算の計算コストは第８の実施の形態と同様に1回あたり6M+2B、
［Ｍ２］中間結果とテーブル６０のエントリの代数的トーラスにおける乗算は、一般の射影表現と6個のFp^mの元のうち2要素を0、1要素を1とする射影表現との代数的トーラスにおける乗算なので1回あたり12M+7Bの計算コスト、
［Ｍ３］中間結果同士の代数的トーラスにおける乗算は一般の射影表現同士なので1回あたり18M+9Bの計算コスト、
［Ｍ４］一般の射影表現同士の代数的トーラスにおける平方なのでComplex法を用いると1回あたり12M+10Bの計算コスト
である。以上をまとめて、本実施の形態における代数的トーラスのべき乗の計算コストを算出すると、テーブル７５の作成の計算コストは式３２により求められ、本計算の計算コストは式３３により求められる。
【００９８】
【数１６】
2011010383.tif 000018
【００９９】
【数１７】
2011010383.tif 000019
【０１００】
Karatsuba法を用いた場合の従来の技術における計算コストと本実施の形態にかかる計算コストとを比較すると、テーブル７５の作成にかかる計算コストの増加分は式３４により求められ、本計算にかかる計算コストの減少分は式３５により求められる。
【０１０１】
【数１８】
2011010383.tif 000020
【０１０２】
【数１９】
2011010383.tif 000021
【０１０３】
具体的な数値として、ceil(log2(p))=13、aは700ビット程度、win=5、  m=27、のとき、平均でf(a,  win,  m)=118.72である（例えば非特許文献４参照）。この場合、テーブル７５の作成にかかる計算コストの増加分は16I+245M-S-59B、本計算にかかる計算コストの減少分は718.32M+278.44Bである。代数的トーラスにおけるべき乗において、テーブル７５の作成を事前計算として行いべき乗の計算を本計算として行なうと、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストは{(16I+245M-S-59B)-(718.32M+278.44B)}だけ増加する。通常I＜30M+21Bが成り立つので総計算コストが減少すると同時に、本計算の計算コストも3分の2程度に減少する。
【０１０４】
尚、上述の計算コストは元gを表すアフィン表現とテーブル７５のエントリTiを表すアフィン表現とを全て式１５により制限射影表現に変換する場合のものであるが、これらを異なる表現変換で制限射影表現に変換するようにしても良い。例えば、式２３により表現変換を実行するようにしても良いし、式１５や式２３における第2要素と第3要素との役割を入れ替えて表現変換を実行するようにしても良い。また、中間値Ajを更に表現変換しても良い。また、中間値Ajを保持せずに第１演算部５５が第2演算部５６の行う計算をしても良い。即ち、第１演算部５５が、第２演算部５６のjを逆順に計算するようにしても良い。
【０１０５】
[第１１の実施の形態]
次に、演算装置の第１１の実施の形態について説明する。なお、上述の第１の実施の形態乃至第１０の実施の形態と共通する部分については、同一の符号を使用して説明したり、説明を省略したりする。
【０１０６】
本実施の形態においては、上述の第１０の実施の形態で説明した代数的トーラスにおけるべき乗の計算を、Toom-Cook法を用いて行なう例について説明する。図１５は、本実施の形態にかかるテーブル作成装置７０の機能的構成を例示する図である。図１６は、本実施の形態にかかる演算装置５０の機能的構成を例示する図である。本実施の形態にかかるテーブル作成装置７０の機能的構成は、図１２に示した第１０の実施の形態における機能的構成と略同様であり、本実施の形態にかかる演算装置５０の機能的構成は、図１３に示した第１０の実施の形態における機能的構成と略同様であるが、Toom-Cook法を用いて代数的トーラスにおけるべき乗の計算を実行する点が異なるため、その点について説明する。
【０１０７】
従来の技術では、入力されたアフィン表現を式１４により射影表現に変換してから、テーブルの作成を実行し、得られた乗算の結果の値をそのままテーブルに保持していた。従来の技術でToom-Cook法を用いてべき乗の計算を実行する場合の計算コストについて説明する。
［Ｔ０］M+2S+B、
［Ｔ１］第７の実施の形態で説明した従来の技術と同様に1回あたり8M+3Bの計算コスト、
［Ｔ２］6個のFp^mの元のうち2要素を0とする射影表現と一般の射影表現と代数的トーラスにおける乗算なので1回あたり10M+4Bの計算コスト
である。
テーブルのエントリはT1を除き一般の射影表現である。簡単のため、全てのエントリが一般の射影表現として本計算の計算コストを見積もる。
［Ｍ１］〜［Ｍ３］一般の射影表現同士の代数的トーラスにおける乗算なので1回あたり11M+5Bの計算コスト、
［Ｍ４］一般の射影表現同士の代数的トーラスにおける平方なので1回あたり11S+5Bの計算コスト
である。以上をまとめて、従来の技術における代数的トーラスのべき乗の計算コストを算出すると、テーブルの作成の計算コストは式３６により求められ、本計算の計算コストは式３７により求められる。
【０１０８】
【数２０】
2011010383.tif 000022
【０１０９】
【数２１】
2011010383.tif 000023
【０１１０】
次に、本実施の形態にかかる演算処理の手順について説明する。本実施の形態にかかる演算処理の手順を示すフローチャートは図１４に示されるものと略同様である。但し、本実施の形態では、ステップＳ９０で、表現変換部７１が、元gを表すアフィン表現を、式２３により制限射影表現に変換し、また、テーブル７５のエントリに対して、6次拡大の1要素を1とするような制限射影表現へ変換する。具体的には、第２の実施の形態乃至第５の実施の形態のようにα/βとせず、(a0,  a1,  a2,  b0,  0,  0)=(α・β^(p^2m+p^m),N(β))としてから、a0の逆元を第2要素乃至第4要素にかける。ここでN(β)はβのノルム写像である。そして、制御部７４が、テーブル７５にエントリを記憶させることにより、テーブル７５を作成する。このようなテーブル７５のエントリは演算装置５０のテーブル６０に記憶される。ステップＳ９１では、第１演算部５５が、ステップＳ９０で変換された制限射影表現を用いて、制限Fp^mnFrobenius写像及び制限Fp^mn乗算を実行する。ステップＳ９２では、ステップＳ９１の演算の結果得られる制限射影表現を用いて、第２演算部５６が、平方及び乗算を実行する。
【０１１１】
次に、本実施の形態でToom-Cook法を用いてべき乗の計算を実行する場合の計算コストの例について説明する。
［Ｔ０］I+4M+2S+B、
［Ｔ１］〜［Ｔ２］第８の実施の形態と同様に1回あたり5M+3Bの計算コスト、
［Ｔ３］テーブル７５のエントリの表現変換は最大(2^(win-1)-1)回で、1回あたりI+21Mの計算コスト
である。テーブル７５のエントリは全て、6個のFp^mの元のうち2要素を0、1要素を1とする射影表現とする。
［Ｍ１］第８の実施の形態と同様に1回あたり5M+3Bの計算コスト、
［Ｍ２］、一般の射影表現と6個のFp^mの元のうち2要素を0、1要素を1とする射影表現との代数的トーラスにおける乗算なので1回あたり8M+4Bの計算コスト、
［Ｍ３］一般の射影表現同士なので1回あたり11M+5Bの計算コスト、
［Ｍ４］一般の射影表現同士の代数的トーラスにおける平方なので1回あたり11S+5Bの計算コスト
である。以上をまとめて、本実施の形態における代数的トーラスのべき乗の計算コストを算出すると、テーブル７５の作成の計算コストは式３８により求められ、本計算の計算コストは式３９により求められる。
【０１１２】
【数２２】
2011010383.tif 000024
【０１１３】
【数２３】
2011010383.tif 000025
【０１１４】
Toom-Cook法を用いた場合の従来の技術における計算コストと本実施の形態にかかる計算コストとを比較すると、テーブル７５の作成にかかる計算コストの増加分は式４０により求められ、本計算にかかる計算コストの減少分は式４１により求められる。
【０１１５】
【数２４】
2011010383.tif 000026
【０１１６】
【数２５】
2011010383.tif 000027
【０１１７】
第１０の実施の形態のパラメータの具体例で、テーブル７５の作成にかかる計算コストの増加分は16I+251M-11B、本計算にかかる計算コストの減少分は359.16M+119.72Bである。代数的トーラスにおけるテーブル７５の作成を事前計算として行いべき乗の計算を本計算として行なうと、表現変換を実行しない場合に比べ事前計算と本計算とを合わせた総計算コストは{(16I+251M-11B)-(359.16M+119.72B)}だけ増加する。I＜6.76M+8.17Bが成り立つ場合には総計算コストが減少すると同時に、本計算の計算コストも72%程度に減少する。
【０１１８】
尚、上述の計算コストは元gを表すアフィン表現とテーブル７５のエントリTiを表すアフィン表現とを全て式２３により制限射影表現に変換する場合のものであるが、これらを異なる表現変換で制限射影表現に変換するようにしても良い。例えば、式１５により表現変換を実行するようにしても良いし、式１５や式２３における第2要素と第3要素との役割を入れ替えて表現変換を実行するようにしても良い。また、中間値Ajを更に表現変換しても良い。また、中間値Ajを保持せずに第１演算部５５が第２演算部の行う計算をしても良い即ち、第１演算部５６が、第２演算部５６のjを逆順に計算するようにしても良い。また、6次拡大体の基底はs  =  xyの他の多項式基底もしくは疑多項式基底でも良い。
【０１１９】
ここで上述の各実施の形態で用いた従来の計算方法であるKaratsuba法、Toom-Cook法、Complex法及びItoh-Tsujii法の概要について各々説明する。
【０１２０】
＜Karatsuba法＞
拡大体の乗算の計算法の一つ。拡大体の元を基礎体の元の組として(a0,  a1,  ・・・,  ak-1)および(b0,  b1,  ・・・,  bk-1)とする。拡大体の乗算にはai×bj,  0≦i≦k-1,  0≦j≦k-1の計k^2個の基礎体上乗算が登場する。これをai×bj,  0≦i=j≦k-1と(ai+  aj)×(bi  +  bj),  i≠j,  0≦i≦k-1,  0≦j≦k-1の計k(k+1)/2個の基礎体上乗算を計算し、その結果を用いて表現する。基礎体上乗算がk(k+1)/2個へ減る代わりに基礎体上加算が増えるが、通常、全体として計算コストは減少する。
【０１２１】
＜Toom-Cook法＞
拡大体の乗算の計算法の一つ。拡大体の元を基礎体の元を係数とする多項式表現としてa0  +  a1  x  +  a2  x^2  +  ・・・  +  ak-1x^(k-1)  および  b0  +  b1  x  +  b2  x^2  +  ・・・  +  bk-1x^(k-1)とする。基礎体上乗算としてxに値を代入した  v(x)  =  (a0  +  a1  x  +  a2  x^2  +  ・・・  +  ak-1x^(k-1))(b0  +  b1  x  +  b2  x^2  +  ・・・  +  bk-1x^(k-1))  を  (2k-1)  個計算する。例えば、v(0)  =  a0×b0,  v(1),  v(-1),  v(∞)  =  ak-1×bk-1など。拡大体の乗算結果の多項式の係数は、(2k-1)  個のx  =  0,  1,  -1,  ∞に対応した連立方程式を解くことによって、v(0),  v(1),  v(-1),  v(∞)で表される。基礎体上乗算が  (2k-1)  個へ減る代わりにkaratsuba法よりも基礎体上加算が増える。
【０１２２】
＜Complex法＞
2次拡大体の平方の計算法の一つ。拡大体の元を基礎体の元を係数とする多項式表現としてa0+  a1  xとする。法多項式をf2(x)  =  x^2  -  d  とする。(a0  +  a1  x)^2  =  (a0^2  +  d×a1^2)  +  (2  a0a1)  xなので、登場する基礎体上乗算は3個である。これを(a0  +  a1)(a0-  a1)  =  a0^2  -  a1^2となる性質を用いて、(a0+  a1)(a0  +d×a1),  a0  a1の2個で表現する。
【０１２３】
＜Itoh-Tsujii法＞
拡大体の逆元の計算法の一つ。拡大体の元のノルム写像を計算すると基礎体の元が得られる性質を用いて、基礎体の逆元を計算することで拡大体の逆元を表現する。拡大体の元をgとするとg^(-1)  =  v(g)×N(g)^(-1)、ここでN(g)はノルム写像、v(g)はノルム写像よりべき指数を1だけ少なくした写像とする。写像Nと写像vはFrobenius写像と乗算で計算できる。
【０１２４】
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【０１２５】
上述の各実施の形態においては、n=  L*r（L：正整数、r：正整数）であり、L=2である場合、演算部５２は、以下の(a)〜(d)のいずれかのようにして、制限Fp^mn乗算を実行しても良い。
(a)Fp^mrの乗算1回とその結果からFp^mの乗算r(r-1)/2回を使いまわして計算するFp^mrの乗算1回とFp^mrの加算とを実行する
(b)Fp^mrの乗算1回とその結果からFp^mの乗算r(r-1)/2回を使いまわして計算するFp^mrの乗算1回とFp^mの乗算1回とFp^mrの加算とを実行する
(c)Fp^mrの乗算2回とFp^mrの加算とを実行する
(d)Fp^mrの乗算2回とFp^mの乗算r回とFp^mrの加算とを実行する
ここで、(a)は(r-1)個の要素を零元0とする制限射影表現と、(r-1)個の要素を零元0かつ1個の要素を単位元1とする制限射影表現の間の計算の具体例である。(b)は(r-1)個の要素を零元0とする制限射影表現の間の計算、(c)は射影表現と(r-1)個の要素を零元0かつ1個の要素を単位元1とする制限射影表現の間の計算、(d)は射影表現と(r-1)個の要素を零元0かつ1個の要素を単位元1とする制限射影表現の間の計算の具体例である。
【０１２６】
また、上述の各実施の形態においては、n=  L*r（L：正整数、r：正整数）であり、L=2である場合、演算部５２は、制限Fp^mnFrobenius写像として、Fp^mrのFrobenius写像1回とFp^mのFrobenius写像1回とFp^mの定数の乗算1回とを実行するようにしても良い。これは、(r-1)個の要素を零元0とする制限射影表現の計算の具体例である。
【符号の説明】
【０１２７】
５０  演算装置
５１  表現変換部
５２  演算部
５３  制限写像部
５４  制限乗算部
５５  第１演算部
５６  第２演算部
５７  制限写像部
５８  制限乗算部
５９  制御部
６０  テーブル
６１  平方部
６２  乗算部
７０  テーブル作成装置
７１  表現変換部
７２  制限写像部
７３  制限乗算部
７４  制御部
７５  テーブル
【図１】
2011010383.tif 000028
【図２】
2011010383.tif 000029
【図３】
2011010383.tif 000030
【図４】
2011010383.tif 000031
【図５】
2011010383.tif 000032
【図６】
2011010383.tif 000033
【図７】
2011010383.tif 000034
【図８】
2011010383.tif 000035
【図９】
2011010383.tif 000036
【図１０】
2011010383.tif 000037
【図１１】
2011010383.tif 000038
【図１２】
2011010383.tif 000039
【図１３】
2011010383.tif 000040
【図１４】
2011010383.tif 000041
【図１５】
2011010383.tif 000042
【図１６】
2011010383.tif 000043
【国際調査報告】
2011010383.tif 000044
2011010383.tif 000045
2011010383.tif 000046
2011010383.tif 000047