(57)【特許請求の範囲】
【請求項１】
被乗数ａと乗数ｂ（ｂはｋｂビットのデータ）との積に対して、法ｐ（ｐはｋビットデータ）による剰余と合同な値を次式の累算値として算出する剰余乗算装置であって、
【数１】
0004293665.tif 000009
ここで[[kｂ/s]]は商kｂ/sの整数部分であり、
iは０から[[k/s]]までの整数であり、
C(i)は漸化式で表わされi=0のときC(i)=a、i>=1のときC(i)≡(C(i-1)*2s) modｐであり（≡は両辺の値が法ｐにおいて合同であることを示す）、
b[s*i+s-1:s*i]は、ｋビットの乗数ｂのうち2s*i+s-1の位から2s*iの位までのｓビットの部分乗数であり、
前記剰余乗算装置は、
ｍ(ｍはｓ以上の整数)ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶するテーブル手段と、
初回（i=0）では被乗数ａを中間数C(0)として出力し、
２回目以降（i>0）では、前回出力された中間数C(i-1)をｓビット桁上げし、桁上げ後の中間数の下位ｋビットを除く上位のｍビットについての前記剰余をテーブル手段から読み出し、読み出した剰余と下位ｋビットとを加算することにより新たな中間数(i)を算出する中間数算出手段と
を備え、
算出された各中間数C(i)と、それに対応する部分乗数b[s*i+s-1:s*i]との部分積C(i)*b[s*i+s-1:s*i]を順次累算することによって前記累算値を算出すること
を特徴とする剰余乗算装置。
【請求項２】
前記中間数算出手段は、
中間数を保持する第１保持手段と、
部分乗数b[s*i+s-1:s*i]に対応して、第１保持手段に保持された中間数をｓビット桁上げする桁上げ手段と、
桁上げ後の中間数を、桁上げ後の中間数における下位ｋビットよりも上位のｍビットの部分である上位データと下位ｋビットの部分である下位データとに分割する分割手段と、
分割手段による上位データに対する法ｐによる剰余を前テーブル手段から読み出す読み出し手段と、
テーブル手段から読み出された剰余と、分割手段による下位データとを加算することにより新たな中間数を得る加算手段と
を備え、
前記第１保持手段は、加算手段において新たな中間数が得られる度にその保持内容を新たな中間数に更新し、前記初回では被乗数を中間数として出力し、前記２回目以降では更新後の新たな中間数を出力すること
を特徴とする請求項１記載の剰余乗算装置。
【請求項３】
前記剰余乗算装置は、さらに、
前記分割手段、読み出し手段、加算手段を利用することにより、前記累算値の法ｐによる剰余を求める後処理手段
を備えることを特徴とする請求項２記載の剰余乗算装置。
【請求項４】
前記テーブル手段は、
ｍビットにより表現される各値に対応するアドレスが入力され、そのアドレスが指す記憶領域に当該アドレスに対応するｍビットの値の２k倍に対する法ｐによる剰余を予め記憶するメモリ素子を有すること
を特徴とする請求項２及び３記載の剰余乗算装置。
【請求項５】
前記mビットは下位m1ビットと上位m2ビット（m＝m1+m2）とに分割され、
前記mビットにより表現される各値は、m1ビットにより表現される値とm2ビットにより表現される値との組み合わせに対応し、
前記テーブル手段は、
m1ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶する第１部分テーブル手段と、
m2ビットにより表現される各値について、その値の２k+m1倍に対する法ｐによる剰余を予め記憶する第２部分テーブル手段と
を備え、
前記加算手段は、第１、第２部分テーブルからの読み出されたそれぞれの剰余と、前記下位データとを加算することにより新たなっ中間数を得る
ことを特徴とする請求項２及び３記載の剰余乗算装置。
【請求項６】
前記mビットは下位側からt(3≦t≦m)個の部分ビットm1、…、mtに分割され、
前記mビットにより表現される各値は、各mi（ｉは１からｔまで整数）ビットにより表現される値（ｔ個）を組み合わせたものに対応し、
前記テーブル手段は、
部分ビットmiビットにより表現される各値について、その値の２k+x倍（ここでｘ=m1+…＋m(i-1)である）に対する法ｐによる剰余を予め記憶するｔ個の部分テーブル手段Ｔiを備え、
前記加算手段は、ｔ個の部分テーブル手段Tiからの読み出されたｔ個の剰余と、前記下位データとを加算することにより新たな中間数を得る
ことを特徴とする請求項２及び３記載の剰余乗算装置。
【請求項７】
前記mビットは下位側からt(2≦t≦m)個の部分ビットm1、…、mtに分割され、
前記テーブル手段は、
ｘが次式で表わされるとき、各部分テーブル手段Ｔiは、部分ビットmiビットにより表現される各値について、その値の２k+x倍に対する法ｐによる剰余を予め記憶するｔ個の部分テーブル手段Ｔi（ｉは１からｔの整数）を備え、
ここでｘは次式によって表わされるものとする
【数２】
0004293665.tif 000010
前記加算手段は、ｔ個の部分テーブル手段Ｔiから読み出されたｔ個の剰余と前記下位データとを加算することにより新たな中間数を得る
ことを特徴とする請求項２及び３記載の剰余乗算装置。
【請求項８】
各部分テーブル手段Ｔiは、前記剰余をｋビットのデータとして記憶すること
を特徴とする請求項７記載の剰余乗算装置。
【請求項９】
前記剰余乗算装置は、さらに累算手段と補正手段とを備え、
前記累算手段は、
初期値として０を保持する第３レジスタと、
部分積C(i)*b[s*i+s-1:s*i]と第３レジスタに保持された累算値とを加算し、加算結果を新たな累算値として第３レジスタに出力して保持させる加算器と
を備え、
前記補正手段は、
ｐの整数倍の値をもつ補正値を保持する補正値保持手段と、
前記第３レジスタに保持された累算値が所定の値以上であれば、補正値保持手段に保持された補正値を、前記加算器に減算させる補正制御手段と
を備えることを特徴とする請求項８記載の剰余乗算装置。
【請求項１０】
前記第３レジスタは符号ビットを有し、
前記補正制御手段は、第３レジスタの累算値が正であれば、前記加算器に対して累算値と部分積との加算と同時に前記補正値を減算させ、
前記補正値は、ｐの整数倍であってその絶対値が前記部分積の最大値(t+1)(2 s -1)p以下の値であること
を特徴とする請求項９記載の剰余乗算装置。
【請求項１１】
前記法ｐはｐ＝2k−αの関係を満たし、
各部分テーブル手段Ｔiは、前記剰余をk3ビットのデータとして記憶する、
ここで、k3はt*2m*αのビット数であり、
前記αは、k3がｋより小さくなるように定められた定数であることを
特徴とする請求項７記載の剰余乗算装置。
【請求項１２】
各部分テーブル手段Ｔiは、miビットにより表現される０から(2mi-1)までの値に対応する2mi個のエントリを有し、
ｊ(jは０から2miまで)番目のエントリは、j*2m1+…+m(i-1) *αを格納していることを特徴とする請求項１１記載の剰余乗算装置。
【請求項１３】
前記剰余乗算装置は、さらに累算手段と補正手段とを備え、
前記累算手段は、
初期値として０を保持する第３レジスタと、
部分積C(i)*b[s*i+s-1:s*i]と第３レジスタに保持された累算値とを加算し、加算結果を新たな累算値として第３レジスタに出力して保持させる加算器と
を備え、
前記補正手段は、
ｐの整数倍の値をもつ補正値を保持する補正値保持手段と、
前記第３レジスタに保持された累算値が所定の値以上であれば、補正値保持手段に保持された補正値を、前記加算器に減算させる補正制御手段と、
を備えることを特徴とする請求項１２記載の剰余乗算装置。
【請求項１４】
前記第３レジスタは符号ビットを有し、
前記補正制御手段は、第３レジスタの累算値が正であれば、前記加算器に対して累算値と部分積との加算と同時に前記補正値を減算させ、
前記補正値は、ｐの整数倍であって前記部分積の最大値(2s+1-2)p以下の値であること
を特徴とする請求項１３記載の剰余乗算装置。
【請求項１５】
被乗数と乗数との積に対する法ｐ（ｐはｋビットデータ）による剰余と合同な数を算出する剰余乗算装置において、
乗数をｓ（ｓは２以上の整数）ビットずつに分けて得られるｓビットの部分乗数を下位側から順に出力する出力手段と、
各部分乗数の位に応じて、被乗数を桁上げし、桁上げ後の被乗数に対して、法ｐによる剰余と合同な数（以下中間数と呼ぶ）を算出する第１算出手段と、
出力手段により出力された部分乗数と、当該部分乗数に対応して第１算出手段により算出された前記中間数との積を部分積として算出する第２算出手段と、
第２算出手段に算出された部分積を累算する累算手段と、
累算手段に累算された累算値にｐの整数倍の値を加減算することにより、累算値を所定のビット数を越えないように補正する補正手段と、
出力手段により全ての部分乗数が出力されるまで、第１算出手段による中間数の算出と、第２算出手段による部分積の算出と、累算手段による累算と、補正手段による補正とを繰り返し行わせる制御手段と
を備え、
前記第１算出手段は、ｍ(ｍはｓ以上の整数)ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶し、
制御手段による繰り返しのうち初回では被乗数を中間数として出力し、２回目以降では、前回出力された中間数をｓビット桁上げし、桁上げ後の中間数の下位ｋビットより上位のｍビットについてテーブル手段を読み出し、読み出した数と下位ｋビットとを加算することにより新たな中間数を算出すること
を特徴とする剰余乗算装置。
【請求項１６】
前記第１算出手段は、
被乗数を保持する第１保持手段と、
出力手段から２回目以降に出力される部分乗数に対応して、第１保持手段に保持された中間数をｓビット桁上げする桁上げ手段と、
桁上げ後の中間数を桁上げ後の中間数における下位ｋビットよりも上位のｍビットの部分である上位データと下位ｋビットの部分である下位データとに分割する分割手段と、
分割手段による上位データに対する法ｐによる剰余を前記テーブル手段から読み出す読み出し手段と、
テーブル手段から読み出された剰余と、分割手段による下位データとを加算することにより新たな中間数を得る加算手段と、
を備え、
前記第１保持手段は、前記加算手段により新たな中間数が得られる度にその保持内容を新たな中間数に更新し、前記初回では被乗数を中間数として出力し、前記２回目以降では更新後の新たな中間数を出力し、
前記第２算出手段は、第１保持手段の保持内容を中間数として前記部分積を算出すること
を特徴とする請求項15記載の剰余乗算装置。
【請求項１７】
前記制御手段は、第１〜第３ステージを含むパイプライン処理を制御する、第１ステージでは出力手段に部分乗数を出力させるとともに第１算出手段に中間数を出力させ、第２ステージでは第２算出手段に部分積を算出させ、第３ステージでは累算手段に累算させるともに補正手段に補正させること
を特徴とする請求項16記載の剰余乗算装置。
【請求項１８】
前記出力手段は、
最初に乗数を保持し、保持している値の下位ｓビットを部分乗数として出力する乗数保持手段と、
乗数保持手段に保持されている値をｓビット下位側にシフトさせ、シフト後の値を乗数保持手段に出力して保持させるシフト手段と
を備えることを特徴とする請求項17記載の剰余乗算装置。
【請求項１９】
前記第２算出手段は、
第１保持手段に保持された中間数と乗数保持手段から出力された部分乗数とから前記部分積を算出する乗算手段と、
乗算手段に算出された部分積を保持する第２保持手段と
を備えることを特徴とする請求項18記載の剰余乗算装置。
【請求項２０】
前記累算手段は、
前記累算値を保持する第３保持手段と、
第２保持手段に保持された部分積と、第３保持手段に保持された累算値とを加算する加算器と
を備え、
前記第３保持手段は加算結果を新たな累算値として保持すること
を特徴とする請求項19記載の剰余乗算装置。
【請求項２１】
前記補正手段は、
ｐの整数倍の値をもつ補正値を保持する補正値保持手段と、
前記第３保持手段に保持された累算値の有効ビット数が所定のビット数以上になったとき、補正値保持手段に保持された補正値を、部分積と累算値の加算と同時に前記加算器に加減算させる補正制御手段と
を備えることを特徴とする請求項20記載の剰余乗算装置。
【請求項２２】
前記制御部は、第１保持手段及び乗数保持手段を第１から第２ステージへのパイプラインラッチとし、第２保持手段を第２から第３ステージへのパイプラインラッチとしてパイプライン処理を制御すること
を特徴とする請求項21記載の剰余乗算装置。
【請求項２３】
前記テーブル手段は、
ｍビットにより表現される各値に対応するアドレスが入力され、そのアドレスが指す記憶領域に当該アドレスに対応するｍビットの値の２k倍に対する法ｐによる剰余を予め記憶するメモリ素子を有すること
を特徴とする請求項17記載の剰余乗算装置。
【請求項２４】
前記mビットは下位m1ビットと上位m2ビット（m＝m1+m2）とに分割され、
前記mビットにより表現される各値は、m1ビットにより表現される値とm2ビットにより表現される値との組み合わせに対応し、
前記テーブル手段は、
m1ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶する第１部分テーブル手段と、
m2ビットにより表現される各値について、その値の２k+m1倍に対する法ｐによる剰余を予め記憶する第２部分テーブル手段と
を備え、
前記加算手段は、第１、第２部分テーブルからの読み出されたそれぞれの剰余と、前記下位データとを加算すること
を特徴とする請求項17記載の剰余乗算装置。
【請求項２５】
前記mビットは下位側からt(3≦t≦m)個の部分ビットm1、…、mtに分割され、
前記mビットにより表現される各値は、各mi（ｉは１からｔまで整数）ビットにより表現される値（ｔ個）を組み合わせたものに対応し、
前記テーブル手段は、
部分ビットmiビットにより表現される各値について、その値の２k+x倍（ここでｘ=m1+…＋m(i-1)）に対する法ｐによる剰余を予め記憶するｔ個の部分テーブル手段Ｔiを備え、
前記加算手段は、ｔ個の部分テーブル手段Tiからの読み出されたｔ個の剰余と、前記下位データとを加算すること
を特徴とする請求項17記載の剰余乗算装置。
【請求項２６】
前記第２算出手段は、
出力手段から出力されたｓビットの部分乗数の全ビットが１であるか否かを判定する判定手段と、
第１算出手段により算出された前記中間数を２のｓ乗倍した値と、当該被乗数の負の値とを生成する第１生成手段と、
部分乗数の各ビットについて、部分乗数におけるビット重みと前記中間数との積を生成する、この積は中間数をビット重みだけ桁上げした数である第２生成手段と、
全ビットが１であると判定された場合、第１生成手段に生成された各値を加算し、全ビットが１であると判定されなかった場合、第２生成手段に生成された積のうち、部分乗数中の”１”のビットに対応するものを加算する第２加算手段と
を備えることを特徴とする請求項16記載の剰余乗算装置。
【請求項２７】
前記第２生成手段は、
第ｉ（ｉは１から（ｓ−１）の整数）のシフト手段は、第１算出手段により算出された前記中間数をｉビット左シフトにより桁上げする第１から第（ｓ−１）のシフト手段
を備え、
前記第１生成手段は、
第１算出手段により算出された前記中間数をｓビット左シフトにより桁上げする第ｓのシフト手段と、
前記中間数の１の補数を生成する補数生成手段と、
定数１を出力する定数出力手段と
を備え、
前記第２加算手段は、
全ビットが１であると判定された場合に、第ｓのシフト手段の出力と、補数生成手段に生成された１の補数と、定数１を選択し、全ビットが１であると判定されなかった場合に、部分乗数の２0の位が”１”であれば前記中間数を選択し、部分乗数の２iの位が”１”であれば、第ｉのシフト手段の桁上げ結果を選択する選択手段と、
選択手段の選択結果を加算することにより前記部分積を算出する加算器と
を備えることを特徴とする請求項26記載の剰余乗算装置。
【請求項２８】
前記ｓは３の倍数（３ｎ）ビットであり、
前記部分乗数は、３ビットずつ区切ったｎ個の３ビットデータsn,…,s1で表され、
前記第２算出手段は、
第ｊ（ｊは１からｎの整数）の判定手段は、前記３ビットデータsjが"１１１"であるか否かを判定する第１から第ｎの判定手段と、
第ｊの判定手段により"１１１"であると判定された場合に、前記中間数に”１０００”と３ビットデータsjの位２3(j-1)とを乗じた値と、被乗数の負の値に３ビットデータsjの位２3(j-1)を乗じた値とを生成する第１から第ｎの特別生成手段と、
第ｊの判定手段により"１１１"でないと判定された場合には、３ビットデータsjの各ビットについて、当該ビットの論理値と、ｓビット部分乗数における各ビットの重みと、前記中間数との積を生成する第１から第ｎの一般生成手段と、
"１１１"であると判定されたsjに対応する特別生成手段により生成された値と、"１１１"でないと判定されたsjに対応する一般生成手段により生成された積とを加算する加算手段と
を備えることを特徴とする請求項16記載の剰余乗算装置。
【請求項２９】
前記第２算出手段は、
第ｉ（ｉは１からｓの整数）のシフト手段は、前記中間数をｉビット左シフトにより桁上げする第１から第ｓのシフト手段を備え、
前記第１の一般生成手段は、第１及び第２シフト手段によるシフト結果を利用し、
前記第１を除く第ｊの一般生成手段は、第（３ｊ−３）、第（３ｊ−２）、第（３ｊ−１）のシフト手段によるシフト結果を利用し、
前記第ｊの特別生成手段は、第（３ｊ）のシフト手段によるシフト結果を利用し、
第ｊの特別生成手段と第（ｊ＋１）の一般生成手段とは、第（３ｊ）のシフト手段を共用する
ことを特徴とする請求項28記載の剰余乗算装置。
【請求項３０】
前記第ｊの特別生成手段は、
前記中間数又は第（３ｊ−３）のシフト手段によるシフト結果の１の補数を生成する補数生成手段と、
定数１を出力する定数出力手段と
を備え、
前記加算手段は、
ｓｊが”１１１”であると判定された場合に、第（３ｊ）のシフト手段の出力と、第ｊの特別生成手段中の補数生成手段により生成された１の補数と、第ｊの特別生成手段中の定数出力手段により出力された定数１とを選択し、
ｓ１が”１１１”であると判定されなかった場合に、中間数と第（３ｊ−２）、第（３ｊ−１）のシフト手段の出力とを選択し、
ｓ１を除くｓｊが”１１１”であると判定されなかった場合に、第（３ｊ−３）、第（３ｊ−２）、第（３ｊ−３）のシフト手段の出力を選択する選択手段と、
選択手段の選択結果を加算することにより前記部分積を算出する加算器と
を備えることを特徴とする請求項29記載の剰余乗算装置。
【請求項３１】
前記分割手段、読み出し手段、加算手段を利用することにより、補正手段に補正された最後の累算値の法ｐによる剰余を求める後処理手段
を備えることを特徴とする請求項16記載の剰余乗算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高速かつ小回路規模の構成により剰余乗算を行う剰余乗算装置に関する。
【０００２】
【従来の技術】
近年、通信分野における暗号化技術の発達に伴って、暗号化の際に利用される各種演算装置の需要が高まっている。
例えば、楕円暗号方式においては剰余乗算を行うための剰余乗算装置が利用される。ここで剰余乗算とは、３つの整数ａ、ｂ及びｐにおいて（ａ＊ｂ）ｍｏｄｐの演算を施すことである。ここにおいてａは被乗数、ｂは乗数、ｐは法という。
【０００３】
図１７は、従来の剰余乗算装置の構成を示す。
なお、同図の剰余乗算装置１においてａ、ｂ、ｐは、説明を簡単にするため４ビットで表わされるような小さい値を用いるものとする。
剰余乗算装置１は、積算出部２、剰余算出部３、制御部４から構成される。
積算出部２は、被乗数レジスタ５（４ビット）、加算器６（４ビット）、積レジスタ７（９ビット）から構成され、制御部４の制御によって被乗数ａと乗数ｂとの積ａ＊ｂを算出する。
【０００４】
積算出部２に対する制御部４の処理手順を以下に示す。
ステップ１：初期設定として、被乗数レジスタ５に被乗数ａを保持させ、積レジスタ７（８ビット）の下位４ビットに乗数ｂを保持させ、積レジスタ７の上位５ビットに０を保持させる。
ステップ２：積レジスタ７の最下位ビットが０であるか１であるかを判定し、１と判定した場合には、加算器６において積レジスタ７の上位５ビットのうち最上位ビットを除く４ビットに保持される値と被乗数レジスタ７に保持される被乗数ａとを加算させ、加算値を積レジスタ７の上位４ビットに保持させる。
【０００５】
ステップ３：積レジスタ７を右１ビットシフトさせる。
ステップ４：ステップ２〜３の処理を４回繰り返す。
以上のようにしてステップ２〜３のループ処理を４回繰り返すと積レジスタ７には積ａ＊ｂが保持されることになる。
剰余算出部３は、法レジスタ８（４ビット）、加算器９（５ビット）、剰余レジスタ１０（１３ビット）から構成され、制御部４の制御によって手書きの筆算と同等な要領により積ａ＊ｂの法ｐによる剰余（ａ＊ｂ）ｍｏｄｐの算出を行う。なお、剰余算出部３により算出される剰余は符号付きの５ビット値である。
【０００６】
剰余算出部３に対する制御部４の処理手順を以下に示す。
ステップ５：初期設定として法レジスタ８に法ｐを保持させ、剰余レジスタ１０の下位８ビットに積レジスタ７に保持される積ａ＊ｂを保持させ、上位５ビットに０を保持させる。
ステップ６：剰余レジスタ１０に左１ビットシフトさせる。
【０００７】
ステップ７：加算器９において剰余レジスタ１０の上位５ビットに保持される値から法レジスタ８に保持される法ｐを減算させ、剰余レジスタ１０の上位５ビットに保持させる。
ステップ８：剰余レジスタ１０の上位５ビットの正負を最上位ビットの値から判定し、負（最上位ビットが１）と判定した場合は、加算器９において剰余レジスタ１０の上位５ビットと法レジスタ８の法ｐとを加算させることによって剰余レジスタ１０の値を元に戻す（つまり、ステップ７において減算される前の値に戻す）。
【０００８】
ステップ９：ステップ６〜８の処理を８回繰り返す。
以上のようにしてステップ６〜８のループ処理を８回繰り返すと、剰余レジスタ１０の上位５ビットに剰余（ａ＊ｂ）ｍｏｄｐが保持されることになる。
このように剰余乗算装置１は、積算出部２においては、被乗数ａと乗数ｂの各ビットとの部分積を、ｂの下位側から被乗数ａに対応させて算出し、算出される部分積を順次に累算することによって積ａ＊ｂを算出する。そして剰余算出部３においては、積算出部２において算出された積ａ＊ｂをシフトさせて法ｐの桁を積ａ＊ｂの上位桁から下位桁へと桁を合わせつつａ＊ｂから法ｐを減算することにより剰余（ａ＊ｂ）ｍｏｄｐを算出する。
【０００９】
【発明が解決しようとする課題】
上記従来技術における剰余乗算装置１においては、ａ、ｂ、ｐが４ビットという小さな値であるので、加算器６及び加算器９は４ビットの加算が行えればよく、またループ処理の回数も積算出部２においては４回、剰余算出部３においては８回と少ない。それに対して実際の楕円暗号に用いられるａ、ｂ、ｐは例えば１６０ビットとかなり大きな値である。よって従来の剰余乗算装置１を１６０ビットのａ、ｂ、ｐを用いた演算に対応させた場合、加算器６及び加算器９は１６０ビットの加算を行う必要があり、回路規模が大きくなるという問題があった。またループ処理の回数は、積算出部２においては１６０回、剰余算出部３においては３２０回繰り返されることとなり、演算時間がかかるという問題があった。
【００１０】
このようにして従来技術の剰余乗算装置１をあらゆる値を用いた演算に対応させるとすると、値のビット数が大きくなればなるほど、加算器で行われる加算のビット数が大きくなるので加算器の回路規模が大きくなり、ループ処理の回数が増えるので演算時間が長くなるという問題があった。
上記剰余乗算装置１の演算時間の問題を解消する他の従来技術として「United States Patent  5,144,574  Modular multiplication method and the system for processing data」に記載の剰余乗算方法がある。
【００１１】
この剰余乗算方法は、乗数ｂの上位側から２ビットずつ順次に被乗数ａに対応させて、被乗数ａと乗数ｂの２ビットずつとの部分積を算出し、算出される度にその部分積から法ｐの整数倍を減算することによって部分積の法ｐによる部分剰余を算出し、その部分剰余を累算することによって（ａ＊ｂ）ｍｏｄｐを算出する方法である。
【００１２】
このような剰余乗算方法を用いた装置においては、剰余乗算装置１が乗数ｂの１ビットずつを被乗数ａに対応させて部分積を算出していたのに対して、被乗数ａと乗数ｂの２ビットずつとの部分積を算出するので、部分積の算出にかかるループ処理の回数が少なくなり演算時間が短縮される。
このように剰余乗算方法は、主に、被乗数ａと乗数ｂの２ビットずつとを対応させた部分積の算出によって演算時間を短縮しようとするものである。ただしこの剰余乗算方法においては、部分積を算出する際に被乗数ａに対応させる乗数ｂのビット数はたかだか２ビットと少なく、ａ、ｂ、ｐが大きな値である場合には、さほど演算時間の短縮の効果は得られない。
【００１３】
上記問題に鑑みて本発明は、回路規模を抑えながら高速に演算を行う剰余乗算装置を提供することを目的とする。
【００１４】
【課題を解決するための手段】
上記問題を解決するため本発明の剰余乗算装置は、被乗数ａと乗数ｂ（ｂはｋｂビットのデータ）との積に対して、法ｐ（ｐはｋビットデータ）による剰余と合同な値を次式の累算値として算出する剰余乗算装置であって、
累算値  ＝  Σ   C(i)*b[s*i+s-1:s*i]
（ここでΣはi=０〜[[kｂ/s]]までの累算を示す。 [[kｂ/s]]は商kｂ/sの整数部分であり、iは０から[[k/s]]までの整数であり、C(i)は漸化式で表わされi=0のときC(i)=a、i>=1のときC(i)≡(C(i-1)*2s) mod ｐであり（≡は両辺の値が法ｐにおいて合同であることを示す））
b[s*i+s-1:s*i]は、ｋビットの乗数ｂのうち2s*i+s-1の位から2s*iの位までのｓビットの部分乗数であり、前記剰余乗算装置は、ｍ(ｍはｓ以上の整数)ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶するテーブル手段と、初回（i=0）では被乗数ａを中間数C(0)として出力し、
２回目以降（i>0）では、前回出力された中間数C(i-1)をｓビット桁上げし、桁上げ後の中間数の下位ｋビットを除く上位のｍビットについての前記剰余をテーブル手段から読み出し、読み出した剰余と下位ｋビットとを加算することにより新たな中間数(i)を算出する中間数算出手段とを備え、算出された各中間数C(i)と、それに対応する部分乗数b[s*i+s-1:s*i]との部分積C(i)*b[s*i+s-1:s*i]を順次累算することによって前記累算値を算出するよう構成される。
【００１５】
また前記中間数算出手段は、中間数を保持する第１保持手段と、部分乗数b[s*i+s-1:s*i]に対応して、第１保持手段に保持された中間数をｓビット桁上げする桁上げ手段と、桁上げ後の中間数を、桁上げ後の中間数における下位ｋビットよりも上位のｍビットの部分である上位データと下位ｋビットの部分である下位データとに分割する分割手段と、分割手段による上位データに対する法ｐによる剰余を前テーブル手段から読み出す読み出し手段と、テーブル手段から読み出された剰余と、分割手段による下位データとを加算することにより新たな中間数を得る加算手段とを備え、前記第１保持手段は、加算手段において新たな中間数が得られる度にその保持内容を新たな中間数に更新し、前記初回では被乗数を中間数として出力し、前記２回目以降では更新後の新たな中間数を出力するよう構成される。
【００１６】
また前記剰余乗算装置は、さらに、前記分割手段、読み出し手段、加算手段を利用することにより、前記累算値の法ｐによる剰余を求める後処理手段を備える。
また、前記テーブル手段は、ｍビットにより表現される各値に対応するアドレスが入力され、そのアドレスが指す記憶領域に当該アドレスに対応するｍビットの値の２k倍に対する法ｐによる剰余を予め記憶するメモリ素子を有する。
【００１７】
また前記mビットは下位m1ビットと上位m2ビット（m＝m1+m2）とに分割され、前記mビットにより表現される各値は、m1ビットにより表現される値とm2ビットにより表現される値との組み合わせに対応し、前記テーブル手段は、m1ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶する第１部分テーブル手段と、m2ビットにより表現される各値について、その値の２k+m1倍に対する法ｐによる剰余を予め記憶する第２部分テーブル手段とを備え、前記加算手段は、第１、第２部分テーブルからの読み出されたそれぞれの剰余と、前記下位データとを加算することにより新たなっ中間数を得るよう構成される。
また前記mビットは下位側からt(3≦t≦m)個の部分ビットm1、…、mtに分割され、前記mビットにより表現される各値は、各mi（ｉは１からｔまで整数）ビットにより表現される値（ｔ個）を組み合わせたものに対応し、前記テーブル手段は、部分ビットmiビットにより表現される各値について、その値の２k+x倍（ここでｘ=m1+…＋m(i-1)である）に対する法ｐによる剰余を予め記憶するｔ個の部分テーブル手段Ｔiを備え、前記加算手段は、ｔ個の部分テーブル手段Tiからの読み出されたｔ個の剰余と、前記下位データとを加算することにより新たな中間数を得るよう構成される。
【００１８】
また前記剰余乗算装置は、さらに累算手段と補正手段とを備え、前記累算手段は、初期値として０を保持する第３レジスタと、部分積C(i)*b[s*i+s-1:s*i]と第３レジスタに保持された累算値とを加算し、加算結果を新たな累算値として第３レジスタに出力して保持させる加算器とを備え、前記補正手段は、ｐの整数倍の値をもつ補正値を保持する補正値保持手段と、前記第３レジスタに保持された累算値が所定の値以上であれば、補正値保持手段に保持された補正値を、前記加算器に減算させる補正制御手段とを備える。
【００１９】
また前記第３レジスタは符号ビットを有し、前記補正制御手段は、第３レジスタの累算値が正であれば、前記加算器に対して累算値と部分積との加算と同時に前記補正値を減算させ、前記補正値は、ｐの整数倍であってその絶対値が前記部分積の最大値(t+1)(2 s -1)p以下の値であることを特徴とする。
また前記法ｐはｐ＝2k−αの関係を満たし、各部分テーブル手段Ｔiは、前記剰余をk3ビットのデータとして記憶する、ここで、k3はt*2m*αのビット数であり、前記αは、k3がｋより小さくなるように定められた定数であることを特徴とする。
【００２０】
また各部分テーブル手段Ｔiは、miビットにより表現される０から(2mi-1)までの値に対応する2mi個のエントリを有し、ｊ(jは０から2miまで)番目のエントリは、j*2m1+…+m(i-1) *αを格納していることを特徴とする。
本発明の剰余乗算装置は、被乗数と乗数との積に対する法ｐ（ｐはｋビットデータ）による剰余と合同な数を算出する剰余乗算装置であって、乗数をｓ（ｓは２以上の整数）ビットずつに分けて得られるｓビットの部分乗数を下位側から順に出力する出力手段と、各部分乗数の位に応じて、被乗数を桁上げし、桁上げ後の被乗数に対して、法ｐによる剰余と合同な数（以下中間数と呼ぶ）を算出する第１算出手段と、出力手段により出力された部分乗数と、当該部分乗数に対応して第１算出手段により算出された前記中間数との積を部分積として算出する第２算出手段と、第２算出手段に算出された部分積を累算する累算手段と、累算手段に累算された累算値にｐの整数倍の値を加減算することにより、累算値を所定のビット数を越えないように補正する補正手段と、出力手段により全ての部分乗数が出力されるまで、第１算出手段による中間数の算出と、第２算出手段による部分積の算出と、累算手段による累算と、補正手段による補正とを繰り返し行わせる制御手段とを備え、前記第１算出手段は、ｍ(ｍはｓ以上の整数)ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶し、制御手段による繰り返しのうち初回では被乗数を中間数として出力し、２回目以降では、前回出力された中間数をｓビット桁上げし、桁上げ後の中間数の下位ｋビットより上位のｍビットについてテーブル手段を読み出し、読み出した数と下位ｋビットとを加算することにより新たな中間数を算出するよう構成される。
【００２１】
また前記制御手段は、第１〜第３ステージを含むパイプライン処理を制御する、第１ステージでは出力手段に部分乗数を出力させるとともに第１算出手段に中間数を出力させ、第２ステージでは第２算出手段に部分積を算出させ、第３ステージでは累算手段に累算させるともに補正手段に補正させるよう構成される。
また前記出力手段は、最初に乗数を保持し、保持している値の下位ｓビットを部分乗数として出力する乗数保持手段と、乗数保持手段に保持されている値をｓビット下位側にシフトさせ、シフト後の値を乗数保持手段に出力して保持させるシフト手段とを備える。
【００２２】
また前記第２生成手段は、第ｉ（ｉは１から（ｓ−１）の整数）のシフト手段は、第１算出手段により算出された前記中間数をｉビット左シフトにより桁上げする第１から第（ｓ−１）のシフト手段を備え、前記第１生成手段は、第１算出手段により算出された前記中間数をｓビット左シフトにより桁上げする第ｓのシフト手段と、前記中間数の１の補数を生成する補数生成手段と、定数１を出力する定数出力手段とを備え、前記第２加算手段は、全ビットが１であると判定された場合に、第ｓのシフト手段の出力と、補数生成手段に生成された１の補数と、定数１を選択し、全ビットが１であると判定されなかった場合に、部分乗数の２0の位が”１”であれば前記中間数を選択し、部分乗数の２iの位が”１”であれば、第ｉのシフト手段の桁上げ結果を選択する選択手段と、選択手段の選択結果を加算することにより前記部分積を算出する加算器とを備える。
【００２３】
【発明の実施の形態】
＜第１実施形態＞
以下に本実施形態における剰余乗算装置ついて図面を用いて説明する。
本実施形態における剰余乗算装置は、楕円曲線暗号の演算等に用いられる装置で、被乗数Ａ（１６０ビット）と乗数Ｂ（１６０ビット）とが入力されると、（式1）に示す積Ａ＊Ｂの法Ｐ（１６０ビットの素数）による剰余Ｒ（＝Ａ＊ＢｍｏｄＰ）又は剰余Ｒと剰余体上において同値の値を算出する。ここにおいて法Ｐは、αを５４ビット以下の値とするときＰ＝２160−αを満たす値である。
【００２４】
本剰余乗算装置は、（式１）を変形させた（式２）に基づいて構成されている。なお、念のため（式１）から（式２）への変形過程の詳細を発明の実施の形態の末尾に示す。
【００２５】
【数３】
0004293665.tif 000002
【００２６】
【数４】
0004293665.tif 000003
【００２７】
＜演算式の説明＞
（式２）においてＲ１は、Ｒと法Ｐの剰余体において同値の値である。ここでＲとＲ１とが法Ｐの剰余体において同値であるとは、Ｒ１とＲとの差がＰの整数倍であるということを示す。
Ｒ１は、ｉ＝１からｋ／ｓまでの間、Ｃ（ｉ）＊ｂ（ｉ）を累算することによって算出される。ここでｋは乗数Ｂのビット数である。ｓは、乗数Ｂを数ビットずつの部分乗数に分割したときの各部分乗数のビット数である。つまりｋ／ｓは、部分乗数の個数と同じ値である。ここにおいてｋとｓとは、ｋがｓで割り切れる関係になるように定められる。
【００２８】
ｂ（ｉ）＝ｂ[ｓ＊ｉ−１：ｓ＊ｉ−ｓ）]は、乗数Ｂを下位からｓビットずつに分割した部分乗数を示す。ｉ＝１のときｂ（１）＝ｂ［ｓ−１：０］、ｉ＝２のときｂ（２）＝ｂ［２ｓ−１：ｓ］、ｉ＝３のときｂ（３）＝［３ｓ−１：２ｓ］、．．．となる。ここでｋビットの乗数Ｂを２進数表記した場合、ｂｋ−１ｂｋ−２．．．ｂ２ｂ１ｂ０と表わすものとする。またｂ［ｘ：ｙ］は、乗数Ｂの下位からｘ＋１ビット目からｙ＋１ビット目（ただしｘ＞ｙ）までのビット列を指すものとする。よって例えばｂ［１５：８］は、乗数Ｂの下位１６ビット目から９ビット目までの部分乗数を指し、２進数表記によりｂ１５ｂ１４ｂ１３ｂ１２ｂ１１ｂ１０ｂ９ｂ８と表わされる。
【００２９】
Ｃ（ｉ）は、ｉ＝１のときＣ（１）＝Ａ（Ａは被乗数）、２＜＝ｉ＜＝ｋ／ｓのときＣ（ｉ）≡Ｃ（ｉ−１）＊２sｍｏｄＰという漸化式で表わされる。つまりＣ（ｉ）は、Ｃ（１）＝Ａ（被乗数）、Ｃ（２）≡Ａ＊２sｍｏｄＰ、Ｃ（３）≡（Ａ＊２sｍｏｄＰ）＊２sｍｏｄＰ、...というように漸化的に変化する。この漸化式において２sは、ｓビットの部分乗数ｂ（ｉ）の桁上げに相当する。Ｃ（ｉ）は、１つ前の値であるＣ（ｉ−１）をｓビット桁上げした値の法Ｐによる剰余である。以下、Ｃ（ｉ）を以後中間数と呼ぶこととする。
【００３０】
このように（式２）においてＲ１は、ｉ＝１〜ｋ／ｓの間、被乗数Ａについて、ｓビット桁上げした値の法Ｐによる剰余を中間数Ｃ（ｉ）として漸化的に算出し、また乗数Ｂを下位からｓビットずつの部分乗数ｂ（ｉ）に分割し、それらの部分積Ｃ（ｉ）＊ｂ（ｉ）を求めて累算することを繰り返しｋ／ｓ回行うことによって求められる。以下、Ｒ１を算出するために演算をｋ／ｓ回繰り返すことを繰り返し処理と呼ぶ。
＜剰余乗算装置の構成＞
図１は、本実施形態における剰余乗算装置１００の概略構成を示すブロック図である。
【００３１】
同図において剰余乗算装置１００は、乗数分割部１１、剰余算出部１２、部分積算出部１３、累算部１４、補正部１５、制御部１６から構成される。この剰余乗算装置１００は、ｋ＝１６０、ｓ＝８としたときの（式２）に基づいて構成されている。
乗数分割部１１は、８ビットずつの部分乗数ｂ（ｉ）＝ｂ［８ｉ−１：８ｉ−８］（ｉ＝１，．．．，１９，２０）を乗数Ｂの下位側から順次出力する。
【００３２】
剰余算出部１２は、中間数Ｃ（ｉ）（ｉ＝１，...１９，２０）を漸化的に算出する。つまり剰余算出部１２は、初回（ｉ＝１）は被乗数Ａを中間数Ｃ（１）として出力する。２回目以降（ｉ＝２，３，．．．，２０）は前回の中間数Ｃ（ｉ−１）を８ビット桁上げして、その桁上げ値Ｃ（ｉ−１）＊２8の法Ｐによる剰余を中間数Ｃ（ｉ）（ｉ＝２，３，．．．，２０）として算出する。より具体的には、剰余算出部１２は、初回はＡ、２回目はＡ＊２8ｍｏｄＰ、３回目は（Ａ＊２8ｍｏｄＰ）＊２8ｍｏｄＰ、４回目は（（Ａ＊２8ｍｏｄＰ）＊２8ｍｏｄＰ）＊２8ｍｏｄＰ、．．．を中間数Ｃ（ｉ）として算出する。ここで剰余算出部１２が算出するＣ（ｉ）は、桁上げ値Ｃ（ｉ−１）＊２8と合同な値であって、Ｐよりも大きい値である場合もある。
【００３３】
剰余の算出が高速に行われるようにするため剰余算出部１２は、ＲＯＭテーブル３０８、ＲＯＭテーブル３０９を有する。これらのＲＯＭは、後に詳しく説明するが、桁上げ値Ｃ（ｉ−１）＊２8から下位１６０ビットを除いた部分、つまり桁上げによって１６０ビットを越えた部分に対応する法Ｐによる剰余を予め記憶する。剰余算出部１２は、桁上げ値Ｃ（ｉ−１）＊２8の１６０ビットを越える部分について、これらのＲＯＭを参照し、ＲＯＭより得られる１６０ビットを越える部分に対応する剰余と、桁上げ値Ｃ（ｉ−１）＊２8の下位１６０ビットの部分とを加算することにより中間数Ｃ（ｉ）を算出する。
【００３４】
部分積算出部１３は、剰余算出部１２より出力される中間数Ｃ（ｉ）と乗数分割部１１より出力される部分乗数ｂ（ｉ）との部分積Ｃ（ｉ）＊ｂ（ｉ）を出力する。
累算部１４は、部分積算出部１３より出力される部分積Ｃ（ｉ）＊ｂ（ｉ）を累算する。
【００３５】
補正部１５は、累算部１４による累算結果に応じて累算値にＰの整数倍の値を加減算することによって累算値を補正し、それによって累算部１４における累算値の桁あふれを防ぐ。
制御部１６は、剰余算出部１２、部分積算出部１３、累算部１４、補正部１５においてｉ＝１〜２０の２０回行われる演算の繰り返し処理を制御する。また制御部１６は、剰余算出部１２による中間数の算出と乗数分割部１１による部分乗数の算出とを第１段階、部分積算出部１３による部分積の算出を第２段階、累算部１４による累算値の算出と補正部１５による累算値の補正とを第３段階としてパイプライン制御を行う。さらに制御部１６は、２０回繰り返し動作させた後、累算部１４における最終的な累算値がＰより大きい場合には、その累算値を剰余算出部１２に入力して累算値のＰによる剰余を算出させる。
【００３６】
図２は、剰余算出部１２のより詳細な構成図を示す。
同図において剰余算出部１２は、セレクタ３０１、レジスタＡ３０２、シフタ３０３、セレクタ３０４、剰余演算部３１１から構成される。
セレクタ３０１は、制御部１６の制御により、まず初期設定（ｉ＝１）として外部より入力される被乗数ＡをレジスタＡ３０２に出力し、初期設定後（２＜＝ｉ＜＝２０）は剰余演算部３１１より入力される中間数Ｃ（ｉ）をレジスタＡ３０２に出力するセレクタである。
【００３７】
レジスタＡ３０２は、１６１ビットのレジスタであり、初期設定（ｉ＝１）として外部よりセレクタ３０１を介して入力される被乗数Ａ（＝Ｃ（１））を保持し、初期設定後（２＜＝ｉ＜＝２０）は加算器３１０からセレクタ３０１を介して入力される中間数Ｃ（ｉ）を保持する。レジスタＡ３０２は、出力側が部分積算出部１３とシフタ３０３とに接続されており、制御部１６の指示に応じて保持している中間数を新たに入力される中間数に更新し、部分積算出部１３とシフタ３０３とに出力する。
【００３８】
シフタ３０３は、入力を８ビット左シフトする１６９ビット幅のシフタであり、レジスタＡ３０２より入力される１６１ビットの中間数Ｃ（ｉ−１）を８ビット左シフトして１６９ビットの桁上げ値Ｃ（ｉ−１）＊２8を出力する。このようにシフタ３０３は、８ビットの左シフトを行うことによって中間数Ｃ（ｉ−１）に対して８ビットの桁上げを行う。
【００３９】
セレクタ３０４は、繰り返し処理の間、シフタ３０３より入力される桁上げ値Ｃ（ｉ−１）＊２8を剰余演算部３１１に出力し、繰り返し処理の後、累算部１４より入力される累算値を剰余演算部３１１に出力する。
剰余演算部３１１は、ＲＯＭテーブル３０８、ＲＯＭテーブル３０９、加算器３１０から構成され、シフタ３０３よりセレクタ３０４を介して入力される桁上げ値Ｃ（ｉ−１）＊２8又は累算部１４より入力される累算値の法Ｐによる剰余又は合同な値を出力する。この剰余または合同な値は１６１ビットである。
【００４０】
また剰余演算部３１１は、セレクタ３０４から入力される１６９ビットの値の下位１６０ビットを加算器３１０に入力するバス３０５と、１６１〜１６５ビット目をＲＯＭテーブル３０８に入力するバス３０６と、１６６〜１６９ビット目をＲＯＭテーブル３０９に入力するバス３０７とを備える。これらのバスは、桁上げ値Ｃ（ｉ−１）＊２8または累算値を下位側から１６０ビットの部分（以下下位部分と呼ぶ）と５ビットの部分（以下５ビット部分と呼ぶ）と４ビットの部分（以下４ビット部分と呼ぶ）とに分割してそれぞれ加算器３１０とＲＯＭテーブル３０８とＲＯＭテーブル３０９とに入力する。
【００４１】
図３（ａ）（ｂ）は、ＲＯＭテーブル３０９及びＲＯＭテーブル３０８の記憶内容を示す。
同図（ｂ）は、ＲＯＭテーブル３０８の記憶内容を示す。ＲＯＭテーブル３０８は、５ビットで表現される値（０００００）2〜（１１１１１）2を入力値とし、それら各値を２160倍した値に対する法Ｐによる剰余を出力値として対応付けて記憶する。同図（ｂ）においてαは、Ｐ＝２160−αの関係を満たすことからα＝２160ｍｏｄＰである。よって同図（ｂ）の出力値０、１＊α、２＊α、...３１＊αは、入力値（５ビット部分）を２160倍した値の法Ｐによる剰余である。ここでαは５４ビット以下の値で入力値は５ビットであるのでＲＯＭテーブル３０８の出力は最大でも５９ビットである。ＲＯＭテーブル３０８は、制御部１６よりｒｅａｄ信号が入力されたときバス３０６より入力される５ビット部分に対応する剰余を読み出して出力する。
【００４２】
同図（ａ）は、ＲＯＭテーブル３０９の記憶内容を示す。ＲＯＭテーブル３０９は、４ビットで表現される値（００００）2〜（１１１１）2を入力値とし、それら各値を２165倍した値に対する法Ｐによる剰余を出力値として対応付けて記憶する。ここでα＝２160ｍｏｄＰであるので、どう図（ａ）の出力値０、▲１▼＊３２＊α、２＊３２＊α、...１５＊３２＊αは入力値（４ビット）を２165倍した値の法Ｐによる剰余である。αは５４ビット以下の値で、入力値は４ビット、３２は５ビットであるのでＲＯＭテーブル３０９の出力は最大でも６３ビットである。ＲＯＭテーブル３０９は、制御部１６よりｒｅａｄ信号が入力されたときバス３０７より入力される４ビット部分に対応する剰余を読み出して出力する。
【００４３】
このように剰余演算部３１１においては桁上げによって１６０ビットを越えた部分についてＲＯＭテーブル３０８、ＲＯＭテーブル３０９を用いて剰余を求めるので、従来のように減算によって剰余を求める構成よりも高速になる。また、ＲＯＭテーブル３０８、ＲＯＭテーブル３０９の２つのＲＯＭに分けたことにより入力値の個数がＲＯＭテーブル３０８は２5個、ＲＯＭテーブル３０９は２4個と少なくなる。これによりＲＯＭテーブル３０８、ＲＯＭテーブル３０９は、５ビット部分、４ビット部分それぞれに対応する入力値の検索がより速くなり、剰余の算出を高速にしている。
【００４４】
加算器３１０は、１６０ビットの下位部分とＲＯＭテーブル３０８より出力される５ビット部分の剰余（５９ビット）とＲＯＭテーブル３０９より出力される４ビット部分の剰余（６３ビット）とを加えることによってＣ（ｉ−１）＊２8ｍｏｄＰ又は合同な値を出力する。
と法Ｐの剰余体上同値の値を出力する。加算器３１０が出力する値は、１６１ビットである。
【００４５】
図４は、乗数分割部１１のより詳細な構成を示す。
同図において乗数分割部１１は、シフタ５０３、セレクタ５０１、レジスタＢ５０２から構成される。
セレクタ５０１は、制御部１６の制御により、初期設定（ｉ＝１）として、外部より入力される乗数ＢをレジスタＢ５０２へ出力し、初期設定後（２＜＝ｉ）は、シフタ５０３より入力される値をレジスタＢ５０２へ出力する。
【００４６】
レジスタＢ５０２は、１６０ビットのレジスタであり、初期設定として外部よりセレクタ５０１を介して入力される乗数Ｂを保持し、初期設定後は、シフタ５０３よりセレクタ５０１を介して入力される値を保持する。レジスタＢ５０２は、出力側がシフタ５０３に接続されており、また下位８ビットの部分が部分積算出部１３に接続されている。乗数分割部１１は、制御部１６の制御により保持している値を、シフタ５０３よりセレクタ５０１を介して新たに入力される値に更新する。レジスタＢ５０２に保持されている値は、シフタ５０３に出力されるとともに下位８ビットが部分積算出部１３へ出力される。
【００４７】
シフタ５０３は、レジスタＢ５０２より入力される値を８ビット右シフトして出力する１６０ビットのシフタである。
このような構成によって乗数分割部１１は、乗数Ｂの下位から８ビットずつの部分乗数ｂ（ｉ）＝ｂ［８ｉ−１：８ｉ−８］（ｉ＝１，．．．１９，２０）を順次に部分積算出部１３に出力する。
【００４８】
図５は、部分積算出部１３のより詳細な構成を示す。
同図において部分積算出部１３は、シフタ部５１２、セレクタ部５１３、加算器５２２、加算器５２３、レジスタＣａ５２４、レジスタＣｂ５２５から構成される。
部分積算出部１３における演算を式によって表わすと（式３）のようになる。
【００４９】
【数５】
0004293665.tif 000004
【００５０】
なお同式においては便宜上、乗数分割部１１より入力される部分乗数ｂ（ｉ）の２進表記をｂｉ７ｂｉ６ｂｉ５ｂｉ４ｂｉ３ｂｉ２ｂｉ１ｂｉ０としている。
同式に示すように、部分積算出部１３は、まず剰余算出部１２より入力される中間数Ｃ（ｉ）に対して部分乗数ｂ（ｉ）の各ビットに応じた０〜７ビットの桁上げを行い（同式▲１▼）、次に桁上げされた各値に部分乗数ｂ（ｉ）の各ビットを乗じ（同式▲２▼）、最後にそれらを加算する（同式▲３▼、▲４▼）
シフタ部５１２は、バス５０４と、入力される値に対してそれぞれ１〜７ビット左シフトを行うシフタ５０５〜５１１とを備え、同式▲１▼に相当する演算を行う。
【００５１】
すなわちシフタ部５１２は、剰余算出部１２より入力される中間数Ｃ（ｉ）を部分乗数ｂ（ｉ）の各ビットの重みに応じた桁上げを行ってセレクタ部５１３に出力する。シフタ５０５〜５１１は、入力されるＣ（ｉ）に対してそれぞれ１〜７ビットの左シフトを行うシフタである。つまりシフタ５０５〜５１１は、入力されるＣ（ｉ）に対して、それぞれＣ（ｉ）＊２1〜Ｃ（ｉ）＊２7を出力する。バス５０４は、中間数Ｃ（ｉ）をそのままセレクタ部５１３に出力する。
【００５２】
セレクタ部５１３は、セレクタ５１４〜５２１を備え、同式▲２▼に相当する演算を行う。セレクタ５１４〜５２１は、それぞれシフタ部５１２よりＣ（ｉ）＊２0〜Ｃ（ｉ）＊２7が入力され、乗数分割部１１よりｂ（ｉ）の各ビットｂｉ０〜ｂｉ７が入力される。セレクタ５１４〜５２１は、それぞれに入力される部分乗数ｂ（ｉ）の各ビットｂｉ０〜ｂｉ７の値に応じて、それぞれに入力されるＣ（ｉ）＊２0〜Ｃ（ｉ）＊２7か０かのどちらかを選択して出力する。すなわちセレクタ５１４〜５２１は、入力されるｂｉｎ（ｎ＝０，１，...，７）の値が１の場合はＣ（ｉ）＊２n（ｎ＝０，１，...，７）を出力し、ｂｉｎの値が０の場合は０を出力する。
【００５３】
加算器５２２は、▲３▼に相当する演算を行う加算器であり、セレクタ５１４〜５１７より入力される４つの値を加算した値（以下部分積ａという）をレジスタＣａ５２４へ出力する。
加算器５２３は、▲４▼に相当する演算を行う加算器であり、セレクタ５１８〜５２１より入力される４つの値を加算した値（以下部分積ｂという）をレジスタＣｂ５２５へ出力する。
【００５４】
レジスタＣａ５２４、レジスタＣｂ５２５は、それぞれ部分積ａ、部分積ｂを保持し、制御部１６の制御により保持している部分積ａ、部分積ｂを新しく入力された値に更新する。レジスタＣａ５２４及びレジスタＣｂ５２５の出力側は、累算部１４に接続されており、レジスタＣａ５２４及びレジスタＣｂ５２５は、保持している部分積ａ、ｂを累算部１４に出力する。
【００５５】
この部分積ａと部分積ｂとを加え合わせた値が部分積Ｃ（ｉ）＊ｂ（ｉ）に相当する。
図６は、累算部１４及び補正部１５の詳細な構成を示す。
累算部１４は、加算器６０１及びレジスタＳ６０２から構成される。
レジスタＳ６０２は、累算値を保持する１７０ビットのレジスタであり、制御部１６の制御により、保持している累算値を、加算器６０１から入力される新しい累算値に更新する。ここでレジスタＳ６０２の最上位ビットは、累算値の正負を表わす符合ビットとなる。
【００５６】
加算器６０１は、レジスタＳ６０２に保持される累算値とレジスタＣａ５２４及びレジスタＣｂ５２５に保持される部分積ａと部分積ｂと補正部１５より入力される補正値とを加算してレジスタＳ６０２に出力する。
補正部１５は、レジスタＥ６０３、インバータ６０６、セレクタ６０４、セレクタ６０５から構成される。
【００５７】
レジスタＥ６０３は、部分積ａ及び部分積ｂを合わせた値の最大値となり得る値より大きく、かつ最も近い値を保持する。
インバータ６０６は、レジスタＥ６０３に保持される５１０＊Ｐの反転値（以下、¬５１０＊Ｐと表記する）を出力する。
セレクタ６０４は、制御部１６の制御に従って、０と５１０＊Ｐと¬５１０＊Ｐのうちからいずれかを補正値として選択して加算器６０１に供給する。
【００５８】
セレクタ６０５は、制御部１６の制御に従って、０または１を加算器６０１に供給する。
ここで制御部１６は、レジスタＳ６０２に保持される累算値の正負に応じてセレクタ６０４に補正値を選択させ、またセレクタ６０５に０または１を選択させて加算器６０１に供給させる。
【００５９】
詳しくは制御部１６は、レジスタＳ６０２の最上位ビットが０であれば、セレクタ６０４に¬５１０＊Ｐを選択させ、セレクタ６０５に１を選択させる。これによってレジスタＳ６０２に保持される累算値が正（最上位ビットが０）である場合には、レジスタＥ６０３からインバータ６０６、セレクタ６０４を介して¬５１０＊Ｐが、またセレクタ６０５を介して１が加算器６０１に供給される。これのおかげで加算器６０１の次の加算においては５１０＊Ｐが減算されることになり、加算器６０１及びレジスタＳ６０２における桁あふれが予防される。
【００６０】
制御部１６は、レジスタＳ６０２に保持される累算値が負（最上位ビットが１）である場合には、セレクタ６０４に０を選択させ、またセレクタ６０５に０を選択させる。
また制御部１６は、ｉ＝１〜２０の繰り返し処理が終わり、レジスタＳ６０２の保持する値が最終的な累算値に更新された場合、その累算値の最上位ビットが１か０かを判定し、１（負を示す）である場合には、セレクタ６０４に５１０＊Ｐを、セレクタ６０５に０を選択させ、加算器６０１においてレジスタＳ６０２に保持される累算値に５１０＊Ｐを加える補正を行わせる。これによって制御部１６は、最終的な累算値が正になるよう補正させる。また制御部１６は、最終的な累算値の最上位ビットが０（正を示す）場合には、セレクタ６０４に０を、セレクタ６０５に０を選択させ、累算値の補正が行われないようにする。
＜第２実施形態＞
以下に第２実施形態における剰余乗算装置について以下に図面を用いて説明する。
【００６１】
本実施形態における剰余乗算装置は、被乗数Ａ（１６０ビット）と乗数Ｂ（１６１ビット）とが入力されると、積Ａ＊Ｂの法Ｐ（１６０ビット）による剰余Ｒ（＝Ａ＊ＢｍｏｄＰ）又は剰余Ｒと剰余体上において同値の値を算出する。ここにおいて法Ｐは、αを５４ビット以下の値とするときＰ＝２160−αを満たす値である。
【００６２】
本実施形態の剰余乗算装置も、第１実施形態と同様（式２）に基づいて構成されている。ただし第１実施形態においてはｓ＝８であったのに対して第２実施形態においてはｓ＝９とする。またｋ／ｓの部分は、実際に計算するとｋ／ｓ＝１６１／９と割り切れないので、本実施形態においてはｋ／ｓの部分は１８と置き換えるものとする。
【００６３】
図７は、第２実施形態における剰余乗算装置２００の概略構成を示すブロック図である。
同図において剰余乗算装置２００は、乗数分割部８１、剰余算出部８２、部分積算出部８３、累算部８４、補正部８５、制御部８６から構成される。
同図の剰余乗算装置２００において剰余算出部８２は、１つしかＲＯＭテーブルを有していない点が剰余算出部１２と異なる。また図１１において詳細に説明するが、部分積算出部８３は部分積算出部１３に対して、その内部の加算器に入力される入力数を減らして加算器の回路規模がより小さくなるように構成されている。さらに剰余乗算装置１００において桁挙げ値Ｃ（ｉ−１）＊２8の算出は剰余算出部１２が行っていたが、剰余乗算装置２００において桁上げ値Ｃ（ｉ−１）＊２9の算出は、剰余算出部８２ではなく部分積算出部８３が行う。
【００６４】
その他、乗数分割部８１、累算部８４、補正部８５、制御部８６は、乗数Ｂが１６１ビット、ｓが９ビットと第１実施形態とビット数が異なっている点から各構成要素における入出力のビット数やレジスタ等のビット数が異なってはいるものの、その点を除けば第１実施形態と同様の構成である
乗数分割部８１は、９ビットずつの部分乗数ｂ（ｉ）＝ｂ［９ｉ−１：９ｉ−９］（ｉ＝１，...，１７，１８）を乗数Ｂの下位側から順次出力する。
【００６５】
剰余算出部８２は、中間数Ｃ（ｉ）（ｉ＝１，...１７，１８）を漸化的に算出する。つまり剰余算出部８２は、初回（ｉ＝１）は、被乗数Ａを中間数Ｃ（ｉ）として出力する。２回目以降（ｉ＝２，．．．１７，１８）は前回の中間数Ｃ（ｉ−１）の９ビット桁上げされた桁上げ値Ｃ（ｉ−１）＊２9の法Ｐによる剰余Ｃ（ｉ−１）＊２9ｍｏｄＰを中間数Ｃ（ｉ）として算出する。より具体的には、剰余算出部８２は、初回はＡ、２回目はＡ＊２9ｍｏｄＰ、３回目は（Ａ＊２9ｍｏｄＰ）＊２9ｍｏｄＰ、４回目は、（（Ａ＊２9ｍｏｄＰ）＊２9ｍｏｄＰ）＊２9ｍｏｄＰ、...を中間数Ｃ（ｉ）として算出する。ただし、剰余算出部８２は、中間数Ｃ（ｉ−１）に対する９ビットの桁上げを行わず、部分積算出部８３において算出される桁上げ値Ｃ（ｉ−１）＊２9を利用してその法Ｐによる剰余Ｃ（ｉ−１）＊２9ｍｏｄＰを算出する。
【００６６】
剰余の算出が高速に行われるようにするため剰余算出部８２は、ＲＯＭテーブル９０４を有する。ＲＯＭテーブル９０４は、桁上げ値Ｃ（ｉ−１）＊２9から下位１６０ビットを除いた部分、つまり桁上げによって１６０ビットを越えた部分に対応する法Ｐによる剰余を予め記憶する。剰余算出部８２は、桁上げ値Ｃ（ｉ−１）＊２9の１６０ビットを越える部分についてＲＯＭテーブル９０４を参照し、当該ＲＯＭにより得られる１６０ビットを越える部分に対応する剰余と、桁上げ値Ｃ（ｉ−１）＊２9の下位１６０ビットの部分とを算出することにより中間数Ｃ（ｉ）を算出する。
【００６７】
部分積算出部８３は、剰余算出部８２より出力される中間数Ｃ（ｉ）と乗数分割部８１より出力される部分乗数ｂ（ｉ）との部分積Ｃ（ｉ）＊ｂ（ｉ）を出力する。また部分積算出部８３は、剰余算出部８２より出力される中間数Ｃ（ｉ−１）の９ビットの桁上げ値を算出して剰余算出部８２に出力する。
累算部８４は、部分積算出部８３により出力される部分積Ｃ（ｉ）＊ｂ（ｉ）を累算する。
【００６８】
補正部８５は、累算部８４による累算結果に応じて累算値にＰの整数倍の値を加減算することによって累算値を補正し、それによって累算部８４における累算値の桁あふれを防ぐ。
制御部８６は、乗数分割部８１、剰余算出部８２、部分積算出部８３、累算部８４、補正部８５においてｉ＝１〜１８の１８回行われる演算の繰り返し処理を制御する。また制御部８６は、剰余算出部８２による中間数の算出と乗数分割部８１による部分乗数の算出とを第１段階、部分積算出部８３による部分積の算出を第２段階、累算部８４による累算値の算出と補正部８５による累算値の補正とを第３段階としてパイプライン制御を行う。制御部８６は、１８回の繰り返し動作の後、累算部８４における最終的な累算値がＰより大きい場合には、その累算値を剰余算出部８２に入力して累算値のＰによる剰余を算出させる。
【００６９】
図８は、剰余算出部８２のより詳細な構成を示す。
同図において剰余算出部８２は、セレクタ９０１、レジスタＡ９０６、セレクタ９０２、剰余演算部９０７から構成される。
セレクタ９０１は、制御部８６の制御により、まず初期設定（ｉ＝１）として外部より入力される被乗数ＡをレジスタＡ９０６に出力し、初期設定後（ｉ＝２，．．．１７，１８）は剰余演算部９０７より入力される中間数Ｃ（ｉ）をセレクタ９０１に出力するセレクタである。
【００７０】
レジスタＡ９０６は、１６１ビットのレジスタであり、初期設定（ｉ＝１）として外部よりセレクタ９０１を介して入力される被乗数Ａ（＝Ｃ（１））を保持し、初期設定後（ｉ＝２，．．．１７，１８）は、加算器９０５からセレクタ９０１を介して入力される中間数Ｃ（ｉ）を保持する。レジスタＡ９０６は、出力側が部分積算出部８３に接続されており、制御部８６の指示に応じて保持している中間数を新たに入力される中間数に更新し、部分積算出部８３に出力する。レジスタＡ９０６は、最終的には剰余乗算値Ｒを保持する。
【００７１】
セレクタ９０２は、繰り返し処理の間、部分積算出部８３より入力される桁上げ値Ｃ（ｉ−１）＊２9を剰余演算部９０７に出力し、繰り返し処理の後、累算部８４より入力される累算値を剰余演算部９０７に出力する。
剰余演算部９０７は、ＲＯＭテーブル９０４と加算器９０５から構成され、部分積算出部８３よりセレクタ９０２を介して入力される１７０ビットの桁上げ値Ｃ（ｉ−１）＊２9又は累算部８４より入力される１７０ビットの累算値の法Ｐによる剰余又は合同な値を出力する。この剰余または合同な値は１６１ビットである。
【００７２】
剰余演算部９０７は、セレクタ９０２から入力される１７０ビットの値の下位１６０ビットを加算器９０５に出力するバス９０８と、下位１６０ビットを除く上位１０ビット（１６１〜１７０ビット目）をＲＯＭテーブル９０４に出力するバス９０９とを備える。これらバス９０８及びバス９０９は、１７０ビットの値を下位１６０ビット（以下下位部分と呼ぶ）と上位１０ビット（以下上位部分と呼ぶ）とに分割して、下位部分と上位部分とをそれぞれ加算器９０５とＲＯＭテーブル９０４とに入力する。
【００７３】
図９は、ＲＯＭテーブル９０４の記憶内容を示す。
同図においてＲＯＭテーブル９０４は、１０ビットで表現される各値（００００００００００）2〜（１１１１１１１１１１）2を入力値とし、それら各値を２160倍した値に対する法Ｐによる剰余を出力値として対応付けて記憶する。ＲＯＭテーブル９０４は、制御部８６よりｒｅａｄ信号が入力されたときバス９０９より入力される上位部分に対応する剰余を読み出して出力する。
【００７４】
加算器９０５は、ＲＯＭテーブル９０４より出力される上位部分に対する剰余と下位部分とを加えることによって１６１ビットのＣ（ｉ−１）＊２9ｍｏｄＰ又はそれと合同な値を出力する。
このように剰余演算部９０７においては９ビットの桁上げによって１６０ビットを越えた部分についてＲＯＭテーブル９０４を用いて剰余を求め、その剰余と下位１６０ビットとを加算することによって桁上げ値Ｃ（ｉ−１）＊２の剰余又は合同な値を求める。
【００７５】
この剰余演算部９０７の内部の構成を従来技術における剰余算出部３と似た構成にした場合、剰余演算部９０７は従来技術に示したようなループ処理（ステップ６〜８）を複数回行わなければならず、剰余の算出に時間がかかる。これに対して本実施形態の剰余演算部９０７は、ＲＯＭテーブル９０４における１回の読出しと加算器９０５における１回の加算とを行うだけで剰余を算出するので従来の構成よりも高速になる。
【００７６】
図１０は、乗数分割部８１のより詳細な構成を示す。
同図において乗数分割部８１は、セレクタ８０１、レジスタＢ８０２、シフタ８０３から構成される。
セレクタ８０１は、制御部８６の制御により、初期設定（ｉ＝１）として、外部より入力される乗数ＢをレジスタＢ８０２へ出力し、初期設定後（ｉ＝２,...17,18）は、シフタ８０３より入力される値をレジスタＢ８０２へ出力する。
【００７７】
レジスタＢ８０２は、１６１ビットのレジスタであり、初期設定として外部よりセレクタ８０１を介して入力される乗数Ｂを保持し、初期設定後は、シフタ８０３よりセレクタ８０１を介して入力される値を保持する。レジスタＢ８０２は、出力側がシフタ８０３に接続されており、また下位９ビットの部分が部分積算出部８３に接続されている。レジスタＢ８０２は、制御部１６の制御により保持している値を、シフタ８０３よりセレクタ８０１を介して新たに入力される値に更新する。レジスタＢ８０２に保持されている値は、シフタ８０３に出力されるとともに下位９ビットが部分積算出部８３へ出力される。
【００７８】
シフタ８０３は、レジスタＢ８０２より入力される値を９ビット右シフトして出力する１６１ビットのシフタである。
このような構成によって剰余算出部８２は、乗数Ｂの下位から９ビットずつの部分乗数ｂ（ｉ）＝ｂ［９ｉ−１：９ｉ−９］（ｉ＝１，．．．１７，１８）を順次に部分積算出部８３に出力する。
＜部分積算出方法＞
ここで部分積算出部８３の詳細な構成を説明する前に、部分積算出部８３の構成の基礎となっている２つの積算出方法について説明する。
【００７９】
被乗数Ｘと３ビットの乗数Ｙ（＝ｙ２ｙ１ｙ０）との積は、（式４）のように展開される。
【００８０】
【数６】
0004293665.tif 000005
【００８１】
つまり（式４）において積Ｘ＊Ｙは、被乗数Ｘと乗数Ｙの各桁の重み（２2，２1，２0）と各桁の値（ｙ２，ｙ１，ｙ０）とを乗じて得られる値（Ｘ＊２2＊ｙ２，Ｘ＊２1＊ｙ１，Ｘ＊２0＊ｙ０、以下ビット積と呼ぶ）を加算することにより算出される。
具体的には例えば、Ｙ＝１０１のとき（式４）はＸ＊Ｙ＝Ｘ＊２2＊ｙ２＋Ｘ＊２0＊ｙ０であり、Ｘ＊Ｙは２つの値（以下ビット積と呼ぶ）の加算によって算出される。Ｙ＝１１０のとき（式４）はＸ＊Ｙ＝Ｘ＊２2＊ｙ２＋Ｘ＊２1＊ｙ１であり、Ｘ＊Ｙは２つのビット積の加算によって算出される。Ｙ＝１１１のとき（式４）はＸ＊Ｙ＝Ｘ＊２2＊ｙ２＋Ｘ＊２1＊ｙ１＋Ｘ＊２0＊ｙ０であり、Ｘ＊Ｙは３つのビット積の加算によって算出される。
【００８２】
このように被乗数に対して乗数の各桁の重みと各桁の値とを乗じて得られるビット積を加算することにより積を算出する方法を一般算出方法と呼ぶこととする。第１実施形態における剰余算出部１２も、この方法に基づいて構成されている。
ところで１１１＝２3−１である。よってＹ＝１１１のとき積Ｘ＊Ｙは、被乗数Ｘに１１１を乗じる代わりに２3−１を乗じることによっても算出することができる。被乗数Ｘと２3−１と積は次のように展開される。
【００８３】
【数７】
0004293665.tif 000006
【００８４】
つまり（式５）においてＹ＝１１１のとき積Ｘ＊Ｙは、被乗数Ｘに２3を乗じた値から被乗数Ｘを減算することにより算出される。
またＹ’＝１１１０００のとき、Ｙ’＝Ｙ＊２3であるから積Ｘ＊Ｙ’は被乗数Ｘに１１１０００を乗じる代わりに２6−２3を乗じることによっても算出することができる。
【００８５】
以上により乗数において２pの位（下位からp＋１ビット目）から２q（下位からq＋１ビット目）の位（ただしp＞q）が全て１であるとき、その部分における積は被乗数に２p+1を乗じた値（以下被減数ともいう）から被乗数に２q（以下減数ともいう）を乗じた値を減ずることによって算出することができる。この方法を特別算出方法と呼ぶこととする。
【００８６】
ところで加算器においてｓとｔとの減算値ｓ−ｔは、ｓとｔの反転値（１の補数）と定数１との加算に置きかえられて算出される。よって乗数において２pの位（下位からp＋１ビット目）から２q（下位からq＋１ビット目）の位（ただしp＞q）が全て１である場合、その部分について特別算出方法によって積を算出するとすれば、加算器は被乗数の２p+1倍と被乗数の２q倍の反転値（以下単に反転値ともいう）と定数１との加算を行うだけでよい。しかも定数１の加算は加算器の下位ビットのキャリーインを利用して実現することができる。つまり特別算出方法によって積を算出する場合、加算器は２つの加算とキャリーインとを行うだけでよい。
【００８７】
これに対してｎビットの乗数の全ビットが１である場合、一般算出方法によって積を算出するとすれば、加算器はｎ個のビット積の加算を行う必要がある。
以上のことから乗数中１が３以上連続して並ぶ場合、その部分については、一般算出方法によるよりも特別算出方法によって積を算出するほうが加算器における加算の数を減らすことができるので、加算器の規模の縮小と加算量の負荷軽減とを実現できる。
部分積算出部８３は、上記２つの方法に基づいて部分積Ｃ（ｉ）＊ｂ（ｉ）を算出するよう構成される。
【００８８】
部分積算出部８３は、部分乗数ｂ（ｉ）のビット列において１が連続している部分に特別算出方法を適用し、それ以外の部分については一般算出方法を適用する。より具体的には、部分積算出部８３は、９ビットの部分乗数ｂ（ｉ）が１１１１１１１１１である場合と、部分乗数ｂ（ｉ）の上位６ビット又は下位６ビットが１１１１１１である場合と、上位３ビット又は中位３ビット又は下位３ビットが１１１である場合にその部分について特別算出方法を適用し、それ以外は一般算出方法を適用する。
【００８９】
例えば、部分乗数ｂ（ｉ）が１１１１１１０１１である場合、部分積算出部８３は、上位６ビットの１１１１１１の部分に特別算出方法を適用し、下位３ビットの０１０の部分に一般算出方法を適用して積Ｃ（ｉ）＊ｂ（ｉ）する。ただしこのとき、上位６ビットの１１１１１１は、下位から３ビット桁上げされた値（２3倍した値）であるので、部分積算出部８３は、特別算出方法を適用する際には上位６ビットの部分に対して２3の桁上げを行わなければならない。
【００９０】
具体的には（式６）のように展開される。
【００９１】
【数８】
0004293665.tif 000007
【００９２】
（式６）に示すように上位６ビットの１１１１１１については特別算出方法の適用と２3の桁上げとにより同式▲１▼のように展開される。すなわち部分積算出部８３は、中間数Ｃ（ｉ）を９ビット桁上げした値と中間数Ｃ（ｉ）を３ビット桁上げした値と定数１との加算によって上位６ビットの１１１１１１の部分における積を算出する。また下位３ビットの０１１については一般算出方法の適用により同式▲２▼のように展開される。すなわち部分積算出部８３は、下位３ビットの０１１の値に応じて、中間数Ｃ（ｉ）を1ビット桁上げした値と中間数Ｃ（ｉ）との加算によって下位３ビットの０１１の部分における積を算出する。
【００９３】
図１１は、部分積算出部８３のより詳細な構成を示す。
同図において部分積算出部８３は、シフタ部５１、選択部５２、ＯＲ回路５１３、加算器Ａ７０１、加算器Ｂ７０２、レジスタＣａ８４４、レジスタＣｂ８４５から構成される。
シフタ部５１は、バス８３０とシフタ８３１〜８３９とを有する。バス８３０は、入力される１６１ビットの中間数Ｃ（ｉ）をそのまま選択部５２へ出力する。シフタ８３１〜８３９は、それぞれ入力される中間数Ｃ（ｉ）を左に１〜９ビットシフトさせることにより中間数Ｃ（ｉ）を１〜９ビット桁上げしてＣ（ｉ）＊２、Ｃ（ｉ）＊２2、Ｃ（ｉ）＊２3、Ｃ（ｉ）＊２4、Ｃ（ｉ）＊２5、Ｃ（ｉ）＊２6、Ｃ（ｉ）＊２7、Ｃ（ｉ）＊２8、Ｃ（ｉ）＊２9を生成して選択部５２に出力する。またシフタ８３９は、中間数Ｃ（ｉ）を左に９ビットシフトさせて選択部５２に出力すると同時に、その値を桁上げ値Ｃ（ｉ−１）＊２9として剰余算出部８２に出力する。
【００９４】
シフタ部５１において、バス８３０とシフタ８３１〜８３８の出力、すなわちＣ（ｉ）、Ｃ（ｉ）＊２1Ｃ、．．．、Ｃ（ｉ）＊２8は一般算出方法による算出の際のビット積の候補となる値である。シフタ８３３、８３６、８３９の出力、すなわちＣ（ｉ）＊２3、Ｃ（ｉ−１）＊２6、Ｃ（ｉ−１）＊２9は、特別算出方法による算出の際の被減数の候補となる値である。またバス８３０、シフタ８３３、８３６の出力、すなわちＣ（ｉ）、Ｃ（ｉ）＊２3、Ｃ（ｉ−１）＊２6は、特別算出方法による算出の際、減数の候補となる値である。以下これらの候補となる値を候補値と呼ぶこととする。
【００９５】
選択部５２は、シフタ部５１より０〜９ビット桁上げされた値と乗数分割部８１からの部分乗数ｂ（ｉ）とが入力されると、９ビットの部分乗数ｂ（ｉ）が１１１１１１１１１であるか否か、部分乗数ｂ（ｉ）の上位６ビット又は下位６ビットが１１１１１１であるか否か、上位３ビット又は中位３ビット又は下位３ビットが１１１であるか否かを判定する。次に選択部５２は、その判定に応じてシフタ部５１から入力される候補値のうちのいくつかを選択する。より詳しくは、選択部５２は、肯定的に判定された部分については、候補値の中からその部分に対応する被減数と減数とを選択する。選択部５２は、否定的に判定された部分については、候補値の中からその部分に対応するビット積を選択する。選択部５２は、選択された候補値のうち、被減数とビット積についてはそのまま加算器Ａ７０１又は加算器Ｂ７０２に出力する。選択部５２は、選択された候補値のうち、減数については、その値を反転させた反転値と定数１とを生成して、生成した値を加算器Ａ７０１又は加算器Ｂ７０２に出力する。
【００９６】
選択部５２は、演算値選択器８４０、８４１、８４２を備える。
図１２は、演算値選択器８４０、８４１、８４２の詳細な構成を示す。
演算値選択器８４０は、インバータ１３０１、セレクタ１３０２、１３０３、制御回路１３０４を備える。また演算値選択器８４０は、入力端子Ｓ、Ｚ、Ｉ０、Ｉ１、Ｉ２、Ｉ３、出力端子Ｆ、Ｏ０、Ｏ１を備える。
【００９７】
インバータ１３０１は、入力端子Ｉ０より候補値Ｃ（ｉ）が減数として入力されると、その減数を反転させた反転値をセレクタ１３０３に出力する。
セレクタ１３０３は、インバータ１３０１より入力端子¬Ｉ０を介して候補値Ｃ（ｉ）の反転値が、入力端子Ｚより０が、入力端子Ｉ０より候補値Ｃ（ｉ）が、入力端子Ｉ１より候補値Ｃ（ｉ）＊２1が入力されると、制御回路１３０４の入出力論理に従ってこれらの入力端子のうちから１つを選択し、選択した入力端子より入力される値を出力端子Ｏ０より出力する。
【００９８】
セレクタ１３０２は、入力端子Ｚより０が、入力端子Ｉ１より候補値Ｃ（ｉ）＊２1が、入力端子Ｉ２より候補値Ｃ（ｉ）＊２2が、入力端子Ｉ３より候補値Ｃ（ｉ）＊２3が入力されると、制御回路１３０４の入出力論理に従ってこれらの入力端子のうちから１つを選択し、選択した入力端子より入力される値を出力端子Ｏ１より出力する。
【００９９】
制御回路１３０４は、入力端子Ｓより部分乗数ｂ（ｉ）が入力されると、図１３（ｃ）に示す入出力論理に基づいてセレクタ１３０２及び１３０３に入力端子の１つを選択させて、その入力端子から入力される値を出力端子Ｏ１、Ｏ０より出力させる。また制御回路１３０４は、セレクタ１３０３に入力端子¬Ｉ０を選択させたとき、出力端子Fより１を出力する。それ以外のとき、制御回路１３０４は、出力端子Fより０を出力する。
【０１００】
図１３（ｃ）は、制御回路１３０４に入力される部分乗数ｂ（ｉ）と入出力論理を示す。
同図（ｃ）の１列目は、入力端子Ｓより入力される部分乗数ｂ（ｉ）を示す。“−”は、１か０かの任意の値を示し、“＃＃＃”は、“１１１”以外の任意の値を示す。２列目は、セレクタ１３０２に選択させる入力端子を示す。３列目は、セレクタ１３０３に選択させる入力端子を示す。４列目は、制御回路１３０４が出力端子Ｆより出力する値で、１のとき定数１を示す。
【０１０１】
例えば、制御回路１３０４は、部分乗数ｂ（ｉ）の下位６ビットすべてが１であると判定した場合は、出力端子Ｏ１より０を、出力端子Ｏ０よりＣ（ｉ）の反転値を出力させ、出力端子Ｆより定数１を出力する。下位６ビットすべてが１であると判定しなかった場合であって、下位３ビットすべてが１であると判定した場合は、制御回路１３０４は、出力端子Ｏ１よりＣ（ｉ）＊２3を出力させ、出力端子Ｏ０よりＣ（ｉ）を出力させ、出力端子Ｆより定数１を選択する。その他の場合、制御回路１３０４は、部分乗数ｂ（ｉ）の下位３ビットの値に応じて出力端子Ｏ１、Ｏ０よりＣ（ｉ）＊２2、Ｃ（ｉ）＊２1、Ｃ（ｉ）、０のうちのいずれか２つの値を出力させる。
【０１０２】
演算値選択器８４１は、インバータ１３０１、セレクタ１３０２、１３０３、制御回路１３０５を備える。また演算値選択器８４１は、入力端子Ｓ、Ｚ、Ｉ０、Ｉ１、Ｉ２、Ｉ３、出力端子Ｆ、Ｏ０、Ｏ１を備える。演算値選択器８４１は、演算値選択器８４０に対して制御回路１３０４の代わりに制御回路１３０５を備える点が異なっている。制御回路１３０５は、入力端子Ｓより部分乗数ｂ（ｉ）が入力されると、図１３（ｂ）に示す入出力論理に基づいてセレクタ１３０２及び１３０３に入力端子の１つを選択させて、その入力端子から入力される値を出力端子Ｏ１、Ｏ０より出力させる。その他の構成要素は、演算値選択器８４０と同様であるので説明を省略する。
【０１０３】
演算値選択器８４２は、インバータ１３０１、セレクタ１３０２、１３０３、制御回路１３０６を備える。また演算値選択器８４２は、入力端子Ｓ、Ｚ、Ｉ０、Ｉ１、Ｉ２、Ｉ３、出力端子Ｆ、Ｏ０、Ｏ１を備える。演算値選択器８４２は、演算値選択器８４０に対して制御回路１３０４の代わりに制御回路１３０６を備える点が異なっている。制御回路１３０６は、入力端子Ｓより部分乗数ｂ（ｉ）が入力されると、図１３（ａ）に示す入出力論理に基づいてセレクタ１３０２及び１３０３に入力端子の１つを選択させて、その入力端子から入力される値を出力端子Ｏ１、Ｏ０より出力させる。その他の構成要素は、演算値選択器８４０と同様であるので説明を省略する。
【０１０４】
ＯＲ回路５１３は、演算値選択器８４０及び８４１それぞれの出力端子Ｆの出力値の論理和をとる。図１３（ｂ）（ｃ）からわかるように、演算値選択器８４０及び８４１において、出力端子Ｆの一方の出力が定数１であるときは必ず他方の出力は０である。よってＯＲ回路５１３は、論理和をとることによって２つの値を１つにまとめ、これにより選択器５２の出力数を減らしている。
【０１０５】
加算器Ａ７０１は、演算値選択器８４２の出力端子Ｏ１、Ｏ０、Ｆの出力値と演算値選択器８４１の出力端子Ｏ１の出力値とを加算して、結果の部分積ｃをレジスタＣａ８４４に出力する。
加算器Ｂ７０２は、演算値選択器８４１の出力端子Ｏ０の出力値と演算値選択器８４０の出力端子Ｏ１、Ｏ０の出力値とＯＲ回路５１３の出力値とを加算しての出力値とを加算して、結果の部分積ｄをレジスタＣａ８４５に出力する。
【０１０６】
ここにおいて部分積ｃと部分積ｄとを加え合わせた値が部分積Ｃ（ｉ）＊ｂ（ｉ）である。
レジスタＣａ８４４レジスタＣｂ８４５は、それぞれ部分積ｃ及び部分積ｄを保持し、制御部８６の制御により保持している部分積ｃ及び部分積ｄを新しく入力される値に更新する。レジスタＣａ８４４レジスタＣｂ８４５の出力側は、累算部８４に接続されており、レジスタＣａ８４４レジスタＣｂ８４５は、保持している部分積ｃ及び部分積ｄを累算部８４に出力する。
【０１０７】
図１４は、累算部８４及び補正部８５のより詳細な構成を示す。
同図において累算部８４は、加算器７０５及びレジスタＳ７０７から構成される。
レジスタＳ７０７は、累算値を保持する１７１ビットのレジスタであり、制御部８６の制御により、保持している累算値を、セレクタ７０６から入力される新しい累算値に更新する。ここでレジスタＳ７０７の最上位ビットは、累算値の正負を表わす符号ビットとなる。
【０１０８】
加算器７０５は、レジスタＳ７０７に保持される累算値とレジスタＣａ８４４及びレジスタＣｂ８４５に保持される部分積ｃと部分積ｄと補正部８５より入力される補正値とを加算してレジスタＳ７０７に出力する。
補正部８５は、レジスタＥ７０３、インバータ７０８、セレクタ７０４、セレクタ７０６から構成される。
【０１０９】
レジスタＥ７０３は、部分積ｃ及び部分積ｄを合わせた値の最大値と成り得る値より大きく、かつ最も近い値を保持する。具体的にはレジスタＥ７０３は、１２２＊Ｐを保持する。
インバータ７０８は、レジスタＥ７０３に保持される１０２２＊Ｐの反転値（以下、¬１０２２＊Ｐと表記する）を出力する。
【０１１０】
セレクタ７０４は、制御部８６の制御に従って、０と１０２２＊Ｐと¬１０２２＊Ｐのうちからいずれかを補正値として選択してセレクタ７０６に供給する。セレクタ７０６は、制御部８６の制御に従って、０または１をセレクタ７０６に供給する。ここで制御部８６は、レジスタＳ７０７に保持される累算値の正負に応じてセレクタ７０４に補正値を選択させ、またセレクタ７０６に０または１を選択させて加算器７０５に供給させる。
【０１１１】
詳しくは制御部８６は、レジスタＳ７０７の最上位ビットが０であれば、セレクタ７０４に¬１０２２＊Ｐを選択させ、セレクタ７０６に１を選択させる。これによってレジスタＳ７０７に保持される累算値が正（最上位ビットが０）である場合には、レジスタＥ７０３からインバータ７０８、セレクタ７０４を介して¬１０２２＊Ｐが、またセレクタ７０６を介して１が加算器７０５に供給される。これのおかげで加算器７０５の次の加算においては１０２２＊Ｐが減算されることになり、加算器７０５及びレジスタＳ７０７における桁あふれが予防される。
【０１１２】
制御部８６は、レジスタＳ７０７に保持される累算値が負（最上位ビットが１）である場合には、セレクタ７０４に０を選択させ、またセレクタ７０６に０を選択させる。
また制御部８６は、ｉ＝１〜１８の繰り返し処理が終わり、レジスタＳ７０７の保持する値が最終的な累算値に更新された場合、その累算値の最上位ビットが１か０かを判定し、１（負を示す）である場合には、セレクタ７０４に１０２２＊Ｐを、セレクタ７０６に０を選択させ、加算器７０５においてレジスタＳ７０７に保持される累算値に１０２２＊Ｐを加えるという補正を行わせる。これによって制御部８６は、最終的な累算値が正になるよう補正させる。また制御部８６は、最終的な累算値の最上位ビットが０（正を示す）の場合には、セレクタ７０４に０を、セレクタ７０６に０を選択させ、累算値の補正が行われないようにする。
【０１１３】
なお部分積算出部８３は、図１５のように構成してもよい。
同図は、図１１に対して、シフタ８４７及びシフタ８４６を備える点と、演算値選択器８４０、８４１、８４２の代わりに演算値選択器８５０、８５１、８５２を備える点が異なっている。
シフタ８４７は、部分乗数ｂ（ｉ）を右に３ビットシフトして出力する。
【０１１４】
シフタ８４６は、部分乗数ｂ（ｉ）を左に３ビットシフトして出力する。
図１６は、演算値選択器８５０、８５１、８５２に共通の制御回路の入出力論理を示す。このように図１６に示す部分積算出部８３は、シフタ８４７及びシフタ８４６を備えることによって、右に３ビットシフトさせた部分乗数ｂ（ｉ）と、部分乗数ｂ（ｉ）そのものと、左に３ビットシフトさせた部分乗数ｂ（ｉ）とを選択器５２に入力させる。こうすることにより演算値選択器８５０、８５１、８５２は、同じ入出力論理を適用することができる。また演算値選択器８５０、８５１、８５２がいずれも同じ入出力論理を適用できるので、制御回路を１つにしても良い。
【０１１５】
また実施形態１において剰余算出部１２が有するROMテーブルは２つ、実施形態２において剰余算出部８２が有するROMテーブルは１つであったが、３つ以上のROMテーブルを備えるようにしてもよい。
＜式の展開＞
実施形態１における（式１）から（式２）の変形過程を以下に示しておく。
【０１１６】
【数９】
0004293665.tif 000008
【０１１７】
【発明の効果】
本発明の剰余乗算装置は、被乗数ａと乗数ｂ（ｂはｋｂビットのデータ）との積に対して、法ｐ（ｐはｋビットデータ）による剰余と合同な値を次式の累算値として算出する剰余乗算装置であって、
累算値  ＝  Σ   C(i)*b[s*i+s-1:s*i]
（ここでΣはi=０〜[[kｂ/s]]までの累算を示す。[[kｂ/s]]は商kｂ/sの整数部分であり、iは０から[[k/s]]までの整数であり、C(i)は漸化式で表わされi=0のときC(i)=a、i>=1のときC(i)≡(C(i-1)*2s) mod ｐであり（≡は両辺の値が法ｐにおいて合同であることを示す））
b[s*i+s-1:s*i]は、ｋビットの乗数ｂのうち2s*i+s-1の位から2s*iの位までのｓビットの部分乗数であり、前記剰余乗算装置は、ｍ(ｍはｓ以上の整数)ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶するテーブル手段と、初回（i=0）では被乗数ａを中間数C(0)として出力し、２回目以降（i>0）では、前回出力された中間数C(i-1)をｓビット桁上げし、桁上げ後の中間数の下位ｋビットを除く上位のｍビットについての前記剰余をテーブル手段から読み出し、読み出した剰余と下位ｋビットとを加算することにより新たな中間数(i)を算出する中間数算出手段とを備え、算出された各中間数C(i)と、それに対応する部分乗数b[s*i+s-1:s*i]との部分積C(i)*b[s*i+s-1:s*i]を順次累算することによって前記累算値を算出するよう構成される。
【０１１８】
この構成によれば、テーブル手段はｍビットにより表現される各値、つまり０から２m−１に相当する各値について、それらの値の２K倍に対する法ｐによる剰余を予め記憶する。中間数算出手段は、ｉ＞＝１のとき、まず桁上げ後の中間数の下位ｋビットを除く上位ｍビットについての剰余、つまり上位ｍビットの２k倍に対する法ｐによる剰余をテーブル手段から読み出す。次に中間数算出手段は、テーブル手段より読み出した剰余と下位ｋビットとを加算することにより桁上げ後の中間数の法ｐによる剰余又は合同な値を算出する。
【０１１９】
ここで桁上げ後の中間数の下位ｋビットは、法ｐによる剰余そのものの値であるか、又は法ｐによる剰余と合同な値である。この合同な値は、剰余より大きくかつ剰余により近い値である。よって桁上げ後の中間数について法ｐによる剰余又は合同な値であって剰余により近い値を得るには、中間数算出手段は、上位ｍビットについて剰余を得て、これと下位ｋビットとを加え合わせればよい。中間数算出手段は、上位ｍビットの剰余をテーブル手段から読み出すことによって、桁上げ後の中間数の法ｐによる剰余又は合同な値をより短時間で算出する。
【０１２０】
仮に、従来技術の剰余乗算装置１の剰余算出部３における剰余算出の手順と同様な手順を用いて桁上げ後の中間数の法ｐによる剰余を求めるとすれば、中間数算出部は、ステップ６〜８のループ処理を複数回繰り返さなければならない。より詳しくは、このループ処理の回数は、桁上げ後の中間数のビット数に相当する。これに対し本発明における中間数算出部は、テーブル部の１回の読み出しと、１回の加算によって桁上げ後の中間数の法ｐによる剰余又は合同な値を算出することができ高速な剰余演算を実現できる。
【０１２１】
また中間数算出手段は、漸化的に前回の中間数を桁上げした値の剰余を中間数として算出し、これによって中間数算出手段は、算出する中間数のビット数の増大を防止している。この防止により、中間数を用いて算出される部分積のビット数の増大を防止する。この結果、部分積の累算においてはビット数の抑えられた部分積を用いて加算を行えばよいので、加算器の回路規模を抑えることができる。
【０１２２】
また前記中間数算出手段は、中間数を保持する第１保持手段と、部分乗数b[s*i+s-1:s*i]に対応して、第１保持手段に保持された中間数をｓビット桁上げする桁上げ手段と、桁上げ後の中間数を、桁上げ後の中間数における下位ｋビットよりも上位のｍビットの部分である上位データと下位ｋビットの部分である下位データとに分割する分割手段と、分割手段による上位データに対する法ｐによる剰余を前テーブル手段から読み出す読み出し手段と、テーブル手段から読み出された剰余と、分割手段による下位データとを加算することにより新たな中間数を得る加算手段とを備え、前記第１保持手段は、加算手段において新たな中間数が得られる度にその保持内容を新たな中間数に更新し、前記初回では被乗数を中間数として出力し、前記２回目以降では更新後の新たな中間数を出力するよう構成される。
【０１２３】
この構成によれば、中間数算出手段内部の各構成要素は、汎用のハードウェア素子を用いて簡単に構成することができる。つまり第１保持手段はレジスタ、桁上げ手段はシフタ、分割手段は前記シフタの上位ｍビット部分と下位ｋビット部分に接続されたｍビットのバスとｋビットのバス、加算手段は加算器を用いて構成でき、これらの構成要素によって中間数算出手段は、中間数Ｃ（ｉ）を漸化的に算出する。
【０１２４】
また前記剰余乗算装置は、さらに、前記分割手段、読み出し手段、加算手段を利用することにより、前記累算値の法ｐによる剰余を求める後処理手段を備える。
この構成によれば、後処理手段が最後の累算値の法ｐによる剰余を求めることにより、最後の累算値をｐよりも小さい値にすることができる。
【０１２５】
また前記テーブル手段は、ｍビットにより表現される各値に対応するアドレスが入力され、そのアドレスが指す記憶領域に当該アドレスに対応するｍビットの値の２k倍に対する法ｐによる剰余を予め記憶するメモリ素子を有する。
この構成によれば、テーブル手段はメモリ素子１個で実現することができる。メモリ素子は、ｍビットにより表現される各値、つまり１０進数の０から２m−１に相当する各値について、その２k倍の法ｐによる剰余を予め記憶する。これら剰余の記憶領域を指し示すアドレスは、各値と同じ値である。メモリ素子は、読み出し手段から上位ｍビットが入力されると、その値をアドレスとして、そのアドレスが示す記憶領域の剰余が読み出し手段によって読み出される。これによって中間数算出手段は、メモリ素子からの１回の読出しを行うだけで、上位ｍビットに対応する剰余を短時間で得ることができる。
【０１２６】
また前記mビットは下位m1ビットと上位m2ビット（m＝m1+m2）とに分割され、前記mビットにより表現される各値は、m1ビットにより表現される値とm2ビットにより表現される値との組み合わせに対応し、前記テーブル手段は、m1ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶する第１部分テーブル手段と、m2ビットにより表現される各値について、その値の２k+m1倍に対する法ｐによる剰余を予め記憶する第２部分テーブル手段とを備え、前記加算手段は、第１、第２部分テーブルからの読み出されたそれぞれの剰余と、前記下位データとを加算することにより新たなっ中間数を得るよう構成される。
【０１２７】
この構成によれば、テーブル手段は、ｍビットのうち上位側のｍ１ビットに対応する第１部分テーブル手段と、下位側のｍ２ビットに対応する第２部分テーブル手段とを有する。第１部分テーブル手段は、上位側ｍ１ビットに対応する剰余を２m1個記憶し、第２部分テーブル手段は、下位側ｍ２ビットに対応する剰余を２m2個記憶する。この個数からわかるように、第１及び第２部分テーブル手段とを合わせた剰余の記憶個数は、メモリ素子１個の場合に比べて、さらに少なくなる。これによりテーブル手段は、記憶容量の小さい２つのメモリ素子によって構成することができる。
【０１２８】
また前記mビットは下位側からt(3≦t≦m)個の部分ビットm1、…、mtに分割され、前記mビットにより表現される各値は、各mi（ｉは１からｔまで整数）ビットにより表現される値（ｔ個）を組み合わせたものに対応し、前記テーブル手段は、部分ビットmiビットにより表現される各値について、その値の２k+x倍（ここでｘ=m1+…＋m(i-1)である）に対する法ｐによる剰余を予め記憶するｔ個の部分テーブル手段Ｔiを備え、前記加算手段は、ｔ個の部分テーブル手段Tiからの読み出されたｔ個の剰余と、前記下位データとを加算することにより新たな中間数を得るよう構成される。
【０１２９】
このようにテーブル手段は、ｍビットを分割したｔ個の部分ビットの各値に対応するｔ個の部分テーブル手段Tiを有する。このようにテーブル手段は、複数の部分テーブル手段Tiを有することにより各部分テーブル手段Tiにおける剰余の記憶個数を少なくしている。
前記剰余乗算装置は、さらに累算手段と補正手段とを備え、前記累算手段は、初期値として０を保持する第３レジスタと、部分積C(i)*b[s*i+s-1:s*i]と第３レジスタに保持された累算値とを加算し、加算結果を新たな累算値として第３レジスタに出力して保持させる加算器とを備え、前記補正手段は、ｐの整数倍の値をもつ補正値を保持する補正値保持手段と、前記第３レジスタに保持された累算値が所定の値以上であれば、補正値保持手段に保持された補正値を、前記加算器に減算させる補正制御手段とを備える。
【０１３０】
この構成によれば補正制御手段は、累算値が所定の値以上であれば、加算器に累算値から補正値を減算させるので、第３レジスタにおける桁あふれが防止される。
また前記第３レジスタは符号ビットを有し、前記補正制御手段は、第３レジスタの累算値が正であれば、前記加算器に対して累算値と部分積との加算と同時に前記補正値を減算させ、前記補正値は、ｐの整数倍であってその絶対値が前記部分積の最大値(t+1)(2 s -1)p以下の値であることを特徴とする。
【０１３１】
この構成によれば、補正制御手段は第３レジスタに保持される累算値の符号ビットが１（累算値が正を示す）であるとき、加算器に累算値から補正値を減算させるので、第３レジスタにおける桁あふれが防止される。また補正値は、ｐの整数倍であって前記部分積の最大値(t+1)(2s-1)p以下の値であるので、累算値の最終的な値がｐより小さい値か又はｐに近い値にする。
【０１３２】
また前記法ｐはｐ＝2k−αの関係を満たし、各部分テーブル手段Ｔiは、前記剰余をk3ビットのデータとして記憶する、ここで、k3はt*2m*αのビット数であり、前記αは、k3がｋより小さくなるように定められた定数であることを特徴とする。
この構成によればｐ＝2k−αの関係を満たし、αはｋ３がｋより小さくなるように上限を定められた定数である。これらによって部分テーブル手段Tiに記憶される剰余はｋ３ビットまでに制限することができ、部分テーブルからの出力ビット数を少なくすることができる。部分テーブル手段Tiから出力される剰余のビット数がｋ３ビット以下であるので、それに合わせて加算部のビット幅も制限することができる。
【０１３３】
また各部分テーブル手段Ｔiは、miビットにより表現される０から(2mi-1)までの値に対応する2mi個のエントリを有し、ｊ(jは０から2miまで)番目のエントリは、j*2m1+…+m(i-1) *αを格納していることを特徴とする。
この構成において、部分テーブル手段Tiは、記憶するエントリの個数を２mi−１と制限することができ、部分テーブルの規模を小さくすることができる。
【０１３４】
また、αが仮にｕビットであるとすると、ｊ番目のエントリであるｊ*2m1+…+m(i-1)＊αのビット数は、最大でもｊのビット数にｍ１＋ｍ２＋...＋ｍ（ｉ−１）とｕビットとを加え合わせた値に制限することができる。部分テーブル手段Tiより出力される剰余を加算する加算手段は、ビット幅を制限することができる。
【０１３５】
本発明の剰余乗算装置は、被乗数と乗数との積に対する法ｐ（ｐはｋビットデータ）による剰余と合同な数を算出する剰余乗算装置であって、乗数をｓ（ｓは２以上の整数）ビットずつに分けて得られるｓビットの部分乗数を下位側から順に出力する出力手段と、各部分乗数の位に応じて、被乗数を桁上げし、桁上げ後の被乗数に対して、法ｐによる剰余と合同な数（以下中間数と呼ぶ）を算出する第１算出手段と、出力手段により出力された部分乗数と、当該部分乗数に対応して第１算出手段により算出された前記中間数との積を部分積として算出する第２算出手段と、第２算出手段に算出された部分積を累算する累算手段と、累算手段に累算された累算値にｐの整数倍の値を加減算することにより、累算値を所定のビット数を越えないように補正する補正手段と、出力手段により全ての部分乗数が出力されるまで、第１算出手段による中間数の算出と、第２算出手段による部分積の算出と、累算手段による累算と、補正手段による補正とを繰り返し行わせる制御手段とを備え、前記第１算出手段は、ｍ(ｍはｓ以上の整数)ビットにより表現される各値について、その値の２k倍に対する法ｐによる剰余を予め記憶し、制御手段による繰り返しのうち初回では被乗数を中間数として出力し、２回目以降では、前回出力された中間数をｓビット桁上げし、桁上げ後の中間数の下位ｋビットより上位のｍビットについてテーブル手段を読み出し、読み出した数と下位ｋビットとを加算することにより新たな中間数を算出するよう構成される。
【０１３６】
この構成によれば第１算出手段は、制御手段により繰り返しのうち２回目以降では、ｓビット桁上げされた桁上げ後の中間数の下位ｋビットを除く上位もｍビットについてテーブル手段より対応する剰余を読出し、その剰余と下位ｋビットとを加算することにより、桁上げ後の中間数の法ｐによる剰余又は合同な値を中間数として算出する。これによって第１算出手段は、剰余の算出を高速に行う。
【０１３７】
また第２算出手段は、ｓビットの部分乗数毎に部分乗数と中間数との部分積を算出する。このように複数桁の部分乗数ずつ部分積を算出するので、部分乗数の個数分だけ部分積の算出を行えばよく、第２算出手段における繰り返しの回数が減り、従来技術の積算出部２に比べて高速になる。
また前記制御手段は、第１〜第３ステージを含むパイプライン処理を制御する、第１ステージでは出力手段に部分乗数を出力させるとともに第１算出手段に中間数を出力させ、第２ステージでは第２算出手段に部分積を算出させ、第３ステージでは累算手段に累算させるともに補正手段に補正させるよう構成される。
【０１３８】
この構成によれば剰余乗算装置は、パイプライン処理を行うので、各構成要素における処理が効率良く行われ、演算の処理速度がより高速になる。
また前記出力手段は、最初に乗数を保持し、保持している値の下位ｓビットを部分乗数として出力する乗数保持手段と、乗数保持手段に保持されている値をｓビット下位側にシフトさせ、シフト後の値を乗数保持手段に出力して保持させるシフト手段とを備える。
【０１３９】
この構成によれば、出力手段は、乗数を保持するレジスタと、保持された乗数をｓビット下位側にシフトさせるシフタによって簡単に構成することができる。
また前記第２生成手段は、第ｉ（ｉは１から（ｓ−１）の整数）のシフト手段は、第１算出手段により算出された前記中間数をｉビット左シフトにより桁上げする第１から第（ｓ−１）のシフト手段を備え、前記第１生成手段は、第１算出手段により算出された前記中間数をｓビット左シフトにより桁上げする第ｓのシフト手段と、前記中間数の１の補数を生成する補数生成手段と、定数１を出力する定数出力手段とを備え、前記第２加算手段は、全ビットが１であると判定された場合に、第ｓのシフト手段の出力と、補数生成手段に生成された１の補数と、定数１を選択し、全ビットが１であると判定されなかった場合に、部分乗数の２0の位が”１”であれば前記中間数を選択し、部分乗数の２iの位が”１”であれば、第ｉのシフト手段の桁上げ結果を選択する選択手段と、選択手段の選択結果を加算することにより前記部分積を算出する加算器とを備える。
【０１４０】
この構成によれば、第１から第（ｓ−１）のシフト手段は、１〜（ｓ−１）ビット左シフトを行うシフタによって実現される。第ｓのシフト手段は、ｓビット左シフトを行うシフタによって実現される。補数生成手段は、インバータにより実現される。このように第１生成手段及び第２生成手段は、汎用的なハードウェア素子によって構成することができる。これらの構成要素は、加算手段に加算させるべき候補の値を前もって生成する。選択手段は、部分乗数の値に応じて候補の値から加算手段に加算させるべき値を選択する。加算手段は、選択された候補の値を加算することによって部分積を算出する。このような構成によって第２算出手段は、複数桁の中間数と部分乗数との部分積を高速に算出することができる。
【図面の簡単な説明】
【図１】第１実施形態における剰余乗算装置１００の概略構成を示すブロック図である。
【図２】剰余算出部１２のより詳細な構成図を示す。
【図３】（ａ）ＲＯＭテーブル３０９の記憶内容を示す。
（ｂ）ＲＯＭテーブル３０８の記憶内容を示す。
【図４】乗数分割部１１のより詳細な構成を示す。
【図５】部分積算出部１３のより詳細な構成を示す。
【図６】累算部１４及び補正部１５の詳細な構成を示す。
【図７】第２実施形態における剰余乗算装置２００の概略構成を示すブロック図である。
【図８】剰余算出部８２のより詳細な構成を示す。
【図９】ＲＯＭテーブル９０４の記憶内容を示す。
【図１０】乗数分割部８１のより詳細な構成を示す。
【図１１】部分積算出部８３のより詳細な構成を示す。
【図１２】演算値選択器８４０、８４１、８４２の詳細な構成を示す。
【図１３】（ａ）は、制御回路１３０６に入力される部分乗数ｂ（ｉ）と制御回路１３０６の入出力論理との対応を示す。
（ｂ）は、制御回路１３０５に入力される部分乗数ｂ（ｉ）と制御回路１３０５の入出力論理との対応を示す。
（ｃ）は、制御回路１３０４に入力される部分乗数ｂ（ｉ）と制御回路１３０４の入出力論理との対応を示す。
【図１４】累算部８４及び補正部８５のより詳細な構成を示す。
【図１５】部分積算出部８３は、図１５のように構成してもよい。
【図１６】演算値選択器８５０、８５１、８５２に共通の制御回路の入出力論理を示す。
【図１７】従来の剰余乗算装置の構成を示す。
【符号の説明】
１００    剰余乗算装置
１１      乗数分割部
１２      剰余算出部
１３      部分積算出部
１４      累算部
１５      補正部
１６      制御部
３０８    ＲＯＭテーブル
３０９    ＲＯＭテーブル
３０１    セレクタ
３０２    レジスタＡ
３０３    シフタ
３０４    セレクタ
３１０    加算器
３１１    剰余演算部
【図１】
0004293665.tif 000011
【図２】
0004293665.tif 000012
【図３】
0004293665.tif 000013
【図４】
0004293665.tif 000014
【図５】
0004293665.tif 000015
【図６】
0004293665.tif 000016
【図７】
0004293665.tif 000017
【図８】
0004293665.tif 000018
【図９】
0004293665.tif 000019
【図１０】
0004293665.tif 000020
【図１１】
0004293665.tif 000021
【図１２】
0004293665.tif 000022
【図１３】
0004293665.tif 000023
【図１４】
0004293665.tif 000024
【図１５】
0004293665.tif 000025
【図１６】
0004293665.tif 000026
【図１７】
0004293665.tif 000027