伸長装置および圧縮装置
【課題】有限体上の要素を効率的に伸長する。
【解決手段】伸長装置は、入力部、算出部、第１選択部、伸長部を備える。入力部は、有限体の乗法群の部分群の要素をトレース表現で表したトレース表現データに変換するときに得られる付加データと、トレース表現データとを入力する。算出部は、トレース表現データによって決定される連立方程式の複数の解を算出する。第１選択部は、付加データに基づいて、複数の解から求められるデータであって、部分群の要素をアフィン表現で表した複数のアフィン表現データのうちいずれかを選択する。伸長部は、選択されたアフィン表現データを要素に伸長する。
【解決手段】伸長装置は、入力部、算出部、第１選択部、伸長部を備える。入力部は、有限体の乗法群の部分群の要素をトレース表現で表したトレース表現データに変換するときに得られる付加データと、トレース表現データとを入力する。算出部は、トレース表現データによって決定される連立方程式の複数の解を算出する。第１選択部は、付加データに基づいて、複数の解から求められるデータであって、部分群の要素をアフィン表現で表した複数のアフィン表現データのうちいずれかを選択する。伸長部は、選択されたアフィン表現データを要素に伸長する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、有限体上の要素の伸長装置および圧縮装置に関する。
【背景技術】
【０００２】
一部の公開鍵暗号は、有限体（その集合の要素のみで四則演算ができる数の集合）の部分集合を利用して構成する。部分集合の要素数をＡとし、有限体の要素数をＢとすると、Ａ≦Ｂである。例えば、公開鍵暗号では、Ａ＝２＾１６０、Ｂ＝２＾１０２４が使われる。一般に、Ｘ個の要素を表現するのに必要なビット数は、ｌｏｇ＿２Ｘビットである。しかし、既存の公開鍵暗号では、部分集合のＡ個の要素しか使っていないにも関わらず、その要素を表現するのに必要なビット数がｌｏｇ＿２Ｂビットとなる方式が存在する。
【０００３】
代数的トーラスという有限体の部分集合の要素は、少ないビット数で表現できる。代数的トーラスの属する拡大体の次数が高々２つの素数ｐ、ｑの冪の積ｎ＝（ｐ＾ｍ）×（ｑ＾ｗ）であるとき、圧縮率（＝圧縮後のビット数／圧縮前のビット数）はφ（ｎ）／ｎとなることが知られている。ただし、φはオイラー関数である。
【０００４】
圧縮率１／４と圧縮率１／６とを実現する方法も知られている。この方法では、代数的トーラスの部分集合の要素を圧縮したデータＤ１を求め、データＤ１の一部を削除したデータＤ２と付加ビットを求めることで、さらなる圧縮を行う。そして、代数的トーラスの部分集合の条件式とデータＤ１とデータＤ２の関係から得られる多変数連立方程式を解くことで、データＤ２に対応するデータＤ１の候補を得て、付加ビットを利用して圧縮されたデータＤ１を特定する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】K．Rubin ａｎd A．Silverberg， “Torus−Based Cryptography”，CRYPTO 2003， LNCS 2729， 349−365， 2003．
【非特許文献２】K．Karabina，“Torus−based Compression by Factor 4 ａｎd 6”，Cryptology ePrint Archive，Report 2010／525．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術では、圧縮装置および伸長装置を効率的に実現するために、代数的トーラスの基礎体の法多項式に制約が置かれていた。そのため、制約条件を満たさない法多項式を利用した場合、効率的に伸長できるとは限らなかった。
【課題を解決するための手段】
【０００７】
実施形態の伸長装置は、入力部、算出部、第１選択部、伸長部を備える。入力部は、有限体の乗法群の部分群の要素をトレース表現で表したトレース表現データに変換するときに得られる付加データと、トレース表現データとを入力する。算出部は、トレース表現データによって決定される連立方程式の複数の解を算出する。第１選択部は、付加データに基づいて、複数の解から求められるデータであって、部分群の要素をアフィン表現で表した複数のアフィン表現データのうちいずれかを選択する。伸長部は、選択されたアフィン表現データを要素に伸長する。
【図面の簡単な説明】
【０００８】
【図１】第１の実施形態の圧縮装置のブロック図。
【図２】第１の実施形態の圧縮処理のフローチャート。
【図３】第１の実施形態の伸長装置のブロック図。
【図４】第１の実施形態の伸長処理のフローチャート。
【図５】第２の実施形態の圧縮装置のブロック図。
【図６】第２の実施形態の伸長装置のブロック図。
【図７】第３の実施形態の圧縮装置のブロック図。
【図８】第３の実施形態の伸長装置のブロック図。
【図９】第４の実施形態の伸長装置のブロック図。
【図１０】各実施形態の伸長装置および圧縮装置のハードウェア構成図。
【発明を実施するための形態】
【０００９】
以下に添付図面を参照して、この発明にかかる伸長装置の好適な実施形態を詳細に説明する。
【００１０】
（第１の実施形態）
第１の実施形態にかかる圧縮装置および伸長装置は、従来技術とは異なる制約を法多項式に置くことで、効率的に圧縮装置および伸長装置を構成する。本実施形態では、代数的トーラスの有限体表現の元（要素）をトレース表現と付加ビットで表すことで表現を圧縮し、そのトレース表現より決定できる多変数連立方程式の解と付加ビットとから代数的トーラスの有限体表現の要素に伸長する。多変数連立方程式を解くと、伸長候補となる複数の代数的トーラスの有限体表現の要素が得られるため、付加ビットを用いて圧縮前の要素を決定する。
【００１１】
（１）代数的トーラスの構成
最初に、以下の各実施形態で用いる用語および表記等について説明する。Ｆｐｍは、要素数ｐ＾ｍの有限体を表し、Ｆｐのｍ次拡大体と呼ぶ。例えば、Ｆ３ｍは、要素数が３つの有限体Ｆ３のｍ次拡大体を表す。また、ａ０、ａ１、・・・、ａｎ∈Ｆｑであるとき、多項式Ｆ（ｘ）＝ａ０＋ａ１×ｘ＋・・・＋ａｎ×ｘ＾ｎは、Ｆｑ上の多項式と呼ぶ。Ｆｑ上の多項式であることを表すために、Ｆ（ｘ）＝ａ０＋ａ１×ｘ＋・・・＋ａｎ×ｘ＾ｎ ｏｖｅｒ Ｆｑのように表記することもある。なお、「ａ＾ｂ」は、ａのｂ乗を表す。以下では、ａのｂ乗をａｂと表す場合もある。
【００１２】
ｎをｎ≡５ （ｍｏｄ １２）なる奇数とし、ｑ＝３＾ｎとし、有限体Ｆｑを考える。このとき、ｑ≡５ （ｍｏｄ ７）となる。また、法多項式として、Φ７＝ｘ＾６＋ｘ＾５＋ｘ＾４＋ｘ＾３＋ｘ＾２＋ｘ＋１を用いて、有限体Ｆｑの６次拡大体Ｆｑ６を考える。なお、法多項式はこれに限られるものではなく、例えばΦ９＝ｘ＾６＋ｘ＾３＋１などの別の法多項式を用いても良い。
【００１３】
このとき、Ｆｑ６上では、ｘ＾ｑ＝ｘ＾５、ｘ＾｛ｑ＾２｝＝ｘ＾４、ｘ＾｛ｑ＾３｝＝ｘ＾６、ｘ＾｛ｑ＾４｝＝ｘ＾２、ｘ＾｛ｑ＾５｝＝ｘ＾３が成立する。このとき、６次拡大体Ｆｑ６上の代数的トーラスＴ６（Ｆｑ）は、位数ｑ−√（３ｑ）＋１の部分群を持つ。ｑは、３の奇数乗であるため、√（３ｑ）は整数になる。ここで、√（３ｑ）＝ｔとおく。
【００１４】
トレース写像Ｔｒ：Ｆｑ６→Ｆｑを以下の（１）式のように定義する。Ｔｒ（ｇ）をｇのトレース表現と呼ぶ。
Ｔｒ（ｇ）＝ｇ＋ｇ＾ｑ＋ｇ＾｛ｑ＾２｝＋ｇ＾｛ｑ＾３｝＋ｇ＾｛ｑ＾４｝＋ｇ＾｛ｑ＾５｝・・・（１）
【００１５】
また、アフィン変換写像Ａｆ：Ｆｑ６→Ｆｑ３とアフィン変換逆写像Ａｆ＾｛−１｝：Ｆｑ３→Ｆｑ６を以下の（２）式のように定義する。
Ａｆ（ｇ）＝（Ｇ１＋１）／Ｇ２、
Ａｆ＾｛−１｝（Ａｆ（ｇ））＝（Ａｆ（ｇ）＋ｚ）／（Ａｆ（ｇ）＋ｚ＾ｑ）・・・（２）
【００１６】
ここで、ｚ：＝ｘ＋ｘ＾｛ｑ＾２｝＋ｘ＾｛ｑ＾４｝＝ｘ＋ｘ＾２＋ｘ＾４、ｇ：＝ａ０＋ａ１×ｘ＋ａ２×ｘ＾２＋ａ３×ｘ＾３＋ａ４×ｘ＾４＋ａ５×ｘ＾５＝（ａ０＋ａ３×ｘ＾３＋ａ５×ｘ＾５）＋（ａ１×ｘ＋ａ２×ｘ＾２＋ａ４×ｘ＾４）＝Ｇ１＋Ｇ２×ｚ（ただし、Ｇ１、Ｇ２∈Ｆｑ３）とする。Ａｆ（ｇ）をｇのアフィン表現と呼ぶ。
【００１７】
（２）圧縮装置の構成
次に、第１の実施形態の圧縮装置および伸長装置の構成例について説明する。図１は、第１の実施形態にかかる圧縮装置１００の構成の一例を示すブロック図である。図１に示すように、圧縮装置１００は、入力部１０１と、第１変換部１０２と、第２変換部１０３と、付加ビット決定部１０４と、出力部１０５と、記憶部１２１と、を備えている。
【００１８】
入力部１０１は、圧縮する代数的トーラスの部分群の要素を入力する。第１変換部１０２は、入力された要素をトレース表現で表したトレース表現データに変換する。以下では、トレース表現データを単にトレース表現ともいう。第１変換部１０２は、上述のトレース写像Ｔｒより、入力された要素をトレース表現に変換する。
【００１９】
第２変換部１０３は、入力された要素をアフィン表現で表したアフィン表現データに変換する。以下では、アフィン表現データを単にアフィン表現ともいう。第２変換部１０３は、上述のアフィン変換写像Ａｆにより、入力された要素をアフィン表現に変換する。
【００２０】
付加ビット決定部１０４は、有限体の乗法群（有限体表現の代数的トーラス）の部分群の要素をトレース表現で表したトレース表現データと有限体の乗法群の部分群の要素をアフィン表現で表したアフィン表現データとに基づいて付加ビットを決定する。付加ビット決定部１０４は、トレース表現およびアフィン表現から、所定の連立方程式の解からアフィン表現を求めるための付加データ（以下、付加ビットという）を決定する。つまり、有限体の乗法群（有限体表現の代数的トーラス）の部分群の要素をトレース表現で表したトレース表現データを伸長して得られるアフィン表現の候補（複数）と、有限体の乗法群（有限体表現の代数的トーラス）の部分群の要素のアフィン表現で表したアフィン表現データとに基づいて付加ビットを決定する。
出力部１０５は、トレース表現と付加ビットとを出力する。記憶部１２１は、付加ビットの決定に用いる予め導出された式を求めるための情報を記憶する。
【００２１】
次に、このように構成された第１の実施形態にかかる圧縮装置１００による圧縮処理について図２を用いて説明する。図２は、第１の実施形態における圧縮処理の全体の流れを示すフローチャートである。
【００２２】
入力部１０１は、代数的トーラスの部分群の要素ｇを入力する（ステップＳ１０１）。第１変換部１０２は、トレース写像にｇを入力し、トレース表現Ｔｒ（ｇ）を計算する（ステップＳ１０２）。第２変換部１０３は、アフィン写像にｇを入力し、アフィン表現（α＋１、β＋１、γ＋１）∈Ｆｑ３を計算する（ステップＳ１０３）。付加ビット決定部１０４は、トレース表現と代数的トーラスの条件と有限体の条件とにより決定される多変数連立方程式を決定する（ステップＳ１０４）。付加ビット決定部１０４は、多変数連立方程式を解くことにより付加ビットを決定する（ステップＳ１０５）。具体的には、付加ビット決定部１０４は、多変数連立方程式を解いて６つの解｛（ａｉ、ｂｉ、ｃｉ）｝＿｛ｉ＝１、・・・、６｝を得て、６つの解を大きい順に並べ、ｇのアフィン表現と一致するｉ番目の要素を決定して、ｉを付加ビットとして決定する。出力部１０５は、トレース表現と付加ビットと（Ｔｒ（ｇ）、ｉ）を出力する（ステップＳ１０６）。なお、付加ビットの決め方は、６つの解を大きい順に並べて決定するだけでなく、例えば小さい順に並べて決定するなどのように、６つの解を区別できれば何でもよい。
【００２３】
本実施形態では、トレース写像Ｔｒ：Ｆｑ６→Ｆｑにより、圧縮率１／６の圧縮が実現できる。なお、１≦ｉ≦６なので、ｉは３ビットで表現できる。すなわち、付加ビットｉは圧縮率１／６にほとんど影響しない。
【００２４】
多変数連立方程式の決定方法（ステップＳ１０４）、および、多変数連立方程式の解法（ステップＳ１０５）は、伸長装置２００と同じ構成で実現できる。これらの各処理の詳細は、伸長装置２００の構成の説明時に詳述する。
【００２５】
（３）伸長装置の構成
図３は、第１の実施形態にかかる伸長装置２００の構成の一例を示すブロック図である。図３に示すように、伸長装置２００は、入力部２０１と、算出部２１０と、第１選択部２０２と、伸長部２０３と、出力部２０４と、記憶部２２１と、を備えている。
【００２６】
入力部２０１は、圧縮装置１００から出力されるトレース表現と付加ビットとを入力する。算出部２１０は、入力されたトレース表現から上述の多変数連立方程式を決定し、多変数連立方程式の解を算出する。算出部２１０は、第１式決定部２１１と、第１求解部２１２と、第２式決定部２１３と、第２求解部２１４と、第３式決定部２１５と、第３求解部２１６と、を備えている。
【００２７】
第１式決定部２１１は、有限体Ｆｑ上の予め求められたｋ１次式（ｋ１は予め定められる１以上の整数）の予め定められた係数に、入力されたトレース表現データを入力して得られる第１式を決定する。以下では、２次式（ｋ１＝２）である第１式を決定する例を説明する。第１求解部２１２は、第１式の解を求める。
【００２８】
第２式決定部２１３は、有限体Ｆｑ上の予め求められたｋ２次式（ｋ２は予め定められる１以上の整数）の予め定められた係数に、第１求解部２１２により求められた解の少なくとも１つを入力して得られる第２式を決定する。以下では、３次式（ｋ２＝３）である第２式を決定する例を説明する。第２求解部２１４は、第２式の解を求める。
【００２９】
第３式決定部２１５は、有限体Ｆｑ上の予め求められたｋ３次式（ｋ３は予め定められる１以上の整数）の予め定められた係数に、第１求解部２１２により求められた解および第２求解部２１４により求められた解のうち少なくとも１つを入力して得られる第３式を決定する。以下では、１次式（ｋ３＝１）である第３式を決定する例を説明する。第３求解部２１６は、第３式の解を求める。
【００３０】
第１選択部２０２は、算出部２１０により算出された複数の解から複数のアフィン表現を求め、求めたアフィン表現のうち、付加データに対応するいずれかのアフィン表現を選択する。伸長部２０３は、選択されたアフィン表現を、圧縮前の代数的トーラスの部分群の要素に伸長する。伸長部２０３は、上述のアフィン変換逆写像Ａｆ＾｛−１｝により、アフィン表現を圧縮前の要素に変換する。出力部２０４は、伸長された代数的トーラス部分群の要素を出力する。
【００３１】
記憶部２２１は、圧縮装置１００の記憶部１２１と同様に、付加ビットの決定に用いた予め導出された式を求めるための情報を記憶する。なお、記憶部１２１および記憶部２２１は、ＨＤＤ（Hard Disk Drivｅ）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００３２】
次に、このように構成された第１の実施形態にかかる伸長装置２００による伸長処理について図４を用いて説明する。図４は、第１の実施形態における伸長処理の全体の流れを示すフローチャートである。
【００３３】
入力部２０１は、トレース表現Ｔ∈Ｆｑと付加ビットｊ∈Ｆ２＾３とを入力する（ステップＳ２０１）。算出部２１０は、入力されたトレース表現から多変数連立方程式を決定し、多変数連立方程式の解を算出する（ステップＳ２０２）。算出部２１０による算出処理の詳細は後述する。
【００３４】
第１選択部２０２は、算出された解と、入力された付加ビットとから、アフィン表現を選択（決定）する（ステップＳ２０３）。伸長部２０３は、アフィン表現を代数的トーラスの部分群の要素ｇに伸長する（ステップＳ２０４）。出力部２０４は、伸長により得られた代数的トーラスの部分群の要素ｇを出力する（ステップＳ２０５）。
【００３５】
次に、ステップＳ２０２の算出部２１０による算出処理の詳細について説明する。
【００３６】
まず、第１式決定部２１１は、以下の（３）式で表される２次式Ａ（ｘ）を決定する（ステップＳ２０２）。
Ａ（ｘ）：ｘ＾２＋（Ｔ＾｛ｔ−２｝＋１）＾｛−１｝＝０ ｏｖｅｒ Ｆｑ・・・（３）
【００３７】
第１式決定部２１１は、例えば、上記Ａ（ｘ）を求めるための情報を記憶部２２１から読み出す。この情報は、例えば係数と変数の関係、トレース表現を入力する係数として予め定められた係数を特定する情報を含む。第１式決定部２１１は、このような情報を参照して、所定の係数に入力されたトレース表現を入力してＡ（ｘ）を決定する。第１式決定部２１１は、決定したＡ（ｘ）を第１求解部２１２に送る。
【００３８】
なお、所望のアフィン表現を（α＋１、β＋１、γ＋１）とすると、この２次式Ａ（ｘ）は、α＋β＋γを根に持つ。このような２次式Ａ（ｘ）を導出する手順については後述する。
【００３９】
第１求解部２１２は、Ａ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いてＦｑ上でＡ（ｘ）を因数分解し、Ａ（ｘ）＝０の解ａ１、ａ２を求める。第１求解部２１２は、求めた解ａ１、ａ２を第２式決定部２１３と第３式決定部２１５とに送る。
【００４０】
第２式決定部２１３は、解ａ１、ａ２が入力されると、以下の（４）式および（５）式で表される３次式Ｂ（ｘ）およびＣ（ｘ）を決定する。
Ｂ（ｘ）：ｘ＾３−ａ１×ｘ＾２−（ａ１＾２−１）ｘ−Ｚ（ａ１）＝０ ｏｖｅｒ Ｆｑ・・・（４）
Ｃ（ｘ）：ｘ＾３−ａ２×ｘ＾２−（ａ２＾２−１）ｘ−Ｚ（ａ２）＝０ ｏｖｅｒ Ｆｑ・・・（５）
【００４１】
ただし、Ｚ（ｘ）＝ｘ＾３−Ｙ（ｘ）＋（ｘ×Ｙ（ｘ）−Ｙ（ｘ）＾２−１）／ｘ＾３ ｏｖｅｒ Ｆｑ、Ｙ（ｘ）＝（−１−ｘ＾２）／ｘ＾ｔ−ｘ ｏｖｅｒ Ｆｑである。第２式決定部２１３は、Ｂ（ｘ）およびＣ（ｘ）を第２求解部２１４に送る。
【００４２】
所望のアフィン表現を（α＋１、β＋１、γ＋１）とすると、これらの３次式の一方は、βを根に持つ。このような３次式Ｂ（ｘ）およびＣ（ｘ）を導出する手順については後述する。
【００４３】
第２求解部２１４は、Ｂ（ｘ）およびＣ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＢ（ｘ）およびＣ（ｘ）を因数分解し、Ｂ（ｘ）＝０の解ｂ１、ｂ２、ｂ３と、Ｃ（ｘ）＝０の解ｃ１、ｃ２、ｃ３を求める。第２求解部２１４は、解（ｂ１、ｂ２、ｂ３）と（ｃ１、ｃ２、ｃ３）を第３式決定部２１５に送る。
【００４４】
第３式決定部２１５は、（ａ１、ａ２）と（ｂ１、ｂ２、ｂ３）と（ｃ１、ｃ２、ｃ３）とを入力されると、以下の（６）式〜（１１）式で表される１次式Ｄ（ｘ）、Ｅ（ｘ）、Ｆ（ｘ）、Ｇ（ｘ）、Ｈ（ｘ）およびＩ（ｘ）を決定する。
Ｄ（ｘ）：（−ｂ１＾｛２｝＋（ａ１＋（１／ａ１））×ｂ１）×ｘ＋Ｚ（ａ１）＋（−ａ１＋（１／ａ１））×ｂ１＾２−（Ｙ（ａ１）／ａ１）×ｂ１＝０ ｏｖｅｒ Ｆｑ・・・（６）
Ｅ（ｘ）：（−ｂ２＾｛２｝＋（ａ１＋（１／ａ１））×ｂ２）×ｘ＋Ｚ（ａ１）＋（−ａ１＋（１／ａ１））×ｂ２＾２−（Ｙ（ａ１）／ａ１）×ｂ２＝０ ｏｖｅｒ Ｆｑ・・・（７）
Ｆ（ｘ）：（−ｂ３＾｛２｝＋（ａ１＋（１／ａ１））×ｂ３）×ｘ＋Ｚ（ａ１）＋（−ａ１＋（１／ａ１））×ｂ３＾２−（Ｙ（ａ１）／ａ１）×ｂ３＝０ ｏｖｅｒ Ｆｑ・・・（８）
Ｇ（ｘ）：（−ｃ１＾｛２｝＋（ａ２＋（１／ａ２））×ｃ１）×ｘ＋Ｚ（ａ２）＋（−ａ２＋（１／ａ２））×ｃ１＾２−（Ｙ（ａ２）／ａ２）×ｃ１＝０ ｏｖｅｒ Ｆｑ・・・（９）
Ｈ（ｘ）：（−ｃ２＾｛２｝＋（ａ２＋（１／ａ２））×ｃ２）×ｘ＋Ｚ（ａ２）＋（−ａ２＋（１／ａ２））×ｃ２＾２−（Ｙ（ａ２）／ａ２）×ｃ２＝０ ｏｖｅｒ Ｆｑ・・・（１０）
Ｉ（ｘ）：（−ｃ３＾｛２｝＋（ａ２＋（１／ａ２））×ｃ３）×ｘ＋Ｚ（ａ２）＋（−ａ２＋（１／ａ２））×ｃ３＾２−（Ｙ（ａ２）／ａ２）×ｃ３＝０ ｏｖｅｒ Ｆｑ・・・（１１）
【００４５】
第３式決定部２１５は、Ｄ（ｘ）、Ｅ（ｘ）、Ｆ（ｘ）、Ｇ（ｘ）、Ｈ（ｘ）およびＩ（ｘ）を第３求解部２１６へ送る。
【００４６】
なお、所望のアフィン表現を（α＋１、β＋１、γ＋１）とすると、これらの１次式の１つは、γを根に持つ。このような１次式Ｄ（ｘ）、Ｅ（ｘ）、Ｆ（ｘ）、Ｇ（ｘ）、Ｈ（ｘ）およびＩ（ｘ）を導出する手順については後述する。
【００４７】
第３求解部２１６は、Ｄ（ｘ）＝０、Ｅ（ｘ）＝０、Ｆ（ｘ）＝０、Ｇ（ｘ）＝０、Ｈ（ｘ）＝０、およびＩ（ｘ）＝０が入力されると、それらの解ｄ、ｅ、ｆ、ｇ、ｈ、ｉを求める。また、第３求解部２１６は、これらの解および上記３次式Ｂ（ｘ）およびＣ（ｘ）の解であるｂ１、ｂ２、ｂ３、ｃ１、ｃ２、ｃ３から、６個の解の組（ａ１−ｂ１−ｄ、ｂ１、ｄ）、（ａ１−ｂ２−ｅ、ｂ２、ｅ）、（ａ１−ｂ３−ｆ、ｂ３、ｆ）、（ａ２−ｃ１−ｇ、ｃ１、ｇ）、（ａ２−ｃ２−ｈ、ｃ２、ｈ）、（ａ２−ｃ３−ｉ、ｃ３、ｉ）を第１選択部２０２に送る。
【００４８】
第１選択部２０２は、６個の解の組と付加ビットｊ（１≦ｊ≦６）とを受け取ったら、６個の解それぞれの各要素に１を加えた（ａ１−ｂ１−ｄ＋１、ｂ１＋１、ｄ＋１）、（ａ１−ｂ２−ｅ＋１、ｂ２＋１、ｅ＋１）、（ａ１−ｂ３−ｆ＋１、ｂ３＋１、ｆ＋１）、（ａ２−ｃ１−ｇ＋１、ｃ１＋１、ｇ＋１）、（ａ２−ｃ２−ｈ＋１、ｃ２＋１、ｈ＋１）、（ａ２−ｃ３−ｉ＋１、ｃ３＋１、ｉ＋１）を算出する。そして、第１選択部２０２は、算出した６個の解を所定の基準に従い整列する。以下では大きい順に整列するものとするが、基準はこれに限られるものではない。
【００４９】
第１選択部２０２は、整列した６個の解のうちｊ番目に大きい値を選択する。この値が、所望のアフィン表現に相当する。第１選択部２０２は、選択した値（アフィン表現）を伸長部２０３に送る。
【００５０】
伸長部２０３は、受け取ったアフィン表現をアフィン変換逆写像Ａｆ＾｛−１｝により代数的トーラス部分群の有限体表現に変換し出力する。
【００５１】
このように、第１の実施形態にかかる圧縮装置および伸長装置では、従来の方法では効率的に伸長写像が構成できない法多項式に対して、効率的に圧縮装置および伸長装置を実現することができる。また、本実施形態の圧縮装置および伸長装置では、代数的トーラスの部分群上のある要素ｇとフロベニウス写像を計算した要素ｇ’について、それらのトレース表現Ｔｒ（ｇ）とＴｒ（ｇ’）は等しいという性質を利用し、トレース表現Ｔｒ（ｇ）を伸長することなく、付加ビットを操作することでＴｒ（ｇ’）を計算することができる。
【００５２】
（第２の実施形態）
第２の実施形態にかかる伸長装置は、付加ビットの一部を用いて、解かなければならない式を絞り込む。これにより、より効率的に圧縮および伸長を実行可能となる。なお、代数的トーラスの構成は第１の実施形態と同様であるため説明を省略する。
【００５３】
（１）圧縮装置の構成
図５は、第２の実施形態にかかる圧縮装置１００−２の構成の一例を示すブロック図である。図５に示すように、圧縮装置１００−２は、入力部１０１と、第１変換部１０２と、第２変換部１０３と、付加ビット決定部１０４−２と、出力部１０５と、記憶部１２１と、を備えている。
【００５４】
第２の実施形態では、付加ビット決定部１０４−２の機能が第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる圧縮装置１００のブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【００５５】
以下、第２の実施形態の付加ビット決定部１０４−２による付加ビットの決定処理について説明する。
【００５６】
第１変換部１０２および第２変換部１０３によりトレース表現Ｔｒ（ｇ）およびアフィン表現（α＋１、β＋１、γ＋１）が計算されると（図２のステップＳ１０２、ステップＳ１０３）、付加ビット決定部１０４−２は、トレース表現と代数的トーラスの条件と有限体の条件とにより決定される２次式を解いて解ａ１、ａ２を求める。付加ビット決定部１０４−２は、求めた解ａ１、ａ２を大きい順に並べ替え、ｇのアフィン表現の各要素の和α＋β＋γ＋３ ｏｖｅｒ Ｆｑと一致するｉ１（ｉ１＝１または２）を付加ビット１として決定する。
【００５７】
つぎに、付加ビット決定部１０４−２は、トレース表現とアフィン表現の各要素の和とトーラスの条件と有限体の条件とから３次式を決定する。付加ビット決定部１０４−２は、３次式の解から１次式を決定し、３つのアフィン表現の候補を求める。付加ビット決定部１０４−２は、求めた候補を大きい順に整列して、ｇのアフィン表現と比較し、ｉ２（１≦ｉ２≦３）番目の要素と一致するとき、ｉ２を付加ビット２として決定する。なお、出力部１０５は、付加ビットｉ１およびｉ２をトレース表現とともに出力する。
【００５８】
なお、２次式と３次式と１次式の決定法と、求解法は、以下に述べる伸長装置２００−２と同じ構成で実現できる。
【００５９】
（２）伸長装置の構成
図６は、第２の実施形態にかかる伸長装置２００−２の構成の一例を示すブロック図である。図６に示すように、伸長装置２００−２は、入力部２０１と、算出部２１０−２と、第１選択部２０２−２と、伸長部２０３と、出力部２０４と、記憶部２２１と、を備えている。
【００６０】
第２の実施形態では、算出部２１０−２および第１選択部２０２−２の機能が第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる伸長装置２００のブロック図である図３と同様であるので、同一符号を付し、ここでの説明は省略する。
【００６１】
算出部２１０−２は、第２選択部２１７をさらに備えている。なお、第１式決定部２１１および第１求解部２１２の機能は第１の実施形態と同様であるため同一の符号を付し説明を省略する。
【００６２】
第２選択部２１７は、入力された付加ビットのうち付加ビット１（ｉ１）を用いて、第１求解部２１２により得られた解を大きい順に並べたときのｉ１番目の解を選択する。
【００６３】
第２式決定部２１３−２は、第２選択部２１７により選択された解を用いて第２式を決定する。第２求解部２１４−２は、第２式の解を求める。第３式決定部２１５−２は、第２選択部２１７により選択された解および第２求解部２１４−２により求められた解のうち少なくとも１つを入力して得られる第３式を決定する。第３求解部２１６−２は、第３式の解を求める。
【００６４】
第１選択部２０２−２は、付加データのうち付加データｉ２を用いて解を選択する点が、第１の実施形態の第１選択部２０２と異なる。
【００６５】
次に、第２の実施形態の算出部２１０−２による算出処理の詳細について説明する。
【００６６】
入力部２０１は、トレース表現Ｔ∈Ｆｑと付加ビット（ｉ１、ｉ２）∈Ｆ２×Ｆ２＾２とを入力すると、トレース表現Ｔを第１式決定部２１１に送る。第１式決定部２１１は、上述の処理により２次式Ａ（ｘ）を決定して第１求解部２１２に送る。第１求解部２１２は、Ｆｑ上でＡ（ｘ）を因数分解し、Ａ（ｘ）＝０の解ａ１、ａ２を求め、解ａ１、ａ２を第２選択部２１７に送る。
【００６７】
第２選択部２１７は、解ａ１、ａ２と付加ビット１（ｉ１）とが入力されると、解ａ１、ａ２を大きい順に整列して、ｉ１番目の要素を選択してａとし、第２式決定部２１３−２と第３式決定部２１５−２に送る。
【００６８】
第２式決定部２１３−２は、解ａが入力されると以下の（１２）式で表される３次式Ｂ（ｘ）を決定する。なお、Ｚ（ｘ）およびＹ（ｘ）は上述のとおりである。
Ｂ（ｘ）：ｘ＾３−ａ×ｘ＾２−（ａ＾２−１）ｘ−Ｚ（ａ）＝０ ｏｖｅｒ Ｆｑ・・・（１２）
【００６９】
第２式決定部２１３−２は、Ｂ（ｘ）を第２求解部２１４−２に送る。第２求解部２１４−２は、Ｂ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＢ（ｘ）を因数分解し、Ｂ（ｘ）＝０の解ｂ１、ｂ２、ｂ３を求める。第２求解部２１４−２は、解（ｂ１、ｂ２、ｂ３）を第３式決定部２１５−２に送る。
【００７０】
第３式決定部２１５−２は、（ａ）と（ｂ１、ｂ２、ｂ３）とを入力されると、以下の（１３）式〜（１５）式で表される１次式Ｄ（ｘ）、Ｅ（ｘ）、およびＦ（ｘ）を決定する。
Ｄ（ｘ）：（−ｂ１＾｛２｝＋（ａ＋（１／ａ））×ｂ１）×ｘ＋Ｚ（ａ）＋（−ａ＋（１／ａ））×ｂ１＾２−（Ｙ（ａ）／ａ）×ｂ１＝０ ｏｖｅｒ Ｆｑ・・・（１３）
Ｅ（ｘ）：（−ｂ２＾｛２｝＋（ａ＋（１／ａ））×ｂ２）×ｘ＋Ｚ（ａ）＋（−ａ＋（１／ａ））×ｂ２＾２−（Ｙ（ａ）／ａ）×ｂ２＝０ ｏｖｅｒ Ｆｑ・・・（１４）
Ｆ（ｘ）：（−ｂ３＾｛２｝＋（ａ＋（１／ａ））×ｂ３）×ｘ＋Ｚ（ａ）＋（−ａ＋（１／ａ））×ｂ３＾２−（Ｙ（ａ）／ａ）×ｂ３＝０ ｏｖｅｒ Ｆｑ・・・（１５）
【００７１】
第３式決定部２１５−２は、１次式Ｄ（ｘ）、Ｅ（ｘ）、およびＦ（ｘ）を第３求解部２１６−２へ送る。
【００７２】
第３求解部２１６−２は、Ｄ（ｘ）＝０、Ｅ（ｘ）＝０、およびＦ（ｘ）＝０が入力されると、それらの解ｄ、ｅ、ｆを求める。第３求解部２１６−２は、３個の解の組（ａ−ｂ１−ｄ、ｂ１、ｄ）、（ａ−ｂ２−ｅ、ｂ２、ｅ）、（ａ−ｂ３−ｆ、ｂ３、ｆ）を第１選択部２０２−２に送る。
【００７３】
第１選択部２０２−２は、３個の解と付加ビットｉ２（１≦ｉ２≦３）とを受け取ると、３個の解それぞれの各要素に１を加えた（ａ−ｂ１−ｄ＋１、ｂ１＋１、ｄ＋１）、（ａ−ｂ２−ｅ＋１、ｂ２＋１、ｅ＋１）、（ａ−ｂ３−ｆ＋１、ｂ３＋１、ｆ＋１）を算出する。そして、第１選択部２０２−２は、算出した３個の解を大きい順に整列する。第１選択部２０２−２は、整列した３個の解のうちｉ２番目に大きい値を選択する。この値が、所望のアフィン表現に相当する。第１選択部２０２−２は、選択した値（アフィン表現）を伸長部２０３に送る。伸長部２０３は、受け取ったアフィン表現を代数的トーラス部分群の有限体表現に変換し出力する。
【００７４】
このように、第２の実施形態にかかる圧縮装置および伸長装置では、付加ビットをｉ１およびｉ２に分けて算出し、付加ビットｉ１を用いて早い段階で解かなければならない式を絞り込むことができる。これにより、より効率的に圧縮および伸長を実行可能となる。
【００７５】
（第３の実施形態）
第３の実施形態では、第１の実施形態と同様の方法を、圧縮率１／４の圧縮に適用する例について説明する。
【００７６】
（１）代数的トーラスの構成
ｑ≡２ （ｍｏｄ ５）かつｑ＝２＾ｎかつｐ|（√（２ｑ））なる有限体Ｆｑを考える。また、法多項式としてΦ５＝ｘ＾４＋ｘ＾３＋ｘ＾２＋ｘ＋１を用いて、有限体Ｆｑの４次拡大体Ｆｑ４を考える。このとき、Ｆｑ４上では、ｘ＾ｑ＝ｘ＾２、ｘ＾｛ｑ＾２｝＝ｘ＾４、ｘ＾｛ｑ＾３｝＝ｘ＾３、ｘ＾｛ｑ＾４｝＝ｘが成立する。
【００７７】
このとき、４次拡大体Ｆｑ４上の代数的トーラスＴ４（Ｆｑ）は、位数ｑ−√（２ｑ）＋１の部分群を持つ。なお、ｑ≡２ （ｍｏｄ ５）より、ｎは奇数であるから、√（２ｑ）は整数になる。ここで、√（２ｑ）＝ｔとおく。
【００７８】
トレース写像Ｔｒ：Ｆｑ４→Ｆｑを以下の（１６）式のように定義する。
Ｔｒ（ｇ）＝ｇ＋ｇ＾ｑ＋ｇ＾｛ｑ＾２｝＋ｇ＾｛ｑ＾３｝・・・（１６）
【００７９】
また、アフィン変換写像Ａｆ：Ｆｑ４→Ｆｑ２とアフィン変換逆写像Ａｆ＾｛−１｝：Ｆｑ２→Ｆｑ４を以下の（１７）式のように定義する。
Ａｆ（ｇ）＝（Ｇ１＋１）／Ｇ２∈Ｆｑ２、
Ａｆ＾｛−１｝（Ａｆ（ｇ））＝（Ａｆ（ｇ）＋ｚ）／（Ａｆ（ｇ）＋ｚ＾ｑ）∈Ｆｑ４・・・（１７）
【００８０】
ここで、ｚ：＝ｘ＋ｘ＾ｑ＝ｘ＋ｘ＾２、ｇ：＝ａ０＋ａ１×ｘ＋ａ２×ｘ＾２＋ａ３×ｘ＾３＝（ａ０＋ａ３×ｘ＾３）＋（ａ１×ｘ＋ａ２×ｘ＾２）＝Ｇ１＋Ｇ２×ｚ（ただし、Ｇ１、Ｇ２∈Ｆｑ２）とする。
【００８１】
（２）圧縮装置の構成
図７は、第３の実施形態にかかる圧縮装置１００−３の構成の一例を示すブロック図である。図７に示すように、圧縮装置１００−３は、入力部１０１と、第１変換部１０２−３と、第２変換部１０３−３と、付加ビット決定部１０４−３と、出力部１０５と、記憶部１２１と、を備えている。第１の実施形態と同様の機能を備える構成部は図１と同一の符号を付し、説明を省略する。
【００８２】
第１変換部１０２−３は、（１６）式のトレース写像Ｔｒより、入力された要素ｇをトレース表現Ｔｒ（ｇ）に変換する。第２変換部１０３−３は、（１７）式のアフィン変換写像Ａｆにより、入力された要素ｇをアフィン表現（α、β）∈Ｆｑ×Ｆｑに変換する。付加ビット決定部１０４−３は、αの最下位ビットを付加ビット１として決定し、βの最下位ビットを付加ビット２として決定する。
【００８３】
（３）伸長装置の構成
図８は、第３の実施形態にかかる伸長装置２００−３の構成の一例を示すブロック図である。図８に示すように、伸長装置２００−３は、入力部２０１と、算出部２１０−３と、第１選択部２０２−３と、伸長部２０３−３と、出力部２０４と、記憶部２２１と、を備えている。第１の実施形態と同様の機能を備える構成部は図３と同一の符号を付し、説明を省略する。
【００８４】
算出部２１０−３は、第１式決定部２１１−３と、第１求解部２１２−３と、第２式決定部２１３−３と、第２求解部２１４−３と、を備えている。
【００８５】
第１式決定部２１１−３は、第１の実施形態と異なる２次式である第１式を決定する。第１求解部２１２−３は、第１式の解を求める。第２式決定部２１３−３は、第１の実施形態と異なり、２次式である第２式を決定する。第２求解部２１４−３は、第２式の解を求める。第１選択部２０２−３は、算出部２１０−３により算出された複数の解から、付加データに対応するいずれかの解を選択する。
【００８６】
次に、第３の実施形態の算出部２１０−３による算出処理の詳細について説明する。
【００８７】
トレース表現Ｔ∈Ｆｑと付加ビット（ｉ１、ｉ２）∈Ｆ２×Ｆ２とが入力されると、第１式決定部２１１−３は、以下の（１８）式で表される２次式Ａ（ｘ）を決定して第１求解部２１２−３に送る。
Ａ（ｘ）：ｘ＾２＋ｘ＋１−Ｔ＾｛ｑ−ｔ｝＝０ ｏｖｅｒ Ｆｑ・・・（１８）
【００８８】
第１求解部２１２−３は、Ａ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＡ（ｘ）を因数分解し、Ａ（ｘ）＝０の解ａ１、ａ２を得て、解ａ１、ａ２を第２式決定部２１３−３に送る。なお、第１求解部２１２−３は、フロベニウス写像を用いて、ｘ＾２の項を１次の項に変換し、変換した１次式を解いても良い。
【００８９】
第２式決定部２１３−３は、解ａ１、ａ２が入力されると、以下の（１９）式および（２０）式で表される２次式Ｂ（ｘ）およびＣ（ｘ）を決定し、第２求解部２１４−３に送る。
Ｂ（ｘ）：ｘ＾２＋ｘ＋ａ１＾２＋ａ１＾ｔ×Ｔ＾｛ｑ−ｔ｝＝０ ｏｖｅｒ Ｆｑ・・・（１９）
Ｃ（ｘ）：ｘ＾２＋ｘ＋ａ２＾２＋ａ２＾ｔ×Ｔ＾｛ｑ−ｔ｝＝０ ｏｖｅｒ Ｆｑ・・・（２０）
【００９０】
第２求解部２１４−３は、Ｂ（ｘ）、Ｃ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＢ（ｘ）およびＣ（ｘ）をそれぞれ因数分解し、Ｂ（ｘ）＝０の解ｂ１、ｂ２とＣ（ｘ）＝０の解ｃ１、ｃ２とを求める。第２求解部２１４−３は、解ｂ１、ｂ２、ｃ１、ｃ２を第１選択部２０２−３に送る。
【００９１】
第１選択部２０２−３は、解ｂ１、ｂ２、ｃ１、ｃ２と付加ビット１と付加ビット２とを受け取ると、４個の解の組（ａ１−ｂ１、ｂ１）、（ａ１−ｂ２、ｂ２）、（ａ２−ｃ１、ｃ１）、（ａ２−ｃ２、ｃ２）を求める。第１選択部２０２−３は、各組の１成分目（ａ１−ｂ１、ａ１−ｂ２、ａ２−ｃ１、ａ２−ｃ２）の最下位ビットと付加ビット１とを比較し、各組の２成分目（ｂ１、ｂ２、ｃ１、ｃ２）の最下位ビットと付加ビット２とを比較し、両方が一致した組を選択する。この組の値が、所望のアフィン表現に相当する。第１選択部２０２−３は、選択した値（アフィン表現）を伸長部２０３−３に送る。伸長部２０３−３は、受け取ったアフィン表現を代数的トーラス部分群の有限体表現に変換し出力する。
【００９２】
このように、第３の実施形態では、第１の実施形態と同様の手法で圧縮率１／４の圧縮および伸長を実現できる。
【００９３】
（第４の実施形態）
第４の実施形態では、第２の実施形態と同様の方法を、圧縮率１／４の圧縮に適用する例について説明する。なお、代数的トーラスの構成は第３の実施形態と同様であるため説明を省略する。また、第４の実施形態の圧縮装置は第３の実施形態の圧縮装置１００−３と同様である。
【００９４】
（１）伸長装置の構成
図９は、第４の実施形態にかかる伸長装置２００−４の構成の一例を示すブロック図である。図９に示すように、伸長装置２００−４は、入力部２０１と、算出部２１０−４と、第１選択部２０２−４と、伸長部２０３−３と、出力部２０４と、記憶部２２１と、を備えている。第３の実施形態と同様の機能を備える構成部は図８と同一の符号を付し、説明を省略する。
【００９５】
算出部２１０−４は、第１式決定部２１１−３と、第１求解部２１２−３と、第２選択部２１７−４と、第２式決定部２１３−４と、第２求解部２１４−４と、を備えている。
【００９６】
第２選択部２１７−４は、入力された付加ビットのうち付加ビット１（ｉ１）と付加ビット２（ｉ２）を用いて、第１求解部２１２−３により得られた解の最下位ビットと付加ビット１（ｉ１）と付加ビット２（ｉ２）のＦ２上の和を比較し、一致する解を選択する。第２式決定部２１３−４は、第２選択部２１７−４により選択された解を用いて第２式を決定する。第２求解部２１４−４は、第２式の解を求める。
【００９７】
次に、第４の実施形態の算出部２１０−４による算出処理の詳細について説明する。
【００９８】
トレース表現Ｔ∈Ｆｑと付加ビット（ｉ１、ｉ２）∈Ｆ２×Ｆ２とが入力されると、第１式決定部２１１−３は、上記（１８）式で表される２次式Ａ（ｘ）を決定して第１求解部２１２−３に送る。
【００９９】
第１求解部２１２−３は、Ａ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＡ（ｘ）を因数分解し、Ａ（ｘ）＝０の解ａ１、ａ２を求める。第１求解部２１２−３は、解ａ１、ａ２を第２選択部２１７−４に送る。なお、フロベニウス写像を用いて、ｘ＾２の項を１次の項に変換し、変換した１次式を解いても良い。
【０１００】
第２選択部２１７−４は、解ａ１、ａ２と付加ビット１（ｉ１）と付加ビット２（ｉ２）とが入力されると、付加ビット１（ｉ１）と付加ビット２（ｉ２）のＦ２での和と、解ａ１、ａ２の最下位ビットとを比較し、一致した解を選択して解ａとする。第２選択部２１７−４は、選択した解ａを第２式決定部２１３−４に送る。
【０１０１】
第２式決定部２１３−４は、解ａが入力されると、以下の（２１）式で表される２次式Ｂ（ｘ）を決定して、第２求解部２１４−４に送る。
Ｂ（ｘ）：ｘ＾２＋ｘ＋ａ＾２＋ａ＾ｔ×Ｔ＾｛ｑ−ｔ｝＝０ ｏｖｅｒ Ｆｑ・・・（２１）
【０１０２】
第２求解部２１４−４は、Ｂ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＢ（ｘ）を因数分解し、Ｂ（ｘ）＝０の解ｂ１、ｂ２を求める。第２求解部２１４−４は、解ｂ１、ｂ２を第１選択部２０２−４に送る。
【０１０３】
第１選択部２０２−４は、解ｂ１、ｂ２と付加ビット２（ｉ２）とを受け取ったら、付加ビット２（ｉ２）と解ｂ１、ｂ２の最下位ビットとを比較し、一致した解を選択して解ｂとする。また、第１選択部２０２−４は、解ａ、ｂから得られる（ａ−ｂ、ｂ）∈Ｆｑ×Ｆｑを伸長部２０３−３に送る。（ａ−ｂ、ｂ）が、所望のアフィン表現に相当する。
【０１０４】
なお、第１選択部２０２−４が、２つの解の組（ａ−ｂ１、ｂ１）と（ａ−ｂ２、ｂ２）とを求め、２成分目が付加ビット２（ｉ２）と一致する解の組（＝所望のアフィン表現）を選択するように構成してもよい。
【０１０５】
伸長部２０３−３は、受け取ったアフィン表現を代数的トーラス部分群の有限体表現に変換し出力する。
【０１０６】
このように、第４の実施形態では、第２の実施形態と同様の手法で圧縮率１／４の圧縮および伸長を実現できる。
【０１０７】
なお、上記各実施形態の圧縮装置および伸長装置は、例えば公開鍵暗号などの暗号化および復号を行う装置内に備えるように構成できる。例えば、公開鍵暗号による暗号化データを送信する情報処理装置（暗号化装置）内に圧縮装置を備え、暗号化データを受信して復号する情報処理装置（復号装置）内に伸長装置を備えるように構成できる。また、上記各実施形態の圧縮装置および伸長装置を共に備える圧縮伸長装置として構成してもよい。
【０１０８】
次に、上記各実施形態で用いた１次式〜３次式を導出する手順について説明する。最初に、圧縮率１／６の場合（第１および第２の実施形態）で用いる式の導出手順について説明する。
【０１０９】
（１）１／６圧縮
トーラスとしてＴ６（Ｆｑ）を考え、そのトーラスの部分群でトレース表現を取ることで、表現の圧縮を行う。Ｔ６（Ｆｑ）の位数は、円分多項式Φ６＝ｑ２−ｑ＋１である。円分多項式Φ６は、Φ６＝ｑ２−ｑ＋１＝（ｑ＋√（３ｑ）＋１）（ｑ−√（３ｑ）＋１）と因数分解できるので、（ｑ＋√（３ｑ）＋１）と（ｑ−√（３ｑ）＋１）が整数であれば、Ｔ６（Ｆｑ）を位数（ｑ＋√（３ｑ）＋１）の部分群と位数（ｑ−√（３ｑ）＋１）の部分群とに分割できる。すなわち、ｑを３の奇数乗に取ると、矛盾なく上記の因数分解により部分群が構成できる。
【０１１０】
ここで位数が（ｑ＋√（３ｑ）＋１）となる部分群をＧ＋、（ｑ−√（３ｑ）＋１）となる部分群をＧ−とする。Ｔ６（Ｆｑ）の部分群の元からトレース表現の元への写像は全単射ではないので、トレース表現の、ある元の逆像には複数のＴ６（Ｆｑ）の元が存在する。１つのトレース表現に対応するＴ６（Ｆｑ）の元は6つ存在するので、これらを識別するには少なくとも３ビットの付加ビットが必要となる。この３ビットの付加ビットを含めると、表現として必要なビット長はＧ＋，Ｇ−ともにｌｏｇ＿２（ｑ）＋３ビットとなるため、ｑよりも小さな群であるＧ−を必ずしも取る必要はないが、ここではＧ−を部分群として取ることとする。
【０１１１】
以下に、トレース表現とアフィン表現との関係を明らかにし、トレース表現からアフィン表現への伸張を可能とする手法を説明する。以降の演算は、特に断りが無い限り、Ｆ（３^ｎ）^６上の演算である。
【０１１２】
（２）準備
（２．１）拡大体に関する条件
有限体Ｆｑを法多項式Φ７で６次拡大した拡大体Ｆｑ６を考え、Ｔ６（Ｆｑ）の部分群Ｇ−の元に対する圧縮・伸長写像を構成する。代数的トーラスと法多項式Φ７とｑに対する条件は、以下の（２２）式で表される。
【数１】
【０１１３】
このとき、ｑ＝５ ｍｏｄ 7であるから、法多項式Φ７は、以下の（２３）式で表される。
【数２】
【０１１４】
次に、法多項式Φ７から構成されるＦｑ６に対して、その基礎体Ｆｑ２，Ｆｑ３を考え、Ｆｑ２の基底ｙとＦｑ３の基底ｚを、以下の（２４）式のように決める。
【数３】
【０１１５】
また、このとき法多項式Φ７とｑの条件から、yとｚに対して、以下の（２５）式および（２６）式の関係式が得られる。
【数４】
【０１１６】
なお、ｎは奇数でなければならないが、ｎ＝５ ｍｏｄ １２という条件は必ずしも必要ではないと考えられる。ここでは計算の簡略化のため、ｙｔ＝ｙ，ｚｔ＝ｚｑという形を作るためにこのような条件を置いた。
【０１１７】
ｆ∈Ｆｑ３は、Ｆｑ２の基底ｙとδ１，δ２，δ３∈Ｆｑを用いて、以下の（２７）式のように表現できる。また、ｆｔは以下の（２８）式のように表される。
【数５】
【０１１８】
（２．２）トレース写像とアフィン写像
Ｆｑ６のトレース写像Ｔｒ：Ｆｑ６→Ｆｑは、以下の（２９）式のように定義できる。
【数６】
【０１１９】
また、ｇ＝σ０＋σ１ｚ∈Ｔ６（Ｆｑ）に対して、アフィン写像ψ：Ｔ６（Ｆｑ）＼｛１｝→Ｆｑ３を、以下の（３０）式のように定義する。ここで、１はＦｑ６の乗法の単位元である。
【数７】
【０１２０】
さらに、アフィン逆写像ψ−１：Ｆｑ３→Ｔ６（Ｆｑ）＼｛１｝を、以下の（３１）式のように定義する。
【数８】
【０１２１】
このとき、以下の（３２）式が成り立つことが知られている。
【数９】
【０１２２】
（２９）式は、上述の（１）式のトレース写像Ｔｒに対応する。（３０）式および（３１）式は、上述の（２）式のアフィン変換写像Ａｆおよびアフィン変換逆写像Ａｆ＾｛−１｝に対応する。
【０１２３】
（３）Ｔ６（Ｆｑ）トレースの計算
ｇのトレース表現Ｔｒ（ｇ）とｇのアフィン表現（（２７）式のｆ）の間の関係式を導くために、アフィン表現の要素を用いて、トレース表現の要素を表現する。以下の（３３）式に示す。
【数１０】
【０１２４】
ここでｈ＝ｆ２−ｆ−１、Ａ１ｙ＋Ａ２ｙｑ＋Ａ３ｙ（ｑ＾３）＝ｈ−１とおくと、以下の（３４）式となる。
【数１１】
【０１２５】
したがって、Ｔｒ（ｇ）はｈ−１の各要素の和で表されることが分かる。ここで、ｈは以下の（３５）式のように表される。
【数１２】
【０１２６】
したがって、ｈ−１を計算し、各要素の和をとるとＴｒ（ｇ）が求まる。これらを式展開すると、Ｔｒ（ｇ）の分母部分は以下の（３６）式のようになる。分子部分は後述するためここでの説明は省略する。
【数１３】
【０１２７】
（４）Ｔ６（Ｆｑ）におけるＧ−の条件式
ｆ＾｛ｑ＋１｝は、以下の（３７）式で表される。
【数１４】
【０１２８】
Ｇ−の位数は、ｑ−ｔ＋１であるから、Ｇ−の元はｑ−ｔ＋１乗すると１になる。すなわち、以下の（３８）式となる。
【数１５】
【０１２９】
したがって、ｇｑ＋１＝ｇｔである。ｇｑ＋１＝ｇｔを整理していくと、以下の（３９）式のようになる。
【数１６】
【０１３０】
よって、Ｇ−の条件式は以下の（４０）式となる。（４０）式に示すように、いずれからも同じ式が導出される。
【数１７】
【０１３１】
ここから、上記（２７）式のｆを用いてさらに式展開すると、以下の（４１）式〜（４３）式が得られる。
【数１８】
【０１３２】
（４．１）Ｔ２（Ｆｑ）の条件式
Ｔ２（Ｆｑ３）∈Ｔ６（Ｆｑ）∈Ｇ−なので、Ｔ２（Ｆｑ３）の条件式も整理する。Ｔ２（Ｆｑ３）の位数はｑ２−ｑ＋１なので、ｇ＾（ｑ２−ｑ＋１）＝１が成立する。この式からδ１，δ２，δ３に関する条件式を整理する。以下の（４４）式に示す。
【数１９】
【０１３３】
よって、以下の（４５）式が得られる。
【数２０】
【０１３４】
ここから上記（２７）式を用いて変換を継続すると、以下の（４６）式の関係が得られる。この式も以降の式変形に利用する。
【数２１】
【０１３５】
（５）トレース値が同値なアフィン表現
ある元のトレース値とその元をｑ乗したトレース値とは同一となる。この性質から、同一のトレース値をとるアフィン表現は少なくとも６通り存在する。ここではこれらのアフィン表現の関係を見ていくことにする。ｆ∈Ｆｑ３とすると、関係式は以下の（４７）式のようになる。
【数２２】
【０１３６】
アフィン表現におけるｑ２乗は要素の入れ替えとなるので、ある元をｑ３乗した場合のアフィン表現の違いを見る。以下の（４８）式が成り立つため、ある元をｑ３乗するとアフィン表現上では各要素を２倍して１減じた値になる。
【数２３】
【０１３７】
上記（２７）式および上記（２５）式の第１式（ｙ＋ｙｑ＋ｙ＾（ｑ２）＝−１）であることに注意してトレース値が同一となる要素の組み合わせを導出すると、以下の６個の組み合わせが得られる。
・（δ１，δ２，δ３）
・（２δ３−１，２δ１−１，２δ２−１）
・（δ２，δ３，δ１）
・（２δ１−１，２δ２−１，２δ３−１）
・（δ３，δ１，δ２）
・（２δ２−1，２δ３−1，２δ１−１）
【０１３８】
ｑ２乗すると、各要素の入れ替えとなることがわかる。またα＝δ１−1、β＝δ２−1、γ＝δ３−1と置くと、以下の（４９）式のようになる。
【数２４】
【０１３９】
このｑ３乗は、以下の（５０）式で表される。
【数２５】
【０１４０】
このようにα、β、γを置いておくと、ｑ乗は２倍と要素の入れ替えと考えることができる。また２×２＝１ （ｍｏｄ ３）となることにも注意する。これ以降ではδ１，δ２，δ３をα＋１，β＋１，γ＋１と置き換えて式変形を行っていくことを考える。
【０１４１】
（５．１）Ｔ６（Ｆｑ）トレースの計算（その２）
α，β，γを用いてトレースの式を変形することを考える。上述の（３６）式を変形すると、以下の（５１）式となる。また、分子部分は以下の（５２）式となる。
【数２６】
【０１４２】
（５．２）Ｔ２（Ｆｑ）の条件式（その２）
上述の（４６）式をα，β，γを用いて変形すると、以下の（５３）式となる。
α２＋β２＋γ２＝１・・・（５３）
【０１４３】
（５．３）Ｔ６（Ｆｑ）におけるＧ−の条件式（その２）
上述の（４１）式〜（４３）式をα，β，γを用いて式変形すると、それぞれ以下の３つの式が得られる。
αｔ（γ−β）＋γｔ（α＋β＋γ）−αγ＋αβ＋α２＋β２＝１
βｔ（α−γ）＋αｔ（α＋β＋γ）−βα＋βγ＋β２＋γ２＝１
γｔ（β−α）＋βｔ（α＋β＋γ）−γβ＋γα＋γ２＋α２＝１
【０１４４】
この式の中に現れるｔ乗項は、以下の（５４）式のようになる。
【数２７】
【０１４５】
ここで（５３）式を用いると、以下の（５５）式が得られる。
【数２８】
【０１４６】
またこの式から、以下の（５６）式に示す関係も得られる。
【数２９】
【０１４７】
（５．４）Ｔ６（Ｆｑ）トレースの計算（その３）
（５３）式を用いて、（５１）式および（５２）式を変形する。このときに最終的には対称式である（α＋β＋γ），αβγの２種類と、非対称式である（αβ２＋βγ２＋γα２）を極力使用することとする。また、ここでは、Ａ＝α＋β＋γ，Ｂ＝αβ２＋βγ２＋γα２，Ｃ＝αβγを用いて式の簡略化も図る。
【０１４８】
まず、以下の（５７）式に示す関係がある。
【数３０】
【０１４９】
また、以下の（５８）式に示す関係がある。
【数３１】
【０１５０】
（５７）式および（５８）式より以下の（５９）式が得られる。
【数３２】
【０１５１】
よって、以下の（６０）式が得られる。
【数３３】
【０１５２】
また、Ｃについて考えると、以下の（６１）式および（６２）式が得られる。
【数３４】
【０１５３】
Ｔｒ（ｇ）を変形すると（５１）式および（５２）式より、以下の（６３）式および（６４）式が得られる。
【数３５】
【０１５４】
ここで分母分子に共通の因子が存在するため、これを約分すると、以下の（６５）式および（６６）式が得られる。
【数３６】
【０１５５】
これに（５６）式を用いて式変形を続けると、以下の（６７）式が得られる。
【数３７】
【０１５６】
（６）トレースからトーラスへの変換
これまでにＴｒ（ｇ）はＡ＝α＋β＋γとＣ＝αβγで書き表されることがわかった。ＣはＡとＢ＝αβ２＋βγ２＋γα２の式で書き表せ、ＢはＡで書き表せることを利用して、Ｔｒ（ｇ）の式をＡで書き表す。（６５）式より、以下の（６８）式が得られる。
【数３８】
【０１５７】
この両辺をｔ−２乗すると、以下の（６９）式が得られる。また、（６９）式から（７０）式が得られる。これにより、Ｔｒ（ｇ）からＡ＝α＋β＋γを求めることができる。
【数３９】
【０１５８】
（７）３次式の導出法
Ａ＝α＋β＋γとその他の関係式より、βを得る方法を示す。現在までに得られている関係式は、次のとおりである（（７１）式〜（７４）式）。
Ａ＝α＋β＋γ ・・・（７１）
Ｂ＝αβ２＋βγ２＋γα２ ・・・（７２）
Ｃ＝αβγ ・・・（７３）
α２＋β２＋γ２＝1 ・・・（７４）
【０１５９】
（７１）式を変形すると、以下の（７５）式が得られる。
α＝Ａ−β−γ ・・・（７５）
【０１６０】
（７５）式を（７２）式、（７３）式、（７４）式に代入して整理すると、以下の（７６）式〜（７８）式が得られる。
−β３＋γ３＋Ａβ２＋Ａβγ＋Ａγ２＋Ａ２γ−Ｂ＝０ ・・・（７６）
−β２γ−βγ２＋Ａβγ−Ｃ＝０ ・・・（７７）
−β２−βγ−γ２＋Ａβ＋Ａγ＋Ａ２−1＝０ ・・・（７８）
【０１６１】
（７８）式にβをかけると、以下の（７９）式が得られる。
−β３−β２γ−βγ２＋Ａβ２＋Ａβγ＋（Ａ２−１）β＝０・・・（７９）
【０１６２】
（７９）式から（７７）式を引いた式に−１をかけると、以下の（８０）式が得られる。
β３−Ａβ２−（Ａ２−１）β−Ｃ＝０・・・（８０）
【０１６３】
ここで、（５６）式よりＢ＝（（−1−Ａ２）／Ａｔ）−Ａとなり、（６１）式よりＣ＝Ａ３−Ｂ＋（ＡＢ−Ｂ２−１）／Ａ３であるから、ＣはＡで書き表すことができる。よって、βを根に持つ３次式である以下の３次式が得られた。この式を解くことで、βを得られる。
ｘ３−Ａｘ２−（Ａ２−１）ｘ−Ｃ＝０
【０１６４】
（８）１次式の導出法
Ａ＝α＋β＋γとβとその他の関係式より、γを得る方法を示す。（７８）式にγをかけると、以下の（８１）式が得られる。
−β２γ−βγ２−γ３＋Ａβγ＋Ａγ２＋（Ａ２−１）γ＝０・・・（８１）
【０１６５】
（８１）式から（７７）式を引くと、以下の（８２）式が得られる。
−γ３＋Ａγ２＋（Ａ２−１）γ＋Ｃ＝０・・・（８２）
【０１６６】
さらに、（７６）式から（８０）式を引き、（８２）式を足すと、以下の（８３）式が得られる。
Ａβγ−Ａγ２＋（−Ａ２＋１）β＋（−Ａ２−１）γ−Ｂ＝０・・・（８３）
【０１６７】
（８３）式にβをかけた式と、（７７）式にＡを書けた式は、それぞれ以下の（８４）式および（８５）式となる。
Ａβ２γ−Ａβγ２＋（−Ａ２＋１）β２＋（−Ａ２−１）βγ−Ｂβ＝０・・・（８４）
−Ａβ２γ−Ａβγ２＋Ａ２βγ−ＡＣ＝０・・・（８５）
【０１６８】
（８４）式）から（８５）式を引くと、以下の（８６）式が得られる。
−Ａβ２γ＋（−Ａ２＋１）β２＋（Ａ２−１）βγ−Ｂβ＋ＡＣ＝０・・・（８６）
【０１６９】
（８６）式をＡで割って、γについて整理すると、以下の（８７）式が得られる。
（−β２＋（Ａ−（１／Ａ））β）γ＋（−Ａ＋（１／Ａ））β２−Ｂβ／Ａ＋Ｃ＝０・・・（８７）
【０１７０】
前に求めた２次式と３次式の解より、Ａ，Ｂ，Ｃとβは定数値であるため、γを根にもつ１次式である以下の（８８）式が得られた。
（−β２＋（Ａ−（１／Ａ））β）ｘ＋（−Ａ＋（１／Ａ））β２−Ｂβ／Ａ＋Ｃ＝０・・・（８８）
【０１７１】
βとγが求まれば、（７１）式よりαが求まる。
【０１７２】
（９）まとめ
以下の（８９）式を解くことで、代数的トーラスの部分群の元のトレース表現Ｔｒ（ｇ）より、アフィン表現（α＋1，β＋1，γ＋１）を得る方法を与えた。
【数４０】
【０１７３】
具体的な手順は、次の通りである。
・α＋β＋γを根にもつ２次式である、ｘ２＝−［｛Ｔｒ（ｇ）｝ｔ−２＋１］−１を解いて、２つの解を得る。
・２つの解をそれぞれＡに代入して求めた、βを根にもつ３次式である、ｘ３−Ａｘ２−（Ａ２−１）ｘ−Ｃ＝０を解いて、それぞれ３つの解を得る。
・２次式の解の１つをＡに、Ａに対応する３次式の解の１つをβに代入して求めた、γを根にもつ１次式である、（−β２＋（Ａ−（１／Ａ））β）ｘ＋（−Ａ＋（１／Ａ））β２−Ｂβ／Ａ＋Ｃ＝０を解いて、それぞれ１つの解を求め、対応するαを計算する。
【０１７４】
以上より、計６個の（α，β，γ）が得られるため、付加ビットを用いて正しい（α，β，γ）を特定する。
【０１７５】
次に、圧縮率１／４の場合（第３および第４の実施形態）で用いる式の導出手順について説明する。
【０１７６】
（１）１／４圧縮
トーラスとしてＴ４（Ｆｑ）を考え、その部分群であるトレース（トレース表現）を取ることを考える。円分多項式Φ４を因数分解すると、Φ４＝ｑ２＋１＝（ｑ＋√（２ｑ）＋１）（ｑ−√（２ｑ）＋１）とすることができるので、これらの項が整数になればトーラスを部分群に分割することができる。具体的にはｑを２の奇数乗に取ると、矛盾なく上記の因数分解により部分群が構成できる。
【０１７７】
ここで位数が（ｑ＋√（２ｑ）＋１）となる部分群をＧ＋、（ｑ−√（２ｑ）＋１）となる部分群をＧ−とする。トーラスの中で部分群を取る元からトレースの元への写像は全単射ではないので、あるトレースの元から写像されるトーラスの元は複数存在する。１つのトレースの元に対応するトレースの元は４つ存在するので（詳細はトレース表現を参照のこと）これらを識別可能とするには２ビットの付加ビットが必要となる。これ以後の小節でトレースとアフィン表現の関係を明らかにし、トレースからアフィン表現への伸張を可能とする手法を説明していく。以降の演算は、特に断りが無い限り、Ｆ（２^ｎ）^４上の演算である。
【０１７８】
（２）準備
（２．１）条件の整理
ｔ＝√（２ｑ）と置く。
検討するトーラスやトレースに矛盾がでないよう、また式変形を容易に行えるように以下の（９０）式に示す定義とｑ≡ｔ≡２（ ｍｏｄ ５）という条件をおく。
【数４１】
【０１７９】
なお、上記定義と条件の下では計算上ｘ＝ｘ１,ｘｑ＝ｘ２,ｘ＾ｑ２＝ｘ４,ｘ＾ｑ３＝ｘ３という置き換えが可能である。このような定義と仮定を置くと、以下の（９１）式に示す条件式が得られる。
【数４２】
【０１８０】
（２．２）よく使う関係式
以下の（９２）式に、この後の式変形で用いるｆの関係式について、先にまとめて記載しておく。
【数４３】
【０１８１】
（３）トーラスの構成要素で表すトレース
トレースの値をアフィン表現で用いた係数を用いて表すとどのようになるかを計算していく。なお、Ｔ４のトレース表現Ｔｒ（ｇ）の定義式はＴｒ（ｇ）＝ｇ＋ｇｑ＋ｇ＾ｑ２＋ｇ＾ｑ３である（上述の（１６）式に対応）。以下の（９３）式がこの計算過程を示す式である。
【数４４】
【０１８２】
（４）Ｇ−の条件
ここではＧ−となる条件であるｇｑ＋１＝ｇｔとなる条件を導出する。以下の（９４）式に示すような式変形ができる。
【数４５】
【０１８３】
これ以後はｔ≡ｑ （ｍｏｄ ５）≡２ （ｍｏｄ ５）と仮定する。このときのｔはｔ＝２４ｋ＋１（ｋ∈Ｚ（整数の集合））という条件になり、前述の仮定と矛盾しない。なお、これ以外のパラメータでも構成は可能である。（９４）式からさらに以下の（９５）式に示すような式変形ができる。
【数４６】
【０１８４】
ここからｆ＝δ１ｙ＋δ２ｙｑを代入し、整理する。まずは、以下の（９６）式に示すように、式変形に用いる関係式をまとめて計算しておく。
【数４７】
【０１８５】
上記を使ってＧ−の条件式を再度整理すると、以下の（９７）式のように書ける。
【数４８】
【０１８６】
以上より、ｆ∈Ｇ−の条件は、以下の（９８）式となる。
【数４９】
【０１８７】
これらの条件式を加えて整理すると、以下の（９９）式となる。
【数５０】
【０１８８】
Ｇ−の元となるためには少なくともこの（９９）式を満たさなければならない。
【０１８９】
（５）ｑ乗による変化
Ｔ４のトレース表現Ｔｒ（ｇ）の定義式はＴｒ（ｇ）＝ｇ＋ｇｑ＋ｇ＾ｑ２＋ｇ＾ｑ３であるので、Ｔｒ（ｇｑ）＝ｇｑ＋ｇ＾ｑ２＋ｇ＾ｑ３＋ｇ、Ｔｒ（ｇ＾ｑ２）＝ｇ＾ｑ２＋ｇ＾ｑ３＋ｇ＋ｇｑ、Ｔｒ（ｇ＾ｑ３）＝ｇ＾ｑ３＋ｇ＋ｇｑ＋ｇ＾ｑ２という関係式が成り立つ。すなわち、あるトーラスの元ｇをｑ乗した元のトレースは、もとのトレースと同じ値となる関係がある。Ｇ−に属していたトーラスの元をｑ乗しても、やはりＧ−の元になることは明らかであるから、ある条件式をｑ乗しても性質は保たれるはずである。そこで、トーラスの元をｑ乗した場合に係数に起こる変化を眺め、その変化を以降の式変形に当てはめて用いることを考える。
【数５１】
以上の（１００）式に示すように式変形可能なので、ｆ＝δ１ｙ＋δ２ｙｑであることを考えると、（δ１,δ２）→（δ２＋１,δ１）というように係数が変化していることが分かる。このように変化してもＧ−の条件式もトーラスからトレースへの変換式も変化がない。実際、この変化を前述のＧ−の条件式に当てはめてみるともとの式に戻り、この変化によりＧ−の条件式が変化することはない。ここ以降ではｑ乗したように係数を変化させて得られる式の関係性をｑ乗対称の関係と呼ぶことにする。
【０１９０】
（６）トレースからトーラスへの伸張
トーラスからトレースへの変換式とＧ−の条件式を用いてトレースからトーラスへの変換式の導出を試みる。
（６．１）準備
以下では、トレースからトーラスへ変換する前に、必要となる関係式を導出しておく。δ１２＋δ２とδ１＋δ２２の関係式をＧ−の条件式である（９９）式から作成することを試みる。Ｇ−の条件式を整理すると（δ１＋δ２）ｔ＋１＝δ１ｔ＋δ２＋１である。これをｔ２＝２であることに注意してｔ−１乗すると、以下の（１０１）式となる。
【数５２】
【０１９１】
（１０１）式はｑ乗対称になっていない。ｑ乗対称性を満たすためには（δ１,δ２）→（δ２＋１,δ１）と係数を変化させても関係が保たれることが必要であるから、（１０１）式をｑ乗対称にした以下の（１０２）式も同時に満たされるはずである。
【数５３】
【０１９２】
一方、（１０１）式にδ１＋δ１２を加えた上で、（δ１＋δ２＋１）をかけると、以下の（１０３）式が得られる。
【数５４】
【０１９３】
左辺に（１０２）式を代入すると以下の（１０４）式が得られる。
【数５５】
【０１９４】
この式もｑ乗対称の関係を考え、（δ１,δ２）→（δ２＋１,δ１）と係数を変化させると、以下の（１０５）式が得られる。
【数５６】
【０１９５】
これらの２式（（１０４）式、（１０５）式）を加えると、以下の（１０６）式となり、以下の（１０７）式が得られる。
【数５７】
【０１９６】
この式でもｑ乗対称の関係を考え、（δ１,δ２）→（δ２＋１,δ１）と係数変化させると、以下の（１０８）式が得られ、δ１２＋δ２とδ１＋δ２２の関係式が得られた。
【数５８】
【０１９７】
（６．２）トレースの式変形
トレースの式をδ１,δ２で表すと、以下の（１０９）式のようになる。
【数５９】
【０１９８】
この式を少し整理し、以下の（１１０）式とする。
【数６０】
【０１９９】
ここでδ１２δ２２＋δ２３＝δ２２（δ１２＋δ２）,δ１３＋δ１δ２＝δ１（δ１２＋δ２）を用いて式変形すると、以下の（１１１）式となる。
【数６１】
【０２００】
ここで上述の（１０７）式および（１０８）式を代入すると、以下の（１１２）式となり、２元２次方程式が得られる。
【数６２】
【０２０１】
δ１＋δ２＝Ｘとおくと、上記（１１２）式は、以下の（１１３）式のような１元２次方程式に置き換わる。
【数６３】
【０２０２】
標数２の２次方程式の解の公式はないが、具体的に体を構成すると解が求まる。具体的にＸが求まれば、前述の（１０７）式の左辺がδ１２＋δ２＝（Ｘ−δ２）２＋δ２＝δ２２＋δ２＋Ｘ２と置き換えられることを利用し、以下の（１１４）式をδ２について解くことでδ１，δ２が求まる。
【数６４】
【０２０３】
なお、これらの（１１３）式および（１１４）式は、解が２つずつ出てくるため、２×２で４つの解が求まるはずである。これらの４解は同じトレース値から得られるもので、これら４つの解のうち、いずれの解がもとのトーラスの元を表しているかを特定するために付加ビットを利用することにする。
【０２０４】
これら４解は、それぞれｑ乗対称の関係にある。すなわち（δ１，δ２）→（δ２＋１，δ１）→（δ１＋１，δ２＋１）→（δ２＋１，δ１）（→（δ１，δ２））という関係である。ｑ乗するごとに矢印を右に進み、ｑ４乗するともとに戻ってくるというものである。この関係から、例えば、ある解のδ１，δ２の最下位１ビットに注目すると、それらが（０，０）であった場合のｑ乗対称の関係を見ていくと、（０，０）→（０，１）→（１，１）→（１，０）（→（０，０））という関係になり、それぞれが１乗、ｑ乗、ｑ２乗，ｑ３乗となっているはずである。このため、例えばδ１、δ２の最下位１ビットずつを付加ビットとして採用しておけば、トレースの元から、もとの正しいトーラスの元を特定することが可能である。
【０２０５】
（６．３）具体的構成例
以下に、トーラスのアフィン表現からトレースに変換する手法とトレースからトーラスのアフィン表現に変換する手法の一例を簡単に記す。
【０２０６】
（トーラスからトレース）
・入力：（δ１，δ２）
・出力：Ｔｒ（ｇ），（ｂ０，ｂ１）（ｂ０，ｂ１は付加ビット）
１．上記（１０９）式によりＴｒ（ｇ）を求める。
２．δ１の最下位ビットをｂ０、δ２の最下位ビットをｂ１とし、Ｔｒ（ｇ），（ｂ０，ｂ１）を出力する。
【０２０７】
（トレースからトーラス）
・入力：Ｔｒ（ｇ），（ｂ０，ｂ１）
・ 出力：（δ１，δ２）
１．Ｘ２＋Ｘ＋１＝｛Ｔｒ（ｇ）｝ｑ−ｔを解き、Ｘ０，Ｘ１を求める。
２．δ２２＋δ２＋Ｘ０２＋Ｘ０ｔ｛Ｔｒ（ｇ）｝ｑ−ｔ＝０を解き、δ２ａ，δ２ｂを求める。
３．Ｘ０＝δ１ａ＋δ２ａよりδ１ａを求める。
４．（δ１ａ，δ２ａ）の最下位ビットと（ｂ０，ｂ１）とを比べ、一致していなかったら５へ遷移し、一致していたら６へ遷移する。
５．（δ１ａ，δ２ａ）＝（δ２ａ＋１，δ１ａ）と設定しなおし、４へ戻る。
６．（δ１，δ２）＝（δ１ａ，δ２ａ）とし、（δ１，δ２）を出力する。
【０２０８】
（７）まとめ
以上で、トレースの元に付加ビットを加えたものからＴ４トーラスの元に復元する具体的手法を与えた。これにより従来のトーラスではもとの有限体の大きさと比べて１／３までしか表現の圧縮ができていなかったのに対し、漸近的に１／４まで圧縮が可能となった。
【０２０９】
以上説明したとおり、第１から第４の実施形態によれば、従来の方法では効率的に伸長写像が構成できない法多項式に対して、効率的に圧縮装置および伸長装置を実現することができる。
【０２１０】
次に、第１から第４の実施形態にかかる伸長装置および圧縮装置のハードウェア構成について図１０を用いて説明する。図１０は、第１から第４の実施形態にかかる伸長装置および圧縮装置のハードウェア構成を示す説明図である。
【０２１１】
第１から第４の実施形態にかかる伸長装置および圧縮装置は、ＣＰＵ（Central Processing Unit）５１などの制御装置と、ＲＯＭ（Read Only Memory）５２やＲＡＭ（Random Access Memory）５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、各部を接続するバス６１を備えている。
【０２１２】
第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムは、ＲＯＭ５２等に予め組み込まれて提供される。
【０２１３】
第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供されるように構成してもよい。
【０２１４】
さらに、第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０２１５】
第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムは、コンピュータを上述した伸長装置および圧縮装置の各部として機能させうる。このコンピュータは、ＣＰＵ５１がコンピュータ読取可能な記憶媒体からプログラムを主記憶装置上に読み出して実行することができる。
【０２１６】
なお、本実施形態は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【符号の説明】
【０２１７】
１００ 圧縮装置
１０１ 入力部
１０２ 第１変換部
１０３ 第２変換部
１０４ 付加ビット決定部
１０５ 出力部
１２１ 記憶部
２００ 伸長装置
２０１ 入力部
２０２ 第１選択部
２０３ 伸長部
２０４ 出力部
２１０ 算出部
２１１ 第１式決定部
２１２ 第１求解部
２１３ 第２式決定部
２１４ 第２求解部
２１５ 第３式決定部
２１６ 第３求解部
２１７ 第２選択部
２２１ 記憶部
【技術分野】
【０００１】
本発明の実施形態は、有限体上の要素の伸長装置および圧縮装置に関する。
【背景技術】
【０００２】
一部の公開鍵暗号は、有限体（その集合の要素のみで四則演算ができる数の集合）の部分集合を利用して構成する。部分集合の要素数をＡとし、有限体の要素数をＢとすると、Ａ≦Ｂである。例えば、公開鍵暗号では、Ａ＝２＾１６０、Ｂ＝２＾１０２４が使われる。一般に、Ｘ個の要素を表現するのに必要なビット数は、ｌｏｇ＿２Ｘビットである。しかし、既存の公開鍵暗号では、部分集合のＡ個の要素しか使っていないにも関わらず、その要素を表現するのに必要なビット数がｌｏｇ＿２Ｂビットとなる方式が存在する。
【０００３】
代数的トーラスという有限体の部分集合の要素は、少ないビット数で表現できる。代数的トーラスの属する拡大体の次数が高々２つの素数ｐ、ｑの冪の積ｎ＝（ｐ＾ｍ）×（ｑ＾ｗ）であるとき、圧縮率（＝圧縮後のビット数／圧縮前のビット数）はφ（ｎ）／ｎとなることが知られている。ただし、φはオイラー関数である。
【０００４】
圧縮率１／４と圧縮率１／６とを実現する方法も知られている。この方法では、代数的トーラスの部分集合の要素を圧縮したデータＤ１を求め、データＤ１の一部を削除したデータＤ２と付加ビットを求めることで、さらなる圧縮を行う。そして、代数的トーラスの部分集合の条件式とデータＤ１とデータＤ２の関係から得られる多変数連立方程式を解くことで、データＤ２に対応するデータＤ１の候補を得て、付加ビットを利用して圧縮されたデータＤ１を特定する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】K．Rubin ａｎd A．Silverberg， “Torus−Based Cryptography”，CRYPTO 2003， LNCS 2729， 349−365， 2003．
【非特許文献２】K．Karabina，“Torus−based Compression by Factor 4 ａｎd 6”，Cryptology ePrint Archive，Report 2010／525．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術では、圧縮装置および伸長装置を効率的に実現するために、代数的トーラスの基礎体の法多項式に制約が置かれていた。そのため、制約条件を満たさない法多項式を利用した場合、効率的に伸長できるとは限らなかった。
【課題を解決するための手段】
【０００７】
実施形態の伸長装置は、入力部、算出部、第１選択部、伸長部を備える。入力部は、有限体の乗法群の部分群の要素をトレース表現で表したトレース表現データに変換するときに得られる付加データと、トレース表現データとを入力する。算出部は、トレース表現データによって決定される連立方程式の複数の解を算出する。第１選択部は、付加データに基づいて、複数の解から求められるデータであって、部分群の要素をアフィン表現で表した複数のアフィン表現データのうちいずれかを選択する。伸長部は、選択されたアフィン表現データを要素に伸長する。
【図面の簡単な説明】
【０００８】
【図１】第１の実施形態の圧縮装置のブロック図。
【図２】第１の実施形態の圧縮処理のフローチャート。
【図３】第１の実施形態の伸長装置のブロック図。
【図４】第１の実施形態の伸長処理のフローチャート。
【図５】第２の実施形態の圧縮装置のブロック図。
【図６】第２の実施形態の伸長装置のブロック図。
【図７】第３の実施形態の圧縮装置のブロック図。
【図８】第３の実施形態の伸長装置のブロック図。
【図９】第４の実施形態の伸長装置のブロック図。
【図１０】各実施形態の伸長装置および圧縮装置のハードウェア構成図。
【発明を実施するための形態】
【０００９】
以下に添付図面を参照して、この発明にかかる伸長装置の好適な実施形態を詳細に説明する。
【００１０】
（第１の実施形態）
第１の実施形態にかかる圧縮装置および伸長装置は、従来技術とは異なる制約を法多項式に置くことで、効率的に圧縮装置および伸長装置を構成する。本実施形態では、代数的トーラスの有限体表現の元（要素）をトレース表現と付加ビットで表すことで表現を圧縮し、そのトレース表現より決定できる多変数連立方程式の解と付加ビットとから代数的トーラスの有限体表現の要素に伸長する。多変数連立方程式を解くと、伸長候補となる複数の代数的トーラスの有限体表現の要素が得られるため、付加ビットを用いて圧縮前の要素を決定する。
【００１１】
（１）代数的トーラスの構成
最初に、以下の各実施形態で用いる用語および表記等について説明する。Ｆｐｍは、要素数ｐ＾ｍの有限体を表し、Ｆｐのｍ次拡大体と呼ぶ。例えば、Ｆ３ｍは、要素数が３つの有限体Ｆ３のｍ次拡大体を表す。また、ａ０、ａ１、・・・、ａｎ∈Ｆｑであるとき、多項式Ｆ（ｘ）＝ａ０＋ａ１×ｘ＋・・・＋ａｎ×ｘ＾ｎは、Ｆｑ上の多項式と呼ぶ。Ｆｑ上の多項式であることを表すために、Ｆ（ｘ）＝ａ０＋ａ１×ｘ＋・・・＋ａｎ×ｘ＾ｎ ｏｖｅｒ Ｆｑのように表記することもある。なお、「ａ＾ｂ」は、ａのｂ乗を表す。以下では、ａのｂ乗をａｂと表す場合もある。
【００１２】
ｎをｎ≡５ （ｍｏｄ １２）なる奇数とし、ｑ＝３＾ｎとし、有限体Ｆｑを考える。このとき、ｑ≡５ （ｍｏｄ ７）となる。また、法多項式として、Φ７＝ｘ＾６＋ｘ＾５＋ｘ＾４＋ｘ＾３＋ｘ＾２＋ｘ＋１を用いて、有限体Ｆｑの６次拡大体Ｆｑ６を考える。なお、法多項式はこれに限られるものではなく、例えばΦ９＝ｘ＾６＋ｘ＾３＋１などの別の法多項式を用いても良い。
【００１３】
このとき、Ｆｑ６上では、ｘ＾ｑ＝ｘ＾５、ｘ＾｛ｑ＾２｝＝ｘ＾４、ｘ＾｛ｑ＾３｝＝ｘ＾６、ｘ＾｛ｑ＾４｝＝ｘ＾２、ｘ＾｛ｑ＾５｝＝ｘ＾３が成立する。このとき、６次拡大体Ｆｑ６上の代数的トーラスＴ６（Ｆｑ）は、位数ｑ−√（３ｑ）＋１の部分群を持つ。ｑは、３の奇数乗であるため、√（３ｑ）は整数になる。ここで、√（３ｑ）＝ｔとおく。
【００１４】
トレース写像Ｔｒ：Ｆｑ６→Ｆｑを以下の（１）式のように定義する。Ｔｒ（ｇ）をｇのトレース表現と呼ぶ。
Ｔｒ（ｇ）＝ｇ＋ｇ＾ｑ＋ｇ＾｛ｑ＾２｝＋ｇ＾｛ｑ＾３｝＋ｇ＾｛ｑ＾４｝＋ｇ＾｛ｑ＾５｝・・・（１）
【００１５】
また、アフィン変換写像Ａｆ：Ｆｑ６→Ｆｑ３とアフィン変換逆写像Ａｆ＾｛−１｝：Ｆｑ３→Ｆｑ６を以下の（２）式のように定義する。
Ａｆ（ｇ）＝（Ｇ１＋１）／Ｇ２、
Ａｆ＾｛−１｝（Ａｆ（ｇ））＝（Ａｆ（ｇ）＋ｚ）／（Ａｆ（ｇ）＋ｚ＾ｑ）・・・（２）
【００１６】
ここで、ｚ：＝ｘ＋ｘ＾｛ｑ＾２｝＋ｘ＾｛ｑ＾４｝＝ｘ＋ｘ＾２＋ｘ＾４、ｇ：＝ａ０＋ａ１×ｘ＋ａ２×ｘ＾２＋ａ３×ｘ＾３＋ａ４×ｘ＾４＋ａ５×ｘ＾５＝（ａ０＋ａ３×ｘ＾３＋ａ５×ｘ＾５）＋（ａ１×ｘ＋ａ２×ｘ＾２＋ａ４×ｘ＾４）＝Ｇ１＋Ｇ２×ｚ（ただし、Ｇ１、Ｇ２∈Ｆｑ３）とする。Ａｆ（ｇ）をｇのアフィン表現と呼ぶ。
【００１７】
（２）圧縮装置の構成
次に、第１の実施形態の圧縮装置および伸長装置の構成例について説明する。図１は、第１の実施形態にかかる圧縮装置１００の構成の一例を示すブロック図である。図１に示すように、圧縮装置１００は、入力部１０１と、第１変換部１０２と、第２変換部１０３と、付加ビット決定部１０４と、出力部１０５と、記憶部１２１と、を備えている。
【００１８】
入力部１０１は、圧縮する代数的トーラスの部分群の要素を入力する。第１変換部１０２は、入力された要素をトレース表現で表したトレース表現データに変換する。以下では、トレース表現データを単にトレース表現ともいう。第１変換部１０２は、上述のトレース写像Ｔｒより、入力された要素をトレース表現に変換する。
【００１９】
第２変換部１０３は、入力された要素をアフィン表現で表したアフィン表現データに変換する。以下では、アフィン表現データを単にアフィン表現ともいう。第２変換部１０３は、上述のアフィン変換写像Ａｆにより、入力された要素をアフィン表現に変換する。
【００２０】
付加ビット決定部１０４は、有限体の乗法群（有限体表現の代数的トーラス）の部分群の要素をトレース表現で表したトレース表現データと有限体の乗法群の部分群の要素をアフィン表現で表したアフィン表現データとに基づいて付加ビットを決定する。付加ビット決定部１０４は、トレース表現およびアフィン表現から、所定の連立方程式の解からアフィン表現を求めるための付加データ（以下、付加ビットという）を決定する。つまり、有限体の乗法群（有限体表現の代数的トーラス）の部分群の要素をトレース表現で表したトレース表現データを伸長して得られるアフィン表現の候補（複数）と、有限体の乗法群（有限体表現の代数的トーラス）の部分群の要素のアフィン表現で表したアフィン表現データとに基づいて付加ビットを決定する。
出力部１０５は、トレース表現と付加ビットとを出力する。記憶部１２１は、付加ビットの決定に用いる予め導出された式を求めるための情報を記憶する。
【００２１】
次に、このように構成された第１の実施形態にかかる圧縮装置１００による圧縮処理について図２を用いて説明する。図２は、第１の実施形態における圧縮処理の全体の流れを示すフローチャートである。
【００２２】
入力部１０１は、代数的トーラスの部分群の要素ｇを入力する（ステップＳ１０１）。第１変換部１０２は、トレース写像にｇを入力し、トレース表現Ｔｒ（ｇ）を計算する（ステップＳ１０２）。第２変換部１０３は、アフィン写像にｇを入力し、アフィン表現（α＋１、β＋１、γ＋１）∈Ｆｑ３を計算する（ステップＳ１０３）。付加ビット決定部１０４は、トレース表現と代数的トーラスの条件と有限体の条件とにより決定される多変数連立方程式を決定する（ステップＳ１０４）。付加ビット決定部１０４は、多変数連立方程式を解くことにより付加ビットを決定する（ステップＳ１０５）。具体的には、付加ビット決定部１０４は、多変数連立方程式を解いて６つの解｛（ａｉ、ｂｉ、ｃｉ）｝＿｛ｉ＝１、・・・、６｝を得て、６つの解を大きい順に並べ、ｇのアフィン表現と一致するｉ番目の要素を決定して、ｉを付加ビットとして決定する。出力部１０５は、トレース表現と付加ビットと（Ｔｒ（ｇ）、ｉ）を出力する（ステップＳ１０６）。なお、付加ビットの決め方は、６つの解を大きい順に並べて決定するだけでなく、例えば小さい順に並べて決定するなどのように、６つの解を区別できれば何でもよい。
【００２３】
本実施形態では、トレース写像Ｔｒ：Ｆｑ６→Ｆｑにより、圧縮率１／６の圧縮が実現できる。なお、１≦ｉ≦６なので、ｉは３ビットで表現できる。すなわち、付加ビットｉは圧縮率１／６にほとんど影響しない。
【００２４】
多変数連立方程式の決定方法（ステップＳ１０４）、および、多変数連立方程式の解法（ステップＳ１０５）は、伸長装置２００と同じ構成で実現できる。これらの各処理の詳細は、伸長装置２００の構成の説明時に詳述する。
【００２５】
（３）伸長装置の構成
図３は、第１の実施形態にかかる伸長装置２００の構成の一例を示すブロック図である。図３に示すように、伸長装置２００は、入力部２０１と、算出部２１０と、第１選択部２０２と、伸長部２０３と、出力部２０４と、記憶部２２１と、を備えている。
【００２６】
入力部２０１は、圧縮装置１００から出力されるトレース表現と付加ビットとを入力する。算出部２１０は、入力されたトレース表現から上述の多変数連立方程式を決定し、多変数連立方程式の解を算出する。算出部２１０は、第１式決定部２１１と、第１求解部２１２と、第２式決定部２１３と、第２求解部２１４と、第３式決定部２１５と、第３求解部２１６と、を備えている。
【００２７】
第１式決定部２１１は、有限体Ｆｑ上の予め求められたｋ１次式（ｋ１は予め定められる１以上の整数）の予め定められた係数に、入力されたトレース表現データを入力して得られる第１式を決定する。以下では、２次式（ｋ１＝２）である第１式を決定する例を説明する。第１求解部２１２は、第１式の解を求める。
【００２８】
第２式決定部２１３は、有限体Ｆｑ上の予め求められたｋ２次式（ｋ２は予め定められる１以上の整数）の予め定められた係数に、第１求解部２１２により求められた解の少なくとも１つを入力して得られる第２式を決定する。以下では、３次式（ｋ２＝３）である第２式を決定する例を説明する。第２求解部２１４は、第２式の解を求める。
【００２９】
第３式決定部２１５は、有限体Ｆｑ上の予め求められたｋ３次式（ｋ３は予め定められる１以上の整数）の予め定められた係数に、第１求解部２１２により求められた解および第２求解部２１４により求められた解のうち少なくとも１つを入力して得られる第３式を決定する。以下では、１次式（ｋ３＝１）である第３式を決定する例を説明する。第３求解部２１６は、第３式の解を求める。
【００３０】
第１選択部２０２は、算出部２１０により算出された複数の解から複数のアフィン表現を求め、求めたアフィン表現のうち、付加データに対応するいずれかのアフィン表現を選択する。伸長部２０３は、選択されたアフィン表現を、圧縮前の代数的トーラスの部分群の要素に伸長する。伸長部２０３は、上述のアフィン変換逆写像Ａｆ＾｛−１｝により、アフィン表現を圧縮前の要素に変換する。出力部２０４は、伸長された代数的トーラス部分群の要素を出力する。
【００３１】
記憶部２２１は、圧縮装置１００の記憶部１２１と同様に、付加ビットの決定に用いた予め導出された式を求めるための情報を記憶する。なお、記憶部１２１および記憶部２２１は、ＨＤＤ（Hard Disk Drivｅ）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００３２】
次に、このように構成された第１の実施形態にかかる伸長装置２００による伸長処理について図４を用いて説明する。図４は、第１の実施形態における伸長処理の全体の流れを示すフローチャートである。
【００３３】
入力部２０１は、トレース表現Ｔ∈Ｆｑと付加ビットｊ∈Ｆ２＾３とを入力する（ステップＳ２０１）。算出部２１０は、入力されたトレース表現から多変数連立方程式を決定し、多変数連立方程式の解を算出する（ステップＳ２０２）。算出部２１０による算出処理の詳細は後述する。
【００３４】
第１選択部２０２は、算出された解と、入力された付加ビットとから、アフィン表現を選択（決定）する（ステップＳ２０３）。伸長部２０３は、アフィン表現を代数的トーラスの部分群の要素ｇに伸長する（ステップＳ２０４）。出力部２０４は、伸長により得られた代数的トーラスの部分群の要素ｇを出力する（ステップＳ２０５）。
【００３５】
次に、ステップＳ２０２の算出部２１０による算出処理の詳細について説明する。
【００３６】
まず、第１式決定部２１１は、以下の（３）式で表される２次式Ａ（ｘ）を決定する（ステップＳ２０２）。
Ａ（ｘ）：ｘ＾２＋（Ｔ＾｛ｔ−２｝＋１）＾｛−１｝＝０ ｏｖｅｒ Ｆｑ・・・（３）
【００３７】
第１式決定部２１１は、例えば、上記Ａ（ｘ）を求めるための情報を記憶部２２１から読み出す。この情報は、例えば係数と変数の関係、トレース表現を入力する係数として予め定められた係数を特定する情報を含む。第１式決定部２１１は、このような情報を参照して、所定の係数に入力されたトレース表現を入力してＡ（ｘ）を決定する。第１式決定部２１１は、決定したＡ（ｘ）を第１求解部２１２に送る。
【００３８】
なお、所望のアフィン表現を（α＋１、β＋１、γ＋１）とすると、この２次式Ａ（ｘ）は、α＋β＋γを根に持つ。このような２次式Ａ（ｘ）を導出する手順については後述する。
【００３９】
第１求解部２１２は、Ａ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いてＦｑ上でＡ（ｘ）を因数分解し、Ａ（ｘ）＝０の解ａ１、ａ２を求める。第１求解部２１２は、求めた解ａ１、ａ２を第２式決定部２１３と第３式決定部２１５とに送る。
【００４０】
第２式決定部２１３は、解ａ１、ａ２が入力されると、以下の（４）式および（５）式で表される３次式Ｂ（ｘ）およびＣ（ｘ）を決定する。
Ｂ（ｘ）：ｘ＾３−ａ１×ｘ＾２−（ａ１＾２−１）ｘ−Ｚ（ａ１）＝０ ｏｖｅｒ Ｆｑ・・・（４）
Ｃ（ｘ）：ｘ＾３−ａ２×ｘ＾２−（ａ２＾２−１）ｘ−Ｚ（ａ２）＝０ ｏｖｅｒ Ｆｑ・・・（５）
【００４１】
ただし、Ｚ（ｘ）＝ｘ＾３−Ｙ（ｘ）＋（ｘ×Ｙ（ｘ）−Ｙ（ｘ）＾２−１）／ｘ＾３ ｏｖｅｒ Ｆｑ、Ｙ（ｘ）＝（−１−ｘ＾２）／ｘ＾ｔ−ｘ ｏｖｅｒ Ｆｑである。第２式決定部２１３は、Ｂ（ｘ）およびＣ（ｘ）を第２求解部２１４に送る。
【００４２】
所望のアフィン表現を（α＋１、β＋１、γ＋１）とすると、これらの３次式の一方は、βを根に持つ。このような３次式Ｂ（ｘ）およびＣ（ｘ）を導出する手順については後述する。
【００４３】
第２求解部２１４は、Ｂ（ｘ）およびＣ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＢ（ｘ）およびＣ（ｘ）を因数分解し、Ｂ（ｘ）＝０の解ｂ１、ｂ２、ｂ３と、Ｃ（ｘ）＝０の解ｃ１、ｃ２、ｃ３を求める。第２求解部２１４は、解（ｂ１、ｂ２、ｂ３）と（ｃ１、ｃ２、ｃ３）を第３式決定部２１５に送る。
【００４４】
第３式決定部２１５は、（ａ１、ａ２）と（ｂ１、ｂ２、ｂ３）と（ｃ１、ｃ２、ｃ３）とを入力されると、以下の（６）式〜（１１）式で表される１次式Ｄ（ｘ）、Ｅ（ｘ）、Ｆ（ｘ）、Ｇ（ｘ）、Ｈ（ｘ）およびＩ（ｘ）を決定する。
Ｄ（ｘ）：（−ｂ１＾｛２｝＋（ａ１＋（１／ａ１））×ｂ１）×ｘ＋Ｚ（ａ１）＋（−ａ１＋（１／ａ１））×ｂ１＾２−（Ｙ（ａ１）／ａ１）×ｂ１＝０ ｏｖｅｒ Ｆｑ・・・（６）
Ｅ（ｘ）：（−ｂ２＾｛２｝＋（ａ１＋（１／ａ１））×ｂ２）×ｘ＋Ｚ（ａ１）＋（−ａ１＋（１／ａ１））×ｂ２＾２−（Ｙ（ａ１）／ａ１）×ｂ２＝０ ｏｖｅｒ Ｆｑ・・・（７）
Ｆ（ｘ）：（−ｂ３＾｛２｝＋（ａ１＋（１／ａ１））×ｂ３）×ｘ＋Ｚ（ａ１）＋（−ａ１＋（１／ａ１））×ｂ３＾２−（Ｙ（ａ１）／ａ１）×ｂ３＝０ ｏｖｅｒ Ｆｑ・・・（８）
Ｇ（ｘ）：（−ｃ１＾｛２｝＋（ａ２＋（１／ａ２））×ｃ１）×ｘ＋Ｚ（ａ２）＋（−ａ２＋（１／ａ２））×ｃ１＾２−（Ｙ（ａ２）／ａ２）×ｃ１＝０ ｏｖｅｒ Ｆｑ・・・（９）
Ｈ（ｘ）：（−ｃ２＾｛２｝＋（ａ２＋（１／ａ２））×ｃ２）×ｘ＋Ｚ（ａ２）＋（−ａ２＋（１／ａ２））×ｃ２＾２−（Ｙ（ａ２）／ａ２）×ｃ２＝０ ｏｖｅｒ Ｆｑ・・・（１０）
Ｉ（ｘ）：（−ｃ３＾｛２｝＋（ａ２＋（１／ａ２））×ｃ３）×ｘ＋Ｚ（ａ２）＋（−ａ２＋（１／ａ２））×ｃ３＾２−（Ｙ（ａ２）／ａ２）×ｃ３＝０ ｏｖｅｒ Ｆｑ・・・（１１）
【００４５】
第３式決定部２１５は、Ｄ（ｘ）、Ｅ（ｘ）、Ｆ（ｘ）、Ｇ（ｘ）、Ｈ（ｘ）およびＩ（ｘ）を第３求解部２１６へ送る。
【００４６】
なお、所望のアフィン表現を（α＋１、β＋１、γ＋１）とすると、これらの１次式の１つは、γを根に持つ。このような１次式Ｄ（ｘ）、Ｅ（ｘ）、Ｆ（ｘ）、Ｇ（ｘ）、Ｈ（ｘ）およびＩ（ｘ）を導出する手順については後述する。
【００４７】
第３求解部２１６は、Ｄ（ｘ）＝０、Ｅ（ｘ）＝０、Ｆ（ｘ）＝０、Ｇ（ｘ）＝０、Ｈ（ｘ）＝０、およびＩ（ｘ）＝０が入力されると、それらの解ｄ、ｅ、ｆ、ｇ、ｈ、ｉを求める。また、第３求解部２１６は、これらの解および上記３次式Ｂ（ｘ）およびＣ（ｘ）の解であるｂ１、ｂ２、ｂ３、ｃ１、ｃ２、ｃ３から、６個の解の組（ａ１−ｂ１−ｄ、ｂ１、ｄ）、（ａ１−ｂ２−ｅ、ｂ２、ｅ）、（ａ１−ｂ３−ｆ、ｂ３、ｆ）、（ａ２−ｃ１−ｇ、ｃ１、ｇ）、（ａ２−ｃ２−ｈ、ｃ２、ｈ）、（ａ２−ｃ３−ｉ、ｃ３、ｉ）を第１選択部２０２に送る。
【００４８】
第１選択部２０２は、６個の解の組と付加ビットｊ（１≦ｊ≦６）とを受け取ったら、６個の解それぞれの各要素に１を加えた（ａ１−ｂ１−ｄ＋１、ｂ１＋１、ｄ＋１）、（ａ１−ｂ２−ｅ＋１、ｂ２＋１、ｅ＋１）、（ａ１−ｂ３−ｆ＋１、ｂ３＋１、ｆ＋１）、（ａ２−ｃ１−ｇ＋１、ｃ１＋１、ｇ＋１）、（ａ２−ｃ２−ｈ＋１、ｃ２＋１、ｈ＋１）、（ａ２−ｃ３−ｉ＋１、ｃ３＋１、ｉ＋１）を算出する。そして、第１選択部２０２は、算出した６個の解を所定の基準に従い整列する。以下では大きい順に整列するものとするが、基準はこれに限られるものではない。
【００４９】
第１選択部２０２は、整列した６個の解のうちｊ番目に大きい値を選択する。この値が、所望のアフィン表現に相当する。第１選択部２０２は、選択した値（アフィン表現）を伸長部２０３に送る。
【００５０】
伸長部２０３は、受け取ったアフィン表現をアフィン変換逆写像Ａｆ＾｛−１｝により代数的トーラス部分群の有限体表現に変換し出力する。
【００５１】
このように、第１の実施形態にかかる圧縮装置および伸長装置では、従来の方法では効率的に伸長写像が構成できない法多項式に対して、効率的に圧縮装置および伸長装置を実現することができる。また、本実施形態の圧縮装置および伸長装置では、代数的トーラスの部分群上のある要素ｇとフロベニウス写像を計算した要素ｇ’について、それらのトレース表現Ｔｒ（ｇ）とＴｒ（ｇ’）は等しいという性質を利用し、トレース表現Ｔｒ（ｇ）を伸長することなく、付加ビットを操作することでＴｒ（ｇ’）を計算することができる。
【００５２】
（第２の実施形態）
第２の実施形態にかかる伸長装置は、付加ビットの一部を用いて、解かなければならない式を絞り込む。これにより、より効率的に圧縮および伸長を実行可能となる。なお、代数的トーラスの構成は第１の実施形態と同様であるため説明を省略する。
【００５３】
（１）圧縮装置の構成
図５は、第２の実施形態にかかる圧縮装置１００−２の構成の一例を示すブロック図である。図５に示すように、圧縮装置１００−２は、入力部１０１と、第１変換部１０２と、第２変換部１０３と、付加ビット決定部１０４−２と、出力部１０５と、記憶部１２１と、を備えている。
【００５４】
第２の実施形態では、付加ビット決定部１０４−２の機能が第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる圧縮装置１００のブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【００５５】
以下、第２の実施形態の付加ビット決定部１０４−２による付加ビットの決定処理について説明する。
【００５６】
第１変換部１０２および第２変換部１０３によりトレース表現Ｔｒ（ｇ）およびアフィン表現（α＋１、β＋１、γ＋１）が計算されると（図２のステップＳ１０２、ステップＳ１０３）、付加ビット決定部１０４−２は、トレース表現と代数的トーラスの条件と有限体の条件とにより決定される２次式を解いて解ａ１、ａ２を求める。付加ビット決定部１０４−２は、求めた解ａ１、ａ２を大きい順に並べ替え、ｇのアフィン表現の各要素の和α＋β＋γ＋３ ｏｖｅｒ Ｆｑと一致するｉ１（ｉ１＝１または２）を付加ビット１として決定する。
【００５７】
つぎに、付加ビット決定部１０４−２は、トレース表現とアフィン表現の各要素の和とトーラスの条件と有限体の条件とから３次式を決定する。付加ビット決定部１０４−２は、３次式の解から１次式を決定し、３つのアフィン表現の候補を求める。付加ビット決定部１０４−２は、求めた候補を大きい順に整列して、ｇのアフィン表現と比較し、ｉ２（１≦ｉ２≦３）番目の要素と一致するとき、ｉ２を付加ビット２として決定する。なお、出力部１０５は、付加ビットｉ１およびｉ２をトレース表現とともに出力する。
【００５８】
なお、２次式と３次式と１次式の決定法と、求解法は、以下に述べる伸長装置２００−２と同じ構成で実現できる。
【００５９】
（２）伸長装置の構成
図６は、第２の実施形態にかかる伸長装置２００−２の構成の一例を示すブロック図である。図６に示すように、伸長装置２００−２は、入力部２０１と、算出部２１０−２と、第１選択部２０２−２と、伸長部２０３と、出力部２０４と、記憶部２２１と、を備えている。
【００６０】
第２の実施形態では、算出部２１０−２および第１選択部２０２−２の機能が第１の実施形態と異なっている。その他の構成および機能は、第１の実施形態にかかる伸長装置２００のブロック図である図３と同様であるので、同一符号を付し、ここでの説明は省略する。
【００６１】
算出部２１０−２は、第２選択部２１７をさらに備えている。なお、第１式決定部２１１および第１求解部２１２の機能は第１の実施形態と同様であるため同一の符号を付し説明を省略する。
【００６２】
第２選択部２１７は、入力された付加ビットのうち付加ビット１（ｉ１）を用いて、第１求解部２１２により得られた解を大きい順に並べたときのｉ１番目の解を選択する。
【００６３】
第２式決定部２１３−２は、第２選択部２１７により選択された解を用いて第２式を決定する。第２求解部２１４−２は、第２式の解を求める。第３式決定部２１５−２は、第２選択部２１７により選択された解および第２求解部２１４−２により求められた解のうち少なくとも１つを入力して得られる第３式を決定する。第３求解部２１６−２は、第３式の解を求める。
【００６４】
第１選択部２０２−２は、付加データのうち付加データｉ２を用いて解を選択する点が、第１の実施形態の第１選択部２０２と異なる。
【００６５】
次に、第２の実施形態の算出部２１０−２による算出処理の詳細について説明する。
【００６６】
入力部２０１は、トレース表現Ｔ∈Ｆｑと付加ビット（ｉ１、ｉ２）∈Ｆ２×Ｆ２＾２とを入力すると、トレース表現Ｔを第１式決定部２１１に送る。第１式決定部２１１は、上述の処理により２次式Ａ（ｘ）を決定して第１求解部２１２に送る。第１求解部２１２は、Ｆｑ上でＡ（ｘ）を因数分解し、Ａ（ｘ）＝０の解ａ１、ａ２を求め、解ａ１、ａ２を第２選択部２１７に送る。
【００６７】
第２選択部２１７は、解ａ１、ａ２と付加ビット１（ｉ１）とが入力されると、解ａ１、ａ２を大きい順に整列して、ｉ１番目の要素を選択してａとし、第２式決定部２１３−２と第３式決定部２１５−２に送る。
【００６８】
第２式決定部２１３−２は、解ａが入力されると以下の（１２）式で表される３次式Ｂ（ｘ）を決定する。なお、Ｚ（ｘ）およびＹ（ｘ）は上述のとおりである。
Ｂ（ｘ）：ｘ＾３−ａ×ｘ＾２−（ａ＾２−１）ｘ−Ｚ（ａ）＝０ ｏｖｅｒ Ｆｑ・・・（１２）
【００６９】
第２式決定部２１３−２は、Ｂ（ｘ）を第２求解部２１４−２に送る。第２求解部２１４−２は、Ｂ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＢ（ｘ）を因数分解し、Ｂ（ｘ）＝０の解ｂ１、ｂ２、ｂ３を求める。第２求解部２１４−２は、解（ｂ１、ｂ２、ｂ３）を第３式決定部２１５−２に送る。
【００７０】
第３式決定部２１５−２は、（ａ）と（ｂ１、ｂ２、ｂ３）とを入力されると、以下の（１３）式〜（１５）式で表される１次式Ｄ（ｘ）、Ｅ（ｘ）、およびＦ（ｘ）を決定する。
Ｄ（ｘ）：（−ｂ１＾｛２｝＋（ａ＋（１／ａ））×ｂ１）×ｘ＋Ｚ（ａ）＋（−ａ＋（１／ａ））×ｂ１＾２−（Ｙ（ａ）／ａ）×ｂ１＝０ ｏｖｅｒ Ｆｑ・・・（１３）
Ｅ（ｘ）：（−ｂ２＾｛２｝＋（ａ＋（１／ａ））×ｂ２）×ｘ＋Ｚ（ａ）＋（−ａ＋（１／ａ））×ｂ２＾２−（Ｙ（ａ）／ａ）×ｂ２＝０ ｏｖｅｒ Ｆｑ・・・（１４）
Ｆ（ｘ）：（−ｂ３＾｛２｝＋（ａ＋（１／ａ））×ｂ３）×ｘ＋Ｚ（ａ）＋（−ａ＋（１／ａ））×ｂ３＾２−（Ｙ（ａ）／ａ）×ｂ３＝０ ｏｖｅｒ Ｆｑ・・・（１５）
【００７１】
第３式決定部２１５−２は、１次式Ｄ（ｘ）、Ｅ（ｘ）、およびＦ（ｘ）を第３求解部２１６−２へ送る。
【００７２】
第３求解部２１６−２は、Ｄ（ｘ）＝０、Ｅ（ｘ）＝０、およびＦ（ｘ）＝０が入力されると、それらの解ｄ、ｅ、ｆを求める。第３求解部２１６−２は、３個の解の組（ａ−ｂ１−ｄ、ｂ１、ｄ）、（ａ−ｂ２−ｅ、ｂ２、ｅ）、（ａ−ｂ３−ｆ、ｂ３、ｆ）を第１選択部２０２−２に送る。
【００７３】
第１選択部２０２−２は、３個の解と付加ビットｉ２（１≦ｉ２≦３）とを受け取ると、３個の解それぞれの各要素に１を加えた（ａ−ｂ１−ｄ＋１、ｂ１＋１、ｄ＋１）、（ａ−ｂ２−ｅ＋１、ｂ２＋１、ｅ＋１）、（ａ−ｂ３−ｆ＋１、ｂ３＋１、ｆ＋１）を算出する。そして、第１選択部２０２−２は、算出した３個の解を大きい順に整列する。第１選択部２０２−２は、整列した３個の解のうちｉ２番目に大きい値を選択する。この値が、所望のアフィン表現に相当する。第１選択部２０２−２は、選択した値（アフィン表現）を伸長部２０３に送る。伸長部２０３は、受け取ったアフィン表現を代数的トーラス部分群の有限体表現に変換し出力する。
【００７４】
このように、第２の実施形態にかかる圧縮装置および伸長装置では、付加ビットをｉ１およびｉ２に分けて算出し、付加ビットｉ１を用いて早い段階で解かなければならない式を絞り込むことができる。これにより、より効率的に圧縮および伸長を実行可能となる。
【００７５】
（第３の実施形態）
第３の実施形態では、第１の実施形態と同様の方法を、圧縮率１／４の圧縮に適用する例について説明する。
【００７６】
（１）代数的トーラスの構成
ｑ≡２ （ｍｏｄ ５）かつｑ＝２＾ｎかつｐ|（√（２ｑ））なる有限体Ｆｑを考える。また、法多項式としてΦ５＝ｘ＾４＋ｘ＾３＋ｘ＾２＋ｘ＋１を用いて、有限体Ｆｑの４次拡大体Ｆｑ４を考える。このとき、Ｆｑ４上では、ｘ＾ｑ＝ｘ＾２、ｘ＾｛ｑ＾２｝＝ｘ＾４、ｘ＾｛ｑ＾３｝＝ｘ＾３、ｘ＾｛ｑ＾４｝＝ｘが成立する。
【００７７】
このとき、４次拡大体Ｆｑ４上の代数的トーラスＴ４（Ｆｑ）は、位数ｑ−√（２ｑ）＋１の部分群を持つ。なお、ｑ≡２ （ｍｏｄ ５）より、ｎは奇数であるから、√（２ｑ）は整数になる。ここで、√（２ｑ）＝ｔとおく。
【００７８】
トレース写像Ｔｒ：Ｆｑ４→Ｆｑを以下の（１６）式のように定義する。
Ｔｒ（ｇ）＝ｇ＋ｇ＾ｑ＋ｇ＾｛ｑ＾２｝＋ｇ＾｛ｑ＾３｝・・・（１６）
【００７９】
また、アフィン変換写像Ａｆ：Ｆｑ４→Ｆｑ２とアフィン変換逆写像Ａｆ＾｛−１｝：Ｆｑ２→Ｆｑ４を以下の（１７）式のように定義する。
Ａｆ（ｇ）＝（Ｇ１＋１）／Ｇ２∈Ｆｑ２、
Ａｆ＾｛−１｝（Ａｆ（ｇ））＝（Ａｆ（ｇ）＋ｚ）／（Ａｆ（ｇ）＋ｚ＾ｑ）∈Ｆｑ４・・・（１７）
【００８０】
ここで、ｚ：＝ｘ＋ｘ＾ｑ＝ｘ＋ｘ＾２、ｇ：＝ａ０＋ａ１×ｘ＋ａ２×ｘ＾２＋ａ３×ｘ＾３＝（ａ０＋ａ３×ｘ＾３）＋（ａ１×ｘ＋ａ２×ｘ＾２）＝Ｇ１＋Ｇ２×ｚ（ただし、Ｇ１、Ｇ２∈Ｆｑ２）とする。
【００８１】
（２）圧縮装置の構成
図７は、第３の実施形態にかかる圧縮装置１００−３の構成の一例を示すブロック図である。図７に示すように、圧縮装置１００−３は、入力部１０１と、第１変換部１０２−３と、第２変換部１０３−３と、付加ビット決定部１０４−３と、出力部１０５と、記憶部１２１と、を備えている。第１の実施形態と同様の機能を備える構成部は図１と同一の符号を付し、説明を省略する。
【００８２】
第１変換部１０２−３は、（１６）式のトレース写像Ｔｒより、入力された要素ｇをトレース表現Ｔｒ（ｇ）に変換する。第２変換部１０３−３は、（１７）式のアフィン変換写像Ａｆにより、入力された要素ｇをアフィン表現（α、β）∈Ｆｑ×Ｆｑに変換する。付加ビット決定部１０４−３は、αの最下位ビットを付加ビット１として決定し、βの最下位ビットを付加ビット２として決定する。
【００８３】
（３）伸長装置の構成
図８は、第３の実施形態にかかる伸長装置２００−３の構成の一例を示すブロック図である。図８に示すように、伸長装置２００−３は、入力部２０１と、算出部２１０−３と、第１選択部２０２−３と、伸長部２０３−３と、出力部２０４と、記憶部２２１と、を備えている。第１の実施形態と同様の機能を備える構成部は図３と同一の符号を付し、説明を省略する。
【００８４】
算出部２１０−３は、第１式決定部２１１−３と、第１求解部２１２−３と、第２式決定部２１３−３と、第２求解部２１４−３と、を備えている。
【００８５】
第１式決定部２１１−３は、第１の実施形態と異なる２次式である第１式を決定する。第１求解部２１２−３は、第１式の解を求める。第２式決定部２１３−３は、第１の実施形態と異なり、２次式である第２式を決定する。第２求解部２１４−３は、第２式の解を求める。第１選択部２０２−３は、算出部２１０−３により算出された複数の解から、付加データに対応するいずれかの解を選択する。
【００８６】
次に、第３の実施形態の算出部２１０−３による算出処理の詳細について説明する。
【００８７】
トレース表現Ｔ∈Ｆｑと付加ビット（ｉ１、ｉ２）∈Ｆ２×Ｆ２とが入力されると、第１式決定部２１１−３は、以下の（１８）式で表される２次式Ａ（ｘ）を決定して第１求解部２１２−３に送る。
Ａ（ｘ）：ｘ＾２＋ｘ＋１−Ｔ＾｛ｑ−ｔ｝＝０ ｏｖｅｒ Ｆｑ・・・（１８）
【００８８】
第１求解部２１２−３は、Ａ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＡ（ｘ）を因数分解し、Ａ（ｘ）＝０の解ａ１、ａ２を得て、解ａ１、ａ２を第２式決定部２１３−３に送る。なお、第１求解部２１２−３は、フロベニウス写像を用いて、ｘ＾２の項を１次の項に変換し、変換した１次式を解いても良い。
【００８９】
第２式決定部２１３−３は、解ａ１、ａ２が入力されると、以下の（１９）式および（２０）式で表される２次式Ｂ（ｘ）およびＣ（ｘ）を決定し、第２求解部２１４−３に送る。
Ｂ（ｘ）：ｘ＾２＋ｘ＋ａ１＾２＋ａ１＾ｔ×Ｔ＾｛ｑ−ｔ｝＝０ ｏｖｅｒ Ｆｑ・・・（１９）
Ｃ（ｘ）：ｘ＾２＋ｘ＋ａ２＾２＋ａ２＾ｔ×Ｔ＾｛ｑ−ｔ｝＝０ ｏｖｅｒ Ｆｑ・・・（２０）
【００９０】
第２求解部２１４−３は、Ｂ（ｘ）、Ｃ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＢ（ｘ）およびＣ（ｘ）をそれぞれ因数分解し、Ｂ（ｘ）＝０の解ｂ１、ｂ２とＣ（ｘ）＝０の解ｃ１、ｃ２とを求める。第２求解部２１４−３は、解ｂ１、ｂ２、ｃ１、ｃ２を第１選択部２０２−３に送る。
【００９１】
第１選択部２０２−３は、解ｂ１、ｂ２、ｃ１、ｃ２と付加ビット１と付加ビット２とを受け取ると、４個の解の組（ａ１−ｂ１、ｂ１）、（ａ１−ｂ２、ｂ２）、（ａ２−ｃ１、ｃ１）、（ａ２−ｃ２、ｃ２）を求める。第１選択部２０２−３は、各組の１成分目（ａ１−ｂ１、ａ１−ｂ２、ａ２−ｃ１、ａ２−ｃ２）の最下位ビットと付加ビット１とを比較し、各組の２成分目（ｂ１、ｂ２、ｃ１、ｃ２）の最下位ビットと付加ビット２とを比較し、両方が一致した組を選択する。この組の値が、所望のアフィン表現に相当する。第１選択部２０２−３は、選択した値（アフィン表現）を伸長部２０３−３に送る。伸長部２０３−３は、受け取ったアフィン表現を代数的トーラス部分群の有限体表現に変換し出力する。
【００９２】
このように、第３の実施形態では、第１の実施形態と同様の手法で圧縮率１／４の圧縮および伸長を実現できる。
【００９３】
（第４の実施形態）
第４の実施形態では、第２の実施形態と同様の方法を、圧縮率１／４の圧縮に適用する例について説明する。なお、代数的トーラスの構成は第３の実施形態と同様であるため説明を省略する。また、第４の実施形態の圧縮装置は第３の実施形態の圧縮装置１００−３と同様である。
【００９４】
（１）伸長装置の構成
図９は、第４の実施形態にかかる伸長装置２００−４の構成の一例を示すブロック図である。図９に示すように、伸長装置２００−４は、入力部２０１と、算出部２１０−４と、第１選択部２０２−４と、伸長部２０３−３と、出力部２０４と、記憶部２２１と、を備えている。第３の実施形態と同様の機能を備える構成部は図８と同一の符号を付し、説明を省略する。
【００９５】
算出部２１０−４は、第１式決定部２１１−３と、第１求解部２１２−３と、第２選択部２１７−４と、第２式決定部２１３−４と、第２求解部２１４−４と、を備えている。
【００９６】
第２選択部２１７−４は、入力された付加ビットのうち付加ビット１（ｉ１）と付加ビット２（ｉ２）を用いて、第１求解部２１２−３により得られた解の最下位ビットと付加ビット１（ｉ１）と付加ビット２（ｉ２）のＦ２上の和を比較し、一致する解を選択する。第２式決定部２１３−４は、第２選択部２１７−４により選択された解を用いて第２式を決定する。第２求解部２１４−４は、第２式の解を求める。
【００９７】
次に、第４の実施形態の算出部２１０−４による算出処理の詳細について説明する。
【００９８】
トレース表現Ｔ∈Ｆｑと付加ビット（ｉ１、ｉ２）∈Ｆ２×Ｆ２とが入力されると、第１式決定部２１１−３は、上記（１８）式で表される２次式Ａ（ｘ）を決定して第１求解部２１２−３に送る。
【００９９】
第１求解部２１２−３は、Ａ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＡ（ｘ）を因数分解し、Ａ（ｘ）＝０の解ａ１、ａ２を求める。第１求解部２１２−３は、解ａ１、ａ２を第２選択部２１７−４に送る。なお、フロベニウス写像を用いて、ｘ＾２の項を１次の項に変換し、変換した１次式を解いても良い。
【０１００】
第２選択部２１７−４は、解ａ１、ａ２と付加ビット１（ｉ１）と付加ビット２（ｉ２）とが入力されると、付加ビット１（ｉ１）と付加ビット２（ｉ２）のＦ２での和と、解ａ１、ａ２の最下位ビットとを比較し、一致した解を選択して解ａとする。第２選択部２１７−４は、選択した解ａを第２式決定部２１３−４に送る。
【０１０１】
第２式決定部２１３−４は、解ａが入力されると、以下の（２１）式で表される２次式Ｂ（ｘ）を決定して、第２求解部２１４−４に送る。
Ｂ（ｘ）：ｘ＾２＋ｘ＋ａ＾２＋ａ＾ｔ×Ｔ＾｛ｑ−ｔ｝＝０ ｏｖｅｒ Ｆｑ・・・（２１）
【０１０２】
第２求解部２１４−４は、Ｂ（ｘ）が入力されると、Ｂｅｒｌｅｋａｍｐアルゴリズムなどを用いて、Ｆｑ上でＢ（ｘ）を因数分解し、Ｂ（ｘ）＝０の解ｂ１、ｂ２を求める。第２求解部２１４−４は、解ｂ１、ｂ２を第１選択部２０２−４に送る。
【０１０３】
第１選択部２０２−４は、解ｂ１、ｂ２と付加ビット２（ｉ２）とを受け取ったら、付加ビット２（ｉ２）と解ｂ１、ｂ２の最下位ビットとを比較し、一致した解を選択して解ｂとする。また、第１選択部２０２−４は、解ａ、ｂから得られる（ａ−ｂ、ｂ）∈Ｆｑ×Ｆｑを伸長部２０３−３に送る。（ａ−ｂ、ｂ）が、所望のアフィン表現に相当する。
【０１０４】
なお、第１選択部２０２−４が、２つの解の組（ａ−ｂ１、ｂ１）と（ａ−ｂ２、ｂ２）とを求め、２成分目が付加ビット２（ｉ２）と一致する解の組（＝所望のアフィン表現）を選択するように構成してもよい。
【０１０５】
伸長部２０３−３は、受け取ったアフィン表現を代数的トーラス部分群の有限体表現に変換し出力する。
【０１０６】
このように、第４の実施形態では、第２の実施形態と同様の手法で圧縮率１／４の圧縮および伸長を実現できる。
【０１０７】
なお、上記各実施形態の圧縮装置および伸長装置は、例えば公開鍵暗号などの暗号化および復号を行う装置内に備えるように構成できる。例えば、公開鍵暗号による暗号化データを送信する情報処理装置（暗号化装置）内に圧縮装置を備え、暗号化データを受信して復号する情報処理装置（復号装置）内に伸長装置を備えるように構成できる。また、上記各実施形態の圧縮装置および伸長装置を共に備える圧縮伸長装置として構成してもよい。
【０１０８】
次に、上記各実施形態で用いた１次式〜３次式を導出する手順について説明する。最初に、圧縮率１／６の場合（第１および第２の実施形態）で用いる式の導出手順について説明する。
【０１０９】
（１）１／６圧縮
トーラスとしてＴ６（Ｆｑ）を考え、そのトーラスの部分群でトレース表現を取ることで、表現の圧縮を行う。Ｔ６（Ｆｑ）の位数は、円分多項式Φ６＝ｑ２−ｑ＋１である。円分多項式Φ６は、Φ６＝ｑ２−ｑ＋１＝（ｑ＋√（３ｑ）＋１）（ｑ−√（３ｑ）＋１）と因数分解できるので、（ｑ＋√（３ｑ）＋１）と（ｑ−√（３ｑ）＋１）が整数であれば、Ｔ６（Ｆｑ）を位数（ｑ＋√（３ｑ）＋１）の部分群と位数（ｑ−√（３ｑ）＋１）の部分群とに分割できる。すなわち、ｑを３の奇数乗に取ると、矛盾なく上記の因数分解により部分群が構成できる。
【０１１０】
ここで位数が（ｑ＋√（３ｑ）＋１）となる部分群をＧ＋、（ｑ−√（３ｑ）＋１）となる部分群をＧ−とする。Ｔ６（Ｆｑ）の部分群の元からトレース表現の元への写像は全単射ではないので、トレース表現の、ある元の逆像には複数のＴ６（Ｆｑ）の元が存在する。１つのトレース表現に対応するＴ６（Ｆｑ）の元は6つ存在するので、これらを識別するには少なくとも３ビットの付加ビットが必要となる。この３ビットの付加ビットを含めると、表現として必要なビット長はＧ＋，Ｇ−ともにｌｏｇ＿２（ｑ）＋３ビットとなるため、ｑよりも小さな群であるＧ−を必ずしも取る必要はないが、ここではＧ−を部分群として取ることとする。
【０１１１】
以下に、トレース表現とアフィン表現との関係を明らかにし、トレース表現からアフィン表現への伸張を可能とする手法を説明する。以降の演算は、特に断りが無い限り、Ｆ（３^ｎ）^６上の演算である。
【０１１２】
（２）準備
（２．１）拡大体に関する条件
有限体Ｆｑを法多項式Φ７で６次拡大した拡大体Ｆｑ６を考え、Ｔ６（Ｆｑ）の部分群Ｇ−の元に対する圧縮・伸長写像を構成する。代数的トーラスと法多項式Φ７とｑに対する条件は、以下の（２２）式で表される。
【数１】
【０１１３】
このとき、ｑ＝５ ｍｏｄ 7であるから、法多項式Φ７は、以下の（２３）式で表される。
【数２】
【０１１４】
次に、法多項式Φ７から構成されるＦｑ６に対して、その基礎体Ｆｑ２，Ｆｑ３を考え、Ｆｑ２の基底ｙとＦｑ３の基底ｚを、以下の（２４）式のように決める。
【数３】
【０１１５】
また、このとき法多項式Φ７とｑの条件から、yとｚに対して、以下の（２５）式および（２６）式の関係式が得られる。
【数４】
【０１１６】
なお、ｎは奇数でなければならないが、ｎ＝５ ｍｏｄ １２という条件は必ずしも必要ではないと考えられる。ここでは計算の簡略化のため、ｙｔ＝ｙ，ｚｔ＝ｚｑという形を作るためにこのような条件を置いた。
【０１１７】
ｆ∈Ｆｑ３は、Ｆｑ２の基底ｙとδ１，δ２，δ３∈Ｆｑを用いて、以下の（２７）式のように表現できる。また、ｆｔは以下の（２８）式のように表される。
【数５】
【０１１８】
（２．２）トレース写像とアフィン写像
Ｆｑ６のトレース写像Ｔｒ：Ｆｑ６→Ｆｑは、以下の（２９）式のように定義できる。
【数６】
【０１１９】
また、ｇ＝σ０＋σ１ｚ∈Ｔ６（Ｆｑ）に対して、アフィン写像ψ：Ｔ６（Ｆｑ）＼｛１｝→Ｆｑ３を、以下の（３０）式のように定義する。ここで、１はＦｑ６の乗法の単位元である。
【数７】
【０１２０】
さらに、アフィン逆写像ψ−１：Ｆｑ３→Ｔ６（Ｆｑ）＼｛１｝を、以下の（３１）式のように定義する。
【数８】
【０１２１】
このとき、以下の（３２）式が成り立つことが知られている。
【数９】
【０１２２】
（２９）式は、上述の（１）式のトレース写像Ｔｒに対応する。（３０）式および（３１）式は、上述の（２）式のアフィン変換写像Ａｆおよびアフィン変換逆写像Ａｆ＾｛−１｝に対応する。
【０１２３】
（３）Ｔ６（Ｆｑ）トレースの計算
ｇのトレース表現Ｔｒ（ｇ）とｇのアフィン表現（（２７）式のｆ）の間の関係式を導くために、アフィン表現の要素を用いて、トレース表現の要素を表現する。以下の（３３）式に示す。
【数１０】
【０１２４】
ここでｈ＝ｆ２−ｆ−１、Ａ１ｙ＋Ａ２ｙｑ＋Ａ３ｙ（ｑ＾３）＝ｈ−１とおくと、以下の（３４）式となる。
【数１１】
【０１２５】
したがって、Ｔｒ（ｇ）はｈ−１の各要素の和で表されることが分かる。ここで、ｈは以下の（３５）式のように表される。
【数１２】
【０１２６】
したがって、ｈ−１を計算し、各要素の和をとるとＴｒ（ｇ）が求まる。これらを式展開すると、Ｔｒ（ｇ）の分母部分は以下の（３６）式のようになる。分子部分は後述するためここでの説明は省略する。
【数１３】
【０１２７】
（４）Ｔ６（Ｆｑ）におけるＧ−の条件式
ｆ＾｛ｑ＋１｝は、以下の（３７）式で表される。
【数１４】
【０１２８】
Ｇ−の位数は、ｑ−ｔ＋１であるから、Ｇ−の元はｑ−ｔ＋１乗すると１になる。すなわち、以下の（３８）式となる。
【数１５】
【０１２９】
したがって、ｇｑ＋１＝ｇｔである。ｇｑ＋１＝ｇｔを整理していくと、以下の（３９）式のようになる。
【数１６】
【０１３０】
よって、Ｇ−の条件式は以下の（４０）式となる。（４０）式に示すように、いずれからも同じ式が導出される。
【数１７】
【０１３１】
ここから、上記（２７）式のｆを用いてさらに式展開すると、以下の（４１）式〜（４３）式が得られる。
【数１８】
【０１３２】
（４．１）Ｔ２（Ｆｑ）の条件式
Ｔ２（Ｆｑ３）∈Ｔ６（Ｆｑ）∈Ｇ−なので、Ｔ２（Ｆｑ３）の条件式も整理する。Ｔ２（Ｆｑ３）の位数はｑ２−ｑ＋１なので、ｇ＾（ｑ２−ｑ＋１）＝１が成立する。この式からδ１，δ２，δ３に関する条件式を整理する。以下の（４４）式に示す。
【数１９】
【０１３３】
よって、以下の（４５）式が得られる。
【数２０】
【０１３４】
ここから上記（２７）式を用いて変換を継続すると、以下の（４６）式の関係が得られる。この式も以降の式変形に利用する。
【数２１】
【０１３５】
（５）トレース値が同値なアフィン表現
ある元のトレース値とその元をｑ乗したトレース値とは同一となる。この性質から、同一のトレース値をとるアフィン表現は少なくとも６通り存在する。ここではこれらのアフィン表現の関係を見ていくことにする。ｆ∈Ｆｑ３とすると、関係式は以下の（４７）式のようになる。
【数２２】
【０１３６】
アフィン表現におけるｑ２乗は要素の入れ替えとなるので、ある元をｑ３乗した場合のアフィン表現の違いを見る。以下の（４８）式が成り立つため、ある元をｑ３乗するとアフィン表現上では各要素を２倍して１減じた値になる。
【数２３】
【０１３７】
上記（２７）式および上記（２５）式の第１式（ｙ＋ｙｑ＋ｙ＾（ｑ２）＝−１）であることに注意してトレース値が同一となる要素の組み合わせを導出すると、以下の６個の組み合わせが得られる。
・（δ１，δ２，δ３）
・（２δ３−１，２δ１−１，２δ２−１）
・（δ２，δ３，δ１）
・（２δ１−１，２δ２−１，２δ３−１）
・（δ３，δ１，δ２）
・（２δ２−1，２δ３−1，２δ１−１）
【０１３８】
ｑ２乗すると、各要素の入れ替えとなることがわかる。またα＝δ１−1、β＝δ２−1、γ＝δ３−1と置くと、以下の（４９）式のようになる。
【数２４】
【０１３９】
このｑ３乗は、以下の（５０）式で表される。
【数２５】
【０１４０】
このようにα、β、γを置いておくと、ｑ乗は２倍と要素の入れ替えと考えることができる。また２×２＝１ （ｍｏｄ ３）となることにも注意する。これ以降ではδ１，δ２，δ３をα＋１，β＋１，γ＋１と置き換えて式変形を行っていくことを考える。
【０１４１】
（５．１）Ｔ６（Ｆｑ）トレースの計算（その２）
α，β，γを用いてトレースの式を変形することを考える。上述の（３６）式を変形すると、以下の（５１）式となる。また、分子部分は以下の（５２）式となる。
【数２６】
【０１４２】
（５．２）Ｔ２（Ｆｑ）の条件式（その２）
上述の（４６）式をα，β，γを用いて変形すると、以下の（５３）式となる。
α２＋β２＋γ２＝１・・・（５３）
【０１４３】
（５．３）Ｔ６（Ｆｑ）におけるＧ−の条件式（その２）
上述の（４１）式〜（４３）式をα，β，γを用いて式変形すると、それぞれ以下の３つの式が得られる。
αｔ（γ−β）＋γｔ（α＋β＋γ）−αγ＋αβ＋α２＋β２＝１
βｔ（α−γ）＋αｔ（α＋β＋γ）−βα＋βγ＋β２＋γ２＝１
γｔ（β−α）＋βｔ（α＋β＋γ）−γβ＋γα＋γ２＋α２＝１
【０１４４】
この式の中に現れるｔ乗項は、以下の（５４）式のようになる。
【数２７】
【０１４５】
ここで（５３）式を用いると、以下の（５５）式が得られる。
【数２８】
【０１４６】
またこの式から、以下の（５６）式に示す関係も得られる。
【数２９】
【０１４７】
（５．４）Ｔ６（Ｆｑ）トレースの計算（その３）
（５３）式を用いて、（５１）式および（５２）式を変形する。このときに最終的には対称式である（α＋β＋γ），αβγの２種類と、非対称式である（αβ２＋βγ２＋γα２）を極力使用することとする。また、ここでは、Ａ＝α＋β＋γ，Ｂ＝αβ２＋βγ２＋γα２，Ｃ＝αβγを用いて式の簡略化も図る。
【０１４８】
まず、以下の（５７）式に示す関係がある。
【数３０】
【０１４９】
また、以下の（５８）式に示す関係がある。
【数３１】
【０１５０】
（５７）式および（５８）式より以下の（５９）式が得られる。
【数３２】
【０１５１】
よって、以下の（６０）式が得られる。
【数３３】
【０１５２】
また、Ｃについて考えると、以下の（６１）式および（６２）式が得られる。
【数３４】
【０１５３】
Ｔｒ（ｇ）を変形すると（５１）式および（５２）式より、以下の（６３）式および（６４）式が得られる。
【数３５】
【０１５４】
ここで分母分子に共通の因子が存在するため、これを約分すると、以下の（６５）式および（６６）式が得られる。
【数３６】
【０１５５】
これに（５６）式を用いて式変形を続けると、以下の（６７）式が得られる。
【数３７】
【０１５６】
（６）トレースからトーラスへの変換
これまでにＴｒ（ｇ）はＡ＝α＋β＋γとＣ＝αβγで書き表されることがわかった。ＣはＡとＢ＝αβ２＋βγ２＋γα２の式で書き表せ、ＢはＡで書き表せることを利用して、Ｔｒ（ｇ）の式をＡで書き表す。（６５）式より、以下の（６８）式が得られる。
【数３８】
【０１５７】
この両辺をｔ−２乗すると、以下の（６９）式が得られる。また、（６９）式から（７０）式が得られる。これにより、Ｔｒ（ｇ）からＡ＝α＋β＋γを求めることができる。
【数３９】
【０１５８】
（７）３次式の導出法
Ａ＝α＋β＋γとその他の関係式より、βを得る方法を示す。現在までに得られている関係式は、次のとおりである（（７１）式〜（７４）式）。
Ａ＝α＋β＋γ ・・・（７１）
Ｂ＝αβ２＋βγ２＋γα２ ・・・（７２）
Ｃ＝αβγ ・・・（７３）
α２＋β２＋γ２＝1 ・・・（７４）
【０１５９】
（７１）式を変形すると、以下の（７５）式が得られる。
α＝Ａ−β−γ ・・・（７５）
【０１６０】
（７５）式を（７２）式、（７３）式、（７４）式に代入して整理すると、以下の（７６）式〜（７８）式が得られる。
−β３＋γ３＋Ａβ２＋Ａβγ＋Ａγ２＋Ａ２γ−Ｂ＝０ ・・・（７６）
−β２γ−βγ２＋Ａβγ−Ｃ＝０ ・・・（７７）
−β２−βγ−γ２＋Ａβ＋Ａγ＋Ａ２−1＝０ ・・・（７８）
【０１６１】
（７８）式にβをかけると、以下の（７９）式が得られる。
−β３−β２γ−βγ２＋Ａβ２＋Ａβγ＋（Ａ２−１）β＝０・・・（７９）
【０１６２】
（７９）式から（７７）式を引いた式に−１をかけると、以下の（８０）式が得られる。
β３−Ａβ２−（Ａ２−１）β−Ｃ＝０・・・（８０）
【０１６３】
ここで、（５６）式よりＢ＝（（−1−Ａ２）／Ａｔ）−Ａとなり、（６１）式よりＣ＝Ａ３−Ｂ＋（ＡＢ−Ｂ２−１）／Ａ３であるから、ＣはＡで書き表すことができる。よって、βを根に持つ３次式である以下の３次式が得られた。この式を解くことで、βを得られる。
ｘ３−Ａｘ２−（Ａ２−１）ｘ−Ｃ＝０
【０１６４】
（８）１次式の導出法
Ａ＝α＋β＋γとβとその他の関係式より、γを得る方法を示す。（７８）式にγをかけると、以下の（８１）式が得られる。
−β２γ−βγ２−γ３＋Ａβγ＋Ａγ２＋（Ａ２−１）γ＝０・・・（８１）
【０１６５】
（８１）式から（７７）式を引くと、以下の（８２）式が得られる。
−γ３＋Ａγ２＋（Ａ２−１）γ＋Ｃ＝０・・・（８２）
【０１６６】
さらに、（７６）式から（８０）式を引き、（８２）式を足すと、以下の（８３）式が得られる。
Ａβγ−Ａγ２＋（−Ａ２＋１）β＋（−Ａ２−１）γ−Ｂ＝０・・・（８３）
【０１６７】
（８３）式にβをかけた式と、（７７）式にＡを書けた式は、それぞれ以下の（８４）式および（８５）式となる。
Ａβ２γ−Ａβγ２＋（−Ａ２＋１）β２＋（−Ａ２−１）βγ−Ｂβ＝０・・・（８４）
−Ａβ２γ−Ａβγ２＋Ａ２βγ−ＡＣ＝０・・・（８５）
【０１６８】
（８４）式）から（８５）式を引くと、以下の（８６）式が得られる。
−Ａβ２γ＋（−Ａ２＋１）β２＋（Ａ２−１）βγ−Ｂβ＋ＡＣ＝０・・・（８６）
【０１６９】
（８６）式をＡで割って、γについて整理すると、以下の（８７）式が得られる。
（−β２＋（Ａ−（１／Ａ））β）γ＋（−Ａ＋（１／Ａ））β２−Ｂβ／Ａ＋Ｃ＝０・・・（８７）
【０１７０】
前に求めた２次式と３次式の解より、Ａ，Ｂ，Ｃとβは定数値であるため、γを根にもつ１次式である以下の（８８）式が得られた。
（−β２＋（Ａ−（１／Ａ））β）ｘ＋（−Ａ＋（１／Ａ））β２−Ｂβ／Ａ＋Ｃ＝０・・・（８８）
【０１７１】
βとγが求まれば、（７１）式よりαが求まる。
【０１７２】
（９）まとめ
以下の（８９）式を解くことで、代数的トーラスの部分群の元のトレース表現Ｔｒ（ｇ）より、アフィン表現（α＋1，β＋1，γ＋１）を得る方法を与えた。
【数４０】
【０１７３】
具体的な手順は、次の通りである。
・α＋β＋γを根にもつ２次式である、ｘ２＝−［｛Ｔｒ（ｇ）｝ｔ−２＋１］−１を解いて、２つの解を得る。
・２つの解をそれぞれＡに代入して求めた、βを根にもつ３次式である、ｘ３−Ａｘ２−（Ａ２−１）ｘ−Ｃ＝０を解いて、それぞれ３つの解を得る。
・２次式の解の１つをＡに、Ａに対応する３次式の解の１つをβに代入して求めた、γを根にもつ１次式である、（−β２＋（Ａ−（１／Ａ））β）ｘ＋（−Ａ＋（１／Ａ））β２−Ｂβ／Ａ＋Ｃ＝０を解いて、それぞれ１つの解を求め、対応するαを計算する。
【０１７４】
以上より、計６個の（α，β，γ）が得られるため、付加ビットを用いて正しい（α，β，γ）を特定する。
【０１７５】
次に、圧縮率１／４の場合（第３および第４の実施形態）で用いる式の導出手順について説明する。
【０１７６】
（１）１／４圧縮
トーラスとしてＴ４（Ｆｑ）を考え、その部分群であるトレース（トレース表現）を取ることを考える。円分多項式Φ４を因数分解すると、Φ４＝ｑ２＋１＝（ｑ＋√（２ｑ）＋１）（ｑ−√（２ｑ）＋１）とすることができるので、これらの項が整数になればトーラスを部分群に分割することができる。具体的にはｑを２の奇数乗に取ると、矛盾なく上記の因数分解により部分群が構成できる。
【０１７７】
ここで位数が（ｑ＋√（２ｑ）＋１）となる部分群をＧ＋、（ｑ−√（２ｑ）＋１）となる部分群をＧ−とする。トーラスの中で部分群を取る元からトレースの元への写像は全単射ではないので、あるトレースの元から写像されるトーラスの元は複数存在する。１つのトレースの元に対応するトレースの元は４つ存在するので（詳細はトレース表現を参照のこと）これらを識別可能とするには２ビットの付加ビットが必要となる。これ以後の小節でトレースとアフィン表現の関係を明らかにし、トレースからアフィン表現への伸張を可能とする手法を説明していく。以降の演算は、特に断りが無い限り、Ｆ（２^ｎ）^４上の演算である。
【０１７８】
（２）準備
（２．１）条件の整理
ｔ＝√（２ｑ）と置く。
検討するトーラスやトレースに矛盾がでないよう、また式変形を容易に行えるように以下の（９０）式に示す定義とｑ≡ｔ≡２（ ｍｏｄ ５）という条件をおく。
【数４１】
【０１７９】
なお、上記定義と条件の下では計算上ｘ＝ｘ１,ｘｑ＝ｘ２,ｘ＾ｑ２＝ｘ４,ｘ＾ｑ３＝ｘ３という置き換えが可能である。このような定義と仮定を置くと、以下の（９１）式に示す条件式が得られる。
【数４２】
【０１８０】
（２．２）よく使う関係式
以下の（９２）式に、この後の式変形で用いるｆの関係式について、先にまとめて記載しておく。
【数４３】
【０１８１】
（３）トーラスの構成要素で表すトレース
トレースの値をアフィン表現で用いた係数を用いて表すとどのようになるかを計算していく。なお、Ｔ４のトレース表現Ｔｒ（ｇ）の定義式はＴｒ（ｇ）＝ｇ＋ｇｑ＋ｇ＾ｑ２＋ｇ＾ｑ３である（上述の（１６）式に対応）。以下の（９３）式がこの計算過程を示す式である。
【数４４】
【０１８２】
（４）Ｇ−の条件
ここではＧ−となる条件であるｇｑ＋１＝ｇｔとなる条件を導出する。以下の（９４）式に示すような式変形ができる。
【数４５】
【０１８３】
これ以後はｔ≡ｑ （ｍｏｄ ５）≡２ （ｍｏｄ ５）と仮定する。このときのｔはｔ＝２４ｋ＋１（ｋ∈Ｚ（整数の集合））という条件になり、前述の仮定と矛盾しない。なお、これ以外のパラメータでも構成は可能である。（９４）式からさらに以下の（９５）式に示すような式変形ができる。
【数４６】
【０１８４】
ここからｆ＝δ１ｙ＋δ２ｙｑを代入し、整理する。まずは、以下の（９６）式に示すように、式変形に用いる関係式をまとめて計算しておく。
【数４７】
【０１８５】
上記を使ってＧ−の条件式を再度整理すると、以下の（９７）式のように書ける。
【数４８】
【０１８６】
以上より、ｆ∈Ｇ−の条件は、以下の（９８）式となる。
【数４９】
【０１８７】
これらの条件式を加えて整理すると、以下の（９９）式となる。
【数５０】
【０１８８】
Ｇ−の元となるためには少なくともこの（９９）式を満たさなければならない。
【０１８９】
（５）ｑ乗による変化
Ｔ４のトレース表現Ｔｒ（ｇ）の定義式はＴｒ（ｇ）＝ｇ＋ｇｑ＋ｇ＾ｑ２＋ｇ＾ｑ３であるので、Ｔｒ（ｇｑ）＝ｇｑ＋ｇ＾ｑ２＋ｇ＾ｑ３＋ｇ、Ｔｒ（ｇ＾ｑ２）＝ｇ＾ｑ２＋ｇ＾ｑ３＋ｇ＋ｇｑ、Ｔｒ（ｇ＾ｑ３）＝ｇ＾ｑ３＋ｇ＋ｇｑ＋ｇ＾ｑ２という関係式が成り立つ。すなわち、あるトーラスの元ｇをｑ乗した元のトレースは、もとのトレースと同じ値となる関係がある。Ｇ−に属していたトーラスの元をｑ乗しても、やはりＧ−の元になることは明らかであるから、ある条件式をｑ乗しても性質は保たれるはずである。そこで、トーラスの元をｑ乗した場合に係数に起こる変化を眺め、その変化を以降の式変形に当てはめて用いることを考える。
【数５１】
以上の（１００）式に示すように式変形可能なので、ｆ＝δ１ｙ＋δ２ｙｑであることを考えると、（δ１,δ２）→（δ２＋１,δ１）というように係数が変化していることが分かる。このように変化してもＧ−の条件式もトーラスからトレースへの変換式も変化がない。実際、この変化を前述のＧ−の条件式に当てはめてみるともとの式に戻り、この変化によりＧ−の条件式が変化することはない。ここ以降ではｑ乗したように係数を変化させて得られる式の関係性をｑ乗対称の関係と呼ぶことにする。
【０１９０】
（６）トレースからトーラスへの伸張
トーラスからトレースへの変換式とＧ−の条件式を用いてトレースからトーラスへの変換式の導出を試みる。
（６．１）準備
以下では、トレースからトーラスへ変換する前に、必要となる関係式を導出しておく。δ１２＋δ２とδ１＋δ２２の関係式をＧ−の条件式である（９９）式から作成することを試みる。Ｇ−の条件式を整理すると（δ１＋δ２）ｔ＋１＝δ１ｔ＋δ２＋１である。これをｔ２＝２であることに注意してｔ−１乗すると、以下の（１０１）式となる。
【数５２】
【０１９１】
（１０１）式はｑ乗対称になっていない。ｑ乗対称性を満たすためには（δ１,δ２）→（δ２＋１,δ１）と係数を変化させても関係が保たれることが必要であるから、（１０１）式をｑ乗対称にした以下の（１０２）式も同時に満たされるはずである。
【数５３】
【０１９２】
一方、（１０１）式にδ１＋δ１２を加えた上で、（δ１＋δ２＋１）をかけると、以下の（１０３）式が得られる。
【数５４】
【０１９３】
左辺に（１０２）式を代入すると以下の（１０４）式が得られる。
【数５５】
【０１９４】
この式もｑ乗対称の関係を考え、（δ１,δ２）→（δ２＋１,δ１）と係数を変化させると、以下の（１０５）式が得られる。
【数５６】
【０１９５】
これらの２式（（１０４）式、（１０５）式）を加えると、以下の（１０６）式となり、以下の（１０７）式が得られる。
【数５７】
【０１９６】
この式でもｑ乗対称の関係を考え、（δ１,δ２）→（δ２＋１,δ１）と係数変化させると、以下の（１０８）式が得られ、δ１２＋δ２とδ１＋δ２２の関係式が得られた。
【数５８】
【０１９７】
（６．２）トレースの式変形
トレースの式をδ１,δ２で表すと、以下の（１０９）式のようになる。
【数５９】
【０１９８】
この式を少し整理し、以下の（１１０）式とする。
【数６０】
【０１９９】
ここでδ１２δ２２＋δ２３＝δ２２（δ１２＋δ２）,δ１３＋δ１δ２＝δ１（δ１２＋δ２）を用いて式変形すると、以下の（１１１）式となる。
【数６１】
【０２００】
ここで上述の（１０７）式および（１０８）式を代入すると、以下の（１１２）式となり、２元２次方程式が得られる。
【数６２】
【０２０１】
δ１＋δ２＝Ｘとおくと、上記（１１２）式は、以下の（１１３）式のような１元２次方程式に置き換わる。
【数６３】
【０２０２】
標数２の２次方程式の解の公式はないが、具体的に体を構成すると解が求まる。具体的にＸが求まれば、前述の（１０７）式の左辺がδ１２＋δ２＝（Ｘ−δ２）２＋δ２＝δ２２＋δ２＋Ｘ２と置き換えられることを利用し、以下の（１１４）式をδ２について解くことでδ１，δ２が求まる。
【数６４】
【０２０３】
なお、これらの（１１３）式および（１１４）式は、解が２つずつ出てくるため、２×２で４つの解が求まるはずである。これらの４解は同じトレース値から得られるもので、これら４つの解のうち、いずれの解がもとのトーラスの元を表しているかを特定するために付加ビットを利用することにする。
【０２０４】
これら４解は、それぞれｑ乗対称の関係にある。すなわち（δ１，δ２）→（δ２＋１，δ１）→（δ１＋１，δ２＋１）→（δ２＋１，δ１）（→（δ１，δ２））という関係である。ｑ乗するごとに矢印を右に進み、ｑ４乗するともとに戻ってくるというものである。この関係から、例えば、ある解のδ１，δ２の最下位１ビットに注目すると、それらが（０，０）であった場合のｑ乗対称の関係を見ていくと、（０，０）→（０，１）→（１，１）→（１，０）（→（０，０））という関係になり、それぞれが１乗、ｑ乗、ｑ２乗，ｑ３乗となっているはずである。このため、例えばδ１、δ２の最下位１ビットずつを付加ビットとして採用しておけば、トレースの元から、もとの正しいトーラスの元を特定することが可能である。
【０２０５】
（６．３）具体的構成例
以下に、トーラスのアフィン表現からトレースに変換する手法とトレースからトーラスのアフィン表現に変換する手法の一例を簡単に記す。
【０２０６】
（トーラスからトレース）
・入力：（δ１，δ２）
・出力：Ｔｒ（ｇ），（ｂ０，ｂ１）（ｂ０，ｂ１は付加ビット）
１．上記（１０９）式によりＴｒ（ｇ）を求める。
２．δ１の最下位ビットをｂ０、δ２の最下位ビットをｂ１とし、Ｔｒ（ｇ），（ｂ０，ｂ１）を出力する。
【０２０７】
（トレースからトーラス）
・入力：Ｔｒ（ｇ），（ｂ０，ｂ１）
・ 出力：（δ１，δ２）
１．Ｘ２＋Ｘ＋１＝｛Ｔｒ（ｇ）｝ｑ−ｔを解き、Ｘ０，Ｘ１を求める。
２．δ２２＋δ２＋Ｘ０２＋Ｘ０ｔ｛Ｔｒ（ｇ）｝ｑ−ｔ＝０を解き、δ２ａ，δ２ｂを求める。
３．Ｘ０＝δ１ａ＋δ２ａよりδ１ａを求める。
４．（δ１ａ，δ２ａ）の最下位ビットと（ｂ０，ｂ１）とを比べ、一致していなかったら５へ遷移し、一致していたら６へ遷移する。
５．（δ１ａ，δ２ａ）＝（δ２ａ＋１，δ１ａ）と設定しなおし、４へ戻る。
６．（δ１，δ２）＝（δ１ａ，δ２ａ）とし、（δ１，δ２）を出力する。
【０２０８】
（７）まとめ
以上で、トレースの元に付加ビットを加えたものからＴ４トーラスの元に復元する具体的手法を与えた。これにより従来のトーラスではもとの有限体の大きさと比べて１／３までしか表現の圧縮ができていなかったのに対し、漸近的に１／４まで圧縮が可能となった。
【０２０９】
以上説明したとおり、第１から第４の実施形態によれば、従来の方法では効率的に伸長写像が構成できない法多項式に対して、効率的に圧縮装置および伸長装置を実現することができる。
【０２１０】
次に、第１から第４の実施形態にかかる伸長装置および圧縮装置のハードウェア構成について図１０を用いて説明する。図１０は、第１から第４の実施形態にかかる伸長装置および圧縮装置のハードウェア構成を示す説明図である。
【０２１１】
第１から第４の実施形態にかかる伸長装置および圧縮装置は、ＣＰＵ（Central Processing Unit）５１などの制御装置と、ＲＯＭ（Read Only Memory）５２やＲＡＭ（Random Access Memory）５３などの記憶装置と、ネットワークに接続して通信を行う通信Ｉ／Ｆ５４と、各部を接続するバス６１を備えている。
【０２１２】
第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムは、ＲＯＭ５２等に予め組み込まれて提供される。
【０２１３】
第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact Disk Recordable）、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供されるように構成してもよい。
【０２１４】
さらに、第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０２１５】
第１から第４の実施形態にかかる伸長装置および圧縮装置で実行されるプログラムは、コンピュータを上述した伸長装置および圧縮装置の各部として機能させうる。このコンピュータは、ＣＰＵ５１がコンピュータ読取可能な記憶媒体からプログラムを主記憶装置上に読み出して実行することができる。
【０２１６】
なお、本実施形態は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【符号の説明】
【０２１７】
１００ 圧縮装置
１０１ 入力部
１０２ 第１変換部
１０３ 第２変換部
１０４ 付加ビット決定部
１０５ 出力部
１２１ 記憶部
２００ 伸長装置
２０１ 入力部
２０２ 第１選択部
２０３ 伸長部
２０４ 出力部
２１０ 算出部
２１１ 第１式決定部
２１２ 第１求解部
２１３ 第２式決定部
２１４ 第２求解部
２１５ 第３式決定部
２１６ 第３求解部
２１７ 第２選択部
２２１ 記憶部
【特許請求の範囲】
【請求項１】
有限体の乗法群の部分群の要素をトレース表現で表したトレース表現データと前記トレース表現データをアフィン表現で表したアフィン表現データに基づいて得られる付加データと、前記トレース表現データとを入力する入力部と、
前記トレース表現データによって決定される連立方程式の複数の解を算出する算出部と、
前記付加データに基づいて、複数の前記解から求められるデータであって、前記要素をアフィン表現で表した複数のアフィン表現データのうちいずれかを選択する第１選択部と、
選択された前記アフィン表現データを前記要素に伸長する伸長部と、
を備えることを特徴とする伸長装置。
【請求項２】
前記算出部は、
前記有限体上の予め求められたｋ１次式（ｋ１は予め定められる１以上の整数）の予め定められた係数に前記トレース表現データを入力して得られる第１式の解を求める第１求解部と、
前記有限体上の予め求められたｋ２次式（ｋ２は予め定められる１以上の整数）の予め定められた係数に前記第１式の解の少なくとも１つを入力して得られる第２式の解を求める第２求解部と、を備え、
前記第２式の解に基づいて前記連立方程式の複数の解を算出すること、
を特徴とする請求項１に記載の伸長装置。
【請求項３】
前記第１求解部は、前記有限体上の予め求められた２次式の予め定められた係数に前記トレース表現データを入力して得られる前記第１式の２個の解を求め、
前記第２求解部は、前記有限体上の予め求められた３次式の予め定められた係数に前記２個の解の少なくとも１つを入力して得られる前記第２式の３個の解を求め、
前記算出部はさらに、
前記有限体上の予め求められた１次式の予め定められた係数に、前記第１式の２個の解および前記第２式の３個の解のうち少なくとも１つを入力して得られる第３式の解を求める第３求解部を備え、
前記第２式の解および前記第３式の解に基づいて前記連立方程式の複数の解を算出すること、
を特徴とする請求項２に記載の伸長装置。
【請求項４】
前記算出部は、
前記付加データに基づいて、前記第１式の解のうちいずれかの解を選択する第２選択部をさらに備え、
前記第２求解部は、前記ｋ２次式の予め定められた係数に、前記第２選択部により選択された解を入力して得られる前記第２式の解を求めること、
を特徴とする請求項２に記載の伸長装置。
【請求項５】
有限体の乗法群の部分群の要素を、前記要素をトレース表現で表したトレース表現データに変換する第１変換部と、
前記要素を、前記要素をアフィン表現で表したアフィン表現データに変換する第２変換部と、
前記アフィン表現データに基づいて、前記アフィン表現データを求めるための付加データを決定する決定部と、
前記トレース表現データと前記付加データとを出力する出力部と、
を備えることを特徴とする圧縮装置。
【請求項６】
前記決定部は、前記アフィン表現データの一部を前記付加データとして決定すること、
を特徴とする請求項５に記載の圧縮装置。
【請求項７】
前記決定部は、前記トレース表現データによって決定される連立方程式の複数の解を予め定められた基準で並べたときの前記アフィン表現データと一致する解の先頭からの順序を前記付加データとして決定すること、
を特徴とする請求項５に記載の圧縮装置。
【請求項８】
前記有限体上の予め求められたｋ１次式（ｋ１は予め定められる１以上の整数）の予め定められた係数に前記トレース表現データを入力して得られる第１式の解を求め、前記有限体上の予め求められたｋ２次式（ｋ２は予め定められる１以上の整数）の予め定められた係数に前記第１式の解の少なくとも１つを入力して得られる第２式の解を求め、前記第２式の解に基づいて前記連立方程式の複数の解を算出する算出部をさらに備え、
前記決定部は、前記第１式の解を予め定められた基準で並べたときの前記アフィン表現データの要素の和と一致する解の先頭からの順序、および、前記連立方程式の複数の解を前記基準で並べたときの前記アフィン表現データと一致する解の先頭からの順序を、前記付加データとして決定すること、
を特徴とする請求項５に記載の圧縮装置。
【請求項１】
有限体の乗法群の部分群の要素をトレース表現で表したトレース表現データと前記トレース表現データをアフィン表現で表したアフィン表現データに基づいて得られる付加データと、前記トレース表現データとを入力する入力部と、
前記トレース表現データによって決定される連立方程式の複数の解を算出する算出部と、
前記付加データに基づいて、複数の前記解から求められるデータであって、前記要素をアフィン表現で表した複数のアフィン表現データのうちいずれかを選択する第１選択部と、
選択された前記アフィン表現データを前記要素に伸長する伸長部と、
を備えることを特徴とする伸長装置。
【請求項２】
前記算出部は、
前記有限体上の予め求められたｋ１次式（ｋ１は予め定められる１以上の整数）の予め定められた係数に前記トレース表現データを入力して得られる第１式の解を求める第１求解部と、
前記有限体上の予め求められたｋ２次式（ｋ２は予め定められる１以上の整数）の予め定められた係数に前記第１式の解の少なくとも１つを入力して得られる第２式の解を求める第２求解部と、を備え、
前記第２式の解に基づいて前記連立方程式の複数の解を算出すること、
を特徴とする請求項１に記載の伸長装置。
【請求項３】
前記第１求解部は、前記有限体上の予め求められた２次式の予め定められた係数に前記トレース表現データを入力して得られる前記第１式の２個の解を求め、
前記第２求解部は、前記有限体上の予め求められた３次式の予め定められた係数に前記２個の解の少なくとも１つを入力して得られる前記第２式の３個の解を求め、
前記算出部はさらに、
前記有限体上の予め求められた１次式の予め定められた係数に、前記第１式の２個の解および前記第２式の３個の解のうち少なくとも１つを入力して得られる第３式の解を求める第３求解部を備え、
前記第２式の解および前記第３式の解に基づいて前記連立方程式の複数の解を算出すること、
を特徴とする請求項２に記載の伸長装置。
【請求項４】
前記算出部は、
前記付加データに基づいて、前記第１式の解のうちいずれかの解を選択する第２選択部をさらに備え、
前記第２求解部は、前記ｋ２次式の予め定められた係数に、前記第２選択部により選択された解を入力して得られる前記第２式の解を求めること、
を特徴とする請求項２に記載の伸長装置。
【請求項５】
有限体の乗法群の部分群の要素を、前記要素をトレース表現で表したトレース表現データに変換する第１変換部と、
前記要素を、前記要素をアフィン表現で表したアフィン表現データに変換する第２変換部と、
前記アフィン表現データに基づいて、前記アフィン表現データを求めるための付加データを決定する決定部と、
前記トレース表現データと前記付加データとを出力する出力部と、
を備えることを特徴とする圧縮装置。
【請求項６】
前記決定部は、前記アフィン表現データの一部を前記付加データとして決定すること、
を特徴とする請求項５に記載の圧縮装置。
【請求項７】
前記決定部は、前記トレース表現データによって決定される連立方程式の複数の解を予め定められた基準で並べたときの前記アフィン表現データと一致する解の先頭からの順序を前記付加データとして決定すること、
を特徴とする請求項５に記載の圧縮装置。
【請求項８】
前記有限体上の予め求められたｋ１次式（ｋ１は予め定められる１以上の整数）の予め定められた係数に前記トレース表現データを入力して得られる第１式の解を求め、前記有限体上の予め求められたｋ２次式（ｋ２は予め定められる１以上の整数）の予め定められた係数に前記第１式の解の少なくとも１つを入力して得られる第２式の解を求め、前記第２式の解に基づいて前記連立方程式の複数の解を算出する算出部をさらに備え、
前記決定部は、前記第１式の解を予め定められた基準で並べたときの前記アフィン表現データの要素の和と一致する解の先頭からの順序、および、前記連立方程式の複数の解を前記基準で並べたときの前記アフィン表現データと一致する解の先頭からの順序を、前記付加データとして決定すること、
を特徴とする請求項５に記載の圧縮装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１２−１２３２７７（Ｐ２０１２−１２３２７７Ａ）
【公開日】平成２４年６月２８日（２０１２．６．２８）
【国際特許分類】
【出願番号】特願２０１０−２７５１６０（Ｐ２０１０−２７５１６０）
【出願日】平成２２年１２月９日（２０１０．１２．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２４年６月２８日（２０１２．６．２８）
【国際特許分類】
【出願日】平成２２年１２月９日（２０１０．１２．９）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]