乗算剰余演算器及び情報処理装置
【課題】 回路規模を増大させることなく、演算時間を短縮できる乗算剰余演算器及び情報処理装置を提供する。
【解決手段】 Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、複数のビット数ｑ単位で供給される乗数Ｂ、Ｎの値をBooth法に基づいて変換し、該変換後のＢに対応する被乗数Ａの整数倍の値を選択して出力し、該変換後のＮに対応する被乗数ｕの整数倍の値を選択して出力する論理回路と、論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、桁上げ保存加算器からビット数ｑ単位で出力されるＡ×Ｂ＋ｕ×Ｎの演算結果とビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を乗算剰余演算結果Ｓとして出力する加算器とを有する構成とする。
【解決手段】 Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、複数のビット数ｑ単位で供給される乗数Ｂ、Ｎの値をBooth法に基づいて変換し、該変換後のＢに対応する被乗数Ａの整数倍の値を選択して出力し、該変換後のＮに対応する被乗数ｕの整数倍の値を選択して出力する論理回路と、論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、桁上げ保存加算器からビット数ｑ単位で出力されるＡ×Ｂ＋ｕ×Ｎの演算結果とビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を乗算剰余演算結果Ｓとして出力する加算器とを有する構成とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はべき乗剰余演算を効率よく処理するための乗算剰余演算器及びそれを備えた情報処理装置に関する。
【背景技術】
【０００２】
近年、パーソナルコンピュータやＰＤＡ（Personal Digital(Data) Assistants）あるいは携帯電話機等の各種情報処理装置の処理能力が飛躍的に向上し、さらに各種記録メディアの大容量化や通信インフラストラクチャーの整備が進んだことで、個人情報や企業情報等がネットワークや無線手段を介して送受信される機会が増大している。そのため、それらの情報を秘匿化し第三者への漏洩を防ぐ技術が益々重要になってきている。
【０００３】
送受信データを秘匿化するための一般的な手法としては、データを送受信する端末装置どうしが共通の鍵を用いて該データの暗号化と復号を行う共通鍵暗号方式がよく知られている。さらに、近年ではＢｔｏＢ、ＢｔｏＣ等の電子商取引の拡大に伴ってＰＫＩ（Public Key Infrastructure）技術が注目されている。
【０００４】
ＰＫＩの基本技術である公開鍵暗号方式は、公開鍵を用いて送信データを暗号化し、該公開鍵とペアとなる公開することのない秘密鍵を用いて受信データを復号する方式である。この公開鍵暗号方式は、送信側と受信側で異なる鍵を用い、かつ秘密鍵を通信相手に通知する必要が無いため、上述した共通鍵暗号方式に比べて秘匿化性能が向上する。
【０００５】
公開鍵暗号方式では、現在、ＲＳＡ（Rivest, Shamir Adleman）暗号が主として用いられている（例えば、非特許文献１参照）。ＲＳＡ暗号は、任意の２つの素数を乗算した値Ｎの素因数分解の困難性とＮを法とする数の世界の性質とを利用する暗号化方式であり、暗号化及び復号化のためにべき乗剰余演算（ＭdｍｏｄＮ）を実行する。
【０００６】
べき乗剰余演算は、通常、以下に示す乗算剰余演算の繰り返し処理に置き換えて実行される。
【０００７】
例えば、ｄ＝１９とするとき、Ｃ＝ＭdｍｏｄＮは、
ｄ＝１９＝１＋２×（１＋２×（０＋２×（０＋２×１）））により、
Ｃ＝Ｍ19ｍｏｄＮ
＝Ｍ1+2×(1+2×(0+2×(0+2×1)))ｍｏｄＮ
＝（（（（（Ｍ1）2Ｍ0）2Ｍ0）2Ｍ1）2Ｍ1ｍｏｄＮ
＝（（（Ｍ2）2）2Ｍ）2ＭｍｏｄＮ
となる。このようにｄを分解すれば、Ｍを単純にｄ回掛けるよりも演算回数を低減できるため、演算時間を短縮できる。なお、ｄの分解方法については様々な方法が知られており、上記はその一例を示している。
【０００８】
しかしながら、このような乗算剰余演算も、乗算によって演算桁数が倍になり、さらにその乗算結果をＮで除算するため、ハードウェアまたはソフトウェアのいずれを利用しても効率よく処理するのが非常に困難な演算である。そのため、乗算剰余演算を効率化するための様々な手法が検討され、代表的な例としてモンゴメリ（Montgomery）法と呼ばれるアルゴリズムを応用した演算方法が知られている（例えば、特許文献１参照）。
【０００９】
モンゴメリ法を応用すると、除算を実質的に行わずに乗算と加減算で上記乗算剰余演算が実現可能であり、乗算剰余演算Ｐ（ＡＢ）N＝ＡＢ・ｒ-nｍｏｄＮ＝Ｓは、例えば、以下の（１）〜（８）で示す手順で求めることができる。但し、０≦Ｎ＜ｒn、Ｎは奇数（Ｎとｒは互いに素である）、０≦Ａ＜Ｎ、０≦Ｂ＜Ｎ、Ａ＝Ａn-1Ａn-2…Ａ０（例えばＡ＝Ａ3Ａ2Ａ1Ａ0＝１２３４）である。
（１）ｖ＝−Ｎ-1ｍｏｄｒ
（２）Ｓ＝０
（３）ｆｏｒ ｉ＝０ ｔｏ ｎ−１ ｛
（４） Ｓ＝Ｓ＋Ａi・Ｂ
（５） ｕ＝Ｓ・ｖｍｏｄｒ
（６） Ｓ＝Ｓ＋ｕ・Ｎ
（７） Ｓ＝Ｓ／ｒ
（８）｝
乗算剰余演算は、上記アルゴリズムからＳ＝Ｓ＋Ａi×Ｂ＋ｕ×Ｎ（ｉ＝０〜ｎ−１）の繰り返し演算処理に置き換え可能であり、この処理を実現するための回路である乗算剰余演算器は、例えば図７に示すような構成になる。
【００１０】
図７は従来の乗算剰余演算器の構成を示すブロック図である。
【００１１】
図７に示すように、従来の乗算剰余演算器は、被乗数である上記Ａの値を保持する第１のラッチ回路５１と、被乗数である上記ｕの値を保持する第２のラッチ回路５２と、Ａ＋ｕの値を保持する第３のラッチ回路５３と、１ビット毎に供給される乗数Ｂ、Ｎの値に応じて被乗数Ａ、ｕ、Ａ＋ｕ、または０Ｈ（全ビット０）を選択し出力するセレクタ５７と、セレクタ５７から出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を行う周知の桁上げ保存加算器（Carry Save Adder:以下、ＣＳＡと称す）５６と、ＣＳＡ５６から出力される乗算剰余演算結果Ｓと外部で保持された算出済みの乗算剰余演算結果Ｓとを加算し、該加算結果を乗算剰余演算結果Ｓとして出力する加算器５９とを有する構成である。なお、Ａ、ｕ、及びＡ＋ｕの各値は、例えば不図示の制御部により第１のラッチ回路５１〜第３のラッチ回路５３に供給され、乗数Ｂ、Ｎ、及び０Ｈの各値は、例えば不図示の制御部によりセレクタ５７に供給される。
【００１２】
図７に示す乗算剰余演算器では、乗算剰余演算器の処理ビット長（例えば、512bit）の乗数Ｂ、Ｎがそれぞれ１ビット単位でセレクタ５７に供給される。また、被乗数Ａ、ｕ、Ａ＋ｕは、ＣＳＡ５６の処理ビット長（図７ではｍビット）に対応して、該ビット長単位でラッチ回路に格納され、ＣＳＡ５６に供給される。したがって、例えば乗算剰余演算器の処理ビット長が512bitであり、ＣＳＡ５６の処理ビット長が128bitの場合、図７に示す構成では、被乗数Ａ、ｕ、Ａ＋ｕの選択処理を５１２回繰り返すことでＡ（128bit）×Ｂ(512bit)＋ｕ(128bit)×Ｎ(512bit)の演算が完了し、さらにＡ（128bit）×Ｂ(512bit)＋ｕ(128bit)×Ｎ(512bit)の演算を４回繰り返すことで、Ａ（512bit）×Ｂ(512bit)＋ｕ(512bit)×Ｎ(512bit)の演算処理が完了することになる。
【００１３】
セレクタ５７は、１ビットづつ供給される乗数Ｂ、Ｎの値に応じて、第１のラッチ回路５１〜第３のラッチ回路５３から供給される被乗数Ａ、ｕ、Ａ＋ｕ、または０Ｈを選択しＣＳＡ５６に供給する。ＣＳＡ５６は、セレクタ５７から順次供給される被乗数Ａ、ｕ、Ａ＋ｕまたは０Ｈをシフト加算することでＡ×Ｂ＋ｕ×Ｎを算出し、その中間演算結果を保持しつつ乗算剰余演算結果Ｓを１ビット単位で出力する。
【非特許文献１】三谷政昭著、「やり直しのための工業数学」、第５版、ＣＱ出版社、2003年2月1日、ｐ．１１５−１２２
【特許文献１】特表２００１−５２７６７３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
現在、公開鍵暗号方式では、上記べき乗剰余演算のＣ、Ｍ、Ｎ、ｄに１０２４ビットの数値を用いたＲＳＡ暗号が広く利用され、さらにビット数が増えることも予想される。そのため、暗号化及び復号化に膨大な量の乗算剰余演算を実行しなければならない。公開鍵暗号方式は、暗号化及び復号化に要する処理時間が共通鍵暗号方式に比べて長いことが問題であり、乗算剰余演算に要する演算時間の短縮が重要な課題となっている。
【００１５】
図７に示した従来の乗算剰余演算器では、例えば被乗数を保持するラッチ回路やＣＳＡの処理ビット長を拡張して一度に処理できるビット数を増やせば、繰り返し処理回数が低減するため演算時間が短縮する。しかしながら、ＣＳＡの処理ビット長を拡張すると、ＣＳＡ内部の中間演算結果を保持するレジスタ、被乗数を保存するためのラッチ回路、及びセレクタ回路のビット長が増えるため、乗算剰余演算器の回路規模が増大してしまう問題がある。
【００１６】
市場では、携帯電話機、ＰＤＡ、パーソナルコンピュータやサーバ装置等の情報処理装置の普及に伴い、処理性能が高く、かつ低コストな製品が求められている。したがって、このような要求を満たすためには、乗算剰余演算に要する演算時間を短縮すると共に、回路規模の削減を実現できる乗算剰余演算器が必須となる。
【００１７】
本発明は上記したような従来の技術が有する問題点を解決するためになされたものであり、演算時間をより短縮できる乗算剰余演算器及び情報処理装置を提供することを目的とする。
【００１８】
また、本発明のさらなる目的は、回路規模を増大させることなく演算時間を短縮できる乗算剰余演算器及び情報処理装置を提供することにある。
【課題を解決するための手段】
【００１９】
上記目的を達成するため本発明の乗算剰余演算器は、被乗数をＡ、ｕとし、乗数をＢ、Ｎとし、乗算剰余演算結果をＳとしたとき、Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、
Booth法に基づいて変換された複数のビット数ｑ単位で供給される前記乗数Ｂの値に対応する前記被乗数Ａの整数倍の値を選択して出力し、前記Booth法に基づいて変換された複数のビット数ｑ単位で供給される前記乗数Ｎの値に対応する前記被乗数ｕの整数倍の値を選択して出力する論理回路と、
前記論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数ｑ単位で出力される前記Ａ×Ｂ＋ｕ×Ｎの演算結果と、前記ビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Ｓとして出力する加算器と、
を有する構成である。
【００２０】
または、被乗数をＡ、ｕとし、乗数をＢ、Ｎとし、乗算剰余演算結果をＳとしたとき、Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、
複数のビット数ｑ＋１単位で供給される乗数Ｂの値をBooth法に基づいて変換し、該変換後の値に対応する前記被乗数Ａの整数倍の値を選択して出力し、前記ビット数ｑ＋１単位で供給される前記乗数Ｎの値をBooth法に基づいて変換し、該変換後の値に対応する前記被乗数ｕの整数倍の値を選択して出力する論理回路と、
前記論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数ｑ単位で出力される前記Ａ×Ｂ＋ｕ×Ｎの演算結果と、前記ビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Ｓとして出力する加算器と、
を有する構成である。
【００２１】
一方、本発明の情報処理装置は、上記乗算剰余演算器と、
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
をさらに有する構成である。
【００２２】
上記のように構成された乗算剰余演算器及び情報処理装置では、Booth法に基づいて乗数を変換し、該変換後の値に対応する被乗数の整数倍の値を選択してＣＳＡに供給するため、ＣＳＡの処理ビット長を短縮できる。
【００２３】
また、本発明の乗算剰余演算器及び情報処理装置は、予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
制御部により、前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する構成である。ここで、前記ビット数ｑは２または４であることが望ましい。
【００２４】
上記のような乗算剰余演算器は、ビット数ｑを２または４とすることで、ｕ生成部の回路規模の増大を抑制できる。
【発明の効果】
【００２５】
本発明の乗算剰余演算器及び情報処理装置は、ＣＳＡの処理ビット長を短縮できるため、従来の乗算剰余演算器よりも演算時間を短縮できる。
【００２６】
また、ＣＳＡの処理ビット長を短縮することで、ＣＳＡが備えるフリップフロップ数が低減するため、乗算剰余演算器の回路規模が低減する。特に、ビット数ｑを２または４とすれば、ｕ生成部の回路規模が増大することがないため、回路規模を増大させることなく演算時間を短縮できる。
【発明を実施するための最良の形態】
【００２７】
次に本発明について図面を参照して説明する。
【００２８】
まず、本発明の乗算剰余演算器で利用するBooth法について簡単に説明する。
【００２９】
Booth法とは、２の補数表現を利用することで乗算の演算回数を低減する手法である。例えば、Ａ×０１１１１１の演算を行う場合、通常、Ａ×０１１１１１＝Ａ×０１００００＋Ａ×００１０００＋Ａ×０００１００＋Ａ×００００１０＋Ａ×０００００１を実行するため、５回の演算処理が必要である。しかしながら、上記２の補数表現を利用すると、乗数である０１１１１１を１００００−１で表すことができるため、Ａ×０１１１１１＝Ａ×１００００−１＝Ａ×１０００００−Ａ×０００００１となり、２回の演算処理で済む。
【００３０】
Booth法では、Ａ×Ｂを計算する際に、例えば乗数Ｂを2bit + 重複1bit = 3bit毎に分割し、該分割した乗数Ｂによる部分積を繰り返し実行する。分割した3bitに対応する部分積の値は表１のようになる。なお、図１はBooth法により乗数０１１１１１を２ビット毎に（上記重複1bitを加えると３ビット）変換する際の具体例を示している。
【００３１】
【表１】
【００３２】
乗数を２ビット毎に変換する場合、変換対象である乗数は０、１、２、３のいずれかの値となる（基数４）。一方、Booth法による変換後の乗数は、表１に示したように０、＋１、−１、＋２、−２のいずれかの値となる。
【００３３】
したがって、変換前の乗数（2bit）を用いて乗算を行う場合、乗算結果に対応する値として被乗数の０〜３倍の値をそれぞれ用意する必要がある。例えば、被乗数をＡ、乗数をＢとすると、乗数Ｂが０(0,0)の場合は０、乗数Ｂが１(0,1)の場合は１Ａ、乗数Ｂが２(1,0)の場合は２Ａ、乗数Ｂが３(1,1)の場合は３ＡをＣＳＡへ供給するため、これらの値を予め用意する必要がある。ここで、０及び１Ａは演算処理を必要としない値であり、２Ａは、２進数である１Ａの値を１ビットずつシフトし、最下位ビットに０をセットすればよいため、実質的に演算処理を必要としない値である。しかしながら、３Ａは、１Ａ＋２Ａの値を事前に計算するか、または１Ａ及び２Ａの２つの値をＣＳＡへそれぞれ供給する必要がある。
【００３４】
このような処理でも、被乗数に対して乗数を2bit毎に乗算するため、従来の乗算剰余演算器のように被乗数に対して乗数を1bit毎に乗算する構成（図７参照）に比べて処理時間を短縮できる。しかしながら、１Ａ＋２Ａを事前に計算しておく場合は、そのための加算器が必要になるため回路規模が増大する。一方、１Ａ及び２Ａの２つの値をＣＳＡへ供給する場合は、ＣＳＡへの入力データ数が増大するため、ＣＳＡの回路規模が増大してしまう。
【００３５】
これに対して、Booth法を用いて乗数を変換すると、０、±１、±２倍の被乗数、すなわち、０、±１Ａ、±２ＡのいずれかをＣＳＡへ供給すればよい。このとき、０、１Ａ、２Ａの値は、上述したように実質的な演算処理を必要としないため容易に得ることができる。但し、−１Ａ（−２Ａ）の値は、１Ａ（２Ａ）の値を反転し、１を足すことで表現するため、負の数であることを示すサインビット（1bit）が必要となる。
【００３６】
本発明の乗算剰余演算器は、乗数Ｂ、Ｎのビット列を、所定のビット数毎にBooth法を用いて変換し、変換後の乗数Ｂ、Ｎの値に対応する被乗数Ａ、ｕの整数倍の値（０、±１、±２）を用いてＣＳＡによりＡ×Ｂ＋ｕ×Ｎの演算処理を行う構成である。
【００３７】
図２は本発明の乗算剰余演算器の一構成例を示すブロック図である。
【００３８】
図２に示すように、本発明の乗算剰余演算器は、被乗数Ａの値を保持する第１のラッチ回路１と、被乗数ｕの値を保持する第２のラッチ回路２と、複数ビット（図２では3bit）毎に供給される乗数Ｂの値に対応する被乗数Ａの整数倍の値（０、±１Ａ、±２Ａ）を選択して出力する第１の論理回路（logic1）４と、複数ビット（図２では3bit）毎に供給される乗数Ｎの値に対応する被乗数ｕの整数倍の値（０、±１ｕ、±２ｕ）を選択して出力する第２の論理回路（logic2）５と、第１の論理回路４及び第２の論理回路５から供給される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する周知のＣＳＡ６と、ＣＳＡ６から複数ビット（図２では2bit）単位で出力される乗算剰余演算結果Ｓを保持し、複数ビット（図２では2bit）単位で出力する第１のシフトレジスタ８と、ＣＳＡ６から出力されるＡ×Ｂ＋ｕ×Ｎの演算結果と第１のシフトレジスタ８の出力とを加算し、加算結果を乗算剰余演算結果Ｓとして第１のシフトレジスタ８に再び格納する加算器９と、被乗数ｕの値を生成するためのテーブルが格納されるｕ生成部１０と、被乗数Ａ、ｕの値を第１のラッチ回路１及び第２のラッチ回路２に供給し、乗数Ｂ、Ｎの値を第１及び第２の論理回路４、５に供給すると共に、ＣＳＡ６、第１のシフトレジスタ８及びｕ生成部１０の動作を制御する制御部１１とを有する構成である。
【００３９】
本発明の乗算剰余演算器は、制御部１１による被乗数Ａ、ｕのラッチ回路へのセット、及び乗数Ｂ、Ｎの第１の論理回路４及び第２の論理回路５へのセットを契機に、外部から供給される所定周波数のクロック（CK）にしたがって動作する回路であり、制御部１１は、例えばプログラムにしたがって動作するＣＰＵ、ＤＳＰあるいは論理回路等によって実現される。
【００４０】
このような構成において、本発明の乗算剰余演算器では、被乗数Ａ、ｕが、例えばＣＳＡ６の処理ビット長に対応して複数に分割され、制御部１１により該分割単位で第１及び第２のラッチ回路１、２に格納される。また、第１のラッチ回路１から第１の論理回路４へはＣＳＡ６の処理ビット長に対応してｎビット単位で被乗数Ａが供給され、第２のラッチ回路２から第２の論理回路５へはＣＳＡ６の処理ビット長に対応してｎビット単位で被乗数ｕが供給される。一方、乗数Ｂ、Ｎは、例えば制御部１１から3bit単位で第１及び第２の論理回路４、５に供給される。
【００４１】
なお、乗数Ｂ、Ｎは、例えばシフトレジスタやＲＡＭ等のように、格納されたデータを複数ビット単位で出力できる記憶素子に一旦格納し、該記憶素子から所定の複数ビット単位で第１及び第２の論理回路４、５へ供給してもよい。その場合、記憶素子には、制御部１１により乗算剰余演算器の処理ビット長単位、あるいはそれを複数ビット長毎に分割した分割単位で乗数Ｂ、Ｎが格納される。
【００４２】
また、図２では、乗数Ｂ、Ｎを3bit（2bit+重複1bit）単位で第１及び第２の論理回路４、５に供給する例を示しているが、乗数Ｂ、Ｎの供給単位は4bit以上であってもよい。例えば、基数が１６の場合、乗数Ｂ、Ｎは5bit（4bit+重複1bit）単位で第１及び第２の論理回路４、５に供給される。
【００４３】
第１の論理回路４は、第１のラッチ回路１から供給される被乗数Ａの値を用いて±１Ａ、±２Ａを生成し、3bit毎に供給される乗数ＢをBooth法に基づいて変換し、該変換結果に対応する０、±１Ａ、±２Ａのいずれかを選択し、選択結果をｎ＋４ビット単位でＣＳＡ６へ供給する。また、第２の論理回路５は、第２のラッチ回路２から供給される被乗数ｕの値を用いて±１ｕ、±２ｕを生成し、3bit毎に供給される乗数ＮをBooth法に基づいて変換し、該変換結果に対応する０、±１ｕ、±２ｕのいずれかを選択し、選択結果をｎ＋４ビット単位でＣＳＡ６へ供給する。図２では２つの論理回路を用いて０、±１Ａ、±２Ａ、または０、±１ｕ、±２を選択する例を示しているが、乗数Ｂ、Ｎの値に対応する０、±１Ａ、±２Ａ、または０、±１ｕ、±２を選択できれば、論理回路の数はいくつであってもよい。また、図２では第１の論理回路４及び第２の論理回路５により3bit毎に供給される乗数ＢをBooth法に基づいて変換する例を示しているが、制御部１１により変換後の値を第１の論理回路４及び第２の論理回路５に供給する構成であってもよい。その場合、第１の論理回路４には2bit毎に乗数Ｂが供給され、第２の論理回路５には2bit毎に乗数Ｎが供給される。
【００４４】
第１の論理回路４及び第２の論理回路５から出力される被乗数の選択値がｎ＋４ビット単位となる理由は以下による。
【００４５】
例えば、最初の演算において乗数Ｂ、Ｎの値により２Ａ、２ｕが選択された場合、ＣＳＡ６による演算結果Ｓは、
Ｓ＝２Ａ［n:0］＋２ｕ［n:0］
となる。
【００４６】
このとき、（n+1bit）+(n+1bit)より、演算結果Ｓの桁数は（n+2bit）となる。
【００４７】
この演算結果Ｓのうち、下位２ビットがＣＳＡ６から出力され、残りのｎビットはＣＳＡ６に保存されて次の演算で加算される。
【００４８】
続いて、次の演算において乗数Ｂ、Ｎの値により再び２Ａ、２ｕが選択されると、ＣＳＡ６による演算結果Ｓは、
Ｓ＝２Ａ［n:0］＋２ｕ［n:0］＋Ｓ［n-1:0］
となる。
【００４９】
このとき、演算結果Ｓの桁数は（n+1bit）+(n+1bit)+(nbit)より（n+3bit）となる。
【００５０】
この演算結果Ｓのうち、下位２ビットがＣＳＡ６から出力され、残りのｎ＋１ビットはＣＳＡ６に保存されて次の演算で加算される。
【００５１】
さらに、次の演算において乗数Ｂ、Ｎの値により再び２Ａ、２ｕが選択されると、ＣＳＡ６による演算結果Ｓは、
Ｓ＝２Ａ［n:0］＋２ｕ［n:0］＋Ｓ［n:0］
となる。
【００５２】
このとき、演算結果Ｓの桁数は（n+1bit）+(n+1bit)+(n+1bit)より（n+3bit）となる。
【００５３】
この演算結果Ｓのうち、下位２ビットがＣＳＡ６から出力され、残りのｎ＋１ビットはＣＳＡ６に保存されて次の演算で加算される。以下、同様の演算処理が繰り返され、演算の終了毎に下位２ビットが出力され、ｎ＋１ビットがＣＳＡ６で保存されて次の演算で利用される。このとき、演算結果Ｓの桁数は（n+1bit）+(n+1bit)+(n+1bit)であり、必ず（n+3bit）内に収まる。
【００５４】
したがって、最大値である２Ａ、２ｕが加算される場合を考慮しても演算結果Ｓの桁数は最大でもｎ＋３ビットとなる。但し、負の最大値（−２Ａ、−２ｕ）が繰り返し選択される場合を考慮すると、負の数であることを示すサインビット（1bit）が必要となるため、演算結果Ｓの桁数は合計でｎ＋４ビットになる。よって、第１の論理回路４及び第２の論理回路５からＣＳＡ６に供給する被乗数の選択値も演算結果Ｓの桁数に合わせて最大でｎ＋４ビットとなる。
【００５５】
ＣＳＡ６は、各論理回路から順次供給される値をシフト加算することでＡ×Ｂ、及びｕ×Ｎをそれぞれ算出し、それらの加算結果Ｓを出力する。本発明の乗算剰余演算器が備えるＣＳＡ６は、第１及び第２の論理回路４、５から最大でｎ＋４ビットのデータが供給されるため、このビット拡張に対応する分だけ従来の乗算剰余演算器が備えるＣＳＡよりも処理ビット長が拡張される。ＣＳＡ６は、桁上げ（carry）出力及び加算結果（sum）出力が格納されるシフトレジスタをそれぞれ備え、該シフトレジスタを用いて中間演算結果を保持しつつ演算結果Ｓを複数ビット単位（図２では2bit）で出力する。ＣＳＡ６から出力された演算結果Ｓは、第１のシフトレジスタ８の出力（過去の乗算剰余演算結果Ｓ）と複数ビット単位で加算され、加算結果は第１のシフトレジスタ８に再び格納される。
【００５６】
なお、図２に示した第１のラッチ回路１、第２のラッチ回路２、第１のシフトレジスタ８及びｕ生成部１０は、乗算剰余演算器の内部に備えている必要はなく、乗算剰余演算器を利用する情報処理装置に備えていてもよい。同様に、乗数Ｂ、Ｎの値を一時的に保持する記憶素子を備えている場合、該記憶素子は乗算剰余演算器の内部に備えている必要はなく、乗算剰余演算器を利用する情報処理装置に備えていてもよい。さらに、制御部１１も乗算剰余演算器の内部に備えている必要はなく、乗算剰余演算器を利用する情報処理装置が備える処理装置（ＣＰＵ）によって実現してもよい。すなわち、乗算剰余演算器は、図２の点線内の構成要素のみを備えていればよい。
【００５７】
また、被乗数Ａ、ｕは、ラッチ回路に格納する必要はなく、例えばシフトレジスタやＲＡＭ等のようにデータを一時的に保持できる記憶素子であればどのようなものを用いてもよい。
【００５８】
図３に示すように、本発明の情報処理装置は、例えばパーソナルコンピュータやサーバ装置等のコンピュータシステムであり、プログラムにしたがって所定の処理を実行する処理装置２０と、処理装置２０に対してコマンドや情報等を入力するための入力装置３０と、処理装置２０の処理結果をモニタするための出力装置４０とを有する構成である。
【００５９】
処理装置２０は、ＣＰＵ２１と、ＣＰＵ２１の処理に必要な情報を一時的に記憶する主記憶装置２２と、ＣＰＵ２１に上記制御部１１の処理を実行させるプログラムが記録された記録媒体２３と、処理に必要なデータ等を蓄積するデータ蓄積装置２４と、主記憶装置２２、記録媒体２３、及びデータ蓄積装置２４とのデータ転送を制御するメモリ制御インタフェース部２５と、入力装置３０及び出力装置４０とのインタフェース装置であるＩ／Ｏインタフェース部２６と、図１に示した乗算剰余演算器２７と、ネットワーク等との通信を制御するインタフェースである通信制御装置２８とを備え、それらがバス２９等を介して接続された構成である。なお、処理装置２０には、乗算剰余演算器２７の構成に応じて、被乗数Ａ、ｕを保持するラッチ回路、及び乗数Ｂ、Ｎ、及び演算結果Ｓを保持するシフトレジスタ等を備えていてもよい。
【００６０】
処理装置２０は、記録媒体２３に記録されたプログラムにしたがってＣＰＵ２１により上記制御部１１の処理を実行し、乗算剰余演算器２７を用いてＳ＝Ｓ＋Ａi×Ｂ＋ｕ×Ｎの演算を実行する。なお、記録媒体２３は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。
【００６１】
次に、本発明の乗算剰余演算器の動作について図面を用いて具体的に説明する。
【００６２】
以下では、Ａ、ｕ、Ｂ、Ｎがそれぞれ512bitであり、処理ビット長が64bitのＣＳＡ６を用い、乗数Ｂ、Ｎが3bit単位で第１の論理回路４及び第２の論理回路５へ供給され、第１のシフトレジスタ８が2bit単位で乗算剰余演算結果Ｓを入出力する場合を例にして説明する。また、第１及び第２のラッチ回路１、２には被乗数Ａ、ｕがＣＳＡ６の処理ビット長に合わせて64bit単位で格納されるものとする。
【００６３】
処理ビット長が64bitのＣＳＡ６を用い、乗数Ｂ、Ｎを3bit単位で出力する場合、Ａ、ｕ、Ｂ、Ｎがそれぞれ512bitの乗算剰余演算（512bit×512bit×2-512 mod 512bit）は、64bit×512bit×2-64 mod 512bit（Ａ×Ｂ×2-64 mod Ｎ）の演算を繰り返し実行すればよい。
【００６４】
本発明の乗算剰余演算器では、モンゴメリ法による乗算剰余演算の特徴である、下位ビットが０になることを利用して（ここでは、下位64bitが０Ｈ）、上記Ｓ、Ａ、Ｂ、Ｎの値に対応するｕを予め算出し、ｕ生成部１０にテーブル形式で格納しておく。
【００６５】
例えば、乗数を2bit（重複1bitを除く）単位で出力する場合、ｕの値を以下のようにして求める（但し、Ｎは奇数）。
【００６６】
N[1:0]=01,(S+AiB)[1:0]=00のとき、
S=S+AiB+uN=00となるuは、u[1:0]=00
N[1:0]=01,(S+AiB)[1:0]=01のとき、
S=S+AiB+uN=00となるuは、u[1:0]=11
N[1:0]=01,(S+AiB)[1:0]=10のとき、
S=S+AiB+uN=00となるuは、u[1:0]=10
N[1:0]=01,(S+AiB)[1:0]=11のとき、
S=S+AiB+uN=00となるuは、u[1:0]=01
N[1:0]=11,(S+AiB)[1:0]=00のとき、
S=S+AiB+uN=00となるuは、u[1:0]=00
N[1:0]=11,(S+AiB)[1:0]=01のとき、
S=S+AiB+uN=00となるuは、u[1:0]=01
N[1:0]=11,(S+AiB)[1:0]=10のとき、
S=S+AiB+uN=00となるuは、u[1:0]=10
N[1:0]=11,(S+AiB)[1:0]=11のとき、
S=S+AiB+uN=00となるuは、u[1:0]=11
以上をまとめると、表２のようになる。
【００６７】
【表２】
【００６８】
ここで、Ａ、Ｂ、Ｎはいずれも既知の値であり、Ｓは０Ｈ（演算開始時）または直前の64bit×512bit×2-64 mod 512bitの演算結果を用いるため既知である。なお、Ｎは奇数であるため、N[1:0]=01または11で固定である。したがって、Ａ、Ｂ、及びＳの各値を基に算出した被乗数ｕの値をテーブル形式でｕ生成部１０に格納しておき、制御部１１は該テーブルを参照して被乗数ｕの値を決定する。
【００６９】
本発明の乗算剰余演算器では、まず、制御部１１により、第１のラッチ回路１に被乗数Ａ（512bit）の最下位64bitのデータをセットし、乗数Ｂ（512bit）のデータを第１の論理回路４へ供給し、乗数Ｎ（512bit）のデータを第２の論理回路５へ供給する。
【００７０】
続いて、制御部１１は、64bitの被乗数Ａ、64bitの乗数Ｂ、64bitの乗数Ｎからｕ生成部１０に格納されたテーブルを参照してｕ（64bit分）の値を求め、第２のラッチ回路２に格納する。
【００７１】
制御部１１による第１のラッチ回路１、第２のラッチ回路２、第１の論理回路４及び第２の論理回路５に対する被乗数または乗数のセットが完了すると、乗算剰余演算器はＳ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算を開始する。
【００７２】
乗算剰余演算器は、まず、第１の論理回路４にて、3bitの乗数Ｂの値からBooth法による変換を行い、該変換後の値に対応する０、＋１Ａ（64+4bit）、−１Ａ（64+4bit）、＋２Ａ（64+4bit）または−２Ａ（64+4bit）を選択しＣＳＡ６へ供給する。同様に、乗算剰余演算器は、第２の論理回路５にて、3bitの乗数Ｎの値からBooth法による変換を行い、該変換後の値に対応する０、＋１ｕ（64+4bit）、−１ｕ（64+4bit）、＋２ｕ（64+4bit）または−２ｕ（64+4bit）を選択しＣＳＡ６へ供給する。
【００７３】
ＣＳＡ６は、第１の論理回路４及び第２の論理回路５から順次供給される値を、桁合わせを実行しつつ加算することでＡ×Ｂ、及びｕ×Ｎを算出し、それらの加算結果（乗算剰余演算結果）Ｓを2bit単位で出力する。ＣＳＡ６から出力された演算結果は、第１のシフトレジスタ８の出力と2bit単位で加算器９にて加算され、加算後の値が第１のシフトレジスタ８に再び格納される。以上の処理を乗数Ｂ、Ｎの全てのビットデータに対して繰り返し実行することで、64bit×512bit×2-64 mod 512bitの演算が終了する。但し、この段階ではＣＳＡ６の内部に部分積の演算結果の上位64bitが残っているため、このデータを制御部１１の指示により第１のシフトレジスタ８に格納する。その結果、該記憶素子に64bit×512bit×2-64 mod 512bitの演算結果Ｓが格納される。
【００７４】
乗算剰余演算器は、64bit×512bit×2-64 mod 512bitの演算が完了すると、制御部１１により第１のラッチ回路１に被乗数Ａ（512bit）の次の下位64bitのデータ（最下位から65bit目〜128bit目のデータ）をセットし、上記と同様にｕ生成部１０のテーブルを参照して被乗数ｕの値を求め、求めた値を第２のラッチ回路２に格納した後、再び64bit×512bit×2-64 mod 512bitの演算を開始する。
【００７５】
以降、第１のラッチ回路１に格納される被乗数Ａ（512bit）の全てのビットデータに対して同様の処理を繰り返し実行する。すなわち、上記64bit×512bit×2-64 mod 512bitの演算を８回繰り返す。その結果、本発明の乗算剰余演算器による512bit×512bit×2-512 mod 512bitの演算が終了する。
【００７６】
次に、本発明の乗算剰余演算器の効果について図面を用いて説明する。
【００７７】
図４は乗数を1bit単位で出力する従来の乗算剰余演算器のレイアウト面積及びBooth法を採用する本発明の乗算剰余演算器のレイアウト面積を示すグラフである。また、図５は乗数を1bit単位で出力する従来の乗算剰余演算器の処理クロック数及びBooth法を採用する本発明の乗算剰余演算器の処理クロック数を示すグラフである。
【００７８】
また、図６は乗数を1bit単位で出力する従来の乗算剰余演算器及びBooth法を採用する本発明の乗算剰余演算器の処理クロック数に対するレイアウト面積をそれぞれ示すグラフである。
【００７９】
図４及び図５に示す「1bit」とは乗数を1bit単位で出力する従来の乗算剰余演算器の構成を示し、「Booth 2bit」とはBooth法による変換後の乗数を用いる（基数４）本発明の乗算剰余演算器の構成を示している。また、図４及び図５に示すグラフの横軸（処理性能）は、表３に示すように乗算剰余演算器の処理ビット長（32bit、64bit、128bit、256bit）に対応する、従来の乗算剰余演算器が備えるＣＳＡの処理ビット長と本発明の乗算剰余演算器が備えるＣＳＡの処理ビット長とを示している。本発明の乗算剰余演算器は、乗数を2bit単位で被乗数に掛けるため、処理性能を比較する際には、表３に示すように乗数を1bit単位で被乗数に掛ける従来の乗算剰余演算器に対してＣＳＡの処理ビット長を１／２にしている。なお、表３の各エントリは（ＣＳＡの処理ビット長）＊（出力ビット数）を示している。
【００８０】
【表３】
【００８１】
図４から分かるように、乗算剰余演算器としての処理ビット長が同じである場合、本発明の乗算剰余演算器は、乗数を複数ビット単位で処理できるため、乗数を1bit単位で処理する従来の乗算剰余演算器に比べて回路のレイアウト面積が低減する。これはBooth 2bitとすることでＣＳＡ６の処理ビット長を従来の半分にできるためである。
【００８２】
例えば、乗算剰余演算器の処理ビット長を128bitとした場合、従来の乗算剰余演算器では、ＣＳＡで加算結果（sum）の値と桁上げ(carry)の値をそれぞれ128個ずつ保持する必要があるため、２５６個のフリップフロップ（Data-F/F）が必要になる。
【００８３】
それに対して、Booth 2bitを採用する本発明の乗算剰余演算器が備えるＣＳＡ６では、処理ビット長が従来の半分の64bitで済むため、加算結果（sum）の値と桁上げ(carry)の値を保持するフリップフロップも１２８個で済む。すなわち、Booth法を採用することで複数ビット単位で乗数を処理するため、ＣＳＡ６が備えるフリップフロップの数が大きく削減され、回路規模を低減できる。また、ＣＳＡ６の処理ビット長が短縮することで第１及び第２のラッチ回路や論理回路（従来の構成ではセレクタに相当）のビット長も短縮されるため、乗算剰余演算器としての回路規模が低減する。但し、上述したようにBooth法を採用することでＣＳＡの処理ビット長を拡張する必要があり（基数４の場合、4bit）、さらに第１の論理回路４及び第２の論理回路５による回路規模の増大もあるため、本発明の乗算剰余演算器のレイアウト面積は従来の１／２よりも大きくなる。
【００８４】
一方、図５から分かるように、乗算剰余演算器の処理ビット長が同じである場合、本発明の乗算剰余演算器は、乗数を複数ビット単位で処理するため、乗数を1bit単位で処理する従来の乗算剰余演算器に比べて処理クロック数が少なくなる。これは上述したＣＳＡ６内に残る部分積の演算結果を出力する処理時間の差から生じる結果である。
【００８５】
本発明の乗算剰余演算器では、上述したようにＣＳＡ６の処理ビット長を従来の半分にできるが（基数４の場合）、被乗数を分割して処理するため、乗算剰余演算を複数回繰り返すことになる。そのため、本発明の乗算剰余演算器では、従来の乗算剰余演算器よりも繰り返し演算の回数が増え、ＣＳＡ６内に残る部分積の演算結果を出力する回数も増えてしまう。
【００８６】
しかしながら、本発明の乗算剰余演算器では、ＣＳＡ６の処理ビット長を短縮できることから、ＣＳＡ６内に残る演算結果を出力する処理時間も従来の１／２となる（基数４の場合）。そのため、僅かではあるが、１つのＡ、ｕ、Ｂ、Ｎに対する乗算剰余演算の処理時間は従来よりも低減する。
【００８７】
本発明の乗算剰余演算器は、処理時間の大幅な低減は実現できないが、多数の数字の配列に対して大きな値のべき乗剰余演算を行うＲＳＡによる暗号化及び復号に本発明の乗算剰余演算器を用いる場合は、この僅かな処理時間の向上が非常に有益となる。
【００８８】
図６に示すように、Booth法を採用する本発明の乗算剰余演算器は、乗数を1bit単位で出力する従来の乗算剰余演算器に比べて、回路規模が少なく、かつ高速な処理を実現できることが分かる。
【００８９】
なお、参考までに、Booth法を採用する本発明の乗算剰余演算器の基数を増やした場合の回路規模の増大量を表４及び表５に示す。本発明の乗算剰余演算器では、基数が１６の場合、乗数Ｂ、Ｎは4bit毎に処理されるため、ＣＳＡ６のビット幅が同じ場合、処理性能は従来の乗算剰余演算器の４倍になる。なお、表４及び表５の各エントリ内の数字の単位は[ｍｍ2]である。
【００９０】
【表４】
【００９１】
表４に示すように、Booth法を採用する本発明の乗算剰余演算器は、基数４、１６共にほぼ同じ回路規模で構成され、従来の乗算剰余演算器と比較してレイアウト面積が約３０％削減されることが分かる。
【００９２】
【表５】
【００９３】
表５に示すように、Booth法を採用する本発明の乗算剰余演算器は、従来の乗算剰余演算器に比べて、基数４の場合、処理速度は約２倍になるがレイアウト面積は１．３倍程度で済む。また、基数１６の場合、処理速度は約４倍になるがレイアウト面積は２．６倍程度で済む。
【００９４】
ところで、被乗数ｕは、乗数Ｂ、Ｎの出力ビット数をｑとすると、上記モンゴメリ法を応用したアルゴリズムの（１）、（５）から以下の式で算出できる。
【００９５】
ｖ＝−Ｎ-1ｍｏｄ２q
ｕ＝Ｓｖｍｏｄ２q
ここで、ｖは演算開始時に一度だけ計算する値である。なお、ｒに代えて２qとしているのはｒを２進数で表したためである。
【００９６】
ｑ＝１となる従来の乗算剰余演算器では、Ｎが奇数であることからｖ＝１となるため、ｕ＝Ｓｍｏｄ２＝Ｓ［０］となり、被乗数ｕはＳの下位ビットに等しくなる。したがって、被乗数ｕを実施的に計算する必要はない。
【００９７】
しかしながら、ｑ＞１となる本発明の乗算剰余演算器では、ｕ＝Ｓ［０］が成立しないため、上記２つの演算が必要になる。但し、ｑの値が小さい場合（例えば、ｑ＝２、４）は、ｖ、ｕも2bitまたは4bitであり、その演算に必要なＮ、Ｓも2bitまたは4bitである。そのため、本発明ではＡ、Ｂ、Ｓ、Ｎの値から予めｕの値を算出してテーブルを作成しておき、該テーブルを参照することで第２のラッチ回路２に格納するｕを決定している。
【００９８】
Booth法による乗数の変換に用いる基数の値を大きくしｑの値を増やせば、ＣＳＡ６の処理ビット長をさらに短縮できるため、乗算剰余演算の処理時間をさらに短縮することができる。
【００９９】
しかしながら、ｑ＞４の場合、すなわち乗数Ｂ、Ｎを８ビット以上で出力する（基数６４以上）構成では、被乗数ｕをテーブル内から選択するために必要な、例えばデコーダ等の回路規模が増大するため、記憶素子を含むｕ生成部１０の回路規模が増大し、上述したＣＳＡ６の処理ビット長を短縮することによる乗算剰余演算器の回路規模の低減効果を相殺してしまう。
【０１００】
表６にｑの値に対するｕ生成部１０のレイアウト面積（単位：ｍｍ2）を示し、表７にｑの値に対するＣＳＡとｕ生成部とを含む総レイアウト面積（単位：ｍｍ2）を示す。
【０１０１】
【表６】
【０１０２】
【表７】
【０１０３】
表６及び表７から分かるように、例えばＣＳＡの処理ビット長を256bitとしたとき、ｑ＝１のときの総レイアウト面積に対して、ＣＳＡの処理ビット長を128bitにできるｑ＝２の場合（基数４）及びＣＳＡの処理ビット長を64bitにできるｑ＝４の場合（基数１６）の総レイアウト面積は低減する。しかしながら、ｑ＝８（基数６４）にすると総レイアウト面積が増大してしまう。
【０１０４】
したがって、本発明の乗算剰余演算器では、ｑの値が２または４であることが回路規模の増大を抑制しつつ演算時間を短縮できるために望ましい。但し、回路規模よりも演算時間の向上を優先する場合は、ｑの値を８以上に設定してもよい。その場合、ｑの値はｕ生成部１０のレイアウト面積の増大を考慮しつつ最適な値を選択すればよい。
【図面の簡単な説明】
【０１０５】
【図１】Booth法による乗数の具体的な変換例を示す模式図である。
【図２】本発明の乗算剰余演算器の一構成例を示すブロック図である。
【図３】本発明の情報処理装置の一構成例を示すブロック図である。
【図４】本発明の乗算剰余演算器のレイアウト面積を示すグラフである。
【図５】本発明の乗算剰余演算器の処理クロック数を示すグラフである。
【図６】本発明の乗算剰余演算器の処理クロック数に対するレイアウト面積の関係を示すグラフである。
【図７】従来の乗算剰余演算器の構成を示すブロック図である。
【符号の説明】
【０１０６】
１ 第１のラッチ回路
２ 第２のラッチ回路
４ 第１の論理回路
５ 第２の論理回路
６ ＣＳＡ
８ 第１のシフトレジスタ
９ 加算器
１０ ｕ生成部
１１ 制御部
２０ 処理装置
２１ ＣＰＵ
２２ 主記憶装置
２３ 記録媒体
２４ データ蓄積装置
２５ メモリ制御インタフェース部
２６ Ｉ／Ｏインタフェース部
２７ 乗算剰余演算器
２８ 通信制御装置
２９ バス
３０ 入力装置
４０ 出力装置
【技術分野】
【０００１】
本発明はべき乗剰余演算を効率よく処理するための乗算剰余演算器及びそれを備えた情報処理装置に関する。
【背景技術】
【０００２】
近年、パーソナルコンピュータやＰＤＡ（Personal Digital(Data) Assistants）あるいは携帯電話機等の各種情報処理装置の処理能力が飛躍的に向上し、さらに各種記録メディアの大容量化や通信インフラストラクチャーの整備が進んだことで、個人情報や企業情報等がネットワークや無線手段を介して送受信される機会が増大している。そのため、それらの情報を秘匿化し第三者への漏洩を防ぐ技術が益々重要になってきている。
【０００３】
送受信データを秘匿化するための一般的な手法としては、データを送受信する端末装置どうしが共通の鍵を用いて該データの暗号化と復号を行う共通鍵暗号方式がよく知られている。さらに、近年ではＢｔｏＢ、ＢｔｏＣ等の電子商取引の拡大に伴ってＰＫＩ（Public Key Infrastructure）技術が注目されている。
【０００４】
ＰＫＩの基本技術である公開鍵暗号方式は、公開鍵を用いて送信データを暗号化し、該公開鍵とペアとなる公開することのない秘密鍵を用いて受信データを復号する方式である。この公開鍵暗号方式は、送信側と受信側で異なる鍵を用い、かつ秘密鍵を通信相手に通知する必要が無いため、上述した共通鍵暗号方式に比べて秘匿化性能が向上する。
【０００５】
公開鍵暗号方式では、現在、ＲＳＡ（Rivest, Shamir Adleman）暗号が主として用いられている（例えば、非特許文献１参照）。ＲＳＡ暗号は、任意の２つの素数を乗算した値Ｎの素因数分解の困難性とＮを法とする数の世界の性質とを利用する暗号化方式であり、暗号化及び復号化のためにべき乗剰余演算（ＭdｍｏｄＮ）を実行する。
【０００６】
べき乗剰余演算は、通常、以下に示す乗算剰余演算の繰り返し処理に置き換えて実行される。
【０００７】
例えば、ｄ＝１９とするとき、Ｃ＝ＭdｍｏｄＮは、
ｄ＝１９＝１＋２×（１＋２×（０＋２×（０＋２×１）））により、
Ｃ＝Ｍ19ｍｏｄＮ
＝Ｍ1+2×(1+2×(0+2×(0+2×1)))ｍｏｄＮ
＝（（（（（Ｍ1）2Ｍ0）2Ｍ0）2Ｍ1）2Ｍ1ｍｏｄＮ
＝（（（Ｍ2）2）2Ｍ）2ＭｍｏｄＮ
となる。このようにｄを分解すれば、Ｍを単純にｄ回掛けるよりも演算回数を低減できるため、演算時間を短縮できる。なお、ｄの分解方法については様々な方法が知られており、上記はその一例を示している。
【０００８】
しかしながら、このような乗算剰余演算も、乗算によって演算桁数が倍になり、さらにその乗算結果をＮで除算するため、ハードウェアまたはソフトウェアのいずれを利用しても効率よく処理するのが非常に困難な演算である。そのため、乗算剰余演算を効率化するための様々な手法が検討され、代表的な例としてモンゴメリ（Montgomery）法と呼ばれるアルゴリズムを応用した演算方法が知られている（例えば、特許文献１参照）。
【０００９】
モンゴメリ法を応用すると、除算を実質的に行わずに乗算と加減算で上記乗算剰余演算が実現可能であり、乗算剰余演算Ｐ（ＡＢ）N＝ＡＢ・ｒ-nｍｏｄＮ＝Ｓは、例えば、以下の（１）〜（８）で示す手順で求めることができる。但し、０≦Ｎ＜ｒn、Ｎは奇数（Ｎとｒは互いに素である）、０≦Ａ＜Ｎ、０≦Ｂ＜Ｎ、Ａ＝Ａn-1Ａn-2…Ａ０（例えばＡ＝Ａ3Ａ2Ａ1Ａ0＝１２３４）である。
（１）ｖ＝−Ｎ-1ｍｏｄｒ
（２）Ｓ＝０
（３）ｆｏｒ ｉ＝０ ｔｏ ｎ−１ ｛
（４） Ｓ＝Ｓ＋Ａi・Ｂ
（５） ｕ＝Ｓ・ｖｍｏｄｒ
（６） Ｓ＝Ｓ＋ｕ・Ｎ
（７） Ｓ＝Ｓ／ｒ
（８）｝
乗算剰余演算は、上記アルゴリズムからＳ＝Ｓ＋Ａi×Ｂ＋ｕ×Ｎ（ｉ＝０〜ｎ−１）の繰り返し演算処理に置き換え可能であり、この処理を実現するための回路である乗算剰余演算器は、例えば図７に示すような構成になる。
【００１０】
図７は従来の乗算剰余演算器の構成を示すブロック図である。
【００１１】
図７に示すように、従来の乗算剰余演算器は、被乗数である上記Ａの値を保持する第１のラッチ回路５１と、被乗数である上記ｕの値を保持する第２のラッチ回路５２と、Ａ＋ｕの値を保持する第３のラッチ回路５３と、１ビット毎に供給される乗数Ｂ、Ｎの値に応じて被乗数Ａ、ｕ、Ａ＋ｕ、または０Ｈ（全ビット０）を選択し出力するセレクタ５７と、セレクタ５７から出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を行う周知の桁上げ保存加算器（Carry Save Adder:以下、ＣＳＡと称す）５６と、ＣＳＡ５６から出力される乗算剰余演算結果Ｓと外部で保持された算出済みの乗算剰余演算結果Ｓとを加算し、該加算結果を乗算剰余演算結果Ｓとして出力する加算器５９とを有する構成である。なお、Ａ、ｕ、及びＡ＋ｕの各値は、例えば不図示の制御部により第１のラッチ回路５１〜第３のラッチ回路５３に供給され、乗数Ｂ、Ｎ、及び０Ｈの各値は、例えば不図示の制御部によりセレクタ５７に供給される。
【００１２】
図７に示す乗算剰余演算器では、乗算剰余演算器の処理ビット長（例えば、512bit）の乗数Ｂ、Ｎがそれぞれ１ビット単位でセレクタ５７に供給される。また、被乗数Ａ、ｕ、Ａ＋ｕは、ＣＳＡ５６の処理ビット長（図７ではｍビット）に対応して、該ビット長単位でラッチ回路に格納され、ＣＳＡ５６に供給される。したがって、例えば乗算剰余演算器の処理ビット長が512bitであり、ＣＳＡ５６の処理ビット長が128bitの場合、図７に示す構成では、被乗数Ａ、ｕ、Ａ＋ｕの選択処理を５１２回繰り返すことでＡ（128bit）×Ｂ(512bit)＋ｕ(128bit)×Ｎ(512bit)の演算が完了し、さらにＡ（128bit）×Ｂ(512bit)＋ｕ(128bit)×Ｎ(512bit)の演算を４回繰り返すことで、Ａ（512bit）×Ｂ(512bit)＋ｕ(512bit)×Ｎ(512bit)の演算処理が完了することになる。
【００１３】
セレクタ５７は、１ビットづつ供給される乗数Ｂ、Ｎの値に応じて、第１のラッチ回路５１〜第３のラッチ回路５３から供給される被乗数Ａ、ｕ、Ａ＋ｕ、または０Ｈを選択しＣＳＡ５６に供給する。ＣＳＡ５６は、セレクタ５７から順次供給される被乗数Ａ、ｕ、Ａ＋ｕまたは０Ｈをシフト加算することでＡ×Ｂ＋ｕ×Ｎを算出し、その中間演算結果を保持しつつ乗算剰余演算結果Ｓを１ビット単位で出力する。
【非特許文献１】三谷政昭著、「やり直しのための工業数学」、第５版、ＣＱ出版社、2003年2月1日、ｐ．１１５−１２２
【特許文献１】特表２００１−５２７６７３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
現在、公開鍵暗号方式では、上記べき乗剰余演算のＣ、Ｍ、Ｎ、ｄに１０２４ビットの数値を用いたＲＳＡ暗号が広く利用され、さらにビット数が増えることも予想される。そのため、暗号化及び復号化に膨大な量の乗算剰余演算を実行しなければならない。公開鍵暗号方式は、暗号化及び復号化に要する処理時間が共通鍵暗号方式に比べて長いことが問題であり、乗算剰余演算に要する演算時間の短縮が重要な課題となっている。
【００１５】
図７に示した従来の乗算剰余演算器では、例えば被乗数を保持するラッチ回路やＣＳＡの処理ビット長を拡張して一度に処理できるビット数を増やせば、繰り返し処理回数が低減するため演算時間が短縮する。しかしながら、ＣＳＡの処理ビット長を拡張すると、ＣＳＡ内部の中間演算結果を保持するレジスタ、被乗数を保存するためのラッチ回路、及びセレクタ回路のビット長が増えるため、乗算剰余演算器の回路規模が増大してしまう問題がある。
【００１６】
市場では、携帯電話機、ＰＤＡ、パーソナルコンピュータやサーバ装置等の情報処理装置の普及に伴い、処理性能が高く、かつ低コストな製品が求められている。したがって、このような要求を満たすためには、乗算剰余演算に要する演算時間を短縮すると共に、回路規模の削減を実現できる乗算剰余演算器が必須となる。
【００１７】
本発明は上記したような従来の技術が有する問題点を解決するためになされたものであり、演算時間をより短縮できる乗算剰余演算器及び情報処理装置を提供することを目的とする。
【００１８】
また、本発明のさらなる目的は、回路規模を増大させることなく演算時間を短縮できる乗算剰余演算器及び情報処理装置を提供することにある。
【課題を解決するための手段】
【００１９】
上記目的を達成するため本発明の乗算剰余演算器は、被乗数をＡ、ｕとし、乗数をＢ、Ｎとし、乗算剰余演算結果をＳとしたとき、Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、
Booth法に基づいて変換された複数のビット数ｑ単位で供給される前記乗数Ｂの値に対応する前記被乗数Ａの整数倍の値を選択して出力し、前記Booth法に基づいて変換された複数のビット数ｑ単位で供給される前記乗数Ｎの値に対応する前記被乗数ｕの整数倍の値を選択して出力する論理回路と、
前記論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数ｑ単位で出力される前記Ａ×Ｂ＋ｕ×Ｎの演算結果と、前記ビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Ｓとして出力する加算器と、
を有する構成である。
【００２０】
または、被乗数をＡ、ｕとし、乗数をＢ、Ｎとし、乗算剰余演算結果をＳとしたとき、Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、
複数のビット数ｑ＋１単位で供給される乗数Ｂの値をBooth法に基づいて変換し、該変換後の値に対応する前記被乗数Ａの整数倍の値を選択して出力し、前記ビット数ｑ＋１単位で供給される前記乗数Ｎの値をBooth法に基づいて変換し、該変換後の値に対応する前記被乗数ｕの整数倍の値を選択して出力する論理回路と、
前記論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数ｑ単位で出力される前記Ａ×Ｂ＋ｕ×Ｎの演算結果と、前記ビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Ｓとして出力する加算器と、
を有する構成である。
【００２１】
一方、本発明の情報処理装置は、上記乗算剰余演算器と、
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
をさらに有する構成である。
【００２２】
上記のように構成された乗算剰余演算器及び情報処理装置では、Booth法に基づいて乗数を変換し、該変換後の値に対応する被乗数の整数倍の値を選択してＣＳＡに供給するため、ＣＳＡの処理ビット長を短縮できる。
【００２３】
また、本発明の乗算剰余演算器及び情報処理装置は、予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
制御部により、前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する構成である。ここで、前記ビット数ｑは２または４であることが望ましい。
【００２４】
上記のような乗算剰余演算器は、ビット数ｑを２または４とすることで、ｕ生成部の回路規模の増大を抑制できる。
【発明の効果】
【００２５】
本発明の乗算剰余演算器及び情報処理装置は、ＣＳＡの処理ビット長を短縮できるため、従来の乗算剰余演算器よりも演算時間を短縮できる。
【００２６】
また、ＣＳＡの処理ビット長を短縮することで、ＣＳＡが備えるフリップフロップ数が低減するため、乗算剰余演算器の回路規模が低減する。特に、ビット数ｑを２または４とすれば、ｕ生成部の回路規模が増大することがないため、回路規模を増大させることなく演算時間を短縮できる。
【発明を実施するための最良の形態】
【００２７】
次に本発明について図面を参照して説明する。
【００２８】
まず、本発明の乗算剰余演算器で利用するBooth法について簡単に説明する。
【００２９】
Booth法とは、２の補数表現を利用することで乗算の演算回数を低減する手法である。例えば、Ａ×０１１１１１の演算を行う場合、通常、Ａ×０１１１１１＝Ａ×０１００００＋Ａ×００１０００＋Ａ×０００１００＋Ａ×００００１０＋Ａ×０００００１を実行するため、５回の演算処理が必要である。しかしながら、上記２の補数表現を利用すると、乗数である０１１１１１を１００００−１で表すことができるため、Ａ×０１１１１１＝Ａ×１００００−１＝Ａ×１０００００−Ａ×０００００１となり、２回の演算処理で済む。
【００３０】
Booth法では、Ａ×Ｂを計算する際に、例えば乗数Ｂを2bit + 重複1bit = 3bit毎に分割し、該分割した乗数Ｂによる部分積を繰り返し実行する。分割した3bitに対応する部分積の値は表１のようになる。なお、図１はBooth法により乗数０１１１１１を２ビット毎に（上記重複1bitを加えると３ビット）変換する際の具体例を示している。
【００３１】
【表１】
【００３２】
乗数を２ビット毎に変換する場合、変換対象である乗数は０、１、２、３のいずれかの値となる（基数４）。一方、Booth法による変換後の乗数は、表１に示したように０、＋１、−１、＋２、−２のいずれかの値となる。
【００３３】
したがって、変換前の乗数（2bit）を用いて乗算を行う場合、乗算結果に対応する値として被乗数の０〜３倍の値をそれぞれ用意する必要がある。例えば、被乗数をＡ、乗数をＢとすると、乗数Ｂが０(0,0)の場合は０、乗数Ｂが１(0,1)の場合は１Ａ、乗数Ｂが２(1,0)の場合は２Ａ、乗数Ｂが３(1,1)の場合は３ＡをＣＳＡへ供給するため、これらの値を予め用意する必要がある。ここで、０及び１Ａは演算処理を必要としない値であり、２Ａは、２進数である１Ａの値を１ビットずつシフトし、最下位ビットに０をセットすればよいため、実質的に演算処理を必要としない値である。しかしながら、３Ａは、１Ａ＋２Ａの値を事前に計算するか、または１Ａ及び２Ａの２つの値をＣＳＡへそれぞれ供給する必要がある。
【００３４】
このような処理でも、被乗数に対して乗数を2bit毎に乗算するため、従来の乗算剰余演算器のように被乗数に対して乗数を1bit毎に乗算する構成（図７参照）に比べて処理時間を短縮できる。しかしながら、１Ａ＋２Ａを事前に計算しておく場合は、そのための加算器が必要になるため回路規模が増大する。一方、１Ａ及び２Ａの２つの値をＣＳＡへ供給する場合は、ＣＳＡへの入力データ数が増大するため、ＣＳＡの回路規模が増大してしまう。
【００３５】
これに対して、Booth法を用いて乗数を変換すると、０、±１、±２倍の被乗数、すなわち、０、±１Ａ、±２ＡのいずれかをＣＳＡへ供給すればよい。このとき、０、１Ａ、２Ａの値は、上述したように実質的な演算処理を必要としないため容易に得ることができる。但し、−１Ａ（−２Ａ）の値は、１Ａ（２Ａ）の値を反転し、１を足すことで表現するため、負の数であることを示すサインビット（1bit）が必要となる。
【００３６】
本発明の乗算剰余演算器は、乗数Ｂ、Ｎのビット列を、所定のビット数毎にBooth法を用いて変換し、変換後の乗数Ｂ、Ｎの値に対応する被乗数Ａ、ｕの整数倍の値（０、±１、±２）を用いてＣＳＡによりＡ×Ｂ＋ｕ×Ｎの演算処理を行う構成である。
【００３７】
図２は本発明の乗算剰余演算器の一構成例を示すブロック図である。
【００３８】
図２に示すように、本発明の乗算剰余演算器は、被乗数Ａの値を保持する第１のラッチ回路１と、被乗数ｕの値を保持する第２のラッチ回路２と、複数ビット（図２では3bit）毎に供給される乗数Ｂの値に対応する被乗数Ａの整数倍の値（０、±１Ａ、±２Ａ）を選択して出力する第１の論理回路（logic1）４と、複数ビット（図２では3bit）毎に供給される乗数Ｎの値に対応する被乗数ｕの整数倍の値（０、±１ｕ、±２ｕ）を選択して出力する第２の論理回路（logic2）５と、第１の論理回路４及び第２の論理回路５から供給される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する周知のＣＳＡ６と、ＣＳＡ６から複数ビット（図２では2bit）単位で出力される乗算剰余演算結果Ｓを保持し、複数ビット（図２では2bit）単位で出力する第１のシフトレジスタ８と、ＣＳＡ６から出力されるＡ×Ｂ＋ｕ×Ｎの演算結果と第１のシフトレジスタ８の出力とを加算し、加算結果を乗算剰余演算結果Ｓとして第１のシフトレジスタ８に再び格納する加算器９と、被乗数ｕの値を生成するためのテーブルが格納されるｕ生成部１０と、被乗数Ａ、ｕの値を第１のラッチ回路１及び第２のラッチ回路２に供給し、乗数Ｂ、Ｎの値を第１及び第２の論理回路４、５に供給すると共に、ＣＳＡ６、第１のシフトレジスタ８及びｕ生成部１０の動作を制御する制御部１１とを有する構成である。
【００３９】
本発明の乗算剰余演算器は、制御部１１による被乗数Ａ、ｕのラッチ回路へのセット、及び乗数Ｂ、Ｎの第１の論理回路４及び第２の論理回路５へのセットを契機に、外部から供給される所定周波数のクロック（CK）にしたがって動作する回路であり、制御部１１は、例えばプログラムにしたがって動作するＣＰＵ、ＤＳＰあるいは論理回路等によって実現される。
【００４０】
このような構成において、本発明の乗算剰余演算器では、被乗数Ａ、ｕが、例えばＣＳＡ６の処理ビット長に対応して複数に分割され、制御部１１により該分割単位で第１及び第２のラッチ回路１、２に格納される。また、第１のラッチ回路１から第１の論理回路４へはＣＳＡ６の処理ビット長に対応してｎビット単位で被乗数Ａが供給され、第２のラッチ回路２から第２の論理回路５へはＣＳＡ６の処理ビット長に対応してｎビット単位で被乗数ｕが供給される。一方、乗数Ｂ、Ｎは、例えば制御部１１から3bit単位で第１及び第２の論理回路４、５に供給される。
【００４１】
なお、乗数Ｂ、Ｎは、例えばシフトレジスタやＲＡＭ等のように、格納されたデータを複数ビット単位で出力できる記憶素子に一旦格納し、該記憶素子から所定の複数ビット単位で第１及び第２の論理回路４、５へ供給してもよい。その場合、記憶素子には、制御部１１により乗算剰余演算器の処理ビット長単位、あるいはそれを複数ビット長毎に分割した分割単位で乗数Ｂ、Ｎが格納される。
【００４２】
また、図２では、乗数Ｂ、Ｎを3bit（2bit+重複1bit）単位で第１及び第２の論理回路４、５に供給する例を示しているが、乗数Ｂ、Ｎの供給単位は4bit以上であってもよい。例えば、基数が１６の場合、乗数Ｂ、Ｎは5bit（4bit+重複1bit）単位で第１及び第２の論理回路４、５に供給される。
【００４３】
第１の論理回路４は、第１のラッチ回路１から供給される被乗数Ａの値を用いて±１Ａ、±２Ａを生成し、3bit毎に供給される乗数ＢをBooth法に基づいて変換し、該変換結果に対応する０、±１Ａ、±２Ａのいずれかを選択し、選択結果をｎ＋４ビット単位でＣＳＡ６へ供給する。また、第２の論理回路５は、第２のラッチ回路２から供給される被乗数ｕの値を用いて±１ｕ、±２ｕを生成し、3bit毎に供給される乗数ＮをBooth法に基づいて変換し、該変換結果に対応する０、±１ｕ、±２ｕのいずれかを選択し、選択結果をｎ＋４ビット単位でＣＳＡ６へ供給する。図２では２つの論理回路を用いて０、±１Ａ、±２Ａ、または０、±１ｕ、±２を選択する例を示しているが、乗数Ｂ、Ｎの値に対応する０、±１Ａ、±２Ａ、または０、±１ｕ、±２を選択できれば、論理回路の数はいくつであってもよい。また、図２では第１の論理回路４及び第２の論理回路５により3bit毎に供給される乗数ＢをBooth法に基づいて変換する例を示しているが、制御部１１により変換後の値を第１の論理回路４及び第２の論理回路５に供給する構成であってもよい。その場合、第１の論理回路４には2bit毎に乗数Ｂが供給され、第２の論理回路５には2bit毎に乗数Ｎが供給される。
【００４４】
第１の論理回路４及び第２の論理回路５から出力される被乗数の選択値がｎ＋４ビット単位となる理由は以下による。
【００４５】
例えば、最初の演算において乗数Ｂ、Ｎの値により２Ａ、２ｕが選択された場合、ＣＳＡ６による演算結果Ｓは、
Ｓ＝２Ａ［n:0］＋２ｕ［n:0］
となる。
【００４６】
このとき、（n+1bit）+(n+1bit)より、演算結果Ｓの桁数は（n+2bit）となる。
【００４７】
この演算結果Ｓのうち、下位２ビットがＣＳＡ６から出力され、残りのｎビットはＣＳＡ６に保存されて次の演算で加算される。
【００４８】
続いて、次の演算において乗数Ｂ、Ｎの値により再び２Ａ、２ｕが選択されると、ＣＳＡ６による演算結果Ｓは、
Ｓ＝２Ａ［n:0］＋２ｕ［n:0］＋Ｓ［n-1:0］
となる。
【００４９】
このとき、演算結果Ｓの桁数は（n+1bit）+(n+1bit)+(nbit)より（n+3bit）となる。
【００５０】
この演算結果Ｓのうち、下位２ビットがＣＳＡ６から出力され、残りのｎ＋１ビットはＣＳＡ６に保存されて次の演算で加算される。
【００５１】
さらに、次の演算において乗数Ｂ、Ｎの値により再び２Ａ、２ｕが選択されると、ＣＳＡ６による演算結果Ｓは、
Ｓ＝２Ａ［n:0］＋２ｕ［n:0］＋Ｓ［n:0］
となる。
【００５２】
このとき、演算結果Ｓの桁数は（n+1bit）+(n+1bit)+(n+1bit)より（n+3bit）となる。
【００５３】
この演算結果Ｓのうち、下位２ビットがＣＳＡ６から出力され、残りのｎ＋１ビットはＣＳＡ６に保存されて次の演算で加算される。以下、同様の演算処理が繰り返され、演算の終了毎に下位２ビットが出力され、ｎ＋１ビットがＣＳＡ６で保存されて次の演算で利用される。このとき、演算結果Ｓの桁数は（n+1bit）+(n+1bit)+(n+1bit)であり、必ず（n+3bit）内に収まる。
【００５４】
したがって、最大値である２Ａ、２ｕが加算される場合を考慮しても演算結果Ｓの桁数は最大でもｎ＋３ビットとなる。但し、負の最大値（−２Ａ、−２ｕ）が繰り返し選択される場合を考慮すると、負の数であることを示すサインビット（1bit）が必要となるため、演算結果Ｓの桁数は合計でｎ＋４ビットになる。よって、第１の論理回路４及び第２の論理回路５からＣＳＡ６に供給する被乗数の選択値も演算結果Ｓの桁数に合わせて最大でｎ＋４ビットとなる。
【００５５】
ＣＳＡ６は、各論理回路から順次供給される値をシフト加算することでＡ×Ｂ、及びｕ×Ｎをそれぞれ算出し、それらの加算結果Ｓを出力する。本発明の乗算剰余演算器が備えるＣＳＡ６は、第１及び第２の論理回路４、５から最大でｎ＋４ビットのデータが供給されるため、このビット拡張に対応する分だけ従来の乗算剰余演算器が備えるＣＳＡよりも処理ビット長が拡張される。ＣＳＡ６は、桁上げ（carry）出力及び加算結果（sum）出力が格納されるシフトレジスタをそれぞれ備え、該シフトレジスタを用いて中間演算結果を保持しつつ演算結果Ｓを複数ビット単位（図２では2bit）で出力する。ＣＳＡ６から出力された演算結果Ｓは、第１のシフトレジスタ８の出力（過去の乗算剰余演算結果Ｓ）と複数ビット単位で加算され、加算結果は第１のシフトレジスタ８に再び格納される。
【００５６】
なお、図２に示した第１のラッチ回路１、第２のラッチ回路２、第１のシフトレジスタ８及びｕ生成部１０は、乗算剰余演算器の内部に備えている必要はなく、乗算剰余演算器を利用する情報処理装置に備えていてもよい。同様に、乗数Ｂ、Ｎの値を一時的に保持する記憶素子を備えている場合、該記憶素子は乗算剰余演算器の内部に備えている必要はなく、乗算剰余演算器を利用する情報処理装置に備えていてもよい。さらに、制御部１１も乗算剰余演算器の内部に備えている必要はなく、乗算剰余演算器を利用する情報処理装置が備える処理装置（ＣＰＵ）によって実現してもよい。すなわち、乗算剰余演算器は、図２の点線内の構成要素のみを備えていればよい。
【００５７】
また、被乗数Ａ、ｕは、ラッチ回路に格納する必要はなく、例えばシフトレジスタやＲＡＭ等のようにデータを一時的に保持できる記憶素子であればどのようなものを用いてもよい。
【００５８】
図３に示すように、本発明の情報処理装置は、例えばパーソナルコンピュータやサーバ装置等のコンピュータシステムであり、プログラムにしたがって所定の処理を実行する処理装置２０と、処理装置２０に対してコマンドや情報等を入力するための入力装置３０と、処理装置２０の処理結果をモニタするための出力装置４０とを有する構成である。
【００５９】
処理装置２０は、ＣＰＵ２１と、ＣＰＵ２１の処理に必要な情報を一時的に記憶する主記憶装置２２と、ＣＰＵ２１に上記制御部１１の処理を実行させるプログラムが記録された記録媒体２３と、処理に必要なデータ等を蓄積するデータ蓄積装置２４と、主記憶装置２２、記録媒体２３、及びデータ蓄積装置２４とのデータ転送を制御するメモリ制御インタフェース部２５と、入力装置３０及び出力装置４０とのインタフェース装置であるＩ／Ｏインタフェース部２６と、図１に示した乗算剰余演算器２７と、ネットワーク等との通信を制御するインタフェースである通信制御装置２８とを備え、それらがバス２９等を介して接続された構成である。なお、処理装置２０には、乗算剰余演算器２７の構成に応じて、被乗数Ａ、ｕを保持するラッチ回路、及び乗数Ｂ、Ｎ、及び演算結果Ｓを保持するシフトレジスタ等を備えていてもよい。
【００６０】
処理装置２０は、記録媒体２３に記録されたプログラムにしたがってＣＰＵ２１により上記制御部１１の処理を実行し、乗算剰余演算器２７を用いてＳ＝Ｓ＋Ａi×Ｂ＋ｕ×Ｎの演算を実行する。なお、記録媒体２３は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。
【００６１】
次に、本発明の乗算剰余演算器の動作について図面を用いて具体的に説明する。
【００６２】
以下では、Ａ、ｕ、Ｂ、Ｎがそれぞれ512bitであり、処理ビット長が64bitのＣＳＡ６を用い、乗数Ｂ、Ｎが3bit単位で第１の論理回路４及び第２の論理回路５へ供給され、第１のシフトレジスタ８が2bit単位で乗算剰余演算結果Ｓを入出力する場合を例にして説明する。また、第１及び第２のラッチ回路１、２には被乗数Ａ、ｕがＣＳＡ６の処理ビット長に合わせて64bit単位で格納されるものとする。
【００６３】
処理ビット長が64bitのＣＳＡ６を用い、乗数Ｂ、Ｎを3bit単位で出力する場合、Ａ、ｕ、Ｂ、Ｎがそれぞれ512bitの乗算剰余演算（512bit×512bit×2-512 mod 512bit）は、64bit×512bit×2-64 mod 512bit（Ａ×Ｂ×2-64 mod Ｎ）の演算を繰り返し実行すればよい。
【００６４】
本発明の乗算剰余演算器では、モンゴメリ法による乗算剰余演算の特徴である、下位ビットが０になることを利用して（ここでは、下位64bitが０Ｈ）、上記Ｓ、Ａ、Ｂ、Ｎの値に対応するｕを予め算出し、ｕ生成部１０にテーブル形式で格納しておく。
【００６５】
例えば、乗数を2bit（重複1bitを除く）単位で出力する場合、ｕの値を以下のようにして求める（但し、Ｎは奇数）。
【００６６】
N[1:0]=01,(S+AiB)[1:0]=00のとき、
S=S+AiB+uN=00となるuは、u[1:0]=00
N[1:0]=01,(S+AiB)[1:0]=01のとき、
S=S+AiB+uN=00となるuは、u[1:0]=11
N[1:0]=01,(S+AiB)[1:0]=10のとき、
S=S+AiB+uN=00となるuは、u[1:0]=10
N[1:0]=01,(S+AiB)[1:0]=11のとき、
S=S+AiB+uN=00となるuは、u[1:0]=01
N[1:0]=11,(S+AiB)[1:0]=00のとき、
S=S+AiB+uN=00となるuは、u[1:0]=00
N[1:0]=11,(S+AiB)[1:0]=01のとき、
S=S+AiB+uN=00となるuは、u[1:0]=01
N[1:0]=11,(S+AiB)[1:0]=10のとき、
S=S+AiB+uN=00となるuは、u[1:0]=10
N[1:0]=11,(S+AiB)[1:0]=11のとき、
S=S+AiB+uN=00となるuは、u[1:0]=11
以上をまとめると、表２のようになる。
【００６７】
【表２】
【００６８】
ここで、Ａ、Ｂ、Ｎはいずれも既知の値であり、Ｓは０Ｈ（演算開始時）または直前の64bit×512bit×2-64 mod 512bitの演算結果を用いるため既知である。なお、Ｎは奇数であるため、N[1:0]=01または11で固定である。したがって、Ａ、Ｂ、及びＳの各値を基に算出した被乗数ｕの値をテーブル形式でｕ生成部１０に格納しておき、制御部１１は該テーブルを参照して被乗数ｕの値を決定する。
【００６９】
本発明の乗算剰余演算器では、まず、制御部１１により、第１のラッチ回路１に被乗数Ａ（512bit）の最下位64bitのデータをセットし、乗数Ｂ（512bit）のデータを第１の論理回路４へ供給し、乗数Ｎ（512bit）のデータを第２の論理回路５へ供給する。
【００７０】
続いて、制御部１１は、64bitの被乗数Ａ、64bitの乗数Ｂ、64bitの乗数Ｎからｕ生成部１０に格納されたテーブルを参照してｕ（64bit分）の値を求め、第２のラッチ回路２に格納する。
【００７１】
制御部１１による第１のラッチ回路１、第２のラッチ回路２、第１の論理回路４及び第２の論理回路５に対する被乗数または乗数のセットが完了すると、乗算剰余演算器はＳ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算を開始する。
【００７２】
乗算剰余演算器は、まず、第１の論理回路４にて、3bitの乗数Ｂの値からBooth法による変換を行い、該変換後の値に対応する０、＋１Ａ（64+4bit）、−１Ａ（64+4bit）、＋２Ａ（64+4bit）または−２Ａ（64+4bit）を選択しＣＳＡ６へ供給する。同様に、乗算剰余演算器は、第２の論理回路５にて、3bitの乗数Ｎの値からBooth法による変換を行い、該変換後の値に対応する０、＋１ｕ（64+4bit）、−１ｕ（64+4bit）、＋２ｕ（64+4bit）または−２ｕ（64+4bit）を選択しＣＳＡ６へ供給する。
【００７３】
ＣＳＡ６は、第１の論理回路４及び第２の論理回路５から順次供給される値を、桁合わせを実行しつつ加算することでＡ×Ｂ、及びｕ×Ｎを算出し、それらの加算結果（乗算剰余演算結果）Ｓを2bit単位で出力する。ＣＳＡ６から出力された演算結果は、第１のシフトレジスタ８の出力と2bit単位で加算器９にて加算され、加算後の値が第１のシフトレジスタ８に再び格納される。以上の処理を乗数Ｂ、Ｎの全てのビットデータに対して繰り返し実行することで、64bit×512bit×2-64 mod 512bitの演算が終了する。但し、この段階ではＣＳＡ６の内部に部分積の演算結果の上位64bitが残っているため、このデータを制御部１１の指示により第１のシフトレジスタ８に格納する。その結果、該記憶素子に64bit×512bit×2-64 mod 512bitの演算結果Ｓが格納される。
【００７４】
乗算剰余演算器は、64bit×512bit×2-64 mod 512bitの演算が完了すると、制御部１１により第１のラッチ回路１に被乗数Ａ（512bit）の次の下位64bitのデータ（最下位から65bit目〜128bit目のデータ）をセットし、上記と同様にｕ生成部１０のテーブルを参照して被乗数ｕの値を求め、求めた値を第２のラッチ回路２に格納した後、再び64bit×512bit×2-64 mod 512bitの演算を開始する。
【００７５】
以降、第１のラッチ回路１に格納される被乗数Ａ（512bit）の全てのビットデータに対して同様の処理を繰り返し実行する。すなわち、上記64bit×512bit×2-64 mod 512bitの演算を８回繰り返す。その結果、本発明の乗算剰余演算器による512bit×512bit×2-512 mod 512bitの演算が終了する。
【００７６】
次に、本発明の乗算剰余演算器の効果について図面を用いて説明する。
【００７７】
図４は乗数を1bit単位で出力する従来の乗算剰余演算器のレイアウト面積及びBooth法を採用する本発明の乗算剰余演算器のレイアウト面積を示すグラフである。また、図５は乗数を1bit単位で出力する従来の乗算剰余演算器の処理クロック数及びBooth法を採用する本発明の乗算剰余演算器の処理クロック数を示すグラフである。
【００７８】
また、図６は乗数を1bit単位で出力する従来の乗算剰余演算器及びBooth法を採用する本発明の乗算剰余演算器の処理クロック数に対するレイアウト面積をそれぞれ示すグラフである。
【００７９】
図４及び図５に示す「1bit」とは乗数を1bit単位で出力する従来の乗算剰余演算器の構成を示し、「Booth 2bit」とはBooth法による変換後の乗数を用いる（基数４）本発明の乗算剰余演算器の構成を示している。また、図４及び図５に示すグラフの横軸（処理性能）は、表３に示すように乗算剰余演算器の処理ビット長（32bit、64bit、128bit、256bit）に対応する、従来の乗算剰余演算器が備えるＣＳＡの処理ビット長と本発明の乗算剰余演算器が備えるＣＳＡの処理ビット長とを示している。本発明の乗算剰余演算器は、乗数を2bit単位で被乗数に掛けるため、処理性能を比較する際には、表３に示すように乗数を1bit単位で被乗数に掛ける従来の乗算剰余演算器に対してＣＳＡの処理ビット長を１／２にしている。なお、表３の各エントリは（ＣＳＡの処理ビット長）＊（出力ビット数）を示している。
【００８０】
【表３】
【００８１】
図４から分かるように、乗算剰余演算器としての処理ビット長が同じである場合、本発明の乗算剰余演算器は、乗数を複数ビット単位で処理できるため、乗数を1bit単位で処理する従来の乗算剰余演算器に比べて回路のレイアウト面積が低減する。これはBooth 2bitとすることでＣＳＡ６の処理ビット長を従来の半分にできるためである。
【００８２】
例えば、乗算剰余演算器の処理ビット長を128bitとした場合、従来の乗算剰余演算器では、ＣＳＡで加算結果（sum）の値と桁上げ(carry)の値をそれぞれ128個ずつ保持する必要があるため、２５６個のフリップフロップ（Data-F/F）が必要になる。
【００８３】
それに対して、Booth 2bitを採用する本発明の乗算剰余演算器が備えるＣＳＡ６では、処理ビット長が従来の半分の64bitで済むため、加算結果（sum）の値と桁上げ(carry)の値を保持するフリップフロップも１２８個で済む。すなわち、Booth法を採用することで複数ビット単位で乗数を処理するため、ＣＳＡ６が備えるフリップフロップの数が大きく削減され、回路規模を低減できる。また、ＣＳＡ６の処理ビット長が短縮することで第１及び第２のラッチ回路や論理回路（従来の構成ではセレクタに相当）のビット長も短縮されるため、乗算剰余演算器としての回路規模が低減する。但し、上述したようにBooth法を採用することでＣＳＡの処理ビット長を拡張する必要があり（基数４の場合、4bit）、さらに第１の論理回路４及び第２の論理回路５による回路規模の増大もあるため、本発明の乗算剰余演算器のレイアウト面積は従来の１／２よりも大きくなる。
【００８４】
一方、図５から分かるように、乗算剰余演算器の処理ビット長が同じである場合、本発明の乗算剰余演算器は、乗数を複数ビット単位で処理するため、乗数を1bit単位で処理する従来の乗算剰余演算器に比べて処理クロック数が少なくなる。これは上述したＣＳＡ６内に残る部分積の演算結果を出力する処理時間の差から生じる結果である。
【００８５】
本発明の乗算剰余演算器では、上述したようにＣＳＡ６の処理ビット長を従来の半分にできるが（基数４の場合）、被乗数を分割して処理するため、乗算剰余演算を複数回繰り返すことになる。そのため、本発明の乗算剰余演算器では、従来の乗算剰余演算器よりも繰り返し演算の回数が増え、ＣＳＡ６内に残る部分積の演算結果を出力する回数も増えてしまう。
【００８６】
しかしながら、本発明の乗算剰余演算器では、ＣＳＡ６の処理ビット長を短縮できることから、ＣＳＡ６内に残る演算結果を出力する処理時間も従来の１／２となる（基数４の場合）。そのため、僅かではあるが、１つのＡ、ｕ、Ｂ、Ｎに対する乗算剰余演算の処理時間は従来よりも低減する。
【００８７】
本発明の乗算剰余演算器は、処理時間の大幅な低減は実現できないが、多数の数字の配列に対して大きな値のべき乗剰余演算を行うＲＳＡによる暗号化及び復号に本発明の乗算剰余演算器を用いる場合は、この僅かな処理時間の向上が非常に有益となる。
【００８８】
図６に示すように、Booth法を採用する本発明の乗算剰余演算器は、乗数を1bit単位で出力する従来の乗算剰余演算器に比べて、回路規模が少なく、かつ高速な処理を実現できることが分かる。
【００８９】
なお、参考までに、Booth法を採用する本発明の乗算剰余演算器の基数を増やした場合の回路規模の増大量を表４及び表５に示す。本発明の乗算剰余演算器では、基数が１６の場合、乗数Ｂ、Ｎは4bit毎に処理されるため、ＣＳＡ６のビット幅が同じ場合、処理性能は従来の乗算剰余演算器の４倍になる。なお、表４及び表５の各エントリ内の数字の単位は[ｍｍ2]である。
【００９０】
【表４】
【００９１】
表４に示すように、Booth法を採用する本発明の乗算剰余演算器は、基数４、１６共にほぼ同じ回路規模で構成され、従来の乗算剰余演算器と比較してレイアウト面積が約３０％削減されることが分かる。
【００９２】
【表５】
【００９３】
表５に示すように、Booth法を採用する本発明の乗算剰余演算器は、従来の乗算剰余演算器に比べて、基数４の場合、処理速度は約２倍になるがレイアウト面積は１．３倍程度で済む。また、基数１６の場合、処理速度は約４倍になるがレイアウト面積は２．６倍程度で済む。
【００９４】
ところで、被乗数ｕは、乗数Ｂ、Ｎの出力ビット数をｑとすると、上記モンゴメリ法を応用したアルゴリズムの（１）、（５）から以下の式で算出できる。
【００９５】
ｖ＝−Ｎ-1ｍｏｄ２q
ｕ＝Ｓｖｍｏｄ２q
ここで、ｖは演算開始時に一度だけ計算する値である。なお、ｒに代えて２qとしているのはｒを２進数で表したためである。
【００９６】
ｑ＝１となる従来の乗算剰余演算器では、Ｎが奇数であることからｖ＝１となるため、ｕ＝Ｓｍｏｄ２＝Ｓ［０］となり、被乗数ｕはＳの下位ビットに等しくなる。したがって、被乗数ｕを実施的に計算する必要はない。
【００９７】
しかしながら、ｑ＞１となる本発明の乗算剰余演算器では、ｕ＝Ｓ［０］が成立しないため、上記２つの演算が必要になる。但し、ｑの値が小さい場合（例えば、ｑ＝２、４）は、ｖ、ｕも2bitまたは4bitであり、その演算に必要なＮ、Ｓも2bitまたは4bitである。そのため、本発明ではＡ、Ｂ、Ｓ、Ｎの値から予めｕの値を算出してテーブルを作成しておき、該テーブルを参照することで第２のラッチ回路２に格納するｕを決定している。
【００９８】
Booth法による乗数の変換に用いる基数の値を大きくしｑの値を増やせば、ＣＳＡ６の処理ビット長をさらに短縮できるため、乗算剰余演算の処理時間をさらに短縮することができる。
【００９９】
しかしながら、ｑ＞４の場合、すなわち乗数Ｂ、Ｎを８ビット以上で出力する（基数６４以上）構成では、被乗数ｕをテーブル内から選択するために必要な、例えばデコーダ等の回路規模が増大するため、記憶素子を含むｕ生成部１０の回路規模が増大し、上述したＣＳＡ６の処理ビット長を短縮することによる乗算剰余演算器の回路規模の低減効果を相殺してしまう。
【０１００】
表６にｑの値に対するｕ生成部１０のレイアウト面積（単位：ｍｍ2）を示し、表７にｑの値に対するＣＳＡとｕ生成部とを含む総レイアウト面積（単位：ｍｍ2）を示す。
【０１０１】
【表６】
【０１０２】
【表７】
【０１０３】
表６及び表７から分かるように、例えばＣＳＡの処理ビット長を256bitとしたとき、ｑ＝１のときの総レイアウト面積に対して、ＣＳＡの処理ビット長を128bitにできるｑ＝２の場合（基数４）及びＣＳＡの処理ビット長を64bitにできるｑ＝４の場合（基数１６）の総レイアウト面積は低減する。しかしながら、ｑ＝８（基数６４）にすると総レイアウト面積が増大してしまう。
【０１０４】
したがって、本発明の乗算剰余演算器では、ｑの値が２または４であることが回路規模の増大を抑制しつつ演算時間を短縮できるために望ましい。但し、回路規模よりも演算時間の向上を優先する場合は、ｑの値を８以上に設定してもよい。その場合、ｑの値はｕ生成部１０のレイアウト面積の増大を考慮しつつ最適な値を選択すればよい。
【図面の簡単な説明】
【０１０５】
【図１】Booth法による乗数の具体的な変換例を示す模式図である。
【図２】本発明の乗算剰余演算器の一構成例を示すブロック図である。
【図３】本発明の情報処理装置の一構成例を示すブロック図である。
【図４】本発明の乗算剰余演算器のレイアウト面積を示すグラフである。
【図５】本発明の乗算剰余演算器の処理クロック数を示すグラフである。
【図６】本発明の乗算剰余演算器の処理クロック数に対するレイアウト面積の関係を示すグラフである。
【図７】従来の乗算剰余演算器の構成を示すブロック図である。
【符号の説明】
【０１０６】
１ 第１のラッチ回路
２ 第２のラッチ回路
４ 第１の論理回路
５ 第２の論理回路
６ ＣＳＡ
８ 第１のシフトレジスタ
９ 加算器
１０ ｕ生成部
１１ 制御部
２０ 処理装置
２１ ＣＰＵ
２２ 主記憶装置
２３ 記録媒体
２４ データ蓄積装置
２５ メモリ制御インタフェース部
２６ Ｉ／Ｏインタフェース部
２７ 乗算剰余演算器
２８ 通信制御装置
２９ バス
３０ 入力装置
４０ 出力装置
【特許請求の範囲】
【請求項１】
被乗数をＡ、ｕとし、乗数をＢ、Ｎとし、乗算剰余演算結果をＳとしたとき、Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、
Booth法に基づいて変換された複数のビット数ｑ単位で供給される前記乗数Ｂの値に対応する前記被乗数Ａの整数倍の値を選択して出力し、前記Booth法に基づいて変換された複数のビット数ｑ単位で供給される前記乗数Ｎの値に対応する前記被乗数ｕの整数倍の値を選択して出力する論理回路と、
前記論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数ｑ単位で出力される前記Ａ×Ｂ＋ｕ×Ｎの演算結果と、前記ビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Ｓとして出力する加算器と、
を有する乗算剰余演算器。
【請求項２】
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
をさらに有する請求項１記載の乗算剰余演算器。
【請求項３】
前記Booth法に基づいて変換した変換後の乗数Ｂ及び乗数Ｎを前記論理回路に供給すると共に、前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項１または２記載の乗算剰余演算器。
【請求項４】
前記制御部は、
前記第１の記憶素子に前記被乗数Ａをセットし、
前記第２の記憶素子に前記被乗数ｕをセットする請求項３記載の乗算剰余演算器。
【請求項５】
予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
前記制御部は、
前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する請求項３または４記載の乗算剰余演算器。
【請求項６】
被乗数をＡ、ｕとし、乗数をＢ、Ｎとし、乗算剰余演算結果をＳとしたとき、Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、
複数のビット数ｑ＋１単位で供給される乗数Ｂの値をBooth法に基づいて変換し、該変換後の値に対応する前記被乗数Ａの整数倍の値を選択して出力し、前記ビット数ｑ＋１単位で供給される前記乗数Ｎの値をBooth法に基づいて変換し、該変換後の値に対応する前記被乗数ｕの整数倍の値を選択して出力する論理回路と、
前記論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数ｑ単位で出力される前記Ａ×Ｂ＋ｕ×Ｎの演算結果と、前記ビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Ｓとして出力する加算器と、
を有する乗算剰余演算器。
【請求項７】
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
をさらに有する請求項６記載の乗算剰余演算器。
【請求項８】
前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項５記載の乗算剰余演算器。
【請求項９】
前記制御部は、
前記第１の記憶素子に前記被乗数Ａをセットし、
前記第２の記憶素子に前記被乗数ｕをセットし、
前記論理回路に前記乗数Ｂ及び前記乗数Ｎを供給する請求項８記載の乗算剰余演算器。
【請求項１０】
予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
前記制御部は、
前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する請求項８または９記載の乗算剰余演算器。
【請求項１１】
前記ビット数ｑは２である請求項１乃至１０のいずれか１項記載の乗算剰余演算器。
【請求項１２】
前記ビット数ｑは４である請求項１乃至１０のいずれか１項記載の乗算剰余演算器。
【請求項１３】
請求項１に記載の乗算剰余演算器と、
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
を有する情報処理装置。
【請求項１４】
前記Booth法に基づいて変換した変換後の乗数Ｂ及び乗数Ｎを前記論理回路に供給すると共に、前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項１３記載の情報処理装置。
【請求項１５】
前記制御部は、
前記第１の記憶素子に前記被乗数Ａをセットし、
前記第２の記憶素子に前記被乗数ｕをセットする請求項１４記載の情報処理装置。
【請求項１６】
予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
前記制御部は、
前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する請求項１４または１５記載の情報処理装置。
【請求項１７】
請求項６記載の乗算剰余演算器と、
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
を有する情報処理装置。
【請求項１８】
前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項１７記載の情報処理装置。
【請求項１９】
前記制御部は、
前記第１の記憶素子に前記被乗数Ａをセットし、
前記第２の記憶素子に前記被乗数ｕをセットし、
前記論理回路に前記乗数Ｂ及び前記乗数Ｎを供給する請求項１８記載の情報処理装置。
【請求項２０】
予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
前記制御部は、
前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する請求項１８または１９記載の情報処理装置。
【請求項２１】
前記ビット数ｑは２である請求項１３乃至２０のいずれか１項記載の情報処理装置。
【請求項２２】
前記ビット数ｑは４である請求項１３乃至２０のいずれか１項記載の情報処理装置。
【請求項１】
被乗数をＡ、ｕとし、乗数をＢ、Ｎとし、乗算剰余演算結果をＳとしたとき、Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、
Booth法に基づいて変換された複数のビット数ｑ単位で供給される前記乗数Ｂの値に対応する前記被乗数Ａの整数倍の値を選択して出力し、前記Booth法に基づいて変換された複数のビット数ｑ単位で供給される前記乗数Ｎの値に対応する前記被乗数ｕの整数倍の値を選択して出力する論理回路と、
前記論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数ｑ単位で出力される前記Ａ×Ｂ＋ｕ×Ｎの演算結果と、前記ビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Ｓとして出力する加算器と、
を有する乗算剰余演算器。
【請求項２】
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
をさらに有する請求項１記載の乗算剰余演算器。
【請求項３】
前記Booth法に基づいて変換した変換後の乗数Ｂ及び乗数Ｎを前記論理回路に供給すると共に、前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項１または２記載の乗算剰余演算器。
【請求項４】
前記制御部は、
前記第１の記憶素子に前記被乗数Ａをセットし、
前記第２の記憶素子に前記被乗数ｕをセットする請求項３記載の乗算剰余演算器。
【請求項５】
予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
前記制御部は、
前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する請求項３または４記載の乗算剰余演算器。
【請求項６】
被乗数をＡ、ｕとし、乗数をＢ、Ｎとし、乗算剰余演算結果をＳとしたとき、Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎを算出するための乗算剰余演算器であって、
複数のビット数ｑ＋１単位で供給される乗数Ｂの値をBooth法に基づいて変換し、該変換後の値に対応する前記被乗数Ａの整数倍の値を選択して出力し、前記ビット数ｑ＋１単位で供給される前記乗数Ｎの値をBooth法に基づいて変換し、該変換後の値に対応する前記被乗数ｕの整数倍の値を選択して出力する論理回路と、
前記論理回路から順次出力される値を用いてＡ×Ｂ＋ｕ×Ｎの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数ｑ単位で出力される前記Ａ×Ｂ＋ｕ×Ｎの演算結果と、前記ビット数ｑ単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Ｓとして出力する加算器と、
を有する乗算剰余演算器。
【請求項７】
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
をさらに有する請求項６記載の乗算剰余演算器。
【請求項８】
前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項５記載の乗算剰余演算器。
【請求項９】
前記制御部は、
前記第１の記憶素子に前記被乗数Ａをセットし、
前記第２の記憶素子に前記被乗数ｕをセットし、
前記論理回路に前記乗数Ｂ及び前記乗数Ｎを供給する請求項８記載の乗算剰余演算器。
【請求項１０】
予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
前記制御部は、
前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する請求項８または９記載の乗算剰余演算器。
【請求項１１】
前記ビット数ｑは２である請求項１乃至１０のいずれか１項記載の乗算剰余演算器。
【請求項１２】
前記ビット数ｑは４である請求項１乃至１０のいずれか１項記載の乗算剰余演算器。
【請求項１３】
請求項１に記載の乗算剰余演算器と、
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
を有する情報処理装置。
【請求項１４】
前記Booth法に基づいて変換した変換後の乗数Ｂ及び乗数Ｎを前記論理回路に供給すると共に、前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項１３記載の情報処理装置。
【請求項１５】
前記制御部は、
前記第１の記憶素子に前記被乗数Ａをセットし、
前記第２の記憶素子に前記被乗数ｕをセットする請求項１４記載の情報処理装置。
【請求項１６】
予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
前記制御部は、
前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する請求項１４または１５記載の情報処理装置。
【請求項１７】
請求項６記載の乗算剰余演算器と、
前記被乗数Ａを保持し、前記セレクタに供給する第１の記憶素子と、
前記被乗数ｕを保持し、前記セレクタに供給する第２の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Ｓを保持し、前記ビット数ｑ単位で該乗算剰余演算結果Ｓを前記加算器に供給する第３の記憶素子と、
を有する情報処理装置。
【請求項１８】
前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項１７記載の情報処理装置。
【請求項１９】
前記制御部は、
前記第１の記憶素子に前記被乗数Ａをセットし、
前記第２の記憶素子に前記被乗数ｕをセットし、
前記論理回路に前記乗数Ｂ及び前記乗数Ｎを供給する請求項１８記載の情報処理装置。
【請求項２０】
予め算出された、前記被乗数Ａ、前記乗数Ｂ、前記乗数Ｎ、及び前記乗算剰余演算結果Ｓの値に対する前記被乗数ｕの値の関係が格納されるｕ生成部をさらに有し、
前記制御部は、
前記Ｓ＝Ｓ＋Ａ×Ｂ＋ｕ×Ｎの演算時に前記ｕ生成部を参照することで前記被乗数ｕの値を決定する請求項１８または１９記載の情報処理装置。
【請求項２１】
前記ビット数ｑは２である請求項１３乃至２０のいずれか１項記載の情報処理装置。
【請求項２２】
前記ビット数ｑは４である請求項１３乃至２０のいずれか１項記載の情報処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００６−２３６４８（Ｐ２００６−２３６４８Ａ）
【公開日】平成１８年１月２６日（２００６．１．２６）
【国際特許分類】
【出願番号】特願２００４−２０３４３６（Ｐ２００４−２０３４３６）
【出願日】平成１６年７月９日（２００４．７．９）
【出願人】（０００２３２０３６）ＮＥＣマイクロシステム株式会社 (72)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
【公開日】平成１８年１月２６日（２００６．１．２６）
【国際特許分類】
【出願日】平成１６年７月９日（２００４．７．９）
【出願人】（０００２３２０３６）ＮＥＣマイクロシステム株式会社 (72)
【出願人】（８９９００００６８）学校法人早稲田大学 (602)
【Ｆターム（参考）】
[ Back to top ]