(57)【特許請求の範囲】
【請求項１】
２次多項式ａ0 ＋ａ1 ｘ＋ａ2 ｘ2 と、ｂ0 ＋ｂ1 ｘ＋ｂ2 ｘ2 の積である４次多項式ｃ0 ＋ｃ1 ｘ＋ｃ2 ｘ2 ＋ｃ3 ｘ3 ＋ｃ4 ｘ4 ＝（ａ0 ＋ａ1 ｘ＋ａ2 ｘ2 ）×（ｂ0 ＋ｂ1 ｘ＋ｂ2 ｘ2 ）の係数ｃ0 ，ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 を出力とする積演算装置であって、
上記係数ａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 を入力する入力手段と、
その入力されたａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 を記憶する入力係数記憶手段と、
上記入力係数記憶手段からａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 を読出す手段と、
これら読出されたａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 を用いて
ｃ0   ←  ａ0 ｂ0 
ｔ1   ←  ａ0 ＋ａ1 
ｔ2   ←  ｂ0 ＋ｂ1 
ｔ3   ←  ａ1 ＋ａ2 
ｔ4   ←  ｂ1 ＋ｂ2 
を演算する第１段階演算手段と、
これら演算結果を演算結果記憶手段に記憶する手段と、
上記入力係数記憶手段からａ2 又はａ0 、ｂ2 又はｂ0 を読出し、上記演算結果記憶手段からｔ1 ，ｔ2 ，ｔ3 ，ｔ4 を読出す手段と、
これら読出されたａ2 又はａ0 、ｂ2 又はｂ0 ，ｔ1 ，ｔ2 ，ｔ3 ，ｔ4 を用いて
ｔ5   ←  ｔ1 ｔ2 
ｔ6   ←  ｔ3 ｔ4 
ｔ7 ←ｔ1 ＋ａ2 ，又は，ｔ7 ←ａ0 ＋ｔ3 
ｔ8 ←ｔ2 ＋ｂ2 ，又は，ｔ8 ←ｂ0 ＋ｔ4 
を演算する第２段階演算手段と、
これら演算結果ｔ5 ，ｔ6 ，ｔ7 ，ｔ8 を上記演算結果記憶手段に記憶する手段と、
上記入力係数記憶手段からａ1 とｂ1 を読出してｔ0 ←ａ1 ｂ1 を上記第１段階演算手段又は上記第２段階演算手段で演算して上記演算結果記憶手段に記憶する手段と、
上記演算結果記憶手段からｔ0 ，ｔ5 ，ｔ6 ，ｔ7 ，ｔ8 を読出す手段と、
これら読出されたｔ0 ，ｔ5 ，ｔ6 ，ｔ7 ，ｔ8 を用いて、
ｔ9   ←  ｔ7 ｔ8 
ｔ10  ←  ｔ5 −ｔ0 
ｔ11  ←  ｔ6 −ｔ0 
を演算する第３段階演算手段と、
これら演算結果ｔ9 ，ｔ10，ｔ11を上記演算結果記憶手段に記憶する手段と、
上記入力係数記憶手段からａ2とｂ2を読出してｃ4 ←ａ2 ｂ2を上記第１段階演算手段、上記第２段階演算手段及び上記第３段階演算手段の何れかで演算して上記演算結果記憶手段に記憶する手段と、
上記演算結果記憶手段からｃ0 ，ｃ4 をｔ9 ，ｔ10，ｔ11を読出す手段と、
これら読出されたｃ0 ，ｃ4 ，ｔ9 ，ｔ10，ｔ11を用いて、
ｃ1   ←  ｔ10−ｃ0 
ｃ3   ←  ｔ11−ｃ4 
ｃ2   ←  ｔ9 −ｔ10−ｔ11
を演算する第４段階演算手段と、
上記演算結果ｃ0 ，ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 を出力する手段と、
を具備する積演算装置。
【請求項２】
２次多項式ａ0 ＋ａ1 ｘ＋ａ2 ｘ2 と、ｂ0 ＋ｂ1 ｘ＋ｂ2 ｘ2 の積である４次多項式ｃ0 ＋ｃ1 ｘ＋ｃ2 ｘ2 ＋ｃ3 ｘ3 ＋ｃ4 ｘ4 ＝（ａ0 ＋ａ1 ｘ＋ａ2 ｘ2 ）×（ｂ0 ＋ｂ1 ｘ＋ｂ2 ｘ2 ）の係数ｃ0 ，ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 を出力とする、積演算装置であって、
上記係数ａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 を格納する格納手段と、
この格納手段に格納されたａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 について
ｃ0   ←  ａ0 ｂ0 を演算する手段と、
ｔ0   ←  ａ1 ｂ1 を演算する手段と、
ｃ4   ←  ａ2 ｂ2 を演算する手段と、
ｔ1   ←  ａ0 ＋ａ1 を演算する手段と、
ｔ2   ←  ｂ0 ＋ｂ1 を演算する手段と、
ｔ3   ←  ａ1 ＋ａ2 を演算する手段と、
ｔ4   ←  ｂ1 ＋ｂ2 を演算する手段と、
上記格納されたａ2 又はａ0 、ｂ2 又はｂ0 、
上記演算結果ｔ1 ，ｔ2 ，ｔ3 ，ｔ4 を用いて
ｔ5   ←  ｔ1 ｔ2 を演算する手段と、
ｔ6   ←  ｔ3 ｔ4 を演算する手段と、
ｔ7 ←ｔ1 ＋ａ2 ，又は，ｔ7 ←ａ0 ＋ｔ3 を演算する手段と、
ｔ8 ←ｔ2 ＋ｂ2 ，又は，ｔ8 ←ｂ0 ＋ｔ4 を演算する手段と、
上記演算結果ｔ0 ，ｔ5 ，ｔ6 ，ｔ7 ，ｔ8 を用いて
ｔ9   ←  ｔ7 ｔ8 を演算する手段と、
ｔ10  ←  ｔ5 −ｔ0 を演算する手段と、
ｔ11  ←  ｔ6 −ｔ0 を演算する手段と、
上記演算結果ｃ0 ，ｃ4 ，ｔ9 ，ｔ10，ｔ11を用いて、
ｃ1   ←  ｔ10−ｃ0 を演算する手段と、
ｃ3   ←  ｔ11−ｃ4 を演算する手段と、
ｃ2   ←  ｔ9 −ｔ10−ｔ11を演算する手段と、
上記演算結果ｃ0 ，ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 を出力する出力手段と
を具備する積演算装置。
【請求項３】
請求項１又は２に記載の積演算装置において、
入力するａ0 ，ａ1 ，ａ2 及び，ｂ0 ，ｂ1 ，ｂ2 を元に持つ、単位元を持つ可換環Ｓの適当な元ｙを用いて定義される３倍長元ａ0 ＋ａ1 ｙ＋ａ2 ｙ2 及び，ｂ0 ＋ｂ1 ｙ＋ｂ2 ｙ2 の積を求める、環上積演算装置のうち、請求項１又は２に記載の積演算装置の手段を用い、請求項１又は２に記載の積演算装置における多項式の変数ｘを環Ｓの元ｙとする事を特徴とする環上積演算装置。
【請求項４】
請求項１ないし請求項３のいずれかに記載の積演算装置としてコンピュータを機能させるプログラムを記録したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、様々な分野の乗算に用いられ、例えば二つの２次多項式の乗算結果の４次多項式の各係数を演算する積演算装置及びそのプログラム記録媒体に関する。
【０００２】
【従来の技術】
１次式ａ0 ＋ａ1 ｘとｂ0 ＋ｂ1 ｘの乗算を実行するためには、教科書通りの方法は下記演算による。
（ａ0 ＋ａ1 ｘ）（ｂ0 ＋ｂ1 ｘ）
＝ａ0 ｂ0 ＋（ａ0 ｂ1 ＋ａ1 ｂ0 ）ｘ＋ａ1 ｂ1 ｘ2 
この乗算結果の２次多項式の各係数を求める演算を、この従来法により求めるには、ａi ，ｂi （ｉ＝０，１）のビット数をｎ弱とすると、つまり各係数を格納するレジスタのビット数がｎとすると、以下のコストで実行することができる。
【０００３】
（ｎビット）×（ｎビット）    →  （２ｎビット）    ４回
（ｎビット）＋（ｎビット）    →  （ｎビット）      ０回
（２ｎビット）±（２ｎビット）  →  （２ｎビット）    １回
つまり（ｎビット）×（ｎビット）の乗算はａ0 ｂ0 とａ0 ｂ1 とａ1 ｂ0 とａ1 ｂ1 の４回であり（ｎビット）と（ｎビット）の加減算は０回であり、（ｎビット）×（ｎビット）の乗算結果の（２ｎビット）の加減算はａ0 ｂ1 ＋ａ1 ｂ0 の１回である。
【０００４】
また、文献「D.E.Knuth 著、中川圭介訳：“準数値算法／算術演算”、サイエンス社、pp.111-112、1986」に紹介されているKaratsuba-Ofman 法をこの１次式同士の乗算に適用すると
（ａ0 ＋ａ1 ｘ）（ｂ0 ＋ｂ1 ｘ）＝ａ0 ｂ0 ＋（（ａ0 ＋ａ1 ）（ｂ0 ＋ｂ1 ）−ａ0 ｂ0 −ａ1 ｂ1 ）ｘ＋ａ1 ｂ1 ｘ2 
となり、計算の順序を工夫すればｘの係数の計算（（ａ0 ＋ａ1 ）（ｂ0 ＋ｂ1 ）−ａ0 ｂ0 −ａ1 ｂ1 ）に定数項ａ0 ｂ0 とｘ2 の係数ａ1 ｂ1 を利用できるので、
（ｎビット）×（ｎビット）    →  （２ｎビット）    ３回
（ｎビット）＋（ｎビット）    →  （ｎビット）      ２回
（２ｎビット）±（２ｎビット）  →  （２ｎビット）    ２回
で実行できる。この方法は、乗算が加減算に比べてある程度以上遅い場合に有効である。さて、このKaratsuba-Ofman 法を用いると、かけ算を実行する多項式の次数が２m −１のとき、再帰的に適用すると効率的な乗算が実行できることがわかるが、それ以外の次数の場合にはどのように適用すればよいか不明であった。
【０００５】
以下では、２次式について効率的な計算を行なう方法を考察する。
２次式ａ0 ＋ａ1 ｘ＋ａ2 ｘ2 とｂ0 ＋ｂ1 ｘ＋ｂ2 ｘ2 の乗算を実行するためには、Lim-Hwang の方法が文献「C.-H.Lim and H.-S.Hwang：“Fast Implementation of Elliptic Curve Arithmetic in GF(pn)，”Public Key Cryptography,Lecture Notes in Computer Science 1751,Springer-Verlag,2000 」に紹介されている。この方法は、
0003766250.tif 000002
である。この方法は、ａ0 ｂ0 の計算が３回、ａ1 ｂ1 の計算が３回、ａ2 ｂ2 の計算が３回あるから、これらは計算の順序を工夫することにより各１回計算すればよいから、ａi ｂi （ｉ＝０，１，２）のビット数をｎ弱とすると、以下のコストで実行することができる。
【０００６】
（ｎビット）×（ｎビット）    →  （２ｎビット）    ６回
（ｎビット）＋（ｎビット）    →  （ｎビット）      ６回
（２ｎビット）±（２ｎビット）  →  （２ｎビット）    ７回
【０００７】
【発明が解決しようとする課題】
上記Lim-Hwang の方法は、乗算に関しては理論上最小値ではあるが、（２ｎビット）の加減算のように多倍長の加減算が多い。この発明では多倍長の加減算の回数を削減することができる２次多項式演算の係数を求める積演算装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
この発明の１形態によれば、２次式ａ0 ＋ａ1 ｘ＋ａ2 ｘ2 とｂ1 ＋ｂ1 ｘ＋ｂ2 ｘ2 を乗算した結果の４次多項式ｃ0 ＋ｃ1 ｘ＋ｃ2 ｘ2 ＋ｃ3 ｘ3 ＋ｃ4 ｘ4 における各係数ｃ0 ，ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 を次式の関係式に基いて求める。
0003766250.tif 000003
つまり各係数ａ0 ，ａ1 ，ａ2 とｂ0 ，ｂ1 ，ｂ2 を入力手段により記憶手段に記憶し、第１段階演算手段により、ａ0 ｂ0 を演算してｃ0 を得、ａ1 ｂ1 を演算してｔ0 を得、ａ2 ｂ2 を演算してｃ4 を得、ａ0 ＋ａ1 を演算してｔ1 を得、ｂ0 ＋ｂ1 を演算してｔ2 を得、ａ1 ＋ａ2 を演算してｔ3 を得、ｂ1 ＋ｂ2 を演算してｔ4 を得、
第２段階演算手段により、ｔ1 ｔ2 を演算してｔ5 を得、ｔ3 ｔ4 を演算してｔ6 を得、ｔ1 ＋ａ2 又はａ0 ＋ｔ3 を演算してｔ7 を得、ｔ2 ＋ｂ2 又はｂ0 ＋ｔ4 を演算してｔ8 を得、
第３段階演算手段により、ｔ7 ｔ8 を演算してｔ9 を得、ｔ5 −ｔ0 を演算してｔ10を得、ｔ6 −ｔ0 を演算してｔ11を得、
第４段階演算手段によりｔ10−ｃ0 を演算してｃ1 を得、ｔ11−ｃ4 を演算してｃ3 を得、ｔ9 −ｔ10−ｔ11を演算してｃ2 を得、
上記演算結果のｃ0 ，ｃ1 ，ｃ2 ，ｃ3 を出力手段により出力する。なおａ1 ｂ1 を演算してｔ0 を得ることに第３段階演算手段で行ってもよい。
【０００９】
【発明の実施の形態】
以下ではこの発明の実施例を示す。
以下にａ0 ＋ａ1 ｘ＋ａ2 ｘ2 とｂ0 ＋ｂ1 ｘ＋ｂ2 ｘ2 の乗算結果のｃ0 ＋ｃ1 ｘ＋ｃ2 ｘ2 ＋ｃ3 ｘ3 ＋ｃ4 ｘ4 における各係数ｃ0 ，ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 を求める装置の実施例を図面を参照して説明する。
図１に示すように入力手段１１により乗算されるべき２次式の各係数ａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 が入力され、その入力された各係数は中央処理手段１２により記憶装置１３中の入力係数記憶部１４に格納される（Ｓ１、図２）。なお中央処理手段１２がプログラムを読出し解読実行するためのプログラムが格納されたＲＯＭ１５、各種演算転送などの処理のためのワークメモリとして用いられるＲＡＭ１６が設けられている。
【００１０】
次に入力係数記憶部１４から各係数ａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 が読出され（Ｓ２）、中央処理手段１２の制御のもとに第１段階演算手段が実行される（Ｓ３）。つまりａ0 ｂ0 を演算してｃ0 を得、ａ1 ｂ1 を演算してｔ0 を得、ａ2 ｂ2 を演算してｃ4 を得、ａ0 ＋ａ1 を演算してｔ1 を得、ｂ0 ＋ｂ1 を演算してｔ2 を得、ａ1 ＋ａ2 を演算してｔ3 を得、ｂ1 ＋ｂ2 を演算してｔ4 を得る。これらの演算の順は任意でよい。
【００１１】
これら演算結果ｃ0 ，ｔ0 ，ｃ4 ，ｔ1 ，ｔ2 ，ｔ3 ，ｔ4 は記憶装置１３の第１演算結果記憶部１７に記憶される（Ｓ４）。
次に入力係数記憶部１４からａ2 ，ｂ2 を読出し、第１演算結果記憶部１７からｔ1 ，ｔ2 ，ｔ3 ，ｔ4 を読出し（Ｓ５）、中央処理手段１２の制御のもとに第２段階演算手段が実行される（Ｓ６）。つまりｔ1 ｔ2 を演算してｔ5 を得、ｔ3 ｔ4 を演算してｔ6 を得、ｔ1 ＋ａ2 を演算してｔ7 を得、ｔ2 ＋ｂ2 を演算してｔ8 を得る。これらの演算の順は任意でよい。
【００１２】
これら演算結果ｔ5 ，ｔ6 ，ｔ7 ，ｔ8 は記憶装置１３の第２演算結果記憶部１８に格納される（Ｓ７）。
次に第１演算結果記憶部１７からｔ0 が読出され、第２演算結果記憶部１８からｔ5 ，ｔ6 ，ｔ7 ，ｔ8 が読出され（Ｓ８）、中央処理手段１２の制御のもとに第３段階演算が実行される（Ｓ９）。つまりｔ7 ｔ8 を演算してｔ9 を得、ｔ5 −ｔ0 を演算してｔ10を得、ｔ6 −ｔ0 を演算してｔ11を得る。これらの演算順は任意でよい。これら演算結果ｔ9 ，ｔ10，ｔ11は記憶装置１３の第３演算結果記憶部１９に記憶される（Ｓ１０）。
【００１３】
次に第１演算結果記憶部１４からｃ0 ，ｃ4 が読出され、第３演算結果記憶部１９からｔ9 ，ｔ10，ｔ11が読出され（Ｓ１１）、中央処理手段１２の制御のもとに第４段階演算手段が実行される（Ｓ１２）。つまりｔ10−ｃ0 を演算してｃ1 を得、ｔ11−ｃ4 を演算してｃ3 を得、ｔ9 −ｔ10−ｔ11を演算してｃ2 を得る。これらの演算の順は任意でよい。これら演算結果ｃ1 ，ｃ3 ，ｃ2 は記憶装置１３の第４演算結果記憶部２１に記憶される（Ｓ１３）。
【００１４】
次に第１演算結果記憶部１７からｃ0 とｃ4 が、第４演算結果記憶部２１からｃ1 ，ｃ2 ，ｃ3 がそれぞれ読出され、出力手段２２から出力される（Ｓ１４）。
上述においてｔ0 は第３段階演算（Ｓ９）で用いられるものであるから、ａ1 ｂ1 ＝ｔ0 の演算は第１段階演算（Ｓ３）ではなく第２段階演算（Ｓ６）で行ってもよい。同様にｃ4 は第４段階演算（Ｓ１２）で用いられるものであるから、第１段階演算（Ｓ３）ではなく、第２段階演算（Ｓ６）又は第３段階演算（Ｓ９）で行ってもよい。またｔ7 はａ0 ＋ａ1 ＋ａ2 であるから、第２段階演算（Ｓ６）において、ｔ1 （＝ａ0 ＋ａ1 ）＋ａ2 の代りにａ0 ＋ｔ3 （＝ａ1 ＋ａ2 ）を演算してもよい、同様にｔ8 はｂ0 ＋ｂ1 ＋ｂ2 であるから、第２段階演算（Ｓ６）においてｔ2 （＝ｂ0 ＋ｂ1 ）＋ｂ2 の代りにｂ0 ＋ｔ4 （＝ｂ1 ＋ｂ2 ）を演算してもよい。また上述の各段階演算において、複数の演算を同時に行ってもよい。
【００１５】
この実施例における演算はａi ，ｂi （ｉ＝０，１，２）のビット数をｎ弱とすると、
（ｎビット）と（ｎビット）の乗算は６回
（ｎビット）と（ｎビット）の加減算は６回
（２ｎビット）と（２ｎビット）の加減算は６回
となり、前記Lim-Hwang の方法に比べ２ｎビット同士の加減算が１回減少している。
【００１６】
上述においてはこの発明をコンピュータにより構成したが各演算をハードウェア構成としてもよい。つまり例えば図３に示すように入力レジスタ群２５にａ0 ，ａ1 ，ａ2 ，ｂ0 ，ｂ1 ，ｂ2 を格納し、演算部２６ａ，２６ｂ，２６ｄ，２６ｅ，２６ｆ，２６ｇでそれぞれａ0 ｂ0 ＝ｃ0 、ａ1 ｂ1 ＝ｔ0 、ａ2 ｂ2 ＝ｃ4 、ａ0 ＋ａ1 ＝ｔ1 、ｂ0 ＋ｂ1 ＝ｔ2 、ａ1 ＋ａ2 ＝ｔ3 、ｂ1 ＋ｂ2 ＝ｔ4 を演算し、演算部２７ａ，２７ｂ，２７ｃ，２７ｄでそれぞれｔ1 ｔ2 ＝ｔ5 、ｔ3 ｔ4 ＝ｔ6 、ｔ1 ＋ａ2 ｘ＝ｔ7 、ｔ2 ＋ｂ2 ＝ｔ8 を演算し、演算部２８ａ，２８ｂ，２８ｃでそれぞれｔ7 ｔ8 ＝ｔ9 、ｔ5 −ｔ0 ＝ｔ10、ｔ6 −ｔ0 ＝ｔ11 を演算し、演算部２９ａ，２９ｂ，２９ｃでそれぞれ、ｔ10−ｃ0 ＝ｃ1 、ｔ11−ｃ4 ＝ｃ3 、ｔ9 −ｔ10−ｔ11＝ｃ2 を演算し、上記演算結果中のｃ0 ，ｃ1 ，ｃ2 ，ｃ3 ，ｃ4 を出力レジスタ群３１に格納してもよい。
【００１７】
この発明はｘとして適当な整数を代入することにより多項式のみならず３倍長の乗算にも利用可能である。つまり、ａ0 ，ａ1 ，ａ2 及びｂ0 ，ｂ1 ，ｂ2 を元に持ち、単位元を持つ可換環Ｓの適当な元ｙを用いて定義される３倍長元ａ0 ＋ａ1 ｙ＋ａ2 ｙ2 及びｂ0 ＋ｂ1 ｙ＋ｂ2 ｙ2 の積を求める。環上積演算装置のうち、先の係数積演算を行って、前記多項式の変数ｘを環Ｓの元ｙとすることにより、求めることができる。
【００１８】
【発明の効果】
以上述べたようにこの発明によれば、２次多項式を乗算した４次多項式の各係数を求める演算を従来よりも少ない計算コストで行うことができ、つまりコンピュータによれば従来より高速に演算でき、ハードウェアで構成すればハードウェア規模を小さくすることができる。
【図面の簡単な説明】
【図１】この発明の実施例の構成を示す図。
【図２】図１の実施例の動作の流れを示す図。
【図３】この発明の他の実施例を示す図。
【図１】
0003766250.tif 000004
【図２】
0003766250.tif 000005
【図３】
0003766250.tif 000006