(57)【要約】【課題】モンゴメリ乗算剰余の多倍長演算を行う回路において、ブロック単位演算器における減算のための遅延時間を短縮し、動作周波数を維持したままで演算を行う。【解決手段】補数モードにおいて、２次Ｂｏｏｔｈアルゴリズムのエンコーダ手段２０２は、乗算Ａ×Ｂを行う通常モードとは異なる選択信号を出力し、選択手段２０３は、Ｂの３つのビットｂ１、ｂ０、およびｂ−１に対しては−Ａを表す部分積を選択し、それ以外のビットに対しては０を表す部分積を選択する。加算手段２０４は、−Ａを表す部分積と０とを加算して、−Ａ（Ａの２の補数またはＡの１の補数）を出力する。【選択図】      図１
2004258141.tif 000002
【特許請求の範囲】
【請求項１】
ビットパターンで表された被乗数Ａと乗数Ｂの乗算を行う演算装置であって、
被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する選択手段と、
前記選択手段から出力される、ｉの数と同じ数だけの部分積を加算して、乗算結果を生成する加算手段とを備え、
前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの２の補数を生成して、該被乗数Ａの２の補数を前記乗算結果として出力するような動作モードを設けたことを特徴とする演算装置。
【請求項２】
ビットパターンで表された被乗数Ａと乗数Ｂの乗算を行う演算装置であって、
被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する選択手段と、
前記選択手段から出力される、ｉの数と同じ数だけの部分積を加算して、乗算結果を生成する加算手段とを備え、
前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの１の補数を生成して、該被乗数Ａの１の補数を前記乗算結果として出力するような動作モードを設けたことを特徴とする演算装置。
【請求項３】
ビットパターンで表された被乗数Ａと乗数Ｂを乗算し、乗算結果とビットパターンで表された数Ｃおよび数Ｄとを加算する、乗算加算を行う演算装置であって、
被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する選択手段と、
前記選択手段から出力される、ｉの数と同じ数だけの部分積と数Ｃと数Ｄとを加算して、乗算加算結果を生成する加算手段とを備え、
前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの１の補数を生成し、該被乗数Ａの１の補数と数Ｃと数Ｄとを加算した結果を前記乗算加算結果として出力するような動作モードを設けたことを特徴とする演算装置。
【請求項４】
ｋビットのビットパターンで表された被乗数Ａと乗数Ｂを乗算し、乗算結果とｋビットのビットパターンで表された数Ｃおよび数Ｄとを加算することで、１ブロックがｋビットであるｇ＋１個のブロックからなる整数Ｙから１ブロックがｋビットであるｇ個のブロックからなる整数Ｎを減算する演算を行う演算装置であって、
被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する選択手段と、
前記選択手段から出力される、ｉの数と同じ数だけの部分積と数Ｃと数Ｄとを加算して、２ｋビットの乗算加算結果を生成する加算手段と、
前記乗算加算結果の一部のビットを反転する反転手段とを備え、
前記部分積生成手段が、整数Ｎのｊ番目のブロックｎｊを被乗数Ａとして用い、前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの１の補数を生成し、ｊ−１番目のブロックの乗算加算からのキャリーを数Ｃとして用い、整数Ｙのｊ番目のブロックｙｊを数Ｄとして用いて、該被乗数Ａの１の補数と数Ｃと数Ｄとを加算した結果をｊ番目のブロックの乗算加算結果として出力し、前記反転手段が、該ｊ番目のブロックの乗算加算結果の一部のビットを反転してｊ＋１番目のブロックの乗算加算へのキャリーを生成することを特徴とする演算装置。
【請求項５】
ビットパターンで表された整数ＩおよびＪと剰余の法Ｎを１ブロックがｋビットであるｇ個のブロックにそれぞれ分割して、Ｙ＝ＩＪ２−ｋｇ  ｍｏｄ  Ｎとなるモンゴメリ乗算剰余の多倍長演算を行う演算装置であって、
ｋビットの被乗数Ａ、乗数Ｂ、数Ｃ、および数Ｄのそれぞれについて、与えられた複数の値のいずれかを選択して出力する第１の選択手段と、
前記第１の選択手段から出力される被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
前記第１の選択手段から出力される乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する第２の選択手段と、
前記第２の選択手段から出力される、ｉの数と同じ数だけの部分積と、前記第１の選択手段から出力される数Ｃと数Ｄとを加算して、２ｋビットの乗算加算結果を生成する加算手段と、
前記乗算加算結果の一部のビットを反転する反転手段とを備え、
前記第１の選択手段が、整数Ｎのｊ番目のブロックｎｊを被乗数Ａとして選択し、ｊ−１番目のブロックの乗算加算からのキャリーを数Ｃとして選択し、Ｙのｊ番目のブロックｙｊを数Ｄとして選択し、前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの１の補数を生成し、該被乗数Ａの１の補数と数Ｃと数Ｄとを加算した結果をｊ番目のブロックの乗算加算結果として出力し、前記反転手段が、該ｊ番目のブロックの乗算加算結果の一部のビットを反転してｊ＋１番目のブロックの乗算加算へのキャリーを生成するような動作モードを設けたことを特徴とする演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、モンゴメリ乗算剰余の多倍長演算を行うための演算装置に関する。
【０００２】
【従来の技術】
近年、コンピュータネットワーク上では、セキュリティ対策として、暗号化データ通信やユーザ認証（デジタル署名）が多く使用されている。これらのセキュリティ対策では、ＲＳＡ（Ｒｉｖｅｓｔ−Ｓｈａｍｉｒ−Ａｄｌｅｍａｎ）暗号や楕円曲線暗号等の暗号処理が利用される。
【０００３】
ＲＳＡ暗号や楕円曲線暗号は非常に大きいビット数の数値を扱うため、これらの暗号処理で使われるモンゴメリ乗算剰余の演算では、ソフトウェアやハードウェアで実現し易い多倍長演算アルゴリズムがよく使われる。多倍長演算アルゴリズムとは、非常に大きいビット数の数値を、ソフトウェアやハードウェアで扱い易いビット数（ブロック）に分割して、ブロック単位の演算を繰り返すアルゴリズムである。
【０００４】
モンゴメリ乗算剰余の多倍長演算アルゴリズムとしては、図１２のようなアルゴリズムが知られている（例えば、特許文献１参照）。図１２において、ＡおよびＢは整数であり、Ｎは剰余の法であり、Ｙは演算結果である。図１２の左側に示すアルゴリズムは、その右側に示すように変形することができる。このアルゴリズムは、Ｙ＝ＡＢ２−ｋｇ  ｍｏｄ  Ｎの演算を表しており、▲１▼〜▲６▼の処理からなる。
【０００５】
ｇはＡ、Ｂ、およびＮをｋビット＝１ブロックで分割した時のＡ、Ｂ、およびＮのブロック数であり、Ｙのブロック数はｇ＋１である。ａｉ、ｂｉ、ｎｉ、およびｙｉはそれぞれＡ、Ｂ、Ｎ、およびＹのｉ番目のブロックを表す。Ａ、Ｂ、Ｎ、およびＹは、それぞれ、ａｉ、ｂｉ、ｎｉ、およびｙｉを用いて次のように表される。
【０００６】
Ａ＝（ａｇ−１，ａｇ−２，．．．，ａ１，ａ０）
Ｂ＝（ｂｇ−１，ｂｇ−２，．．．，ｂ１，ｂ０）
Ｎ＝（ｎｇ−１，ｎｇ−２，．．．，ｎ１，ｎ０）
Ｙ＝（ｙｇ，ｙｇ−１，．．．，ｙ１，ｙ０）
２−ｋｇは剰余の法Ｎの上での２ｋｇの逆数であり、ｎ’０は、Ｒ＝２ｋｇとしてＲ・Ｒ−１−Ｎ・Ｎ’＝１（０≦Ｒ−１＜Ｎ，０≦Ｎ’＜Ｒ）を満たすＮ’をｋビット＝１ブロックで分割した時の最下位ブロック（０番目のブロック）を表す。また、ｃ１、ｃ２、ｍ、ｔｍｐはｋビットのワーク変数であり、ｉおよびｊはループ変数である。
【０００７】
図１２のアルゴリズムを▲６▼の処理を除いて回路化した場合、図１３のような回路になることが多いと考えられる。図１３の回路では、Ａ、Ｂ、およびＮがそれぞれｇ個のブロックに分割されて、ブロック毎にブロック単位演算器１０１に入力され、演算結果ｙ’ｉおよびｙ’ｉ−１がそれぞれＹのブロックｙｉおよびｙｉ−１に格納される。このとき、演算に必要なｙｉがＹから読み出されてブロック単位演算器１０１に入力される。
【０００８】
ブロック単位演算器１０１は、図１３の下方に示すように、レジスタ１１１、１１２、１１３、１１４、１１５、１２１、１２２、１２３、１２４、１２５、１２６、セレクタ１１６、１１７、１１８、１１９、および乗算加算器１２０を備える。乗算加算器１２０はＡ×Ｂ＋Ｃ＋Ｄの演算を行う。図１３の回路と図１２のアルゴリズムの▲１▼〜▲５▼の処理の対応関係は次の通りである。
▲１▼の処理：（ｃ１，ｔｍｐ）＝ａｉ＊ｂｊ＋ｙｉ＋ｃ１
セレクタ１１６によりＡ＝ａｉと選択し、セレクタ１１７によりＢ＝ｂｊと選択し、セレクタ１１８によりＣ＝ｃ１と選択し、セレクタ１１９によりＤ＝ｙｉと選択して、乗算加算器１２０の出力の上位ｋビットをｃ１としてレジスタ１２１に格納し、下位ｋビットをｔｍｐとしてレジスタ１２６に格納する。
▲２▼の処理：ｍ＝ｔｍｐ＊ｎ’０
セレクタ１１６によりＡ＝ｔｍｐと選択し、セレクタ１１７によりＢ＝ｎ’０と選択し、セレクタ１１８によりＣ＝０と選択し、セレクタ１１９によりＤ＝０と選択して、乗算加算器１２０の出力の下位ｋビットをｍとしてレジスタ１２５に格納する。
▲３▼の処理：（ｃ２，ｔｍｐ）＝ｍ＊ｎｉ＋ｔｍｐ＋ｃ２
セレクタ１１６によりＡ＝ｎｉと選択し、セレクタ１１７によりＢ＝ｍと選択し、セレクタ１１８によりＣ＝ｔｍｐと選択し、セレクタ１１９によりＤ＝ｃ２と選択して、乗算加算器１２０の出力の上位ｋビットをｃ２としてレジスタ１２２に格納し、下位ｋビットをｔｍｐとしてレジスタ１２６に格納する。
▲４▼の処理：（ｃ２，ｙｉ−１）＝ｍ＊ｎｉ＋ｔｍｐ＋ｃ２
セレクタ１１６によりＡ＝ｎｉと選択し、セレクタ１１７によりＢ＝ｍと選択し、セレクタ１１８によりＣ＝ｔｍｐと選択し、セレクタ１１９によりＤ＝ｃ２と選択して、乗算加算器１２０の出力の上位ｋビットをｃ２としてレジスタ１２２に格納し、下位ｋビットをｙ’ｉ−１としてレジスタ１２４に格納する。レジスタ１２４の内容はＹのｙｉ−１に格納される。
▲５▼の処理：（ｙｉ，ｙｉ−１）＝ｙｉ＋ｃ１＋ｃ２
セレクタ１１６によりＡ＝ｙ’ｉと選択し、セレクタ１１７によりＢ＝１と選択し、セレクタ１１８によりＣ＝ｃ１と選択し、セレクタ１１９によりＤ＝ｃ２と選択して、乗算加算器１２０の出力の上位ｋビットをｙ’ｉとしてレジスタ１２３に格納し、下位ｋビットをｙ’ｉ−１としてレジスタ１２４に格納する。レジスタ１２３および１２４の内容はそれぞれＹのｙｉおよびｙｉ−１に格納される。
【０００９】
図１３の回路に図１２のアルゴリズムの▲６▼の処理を追加して、モンゴメリ乗算剰余の多倍長演算アルゴリズムの回路として完成させる場合、▲６▼以外の処理と同じように、ＹおよびＮをｋビット＝１ブロックで分割してブロック毎の演算を繰り返す図１４のような多倍長減算を採用して、図１５のような回路にすることが多いと考えられる。
【００１０】
図１５では、図１４の上方に示す多倍長減算を２の補数表現を用いてその下方に示すような加算に変形してから回路化している。２の補数は、コンピュータ内で負数を表現するために用いられ、１の補数に１を加えることで得られる。また、１の補数は、ビットパターンを反転させることで得られる。
【００１１】
図１５では、図１３のブロック単位演算器１０１がブロック単位演算器１３１に置き換えられている。ブロック単位演算器１３１は、ブロック単位演算器１０１に反転／非反転回路１４１を加えた構成を有する。
【００１２】
図１５の回路の動作のうち、図１２のアルゴリズムの▲６▼以外の処理（通常処理）に対応する動作は図１３の回路と同じであるため、▲６▼の処理（最終処理）に対応する動作のみを以下に説明する。この処理では、最終処理状態信号により、反転／非反転回路１４１はｎｉを反転して出力し、レジスタ１２３のｙ’ｉは１に初期化され、ブロック単位演算器１３１から出力されたｙ’ｉ−１はＹのｙｉに格納される。
（１）ｙ’ｉを１に初期化する。
（２）次の動作を０≦ｉ≦ｇの範囲で繰り返す。
【００１３】
セレクタ１１６によりＡ＝ｎｉの反転（１の補数）と選択し、セレクタ１１７によりＢ＝１と選択し、セレクタ１１８によりＣ＝ｙ’ｉ（ｙｉ−１−ｎｉ−１の結果からのキャリー）と選択し、セレクタ１１９によりＤ＝ｙｉと選択して、乗算加算器１２０の出力の上位ｋビットをｙ’ｉとしてレジスタ１２３に格納する。
（３）ｙ’ｉのｂｉｔ０（最下位ビット）が１（Ｙ≧Ｎ）の場合は（４）へ進み、ｙ’ｉのｂｉｔ０が０（Ｙ＜Ｎ）の場合は（５）へ進む。
（４）次の動作を０≦ｉ≦ｇの範囲で繰り返す。
【００１４】
セレクタ１１６によりＡ＝ｎｉの反転（１の補数）と選択し、セレクタ１１７によりＢ＝１と選択し、セレクタ１１８によりＣ＝ｙ’ｉ（ｙｉ−１−ｎｉ−１の結果からのキャリー）と選択し、セレクタ１１９によりＤ＝ｙｉと選択して、乗算加算器１２０の出力の上位ｋビットをｙ’ｉとしてレジスタ１２３に格納し、下位ｋビットをｙ’ｉ−１としてレジスタ１２４に格納する。レジスタ１２４の内容はＹのｙｉに格納される。
（５）動作を終了する
【００１５】
【特許文献１】
特開平１１−２１２４５６号公報
【００１６】
【発明が解決しようとする課題】
しかしながら、上述した仮想的な多倍長演算回路には、次のような問題がある。
【００１７】
図１５の回路において、Ａ、Ｂ、Ｎ、Ｙ、ｃ１、ｃ２、ｍ、およびｔｍｐを格納する回路は、通常、動作クロックに同期したＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）もしくはＦＦ（ｆｌｉｐ−ｆｌｏｐ  ）で構成される。このため、乗算加算器１２０とその直前のセレクタ１１６〜１１９は、上記ＲＡＭもしくはＦＦの出力（Ａ，Ｂ，Ｎ，Ｙ，ｃ１，ｃ２，ｍ，ｔｍｐ）からＲＡＭもしくはＦＦの入力（Ｙ，ｃ１，ｃ２，ｍ，ｔｍｐ）までの通り道となるので、乗算加算器１２０とセレクタ１１６〜１１９の総遅延時間が動作クロックの周期より小さくなければ、回路全体として動作しないということになる。
【００１８】
したがって、図１５の回路の動作周波数を向上させる際のボトルネックは、ブロック単位演算器１３１の最大遅延経路＜ｎｉ→反転／非反転回路１４１→セレクタ１１６→乗算加算器１２０→（ｃ１，ｃ２，ｙ’ｉ，ｙ’ｉ−１，ｍ，ｔｍｐ）＞であり、この経路をいかに短縮するかが問題となる。
【００１９】
本発明の課題は、モンゴメリ乗算剰余の多倍長演算を行う回路においてブロック単位演算器における減算のための遅延時間を短縮し、動作周波数を維持したままで多倍長演算を行うための演算装置を提供することである。
【００２０】
【課題を解決するための手段】
図１は、本発明の演算装置の原理図である。図１の演算装置は、部分積生成手段２０１、エンコーダ手段２０２、選択手段２０３、および加算手段２０４を備え、ビットパターンで表された被乗数Ａと乗数Ｂの乗算を行う。
【００２１】
部分積生成手段２０１は、被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する。エンコーダ手段２０２は、乗数Ｂを２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力する。選択手段２０３は、選択信号に応じて、複数の部分積のいずれかを選択して出力する。加算手段２０４は、選択手段２０３から出力される、ｉの数と同じ数だけの部分積を加算して、乗算結果を生成する。
【００２２】
そして、エンコーダ手段２０２が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、加算手段２０４が、−Ａを表す部分積から被乗数Ａの２の補数を生成して、被乗数Ａの２の補数を乗算結果として出力するような動作モードを、演算装置に設ける。この動作モードにおいて、加算手段２０４が、−Ａを表す部分積から被乗数Ａの２の補数を生成する代わりに、被乗数Ａの１の補数を生成するようにすることもできる。
【００２３】
２次Ｂｏｏｔｈアルゴリズムは、ＡおよびＢが２の補数の整数である場合の乗算Ａ×Ｂにおいて部分積の個数を削減するためのアルゴリズムとして知られている。部分積生成手段２０１は、被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積として、Ａ、２Ａ、−Ａ、−２Ａ、および０を表す部分積を生成する。
【００２４】
上記動作モード（後述する補数モード）において、エンコーダ手段２０２は、乗数Ｂの連続する３つのビットｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１をエンコードして、ｂ１、ｂ０、およびｂ−１の３つのビットに対しては−Ａを表す部分積を選択するための選択信号を生成し、ｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１（ｉ≠０）の３つのビットに対しては０を表す部分積を選択するための選択信号を生成する。
【００２５】
これにより、選択手段２０３は、ｂ１、ｂ０、およびｂ−１の３つのビットに対しては−Ａを表す部分積を選択し、それ以外のビットに対しては０を表す部分積を選択するので、加算手段２０４は、−Ａを表す部分積と０とを加算することになる。−ＡはＡの２の補数またはＡの１の補数で表されるから、この動作モードにおける乗算結果は、Ａの２の補数またはＡの１の補数（＝−Ａ）となる。
【００２６】
これに対して、通常の動作モードにおいては、演算装置は乗算Ａ×Ｂの結果を出力することができる。このように、乗算Ａ×Ｂを行う演算装置において−Ａを乗算結果として出力する動作モードを設けることで、図１５の反転／非反転回路１４１がなくても図１２の▲６▼の処理を行うことが可能となる。この演算装置をブロック単位演算器１３１に組み込めば、ブロック単位演算器１３１における遅延時間を短縮して、動作周波数を向上させることができる。
【００２７】
図１の部分積生成手段２０１は、例えば、後述する図５のシフト回路２４１、２４３、および反転回路２４２に対応し、図１のエンコーダ手段２０２は、例えば、図５のエンコーダ２４７に対応する。また、図１の選択手段２０３は、例えば、図５の選択回路２４４に対応し、図１の加算手段２０４は、例えば、図５の多段加算回路２４５に対応する。
【００２８】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本実施形態では、乗算加算器のアーキテクチャに２次Ｂｏｏｔｈアルゴリズムを採用して、図１５の回路のブロック単位演算器１３１の最大遅延経路＜ｎｉ→反転／非反転回路１４１→セレクタ１１６→乗算加算器１２０→（ｃ１，ｃ２，ｙ’ｉ，ｙ’ｉ−１，ｍ，ｔｍｐ）＞上の反転／非反転回路１４１を乗算加算器１２０に吸収させる。これにより、ブロック単位演算器１３１における遅延時間を短縮して、動作周波数を向上させる。
【００２９】
また、図１５の回路では、反転／非反転回路１４１の規模がブロックビット数ｋに比例するため、ｋが大きくなるほど、図１３の回路の規模に対する増分が顕著になる。しかし、本実施形態では、反転／非反転回路１４１を乗算加算器１２０に吸収することにより、図１３の回路とほぼ同じ規模で図１２のアルゴリズムを実現することができる。
【００３０】
２次Ｂｏｏｔｈアルゴリズムは、ＡおよびＢが−２ｑ−１≦Ａ，Ｂ≦２ｑ−１−１でｑビットの２の補数の整数である場合の乗算Ａ×Ｂについて、ＡおよびＢのビット表現をそれぞれ｛ａｑ−１，ａｑ−２，．．．，ａ１，ａ０｝および｛ｂｑ−１，ｂｑ−２，．．．，ｂ１，ｂ０｝として、以下の手順により乗算Ａ×Ｂの部分積の個数をｑ／２に削減するアルゴリズムである。
・Ｂの多項式表現である式（１）を式（２）に変形する。
・さらに、ｄｉを−２、−１、０、＋１、および＋２を取りうるビットと定義して、式（２）を式（３）で表す。
2004258141.tif 000003
ｑは偶数である必要があるが、ｑが奇数であっても＋１補正して２次Ｂｏｏｔｈアルゴリズムを適用することができる。ＡおよびＢが０≦Ａ，Ｂ≦２ｋ−１のｋビットの整数である場合の乗算Ａ×Ｂについても、ｋが偶数であればｑ＝ｋ＋２、ａｑ−１＝ａｑ−２＝ｂｑ−１＝ｂｑ−２として、ｋが奇数であればｑ＝ｋ＋１、ａｑ−１＝ｂｑ−１として２次Ｂｏｏｔｈアルゴリズムを適用することができる。
【００３１】
図２は、ＡおよびＢが０≦Ａ，Ｂ≦２ｋ−１のｋビットの整数である場合の２次Ｂｏｏｔｈアルゴリズムによる乗算Ａ×Ｂを示している。この場合の動作は次の通りである。
▲１▼ｋビットのＡおよびＢをｑビットに補正してＡ’およびＢ’とする。このとき、ｋが偶数であればｑ＝ｋ＋２、ａｑ−１＝ａｑ−２＝ｂｑ−１＝ｂｑ−２とし、ｋが奇数であればｑ＝ｋ＋１、ａｑ−１＝ｂｑ−１とする。
▲２▼０≦ｉ≦ｑ／２−１とした場合のＢ’の３つのビットｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を、Ｂｏｏｔｈエンコーダ２１１を用いてｄｉにエンコードする。
▲３▼ｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１から得られたｄｉを−２、−１、０、＋１、および＋２を取りうるＢ’のビットとして用いて、乗算Ａ’×Ｂ’を行う。この乗算における各部分積はＡ’×ｄｉ（２の補数）である。
▲４▼積Ａ’×Ｂ’（２ｑビット）から下位２ｋビットを切り出し、積Ａ×Ｂ（２ｋビット）とする。
【００３２】
図３は、２次Ｂｏｏｔｈアルゴリズムを採用した乗算器に、出力が−Ａ（２の補数）になるモード（補数モード）を追加した乗算器を示している。図３の乗算器においては、モード選択信号により、通常の乗算Ａ×Ｂを行うモード（通常モード）と補数モードとが切り替えられる。
【００３３】
補数モード時には、Ｂｏｏｔｈエンコーダ２２１の出力ｄ０が−１になり、それ以外の出力ｄｉ（ｉ≠０）が０になるため、部分積Ａ’×ｄ０は−Ａ’（２の補数）になり、他の部分積Ａ’×ｄｉ（ｉ≠０）は０になる。したがって、乗算器の出力Ｘは−Ａ（２の補数）になる。補数モード時のＢはｄｏｎ’ｔ  ｃａｒｅで構わない。
【００３４】
ここでは、部分積Ａ’×ｄ０を２の補数としている。２の補数は１の補数に１を加えたものであるから、２の補数を回路で実現するときは、ビットパターンを１の補数にして（つまり、ビット反転して）から、＋１加算する。しかし、この操作をそのまま行うと、部分積加算にとても時間がかかる。
【００３５】
そこで、部分積Ａ’×ｄ０を１の補数としておき、２の補数にするための＋１加算を部分積加算と一緒に行うのが一般的である。図３のＢｏｏｔｈエンコーダ２２１のｓｉは、この＋１加算を実現するための補正値として用いられ、ｄｉ＜０のときｓｉ＝１となり、ｄｉ≧０のときｓｉ＝０となる。
【００３６】
図３の乗算器では、補数モード時のＢがｄｏｎ’ｔ  ｃａｒｅで構わないのに対して、補数モード時にＢ＝０を入力すれば、補数モード時のｄｉ（ｉ≠０）として通常モード時と同じ値を用いることができる。
【００３７】
図４は、このような乗算器を示している。補数モード時には、Ｂｏｏｔｈエンコーダ２３１の出力ｄ０が−１になり、それ以外の出力ｄｉ（ｉ≠０）は、Ｂ＝０の場合の通常モード時の出力ｄｉ（ｉ≠０）と同じ０になる。このため、部分積Ａ’×ｄ０は−Ａ’（２の補数）になり、他の部分積Ａ’×ｄｉ（ｉ≠０）は０になる。したがって、乗算器の出力Ｘは−Ａ（２の補数）になる。
【００３８】
図４の乗算器は、図３の乗算器に比べてＢｏｏｔｈエンコーダの規模が小さくて済むため、乗算器を使用する側でＢ＝０を入力するのが容易である場合は、最適な乗算器であるといえる。
【００３９】
図３および図４の乗算器は、例えば、図５に示すような回路で構成される。図５の回路は、レジスタ２４０、２４６、シフト回路２４１、２４３、反転回路２４２、選択回路２４４、多段加算回路２４５、およびエンコーダ２４７を備える。エンコーダ２４７は、図３のＢｏｏｔｈエンコーダ２２１または図４のＢｏｏｔｈエンコーダ２３１に対応する。
【００４０】
レジスタ２４６のＢ’は２ビットずつの組に分割され、各組のビット対が下位の組の上位ビットとともにエンコーダ２４７に順番に入力される。エンコーダ２４７は、これらの３つの入力ｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１からｄｉに相当する選択信号を生成し、Ａ’の倍数を選択する選択回路２４４に出力する。
【００４１】
シフト回路２４１、２４３は、入力されたビットパターンを１ビットシフトし、反転回路２４２は、入力されたビットパターンを反転させる。これらの回路により、レジスタ２４０のＡ’からは、直接（Ａ’）、１ビットシフト（２Ａ’）、反転（−Ａ’（１の補数））、および反転の１ビットシフト（−２Ａ’）の４種類の値が生成され、選択回路２４４に入力される。
【００４２】
選択回路２４４は、エンコーダ２４７の各ビット対出力に対応して設けられており、エンコーダ２４７からの選択信号に応じて４種類の入力値の１つを選択し、部分積Ａ’×ｄｉとして多段加算回路２４５に出力する。このとき、選択回路２４４からは補正値ｓｉも同時に出力される。多段加算回路２４５は、入力された部分積Ａ’×ｄｉおよび補正値ｓｉを加算して、乗算結果Ｘ（＝Ａ×Ｂ）を出力する。
【００４３】
図３および図４の乗算器では、補数モード時にｄ０＝−１およびｓ０＝１とすることで、出力を−Ａ（２の補数）としているが、ｓ０＝０とすればこの出力を−Ａ（１の補数）にすることができる。図１４に示したように、多倍長減算では、ビットパターン全体として２の補数であってもブロック単位の演算では１の補数を扱うことになるので、乗算器の出力を−Ａ（１の補数）にすることが重要である。この場合、部分積Ａ’×ｄ０に対応する−Ａ’を生成する回路は、図６に示すように、反転回路２５１および加算回路２５２を用いて構成される。
【００４４】
図６の反転回路２５１は、Ａ’を反転して出力し、加算回路２５２は、反転されたＡ’と補正値２５３とを加算して出力する。補正値２５３は、通常モード時に１となり、補数モード時に０となるので、通常モード時は−Ａ’（２の補数）が出力され、補数モード時は−Ａ’（１の補数）が出力される。
【００４５】
図６の反転回路２５１および加算回路２５２は、それぞれ、図５の反転回路２４２および多段加算回路２４５に対応し、補正値２５３は補正値ｓ０に対応する。この構成では、通常モードと補数モードとでｓ０が異なる値をとることになる。
【００４６】
図５の乗算器の出力と、０≦Ｃ≦２ｋ−１−１および０≦Ｄ≦２ｋ−１−１であるｋビットのＣおよびＤとを加算する、Ａ×Ｂ＋Ｃ＋Ｄの乗算加算器は、図７のような回路で構成される。図７の回路では、図５の多段加算回路２４５の代わりに、多段加算回路２６１が用いられている。
【００４７】
多段加算回路２６１は、選択回路２４４からの部分積および補正値に加えて、外部から入力されるＣおよびＤを加算し、乗算加算結果をＸ（＝Ａ×Ｂ＋Ｃ＋Ｄ）を出力する。補数モード時は、Ｘ＝−Ａ（２の補数）＋Ｃ＋Ｄとなる。
【００４８】
しかし、図６の−Ａ’生成回路のような構成を採用すれば、補数モード時の出力は、Ｘ＝−Ａ（１の補数）＋Ｃ＋Ｄとなる。この場合、図６の反転回路２５１および加算回路２５２は、それぞれ、図７の反転回路２４２および多段加算回路２６１に対応し、補正値２５３は補正値ｓ０に対応する。
【００４９】
図８および図９は、図７において補数モード時の出力を−Ａ（１の補数）＋Ｃ＋Ｄとした乗算加算器を使用して、図１４の多倍長減算（Ｙ＝Ｙ−Ｎ）を実行する回路を示している。図８の多倍長減算回路は、レジスタ２７１、２７２、２７３、２７４、２７５、２７７、乗算加算器２７６、および反転回路２７８を備え、図９の多倍長減算回路は、図８において乗算加算器２７６の代わりに乗算加算器２８１を用いた構成を有する。
【００５０】
図８の乗算加算器２７６は、図３のＢｏｏｔｈエンコーダ２２１に従って乗算を行うため、入力Ｂはｄｏｎ’ｔ  ｃａｒｅとなっている。これに対して、図９の乗算加算器２８１は、図４のＢｏｏｔｈエンコーダ２３１に従って乗算を行うため、入力Ｂは０となっている。図８および図９の回路の動作は次の通りである。
（０）レジスタ２７７のキャリー（ｃａｒｒｙ）の値を１に初期化する。
（１）レジスタ２７１のＮからｎｉを選択してレジスタ２７３に格納し、レジスタ２７２のＹからｙｉを選択してレジスタ２７４に格納する。
（２）乗算加算器２７６は、入力をＡ＝ｎｉ、Ｂ＝ｄｏｎ’ｔ  ｃａｒｅ、Ｃ［ｋ−１：１］＝０、Ｃ［０］＝ｃａｒｒｙ（ｉ−１番目のブロックの演算結果からのキャリー）、Ｄ＝ｙｉとして、補数モード時のｋビットの演算Ｘ＝−Ａ（１の補数）＋Ｃ＋Ｄを実行する。
【００５１】
また、乗算加算器２８１は、入力をＡ＝ｎｉ、Ｂ＝０、Ｃ［ｋ−１：１］＝０、Ｃ［０］＝ｃａｒｒｙ、Ｄ＝ｙｉとして、Ｘ＝−Ａ（１の補数）＋Ｃ＋Ｄを実行する。
（３）乗算加算器２７６および２８１の出力のうち、Ｘ［ｋ−１：０］をｙ’ｉ−１としてレジスタ２７５に保存し、Ｘ［ｋ］を反転回路２７８により反転させてレジスタ２７７に格納する。レジスタ２７７に格納されたｃａｒｒｙは、ｉ＋１番目のブロックへのキャリーとなる。ここで、Ｘ［ｋ］を反転させるのは、図１４に示したように、補数のキャリーが必要となるためである。Ｘ［２ｋ−１：ｋ＋１］は不要なので、無視される。
（４）レジスタ２７５のｙ’ｉ−１をｙ  ｉとしてレジスタ２７２に格納する。
（５）（１）〜（４）の動作を０≦ｉ≦ｇの範囲で繰り返す。
（６）（５）の動作が終了した時点で、レジスタ２７２のＹにはＹ−Ｎの演算結果が格納されている。また、ｇ番目のブロックの演算結果Ｘ［ｋ］は、Ｙ＝Ｙ−Ｎの符号（１：Ｙ≧Ｎ，０：Ｙ＜Ｎ）を表す。
【００５２】
図１０および図１１は、図７において補数モード時の出力を−Ａ（１の補数）＋Ｃ＋Ｄとした乗算加算器を使用して、モンゴメリ乗算剰余の多倍長演算（Ｙ＝ＡＢ２−ｋｇ  ｍｏｄ  Ｎ）を実行する回路を示している。図１０の多倍長演算回路は、レジスタ２９１、２９２、２９５、２９９、ブロック選択回路２９３、２９４、２９６、２９８、３００、およびブロック単位演算器２９７を備え、図１１の多倍長演算回路は、図１０においてブロック単位演算器２９７の代わりにブロック単位演算器３３１を用いた構成を有する。
【００５３】
図１０において、レジスタ２９１、２９２、および２９５には、Ａ、Ｂ、およびＮがそれぞれｇ個のブロックに分割されて格納され、ブロック選択回路２９３、２９４、および２９６は、それぞれＡ、Ｂ、およびＮのブロックａｉ、ｂｉ、およびｎｉを選択して、ブロック単位演算器２９７に出力する。また、ブロック選択回路２９８は、レジスタ２９９からＹのブロックｙｉを選択して、ブロック単位演算器２９７に出力する。
【００５４】
ブロック単位演算器２９７は、ブロックａｉ、ｂｉ、ｎｉ、ｎ’０、およびｙ’ｉを入力として演算を行い、演算結果ｙ’ｉおよびｙ’ｉ−１を出力する。ブロック選択回路３００は、ｙ’ｉおよびｙ’ｉ−１のいずれかを選択し、ブロックｙｉまたはｙｉ−１としてレジスタ２９９に格納する。図１１の多倍長演算回路の動作も同様である。
【００５５】
ブロック単位演算器２９７は、図１０の下方に示すように、レジスタ３１１、３１２、３１３、３１４、３１５、３２１、３２２、３２３、３２４、３２５、３２６、セレクタ３１６、３１７、３１８、３１９、乗算加算器２７６、および反転回路３２０を備える。図１１のブロック単位演算器３３１は、図１０において乗算加算器２７６の代わりに乗算加算器２８１を用い、さらにセレクタ３３２を追加した構成を有する。
【００５６】
図１０および図１１の回路では、図１２のアルゴリズムの▲６▼以外の処理（通常処理）と▲６▼の処理（最終処理）が、処理状態信号３０１によって切り替えられる。乗算加算器２７６および２８１は、通常処理のときは通常モードの演算（Ｘ＝Ａ×Ｂ＋Ｃ＋Ｄ）を行い、最終処理のときは補数モードの演算（Ｘ＝−Ａ（１の補数）＋Ｃ＋Ｄ）を行う。また、図１１のセレクタ３３２は、通常処理のときは入力１を選択し、最終処理のときは入力０を選択して、乗算加算器２８１に出力する。
【００５７】
図１０および図１１の回路の通常処理に対応する動作は図１３の回路と同じであるため、最終処理に対応する動作のみを説明することにする。図１０および図１１の回路の処理▲６▼に相当する動作は次の通りである。
（０）レジスタ３２３のｙ’ｉの値を１に初期化し、乗算加算器２７６および２８１を補数モードに設定する。
（１）レジスタ２９５のＮからｎｉを選択してレジスタ３１２に格納し、レジスタ２９９のＹからｙｉを選択してレジスタ３１５に格納する。
（２）セレクタ３１６、３１８、および３１９は、それぞれ、Ａ＝ｎｉ、Ｃ＝ｙ’ｉのｂｉｔ０を反転回路３２０により反転した値（ｉ−１番目のブロックの演算結果からのキャリー）、およびＤ＝ｙｉと選択する。
【００５８】
このとき、図１０の回路では、セレクタ３１７の出力Ｂはｄｏｎ’ｔ  ｃａｒｅで構わない。これに対して、図１１の回路では、セレクタ３３２が入力０を選択し、セレクタ３１７がセレクタ３３２の出力を選択するので、結局、Ｂ＝０と選択される。
【００５９】
そして、乗算加算器２７６および２８１は、補数モード時のｋビットの演算Ｘ＝−Ａ（１の補数）＋Ｃ＋Ｄを実行する。
（３）乗算加算器２７６および２８１の出力のうち、Ｘ［ｋ−１：０］をｙ’ｉ−１としてレジスタ３２４に保存し、Ｘ［２ｋ−１：ｋ］をｙ’ｉとしてレジスタ３２３に格納する。レジスタ３２３に格納されたｙ’ｉのｂｉｔ０（Ｘ［ｋ］）は、反転回路３２０により反転されて、ｉ＋１番目のブロックへのキャリーとなる。
（４）レジスタ３２４のｙ’ｉ−１をｙ  ｉとしてレジスタ２９９に格納する。レジスタ３２３のｙ’ｉのｂｉｔ０以外のビットは不要なので、無視される。
（５）（１）〜（４）の動作を０≦ｉ≦ｇの範囲で繰り返す。
（６）（５）の動作が終了した時点で、レジスタ２９９のＹにはＹ−Ｎの演算結果が格納されている。また、レジスタ３２３に格納されたｙ’ｇのｂｉｔ０は、Ｙ＝Ｙ−Ｎの符号（１：Ｙ≧Ｎ，０：Ｙ＜Ｎ）を表す。
【００６０】
（付記１）  ビットパターンで表された被乗数Ａと乗数Ｂの乗算を行う演算装置であって、
被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する選択手段と、
前記選択手段から出力される、ｉの数と同じ数だけの部分積を加算して、乗算結果を生成する加算手段とを備え、
前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの２の補数を生成して、該被乗数Ａの２の補数を前記乗算結果として出力するような動作モードを設けたことを特徴とする演算装置。
【００６１】
（付記２）  ビットパターンで表された被乗数Ａと乗数Ｂの乗算を行う演算装置であって、
被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する選択手段と、
前記選択手段から出力される、ｉの数と同じ数だけの部分積を加算して、乗算結果を生成する加算手段とを備え、
前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの１の補数を生成して、該被乗数Ａの１の補数を前記乗算結果として出力するような動作モードを設けたことを特徴とする演算装置。
【００６２】
（付記３）  前記エンコーダ手段は、前記動作モードにおいて、乗数Ｂの値にかかわらず、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力することを特徴とする付記２記載の演算装置。
【００６３】
（付記４）  前記エンコーダ手段は、前記動作モードにおいて、乗数Ｂとして０が入力された場合に、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力することを特徴とする付記２記載の演算装置。
【００６４】
（付記５）  ビットパターンで表された被乗数Ａと乗数Ｂを乗算し、乗算結果とビットパターンで表された数Ｃおよび数Ｄとを加算する、乗算加算を行う演算装置であって、
被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する選択手段と、
前記選択手段から出力される、ｉの数と同じ数だけの部分積と数Ｃと数Ｄとを加算して、乗算加算結果を生成する加算手段とを備え、
前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの１の補数を生成し、該被乗数Ａの１の補数と数Ｃと数Ｄとを加算した結果を前記乗算加算結果として出力するような動作モードを設けたことを特徴とする演算装置。
【００６５】
（付記６）  ｋビットのビットパターンで表された被乗数Ａと乗数Ｂを乗算し、乗算結果とｋビットのビットパターンで表された数Ｃおよび数Ｄとを加算することで、１ブロックがｋビットであるｇ＋１個のブロックからなる整数Ｙから１ブロックがｋビットであるｇ個のブロックからなる整数Ｎを減算する演算を行う演算装置であって、
被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する選択手段と、
前記選択手段から出力される、ｉの数と同じ数だけの部分積と数Ｃと数Ｄとを加算して、２ｋビットの乗算加算結果を生成する加算手段と、
前記乗算加算結果の一部のビットを反転する反転手段とを備え、
前記部分積生成手段が、整数Ｎのｊ番目のブロックｎｊを被乗数Ａとして用い、前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの１の補数を生成し、ｊ−１番目のブロックの乗算加算からのキャリーを数Ｃとして用い、整数Ｙのｊ番目のブロックｙｊを数Ｄとして用いて、該被乗数Ａの１の補数と数Ｃと数Ｄとを加算した結果をｊ番目のブロックの乗算加算結果として出力し、前記反転手段が、該ｊ番目のブロックの乗算加算結果の一部のビットを反転してｊ＋１番目のブロックの乗算加算へのキャリーを生成することを特徴とする演算装置。
【００６６】
（付記７）  ビットパターンで表された整数ＩおよびＪと剰余の法Ｎを１ブロックがｋビットであるｇ個のブロックにそれぞれ分割して、Ｙ＝ＩＪ２−ｋｇ  ｍｏｄ  Ｎとなるモンゴメリ乗算剰余の多倍長演算を行う演算装置であって、
ｋビットの被乗数Ａ、乗数Ｂ、数Ｃ、および数Ｄのそれぞれについて、与えられた複数の値のいずれかを選択して出力する第１の選択手段と、
前記第１の選択手段から出力される被乗数Ａから２次Ｂｏｏｔｈアルゴリズムにおける複数の部分積を生成する部分積生成手段と、
前記第１の選択手段から出力される乗数Ｂを前記２次Ｂｏｏｔｈアルゴリズムによりエンコードして、乗数Ｂの連続する３つのビットであるｂ２ｉ＋１、ｂ２ｉ、およびｂ２ｉ−１を指定するｉの値に応じた選択信号を出力するエンコーダ手段と、
前記選択信号に応じて、前記複数の部分積のいずれかを選択して出力する第２の選択手段と、
前記第２の選択手段から出力される、ｉの数と同じ数だけの部分積と、前記第１の選択手段から出力される数Ｃと数Ｄとを加算して、２ｋビットの乗算加算結果を生成する加算手段と、
前記乗算加算結果の一部のビットを反転する反転手段とを備え、
前記第１の選択手段が、整数Ｎのｊ番目のブロックｎｊを被乗数Ａとして選択し、ｊ−１番目のブロックの乗算加算からのキャリーを数Ｃとして選択し、Ｙのｊ番目のブロックｙｊを数Ｄとして選択し、前記エンコーダ手段が、ｉが０のときには−Ａを表す部分積を選択するための選択信号を出力し、ｉが０以外のときには０を表す部分積を選択するための選択信号を出力し、前記加算手段が、該−Ａを表す部分積から被乗数Ａの１の補数を生成し、該被乗数Ａの１の補数と数Ｃと数Ｄとを加算した結果をｊ番目のブロックの乗算加算結果として出力し、前記反転手段が、該ｊ番目のブロックの乗算加算結果の一部のビットを反転してｊ＋１番目のブロックの乗算加算へのキャリーを生成するような動作モードを設けたことを特徴とする演算装置。
【００６７】
【発明の効果】
本発明によれば、モンゴメリ乗算剰余の多倍長減算を行うために必要となる回路を乗算加算器に吸収させることができ、モンゴメリ乗算剰余の多倍長演算アルゴリズムを、従来の回路より小さい規模のハードウェアで実現することが可能となる。
【００６８】
また、多倍長減算を行うために必要となる回路を乗算加算器に吸収させることで、回路の遅延時間が短縮されるため、従来の回路より高い動作周波数で動作させることができる。
【００６９】
モンゴメリ乗算剰余の多倍長演算アルゴリズムは、ＲＳＡ暗号や楕円曲線暗号で使われる演算の中では計算量が多いものであり、本発明はこれらの暗号処理の速度向上に寄与するところが大きい。
【図面の簡単な説明】
【図１】本発明の演算装置の原理図である。
【図２】２次Ｂｏｏｔｈアルゴリズムによる演算を示す図である。
【図３】第１の乗算器を示す図である。
【図４】第２の乗算器を示す図である。
【図５】乗算器の回路構成図である。
【図６】−Ａ’生成回路を示す図である。
【図７】乗算加算器の回路構成図である。
【図８】第１の多倍長減算回路を示す図である。
【図９】第２の多倍長減算回路を示す図である。
【図１０】第１の多倍長演算回路を示す図である。
【図１１】第２の多倍長演算回路を示す図である。
【図１２】モンゴメリ乗算剰余の多倍長演算アルゴリズムを示す図である。
【図１３】仮想的な乗算剰余演算回路を示す図である。
【図１４】多倍長減算を示す図である。
【図１５】仮想的な多倍長演算回路を示す図である。
【符号の説明】
１０１、１３１、２９７、３３１  ブロック単位演算器
１１１、１１２、１１３、１１４、１１５、１２１、１２２、１２３、１２４、１２５、１２６、２４０、２４６、２７１、２７２、２７３、２７４、２７５、２７７、２９１、２９２、２９５、２９９、３１１、３１２、３１３、３１４、３１５、３２１、３２２、３２３、３２４、３２５、３２６、  レジスタ
１１６、１１７、１１８、１１９、３１６、３１７、３１８、３１９、３３２セレクタ
１４１  反転／非反転回路
１２０、２７６、２８１  乗算加算器
２０１  部分積生成手段
２０２  エンコーダ手段
２０３  選択手段
２０４  加算手段
２１１、２２１、２３１  Ｂｏｏｔｈエンコーダ
２４１、２４３  シフト回路
２４２、２５１、２７８、３２０  反転回路
２４４  選択回路
２４５、２６１  多段加算回路
２４７  エンコーダ
２５２  加算回路
２５３  補正値
２９３、２９４、２９６、２９８、３００  ブロック選択回路
【図１】
2004258141.tif 000004
【図２】
2004258141.tif 000005
【図３】
2004258141.tif 000006
【図４】
2004258141.tif 000007
【図５】
2004258141.tif 000008
【図６】
2004258141.tif 000009
【図７】
2004258141.tif 000010
【図８】
2004258141.tif 000011
【図９】
2004258141.tif 000012
【図１０】
2004258141.tif 000013
【図１１】
2004258141.tif 000014
【図１２】
2004258141.tif 000015
【図１３】
2004258141.tif 000016
【図１４】
2004258141.tif 000017
【図１５】
2004258141.tif 000018