TOP > 国内特許検索 > 剰余系の計算方法及び装置並びにプログラム > 明細書

明細書 :剰余系の計算方法及び装置並びにプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4182226号 (P4182226)
公開番号 特開2007-057811 (P2007-057811A)
登録日 平成20年9月12日(2008.9.12)
発行日 平成20年11月19日(2008.11.19)
公開日 平成19年3月8日(2007.3.8)
発明の名称または考案の名称 剰余系の計算方法及び装置並びにプログラム
国際特許分類 G09C   1/00        (2006.01)
FI G09C 1/00 650A
請求項の数または発明の数 2
全頁数 14
出願番号 特願2005-242956 (P2005-242956)
出願日 平成17年8月24日(2005.8.24)
新規性喪失の例外の表示 特許法第30条第1項適用 2005年3月3日 社団法人電子情報通信学会発行の「電子情報通信学会技術研究報告 信学技報Vol.104 No.708」に発表
審査請求日 平成19年10月31日(2007.10.31)
特許権者または実用新案権者 【識別番号】504139662
【氏名又は名称】国立大学法人名古屋大学
発明者または考案者 【氏名】▲高▼木 直史
【氏名】カイハラ、マルセロ エミリオ
早期審査対象出願または早期審理対象出願 早期審査対象出願
個別代理人の代理人 【識別番号】100082500、【弁理士】、【氏名又は名称】足立 勉
審査官 【審査官】速水 雄太
参考文献・文献 特開平05-324277(JP,A)
調査した分野 G09C 1/00
特許請求の範囲 【請求項1】
r進の整数Mを法とする剰余系において(ただし、Mとrとは互いに素)、前記法M、r進でn桁の変数Y及び変数Xが入力されたときに前記変数Yを上位(n-m)桁のYH
及び下位m桁のYLに分割する分割手段と、
前記変数Yを分割した上位(n-m)桁のYH、前記変数X及び前記法Mで
X・YH mod M
を計算して出力する第1乗算剰余算器と、
前記変数Yを分割した下位m桁のYL、前記変数X及び前記法Mで
X・YL・r-m mod M
を計算して出力する第2乗算剰余算器と、
前記第1乗算剰余算器の出力及び前記第2乗算剰余算器の出力を加算し、その加算結果を出力する加算器と、
を備えたことを特徴とする乗算剰余演算装置。
【請求項2】
請求項1に記載の乗算剰余演算装置において、
前記加算器の加算結果を入力し、前記法Mによる剰余算を行って出力する剰余算器を備えたことを特徴とする乗算剰余演算装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、剰余系の計算方法及び装置並びにプログラムに関する。
【背景技術】
【0002】
従来、ネットワーク上で送受信されるデータのセキュリティを確保するために、データを暗号化・復号化するRSA(Rivest-Shamir-Adleman)等の公開鍵暗号システムが用いられている。
【0003】
その公開鍵暗号システムでは、使用される公開鍵のサイズ(桁数)を大きくすれば、不正な方法による暗号の解読が困難となり、情報を送受信する際のセキュリティをより強化することができる。
【0004】
ところが、RSA等の公開鍵暗号システムでは、暗号化と復号化のために剰余系指数演算を行う必要があり、その剰余系指数演算の量は公開鍵のサイズにともなって多くなる。
そして、ほとんどの場合、その剰余系指数演算は非常に大きな整数の乗算剰余算(剰余系乗算)を繰返し計算することにより実現されており、その乗算剰余算の繰返し計算には膨大な時間が必要であった。
【0005】
したがって、この乗算剰余算の繰り返し計算の実行速度を速くすることができれば、使用する鍵のサイズをさらに大きくでき、ネットワーク上で送受信されるデータのセキュリティ強化を図ることができる。
【0006】
乗算剰余算の繰返し計算を高速化する方法として、変数をモンゴメリの領域に変換して個々の乗算剰余算をモンゴメリ乗算に置き換える方法があり(例えば、非特許文献1参照)、さらに、そのモンゴメリ乗算の高速化法として基数を増す方法がある(例えば、非特許文献2参照)。
【0007】
また、個々の乗算剰余算の高速化の方法としてインターリーブ法で基数を増す方法がある(例えば、非特許文献3参照)。

