(57)【特許請求の範囲】
【請求項１】
有限体ＧＦ（２m ）の定義多項式ｇを選択し、該定義多項式ｇを用いて、多項式ｆをｇで除した剰余ｒを求める剰余演算装置であって、
次数ｍが与えられたとき、１次もしくは２次多項式のｈに対して、次数がｍより１次もしくは２次高く、項数が４項もしくは３項であり、かつ、ｍ次の既約因子を持つ多項式Ｇを見つけ出し、見い出した多項式Ｇと、Ｇ＝ｇｈの関係より（Ｇ，ｇ）の組みを求める選択手段と、求めた（Ｇ，ｇ）の組みを保存する手段と、
上記（Ｇ，ｇ）の組みを利用して、多項式ｆをｇで除した剰余ｒを求める演算手段とを備え、
上記選択手段は、Ｇが３項式で、ｍ＋２次の場合、ｍ＋２次の３項式Ｇが、２次多項式であるｈ＝ｘ2 ＋ｘ＋１で割り切れるかどうかをチェックし、割り切れたらｇ＝Ｇ／ｈの既約判定を行うという操作を繰り返し、（Ｇ，ｇ）の組みを求め、
Ｇが４項式でｍ＋１次の場合、１次多項式であるｈ＝ｘ＋１について、ｇ＝Ｇ／ｈの既約判定を行うことにより（Ｇ，ｇ）の組みを求め、
上記演算手段は、多項式ｆを多項式ｇで割った剰余を求めるに際し、上記選択手段により求めた（Ｇ，ｇ）の組みを利用し、下記式を用いて剰余計算を２段階に分けて行う
ｒ＝（ｆ mod  Ｇ）mod ｇ
ことを特徴とする剰余演算装置。
【請求項２】
有限体ＧＦ（２m ）の定義多項式ｇを選択し、該定義多項式ｇを用いて、多項式ｆをｇで除した剰余ｒを求める剰余演算を行う処理をコンピュータに実行させるプログラムを記録した記録媒体であって、
上記プログラムは、次数ｍが与えられたとき、１次もしくは２次多項式のｈに対して、次数がｍより１次もしくは２次高く、項数が４項もしくは３項であり、かつ、ｍ次の既約因子を持つ多項式Ｇを、Ｇが３項式で、ｍ＋２次の場合、ｍ＋２次の３項式Ｇが、２次多項式であるｈ＝ｘ2 ＋ｘ＋１で割り切れるかどうかをチェックし、割り切れたらｇ＝Ｇ／ｈの既約判定を行うという操作を繰り返し、（Ｇ，ｇ）の組みを求める処理と、
Ｇが４項式でｍ＋１次の場合、１次多項式であるｈ＝ｘ＋１について、ｇ＝Ｇ／ｈの既約判定を行うことにより（Ｇ，ｇ）の組みを求める処理と、
求めた（Ｇ，ｇ）の組みを保存する処理と、
上記（Ｇ，ｇ）の組みを利用し、下記式を用いて剰余計算を２段階に分けて行う
ｒ＝（ｆ mod  Ｇ）mod ｇ
処理をコンピュータに実行させることを特徴とするプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
近年のコンピュータセキュリティの重要性の増大に伴い、暗号技術の更なる進歩が要求されており、ポストＲＳＡ最有力候補して、同じ公開鍵暗号である楕円曲線暗号（ECC:Eliptic curve cryptosystems)が注目されている。
楕円曲線暗号は、有限体上の楕円曲線Ｅｍ：ｙ2 ＝ｘ3 ＋ａｘ＋ｂ（mod ｍ）上の整数点（ｘ．ｙ）の解集合をメッセージ空間とみなし、このメッセージ空間の２つの点を平文と暗号文とし、これら２点間の写像を暗号化と復号に対応させるものである（公開鍵暗号および楕円曲線暗号については、例えば、日経ＢＰ社、９８／７／２５発行、岡本龍明著「図解、暗号と情報セキュリティ」Ｐ４１〜Ｐ５０、Ｐ１９０等を参照されたい）。
【０００２】
上記有限体として、大きな素数ｐに対する素体ＧＦ（ｐ）および、２元体ＧＦ（２）の拡大体ＧＦ（２m ）が用いられ、楕円曲線暗号の運用においては、いずれの場合にも、有限体における四則演算を高速に行うことが、多くのデータを扱う上で重要になってくる。
本発明は、上記したＧＦ（２m ）における演算を高速に行うための剰余演算装置に関し、さらに詳細には、効率よく演算を行うことができる有限体ＧＦ（２m ）の定義多項式ｇを選択し、該定義多項式を用いて剰余演算を高速に行う剰余演算装置および該演算処理を行うプログラムを記録した記録媒体に関するものである。
【０００３】
【従来の技術】
楕円曲線暗号は、同一鍵長であれば、ＲＳＡ暗号と比較して約１０倍高速なことや、少ないメモリで動作することが確認されている。このため、近年では、ＲＳＡ暗号に代わるものとして注目されており、例えば、金融業等における電子署名等への使用が提案されている（例えば、AMERICAN NATIONAL STANDARD X9.62,Eliptic Curve Signature Algorism(ECDSA)を参照）。
上記のように次世代暗号として期待されている楕円曲線暗号は、前記したように、有限体上の楕円曲線線上で構成され、上記有限体としては、大きな素数ｐに対する素体ＧＦ（ｐ）および、２元体ＧＦ（２）の拡大体ＧＦ（２m ）が用いられる。
【０００４】
なお、前記ＧＦ（ｐ）はある数をＰでわったときの剰余の集合｛０，１，２，…Ｐ−１｝であり、したがってＧＦ（２）は、ある数を２で割った余りの集合｛０，１｝である。
また、ＧＦ（２m ）は、あらゆる次数の係数が１または０であるｘの多項式を、既約で（他の式で割り切れない）、係数が１または０であるｘのｍ次多項式ｇ（ｘ）により除したときの剰余であり、ＧＦ（２m ）は、ＧＦ（２）上の１変数ｍ次既約多項式ｇ（ｘ）によりＧＦ（２m ）＝ＧＦ（２）〔ｘ〕／（ｇ）なる剰余環として現される。
これにより、ＧＦ（２m ）の元はｆ  ｍｏｄ  ｇ（ｆをｇで除したときの余り）と表され、多項式表現とよばれる。
【０００５】
この表現において、例えばａ  ｍｏｄ  ｇとｂ  ｍｏｄ  ｇの積は、ａｂ  ｍｏｄ  ｇ（ａｂは多項式としての積）となり、ここで多項式ａｂをｇで割った剰余を求める必要が出て来る。すなわち、有限体における四則演算においては、多項式ｆを既約な多項式ｇで除したときの剰余を求める剰余演算が必要となる。
多項式をｇで割った余りを求める演算をソフトウェアで実現する場合、筆算と同様に、多項式ｆから多項式ｇをシフトしたものを引いていくあるいは、それを何桁かずつまとめて行う方法が考えられる。
【０００６】
しかし、一般にこのような方法は、多項式ｇの項数が多い場合効率が悪い。そこで、多項式ｇとしては、ｍ次で既約でさえあればよいため、なるべく項数の少ない既約の３項あるいは５項式を探し、それを多項式ｇとして用いることが提案されている。
例えば多項式ｇが３項式ｘm ＋ｘk ＋１の場合、多項式ｇによる剰余を計算することは、多項式ｆ中のｘm をｘk ＋１で置き換えることを繰り返すことにより行える。
この場合、ｍ−ｋ項分まとめて行うことで、ｍ−ｋ次次数を下げることができ、また｛ｘk ，１｝の２つの項に対してのみreduction を行えばよいので手間も少ない。
【０００７】
一方で、上記多項式ｇがｇ＝（ｘm+1 −１）／（ｘ−１）〔All One Polynominal(A0P)；全次数の係数が１の多項式〕の場合、多項式ｇには０次からｍ次までの全ての項が現れており、既に述べた一般的方法では極めて効率が悪いが、まずｘm+1 −１で剰余を計算し、残った多項式の次数がｍならば、多項式ｇを加える、すなわち全係数をビット反転するという方法で効率よく計算できる。すなわち、ｇは係数が０または１のｍ次の多項式であることから、残ったｍ次の多項式に多項式ｇを加えることにより、全係数がビット反転され、ｍ次の項の係数は０となりｍ−１次の多項式である剰余が求まる。
【０００８】
【発明が解決しようとする課題】
ところで、上記した３項式、５項式等の疎多項式を用いて剰余演算を行う方法においては、既約な３項式、５項式を探さなければならないが、３項式の場合、次数によってはかならずしも既約のものが見つかるとは限らない。この場合には５項式を用いることになるが、５項式を用いると、３項式より次数が多いため、より計算時間がかかる。
【０００９】
本発明は上記した事情に鑑みなされたものであって、その目的とするところは、上記従来技術で述べた３項式、５項式等の疎多項式による効率のよい剰余演算と、ＡＯＰに対する方法とを拡張して組み合わせ、より広い範囲の多項式による剰余演算を高速に行うことができるようにすることである。
【００１０】
【課題を解決するための手段】
図１に本発明の原理図を示す。図１（ａ）に本発明の剰余演算装置の構成を示し、１は（Ｇ，ｇ）の組を見つけ出すための選択手段、２は選択手段１で見つけ出した（Ｇ，ｇ）の組を用いて剰余を演算する演算手段である。また、図１（ｂ）（ｃ）は上記選択手段１において（Ｇ，ｇ）の組を見つけ出す処理フローの一例である。
図１に示すように、本発明においては、次のようにして剰余演算を行う。
まず、選択手段１において定義多項式を選択する。このため、前記したＡＯＰに対する方法を拡張し、定義多項式の次数ｍが与えられた場合、次数がｍより高々２以上である疎多項式Ｇ（係数が１の項数が少ない多項式）についてＧ＝ｇｈとなる（Ｇ，ｇ）の組を見つける。
【００１１】
すなわち、次数ｍが与えられたとき、１次もしくは２次多項式のｈに対して、次数がｍより１次もしくは２次高く、項数が４項もしくは３項であり、かつ、ｍ次の既約因子を持つ多項式Ｇを選択する。
例えば、Ｇが３項式で、ｍ＋２次の場合、図１（ｂ）に示すようにｍ＋２次の３項式Ｇが、２次多項式であるｈ＝ｘ2 ＋ｘ＋１で割り切れるかどうかをチェックして、割れたらｇ＝Ｇ／ｈの既約判定を行うという操作を繰り返すことにより（Ｇ，ｇ）の組みを求める。
また、Ｇが４項式でｍ＋１次の場合には、ｍ＋１次の４項式は、１次多項式ｘ＋１で常に割り切れるので、図１（ｃ）に示すようｇ＝Ｇ／ｈの既約判定を行うことにより（Ｇ，ｇ）の組みを求める。
上記（Ｇ，ｇ）の組みを用い、演算手段２において、剰余演算を次のように行う。
【００１２】
多項式ｆのｇによる剰余ｒは、ｇがある疎多項式Ｇの因子の場合、次の式により求めることができる。
ｒ＝（ｆ mod  Ｇ）mod ｇ
上記式において、Ｒ＝ｆ mod  Ｇは、多項式Ｇが疎であることを利用して効率よく求めることができ、また、Ｇ＝ｇｈにおけるｈの次数が低次であれば、剰余ｒの計算は容易となる。
【００１３】
すなわち、本発明においては、前記した（Ｇ，ｇ）の組みを見つけ出し、上記式を用いて剰余計算を２段階に分けて行い剰余演算を高速化する。
今、ｄg ＝deg(ｇ）、ｄh ＝deg(ｈ）とすると（deg(ｊ）は多項式ｊの次数）、剰余Ｒの次数deg(Ｒ）はＧ（＝ｇｈ）の次数ｄg ＋ｄh より小さいはずであるから、次のようになる。
deg(Ｒ）≦ｄg ＋ｄh −１
よって、Ｒ＝Ｑｇ＋ｒとすれば、Ｑの次数deg(Ｑ）＝deg(Ｒ）−ｄg であるから、deg(Ｑ）≦ｄh −１となる。
すなわち、ｈの次数が低次であるため、Ｑも低次となり、剰余ｒの計算は容易となる。
【００１４】
例えば、ｈの次数ｄh ＝２の場合、deg(Ｑ）≦１となるので、剰余ｒは次のように求めることができる。
▲１▼  deg （Ｒ）＜ｄg の場合、ｒ＝Ｒとなる。
▲２▼  deg （Ｒ）＝ｄg の場合、ｒ＝Ｒ＋ｇとなる。
すなわち、剰余Ｒと多項式ｇの次数が等しいので、Ｒとｇを加算すると前記ビット反転によりＲより次数が１少ない剰余ｒが求まる。
▲３▼  deg （Ｒ）＝ｄg ＋１の場合、ｒ＝Ｒ＋ｘｇ  or  Ｒ＋（ｘ＋１）ｇとなる。
すなわち、Ｒの次数がｇの次数より１多いので、ｇより次数が１大きなｘｇとＲを加算してＲより次数が１少ない剰余ｒを求めるか、あるいは、それに更にｇを加算して剰余ｒを求める。
【００１５】
【発明の実施の形態】
以下、本発明の実施の形態について説明する。
図２は本発明を実施するためのシステムの構成例を示す図であり、本発明は、同図に示すように、ＣＰＵ３１と、ＣＰＵ３１とバス３２を介して接続されたＲＯＭ３３、ＲＡＭ３４、入力／出力装置３５と、必要に応じてハードディスク装置３６等から構成されるコンピュータシステムで実現することができる。ＲＯＭ３３には、剰余演算を行うためのプログラム等が記憶され、また、ＲＡＭ３４には、演算に必要なデータやパラメータ等が格納され、ＣＰＵ３１は上記ＲＯＭ３３に格納されたプログラムを実行して本発明に係わる処理を行う。
【００１６】
図３は本発明の実施例の剰余演算装置の機能ブロック図である。同図において、１０は前記した多項式（Ｇ，ｇ）の組を選択する選択手段であり、（Ｇ，ｇ）選択手段１０は３項式選択手段１１と、４項式選択手段１２と、３項式選択手段１１もしくは４項式選択手段１２で見つけた多項式（Ｇ，ｇ）の組を保存する手段１３から構成されている。
次数ｍが与えられると、まず、３項式選択手段１１で前記した手法により３項式Ｇを探す。前記条件を満たす３項式Ｇが見つからないときは、４項式選択手段１２で前記した手法で４項式Ｇを探す（前記条件を満たす４項式は必ず存在する）。以上のようにして３項式Ｇもしくは４項式Ｇが見つかると、前記したｇ＝Ｇ／ｈの関係より多項式ｇを求め、保存手段１３に（Ｇ，ｇ）の組を保存する。
【００１７】
２０は剰余演算手段であり、剰余演算手段２０は、与えられ多項式ｆについて、ｆ／Ｇの剰余を演算する剰余Ｒ算出手段２１と、deg （Ｒ），ｄg の次数を判定する次数判定手段２２と、前記した手法で剰余ｒ算出する剰余ｒ算出手段２３から構成されている。
剰余ｒ算出手段２３は、次数判定手段２２により判定したdeg （Ｒ），ｄg の次数に基づき、剰余ｒを求める。
【００１８】
図４、図５は本実施例の３項式、４項式の選択処理を示すフローチャートである。
図４に示すように、前記３項式選択手段１１は次のようにして３項式を選択する。
ステップＳ１において、ｋを１に設定し、ステップＳ２において、２ｋ＞ｍ＋２であるかを判定する。２ｋ＞ｍ＋２になっても、多項式Ｇが見つからない場合には、３項式の探索は失敗したとして処理を終了する。
２ｋ≦ｍ＋２の場合には、ステップＳ３に行き、Ｇに（ｘm+2 ＋ｘk ＋１）を入れ、Ｇを（ｘ2 ＋ｘ＋１）で割った剰余Ｒを求める。
【００１９】
ステップＳ５でＲ≠０であるかを調べ、剰余Ｒが０でない場合には、Ｇは（ｘ2 ＋ｘ＋１）で割り切れないので、ステップＳ８に行き、ｋ＝ｋ＋１にして、ステップＳ２に戻る。
また、Ｒ≠０でない場合には、Ｇが（ｘ2 ＋ｘ＋１）で割り切れるので、ステップＳ６に行き、Ｇ／（ｘ2 ＋ｘ＋１）を演算してｇを求め、ステップＳ７においてｇが既約であるかを調べる。ｇが既約の場合には、３項式のＧが見つかったので、（Ｇ，ｇ）の組を返す。また、ｇが既約でない場合には、ステップＳ８に行き、ｋ＝ｋ＋１にして、ステップＳ２に戻る。
【００２０】
以上の処理を行うことにより３項式Ｇが見つかった場合には、（Ｇ，ｇ）の組を前記保存手段１３に保存する。また、３項式が見つからなかった場合には、前記４項式選択手段１２により次のようにして、４項式の選択処理を行う。
図５において、ステップＳ１において、ｋ１に１を設定し、ｋ２に２を設定する。ステップＳ２において、ｋ２＝ｍ＋１であるかを調べる。ｋ２がｍ＋１になると４項式の選択は失敗したものとして処理を終了する。
ｋ２＜ｍ＋１の場合には、ステップＳ３に行き、Ｇに（ｘm+1 ＋ｘk2＋ｘk1＋１）を入れ、ステップＳ４において、Ｇを（ｘ＋１）で割ってｇを求める（４項式の場合Ｇは（ｘ＋１）で必ず割り切れる）。
【００２１】
ステップＳ６において、ｇが既約であるかを調べ、ｇが既約の場合には、４項式のＧが見つかったので、（Ｇ，ｇ）の組を返す。また、ｇが既約でない場合には、ステップＳ６に行き、ｋ２＝ｋ１＋１であるかを調べ、ｋ２＝ｋ１＋１の場合には、ステップＳ７において、ｋ２＝ｋ２＋１，ｋ１＝１にしてステップＳ２に戻る。また、ｋ２＝ｋ１＋１でない場合には、ステップＳ８において、ｋ１＝ｋ１＋１にしてステップＳ２に戻る。
以上のようにして４項式のＧが求まると、（Ｇ，ｇ）の組を前記保存手段１３に保存する。
以上のようにして、予め次数ｍに対応した３項式もしくは４項式の（Ｇ，ｇ）の組を求めて保存手段１３に保存しておき、剰余演算手段２０は多項式ｆが与えられたとき、保存手段１３に保存された（Ｇ，ｇ）の組を用いて剰余演算を行う。
【００２２】
図６、図７、図８は剰余演算手段２０による演算処理を示すフローチャートである。図６、図７は３項式のＧを用いた剰余演算処理を示し、図８は４項式のＧを用いた剰余演算処理を示しており、図６〜図８により剰余演算処理について説明する。
図６において、まず、ｆ／Ｇの剰余Ｒの演算を行う。なお、この演算は、通常の多項式の除算処理である。
ステップＳ１において、Ｆに与えられた多項式ｆを入れ、Ｇに保存手段１３に保存されている３項式Ｇ（＝ｘn ＋ｘk ＋１）を入れる。ステップＳ２において、Ｆの次数ｄｅｇ（Ｆ）をｄに入れる。ステップＳ３において、ｄ＜ｎであるかを調べ、ｄ＜ｎになれば、剰余Ｒが求まったので、ステップＳ９において、ＲにＦを入れて次の次数判定処理（ステップＳ１０）に行く。
また、ｄ＜ｎでない場合には、ステップＳ４において、ｄ−ｎ＜ｎ−ｋであるかを調べる。すなわち、Ｆの次数ｄとＧの次数ｎの差が、３項式Ｇの１項目の次数ｎと２項目の次数ｋの差より小さいかを調べる。
【００２３】
ｄ−ｎ＜ｎ−ｋの場合には、ステップＳ６に行き、Ｌに３項式Ｇの１項目の次数ｎを入れる。また、ｄ−ｎ＜ｎ−ｋの場合には、ステップＳ５に行き、Ｌに、Ｆの次数ｄとＧの次数ｎの差にｋ＋１を加算したものを入れる。
ステップＳ７において、Ｆを（Ｆ１・ｘL ＋Ｆ２）（ここでｄｅｇ（Ｆ２）＜Ｌ）と分解し、ステップＳ６において、Ｆに（Ｆ２＋ｘL-n+K Ｆ１＋ｘL-n Ｆ１）を入れる。次いで、ステップＳ３に戻り、上記処理を繰り返す。
【００２４】
以上の処理を繰り返し、ｆ／Ｇの剰余Ｒが求まったら、次に図７のステップＳ１０以降の次数判定処理を行い、前記課題を解決する手段で説明したようにして剰余ｒを求める。
ステップＳ１０において、ｄｅｇ（Ｒ）が次数ｍより小さいかを調べ、小さい場合にはステップＳ１１に行き、ｒにＲを入れ（前記課題を解決する手段の▲１▼参照）、処理を終了する。
ｄｅｇ（Ｒ）が次数ｍより小さく無い場合には、ステップＳ１２に行き、ｄｅｇ（Ｒ）が次数ｍと等しいかを調べ、ｄｅｇ（Ｒ）が次数ｍに等しい場合には、ステップＳ１３に行き、ｒにＲ＋ｇを入れ（前記課題を解決する手段の▲２▼参照）、処理を終了する。
【００２５】
ｄｅｇ（Ｒ）が次数ｍに等しくない場合には、ステップＳ１４に行き、剰余Ｒのｍ次項がｇのｍ−１次項と等しいかを調べる。剰余Ｒのｍ次項がｇのｍ−１次項と等しい場合には、ステップＳ１６に行き、ｒにＲ＋ｘｇを入れて処理を終了する。また、剰余Ｒのｍ次項がｇのｍ−１次項と等しくない場合には、ステップＳ１５に行き、ｒにＲ＋ｘｇ＋ｇを入れて処理を終了する（前記課題を解決する手段の▲３▼参照）。
【００２６】
次に図８により、４項式の剰余演算処理について説明する。
まず、ｆ／Ｇの剰余Ｒの演算を行う。なお、この演算は、前記３項式の場合と同様、通常の多項式の除算処理である。
ステップＳ１において、Ｆに与えられた多項式ｆを入れ、Ｇに保存手段１３に保存されている４項式Ｇ（＝ｘn ＋ｘk2＋ｘk1＋１）を入れる。ステップＳ２において、Ｆの次数ｄｅｇ（Ｆ）をｄに入れる。ステップＳ３において、ｄ＜ｎであるかを調べ、ｄ＜ｎになれば、剰余Ｒが求まったのでステップＳ９においてＲにＦを入れて次の次数判定処理（ステップＳ１０）に行く。
また、ｄ＜ｎでない場合には、ステップＳ４において、ｄ−ｎ＜ｎ−ｋ２であるかを調べる。すなわち、Ｆの次数ｄとＧの次数ｎの差が、４項式Ｇの１項目の次数ｎと２項目の次数ｋの差より小さいかを調べる。
【００２７】
ｄ−ｎ＜ｎ−ｋ２の場合には、ステップＳ６に行き、Ｌに４項式Ｇの１項目の次数ｎを入れる。また、ｄ−ｎ＜ｎ−ｋの場合には、ステップＳ５に行き、Ｌに、Ｆの次数ｄとＧの次数ｎの差にｋ２＋１を加算したものを入れる。
ステップＳ７において、Ｆを（Ｆ１・ｘL ＋Ｆ２）（ここでｄｅｇ（Ｆ２）＜Ｌ）と分解し、ステップＳ８において、Ｆに（Ｆ２＋ｘL-n+K2Ｆ１＋ｘL-n+K1Ｆ１＋ｘL-n Ｆ１）を入れる。次いで、ステップＳ３に戻り、上記処理を繰り返す。
【００２８】
以上の処理を繰り返し、ｆ／Ｇの剰余Ｒが求まったら、次にステップＳ１０以降の次数判定処理を行い、上記と同様に剰余ｒを求める。
ステップＳ１０において、ｄｅｇ（Ｒ）が次数ｍより小さいかを調べ、小さい場合にはステップＳ１１に行き、ｒにＲを入れ処理を終了する。
ｄｅｇ（Ｒ）が次数ｍより小さく無い場合には、ステップＳ１２に行き、ｒにＲ＋ｇを入れ処理を終了する。
本実施例においては、上記のように次数ｍが与えられたとき、１次もしくは２次多項式のｈに対して、次数がｍより１次もしくは２次高く、項数が４項もしくは３項であり、かつ、ｍ次の既約因子を持つ多項式Ｇを見つけ出し、見い出した多項式Ｇと、Ｇ＝ｇｈの関係より（Ｇ，ｇ）の組みを求め、該（Ｇ，ｇ）の組みを利用して、多項式ｆをｇで除した剰余ｒを求めているので、従来方法に比べ、剰余時間を短縮することができる。
【００２９】
次に、本発明の効果を検証するため、同一多項式および５項式による従来法との剰余演算の性能比較を行った。
（ａ）同一多項式による剰余演算の性能比較
ｍ次の既約３項式が存在しないような１６０≦ｍ≦３２０に対して、ｇがある３項式Ｇの既約因子でありＧ／ｇが２次式であるような条件を満たす組（Ｇ，ｇ）が存在する次数ｍは次の通りである。
ｍ＝１７１，１７６，１７９，１９５，２０６，２１９，２２２，２２７，２３０，２４，２４３，２４５，２４６，２４８，２５１，２５４，２６７，２８８，２９１，２９３，２９９，３１５
まず、これらについて、ｇによる剰余演算を、従来技術である密な多項式に対する多項式除算による方法で行った場合と、本発明による方法で、Ｇ，ｇの２段階剰余計算で行った場合の計算時間を比較した。
その結果を表１に示す。
【００３０】
【表１】
0004043119.tif 000002
【００３１】
同表において、ｎｅｗ／ｏｌｄは本発明と従来法の剰余時間の比であり、ｎｅｗは本発明、ｏｌｄは従来法（同一のｇに対する剰余）である。
この結果から分かるように、本発明の方法による剰余計算は、従来法である密多項式に村する剰余演算に比較して、多項式による剰余演算に関しては１０倍程度の効率を達成できる。
【００３２】
（ｂ）５項式による従来法との比較
従来技術では、既約３項が存存しない場合には、既約５項式を定義多項式として用いる。ここでは、既約５項式による剰余計算と、本発明による剰余計算を適用した場合の計算時間の比を表２に示す。
【００３３】
【表２】
0004043119.tif 000003
【００３４】
同表において、ｎｅｗ／ｏｌｄは表１と同様、本発明と従来法の剰余時間の比であり、ｎｅｗは本発明、ｏｌｄは従来法（同一のｇに対する剰余）である。また、行った計算は、（ａ）と同様である。
【００３５】
この結果から分かるように、本発明で提案した定義多項式により、剰余演算に関しては５項式を越える効率を達成できることがわかる。
また、４項式／（ｘ＋１）を定義多項式に用いて本発明の方法を用いた場合と、５項式を用いた場合を比較すると、本発明が同等またはそれ以上の効率を示している。実験によれば、少なくとも３≦ｍ≦５００に対しては、４項式／（ｘ＋１）が既約となるものが存在する。よって、これらは５項式の代替として有効である。
【００３６】
【発明の効果】
以上説明したように、本発明によれば、疎多項式の因子で、余因子の次数が小さいような多項式ｇによる剰余演算の高速計算を行うことができる。
また、既約３項式が存在しない場合にも、本発明と５項式を用いる従来技術を比較した結果から明らかなように、実際に剰余計算時間を短縮することができる。さらに、本発明によれば、３項、５項、ＡＯＰ以外の多項式でもこれらと同等あるいは同等以上の剰余演算効率を達成できることから、３項、５項、ＡＯＰが何らかの理由で使用できなくなった場合の代替として用いることもできる。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】本発明を実施するためのシステムの構成例を示す図である。
【図３】本発明の実施例の機能ブロック図である。
【図４】本発明の実施例の３項式を探す処理を示すフローチャートである。
【図５】本発明の実施例の４項式を探す処理を示すフローチャートである。
【図６】本発明の実施例の３項式剰余演算処理を示すフローチャートである。
【図７】本発明の実施例の３項式剰余演算処理を示すフローチャートである。
【図８】本発明の実施例の４項式剰余演算処理を示すフローチャートである。
【符号の説明】
１    （Ｇ，ｇ）の組を見つけ出すための選択手段
２    剰余を演算する演算手段
１０  選択手段
１１  ３項式選択手段
１２  ４項式選択手段
１３  保存手段
２０  剰余演算手段
２１  剰余Ｒ算出手段
２２  次数判定手段
２３  剰余ｒ算出手段
【図１】
0004043119.tif 000004
【図２】
0004043119.tif 000005
【図３】
0004043119.tif 000006
【図４】
0004043119.tif 000007
【図５】
0004043119.tif 000008
【図６】
0004043119.tif 000009
【図７】
0004043119.tif 000010
【図８】
0004043119.tif 000011