"標数pの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をEとし、合成数位数rを持つ有理点の集合すなわち前記加法群の部分群をG1Er、G2Erとして、有理点P∈G1及び有理点Q∈G2の情報を送受信するCPU及び記憶手段を備えた有理点情報圧縮装置において、前記加法群Eは、埋め込み次数を1とし、前記電子計算機のCPUは、有理点P’を入力して前記記憶手段に記憶する入力手段と、前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、λ1Pψ、λ2Qψλ1≠λ2は整数を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段と、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψまたはψを演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段と、前記有理点P及び前記有理点Qから有理点R=PQを演算する第1演算手段と、前記有理点Rから有理点P及び有理点Qを演算する第2演算手段と、を有する有理点情報圧縮装置。前記楕円曲線は、Ey2x3axa∈Fp4であり、前記合成数位数rは、rE4を満たし、前記整数λ1、λ2は、λ121≡0、λ221≡0を満たし、前記自己準同型写像は、ψEr→Er、→ζ41ζζ2∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれλ1ψλ1R2PQRPを用いて行う請求項1に記載の有理点情報圧縮装置。前記楕円曲線は、Ey2x3bb∈Fp3であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行う請求項1に記載の有理点情報圧縮装置。前記楕円曲線は、Ey2x3bb∈Fp6であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行う請求項1に記載の有理点情報圧縮装置。標数pの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をEとし、合成数位数rを持つ有理点の集合すなわち前記加法群の部分群をG1Er、G2Erとして、有理点P∈G1及び有理点Q∈G2の情報を送受信する場合に、CPU及び記憶手段を備えた電子計算機で行う情報圧縮方法において、前記加法群Eは、埋め込み次数を1とし、前記電子計算機のCPUを入力手段として機能させて、有理点P’を入力して前記記憶手段に記憶する入力ステップと、前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、λ1Pψ、λ2Qψλ1≠λ2は整数を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定するステップと、前記電子計算機のCPUを自己準同型写像演算手段として機能させて、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψまたはψを演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算ステップと、前記電子計算機のCPUを第1演算手段として機能させて、前記有理点P及び前記有理点Qから有理点RPQを演算する第1演算ステップと、前記電子計算機のCPUを第2演算手段として機能させて、前記有理点Rから有理点P及び有理点Qを演算する第2演算ステップと、を有する有理点情報圧縮方法。前記楕円曲線は、Ey2x3axa∈Fp4であり、前記合成数位数rは、rE4を満たし、前記整数λ1、λ2は、λ121≡0、λ221≡0を満たし、前記自己準同型写像は、ψEr→Er、→ζ41ζζ2∈Fpであり、前記第2演算ステップは、前記有理点P前記有理点Qの演算を、それぞれλ1ψλ1R2PQRPを用いて行う請求項5に記載の有理点情報圧縮方法。前記楕円曲線は、Ey2x3bb∈Fp3であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算ステップは、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行う請求項5に記載の有理点情報圧縮方法。前記楕円曲線は、Ey2x3bb∈Fp6であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算ステップは、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行う請求項5に記載の有理点情報圧縮方法。標数pの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をEとし、合成数位数rを持つ有理点の集合すなわち前記加法群の部分群をG1Er、G2Erとして、有理点P∈G1及び有理点Q∈G2の情報を送受信する場合に、CPU及び記憶手段を備えた電子計算機に行わせる有理点情報圧縮プログラムにおいて、前記加法群Eは、埋め込み次数を1とし、前記電子計算機のCPUを有理点P’を入力して前記記憶手段に記憶する入力手段、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、λ1Pψ、λ2Qψλ1≠λ2は整数を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψまたはψを演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段、前記有理点P及び前記有理点Qから有理点RPQを演算する第1演算手段、前記有理点Rから有理点P及び有理点Qを演算する第2演算手段、として機能させる有理点情報圧縮プログラム。前記楕円曲線は、Ey2x3axa∈Fp4であり、前記合成数位数rは、rE4を満たし、前記整数λ1、λ2は、λ121≡0、λ221≡0を満たし、前記自己準同型写像は、ψEr→Er、→ζ41ζζ2∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれλ1ψλ1R2PQRPを用いて行う請求項9に記載の有理点情報圧縮プログラム。前記楕円曲線は、Ey2x3bb∈Fp3であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行う請求項9に記載の有理点情報圧縮プログラム。前記楕円曲線は、Ey2x3bb∈Fp6であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行う請求項9に記載の有理点情報圧縮プログラム。しかしながら、本発明が対象とする有理点群の埋め込み次数が1の場合、有理点P及びQを圧縮して有理点Rを送信し、受信先でこれを分解復元する方法は、これまで知られていなかった。本発明者らは、このような現状に鑑み、有理点の情報圧縮を効率的に行うべく研究開発を行って、本発明を成すに至ったものである。本発明の有理点情報圧縮装置では、標数pの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をEとし、合成数位数rを持つ有理点の集合すなわち前記加法群の部分群をG1Er、G2Erとして、有理点P∈G1及び有理点Q∈G2の情報を送受信するCPU及び記憶手段を備えた有理点情報圧縮装置において、前記加法群Eは、埋め込み次数を1とし、前記電子計算機のCPUは、有理点P’を入力して前記記憶手段に記憶する入力手段と、前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、λ1Pψ、λ2Qψλ1≠λ2は整数を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段と、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψまたはψを演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段と、前記有理点P及び前記有理点Qから有理点R=PQを演算する第1演算手段と、前記有理点Rから有理点P及び有理点Qを演算する第2演算手段と、を有することとした。さらに本発明の有理点情報圧縮装置では、前記楕円曲線は、Ey2x3axa∈Fp4であり、前記合成数位数rは、rE4を満たし、前記整数λ1、λ2は、λ121≡0、λ221≡0を満たし、前記自己準同型写像は、ψEr→Er、→ζ41ζζ2∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれλ1ψλ1R2PQRPを用いて行うことにも特徴を有するものである。本発明の有理点情報圧縮装置では、前記楕円曲線は、Ey2x3bb∈Fp3であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行うことにも特徴を有するものである。さらに本発明の有理点情報圧縮装置では、前記楕円曲線は、Ey2x3bb∈Fp6であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行うことにも特徴を有するものである。本発明の有理点情報圧縮方法では、標数pの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をEとし、合成数位数rを持つ有理点の集合すなわち前記加法群の部分群をG1Er、G2Erとして、有理点P∈G1及び有理点Q∈G2の情報を送受信する場合に、CPU及び記憶手段を備えた電子計算機で行う情報圧縮方法において、前記加法群Eは、埋め込み次数を1とし、前記電子計算機のCPUを入力手段として機能させて、有理点P’を入力して前記記憶手段に記憶する入力ステップと、前記電子計算機のCPUを有理点部分群特定手段として機能させて、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、λ1Pψ、λ2Qψλ1≠λ2は整数を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定するステップと、前記電子計算機のCPUを自己準同型写像演算手段として機能させて、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψまたはψを演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算ステップと、前記電子計算機のCPUを第1演算手段として機能させて、前記有理点P及び前記有理点Qから有理点RPQを演算する第1演算ステップと、前記電子計算機のCPUを第2演算手段として機能させて、前記有理点Rから有理点P及び有理点Qを演算する第2演算ステップと、を有することとした。さらに本発明の有理点情報圧縮方法では、前記楕円曲線は、Ey2x3axa∈Fp4であり、前記合成数位数rは、rE4を満たし、前記整数λ1、λ2は、λ121≡0、λ221≡0を満たし、前記自己準同型写像は、ψEr→Er、→ζ41ζζ2∈Fpであり、前記第2演算ステップは、前記有理点P前記有理点Qの演算を、それぞれλ1ψλ1R2PQRPを用いて行うことにも特徴を有するものである。さらに本発明の有理点情報圧縮方法では、前記楕円曲線は、Ey2x3bb∈Fp3であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算ステップは、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行うことにも特徴を有するものである。さらに本発明の有理点情報圧縮方法では、前記楕円曲線は、Ey2x3bb∈Fp6であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算ステップは、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行うことにも特徴を有するものである。本発明の有理点情報圧縮プログラムでは、標数pの有限体Fp上で定義された楕円曲線上の有理点の成す加法群をEとし、合成数位数rを持つ有理点の集合すなわち前記加法群の部分群をG1Er、G2Erとして、有理点P∈G1及び有理点Q∈G2の情報を送受信する場合に、CPU及び記憶手段を備えた電子計算機に行わせる有理点情報圧縮プログラムにおいて、前記加法群Eは、埋め込み次数を1とし、前記電子計算機のCPUを有理点P’を入力して前記記憶手段に記憶する入力手段、前記記憶手段から前記有理点P’を読み出し、自己準同型写像ψにより、λ1Pψ、λ2Qψλ1≠λ2は整数を満足する前記有理点P及びQの集合である前記部分群G1及びG2を特定する有理点部分群特定手段、前記記憶手段から前記有理点PまたはQを読み出し、前記自己準同型写像ψまたはψを演算しその結果の有理点を前記記憶手段に記憶する自己準同型写像演算手段、前記有理点P及び前記有理点Qから有理点RPQを演算する第1演算手段、前記有理点Rから有理点P及び有理点Qを演算する第2演算手段、として機能させることとした。さらに本発明の有理点情報圧縮プログラムでは、前記楕円曲線は、Ey2x3axa∈Fp4であり、前記合成数位数rは、rE4を満たし、前記整数λ1、λ2は、λ121≡0、λ221≡0を満たし、前記自己準同型写像は、ψEr→Er、→ζ41ζζ2∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれλ1ψλ1R2PQRPを用いて行うことにも特徴を有するものである。さらに本発明の有理点情報圧縮プログラムでは、前記楕円曲線は、Ey2x3bb∈Fp3であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行うことにも特徴を有するものである。さらに本発明の有理点情報圧縮プログラムでは、前記楕円曲線は、Ey2x3bb∈Fp6であり、前記合成数位数rは、rE3を満たし、前記整数λ1、λ2は、λ12λ11≡0、λ22λ21≡0を満たし、前記自己準同型写像は、ψEr→Er、→ε31ε∈Fpであり、前記第2演算手段は、前記有理点P前記有理点Qの演算を、それぞれ2λ11ψλ11R3PQRPを用いて行うことにも特徴を有するものである。本発明によれば、有理点PQの情報を送信する時に有理点Pと有理点Qの楕円加算を行い求めた有理点Rの情報を送信し、受信先で有理点Rの情報を分解し有理点PQの情報を復元することとなり、送受信する有理点の情報量を半分に圧縮することができる。この分解復元に要する計算は、有理点のペアあたり、おおよそスカラー倍算1回分である。このことにより、インターネット等のネットワークを介して有理点情報を送受信する際の効率化を図ることができる。本発明の成果を適用できるようなペアリング曲線は、以下のような条件を満たす必要がある。まず、標数pの有限体Fp上で定義される楕円曲線を、EFpy2x3axba∈Fpb∈Fpとし、E標数pの有限体Fp上で定義される楕円曲線の有理点が成す加法群、r:Eの位数Eを割り切る合成数、Er:位数が合成数rである有理点の集合、ψ有理点に対する自己準同型写像、t:フロベニウス写像のトレース、j:有理点をj倍する写像、G:GEr∩Ker、λは整数を満たす有理点の集合、と定義する。また、x|yは、xがyを割り切ることを表わすものとする。楕円曲線の生成にはCMComplexMultiplication法が知られている。標数p、フロベニウス自己準同型写像のトレースt、判別式Dによる次式のようなCM方程式において、判別式D13の場合を考える。4pt2Ds2この時、ペアリング曲線の式はそれぞれ以下のように与えられる。Eay2x3axa∈FpEby2x3bb∈Fp本発明者らは、大きな合成数位数に対してこのようなペアリング曲線を生成する簡便な生成法を提案済みである。上記のペアリング曲線上の有理点が、簡単な自己準同型写像ψ即ち有理点をP、整数をλとして、ψλPを持つためには、パラメータの条件がある。これには、以下に示すように、自己準同型写像の周期3,4,6に対応して3次、4次、6次の3つの場合がある。この自己準同型写像はスカラー倍算、ペアリングに用いる他、本発明では、この自己準同型写像を有理点情報の圧縮復元に用いる。以下に、パラメータの条件及びその写像を示す。<3次の場合>楕円曲線のパラメータが、3Ey2x3bb∈FpD3の場合、rE3を満たす合成数rに対して、次式を満足するある整数λ3が存在する。λ32λ31≡0また、以下に示す周期3の自己準同型写像ψ3が与えられる。このような合成数rを位数として持つ有理点をP∈Erとすれば、3次の場合、λ3Pψ3の関係を用いることで後述の有理点情報圧縮の効率化を図っている。しかしながら、有理点群の埋め込み次数が1の場合、一般の有理点P’∈Erに対しては、λ3P’ψ3は成り立たない。上述したように、これを満たすような有理点の割合は1/r=1/22000であり、簡便にそのような有理点及び有理点部分群を準備できる必要がある。本発明では、本発明者らが発見した以下の性質を用いる。まず、任意の有理点P’∈Erは次式を満たす。P’Oここで、Oは、無限遠点を示す。以下の記述においても同様である。すなわち、ランダムに生成した有理点P’∈Erを倍し、Pψ3λ31P’とすることにより、その有理点Pはλ3Pψ3を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1とする。また逆に、Qψ3λ3P’とすれば、λ31Qψ3を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2とする。これらG1及びG2を用いて後述の有理点情報の圧縮復元を実現することができる。<関係式の導出法の説明>3次の場合の式の導出について以下に説明する。まず、任意の有理点P’∈Erは、Eのフロベニウス写像のトレースt及びフロベニウス写像φを用いて、次式を満たすことが知られている。φ→P’O同様に、P’をEと同型な群を内包する拡大体上ツイスト曲線E’に写像した有理点Pを考えれば、E’のフロベニウス写像のトレースをt’として次式を満たす。POここで、ツイスト曲線は、E’y2x3bv2b∈Fpで与えられ、vはFpの3乗非剰余な元であり、Pは、P’として以下で与えられる。Pここで、上式を写像ψP’∈E→P∈E’とすれば、式は次式のように変形できる。ψ1φ2ψt’そしてこの場合、ψ1φψψ3が成り立つので次式を得る。P’O上式に対して、有理点群の埋め込み次数が1であることからp≡1であり、加えてこれに用いる楕円曲線をt’≡1、0、1となるように生成していることから、P’∈Er位数rの有理点とすれば、3次のときには次式を得る。P’O一方で3次の場合には、式を満たすような整数λ3も存在し、すなわちψ32ψ31≡0を、ψ3を変数とするような方程式と考えれば、その解の1つがψ3となる。したがって、式のような因数分解された関係式が得られる。<4次の場合>同様に、楕円曲線のパラメータが、4Ey2x3axa∈FpD1の場合、rE4を満たす合成数rに対して、次式を満足するある整数λ4が存在する。λ421≡0また、以下に示す周期4の自己準同型写像ψ4が与えられる。このような合成数rを位数として持つ有理点をP∈Erとすれば、4次の場合、λ4Pψ4の関係を用いることで後述の有理点情報圧縮の効率化を図っている。本発明では、本発明者らが発見した以下の性質を用いる。まず、任意の有理点P’∈Erは次式を満たす。P’Oすなわち、ランダムに生成した有理点P’∈Erを倍し、Pψ4λ4P’とすることにより、その有理点Pはλ4Pψ4を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1とする。また逆に、Qψ4λ4P’とすれば、λ4Qψ4を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2とする。これらG1及びG2を用いて後述の有理点情報の圧縮復元を実現することができる。4次の場合の式の導出については、3次の場合と同様であるので説明は省略する。<6次の場合>さらに同様に、楕円曲線のパラメータが、6Ey2x3bb∈FpD3の場合、rE3を満たす合成数rに対して、次式を満足するλ6が存在する。λ62λ61≡0また、以下に示す周期6の自己準同型写像ψ6が与えられる。このような位数rを持つ有理点をP∈Erとし、6次の場合、λ6Pψ6の関係を用いることで後述の有理点情報圧縮の効率化を図っている。本発明では、本発明者らが発見した以下の性質を用いる。まず、任意の有理点P’∈Erは次式を満たす。P’Oすなわち、ランダムに生成した有理点P’∈Erを倍し、Pψ6λ61P’とすることにより、その有理点Pはλ6Pψ6を満たすこととなる。そして、そのようなPが生成する有理点部分群をG1とする。また逆に、Qψ6λ6P’とすれば、λ61Qψ6を満たす有理点Qとなる。そして、そのようなQが生成する有理点部分群をG2とする。これらG1及びG2を用いて後述の有理点情報の圧縮復元を実現することができる。6次の場合の式の導出についても、3次の場合と同様であるので説明は省略する。本発明の有理点情報の圧縮装置、圧縮方法及び圧縮プログラムでは、有理点群の埋め込み次数が1の場合において、有理点部分群G1、G2を特定し、2つの有理点P∈G1、Q∈G2を送信する際に有理点PQを楕円加算して圧縮した有理点Rを送信している。受信先での元の有理点情報PQへの分解復元は、上述のG1、G2の特性を利用して行う。以下に4次、3次、及び6次の場合について説明する。いずれもスカラー倍算1回程度の計算で、有理点情報を分解復元できる。<4次の場合>まず、有理点PQは次式を満たす。λ4Pψ4λ4Qψ4すなわち、言い換えればそれぞれ次式を満たす。ψ4λ4POψ4λ4QOしたがって、受信データRPQに対して、例えば、ψ4λ4倍算を施せば、ψ4λ4Rψ4λ4ψ4λ4Pψ4λ4Qψ4λ4POψ4λ4Pλ4Pλ4P2λ4Pとなり、両辺にλ4を乗じて、rλ421≡0を適用すれば次式を得る。λ4ψ4λ4R2λ42P2Pこれに21modr倍算を施せばPを得ることができる。Qは、QRPにより求めることができる。このようにスカラー倍算1回くらいの計算量で分解復元ができるため、情報圧縮してデータを送信することの効率化を図ることができる。3次の場合>まず、有理点PQは次式を満たす。λ3Pψ3λ31Qψ3すなわち、言い換えればそれぞれ次式を満たす。ψ3λ3POψ3λ31QOしたがって、受信データRPQに対して、例えばψ3λ31倍算を施せば、ψ3λ31Rψ3λ31ψ3λ31Pψ3λ31Qψ3λ31POψ3λ3PP2λ31Pとなり、両辺に2λ31を乗じて、rλ32λ31≡0を適用すれば次式を得る。2λ31ψ3λ31R2λ312P4λ324λ31P3Pこれに31modr倍算を施せばPを得ることができる。Qは、QRPにより求めることができる。このようにスカラー倍算1回くらいの計算量で分解復元ができるため、情報圧縮してデータを送信することの効率化を図ることができる。6次の場合>まず、有理点PQは次式を満たす。λ6Pψ6λ61Qψ6すなわち、言い換えればそれぞれ次式を満たす。ψ6λ6POψ6λ61QOしたがって、受信データRPQに対して、例えばψ6λ61倍算を施せば、ψ6λ61Rψ6λ61ψ6λ61Pψ6λ61Qψ6λ61POψ6λ6PP2λ61Pとなり、両辺に2λ61を乗じて、rλ62λ61≡0を適用すれば次式を得る。2λ61ψ6λ61R2λ612P4λ624λ61P3Pこれに31modr倍算を施せばPを得ることができる。Qは、QRPにより求めることができる。このようにスカラー倍算1回くらいの計算量で分解復元ができるため、情報圧縮してデータを送信することの効率化を図ることができる。上述したように、4次の場合には、21倍算が、3次及び6次の場合は、31倍算が必要となる。これらのスカラー倍算は通常のスカラー倍算よりも効率よく求めることができる。<21倍算>まず、rλ421に注意すれば、21modrは、次式で求めることができる。ここで、λ4が偶整数であることに注意する。2122λ41すなわち、有理点Tに対する21倍算は、以下のようになる。21Tλ41Tψ4Tすなわち、実質的には、λ42程度の計算量で求められ、これはrのビットサイズの約半分なので計算コストは通常のスカラー倍算の半分になる。<31倍算>3次の場合の31倍算は、rλ32λ31に注意すれば以下のように求まる。313333λ3231ただしこの場合、λ31は、3の倍数であることが条件である。すなわち、有理点Tに対する31倍算は、以下のようになる。31Tλ3231Tψ33TTすなわち、実質的には、λ323程度の計算量で求められ、これはrのビットサイズの約半分なので計算コストは通常のスカラー倍算の半分になる。6次の場合の31倍算は、rλ62λ61に注意すれば以下のように求まる。313333λ6231ただしこの場合、λ61は、3の倍数であることが条件である。すなわち、有理点Tに対する31倍算は、以下のようになる。31Tλ6231Tψ63TTすなわち、実質的には、λ623程度の計算量で求められ、これはrのビットサイズの約半分なので計算コストは通常のスカラー倍算の半分になる。以下において、本発明の実施形態について、図を用いて説明する。図1は、本発明の実施形態にかかる有理点情報圧縮装置の概略模式図である。図2は、本発明の実施形態にかかるクライアント装置上の有理点情報圧縮装置100の全体構成を例示したブロック図である。図3は、本発明の実施形態にかかる認証サーバ上の有理点情報圧縮装置200の全体構成を例示したブロック図である。まず、図1、図2、及び図3を用いてこの形態の全体について説明し、次にその詳細について説明する。なお、本実施形態では、所要の電子計算機で構成された認証サーバ及びクライアント装置によってディジタルグループ署名の認証処理を行う際に、与えられたペアリング曲線から上述した有理点部分群を特定するプログラム、及び有理点情報を復元するプログラム部分についてのみ説明する。なお、有理点部分群の特定及び有理点情報復元の演算は、認証サーバまたは、クライアント装置で実行される場合に限定されるものではなく、少なくともCPUなどの演算手段及び記憶手段を備えた装置であれば、どのような装置であってもよい。図1に示すように、認証サーバまたはクライアント装置を構成する電子計算機10は、演算処理を実行するCPU11と有理点部分群特定プログラム、有理点情報復元プログラム、ペアリング演算プログラムなどの各種プログラム、及びこれらのプログラムで使用するデータなどを記憶したハードディスクなどの記憶装置12と、これらのプログラムを展開して実行可能とするとともに、これらプログラムの実行にともなって生成されたデータを一時的に記憶するRAMなどで構成されたメモリ装置13を備えている。図1中、14はバスである。また、認証サーバを構成する電子計算機10は、インターネットなどの電気通信回線20に接続され、この電気通信回線20に接続されたクライアント装置30から送信されたディジタルグループ署名の署名データを受信可能としている。図1中、15は電子計算機10の入出力部である。図2に、クライアント装置上の有理点情報圧縮装置100を示す。図2に示すように、有理点情報圧縮装置100は、有理点部分群特定部110と、認証データ生成部120と、有理点情報圧縮部130と、入出力部140とを有する。まず、ディジタルグループ署名データ認証データを生成するクライアント装置では、与えられたペアリング曲線から有理点部分群G1、G2を特定する有理点部分群特定部110。次に、署名データを生成し認証データ生成部120、署名データを構成する有理点P∈G1及びQ∈G2のペアを楕円加算して有理点Rに圧縮する有理点情報圧縮部130。全てのペアについて圧縮した後、署名データを入出力部140より、認証サーバに向け送信する。図3に、認証サーバ上の有理点情報圧縮装置200を示す。図3に示すように、有理点情報圧縮装置200は、入出力部210と、有理点情報復元部220と、認証処理部230と、認証結果データ生成部240と、有理点情報圧縮部250と、入出力部260とを有する。認証サーバを構成する電子計算機10では、クライアント装置30からディジタルグループ署名の署名データが送信されると、入出力部210を経由して署名データを受信し、受信した署名データをメモリ装置13に一旦記憶し、有理点情報復元プログラムを起動して元の有理点のペアの情報を復元した後有理点情報復元部220、ペアリング演算プログラムを起動して、ペアリング演算を実行している。その後、認証結果のデータを生成し認証結果データ生成部240、有理点のペアの情報を圧縮し有理点情報圧縮部250、入出力部260を経由してクライアント装置に向け送信している。次に、本実施形態の詳細について図を用いて説明する。<有理点部分群の特定>図4は図1で示した装置で所定のプログラムを実行させることにより実現される有理点部分群特定部110の機能構成を例示した図である。図7は有理点部分群特定部の処理を行う有理点部分群特定プログラムのフローチャートである。電子計算機10では、起動した有理点部分群特定プログラムによって、図7に示すフローチャートに基づいて効率的な自己準同型写像を可能とする有理点部分群を特定している。すなわち、入力された、有理点群が埋め込み次数1の一般の有理点を特定の有理点部分群内の有理点に変換している。この場合電子計算機10は有理点部分群特定手段として機能する。以下では、3次の場合について説明する。ステップT1有理点入力部111では、外部から与えられ入力手段により記憶手段に記憶された一般の有理点P’を読み出している。ステップT2定数演算部112では、あらかじめレジスタ119に記憶された有限体の標数p及び合成数位数rとを用いて、式3で示したλ2λ1≡0となるλ及び、式4bで示したε3≡1となるεを演算し設定している。ステップT3自己準同型写像演算部113では、式4bのψ:→として、P’のx座標値xをε倍し、ψを求めている。ステップT4有理点演算部114では、式6のPψP’を計算している。ステップT5判定部115では、POかどうかを判定している。POの場合は、2つの部分群を特定できないのでエラーリターンしている発生確率は、122000程度である。。ステップT6では、式7のQψP’を計算している。ステップT7では、QO無限遠点かどうかを判定している。QOの場合は2つの部分群を特定できないのでエラーリターンしている発生確率は、122000程度である。。ステップT8では、P、Qを記憶手段に記憶している。Pの集合が有理点部分群G1となり、Qの集合が有理点部分群G2となる。本実施形態では、3次の場合について説明したが、4次及び6次の場合も、λ、ψ、εまたはζ、P、Qがそれぞれ4次では、式:λ21≡0、式:ψ→∈Fp、式λP’、式:QψP’となり、6次では、式:λ2λ1≡0、式:ψ→∈Fp、式:PψP’、式:QψP’となるだけであり、同様に有理点部分群を特定することができる説明は省略する。。<有理点情報の圧縮>有理点P∈G1Q∈G2の圧縮はこれらの有理点を楕円加算して有理点Rとすることにより行う。これにより、有理点のデータ長は半分となる。<有理点情報の復元>図5は図1で示した装置で所定のプログラムを実行させることにより実現される有理点情報復元部220の機能構成を例示した図である。図6は有理点情報復元部の処理を行う有理点復元プログラムのフローチャートである4次の場合。電子計算機10では、起動した有理点復元プログラムによって、図6に示すフローチャートに基づいて有理点Rから有理点PQを求めている。この場合電子計算機10は第2演算手段として機能する。以下では、4次の場合について説明する。まず、有理点Rを入力し、メモリ手段13に記憶する。ステップS1、パラメータ入力部221次に、T1λ4ψ4λ4Rを計算する。ステップS2、レジスタ229、定数演算部222、自己準同型写像演算部224次に、P21T1を計算する。次に、QRPを計算する。21倍算は、具体的には、以下のアルゴリズムを実行している。[表1]4次の場合の21倍算アルゴリズム入力:λ4、T1∈G1出力:21T11T←λ42T12T←ψ4T13ReturnTすなわち、ステップ1では、有理点T1のλ42倍算を実行し、Tに代入している。ステップ2では、ステップ1で求めたTの自己準同型写像ψ4を実行し、有理点T1を加算してTに代入している。ステップ3では戻り値をTとしてリターンしている。4次の場合の有理点の復元は、具体的には、以下のアルゴリズムを実行している。[表2]4次の場合有理点復元アルゴリズム入力:λ4、RPQP∈G1Q∈G2出力:PQ1T1←ψ42T1←λ4T1R3P←21T14Q←RP5ReturnPQすなわち、ステップ1では、有理点Rの自己準同型写像ψ4を実行し、T1に代入している。ステップ2では、有理点T1のλ4倍算を実行し、次にRを楕円加算してT1に代入している。ステップ3では、[表1]のアルゴリズムを実行し、符号をマイナスにしてPを求めている。ステップ4では、RとPを楕円加算してQを求めている。ステップ5では、PQを戻り値としてリターンしている。次に3次の場合について説明する。3次の場合の31倍算は、具体的には、以下のアルゴリズムを実行している。[表3]3次の場合の31倍算アルゴリズム入力:λ3、T1∈G1出力:31T11T←23T12T←ψ3T13ReturnTすなわち、ステップ1では、有理点T1の23倍算を実行し、Tに代入している。ステップ2では、ステップ1で求めたTの自己準同型写像ψ3を実行し、有理点T1を加算してTに代入している。ステップ3では戻り値をTとしてリターンしている。3次の場合の有理点の復元は、具体的には、以下のアルゴリズムを実行している。[表4]3次の場合有理点復元アルゴリズム入力:λ3、RPQP∈G1Q∈G2出力:PQ1T1←ψ32T2←2T1R3T2←λ3T24T1←T2T1R5P←31T16Q←RP7ReturnPQすなわち、ステップ1では、有理点Rの自己準同型写像ψ3を行い、T1に代入している。ステップ2では、有理点T1の2倍算を実行し、次にRを楕円加算してT2に代入している。ステップ3では、有理点T2のλ3倍算を行いT2に代入している。ステップ4では、T2T1Rを楕円加算してT1に代入している。ステップ5では、[表3]のアルゴリズムを実行し、符号をマイナスにしてPを求めている。ステップ6では、RとPを楕円加算してQを求めている。ステップ7では、PQを戻り値としてリターンしている。次に6次の場合について説明する。6次の場合の31倍算は、具体的には、以下のアルゴリズムを実行している。[表5]6次の場合の31倍算アルゴリズム入力:λ6、T1∈G1出力:31T11T←23T12T←ψ6T13ReturnTすなわち、ステップ1では、有理点T1の23倍算を実行し、Tに代入している。ステップ2では、ステップ1で求めたTの自己準同型写像ψ6を実行し、有理点T1を加算してTに代入している。ステップ3では戻り値をTとしてリターンしている。6次の場合の有理点の復元は、具体的には、以下のアルゴリズムを実行している。[表6]6次の場合の有理点復元アルゴリズム入力:λ6、RPQP∈G1Q∈G2出力:PQ1T1←ψ62T2←2T1R3T2←λ6T24T1←T2T1R5P←31T16Q←RP7ReturnPQすなわち、ステップ1では、有理点Rの自己準同型写像ψ6を実行し、T1に代入している。ステップ2では、有理点T1の2倍算を実行し、次にRを楕円加算してT2に代入している。ステップ3では、有理点T2のλ6倍算を行いT2に代入している。ステップ4では、T2T1Rを楕円加算してT1に代入している。ステップ5では、[表5]のアルゴリズムを実行し、符号をマイナスにしてPを求めている。ステップ6では、RとPを楕円加算してQを求めている。ステップ7では、PQを戻り値としてリターンしている。"