【非特許文献1】P.L. Montgomery, "Modular Multiplication without Trial Division," Mathematics of Computation, vol.44,no.170,pp.519-521, Apr.1985.
【非特許文献2】S.E Eldridge and C.D. Walter, "Hardware Implementation of Montgomery's Modular Multiplication Algorithm," IEEE Transactions on Computers, vol.42,no.6,pp.693-699,Jun.1993.
【非特許文献3】N. Takagi, "A Radix-4 Modular Multiplication Hardware Algorithm for Modular Exponentiation," IEEE Transactions on Computers, vol.41, no.8, pp.949-956, Aug. 1992.
【発明の開示】
【発明が解決しようとする課題】
【0008】
ところで、上記非特許文献2及び非特許文献3に記載されている改良された乗算剰余算方法は、演算の基数を増すことにより、演算に必要なクロックサイクル数を削減するものである。
【0009】
しかし、基数が増すと演算回路が複雑になり、演算のサイクル時間が大きくなる。従って、基数が増すにつれ、高速化の割合は小さくなるという問題がある。
本発明は、こうした問題に鑑みなされたもので、剰余系における乗算剰余算の繰り返し計算をサイクル時間を増すことなく高速化するための計算方法を提供することを目的とする。
【課題を解決するための手段】
【0010】
本発明の理解をより明確にするために、特許請求の範囲に記載した課題解決手段を具体的に解説する前に、本発明の技術的思想の創作過程について説明する。
前述したように、RSA等の公開鍵暗号システムでは、暗号化と復号化のために非常に大きな整数の乗算剰余算(剰余系乗算)を繰返し計算することにより実現されている。
【0011】
このような、大きな整数に関する繰返し計算においては、その大きな整数を上位部分と下位部分とに分割して、上位部分の計算と下位部分の計算とを並列処理して高速化することが考えられる。
【0012】
ところが、乗算剰余算は、被乗数に乗数を掛け、その掛け算の結果を法Mで割り、そのときの余りを得るという演算であるため、乗数を分割して並列処理をするメリットが得られない。
【0013】
これを分かりやすく説明するために、以下に具体的な例により説明する。
例えば、法M=9753とする乗算剰余算、 5432×4321 mod 9753を考える。
【0014】
5432×4321 mod 9753をそのまま計算すると、
5432×4321 mod 9753
=23471672 mod 9753=5954
となり、8桁を4桁で割る割り算を行う必要がある。
【0015】
次に、乗数の4321を上位2桁の43と下位2桁の21とに分割して計算すると、
5432×4321 mod 9753
=(5432×4300 mod 9753
+5432×21 mod 9753) mod 9753 となり、上位部分と下位部分とを並列計算することができるようになる。
【0016】
実際に計算すると、乗数の上位部分は、23357600 mod 9753=8918となり、下位部分は、114072 mod 9753=6789になる。
このように、乗数4321を上位2桁と下位2桁に分割すると、下位部分は、6桁を4桁で割る割り算となり、確かに計算が簡単になる。
【0017】
ところが、上位部分の計算は、結局8桁を4桁で割る割り算が必要となる。つまり、乗算剰余算においては、乗数を単純に上位部分と下位部分とに分割して、それを並列計算しても、結局、上位部分で分割前と同じ桁数同士の割り算(ここでは、8桁を4桁で割る割り算)を行う必要がある。
【0018】
このように、乗算剰余算では、乗数を上位部分と下位部分に分割して計算しても、並列処理を行う利点が得られなかった。
そこで、本発明では、剰余系を新たに定義する領域に変換し、乗数を上位部分と下位部分とに分割した場合に、剰余演算の部分で上位部分、下位部分ともに計算の桁数を減らして並列計算ができるようにし、ひいては計算の高速化を可能としたのである。
【0019】
ここで、乗算剰余算と新たに定義する領域との関係を図1を参照しつつ説明する。
図1に示すように、剰余系における変数U,Vを新たに定義する領域では、各々X=U・R mod M、Y=V・R mod Mに変換する。また、剰余系における乗算剰余算U・V mod MをX・Y・R-1 mod M=U・V・R mod Mに置き換える。
【0020】
ここで、Mがr進であるとき、R=rmとすると、図1のS100に示すように、被乗数Uは、X=U・rm mod Mに変換される。また乗数Vも同様に、Y=V・rm mod Mに変換される(図1のS102を参照)。つまり、U,Vが新たに定義する領域のX,Yに変換される。
【0021】
そして、乗算剰余算を、U・V mod Mから、新たに定義する領域における、X・Y・r-m mod Mに置換する(図1のS104を参照)。
このようにして、パラメータmを導入することにより、n桁の乗数Yを上位(n-m)桁のYHと下位m桁のYLとの二つの部分に分割し、これらを並列に処理することが可能となる。ここで、0<m<n、m:整数とする。
【0022】
このように、その新たに定義した領域において、変数(乗数)Yを上位部分YHと下位
部分YLとに分けて、それらを並列に計算し、その計算結果を逆変換して元の領域に戻す
ことにより最終的に乗算剰余算の結果を得るという剰余系の計算方法がある。
【0023】
その計算方法とは、以下に記載のように、整数Mを法とする剰余系において、変数U,Vを法Mと互いに素でMより小さな定数Rを用いて、変数X=U・R mod M、変数Y=V・R mod M、に変換し、剰余系における乗算剰余算、U・V mod Mを演算
X・Y・R-1 mod M・・・式1
に置換し、剰余系における計算と同じ計算を行い、その計算結果Zを演算
Z・R-1 mod M・・・式2
にて逆変換して剰余系における計算結果を得ることを特徴とする。
【0024】
このような計算方法によれば、各変数U,Vが定数Rで、X=U・R mod M、Y=V・R mod M、に変換され、剰余系における乗算剰余算U・V mod Mが新たに定義されるX・Y・R-1 mod Mに置換される。この、変数の変換と乗算剰余算式の置換とによって得られる代数系を「新たに定義した領域」と呼ぶことにすると、剰余系での計算が新たに定義した領域において、同じように計算できる。
【0025】
この新たに定義した領域における乗算剰余算においては、前述したように乗数Yを上位部分YHと下位部分YLとに分割して計算することができる。
したがって、剰余系の演算を新たに定義した領域において計算しようとすると、上記の変換や逆変換が必要となるものの、乗算剰余算において乗数Yを上位部分YHと下位部分YLとに分けて計算できるので、例えば公開鍵暗号等の計算のように、剰余系において乗算剰余算を繰返し行わなければならない計算を高速化することができる。
【0026】
つまり、新たに定義した領域において、上位部分YH及び下位部分YLの計算を並列計算によって、剰余系における乗算剰余算と同じ計算結果を得ることができるので、剰余系において乗算剰余算を繰返し行わなければならない計算を高速化することができるのである。
【0027】
ここで、上記式1及び式2におけるmod Mは、Mを法とする剰余算であり、その計算の結果は通常0から(M-1)の値をとるが、ここでは計算結果が法Mと合同であり、M以上あるいは負である場合も含むものである。なお、上記式1及び式2におけるmodMに限らず、本明細書において、mod Mはすべて同様の意味である。
【0028】
そして、新たに定義した領域において、以下に記載のように、変数Yがr進でn桁であるとき、定数Rを、
R=rm
とし、変数Yを
Y=YH・rm+YL・・・式3
によって、上位(n-m)桁のYHと下位m桁のYLとに分割し、(mは、m<nを満たす整数)式1を、
(X・YH mod M+X・YL・R-1 mod M)mod M・・・式4
に変換して、式4の
X・YH mod M・・・式4a
と、
X・YL・R-1 mod M・・・式4b
と、を並列処理で実行するようにするとよい。
【0029】
このように、式4aによる計算と式4bとによる計算とを並列処理すれば、剰余系における乗算剰余算に対応する新たに定義した領域での計算速度を容易に高速化することができる。
【0030】
すなわち、式4aによる計算と式4bとによる計算とは各々の計算方法が異なるためその計算速度が異なるので、式4aによる計算と式4bとによる計算とを各々の計算速度に合わせるようにする。
【0031】
例えば、式4aによる計算の計算速度が速ければ、乗数Yを分割する際の上位部分YHの桁数(n-m)を下位部分YLの桁数mよりも多くし、逆に、式4bによる計算の計算速度が速ければ、上位部分YHの桁数(n-m)を下位部分YLの桁数mよりも少なくするようにする。すると、両方の計算をほぼ同時に終了させることができるので、全体での計算時間を容易に短縮、換言すれば、計算速度を高速化することができるのである。
【0032】
以上のように、新たに定義した領域において、乗数Yを上位部分YHと下位部分YLとに分割して計算することによって、剰余系における乗算剰余算の演算速度を高速化することができるが、分割した上位部分YHを計算するための式4aによる計算と下位部分YLを計算するための式4bによる計算とには、「背景技術」で述べたように種々の計算方法がある。
【0033】
例えば、式4aによる計算にインターリーブ法を用い、式4bによる計算にモンゴメリ乗算における計算方法を用いると、従来のプログラムや演算回路を利用することができるので、プログラムや演算装置を容易に構成することができる。したがって、プログラム作成や演算装置のコストダウン等が可能になる。
【0034】
なお、式4aと式4bとによる計算は、必ずしも独立している必要はなく、式4aと式4bとによる計算を行っていく過程で同期をとって、お互いの中間計算結果をやり取りしつつ計算を行うようにしてもよい。
【0035】
また、r進、n桁の変数Yにおいて、n桁とは変数Yの桁数として設定された桁数のことであり、例えば、r=2でn=8(つまり、2進8桁)の場合、Y=00001010のように、桁の上位桁(この場合上位4桁)が0であるものも含んでいる。
【0036】
以上に説明した剰余系の計算方法を装置化したものが請求項1に記載の乗算剰余系演算装置である。すなわち、請求項1に記載の乗算剰余演算装置は、r進の整数Mを法とする剰余系において(ただし、Mとrとは互いに素)、法M、r進でn桁の変数Y及び変数Xが入力されたときに変数Yを上位(n-m)桁のYH及び下位m桁のYLに分割する分割手段(10:この欄においては、発明に対する理解を容易にするため、必要に応じて「発明を実施するための最良の形態」欄において用いた符号を付すが、この符号によって請求の範囲を限定することを意味するものではない。)と、変数Yを分割した上位(n-m)桁のYH、変数X及び法
Mで
X・YH mod M
を計算して出力する第1乗算剰余算器(20)と、変数Yを分割した下位m桁のYL、変
数X及び法Mで
X・YL・r-m mod M
を計算して出力する第2乗算剰余算器(30)と、第1乗算剰余算器(20)の出力及び第2乗算剰余算器(30)の出力を加算し、その加算結果を出力する加算器(40)と、を備えたことを特徴とする乗算剰余演算装置である。
【0037】
このように構成された乗算剰余演算装置の出力、つまり加算器(40)から出力される計算結果は、0から(M-1)の値以外に、法Mと合同であり、かつ、M以上あるいは負である場合の計算結果を得ることができる。
【0038】
そして、このように構成された乗算剰余演算装置によれば、第1乗算剰余算器(20)において実行される上位(n-m)桁の計算と、第2乗算剰余算器(30)において実行される下記m桁の計算とが並列計算される。そして、変数YHとYLとは分割される前の変数Yに比べ、桁数が減っているので、各々の乗算剰余算器(20,30)での計算速度は速くなる。したがって、剰余系における乗算剰余算に対応する新たに定義した領域での計算速度を容易に高速化することができる。
【0039】
また、上記計算方法にて説明したように、第1乗算剰余算器(20)で実行される計算(式4aに相当)と第2乗算剰余算器(30)で実行される計算(式4b相当)とが並列処理されているので、剰余系における乗算剰余算に対応する新たに定義した領域での計算速度を容易に高速化することができる。
【0040】
すなわち、第1乗算剰余算器(20)で実行される計算と第2乗算剰余算器(30)で実行される計算とは各々の計算方法が異なるため、その計算速度が異なる。そこで、第1乗算剰余算器(20)で実行される計算と第2乗算剰余算器(30)で実行される計算とを各々の計算速度に合わせて実行する。
【0041】
例えば、第1乗算剰余算器(20)での計算速度が速ければ、乗数Yを分割する際の上位部分YHの桁数(n-m)を下位部分YLの桁数mよりも多くし、逆に、第2乗算剰余算器(30)での計算速度が速ければ、上位部分YHの桁数(n-m)を下位部分YLの桁数mよりも少なくするようにする。すると、両方の乗算剰余算器(20,30)での計算をほぼ同時に終了させることができるので、全体での計算時間を容易に短縮、換言すれば、計算速度を高速化することができるのである。
【0042】
以上のように、新たに定義した領域において、乗数Yを上位部分YHと下位部分YLとに分割して計算することによって、剰余系における乗算剰余算の演算速度を高速化することができるが、分割した上位部分YHを計算するための第1乗算剰余算器(20)及び下位部分YLを計算するための第2乗算剰余算器(30)には種々の回路構成がある。
【0043】
例えば、第1乗算剰余算器(20)にインターリーブ法による乗算剰余を行う回路を用い、第2乗算剰余算器(30)にモンゴメリ乗算における計算を行う回路を用いると、従来の回路を利用することができるので、回路を容易に構成することができる。したがって乗算剰余演算装置のコストダウン等が可能になる。
【0044】
ところで、第1乗算剰余算器(20)の処理と第2乗算剰余算器(30)の処理とは必ずしも独立している必要はなく、第1剰余算器(20)の処理と第2乗算剰余算器(30)の処理との過程で同期をとって、お互いの中間処理結果をやり取りしつつ処理を行うように各々を構成してもよい。
【発明を実施するための最良の形態】
【0048】
以下に、本発明の実施形態を式及び図面とともに説明する。
(新たに定義した領域における計算方法の説明)
Rをrmとする。ただし、0<m<nで、rmは整数とする。このとき、R=rmはMと互いに素である。
【0049】
この新たに定義した領域における計算を効率よく行う計算方法として、基数をrとした場合について以下に示す。
法をM(rn-1<M<rn、かつ、Mとrとが互いに素)とし、n桁の被乗算X、n桁の乗算Y(0≦X,Y<M)を入力とし、Z=X・Y・r-m mod Mを出力する演算であり、具体的には以下の手順で実行される。
【0050】
ステップ1として、S,Tを0に初期化し、被乗数XをAに代入し、乗数Yをパラメータmにより、上位(n-m)桁のYHと下位m桁のYLとに分割して、各々をBHとBLとに代入する。
【0051】
すなわち、下位BLはm桁、上位BHは(n-m)桁となる。
ステップ2としてAとBHに従来のインターリーブ法を適用して、(n-m)桁分の乗算剰余算を行い、その結果としてSを得る。また、AとBLに従来のモンゴメリ乗算における計算方法を適用して、m桁分の計算を行い、Tを得る。
【0052】
このステップ2のインターリーブ法による乗算剰余算と、モンゴメリ乗算における計算とは並列処理で実行される。
そして、並列処理が終了して、SとTの両者が得られると、ステップ3へ移行する。
【0053】
ステップ3として、Mを法としてSとTとの加算剰余算を行い、出力Zを得る。
このようにして最終的に得られたZが新たに定義した領域での計算結果となる。
以上の手順を式に表すと下記のようになる。
【0054】
入力:M:rn-1<M<rn,gcd(M,r)=1
0≦X,Y<M
出力:Z=X・Y・r-m mod M
演算手順:
ステップ1:A:=X;M:=M;S:=0;T:=0;
H:=YH;BL:=YL (但し、Y=YHm+YL
ステップ2:{S:=Interleaved_modmul(A,BH,M);
T:=Montgomery_modmul(A,BL,M);}
ステップ3:Z:=S+T mod M;
なお、ステップ2の中で、Interleaved_modmul(A,BH,M)は、前述のインターリーブ法による乗算剰余算を示しており、Aは被乗数、BHは乗数、Mは法を示している。
【0055】
また、Montgomery_modmul(A,BL,M)とは、前述のモンゴメリ乗算における計算方法を示しており、Aは被乗数、BLは乗数、Mは法を示している。
また、ステップ2における{ }内の計算は並列に行う。
【0056】
次に、以上に説明した新たに定義した領域における計算において、乗数を上位部分YHと下位部分YLの桁数を同じにした場合、つまりmをn/2とした場合の演算方法について図2を参照しつつ説明する。
【0057】
図2は、新たに定義した領域での計算手順を被乗数Xと乗数Yとが各々8ビットの場合について模式的に示した図である。
ここでは、基数を2とし、基数2の符号付きディジット表現により、すべての加減算を桁上げの伝搬なしに行うものとする。
【0058】
nビットの被乗数X、nビットの乗数Y(0≦X、Y<M)を入力とし、Z=X・Y・2-n/2 mod Mを出力する演算であり、具体的には以下の手順で実行される。
ステップ1として、S,Tを0に初期化し、被乗数XをAに代入する。さらに、乗数Yをパラメータm(=n/2)により、上位のYHと下位のYLとに分割し、各々をBHとBLとに代入する(図2のS110参照)。
【0059】
ステップ2として、nビットのAとn/2ビットのBHに従来のインターリーブ法を適用し、また、Aとn/2ビットのBLに従来のモンゴメリ乗算における計算方法を適用して、各々の計算を並列処理で実行し、各々の計算結果であるSとTとを得る(図2のS112参照)。
【0060】
ここで、上位部分の計算は以下の手順(H1)~(H7)をn/2回繰り返すことにより行われる。
(H1)Sを左(上位)へ1桁シフトする。
【0061】
(H2)シフト後のSの(n+1)番目の桁(シフトした際の桁上がり)、n番目の
桁、(n-1)番目の桁をq1、つまり、q1=[sn+1nn-1]とする。
(H3)q1が0よりも大きければSから法Mを減じて、それを新たなSとし、q1
0よりも小さければSに法Mを加算したものを新たなSとする。
【0062】
(H4)被乗数Aと乗数BHの最上位ビットbn-1との論理積をとり、その結果にSを
加算したものを新たなSとする。
(H5)新たなSの(n+1)番目の桁、n番目の桁、(n-1)番目の桁をq2
つまり、q2=[sn+1nn-1]とする。
【0063】
(H6)q2が0よりも大きければSから法Mを減じて、それを新たなSとし、q2
0よりも小さければSに法Mを加算したものを新たなSとする。
(H7)BHを左へ1ビットシフトする。
【0064】
また、下位部分の演算は以下の手順(L1)~(L4)をn/2回繰り返すことにより行われる。
(L1)被乗数Aと乗数BLの最下位ビットb0との論理積をとり、その結果にTを加
算したものを新たなTとする。
【0065】
(L2)Tの最下位桁t0をq3とする。
(L3)q3が0でなければ、Tに法Mを加算して、それを右へ1桁シフトしたもの を新たなTとする。一方、q3が0であればTを右へ1桁シフトし、それを 新たなTとする。
【0066】
(L4)BLを右へ1ビットシフトする。
以上のように、並列処理で上位部分の乗算剰余算結果Sと下位部分の乗算剰余算結果Tとを得る。
【0067】
次に、ステップ3として、SとTとを加算し、それを新たなSとする(図2のS114参照)。
そして、新たなSの(n+1)番目の桁、n番目の桁、(n-1)番目の桁をq2、つまり、q2=[sn+1nn-1]とする。
【0068】
2が0よりも大きければSから法Mを減じて、それを新たなSとし、q2が0よりも小さければSに法Mを加算したものを新たなSとする。
ステップ4として、Sを周知の演算方法により、基数2の符号付きディジット表現から通常の2進数表現に変換し、その結果を出力Zとする(図2では省略)。
【0069】
ステップ5として、出力Zが0よりも小さければ、出力Zに法Mを加算して、それを出力Zとする(図2のS116参照)。
このようにして最終的に得られた出力Zが乗数Yと被乗数Xとの法Mに基づく新たに定義した領域における乗算剰余算結果となる。
【0070】
以上の手順を式に表すと下記のようになる。

入力:M:2n-1<M<2n、gcd(M、2)=1
X、Y:0≦X,Y<M
出力:Z=X・Y・2-n/2 mod M(0≦Z<M)
演算手順:
ステップ1:A:=X;BH:=YH;BL:=YL;S:=0;T:=0;M:=M;
ステップ2:for i:=1 to n/2
do H and L in parallel
H:do
S:=2・S;
1:=[sn+1nn-1
if q1>0 then S:=S-M
elseif q1<0 then S:=S+M;
S:=S+bn-1・A;
2:=[sn+1nn-1];
if q2>0 then S:=S-M
elseif q2<0 then S:=S+M;
H:=BH<<1;
enddo
L:do
T:=T+b0・Ai
3:=t0
if q3 ≠ 0 then T:=(T+M)>>1
else T:=T>>1;
L:=BL>>1;
enddo
endfor
ステップ3:S:=S+T;
2:=[sn+1nn-1];
if q2>0 then S:=S-M
elseif q2<0 then S:=S+M;
ステップ4:Z:=SD2_to_Binary(S);
ステップ5:if Z<0 then Z:=Z+M;

以上に説明した、基数を2とした場合の新たに定義した領域における計算では、nビットの乗数が同じビット数(n/2)の上位部分と下位部分とに分割され、上位部分はインターリーブ法で乗算剰余算され、下位部分はモンゴメリ乗算における計算方法で計算されている。さらに、その2つの計算は並列処理で、ほぼ同時に実行されている。
【0071】
従って、新たに定義した領域での計算によれば、nビットの乗数全体をインターリーブ法により乗算剰余算する場合の約1/2の時間で実行することができる。
すなわち、通常、処理するビット数が同じであれば、インターリーブ法よりもモンゴメリ乗算における計算の方が高速であるので、インターリーブ法によりn/2ビットの乗算剰余算(つまり、上位部分の乗算剰余算)が終了したときには、モンゴメリ乗算における計算方法によるn/2ビットの計算(つまり、下位部分の計算)は終了している。
【0072】
従って、新たに定義した領域における計算によれば、乗数全体をインターリーブ法によって乗算剰余算を行う場合に比べ、約1/2の演算時間で計算を実行することができるのである。
【0073】
なお、本実施形態では、乗数のビットを上位と下位のビット数を同じ、つまりmをn/2としたが、上位部分と下位部分のビット数が異なるようにしてもよい。
例えば、インターリーブ法とモンゴメリ法との演算速度の違いを考慮すれば、全体の計算時間をより短縮できる分割方法を決定することができる。つまり、インターリーブ法とモンゴメリ乗算における計算方法との演算速度の比がp:qのときには、下位部分のビット数mをおよそ、n・q/(p+q)とすれば、上位部分と下位部分の計算時間がほぼ同じになり、全体の計算時間を短縮することができる。
(乗算剰余演算装置の説明)
次に、上記説明した新たに定義した領域における計算を実行するための乗算剰余演算装置1について図3に従って説明する。
【0074】
図3は、乗算剰余演算装置1の構成を表すブロック図である。
図3に示すように、乗算剰余演算装置1は、主に分割回路10、乗算剰余算回路20、モンゴメリ乗算回路30、加算回路40、剰余算回路50とを備えている。
【0075】
分割回路10は、入力されたr進、n桁の変数Yを上位(n-m)桁のYHと下位m桁のYLとに分割するための回路である。なお、n桁の変数Yを上位部分のYHと下位部分のYLとに分割するためのパラメータmは、分割回路10の内部にあらかじめ設定されていてもよいし、外部から入力されるようになっていてもよい。
【0076】
乗算剰余算回路20は、分割回路10で分割された変数Yの上位(n-m)桁のYHと入力された変数X及び法Mによって
S=X・YH mod M・・・式10
を計算して、Sを加算回路40に出力するための公知の回路である。
【0077】
モンゴメリ乗算回路30は、分割回路10で分割された変数Yの下位m桁のYLと入力された変数X及び法Mによって、モンゴメリ乗算に基づいた計算、
T=X・YL・r-m mod M・・・式20
を実行して、Tを加算回路40に出力するための公知の回路である。
【0078】
加算回路40は、乗算剰余算回路20の出力S、モンゴメリ乗算回路30の出力Tを入力とし、S+Tを計算して出力するための公知の回路である。
剰余算回路50は、加算回路40の出力S+T及び法Mを入力として剰余算を行い、Zを出力するための回路、すなわち、
Z=S+T mod M・・・式30
によりZを出力するための公知の回路である。
【0079】
以上のように構成された乗算剰余演算装置1における計算の流れについて説明する。
乗算剰余演算装置1には、r進、n桁の変数Y、変数X及び法Mが入力される。
入力された変数Yは、分割回路10に入力され、変数Xは、乗算剰余算回路20、モンゴメリ乗算回路30に入力され、法Mは、乗算剰余算回路20、モンゴメリ乗算回路30及び剰余算回路50に入力される。
【0080】
乗算剰余演算装置1に入力された変数Yは、分割回路10に入力され、(n-m)桁の上位部分YHとm桁の下位部分YLとに分割される。
分割された上位部分YHは、乗算剰余算回路20に入力され、変数Xと法Mとで上記式10に従って乗算剰余算が実行され、その結果Sが出力される。
【0081】
一方、分割された下位部分YLは、モンゴメリ乗算回路30に入力され、変数Xと法Mとで上記式20に従ってモンゴメリ乗算に基づく計算が実行され、その結果Tが出力される。
【0082】
そして、乗算剰余算回路20の出力S、モンゴメリ乗算回路30の出力Tが加算回路40に入力されて加算され、その出力と法Mとが剰余算回路50に入力され、上記式30に従って、剰余算が実行され、その結果Zが出力される。
【0083】
このような構成の乗算剰余演算装置1によれば、乗数Yを2分割し、上位部分YHと下位部分YLとに割り当てて各々の乗算剰余算を独立して並列処理で実行している。従って、従来のようにn桁の乗数をそのまま乗算剰余算する演算方法に比べ、少ない時間で乗算剰余算を実行することができる。
【0084】
なお、本実施形態において、分割回路10が分割手段に、乗算剰余算回路20が第1乗算剰余算器に、モンゴメリ乗算回路30が第2乗算剰余器に、加算回路40が加算器に、剰余算回路50が剰余算器に各々相当する。
【0085】
以上、本発明の実施形態について説明したが、本発明は、本実施形態に限定されるものではなく、種々の態様を採ることができる。
例えば、本実施形態では、乗数を分割した上位部分の計算(式4aによるの計算)にインターリーブ法を用い、下位部分の計算(式4bによる計算)にモンゴメリ乗算における計算を用いたが、各計算はそれらに限定されるものではなく、数学的に並列処理できる計算方法であればどのような計算方法であってもよい。
【0086】
また、並列処理の際、式4aと式4bとによる計算は、必ずしも独立している必要はなく、式4aと式4bとによる計算を行っていく過程で同期をとって、お互いの中間計算結果をやり取りしつつ計算を行うようにしてもよい。
【0087】
同様に、乗算剰余算回路20の処理とモンゴメリ乗算回路30の処理とは必ずしも独立している必要はなく、乗算剰余算回路20の処理とモンゴメリ乗算回路30の処理との過程で同期をとって、お互いの中間処理結果をやり取りしつつ処理を行うように各々を構成してもよい。
【0088】
また、乗算剰余演算装置1では、乗除算器50の出力をZとしているが、加算器40の出力を他の回路や装置、例えば、他の乗算剰余算回路に入力して、加算器40の計算結果を基に更なる演算を行うようにしてもよい。
【図面の簡単な説明】
【0089】
【図1】剰余系におけるrを基数とする各変数と新たに定義した領域における表現との関係を示す図である。
【図2】新たに定義した領域における演算手順を被乗数Xと乗数Yとが各々8ビットの場合について模式的に示した図である。
【図3】乗算剰余演算装置1の構成を表すブロック図である。
【符号の説明】
【0090】
1…乗算剰余演算装置、10…分割回路、20…乗算剰余算回路、30…モンゴメリ乗算回路、40…加算回路、50…剰余算回路。
図面
【図1】
0
【図2】
1
【図3】
2