(57)【要約】乗算機関において、Ｒ＝Ｘ．ＹｍｏｄＮとなる結果Ｒを生成するために整数ＸとＹとのモジュラ乗算を実行する方法である。各々が第一の所定の数のビットｋを有する第一の複数の語ｘｎにＸは断片化され、各々が第二の所定の数のビットｍを有する第二の複数の語ｙｎにＹは断片化される。Ｘの語ｘｎの倍数が前計算回路において得られ、その後Ｙの複数の語ｙｎの各々とのＸの語ｘｎの積を得るために使用される。中間結果Ｒｊは、前記前計算された倍数から得られる累積和としてを算出され、当該ステップは、第一の複数の語ｘｎの各々に対して連続した中間結果Ｒｊを生成するように各々の連続したＸの語に対して繰り返される。最終結果Ｒは最後の中間結果Ｒｎ−１から得られる。
2006508464.tif 000002
【特許請求の範囲】
【請求項１】
乗算機関において、Ｒ＝Ｘ．ＹｍｏｄＮとなる結果Ｒを生成するために整数ＸとＹとのモジュラ乗算を実行する方法であって、
（ａ）各々が第一の所定の数のビットｋを有する第一の複数の語ｘｎにＸを断片化するステップと、
（ｂ）各々が第二の所定の数のビットｍを有する第二の複数の語ｙｎにＹを断片化するステップと、
（ｃ）前計算回路においてＸの語ｘｎの倍数を前計算すると共に、前記Ｙの複数の語ｙｎの各々との前記Ｘの語ｘｎの積を得るために、前記前計算された倍数を使用するステップと、
（ｄ）前記前計算された倍数から得られる累積和として中間結果Ｒｊを算出するステップと、
（ｅ）前記第一の複数の語ｘｎの各々に対して連続した中間結果Ｒｊを生成するように各々の連続したＸの語に対して前記前計算するステップ及び前記算出するステップを繰り返すステップと、
（ｆ）最終結果を形成するように前記中間結果Ｒｊの各々を出力としてもたらすステップと
を有する方法。
【請求項２】
Ｂｘ＝２ｋの場合、式Ｘ＝ｘｎ−１Ｂｘｎ−１＋ｘｎ−２Ｂｘｎ−２．．．＋ｘ０に従ってＸが各々ｋビットのｎ語に断片化される請求項１に記載の方法。
【請求項３】
Ｂｙ＝２ｍの場合、式Ｙ＝ｙｎ−１Ｂｙｎ−１＋ｙｎ−２Ｂｙｎ−２．．．＋ｙ０に従ってＹが各々ｍビットのｎ語に断片化される請求項１に記載の方法。
【請求項４】
前記中間結果Ｒｊを算出するステップが加算に対する項の連続部ｘ．ｙ＋ｃ＋ｚを生成するステップを有し、
（ｉ）ｘｎ．ｙｎ積を形成するためにＸの語ｘｎの前計算された倍数を読み出すステップと、
（ｉｉ）先行する項からのキャリー語ｃｊを加算するステップと、
（ｉｉｉ）先行する中間結果からの対応する項ｚを加算するステップと、
（ｉｖ）前記結果をより低い次数ｍビット語及びより高い次数ｋビットキャリー語に断片化するステップと、
（ｖ）ｘｎ．ｙｎ積の各々に対してステップ（ｉ）乃至（ｉｖ）を繰り返すステップと、
（ｖｉ）全てのｘｎ．ｙｎ積の使用後、前記先行する中間結果からの対応する項と最終キャリー語とを加算することによって最終項を形成するステップと
を有する請求項１に記載の方法。
【請求項５】
前記中間結果を算出するステップが
Rj
= xn-j+1y0 + (xn-j+1y1 + rj-1,0)By
+ (xn-j+1y2 + rj-1,1)By2   + …
+ (xn-j+1yn-1 + rj-1,n-2) Byn-1  + rj-1,n-1) Byn
として実現される請求項４に記載の方法。
【請求項６】
ステップ（ｆ）が、Ｒを形成するために式
R = ((((xn-1Y
mod N )Bx + xn-2Y) mod N)Bx + …x0Y) mod N
に従って全ての前記中間結果Ｒｊを結合するステップを更に含む請求項１に記載の方法。
【請求項７】
ステップ（ｉ）が前記Ｘの語ｘｎの選択基本倍数を読み出すと共にｚ前記積ｘｎ．ｙｎを得るために当該倍数を結合するステップを有する請求項４に記載の方法。
【請求項８】
ステップ（ｉ）、（ｉｉ）、及び（ｉｉｉ）が、加算器回路において前記Ｘの語の前記選択基本倍数と、前記キャリー語ｃｊと、前記対応する項ｚとを結合するステップを更に含む請求項７に記載の方法。
【請求項９】
先行する中間結果からの前記対応する項ｚが、前記先行する中間結果からの中間の下位語となる請求項４に記載の方法。
【請求項１０】
先行する中間結果からの前記対応する項ｚが、前記先行する中間結果からのｋ／ｍ番目の下位語となる請求項４に記載の方法。
【請求項１１】
前記前計算するステップが
前記Ｘの語の前選択基本倍数を計算するステップと、所望のＸ、Ｙ積を形成するために前記基本倍数を結合するステップと、
を有する請求項１に記載の方法。
【請求項１２】
Ｘの語の倍数の前記前計算が前記先行する語に対してステップ（ｖｉ）の間に行われる請求項４に記載の方法。
【請求項１３】
Ｒ＝Ｘ．ＹｍｏｄＮとなる結果Ｒを生成するために整数ＸとＹとのモジュラ乗算を実行するための装置であって、
各々が第一の所定の数のビットｋを有する第一の複数の語ｘｎにＸを断片化するための手段と、
各々が第二の所定の数のビットｍを有する第二の複数の語ｙｎにＹを断片化するための手段と、
Ｘの語ｘｎの倍数を前計算すると共に、前記Ｙの複数の語ｙｎの各々との前記Ｘの語ｘｎの積を得るために前記前計算された倍数を使用する前計算回路と、
前記前計算された倍数から得られる累積和として中間結果Ｒｊを算出するための手段と、
前記第一の複数の語ｘｎの各々に対して連続した前記中間結果Ｒｊを生成するように各々の連続したＸの語に対する中間結果の前記前計算及び前記算出の繰り返しを制御するための制御手段と
を有する装置。
【請求項１４】
前記中間結果Ｒｊを算出するための手段が、加算に対する項の連続部ｘ．ｙ＋ｃ＋ｚを生成し、  
（ｉ）ｘ．ｙ積を形成するためにＸの語ｘの前計算された倍数を読み出すための手段と、
（ｉｉ）先行する項からのキャリー語ｃｊを加算するための手段と、
（ｉｉｉ）先行する中間結果からの対応する項ｚを加算するための手段と、
（ｉｖ）前記結果をより低い次数ｍビット語及びより高い次数ｋビットキャリー語に断片化するための手段と、
（ｖ）前計算された倍数の前記読み出しと、前記ｘ．ｙ積の各々に対して対応する項及び前記キャリー語の加算との繰り返しをもたらすと共に、前記先行する中間結果からの対応する項と最終キャリー語とを加算することによって最終項を形成するための制御手段と
を有する請求項１３に記載の装置。
【請求項１５】
積ｘ．ｙを形成するために複数の整数Ｘの倍数の各々をもたらすための計算回路であって、
複数のｘの基本倍数を得るためのシフト回路及び加算器回路と、
前記複数のｘの基本倍数のうちの少なくともいくつかを記憶するための複数のレジスタと、
各々が前記ｘの基本倍数を受信すると共に選択されたｙ語の選択ビットを受信するための選択線を有する複数のマルチプレクサと、
前記各々のマルチプレクサからの出力を受信すると共に、前記各マルチプレクサ選択線に対する入力として使用される前記ｙ語の部分の数の重みに従って当該出力を結合するための総和回路と
を有する計算回路。
【請求項１６】
前記複数のレジスタは、選択された奇数のｘの基本倍数に対応し、偶数のｘの基本倍数は、前記複数のレジスタのうちの選択されたレジスタに結合される線をビットシフトすることによって各々のマルチプレクサにもたらされる請求項１５に記載の計算回路。
【請求項１７】
前記複数の出力マルチプレクサは、各々が、ｘの各基本倍数を受信するように接続される第一の入力部と、論理ゲートの出力部における前記基本倍数の活性化を可能にする選択線とを有する一組の論理ゲートを有し、
前記総和回路は、前記論理ゲートの列の全ての活性化された出力を受信するための一連の加算器を有し、
選択入力が変化させられている前記一組の論理ゲートにおける論理ゲートのみが、前記選択されたｙ語における変化の間にスイッチされる
請求項１５に記載の計算回路。
【請求項１８】
プログラムがコンピュータ上にロードされるとき、請求項１乃至１２の何れか一項に記載のプロシージャを前記コンピュータに実行させるように適用されるコンピュータプログラムコード手段を有するコンピュータ読み出し可能な媒体を有するコンピュータプログラム。
【請求項１９】
プログラムがコンピュータ上にロードされるとき、請求項１乃至１２の何れか一項に記載のプロシージャを前記コンピュータに実行させるように適用されるコンピュータプログラムコード手段を有する、電子データ送信によって分配可能なコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、長整数モジュラ乗算（ｌｏｎｇ  ｉｎｔｅｇｅｒ  ｍｏｄｕｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）を効率的に実現するための方法及び装置に関する。  
【背景技術】
【０００２】
電子デバイスにおける暗号化アルゴリズムの増大する使用により、長整数モジュラ乗算を高速且つ効率的に実行する必要性がもたらされてきた。例えばスマートカード及び多くの他の電子デバイスが、ＲＳＡのような複数の暗号化プロトコル、並びに楕円曲線及び超楕円曲線（ｈｙｐｅｒ  ｅｌｌｉｐｔｉｃ）計算に基づく他のプロトコルを使用している。これらのプロトコルの全ては基本的な要求仕様として、形式Ｒ＝Ｘ．ＹｍｏｄＮの長整数モジュラ乗算を実行する機能を有している。
【０００３】
通常ＲＳＡのようなプロトコルの場合、長整数Ｘ及びＹは１０２４ビット、又は２０４８ビット整数にさえなり、乗算動作が、暗号化（ｅｎｃｒｙｐｔｉｏｎ）又は復号化（ｄｅｃｒｙｐｔｉｏｎ）動作を完了させるために何百回又は何千回も実行されなければならない。それ故にこれらの動作を実行する暗号化デバイスは、高速乗算器を使用して長整数乗算を高速に実行することが所望される。
【０００４】
従来、当該乗算を高速実行するように設計される電子デバイスは多くの電力を消費しており、このことは、スマートカード及び他の小型電子デバイスのような低消費電力を有することを意図するデバイスにおいて所望されていない。  
【発明の開示】
【発明が解決しようとする課題】
【０００５】
それ故に本発明の目的は、消費電力を低減する態様で装置において長整数モジュラ乗算を可能にするための方法を提供することにある。  
【課題を解決するための手段】
【０００６】
一つの態様によれば本発明は、乗算機関において、Ｒ＝Ｘ．ＹｍｏｄＮとなる結果Ｒを生成するために整数ＸとＹとのモジュラ乗算を実行する方法であって、
（ａ）各々が第一の所定の数のビットｋを有する第一の複数の語ｘｎにＸを断片化するステップと、
（ｂ）各々が第二の所定の数のビットｍを有する第二の複数の語ｙｎにＹを断片化するステップと、
（ｃ）前計算回路においてＸの語ｘｎの倍数を前計算すると共に、前記Ｙの複数の語ｙｎの各々との前記Ｘの語ｘｎの積を得る（導き出す）ために、前記前計算された倍数を使用するステップと、
（ｄ）前記前計算された倍数から得られる累積和として中間結果Ｒｊを算出するステップと、
（ｅ）前記第一の複数の語ｘｎの各々に対して連続した中間結果Ｒｊを生成するように各々の連続したＸの語に対して前記前計算するステップ及び前記算出するステップを繰り返すステップと、
（ｆ）最終結果を形成するように中間結果Ｒｊの各々を出力としてもたらすステップと
を有する方法を提供する。
【０００７】
他の態様によれば本発明は、Ｒ＝Ｘ．ＹｍｏｄＮとなる結果Ｒを生成するために整数ＸとＹとのモジュラ乗算を実行するための装置であって、
各々が第一の所定の数のビットｋを有する第一の複数の語ｘｎにＸを断片化するための手段と、
各々が第二の所定の数のビットｍを有する第二の複数の語ｙｎにＹを断片化するための手段と、
Ｘの語ｘｎの倍数を前計算すると共に、前記Ｙの複数の語ｙｎの各々との前記Ｘの語ｘｎの積を得るために前記前計算された倍数を使用する前計算回路と、
前記前計算された倍数から得られる累積和として中間結果Ｒｊを算出するための手段と、
前記第一の複数の語ｘｎの各々に対して連続した中間結果Ｒｊを生成するように各々の連続したＸの語に対する中間結果の前記前計算及び前記算出の繰り返しを制御するための制御手段と
を有する装置を提供する。
【０００８】
更に他の態様によれば本発明は、積ｘ．ｙを形成するために複数の整数Ｘの倍数の各々をもたらすための計算回路であって、
複数のｘの基本倍数を得るためのシフト回路及び加算器回路と、
前記複数のｘの基本倍数のうちの少なくともいくつかを記憶するための複数のレジスタと、
各々が前記ｘの基本倍数を受信すると共に選択されたｙ語の選択ビットを受信するための選択線を有する複数のマルチプレクサと、
前記各々のマルチプレクサからの出力を受信すると共に、前記各マルチプレクサ選択線に対する入力として使用される前記ｙ語の部分の数の重みに従って当該出力を結合するための総和回路と
を有する計算回路を提供する。
【０００９】
本発明の実施例はこの場合例示によって、及び添付図面を参照して記載されるであろう。
【発明を実施するための最良の形態】
【００１０】
Ｘ及びＹが例えば１０２４又は２０４８ビット長のオーダの長整数変数である場合のＮを法とした積Ｘ．Ｙ（Ｘ．ＹｍｏｄＮ）を計算するために、長整数変数Ｘ及びＹは例えば長さが３２ビットのより小さな“語（ワード（ｗｏｒｄ））”に分割される。後に記載の好ましい実施例において、Ｘは長さが６４ビットの“語”に分割され、Ｙは長さが１６ビットの“語”に分割される。
【００１１】
まずＸは
Ｘ＝ｘｎ−１Ｂｘｎ−１＋ｘｎ−２Ｂｘｎ−２．．．＋ｘ０
（ここでＢｘ＝２ｋ）となるようにｎ語、通常長さｋの各々に分割される。一つの例においてｋ＝３２となり、他の例においてｋ＝６４となる。
【００１２】
この態様でＸは、各々長さｋビットの複数の語に断片化（分割）（フラグメント（ｆｒａｇｕｍｅｎｔ））される。それから結果Ｒが次のように計算される。
【数１】
2006508464.tif 000003
従って、Ｒｊ＝（ｘｎ−ｊ−１Ｙ＋Ｒｊ−１Ｂｘ）ｍｏｄＮとなる。
【００１３】
まず、ｘｎ−１が完全なＹによって乗算され、それの法（モジュロ（ｍｏｄｕｌｕａ））が計算される。当該結果はＲ０となる。次にｘｎ−２が完全なＹ（ｃｏｍｐｌｅｔｅ  Ｙ）によって乗算され、Ｚ０＝Ｒ０．Ｂｘがその結果に加算され、Ｎを法とした低次元化（モジュロＮリダクション（ｍｏｄｕｌｏ  Ｎ  ｒｅｄｕｃｔｉｏｎ））が計算される。当該結果はＲ１となる。次にｘｎ−３が完全なＹによって乗算され、Ｚ１＝Ｒ１．Ｂｘがその結果に加算され、Ｎを法とした低次元化が計算される。当該結果はＲ２となる。このプロシージャは、Ｘの全ての語が使用されるまで繰り返され、ｘ０は処理されるべきＸの最後の語となり、その結果最終的な結果Ｒ＝Ｒｎー１が得られる。しかしながら１０２４ビット長となるＹに対する乗算器は実用的な見地から好ましくない。それ故にＹ、従ってＲｊは、例えば長さが３２ビット又は１６ビットのようなより小さな“語”に更に分解（ブレークダウン）される。それ故にＺｊ−１＝Ｒｊ−１．Ｂｘの場合、基本乗算Ｒｊ＝（ｘｎ−ｊ−１Ｙ＋Ｚｊ−１）ｍｏｄＮも断片化される。
Ｙ及びＲｊは、長さがｍビット、すなわちＢｙ＝２ｍの語に分割される。すなわち
Ｙ＝ｙｎ−１Ｂｙｎ−１＋ｙｎ−２Ｂｙｎ−２．．．＋ｙ０   
Ｒｊ＝ｒｊ，ｎ−１Ｂｙｎ−１＋ｒｊ，ｎ−２Ｂｙｎ−２．．．＋ｒｊ，０ 
となる。
【００１４】
この態様でＹは、各々長さｍビットの複数の語に断片化される。
【数２】
2006508464.tif 000004
Ｒｊの計算に対して、次の動作が実行される、
まず、ｘｎ−ｊ＋１がｙ０によって乗算され、その結果が二つの部分、すなわちより低い部分ｒｊ，０（ｍビット）及びより高い部分ｃｊ，０（ｋビット）に分割される。すなわち
Ｂｙ．ｃｊ，０＋ｒｊ，０＝ｘｎ−ｊ＋１．ｙ０
となる。
【００１５】
次にｘｎ−ｊ＋１がｙ１によって乗算され、先行するキャリー（桁上げ（ｃａｒｒｙ））語ｃｊ，０に加算される。更にＺ０＝ｒｊ−１，０も加算される。その結果はここでも、それぞれ長さがｋ及びｍビットの二つの部分、すなわちより低い部分ｒｊ，１及びより高い部分ｃｊ，１に分割される。すなわち
Ｂｙ．ｃｊ，１＋ｒｊ，１＝ｘｎ−ｊ＋１．ｙ１＋ｃｊ，０＋ｚ０
となる。
【００１６】
次にｘｎ−ｊ＋１がｙ２によって乗算され、先行するキャリー語ｃｊ，１に加算される。更にＺ１＝ｒｊ−１，１も加算される。その結果はここでも、それぞれ長さがｋ及びｍビットの二つの部分、すなわちより低い部分Ｒｊ，２及びより高い部分ｃｊ，２に分割される。すなわち
Ｂｙ．ｃｊ，２＋ｒｊ，２＝ｘｎ−ｊ＋１．ｙ２＋ｃｊ，１＋ｚ１   
となる。
【００１７】
このプロシージャはｙｎ−１によって最後の乗算が実行されるまで、すなわちｘｎ−ｊ＋１がｙｎー１によって乗算され、先行するキャリー語ｃｊ，ｎ−２に加算されるまで繰り返される。更にＺｎ−２＝ｒｊ−１，ｎ−２も加算される。その結果はここでも、それぞれ長さがｋ及びｍビットの二つの部分、すなわちより低い部分Ｒｊ，ｎ−１及びより高い部分ｃｊ，ｎ−１に分割される。すなわち
Ｂｙ．ｃｊ，ｎ−１＋ｒｊ，ｎ−１＝ｘｎ−ｊ＋１．ｙｎ−１＋ｃｊ，ｎ−２＋ｚｎ−２   
となる。
【００１８】
最後のステップは、ｃｊ，ｎ−１とｚｎ−１との加算、すなわちｒｊ，ｎ−１＝ｃｊ，ｎ−１＋ｚｎ−１になる。
【００１９】
通常の態様で、Ｙの複数の語の各々とのＸの第一の語の積が計算され、各々の記憶された積からもたらされる累積和（ｃｕｍｕｌａｔｉｎｇ  ｓｕｍ）として中間結果Ｒｊが計算されることは理解されるであろう。
【００２０】
更に一般的には本計算は、
（ｉ）積ｘ．ｙを得るステップと、
（ｉｉ）（当然のことながら第一の項が計算されるとき、ゼロとなる）先行する項（ｔｅｒｍ）からキャリー語ｃｊを加算するステップと、
（ｉｉｉ）（当然のことながら少なくとも第一のＲｊが計算されるとき、ここでもゼロとなる）先行する中間結果から対応する項ｚを加算するステップと、  
（ｉｖ）結果をより低い次数（オーダ）ｍビット語及びより高い次数ｋビットキャリー語に断片化するステップと、
（ｖ）記憶された積の各々に対してステップ（ｉ）乃至（ｉｖ）を繰り返すステップと、
（ｖｉ）全ての記憶された積の使用後、先行する中間結果からの対応する項と最終キャリー語とを加算することによって最終項を形成するステップと
によって実現される。
【００２１】
この場合Ｒｊは完了させられ、Ｘの一つの語の長さによってもたらされたＹ変数よりも大きくなる。Ｒｊの大きさは好ましくはＮを法とした低次元化で一つの語によって低次元化され、低次元化された結果はそれから、後続するＲｊ＋１の計算の間、ｚｊとして使用される。
【００２２】
上記の計算により、Ｘ語（ｘｎ）の長さはｙ語（ｙｎ）の長さと同じ、すなわちＢｘ＝Ｂｙになる通常プロシージャが示される。
【００２３】
Ｘ語はＹ語と長さが異なっていてもよい。例えばｋ／ｍ＞１、ｋ＝６４、及びｍ＝１６の場合、Ｂｘ＝Ｂｘ４となる。そのとき、
１．ｚの加算は１語の代わりにｋ／ｍ（＝４（例において））語だけシフトされなければならない。すなわち第一のｋ／ｍ（＝４）乗算の間、ｚ＝０となる。従って上記議論のステップ（ｉｉｉ）において、先行する中間結果Ｒｊ−１からの対応する項ｚの加算で、‘対応する項’は、先行する中間結果からの中間の下位語（ｉｎｔｅｒｍｅｄｉａｔｅ  ｌｅｓｓ  ｓｉｇｎｉｆｉｃａｎｔ  ｗｏｒｄ）の代わりに、先行する中間結果Ｒｊ−１から四番目の下位語（ｆｏｕｒｔｈ  ｌｅｓｓ  ｓｉｇｎｉｆｉｃａｎｔ  ｗｏｒｄ）になる。
２．ステップ（ｉｉ）において使用されるキャリー語ｃｊ，１は、結果ｒｊ，ｉ（長さがｍビット）のｋ／ｍ（＝４）倍の大きさ（長さが４ｍビット）になる。
３．上記の最後のステップ（ｖｉ）は、（先行する中間結果からの対応する項）ｚ語及びキャリー語のｋ／ｍ（＝４）加算から構成される。全ての加算において、キャリー語はｍビットだけ低次元化される。
【００２４】
従って基本動作において全てのインデックスが省略され、
Ｂ．ｃ＋ｒ＝ｘ．ｙ＋ｃ＋ｚ
となる。
ここで、第一の動作の間、ｃ＝０、
第一のｋ／ｍ動作の間、ｚ＝０、
最後のｋ／ｍ動作の間、ｙ＝０
となる。
【００２５】
Ｒｊの各々の計算に対する全列の動作の間、ｘは一定に保持される。各々の中間結果Ｒｊに対する反復計算を通じてｘ語の値が一定に保持されるという事実は、Ｎを法としたＸ及びＹの長語乗算（ｌｏｎｇ  ｗｏｒｄ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ）を実行するために必要とされる処理電力をかなり低減するために使用され得る。
【００２６】
３２ビット乗算によって従来の３２ビットを実行する場合、３２積、キャリー、及びＺ項を加算することが必要とされる。それ故に、長さが各々３２ビットになる３４項の加算がもたらされる。このような加算は、高速で実行される場合、多くの電力を必要とする。
【００２７】
上記のアルゴリズムにおいて各々の中間項Ｒｊに対して、乗算項（ｍｕｌｔｉｐｌｉｃａｎｔ）（すなわちｘ）の一つが列（シリーズ（ｓｅｒｉｅｓ））全体を通じて一定に保持されることは注意されるであろう。
【００２８】
それ故にＲｊに対して計算が開始される前に、ｘｎ−ｊ＋１の複数の倍数（多項）（ｍｕｌｔｉｐｌｅ）が前計算（ｐｒｅ−ｃａｌｃｕｌａｔｅ）され、記憶されるか、又はラッチされる。上記の例に戻ると、６４ビット語（ｘ）に断片化される長語Ｘ、及び１６ビット語（ｙ）に分割されるＹに対してこのことは、複数の異なる設計による前計算回路を使用してもたらされてもよい。第一の例において前計算回路１０は、各々の行（又は列）アドレスで記憶されるｘの各々の可能な倍数で前ロード（プレロード（ｐｒｅ−ｌｏａｄ））されるルックアップテーブル１１を有していてもよい。ルックアップテーブルは、適切な加算回路を使用して占められ得る。ルックアップテーブルはそれから、適切な読み出し行（又は列）アドレスを使用することによって各々のｘ．ｙ倍数に対してアクセスされる。
【００２９】
しかしながら、全ての可能なｘ．ｙ積（ｙ語が１６ビットである場合、全ての積に対して６５５３６存在する）でルックアップテーブルを占める場合、このような構成は非効率となる。
【００３０】
好ましい技術は、ｘの選択された基本倍数を計算すると共に記憶し、ｘの選択された基本倍数からの適切なシフト（桁送り（ｓｈｉｆｔ））動作、及び／又は加算動作によって動作中（ｏｎ  ｔｈｅ  ｆｌｙ）の全ての他のｘの値を決定する前計算回路を使用することにある。
【００３１】
１６ビットｙ語による６４ビットｘ語の全ての倍数を前計算するのに適しているこのような前計算回路の例が図１に示されている。
【００３２】
前計算回路１０は  
前選択（ｐｒｅ−ｓｅｌｅｃｔｅｄ）されたｘの基本倍数を記憶するための（ひとまとめにしてレジスタ２０として示されている）六つのレジスタ２１乃至２６と、
前決定（ｐｒｅ−ｄｅｔｅｒｍｉｎｅｄ）されたｘの基本倍数を得るための（ひとまとめにして入力加算器３０として示されている）二つの加算器３１及び３２と、
前選択されたｘの基本倍数の計算の間、入力加算器３１及び３２に入力をもたらすための（ひとまとめにして入力マルチプレクサ４０として示されている）三つのマルチプレクサ４１、４２、及び４３と、
前選択されたｘの基本倍数を調整（位置合わせ）（アライン（ａｌｉｇｎ））するための（ひとまとめにしてビットシフタ５０として示されている）七つのビットシフタ５１乃至５７と、
適切なｘの基本倍数を出力として選択するための（ひとまとめにしてマルチプレクサ６０として示されている）四つの出力マルチプレクサ６１乃至６４と、
得られた所望のｘ．ｙ積にｘの出力倍数を結合するための出力加算器７０と   
を含んでいる。
【００３３】
レジスタ２０の各々は前選択されたｘの基本倍数を記憶する。レジスタ２１は値１ｘを記憶する。レジスタ２３は、入力マルチプレクサ４１及び４２を介して１ｘと２ｘとを結合する入力加算器３１によってもたらされる値３ｘを記憶する。レジスタ２２は、入力マルチプレクサ４１及び４２を介して３ｘと２ｘとを結合する加算器３１によってもたらされる５ｘの値を記憶する。倍数７ｘは、通常入力マルチプレクサ４１及び４２からの４ｘと３ｘとの結合によって入力加算器３１から直接もたらされ、一つのレジスタが節減される。レジスタ２４は、入力マルチプレクサ４３を介して８ｘと１ｘと（８ｘ＋１ｘ）を結合する入力加算器３２によってもたらされる９ｘの値を記憶する。レジスタ２５は、入力マルチプレクサ４３からの３ｘと８ｘとの結合によって入力加算器３２によってもたらされる１１ｘの値を記憶する。レジスタ２６は、入力マルチプレクサ４３を介して５ｘと８ｘとを結合する入力加算器３２によってもたらされる１３ｘの値を記憶する。倍数１５ｘは、通常（加算器３１からの）７ｘと８ｘとの結合によって入力加算器３２から直接もたらされ、他のレジスタが節減される。
【００３４】
偶数値は、ビットシフト機能部５０のうちの適切な一つを使用して適切な基本倍数レジスタ２０の単なる左シフトから得られることが可能なため、何れのレジスタにも記憶される必要がない。具体的には２ｘは１ｘレジスタ２１のコンテンツの１ビット左シフトによって得られ、４ｘは１ｘレジスタ２１のコンテンツの２ビット左シフトによって得られ、６ｘは３ｘレジスタ２３の１ビット左シフトによって得られ、８ｘは１ｘレジスタ２１のコンテンツの３ビット左シフトによって得られ、１０ｘは５ｘレジスタ２２のコンテンツの１ビット左シフトによって得られ、１２ｘは３ｘレジスタ２３の２ビット左シフトによって得られ、１４ｘは加算器３１の出力の１ビット左シフトによって得られる。これらのビットシフト機能部は、マルチプレクサ６０の入力部に対するレジスタ２０の適切な配線（ワイヤリング（ｗｉｒｉｎｇ））によって実現され得る。
【００３５】
従って全体として、基本倍数に対するレジスタの数（又はメモリ空き容量（ｍｅｍｏｒｙ  ｓｐａｃｅ））は１６からちょうど６に低減されている。好ましい装置においてｘレジスタ２１、ｎｘレジスタ２２、及びｍｘレジスタ２６はフリップフロップとして実現される一方、他のレジスタ２３、２４、及び２５はラッチとなる。
【００３６】
これらのｘの１６の基本倍数は、四つの出力マルチプレクサ６０によって出力部に対して選択され、各々のマルチプレクサは、選択入力部６６として１６ビットのｙ値の四つの各ビットを受信する。示されるように出力マルチプレクサ６１はｙ語の四つの最下位ビット（ｌｅａｓｔ  ｓｉｇｎｉｆｉｃａｎｔ  ｂｉｔ）（３：０）を受信し、出力マルチプレクサ６２はｙ語の次の四つの上位（重要）ビット（７：４）を受信し、出力マルチプレクサ６３はｙ語の次の四つの上位ビット（１１：８）を受信し、出力マルチプレクサ６４はｙ語の四つの最上位ビット（１５：１２）を受信する。出力マルチプレクサ６０の（ひとまとめに出力６７として示されている）各出力Ｐ０、Ｐ１、Ｐ２、及びＰ３は、出力の正確な相対的重み（ｓｉｇｎｉｆｉｃａｎｃｅ）をもたらすために互いに対してそれぞれシフトされる。特にマルチプレクサ６１はｘ．ｙ積のビット（６７：０）としてＰ０を供給し、マルチプレクサ６２はｘ．ｙ積のビット（７１：４）としてＰ１を供給し、マルチプレクサ６３はｘ．ｙ積のビット（７５：８）としてＰ２を供給し、マルチプレクサ６４はｘ．ｙ積のビット（７９：１２）としてＰ３を供給する。当然のことながらこれらの出力の各々は、ｘ．ｙに対する正確な値を得るために加算器７０によって結合されなければならない。
【００３７】
出力Ｐ０．．．Ｐ３の組み合わせは好ましくは加算器７０において、値ｚ（先行する中間結果からの対応する項）及び先行する項からのキャリー語ｃと同時に共に加算され、結果ｒ及び新たなキャリーｃが得られる。
【００３８】
前計算回路又はルックアップテーブルは、０、ｘ．．．１５ｘの範囲を有するｘの倍数をもたらさなければならない。図２に関して、図１の前計算回路は、４クロックサイクル内に全てのｘの基本倍数を生成し得ることが理解されるであろう。
【００３９】
第一のサイクルの開始で、新たなｘ値が１ｘレジスタにクロックにより入力される。第一のサイクルの間、ｎｘ加算器３１はｘ及び２ｘに接続され、ｍｘ加算器３２はｘ及び８ｘに接続される。第二のサイクルの開始で、結果３ｘ＝ｘ＋２ｘがｎｘレジスタ２２に記憶され、結果９ｘ＝ｘ＋８ｘがｍｘレジスタに記憶される。
【００４０】
第二のサイクルへの移行で、３ｘはｎｘレジスタ２２から３ｘレジスタ２３に転送され、９ｘはｍｘレジスタ２６から９ｘレジスタ２４に転送される。サイクル２の間、ｎｘ加算器３１はｘ及び４ｘに接続され、ｍｘ加算器３２はｎｘレジスタ２２及び８ｘに接続されるので、加算器３１及び３２はそれぞれ５ｘ＝ｘ＋４ｘ及び１１ｘ＝３ｘ＋８ｘを計算する。
【００４１】
第三のサイクルへの移行で、結果５ｘはｎｘレジスタ２２に記憶され、１１ｘはｍｘレジスタ２６に記憶される。第三のサイクルの第一の部分の間、９ｘはｍｘレジスタ２６から９ｘレジスタ２４に転送される。第三のサイクルの間、ｎｘ加算器３１は３ｘ及び４ｘに接続され、ｍｘ加算器３２はｎｘ及び８ｘに接続されるので、加算器３１及び３２はそれぞれ７ｘ＝３ｘ＋４ｘ及び１３ｘ＝５ｘ＋８ｘを計算する。
【００４２】
第四のサイクルの間、ｍｘ加算器３２はｎｘ加算器３１の出力部及び８ｘに接続されるので、ｍｘ加算器３２は１５ｘ＝７ｘ＋８ｘを計算する。加算器（７ｘ及び１５ｘ）の出力は記憶されず、出力マルチプレクサ６０に対する直接の入力として使用される。
【００４３】
好ましくは最適効率のために、中間結果Ｒｊの計算の最終部分の間、１６のｘの倍数を生成するために使用される四つのクロックサイクルが費やされる。この場合、累積和計算における最終項がｘ．ｙ積の使用を必要とせず、（最終項に対してｘ＝０となるため）ｚ及びｃ項しか加算されないことは注意されるであろう。この期間の間、マルチプレクサ６０の出力Ｐ０．．．Ｐ３は、例えば各々の場合、‘０’入力の選択によってゼロにドライブ（駆動）されなければならない。
【００４４】
上記の記載から、前計算回路の構成体は複数の態様で変更されることも可能であることが明らかとなるであろう。例えばマルチプレクサの数が８まで増加され、それぞれはｙ語の２ビット入力を受信することが可能である。同様にｙ語の３ビット入力を使用することにより、五つのマルチプレクサ及び一つの通常論理積（ｎｏｒｍａｌ  ａｎｄ−ｐｒｏｄｕｃｔ）が必要とされる。
【００４５】
通常前計算回路は、各々がｘの基本倍数を受信すると共に、各々が、ｙ語の選択ビットを受信するための選択線（ライン）と、各々のマルチプレクサからの出力を受信すると共に、各マルチプレクサ選択線に対する入力として使用されるｙ語の部分の数の重みに従って当該出力を結合させるための総和（加算）回路（ｓｕｍｍａｔｉｏｎ  ｃｉｒｃｕｉｔ）とを有する複数のマルチプレクサを使用する。
【００４６】
図３に関して、出力マルチプレクサ１６０の代わりの形態が示されている。図１の実施例において使用されている出力マルチプレクサ６０の形式に対してもたらされ得る不利点は、出力部が選択されていないとき、すなわち各々のマルチプレクサ６１．．．６４のたった一つの出力部しか一度に必要とされないとき、更に多くの場合、出力部が特定のマルチプレクサから全く必要とされないときにさえ、マルチプレクサはスイッチされることにある。例えば１１ｘから１２ｘにスイッチされるとき、マルチプレクサ６１の出力部しか変化させられないであろう。マルチプレクサ６２、６３、及び６４は依然ゼロ出力を必要としているであろう。各々のマルチプレクサのスイッチングにより、不必要な電力消費がもたらされる。それ故にマルチプレクサ１６０の代わりの構成体が図３に示される。
【００４７】
基本倍数ｘ．．．１５ｘの各々が入力としてもたらされ、各選択線Ｓ１．．．Ｓ１５によって選択される。必要なｘの基本倍数は、論理ゲート１６１．．．１６７によって選択される（更に必要ならば部分的に加算される）。論理ゲート１６１．．．１６７からの出力は加算器１７１及び１８１によっても加算され、最終出力ｘ．ｙが出力部１９０に生成される。この構成体において、選択入力が変化するとき、影響を受けた論理ゲート１６１．．．１６７しかスイッチされないであろう。例えば必要とされるｘ倍数が１ｘから５ｘに変化するとき、論理ゲート１６１及び１６３しかスイッチされない。ゲート１６２及び１６４．．．１６７の全ての他の入力部及び出力部はスイッチされないことにより、低減された消費電力がもたらされる。制御入力部におけるいかなる所与の変化に対しても最少数の論理ゲートしかスイッチされない。
【００４８】
それ故に通常、複数の出力マルチプレクサは、各々が、ｘの各基本倍数を受信するように接続される第一の入力部ｘｉと、論理ゲートの出力部における基本倍数の活性化（アクティブ化（ａｓｓｅｒｔｉｏｎ））を可能にする選択線Ｓｉとを有する一組（１セット）の論理ゲート１６１．．．１６７を有することが認識されるであろう。総和回路は、論理ゲートの列の全ての活性化された出力を受信すると共に、マルチプレクサ選択線に対する入力として使用されるｙ語の部分の数の重みに従って当該出力を結合させるための（部分的に各々の論理回路１６１．．．１６７と回路１７１及び１８１とでの）一組の加算器を有する。
【００４９】
四つの積Ｐ０．．．Ｐ３とｚ項とキャリー項ｃとを加算する加算器７０の好ましい構成体は、図４に概略的に示されているように、キャリー保留加算器（キャリーセーブアダー（ｃａｒｒｙ−ｓａｖｅ−ａｄｄｅｒ））型となる。
【００５０】
全加算器（フルアダー（ｆｕｌｌ  ａｄｄｅｒ））によって最下位１６ビット（Ｒ（１５：０））のみが加算される。このことは、二つのフィードバック項Ｃｃ’及びＣｓ’が加算されなければならないことを意味する（キャリーは両方の和となる）。これらの項は、１６ビットに渡るシフト後に加算される。
【００５１】
実際Ｃｃ’（７８：０）及びＣｓ’（７８：０）は、フリップフロップに記憶される。次のクロックサイクルにおいて、より上位の部分（Ｃｃ’（７８：１６）及びＣｓ’（７９：１６））は、矢印によって示されているようにＣｃ（６２：０）及びＣｓ（６２：０）として加算器に入力される。Ｃｃ’（１５：０）及びＣｓ’（１５：０）は、先行するキャリービットｃｉ＝Ｒ（１６）と共に全加算器によって加算され、その結果Ｒ（１６：０）となる。
【００５２】
Ｒ（１５：０）は好適なメモリ、例えばＲＡＭに連続的に記憶される。Ｒ（１６）はｃｉとして次のクロックサイクルにおいて加算される。
【００５３】
中間結果ＲｊからのＺ（１５：０）は好適なメモリ、例えばＲＡＭに連続的に記憶され、メモリから各々の対応する命令（ｏｐｅｒａｔｉｏｎ）に対して読み出される。      
【図面の簡単な説明】
【００５４】
【図１】ｘの選択された基本乗算からｘ．ｙ積を生成する乗算器のための前計算回路を示す。
【図２】図１の回路の動作に対するタイミング図を示す。
【図３】図１に示されている回路を置換するように設計される代わりの乗算器／加算器回路を示す。
【図４】加算器の好ましい構成体を概略的に示す。
【図１】
2006508464.tif 000005
【図２】
2006508464.tif 000006
【図３】
2006508464.tif 000007
【図４】
2006508464.tif 000008
【国際調査報告】
2006508464.tif 000009
2006508464.tif 000010
2006508464.tif 000011