(57)【特許請求の範囲】
【請求項１】
楕円曲線または代数曲線上の点Ｐがその曲線上のある特定の部分群上にあるか否かを判定する装置において、
上記Ｐに対するフロベニウス写像φの多項式をｆ（φ）とすると、ｆ（φ）を上記曲線の位数＃Ｅの剰余値として求めることができ、その剰余値が上記曲線の上記部分群の位数ｋの倍数であり、かつｆ（φ）／ｋと＃Ｅ／ｋとが互いに素であって、
上記Ｐのφi 倍（ｉ＝０，…,ｍ−１）（ｍは拡大次数）を演算するφ倍演算手段と、楕円又は代数加算手段とを用いてｆ（φ）Ｐを演算するｆ（φ）Ｐ演算手段と、
上記ｆ（φ）Ｐの演算結果が入力され、それが単位元であるか否か判定して、上記Ｐが上記部分群上にあるか否かを出力する判定手段と、
を具備し、
上記ｆ（φ）はΣi=0m-1φi である、
ことを特徴とする曲線上の有理点群の部分群上元判定装置。
【請求項２】
楕円曲線または代数曲線上の点Ｐがその曲線上のある特定の部分群上にあるか否かを判定する装置において、
上記Ｐに対するフロベニウス写像φの多項式をｆ（φ）とすると、ｆ（φ）を上記曲線の位数＃Ｅの剰余値として求めることができ、その剰余値が上記曲線の上記部分群の位数ｋの倍数であり、かつｆ（φ）／ｋと＃Ｅ／ｋとが互いに素であって、
上記Ｐのφi 倍（ｉ＝０，…,ｍ−１）（ｍは拡大次数）を演算するφ倍演算手段と、楕円又は代数加算手段とを用いて、ｆ1(φ）Ｐとｆ2(φ）Ｐの加算値がｆ（φ）Ｐとなる値ｆ1(φ）Ｐとｆ2(φ）Ｐを求めるｆ（φ）Ｐ演算手段と、
上記ｆ1(φ）Ｐとｆ2(φ）Ｐとが逆元であるか否か判定して上記Ｐが上記部分群上にあるか否かを出力する判定手段と、
を具備し、
上記ｆ（φ）はΣi=0m-1φi である、
ことを特徴とする曲線上の有理点群の部分群上元判定装置。
【請求項３】
上記ｆ（φ）Ｐ演算手段は上記φ倍演算手段によりＰに対しφ倍し、その結果に対しφ倍することを繰返す手段と、その各φ倍演算の繰返しごとにその演算結果と前回の曲線加算結果との加算を上記加算手段を用いて行う手段を含むことを特徴とする請求項１又は２記載の曲線上の有理点群の部分群上元判定装置。
【請求項４】
上記φ倍演算手段は上記ｉの値を異にする複数のφ倍演算部を備え、上記加算手段はこれら複数のφ倍演算部の各演算結果を、２個ずつ加算する複数の加算部と、これら加算部の加算結果を更に２個ずつ加算する加算部と、のように順次加算結果の数を減少させる複数の加算手段を備えることを特徴とする請求項１又は２記載の曲線上の有理点群の部分群上元判定装置。
【請求項５】
上記ｆ（φ）Ｐ演算手段は、上記φ倍演算手段によるφuＰj（ただしu＝２j） を演算する第１手段と、上記加算手段によりＰj とφuＰjを加算して加算結果Ｐj+1 を求める第２手段と、上記加算結果Ｐj+1 をＰj として上記第１手段及び上記第２手段を少くとも１回繰返す第３手段とを含むことを特徴とする請求項１又は２記載の曲線上の有理点群の部分群上元判定装置。
【請求項６】
楕円曲線または代数曲線上の点Ｐに対するフロベニウス写像φの多項式をｆ（φ）とすると、ｆ（φ）を上記曲線の位数＃Ｅの剰余値として求めることができ、その剰余値が上記曲線上のある特定の部分群の位数ｋの倍数であり、かつｆ（φ）／ｋと＃Ｅ／ｋとが互いに素であるとし、上記ｆ（φ）がΣi=0m-1φi であるとし、
上記Ｐ点が上記曲線上の上記部分群上にあるか否かを判定するコンピュータを、
上記Ｐのφi 倍（ｉ＝０，…,ｍ−１）（ｍは拡大次数）を演算するφ倍演算手段と、楕円又は代数加算手段とを用いてｆ（φ）Ｐを演算するｆ（φ）Ｐ演算手段、
上記ｆ（φ）Ｐの演算結果が入力され、それが単位元であるか否か判定して、上記Ｐが上記部分群上にあるか否かを出力する判定手段
として機能させるための曲線上の有理点群の部分群上元判定プログラム。
【請求項７】
楕円曲線または代数曲線上の点Ｐに対するフロベニウス写像φの多項式をｆ（φ）とすると、ｆ（φ）を上記曲線の位数＃Ｅの剰余値として求めることができ、その剰余値が上記曲線上のある特定の部分群の位数ｋの倍数であり、かつｆ（φ）／ｋと＃Ｅ／ｋとが互いに素であるとし、上記ｆ（φ）がΣi=0m-1φi であるとし、
上記Ｐ点が上記曲線上の上記部分群上にあるか否かを判定するコンピュータを、
上記Ｐのφi 倍（ｉ＝０，…,ｍ−１）（ｍは拡大次数）を演算するφ倍演算手段と、楕円又は代数加算手段とを用いて、ｆ1(φ）Ｐとｆ2(φ）Ｐの加算値がｆ（φ）Ｐとなる値ｆ1(φ）Ｐとｆ2(φ）Ｐを求めるｆ（φ）Ｐ演算手段、
上記ｆ1(φ）Ｐとｆ2(φ）Ｐとが逆元であるか否か判定して上記Ｐが上記部分群上にあるか否かを出力する判定手段、
として機能させるための曲線上の有理点群の部分群上元判定プログラム。
【請求項８】
上記ｆ（φ）Ｐ演算手段は上記φ倍演算手段によりＰに対しφ倍し、その結果に対しφ倍することを繰返す手段と、その各φ倍演算の繰返しごとにその演算結果と前回の曲線加算結果との加算を上記加算手段を用いて行う手段を含むことを特徴とする請求項６又は７記載の曲線上の有理点群の部分群上元判定プログラム。
【請求項９】
上記φ倍演算手段は上記ｉの値を異にする複数のφ倍演算部を備え、上記加算手段はこれら複数のφ倍演算部の各演算結果を、２個ずつ加算する複数の加算部と、これら加算部の加算結果を更に２個ずつ加算する加算部とのように順次加算結果の数を減少させる複数の加算手段を備えることを特徴とする請求項６又は７記載の曲線上の有理点群の部分群上元判定プログラム。
【請求項１０】
上記ｆ（φ）Ｐ演算手段は、上記φ倍演算手段によるφuＰj（ただしu＝２j） を演算する第１手段と、上記加算手段によりＰj とφuＰjを加算して加算結果Ｐj+1 を求める第２手段と、上記加算結果Ｐj+1 をＰj として上記第１手段及び上記第２手段を少くとも１回繰返す第３手段とを含むことを特徴とする請求項６又は７記載の曲線上の有理点群の部分群上元判定プログラム。
【請求項１１】
請求項６乃至１０の何れかに記載のプログラムを記録したコンピュータ読み出し可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、情報セキュリティの分野に用いられ、楕円曲線あるいは代数曲線上の点が、その曲線上のある特定の部分群に属するか否かを判定する装置、そのプログラム及びその記録媒体に関する。
【０００２】
【従来の技術】
楕円曲線あるいは代数曲線を用いた公開鍵暗号やデジタル署名では、外部から入力される楕円曲線あるいは代数曲線上の点が、システムの想定している群上に存在しているかどうか検査しなければならない。特に、電子投票や電子入札等の情報セキュリティ技術を用いるアプリケーション（応用技術）の場合はこの事が重要である。従来前記検査を行う為には、例えば、楕円曲線のａｆｆｉｎｅ座標の場合なら先ず入力の点Ｐ＝（ｘ，ｙ）がシステムが想定する楕円曲線、例えばｙ2 ＝ｘ3 ＋ａｘ＋ｂを満たすかどうかを検査する。さらに、システムが想定する群が楕円曲線上の有理点群の部分群であるような場合は、部分群の位数ｋを用いて楕円スカラー倍演算ｋＰを行い、その値が無限遠点（単位元）となるか否かによって、システムが想定する部分群上の点であるか否かの判定を行っていた。
【０００３】
【発明が解決しようとする課題】
従来の技術では、前述したようにシステムが想定する部分群上の元であるか否かの検査は楕円スカラー倍演算あるいは代数曲線上の点のスカラー倍演算を用いて行われていた。例えば１６０ｂｉｔの楕円曲線上でバイナリ法を用いて楕円スカラー倍演算を行う為には、およそ８０回の楕円加算と１６０回の楕円２倍算が必要である。この部分の演算コスト（楕円加算及び楕円２倍算合わせておよそ２４０回）が高いという問題点があった。
【０００４】
【課題を解決するための手段】
この発明によれば、入力点Ｐに対するフロベニウス写像φの多項式ｆ（φ）を用いる。このｆ（φ）はその楕円曲線あるいは代数曲線の位数＃Ｅの剰余値として求めることができるものであり、かつその剰余値が上記曲線の部分群の位数ｋの倍数であり、またｆ（φ）／ｋと＃Ｅ／ｋとが互いに素である。
この発明においてはＰのφi 倍（ｉ＝０，…,ｍ−１）（ｍは拡大次数）を演算するφ倍演算手段と、楕円又は代数加算手段とを用いてｆ（φ）Ｐがｆ（φ）Ｐ演算手段で演算され、そのｆ（φ）Ｐの演算結果が単位元であるか否かが判定手段により判定され、単位元であれば入力点Ｐは部分群上の元であるとされる。あるいは上記ｆ（φ）Ｐ演算手段の最後の曲線加算における各値ｆ1(φ）Ｐとｆ2(φ）Ｐとが逆元であるか否かが判定手段により判定され、逆元であれば入力点Ｐは部分群上の元であるとされる。
【０００５】
以下にこの発明の原理を説明する。
楕円曲線とフロベニウス写像
有限体ＧＦ（ｑ）上で定義された楕円曲線をＥ／ＧＦ（ｑ）と表記する。Ｅ／ＧＦ（ｑ）上のｍ次拡大体ＧＦ（ｑm）有理点の集合Ｅ（ＧＦ（ｑm））に対して、以下のようなフロベニウス写像φを用いた演算を定義できる。Ｐ＝（ｘ，ｙ）,ｘ，ｙ∈ＧＦ（ｑm）に対する自己準同型写像
φ：（ｘ，ｙ）→（ｘq ，ｙq）
をフロベニウス写像と呼ぶ。φＰ＝（ｘq ，ｙq）である。フロベニウス写像φは、楕円曲線上の自己準同型写像であり、一般に楕円加算などと比べて少ない演算コストで実行できる。写像φのφi は上記フロベニウス写像φをｉ回（ｉは整数）適用する演算で、
φi ：（ｘ，ｙ）→（ｘv ，ｙv)  ただしv＝ｑi
である。φi Ｐ＝（ｘv ，ｙv)である。一見写像φi の演算コストはφの演算コストのｉ倍のように思えるが、通常、このｉ回分の計算をまとめて行うことが可能で、φi の演算コストをφの演算コストと等しくすることが可能である。従ってφi も一般に楕円加算などと比べて少ない演算コストで実行できる。
フロベニウス写像を使った判定
ｐを素数とする。有限体ＧＦ（ｑ）上に定義された楕円曲線Ｅ／ＧＦ（ｑ）上のＧＦ（ｑm）有理点Ｐに対してＰが、Ｅ／ＧＦ（ｑ）上のＧＦ（ｑm）有理点群の部分群上にあることが、フロベニウス写像の小係数の多項式ｆ（φ）で表現できることがある。例えば一般にＰがＥ／ＧＦ（ｑ）上のＧＦ（ｑm）有理点群の部分群である、ＧＦ（ｑ）有理点であることを示す方程式は、ΟをＥ／ＧＦ（ｑ）上のＧＦ（ｑm）有理点群の単位元とすると、
（φ−１）Ｐ＝Ο                （１）
であり、対応するフロベニウス写像の小係数の多項式ｆ（φ）は、φ−１である。どのようなφの多項式ｆ（φ）がどのような部分群に相当するかは一般にはＥ／ＧＦ（ｑ）上のＧＦ（ｑm）有理点群の性質に依存している。一度楕円上の点であることが確認された点Ｐに対して、多項式φm −１はＥ／ＧＦ（ｑ）上のＧＦ（ｑm）有理点群そのものを表しており、ＧＦ（ｑm）有理点群の位数＃Ｅの因数を法としたφm −１の因数分解から部分群に相当するφの多項式を決定できることがある。例えばｐ＝２14−３，ｍ＝１３の時、楕円曲線Ｅ／ＧＦ（ｑ）をｙ2 ＝ｘ3 −３ｘ−１７２とすると、Ｅ／ＧＦ（ｑ）のＧＦ（ｑm）有理点群の位数は
＃Ｅ＝6115406551204556260470903011864106707649384284127512766
となるが、このＧＦ（ｑm）有理点群の部分群で、その位数ｋが
ｋ＝377354470640784663733858016281877496461149221530761
である部分群の元であることを表現するフロベニウス写像の小係数の多項式ｆ（φ）は、φm −１の因数分解
φm −１＝（φ−１）Σi=0m-1φi               （２）
から、ｆ（φ）＝Σi=0m-1φi である。即ちあるＥ／ＧＦ（ｑ）のＧＦ（ｑm）有理点群の元Ｐが、ＧＦ（ｑm）有理点群の部分群上にあるか否かを判定するには、従来は部分群の位数ｋによりｋＰを計算し、その結果が単位元Οとなるか否かで判定していたが、この発明の一例ではΣi=0m-1φi Ｐを計算し、その結果が単位元Οとなるか否かで判定する。つまり、ＧＦ（ｑ）有理点の位数は＃Ｅ／ｋであるが、φ−１≡＃Ｅ／ｋであり、φm −１≡＃Ｅであるから（２）より、ｋ≡Σi=0m-1φi とできる。従ってΣi=0m-1φi ＰがＧＦ（ｑm）有理点群の部分群の単位元（ゼロ）になれば、ＰがＧＦ（ｑm）有理点群の部分群上にあることになる。
【０００６】
このようにして、演算コストを削減しつつ従来法と同等の効果を得る。つまりｋが素数でなければ、式（２）中のΣi=0m-1φi は更に因数分解できることになる。従ってＧＦ（ｑ）有理点群の位数でＧＦ（ｑm）有理点群の位数＃Ｅを割った値ｋが素数であれば式（２）のように多項式ｆ（φ）を表現することができる。
一般には楕円曲線Ｅ／ＧＦ（ｑ）上のＧＦ（ｑm）有理点群の位数＃Ｅの剰余値としてｆ（φ）を求めることができ、その値がＧＦ（ｑm）有理点群の部分群の位数ｋの倍数であり、かつｆ（φ）／ｋと＃Ｅ／ｋとが互いに素であれば、ｆ（φ）Ｐを演算し、その結果がＧＦ（ｑm）有理点群の単位元（無限遠）であれば入力点ＰはＧＦ（ｑm）有理点群の部分群の元であることになる。このようなｆ（φ）は前述のように前記条件のもとに、因数分解により求めることもできるが、ｆ（φ）は小係数の多項式であるから、例えば総当り式に、各種のｆ（φ）を作り、前記一般的な条件を満すか否かを調べて、ｆ（φ）を求めてもよい。何れにしてもｍ，ｑが与えられ、それに対応したｆ（φ）が求められており、ｆ（φ）Ｐを演算することによりＰがＧＦ（ｑm）有理点群の部分群の単位元Οであれば、Ｐは前記部分群の元に属するものである。
【０００７】
なおこの発明において、要求に応じてハードウェア規模を小さくしたり、演算速度を高速にしたりする、つまり演算を有利にするために用いられる手法を以下に述べる。
楕円加算の実行順序の変更
楕円曲線上の有理点群は群であるゆえ結合律が成立する。即ち一般に楕円曲線上の有理点群の３つの元Ｐ，Ｑ，Ｒに対して
（Ｐ＋Ｑ）＋Ｒ＝Ｐ＋（Ｑ＋Ｒ）
が成立する。また、楕円曲線上の有理点群は可換群である。即ち一般に楕円曲線上の有理点群の２つの元Ｐ，Ｑに対して
Ｐ＋Ｑ＝Ｑ＋Ｐ
が成立する。これらの性質を用いて、複数の楕円加算の実行順序を演算に有利なように、つまり要求に応じてハードウェア規模を小さくするとか、演算速度を速くするように変更することが出来ることがある。
写像φの分配則
上記フロベニウス写像φには分配則がある。分配則とは、Ｅ／ＧＦ（ｑ）上の２つのＧＦ（ｑm）有理点Ｑ，Ｒに対して写像φが次の性質を持つ事を云う。
【０００８】
φ（Ｑ＋Ｒ）＝φＱ＋φＲ
この事を利用して、楕円曲線上の有理点群の部分群上元の判定の演算コストを削減出来ることがある。例えば上記の例ではΣi=0m-1φi Ｐを計算する場合に、この計算の途中に
Ｐ1 ＝Ｐ＋φＰ
なる、楕円加算を実行したとする。計算の途中結果のＰ1 に関して、φ2 Ｐ1 なる値は、分配則を用いれば
φ2 Ｐ1 ＝φ2 Ｐ＋φ3 Ｐ
である。従って、
Ｐ1 ＋φ2 Ｐ1 ＝Ｐ＋φＰ＋φ2 Ｐ＋φ3 Ｐ
が成立する。右辺を計算する手続きは楕円加算を３回必要とするように思えるが、この方法を用いればＰ1 を計算する際とＰ1 ＋φ2 Ｐ1 を計算する際との２回のみ楕円加算を用いれば良い。またこの方法は再帰的に適用可能である。即ち、Ｐ2 ＝Ｐ1 ＋φ2 Ｐ1 
とするならば、追加の１回の楕円加算で
Ｐ2 ＋φ4 Ｐ2 ＝Σi=07φi Ｐ
を計算できる。右辺の計算は楕円加算７回に見えるが、この方法を用いれば楕円加算は３回で済む。一般に拡大次数ｍに対してｍ−１回の楕円加算が必要であったものをこの方法を再帰的に用いれば、およそｌｏｇ2ｍ回の楕円加算で済ますことが出来る。
【０００９】
【発明の実施の形態】
基本構成
図１にこの発明装置の実施形態の基本機能構成を示す。楕円曲線Ｅ／ＧＦ（ｑ）上のＧＦ（ｑm）有理点であることが確認された入力点Ｐが入力手段１２より入力されると、ｆ（φ）Ｐ演算手段１３は、Ｐをφi(ｉ＝０，…,ｍ−１)倍するφ倍演算手段１４と、二つの値を楕円加算する楕円加算手段１５と、必要に応じてφi 倍演算結果に対して係数を乗算する係数乗算手段１６とを備え、フロベニウス写像の多項式ｆ（φ）とＰの乗算を計算する。その計算結果は判定手段１７においてＧＦ（ｑm）有理点群の部分群（位数ｋ）の単位元であるか否かの判定が行われ、単位元であれば、入力点Ｐは前記部分群の元であることを示す情報（真）を出力手段１８から出力し、単位元でなければ偽を示す情報を出力する。
【００１０】
ｆ（φ）Ｐ演算手段１３はその最終結果が得られる直前の楕円加算ｆ1(φ）Ｐとｆ2(φ）Ｐ＝ｆ（φ）Ｐに用いるｆ1(φ）Ｐとｆ2(φ）Ｐが得られると、これらを判定手段１７へ出力し、判定手段１７はこれらｆ1(φ）Ｐとｆ2(φ）Ｐとが逆元つまりｆ2(φ）Ｐ＝−ｆ1(φ）Ｐであるか否かを判定し、逆元であれば真を出力手段１８から出力し、逆元でなければ偽を出力するようにしてもよい。なお楕円演算においてはＡ＋Ａの加算は、通常２倍演算、２Ａにより求めるが、楕円加算手段１５としてはこの２倍演算による加算も含むものとする。
【００１１】
次にｍ＝１３、ｆ（φ）＝Σi=0m-1φi の場合の具体的構成例のいくつかを説明する。
第１実施例（図２参照）
入力をφ倍演算するφ倍器２１−1，…,２１−１２が直列に接続されて、φ倍演算手段１４が構成される。つまりφ倍器はｍ−１個設けられる。また楕円加算器２２−１，…,２２−１２が設けられ、その各楕円加算器２２−ｉ（ｉ＝１，…,１２）の一方の入力として、φ倍器２１−ｉのφ倍演算結果が入力され、他方の入力として、直前の楕円加算器２１−ｉ−１の加算結果が入力される。ただし楕円加算器２２−１の他方の入力はＰとされる。これら楕円加算器２２−１，…,２２−１２により楕円加算手段１５が構成される。
【００１２】
最終段の楕円加算器２２−１２の加算結果が単位元判定器２３で位数ｋの部分群の単位元であるか否かの判定が行われる。あるいはφ倍器２１−１２の演算結果と楕円加算器２２−１１の演算結果が逆元判定器２４に入力されて、これら演算結果が互いに逆元であるか否か判定される。
図２に示した演算はソフトウェアで処理すると、ハードウェアの規模を著しく小さくすることができる。この場合の機能構成を図３に示す。入力手段１２、φ倍演算手段１４、楕円加算手段１５、判定手段１７、記憶手段１９が制御手段１１に接続される。記憶手段１９にはｑ，ｍが格納されてあり、またφ倍演算結果Ｑが格納される。φ倍記憶部１９ａ、楕円加算結果Ｒが格納される加算記憶部１９ｂが設けられている。制御手段１１はこの楕円曲線上の有理点群の部分群上元判定プログラムをＣＰＵ（マイクロプロセッサ）により実行するものであり、実際にはφ倍記憶部１９ａ、加算記憶部１９ｂは制御手段１１内のレジスタが用いられることもあり、また、φ倍演算手段１４、楕円加算手段１５、判定手段１７は制御手段１１における演算機能により実行される。
【００１３】
この場合の処理手順の例を図４を参照して説明する。入力点Ｐが入力されると（Ｓ１）、Ｐをφ倍記憶部１９ａにＱとして、また加算記憶部１９ｂにＲとしてそれぞれ記憶する（Ｓ２）。記憶手段１９にパラメータｉを１として格納する（Ｓ３）。記憶部１９ａの記憶値Ｑをφ倍して記憶部１９ａのＱを更新する（Ｓ４）、そのＱをφ倍した値と記憶部１９ｂの記憶値Ｒとを楕円加算して記憶部１９ｂのＲを更新する（Ｓ５）。
ｉがｍ−１となったかを調べ（Ｓ６）、ｉ＝ｍ−１でなければｉを＋１してステップＳ４に戻り（Ｓ７）、ステップＳ６でｉ＝ｍ−１となれば、ステップＳ５の演算結果が単位元か否かの判定を行って出力する（Ｓ８）。
【００１４】
なお、図中に破線で示すようにステップＳ４の後ｉ＝ｍ−１か否かの判定を行いｉ＝ｍ−１でなければステップＳ５に移り、ｉ＝ｍ−１であればステップＳ４の演算結果φＱと、記憶部１９ｂのＲとが互いに逆元であるか否かの判定を行って出力してもよい。この場合はステップＳ５の後、直ちにステップＳ７に移る。
第２実施例（図５参照）
図５にハードウェア規模は大きくなるが、演算速度を速くする例を示す。φ倍演算手段１４としてｍ−１＝１２個のφi 倍器３１−ｉ（ｉ＝１，…,ｍ−１）が設けられ、これら各φi 倍器３１−ｉにＰが入力される。
【００１５】
これらφi 倍器３１−ｉの演算結果φi ＰとＰから２個づつ組合せてそれぞれ組合せた２つの演算結果を楕円加算器３２−１，…,３２−６で楕円加算する。更にこれら楕円加算器３２−１，…,３２−６の加算結果と、第１段目楕円加算の組合せで残った演算結果とを含めて、これらから２個ずつ組合せて、それぞれ組合せた２つの演算結果を楕円加算器３３−１，…，３３−３で楕円加算する。更にこれら楕円加算結果と、これらまでの組合せで残った演算結果とを含めて、楕円加算器３４−１，３４−２で楕円加算し、これら両楕円加算結果を楕円加算器３５−１で楕円加算し、その加算結果を単位元判定器２３へ入力する。あるいは楕円加算器３４−１，３４−２の各加算結果を逆元判定器２４へ入力する。
【００１６】
単位元判定器２３を用いる場合は図中の全ての楕円加算器で楕円加算手段１５が構成され、逆元判定器２４を用いる場合は図中の楕円加算器３５−１を除く全ての楕円加算器で楕円加算手段１５が構成される。
図示例では各楕円加算はその前段の演算器における配列順は２つずつを組合せ、第１段目の楕円加算ではφ12Ｐ演算結果が組合せから残り、第２段目の楕円加算もφ12Ｐ演算結果が残り、第３段目の楕円加算において、前段の楕円加算で残った楕円加算器３３−３の演算結果とそれまでに残っていた演算結果φ12Ｐとが楕円加算器３４−２で加算される。しかし、何れの楕円加算段においても、その前段の演算結果とそれまでに残っている演算結果とを合せて、任意の２つずつを組合せて楕円加算をしてもよい。
【００１７】
この例では１回のφi 倍並列演算と、５回の並列楕円演算との６回の演算でΣi=012φi Ｐの演算を行うことができ、高速に処理することができる。なお個々の演算の回数は図２に示した第１実施例と同数、つまりφ倍演算の回数、楕円加算の回数はそれぞれ各１２ずつである。
図５に示した手法も、複数の演算を並列に処理できるＣＰＵ（マイクロプロセッサ）を用いればコンピュータにより実行させることもできる。この場合は例えば図６に示すように、Ｐが入力されると（Ｓ１）Ｐをそれぞれφ0 ，…,φm-1 倍する並列演算を行い、これらの演算結果を記憶部に格納し（Ｓ２）、次に前段の演算結果に組合せて残った演算結果を含め、これらから２つを組合せて、その各組合せた２つの演算結果の楕円加算を並列に行い、これら加算結果を記憶部に格納する（Ｓ３）。残りの演算結果が１個になったかを調べ（Ｓ４）、１個でなければステップＳ３に戻り、１個であればその残った演算結果が単位元であるかの判定を行う（Ｓ５）。逆元判定を用いる場合は、図中破線で示すようにステップＳ３の結果、残った演算結果が２つであるかを調べ、２つ以上であればステップＳ３に戻り、２つであれば逆元判定を行う。
第３実施例
フロベニウス写像φの分配則を用いて演算コストを一層削減する実施例を図７に示す。入力点Ｐはφ倍器４１でφ倍とされ、この結果φＰとＰとが楕円加算器４２で加算され、その加算結果Ｐ1 ＝Ｐ＋φＰがφ2 倍器４３でφ2 倍され、その結果φ2 Ｐ1 とＰ1 とが楕円加算器４４で楕円加算される。この加算結果Ｐ2 ＝Ｐ1 ＋φ2 Ｐ1 がφ4 倍器４５でφ4 倍され、その結果φ4 Ｐ2 とＰ2 とが楕円加算器４６で楕円加算される。この場合は楕円加算器４４の加算結果Ｐ2 がφ8 倍器４７でφ8 倍され、また入力点Ｐがφ12倍器４８でφ12倍され、これらの演算結果φ8 Ｐ2 とφ12Ｐが楕円加算器４９で楕円加算される。楕円加算器４６及び４９の各楕円加算結果が楕円加算器５１で楕円加算され、単位元判定器２３に入力される。逆元判定を用いる場合は楕円加算器４６及び４９の各加算結果が逆元判定器２４へ入力される。
【００１８】
この場合はφ倍演算が５回、楕円加算が５回となり、図２及び図５に各々示した場合の各１２回ずつと比較して計算数が削減される。従って図８に示すようにＰj(ｊ＝０，１，２，…)をφu （ただしu＝２j）倍し（Ｓ１）、その結果とＰj を楕円加算し、その加算結果をＰj とし（Ｓ２）、ｊを＋１してステップＳ１に戻る（Ｓ３）。このような分配則を用いた繰返し演算を行う手段を図１中のｆ（φ）Ｐ演算手段１３内に含ませると計算コストを削減することができる。
フロベニウス写像φの多項式ｆ（φ）は一般には例えばａφ2 ＋ｂφ＋ｃのように、係数ａ，ｂが１でない。従って、ｆ（φ）がこのような係数である場合は図１及び図３に示すように係数乗算手段１６により係数を乗算する。
【００１９】
この発明は楕円曲線上の点がある特定の部分群上にあるか否かの判定のみならず、代数曲線上の点がある特定の部分群上にあるか否かの判定にも適用することができる。
また上述したようにこの発明の装置はコンピュータにプログラムを実行させて機能させることもできる。その場合、コンピュータには、この曲線との有理点群の部分群上元判定プログラムをＣＤ−ＲＯＭ、フロッピーディスク、磁気ディスクなどからインストールしたり、通信回線を通じてダウンロードして実行する。
【００２０】
【発明の効果】
以上述べたように部分群上元の判定は、例えば上記パラメータ（約１６０ｂｉｔ）において、従来法では、楕円加算及び楕円２倍算が合計約２４０回必要だったが、第一及び第二の実施例に於いては合計１２回に、第三の実施例に於いては合計５回に削減されている。従って、この発明により部分群上元の判定に必要な演算コストを約１／２０〜１／４８にできる。
【図面の簡単な説明】
【図１】この発明装置の基本機能構成例を示すブロック図。
【図２】この発明の第１実施例を示すブロック図。
【図３】この発明装置の他の実施形態の機能構成を示すブロック図。
【図４】図２に示した実施例をコンピュータにより処理させる場合の手順の例を示す流れ図。
【図５】この発明の第２実施例を示すブロック図。
【図６】第２実施例をコンピュータにより処理させる場合の手順の例を示す流れ図。
【図７】この発明の第３実施例を示すブロック図。
【図８】フロベニウス写像の分配則を利用した繰返し処理の例を示す流れ図。
【図１】
0003787075.tif 000002
【図２】
0003787075.tif 000003
【図３】
0003787075.tif 000004
【図４】
0003787075.tif 000005
【図５】
0003787075.tif 000006
【図６】
0003787075.tif 000007
【図７】
0003787075.tif 000008
【図８】
0003787075.tif 000009