(57)【特許請求の範囲】
【請求項１】
ガロア体ＧＦ（２ｍ＊ｐ）からの第一の係数（ファクタ）と第二の係数（ファクタ）とを乗算するための方法であって、これら係数が各々ｍビット幅を有するｐ個の上位又は下位のサブブロックのベクトルとして表され、ｐとｍは１より大きな正の整数を表し、この方法が、制御ユニットによって、：
ａ）非零の先頭ビットと各々がｍビットを有するｐ個のこれに続くサブブロックとを含み、各々がｍビットを有するこれらｐ個のサブブロックの内のｒ個の下位サブブロックは任意的に非零ベクトルとして選択され、他のサブブロックは零ベクトルとして選択される（ここでｒはｐより小さな正の整数を表す）一つの簡約多項式を選択し、その簡約多項式のこれらｒ個の下位サブブロックを第一のレジスタ内に格納するステップと、
ｂ）前記第一の係数のサブブロックと前記第二の係数のサブブロックとを、前記第一の係数の最上位サブブロック及び前記第二の係数の最上位サブブロックとから開始して順番に、前記第一の係数の全てのサブブロックと前記第二の係数の全てのサブブロックとを乗算するステップと、
ｃ）前記第一と第二の係数のサブブロックの乗算的連結の全ての中間結果を、桁上げを伴うことなく、排他的論理和に従って桁整合して累積するステップと、
ｄ）前記第一の係数のあるサブブロックと前記第二の係数のあるサブブロックの各乗算的連結の後に、少なくとも前記第一の係数の一つのサブブロックと前記第二の係数の全てのサブブロックとの乗算的連結の中間結果の累積の後に、前記簡約多項式を用いて候補累積中間結果をｍビット幅となるまで簡約するステップとを含み、この簡約ステップが：
ｄ１）簡約されるべき候補累積中間結果を供給するサブステップと、
ｄ２）前記簡約多項式の少なくとも一つのサブブロックを供給するサブステップと、
ｄ３）前記簡約多項式と前記簡約されるべき候補累積中間結果の上位ｍビットとを乗算し、最上位ビットの値が前記簡約されるべき候補累積中間結果の最上位ビットの値に対応する減算されるべき多項式を得るサブステップと、
ｄ４）前記減算されるべき多項式を前記簡約されるべき候補累積中間結果から減算し、この減算の結果を新たな簡約されるべき候補累積中間結果として供給するサブステップと、
ｄ５）前記サブステップｄ１）〜ｄ４）の実行を前記候補累積中間結果の幅がｍとなるまで反復するサブステップとを含む、ことを特徴とする方法。
【請求項２】
ガロア体ＧＦ（２ｍ＊ｐ）からの第一の係数（ファクタ）と第二の係数（ファクタ）とを乗算するための乗算器であって、これら係数が各々ｍビット幅を有するｐ個の上位又は下位のサブブロックのベクトルとして表され、ｐとｍは１より大きな正の整数を表し：
簡約多項式の、各々がｍビットから成るｒ個の下位サブブロック（ここで、ｒはｐより小さな正の整数を表す）のベクトルとして表される、乗算されるべき前記係数、及びこれら係数の乗算の簡約最終結果を格納するためのメモリユニットと、
毎回、前記係数の前記サブブロックの二つを乗算的に連結し、２ｍビットなる幅を有する乗算結果を出力するためのｍ＊ｍビット乗算器段と、
毎回、乗算的に連結されるべき前記サブブロックの一つを格納及び供給するための第一及び第二のサブブロックメモリと、
少なくとも一つの中間結果を格納するための第一の中間結果メモリと、
各乗算結果のｍ個の最上位ビットを、排他的論理和に従って、前記第一の中間結果メモリからの桁整合された選択された中間結果及び第一のマルチプレクサ段を介して選択された要素（元）と連結するための第一の排他的論理和リンク段と、
各乗算結果のｍ個の最下位ビットを、排他的論理和に従って、第二のマルチプレクサ段を介して選択された要素（元）と連結するための第ニの排他的論理和リンク段と、
前記第二の排他的論理和リンク段から出力される連結結果を格納するための第二の中間結果メモリと、
前記簡約多項式のｒ個の最下位サブブロックを格納及び供給するための簡約多項式メモリと、
前記第一或いは第二の排他的論理和リンク段から出力される連結結果の一つを、前記メモリユニットに加えられるべき前記係数の乗算の簡約最終結果のサブブロックとして一時的に格納するための出力レジスタと、
第一或いは第二の排他的論理和リンク段から出力された連結結果或いは前記メモリユニットからの選択されたサブブロックをオプションとして前記簡約多項式メモリ、前記第一の中間結果メモリ或いは前記出力レジスタに加えるための第三のマルチプレクサ段と、
前記簡約多項式メモリからの簡約多項式のサブブロック或いは前記メモリユニットからの前記第二の係数のサブブロックをオプションとして前記第二のサブブロックメモリに供給するための第四のマルチプレクサ段と、
前記乗算器の前記コンポーネントを所定の関数系列に従って制御するための制御ユニットとを含み、
前記第一のマルチプレクサ段と前記第二のマルチプレクサ段が、各々、前記第二の中間結果メモリの現在の連結結果と同一幅の零ベクトルのいずれかを選択することを特徴とする乗算器。
【請求項３】
前記第一の排他的論理和リンク段から出力される連結結果に合うような寸法にされたメモリセクションの入力が直接に前記第一の排他的論理和リンク段の出力に接続され、このメモリセクションの一つの出力が第五のマルチプルクサ段の一つの入力に接続され、この第五のマルチプルクサ段を介して前記第一の排他的論理和リンク段から出力された連結結果或いは第一の中間結果メモリからの別の中間結果がオプションとして前記第一の排他的論理和リンク段に加えられることを特徴とする請求項２記載の乗算器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ガロア体ＧＦ（２ｍ＊ｐ）からの二つの係数を乗算するための方法に関する。ここで、これら係数は各々ｍビットなる幅を有するｐ個のサブブロックのベクトルとして表現され、ｐとｍは１より大きな正の整数を表す。本発明はさらにこの方法を遂行するための乗算器にも係る。
【０００２】
【従来の技術】
楕円曲線は公開鍵を用いる暗号法の性能に適することが証明されている。暗号法に楕円曲線を用いることの長所は、同等な安全性に対して、公開鍵の長さをいわゆるＲＳＡ法を用いたときの鍵の長さよりも大幅に短縮できることである。このため、メモリ空間を節約できることに加えて、暗号化に関するデータスループットは一般的に鍵の長さの増加と共に劣化するためにデータスループットを大幅に向上することができる。
【０００３】
国際特許出願ＷＯ９６／３０８２８は、一対のｍ-セルシフトレジスタと一つのｍ-セル累積セルから形成されるガロア体ＧＦ２ｎｍに対する有限体乗算器を開示する。この乗算器は、各シフトレジスタ内の部分体元のベクトルを保持するために、これらセル内にその累積セルに関するグループ化された項を生成するための論理リンクを備える。各セルは、一つの部分体元を各々が一つの二進数を格納するｎ個の部分セルの形式にて含む。これら論理リンクは固有の部分体演算に従って演算動作を遂行し、累積レジスタの各セル内にｎ個の二進数から成る一つの部分体元を生成する。この乗算器は、２個のベクトルの積をｍ個のクロックサイクルにて生成する。個々のレジスタ間の写像により一つのベクトルが１クロックサイクルをかけて二乗される。
【０００４】
２個の２数を乗算すると、結果として長さは二倍となる。つまり、ビットの数は二倍となる。暗号化において要求されるように、より長い数の乗算においては、このために非常に長い結果が生成され、非常に多くのメモリ空間が要求されることとなる。
【０００５】
【発明が解決しようとする課題】
ガロア体からの元の乗算は、整数の２数の乗算とは、従来のマイクロプロセッサによる整数の乗算においては剰余クラス環が用いられるが、ガロア体においては数学上の体が用いられる点で異なる。ガロア体に関する乗算は、正規ベースと多項式ベースに基づいて遂行することができる。後者は国際特許出願ＷＯ／３０８２８に開示される乗算器の機能に対するベースでもある。このような多項式ベース（基底）に基づく乗算は、以下では簡単に多項式乗算と呼ばれるが、従来のマイクロプロセッサで遂行された場合は、非常に時間がかかり、非常に非効率となる。さらに、このような多項式乗算が暗号過程において非常に頻繁に要求される場合は、暗号過程の実行に望ましくない遅延が導入されることとなる。
【０００６】
本発明の目的は、上述の多項式乗算を、最小限のメモリ要件にて、迅速かつ効率的に遂行することができる方法及び乗算器を提供することにある。
【０００７】
【課題を解決するための手段】
上記目的を達成するために、本発明の第１の態様によるガロア体ＧＦ（２ｍ＊ｐ）からの二つの係数（ファクタ）を乗算するための方法は、これら係数が各々ｍビット幅を有するｐ個のサブブロックのベクトルとして表され、ｐとｍは１より大きな正の整数を表し、この方法が：
ａ）非零の先頭ビットと各々がｍビットを有するｐ個のこれに続くサブブロックとを含み、各々がｍビットを有するこれらｐ個のサブブロックの内のｒ個の下位サブブロックは任意的に非零ベクトルとして選択され、他のサブブロックは零ベクトルとして選択される（ここでｒはｐより小さな正の整数を表す）一つの簡約多項式を選択し、その簡約多項式のこれらｒ個の下位サブブロックを第一のレジスタ内に格納するステップと、
ｂ）前記第一の係数のあるサブブロックをその第一の係数の最上位サブブロックから開始して順番に、前記第二の係数の全てのサブブロックとその第二の係数の最上位サブブロックから開始して、乗算的に連結するステップと、
ｃ）前記第一と第二の係数のサブブロックの乗算的連結の全ての中間結果を、桁上げを伴うことなく、排他的ＯＲファンクションに従って桁整合して累積するステップと、
ｄ）前記第一の係数のあるサブブロックと前記第二の係数のあるサブブロックの各乗算的連結の後に、少なくとも前記第一の係数の一つのサブブロックと前記第二の係数の全てのサブブロックとの乗算的連結の中間結果の累積の後に、前記簡約多項式を用いて候補累積中間結果をｍビット幅となるまで簡約するステップとを含み、この簡約ステップが：
ｄ１）簡約されるべき中間結果を供給するサブステップと、
ｄ２）前記簡約多項式の少なくとも一つのサブブロックを供給するサブステップと、
ｄ３）前記簡約多項式と簡約されるべき候補累積中間結果の上位ｍビットとを乗算し、最上位ビットの値が簡約されるべき前記中間結果の最上位ビットの値に対応する減算されるべき多項式を得るサブステップと、
ｄ４）前記減算されるべき多項式を前記簡約されるべき中間結果から減算し、この減算の結果を新たな簡約されるべき中間結果として供給するサブステップと、
ｄ５）前記サブステップｄ１）〜ｄ４）の実行を前記中間結果の幅がｍとなるまで反復するサブステップとを含む、ことを特徴とする。
【０００８】
また、本発明の第２の態様によるガロア体ＧＦ（２ｍ＊ｐ）からの二つの係数を乗算するための乗算器は、これら係数が各々ｍビット幅を有するｐ個のサブブロックのベクトルとして表され、ｐとｍは１より大きな正の整数を表し：
簡約多項式の、各々がｍビットから成るｒ個の下位サブブロック（ここで、ｒはｐより小さな正の整数を表す）のベクトルとして表される、乗算されるべき前記係数、及びこれら係数の乗算の簡約最終結果を格納するためのメモリユニットと、
毎回、前記係数の前記サブブロックの二つを乗算的に連結し、２ｍビットなる幅を有する乗算結果を出力するためのｍ＊ｍビット乗算器段と、
毎回、乗算的に連結されるべき前記サブブロックの一つを格納及び供給するための第一及び第二のサブブロックメモリと、
少なくとも一つの中間結果を格納するための第一の中間結果メモリと、
各乗算結果のｍ個の最上位ビットを、排他的論理和に従って、前記第一の中間結果メモリからの桁整合された選択された中間結果及び第一のマルチプレクサ段を介して選択された要素（元）と連結するための第一の排他的論理和リンク段と、
各乗算結果のｍ個の最下位ビットを、排他的論理和に従って、第二のマルチプレクサ段を介して選択された要素（元）と連結するための第ニの排他的論理和リンク段と、
前記第二の排他的論理和リンク段から出力される連結結果を格納するための第二の中間結果メモリと、
前記簡約多項式のｒ個の最下位サブブロックを格納及び供給するための簡約多項式メモリと、
前記第一或いは第二の排他的論理和リンク段から出力される連結結果の一つを、前記メモリユニットに加えられるべき前記係数の乗算の簡約最終結果のサブブロックとして一時的に格納するための出力レジスタと、
第一或いは第二の排他的論理和リンク段から出力された連結結果或いは前記メモリユニットからの選択されたサブブロックをオプションとして前記簡約多項式メモリ、前記第一の中間結果メモリ或いは前記出力レジスタに加えるための第三のマルチプレクサ段と、
前記簡約多項式メモリからの簡約多項式のサブブロック或いは前記メモリユニットからの前記第二の係数のサブブロックをオプションとして前記第二のサブブロックメモリに供給するための第四のマルチプレクサ段と、
前記乗算器の前記コンポーネントを所定の関数系列に従って制御するための制御ユニットとを含み、
前記第一のマルチプレクサ段と前記第二のマルチプレクサ段が、各々、前記第二の中間結果メモリの現在の連結結果と同一幅の零ベクトルのいずれかを選択することを特徴とする。
【０００９】
なお、前記第一の排他的ＯＲリンク段から出力される連結結果に合うような寸法にされたメモリセクションの入力が直接に前記第一の排他的ＯＲリンク段の出力に接続され、このメモリセクションの一つの出力が第五のマルチプルクサ段の一つの入力に接続され、この第五のマルチプルクサ段を介して前記第一の排他的ＯＲリンク段から出力された連結結果或いは第一の中間結果メモリからの別の中間結果がオプションとして前記第一の排他的ＯＲリンク段に加えられるように構成しても良い。
【００１０】
また、本発明による方法は多項式乗算器に基づく。本発明による乗算器は、ｎ＊ｎビットに対する多項式乗算器から成り、ここで、ｎはパラメータｐとｍの積から成る。好ましくは、データの暗号化或いは復号化用のマイクロプロセッサ制御装置においては、このような乗算器が従来の構造のマイクロプロセッサに対する外部要素として設けられ、こうして暗号化或いは復号化の際に遂行されるべきガロア体からの係数の乗算はマイクロプロセッサの外部で遂行される。これによって暗号化或いは復号化過程を大幅に高速化することが可能となる。さらに、簡約多項式を用いて絶えず簡約を遂行することでメモリ空間も節約される。本発明による乗算器の核となる要素は、連結ネットワークとしても知られるｍ＊ｍビット乗算器段から成る。個々の乗算ステップの、全体でｐ＊ｐ個の数から成る結果は、本発明による乗算器によってガロア体内で排他的論理和リンク段を用いて総和される。
【００１１】
【発明の実施の形態】
以下では本発明を図面に示される実施例との関連で説明するが、本発明はこれに制限されるものではない。
【００１２】
図１は、本発明による、各々がｎビットなる幅を有する二進数ＸとＹとして表される二つの係数を乗じるための多項式乗算器の第一の実施例を示す。本発明によるこの多項式乗算器は独立に機能する。つまり、この乗算器に外部要素として追加される従来の構成のマイクロプロセッサのプログラム制御を必要とすることなく、指定される関数系列に従ってこの乗算器を制御するための自身の制御ユニット１８を有する。この乗算器によって遂行される多項式乗算は多項式ベースにて遂行される。計算は係数ＸのサブブロックＸ（ｐ），Ｘ（ｐ-１）…，Ｘ（１）と係数ＹのサブブロックＹ（ｐ），Ｙ（ｐ-１）…，Ｙ（１）を用いて別個のステップにて遂行され、これらサブブロックは各々ｍビット幅を有し、係数Ｘ，Ｙの幅ｎは、幅ｍ、係数ｐに対して、ｐ＝ｎ／ｍなる関係を有するような整数の倍数を表す。一つの好ましい実施例においては、
ｎ＝１９２ビット、ｍ＝３２ビット、ｐ＝６とされる。
【００１３】
本発明による乗算器においては、遂行された多項式乗算の結果は自動的にｎビット幅に簡約され；この目的のためには、後により詳細に説明するように、簡約多項式が用いられる。
【００１４】
図１の参照符号１はメモリユニットを示す。メモリユニットは、好ましくは、ｍビットなるワード幅を有するＲＡＭとして形成される。つまり、この中に格納されるデータは各々がｍビットから成るサブブロックにアセンブルされる。メモリユニット１は、接続２１を介して、データ及び／或いはプログラムを交換するためのＣＰＵとしても知られる中央処理ユニット２０に接続される。この中央処理ユニット２０を介してメモリユニット１内に格納されているデータを処理するためのプログラムを実行することもできる。ただし、ガロア体からの二つの係数を乗算するためには、この中央処理ユニットは用いられない。この目的のためには、メモリユニット１は、代りに、以下に説明される装置に直接に接続される。
【００１５】
この装置は、中心的な要素として、毎回、乗算器段９の二つの入力２２，２３に加えられる、ワード幅ｍとしても言及される、幅ｍの二つのサブブロックを乗算的にリンクするためのｍ＊ｍビット乗算器段９を備える。乗算器段９の二つの出力２４，２５の所にはこの乗算結果が供給される。上位ビットは乗算器段９の第一の出力２４の所に出力され、下位ビットは第二の出力２５の所に出力される。乗算器段９のこれら出力２４，２５もｍビットなるワード幅を有する。全体で２ｍビットなる幅を有するこれら乗算結果の各々は、たった一つの因子に過ぎず、多項式乗算の最終結果は、全部でｐ＊ｐ個のこのような因子を累積することで形成される。この累積は、本発明による乗算器のこの実施例においては、後に説明するように、排他的論理和リンク段を用いて遂行される。
【００１６】
乗算器段９の入力２２，２３は、それぞれ、第一のサブブロックメモリ７と第二のサブブロックメモリ８に接続される。これらサブブロックメモリ７，８内には、乗算器段９内で乗算的に互いに連結されるべきワード幅ｍのサブブロックが格納及び準備される。乗算器段９の第一の出力２４は、最上位ビットＭＳＢに対するライン１０を介して、第一の排他的論理和リンク段１２の第一の入力２６に接続される。乗算器段９の最下位ビットＬＳＢに対する第ニの出力２５は、ライン１１を介して、第ニの排他的論理和リンク段１３の第一の入力２９に接続される。これら排他的論理和リンク段１２，１３は、遂行されるべき多項式乗算に対する加算器として用いられる。
【００１７】
第一の排他的論理和リンク段１２の第二の入力２７は、第一のマルチプレクサ段１４の出力３３に接続される。この接続もｍビットなるワード幅に合わせた寸法にされる。第ニの排他的論理和リンク段１３の第二の入力３０は、ｍビットなるワード幅に対して設計された接続を介して、第ニのマルチプレクサ段１５の出力３６に接続される。第ニの排他的論理和リンク段１３の出力３８は、第二の中間結果メモリ１６の入力３９に接続される。この接続もｍビットなるワード幅に合わせて設計される。第二の排他的論理和リンク段１３のリンク結果は、この第二の中間結果メモリ１６内に一時的に格納され、第二の中間結果メモリ１６の出力４０の所に供給される。第二の中間結果メモリ１６の出力４０からは、ｍビットなるワード幅に対する接続が、第一のマルチプレクサ段１４の第一の入力３１と、第ニのマルチプレクサ段１５の第一の入力３４に向かって延びる。第一のマルチプレクサ段１４の第ニの入力３２と、第ニのマルチプレクサ段１５の第ニの入力３５には、零ベクトル、つまり、零にセットされたｍビットの数が加えられる。それぞれ、排他的論理和リンク段１２，１３の第二の入力２７，３０には、遂行される計算動作に応じて、マルチプレクサ段１４，１５を介して、第二の中間結果メモリ１６の中間結果の出力４０、或いは上述の零ベクトルが加えられる。
【００１８】
第一の排他的論理和リンク段１２の出力３７は、ｍビットなるワード幅を有する接続を介して、第三のマルチプレクサ段２の第一の入力４１に接続される。第三のマルチプレクサ段２の第二の入力４２は、第二の中間結果メモリ１６の出力４０に接続される。第三のマルチプレクサ段２の第三の入力４３は、メモリユニット１のデータ出力４５に接続される。これら接続もｍビットなるワード幅に対して設計される。
【００１９】
第三のマルチプレクサ段２の出力４４からは、ｍビットなるワード幅の接続が、出力レジスタ５の入力４７、第一の中間結果メモリ３の入力４９、及び簡約多項式メモリ４に向かって存在する。出力レジスタ５は、第三のマルチプレクサ段２を介して、第一或いは第二の排他的論理和リンク段１２，１３から供給されるリンク結果を一時的に格納するために用いられる。このリンク結果は、出力レジスタ５とその出力４８を介して、メモリユニット１のデータ入力４６に、ガロア体の係数の乗算の簡約最終結果のサブブロックとして供給される。メモリユニット１のデータ出力４５と第三のマルチプレクサ段２の第三の入力４３の間の接続を介して、メモリユニット１からの選択されたサブブロックを第三のマルチプレクサ段２の出力４４の所の前述の接続に加えることもできる。第三のマルチプレクサ段２に加えられるこれら信号は、一時的に、第一の中間結果メモリ３、簡約多項式メモリ４、或いは出力レジスタ５内に格納される。
【００２０】
第一の中間結果メモリ３の出力５０からは、ｍビットなるワード幅を有する接続が、第一の排他的論理和リンク段１２の第三の入力２８と、第一のサブブロックメモリ７の入力５３に向かって延びる。第一のサブブロックメモリ７の出力５４は、ｍビットなるワード幅に対する接続を介して、乗算器段９の第一の入力２２に接続される。
【００２１】
簡約多項式メモリ４の出力５２からは、ｍビットなるワード幅に対する接続が第四のマルチプレクサ段６の第一の入力５５に向かって延びる。第四のマルチプレクサ段６の第二の入力５６は、ｍビットなるワード幅に対する接続を介して、メモリユニット１のデータ出力４５に接続される。第四のマルチプレクサ段６の出力５７も、ｍビットなるワード幅を有する接続を介して、第二のサブブロックメモリ８の入力５８に接続される。第二のサブブロックメモリ８の出力５９は、ｍビットなるワード幅を有する接続を介して、乗算器段９の第二の入力２３に接続される。
【００２２】
説明の装置によって遂行されるデータ処理ステップを制御するためには、制御ユニット１８が設けられる。制御ユニット１８は、制御ライン６０〜６５を介して、出力レジスタ５、第一の中間結果メモリ３、簡約多項式メモリ４、第一のサブブロックメモリ７、第二のサブブロックメモリ８及び第二の中間結果メモリ１６に接続される。制御ライン６０〜６５を介して制御コマンドがこれら段に加えられる。制御ユニット１８は、さらに、それぞれ、制御ライン６６〜６９を介して、第三のマルチプレクサ段２、第四のマルチプレクサ段６、第一のマルチプレクサ段１４、及び第ニのマルチプレクサ段１５に接続される。これら制御ライン６６〜６９を介して、これらマルチプレクサ段２，６，１４，１５は選択信号を受信し、これら選択信号に基づいて、毎回、これらマルチプレクサ段２，６，１４，或いは１５の複数の入力のどの一つがその出力にスイッチングされるべきか決定される。制御ユニット１８は、更に、コマンドライン７０を介して中央処理ユニット２０に接続される。中央処理ユニット２０は、このコマンドライン７０を介して、乗算を独立的に実行するコマンドを制御ユニット１８に与える。制御ユニット１８は、更に、このコマンドライン７０を介して、状態情報を、例えば、乗算が完了した後に、準備完了メッセージを中央処理ユニット２０に加えることもできる。
【００２３】
第一の中間結果メモリ３は、ｐ個のサブブロックの中間結果を中間結果メモリ３の、図１においてはシンボル的にＺ（ｊ）として示されるセクションに格納すると共に、３個のさらなるデータワード或いはサブブロックを、中間結果メモリ３の、図１においてシンボル的にＴ，ＸＩ，Ｃ１として示されるセクションに格納するように設計される。遂行されるべき多項式乗算に対するこれらサブブロックの重要性については後に説明される。
【００２４】
第一の中間結果メモリ３から、毎回、ここに格納されているサブブロックＺ（ｊ），Ｔ，ＸＩ或いはＣ１の一つが、出力５０を介して、ｍビットなる幅にて出力され、第一のサブブロックメモリ７の入力５３と、第一の排他的論理和リンク段１２の第三の入力の両方に加えられる。第一のサブブロックメモリ７において、こうして加えられたサブブロックは説明のように乗算器段９内での連結に対して準備される。このサブブロックは説明の第一のサブブロックメモリ７の出力５４から乗算器段９の第一の入力２２へと延びる、ｍビットなるワード幅を有する接続を用いて乗算器段９に加えれる。
【００２５】
メモリユニット１は、レジスタ、好ましくは、ＲＡＭとして設計され、少なくとも（２ｐ＋ｒ）＊ｍビットなるメモリ空間を有する。ここで、ｐは、各々がｍビット幅を有するサブブロックの数を表し、これら各サブブロックによって乗算されるべきガロア体ＧＦ（２ｍ＊ｐ）からの各係数を表すベクトルが形成され、ここで、ｐ，ｍは、１より大きな正の整数を表す。数ｒは、各々任意的に非零ベクトルにセットされる、ｍビットから成る、簡約多項式の下位サブブロックの数を表し、ここで、ｒはｐより小さな正の整数とされる。第一の中間結果メモリ３もレジスタとして設計され、（ｐ＋３）＊ｍビットなるメモリ空間を有し、この中間結果メモリ３のＴ，ＸＩ或いはＣ１として示されるセクションには、毎回、ｍビットが供給され、セクションＺ（ｊ）は、ｐ＊ｍビットなるメモリ空間を有する。簡約多項式メモリ４はｒ＊ｍビットなるメモリ空間を有するレジスタから形成される。出力レジスタ５、第一と第二のサブブロックメモリ７，８、及び第二の中間結果メモリ１６は、ｍビットなるメモリ空間を有する各々のレジスタから形成される。
【００２６】
本発明による乗算器のコアは、ｍ＊ｍビット乗算器段９から形成される。二つの係数ＸとＹの完全な乗算を行うためには、このｍ＊ｍビット乗算器段９を用いたて、全部でｐ＊ｐ個の因子がサブブロックＸ（ｉ）とＹ（ｊ）の積としてＸ（ｉ）＊Ｙ（ｊ）なる形式にて形成され、これらが遂行されるべき多項式乗算に対する加算器として用いられる排他的論理和リンク段１２，１３によって排他的論理和を介して累積される。
【００２７】
図１の回路装置の機能は以下の通りである。中央処理ユニット２０は、乗算されるべき二つの係数ＸとＹ及び前述の簡約多項式Ｒをメモリユニット１内に書き込む。簡約多項式Ｒは、非零の先頭のビットと、各々ｍビットの、ｐ個のこれに続くサブブロックＲ（ｐ），Ｒ（ｐ-１），…，Ｒ（１）を含む。後者の内の、各々がｍビットを有するＲ個の下位ブロックＲ（ｒ），Ｒ（ｒ-１），…，Ｒ（１）は、任意的に非零とされ、他のサブブロックＲ（ｐ），Ｒ（ｐ-１），…，Ｒ（ｒ＋１），Ｒ（ｒ）は零に選択される。ここで、ｒは、ｐより小さな正の整数を表す。この書込みプロセスによって、メモリユニット１内には、以下のサブブロック：Ｘ（ｐ），Ｘ（ｐ-１），…，Ｘ（２），Ｘ（１）；Ｙ（ｐ），Ｙ（ｐ-１），…，Ｙ（２），Ｙ（１）；及びＲ（ｒ），Ｒ（ｒ-１），…，Ｒ（２），Ｒ（１）が存在することとなるが、ここで、ｒは、ｐより小さく、１より大きいかこれに等しい。これらサブブロックは、その後のデータ処理手続きのためにメモリユニット１から、多項式乗算器によって、直接に読み出す、つまり、直接メモリアクセス（DMA）することができる。多項式乗算器を起動するためには、制御ユニット１８と中央処理ユニット２０の間のコマンドライン７０を介して乗算を独立的に実行するためのコマンドが制御ユニット１８に与えられる。
【００２８】
制御ユニット１８によって制御されると、図１による多項式乗算器においては、最初に、簡約多項式Ｒのｒ個のサブブロックＲ（ｒ），Ｒ（ｒ-１），…，Ｒ（２），Ｒ（１）が簡約多項式メモリ４内にロードされる。実際の簡約多項式Ｒは、全体では、常にｎ＋１ビットなる幅を有するが、メモリユニット１と簡約多項式メモリ４内には、これらの一部（セクション）のみ、つまり、非零ベクトルのｒ個のサブブロックＲ（ｒ），Ｒ（ｒ-１），…，Ｒ（２），Ｒ（１）のみが格納される。この目的のために、多項式乗算器は、先頭ビットは“１”と想定するが、この先頭の（ｎ＋１）番目のビット点は、メモリユニット１或いは簡約多項式メモリ４内には明示的には格納しない。上述のように、簡約多項式Ｒによって考慮されるサブブロックの数ｒ、つまり、このｒ個の非零ベクトルのサブブロックＲ（ｒ），Ｒ（ｒ-１），…，Ｒ（２），Ｒ（１）の数は、乗算されるべき係数ＸとＹのサブブロックＸ（ｉ）或いはＹ（ｊ）の数ｐより少くなる。一つの好ましい実施例においては、ｒ＝１或いはｒ＝２とされる。つまり、簡約多項式Ｒの、１或いは２個のサブブロックのみが考慮される。この寸法例においては、これらは、簡約多項式Ｒの、全体で（ｎ＋１）＝１９３ビットなる幅の内の、３２ビット或いは６４ビットに相当する。先頭の（ｎ＋１）番目のビット点の値は“１”にセットされ、他のビット点の値は“０”にセットされる。
【００２９】
第一の中間メモリ３は、以下に説明される計算の中間結果をＺ（ｊ）として示されるセクッション内に格納すると共に、３個のさならるサブブロック（「データワード」としても言及される）をＸＩ，Ｃ１及びＴとして示されるセクション内に格納する。これらサブブロック、或いはデータワードＸＩ，Ｃ１及びＴは、乗算結果の簡約のために用いられる。係数ＸとＹを乗算する過程の開始において、第一の中間結果メモリ３が“０”に初期化される。つまり、これらセクション内に格納されている全ての値が“０”にセットされる。
【００３０】
ｍ＊ｍビット乗算器段９内で互いに乗算されるべき係数Ｘの全てのサブブロックＸ（ｉ）を通じてランするためのランインデックスｉが最初に値ｐにセットされる：
ｉ：＝ｐ
上に定義された初期状態から開始して、次に、以下の計算ステップを用いてｐ回のランが遂行される：
１．ＸＩ：＝Ｘ（ｉ）を、メモリユニット１からデータ出力４５と第三のマルチプレクサ段２を介して第一の中間結果メモリ３のセクションＸＩ内にロードする。
【００３１】
２．ＸＩを第一のサブブロックメモリ７内にロードする。
【００３２】
３．ｊ：＝ｐにセットする。
【００３３】
４．Ｙ（ｊ）をメモリユニット１からデータ出力４５と第四のマルチプレクサ段６を介して第二のサブブロックメモリ８内にロードする。すると、ｍ＊ｍビット乗算器段９の出力２４，２５の所に係数ＸとＹのサブブロックＸ（ｉ）とＹ（ｊ）の乗算結果Ｘ（ｉ）＊Ｙ（ｊ）のＭＳＢとＬＳＢがさらなる処理のために供給される。
【００３４】
５．係数Ｘ、ＹのサブブロックＸ（ｉ）、Ｙ（ｊ）の乗算結果Ｘ（ｉ）＊Ｙ（ｊ）を第一の中間結果メモリ３のセクションＺ（ｊ）からの前の中間結果Ｚ（ｊ）に加える。これは、第一の中間結果メモリ３のセクションＴ内の乗算結果Ｘ（ｉ）＊Ｙ（ｊ）のＭＳＢと、第二の中間結果メモリ１６内の乗算結果Ｘ（ｉ）＊Ｙ（ｊ）のＬＳＢとを、式
［Ｔ，Ｃ］：＝［Ｚ（ｊ），０］＋Ｘ（ｉ）＊Ｙ（ｊ）
に従って累積することで行われる。
【００３５】
ここでは、第一の排他的論理和リンク段１２がＭＳＢに対する加算器として用いられ、第二の排他的論理和リンク段１３がＬＳＢに対して用いられ；第二の中間結果メモリ１６はセットされ、ＭＳＢは第三のマルチプレクサ段２を介して第一の中間結果メモリ３にパスされる。
【００３６】
６．ランインデックスｊを１だけ、式
ｊ：＝ｊ−１
に従って低減（減分）する。
【００３７】
７．Ｙ（ｊ）を、メモリユニット１からデータ出力４５と第四のマルチプレクサ段６を介して第二のサブブロック８内にロードする。
【００３８】
８．ｊ＜ｒであるときは：ＸＩを第一のサブブロックメモリ７内にロードする。すると、ｍ＊ｍビット乗算器段９の出力２４，２５の所に係数Ｘ、ＹのサブブロックＸ（ｉ）、Ｙ（ｊ）の乗算結果Ｘ（ｉ）＊Ｙ（ｊ）のＭＳＢとＬＳＢがさらなる処理のために供給される。
【００３９】
９．係数Ｘ、ＹのサブブロックＸ（ｉ）、Ｙ（ｊ）の乗算結果Ｘ（ｉ）＊Ｙ（ｊ）を第一の中間結果メモリ３のセクションＺ（ｊ）からの前の中間結果Ｚ（ｊ）と、第二の中間結果メモリ１６からの結果Ｃ（ＬＳＢ）に加える。これは、第一の中間結果メモリ３のセクションＺ（ｊ＋１）或いはセクションＣ１内の乗算結果Ｘ（ｉ）＊Ｙ（ｊ）のＭＳＢと、第二の中間結果メモリ１６内の乗算結果Ｘ（ｉ）＊Ｙ（ｊ）のＬＳＢとを累積し；さらに、ｊがｒより小さいか或いはこれと等しい場合は、簡約多項式Ｒの第一のサブブロックＲ（ｊ）と第一の中間結果メモリ３のセクションＴ内に格納されているサブブロックＴとの積を計算し、この積を、それぞれ、セクションＣ１内に格納されているサブブロックＣ１（ＭＳＢ）或いは第二の中間結果メモリ１６内に格納されているサブブロックＣ（ＬＳＢ）に加え、第一の中間結果メモリ３のセクションＺ（ｊ＋１）内、或いは第二の中間結果メモリ１６（サブブロックＣの場合）内の結果を式：
ｊ＞ｒの場合は：
［Ｚ(ｊ＋１)，Ｃ］：＝＋［Ｚ(ｊ)＋Ｃ，０］＋Ｘ(ｉ)＊Ｙ(ｊ)；
ｊ＜ｒ或いはｊ＝ｒの場合は：
［Ｃ１，Ｃ］：＝［Ｚ(ｊ)＋Ｃ，０］＋Ｘ(ｉ)＊Ｙ(ｊ)及び
［Ｚ(ｊ＋１)，Ｃ］：＝［Ｃ１，Ｃ］＋Ｔ＊Ｒ(ｊ)
従って累積することで達成される。
【００４０】
ここでは、第一の排他的論理和リンク段１２がＭＳＢに対する加算器として用いられ、第二の排他的論理和リンク段１３がＬＢＳに対して用いられ、第二の中間結果メモリ１６がセットされ、ＭＳＢが第三のマルチプレクサ段２を介して第一の中間結果メモリ３に加えれ、この内部ではセクションＺ（ｊ＋１）とＣ１がセットされる。積Ｔ＊Ｒ（ｊ）を計算するためには、Ｒ（ｊ）が簡約多項式メモリ４から第四のマルチプレクサ段６を介して第二のサブブロックメモリ８にパスされ、一方、サブブロックＴが第一の中間結果メモリ３の対応するセクションＴから第一のサブブロックメモリ７内にロードされる。この計算ステップは、従って、ｍ＊ｍビット乗算器段９、第一と第二の排他的論理和リンク段１２，１３、第一、第二、第三及び第四のマルチプレクサ段１４，１５，２，６、並びに第二の中間結果メモリ１６を伴う。
【００４１】
１０．ランインデックスｊを１だけ、式
ｊ：＝ｊ−１
に従って減少（減分）し、ｊ＞０の場合は、計算ステップ７に進む。
【００４２】
１１．第二の中間結果メモリ１６からの結果値Ｃを、
Ｚ（１）：＝Ｃ
なる式に従って、第一の中間結果メモリ３のセクションＺ（１）内に格納する。
【００４３】
１２．ランインデックスｉを１だけ、式
ｉ：＝ｉ−１
に従って減少（減分）し、ｉ＞１の場合は、計算ステップ１に進む。
【００４４】
１３．ここで、ランインデックスｉに対しては、以下の関係が適用する：
ｉ＝１
上述の計算ステップ１〜１２を通じての最後のランは、全部でｐ個のサブブロックＺ（ｊ）の新たに計算された値のおのおのが多項式乗算の要求される簡約された最終結果の部分を構成するとき開始され；これらサブ結果Ｚ（ｊ）、並びにステップ１〜１２に対して説明された計算動作（結果）は、直接メモリアクセス（ＤＭＡ）にて、出力レジスタ５を介してメモリユニット１のデータ入力にパスされ、この中の所定のメモリ位置に格納される。
【００４５】
図１の実施例は、計算ステップ９において、上述のように、第一の中間結果メモリ３のセクションＣ１と呼ばれるメモリセクションを利用する。しかし、図２に示される第一の実施例に対する代替実施例においては、このサブブロックＣ１は、第一の中間結果メモリ３のセクション内に格納されるのではなく、別個のレジスタ、つまり、ｍビットなるメモリ空間を有する第三の中間結果メモリ１９内に格納される。これに対応するように、図２に参照符号１０３にて示される第一の中間結果メモリでは、サブブロックＣ１を格納するためのセクションが削除される。図２の代替によると、第一の中間結果メモリ１０３は、残りの回路への接続のために、図１の第一の中間結果メモリ３の入力４９の代りに入力１４９を備える。さらに、図２の代替による第一の中間結果メモリ１０３は、残りの回路への接続のために、図１の第一の中間結果メモリ３の出力５０の代りに出力１５０を備える。
【００４６】
第三の中間結果メモリ１９は、第一の排他的論理和リンク段１２によって出力されるリンク結果Ｃ１を格納できる寸法とされるメモリセクションを形成し、この入力７１は、ｍビットなるワード幅に対して設計された接続を介して、第一の排他的論理和リンク段１２の出力３７に接続される。こうして、第一の排他的論理和リンク段１２から出力されたリンク結果は直接に入力７１に加えられ、サブブロックＣ１として格納される。第三の中間結果メモリ１９として示されるこのメモリセクションの出力７２は、ｍビットなるワード幅に対して設計された接続を介して、第五のマルチプレクサ段１７の第一の入力７３に接続され、この第五のマルチプレクサ段１７の第二の入力７４は、これもｍビットなるワード幅に対して設計された接続を介して、第一の中間結果メモリ１０３の出力１５０に接続される。この第五のマルチプレクサ段１７の出力７５は、ｍビットなるワード幅に対して設計された接続を介して、第一の排他的論理和リンク段１２の第三の入力２８に接続される。
【００４７】
第五のマルチプレクサ段１７を介して、第一の排他的論理和リンク段１２から供給され、第三の中間結果メモリ１９内に格納されたリンク結果或いは第一の中間結果メモリ１０３からの別の中間結果のいずれかが第一の排他的論理和リンク１２内に加えられる。これは制御ユニット１８によって制御ライン７６を介して制御される。つまり、制御ユニット１８から制御ライン７６を介して対応する選択信号が第五のマルチプレクサ段１７に送られる。サブブロックＣ１の格納を制御するためには、第二の中間結果メモリ１６を制御するのと類似のやり方にて制御ユニット１８によってさらなるメモリコマンドが制御ライン７７を介して第三の中間結果メモリ１９に加えられる。
【００４８】
勿論、第二と第三の中間結果メモリ１６，１９を２ｍビットなる幅を有する一つのレジスタに結合し、この内部にサブブロックＣとＣ１の両方に対するメモリ空間を設けることもできる。
【００４９】
本発明は、第一の中間結果メモリ（図１或いは図２に示される実施例における要素３或いは１０３）、及び簡約多項式メモリ（図１と図２に示される実施例における要素４）を用いることによりメモリユニット１へのメモリアクセスを最小限に押さえることができるという長所を有する。これは、第一に乗算器の電力消費に対して好ましい効果を有し、第二に、ＲＡＭとして形成されるメモリユニット（図１と図２に示される実施例における要素１）へのアクセスは、通常、時間が掛り、このため乗算の実行におけるボトルネックとなるという理由から計算プロセス全体の高速化にも大きく寄与する。
【００５０】
本発明は、更に、従来の簡約多項式（図１と図２に示される実施例における要素Ｒ（ｊ））においては先頭（（ｎ＋１）番目の）ビット点における“１”の後ろに非常に多数の零が続くという知識も有効に活用する。本発明においてはこの知識が有効に活用され、全体でｐ個のサブブロックの内のｒ個のみが格納され、遂行される計算ステップにおいて考慮される。この格納動作と計算ステップの節約により、電力消費と計算時間の両方に好ましい効果がもたらされる。更に、これらの節約のために、本発明による乗算器はサイズを小さくすることができ、このため半導体結晶上の集積回路として実現されるような装置においては結晶表面を節約することが可能となる。
【００５１】
さらに、本発明による乗算器はシフトレジスタではなく単純なレジスタ回路を用いて構成することができる。さらに、本発明による乗算器及び本発明による方法は、計算の各ステップにおいて図１の実施例に対して説明されたように、中間結果Ｚ（ｊ）が決して同時に全ては交換されないように設計される。この結果、乗算器の回路装置の電力消費におけるピークを回避できるのみでなく、総電力消費も低く押さえることができる。より具体的には、識別のための製品、例えば、チップカード等においては、これによって、第一には第一にエネルギーバランスが改善され、第二には妨害（干渉）に対する抵抗が向上すると共に、機密データの漏洩に対する保護が増強される。
【図面の簡単な説明】
【図１】  本発明による乗算器の第一の実施例を示す。
【図２】  図１の実施例に対する代替実施例を示し、対応する要素は同一の参照符号にて示される。
【符号の説明】
１  レジスタ、好ましくはＲＡＭとして実現されるメモリユニットであり、少なくとも（２ｐ＋ｒ）＊ｍビットなるメモリ空間を有する
２  第三のマルチプレクサ段
３  図１による第一の中間結果メモリであり、（ｐ＋３）＊ｍビットなるメモリ空間を有するレジスタとして設計される。この中間結果メモリ３のＴ，ＴＩ或いはＣ１として各セクションにはｍビットが割当てられ、セクションＺ（ｊ）にはｐ＊ｍビットなるメモリ空間が割当てられる
４  簡約多項式メモリであり、ｐ＊ｍビットなるメモリ空間を有するレジスタとして設計される
５  リンク結果を中間的に格納に対する出力レジスタであり、ｍビットなるメモリ空間を有するレジスタとして設計される
６  第四のマルチプレクサ段
７  乗算器段９内で互いに連結されるべきワード幅ｍなるサブブロックを格納及び供給するために用いられる第一のサブブロックメモリであり、ｍビットなるメモリ空間を有するレジスタとして設計される
８  乗算器段９内で互いにリンクされるべきワード幅ｍなるサブブロックを格納及び供給するために用いられる第ニのサブブロックメモリであり、ｍビットなるメモリ空間を有するレジスタとして設計される
９  ｍ＊ｍビット乗算器段
１０  乗算器段９の第一の出力２４と第一の排他的論理和リンク段１２の第一の入力２６との間の、より上位のビットＭＳＢに対するライン
１１  乗算器段９の第ニの出力２５と第ニの排他的論理和リンク段１３の第一の入力２９との間の、より下位のビットＬＳＢに対するライン
１２  第一の排他的論理和リンク段であり、遂行されるべき多項式乗算に対する加算器として用いられる
１３  第ニの排他的論理和リンク段であり、遂行されるべき多項式乗算に対する加算器として用いられる
１４  第一のマルチプレクサ段
１５  第ニのマルチプレクサ段
１６  第二の中間結果メモリであり、ｍビットなるメモリ空間を有するレジスタとして設計される
１７  第五のマルチプレクサ段
１８  制御ユニットであり、乗算器を所定のファンクション系列に従って制御するために用いられる
１９  ｍビットなるメモリ空間を有する別個のレジスタとして設計された、サブブロックＣ１を格納する第三の中間結果メモリ
２０  中央プロセッサであり、ＣＰＵとも呼ばれる
２１  メモリユニット１と中央プロセッサユニット２０の間の接続
２２  乗算器段の第一の入力であり、ワード幅ｍを有する
２３  乗算器段の第ニの入力であり、ワード幅ｍを有する
２４  乗算器段９の第一の出力であり、ワード幅ｍを有し、より上位のビットＭＳＢに対して用いられる
２５  乗算器段９の第ニの出力であり、ワード幅ｍを有し、より下位のビットＬＳＢに対して用いられる
２６  第一の排他的論理和リンク段１２の第一の入力
２７  第一の排他的論理和リンク段１２の第ニの入力
２８  第一の排他的論理和リンク段１２の第三の入力
２９  第ニの排他的論理和リンク段１３の第一の入力
３０  第ニの排他的論理和リンク段１３の第ニの入力
３１  第一のマルチプレクサ段１４の第一の入力
３２  第一のマルチプレクサ段１４の第二の入力であり、零ベクトルを供給するたに用いられる
３３  第一のマルチプレクサ段１４の出力
３４  第二のマルチプレクサ段１５の第一の入力
３５  第二のマルチプレクサ段１５の第二の入力であり、零ベクトルを供給するために用いられる
３６  第二のマルチプレクサ段１５の出力
３７  第一の排他的論理和リンク段１２の出力
３８  第ニの排他的論理和リンク段１３の出力
３９  第二の中間結果メモリ１６の入力
４０  第二の中間結果メモリ１６の出力
４１  第三のマルチプレクサ段２の第一の入力
４２  第三のマルチプレクサ段２の第ニの入力
４３  第三のマルチプレクサ段２の第三の入力
４４  第三のマルチプレクサ段２の出力
４５  メモリユニット１のデータ出力
４６  メモリユニット１のデータ入力
４７  出力レジスタ５の入力
４８  出力レジスタ５の出力
４９  第一の中間結果メモリ３の入力
５０  第一の中間結果メモリ３の出力
５１  簡約多項式メモリ４の入力
５２  簡約多項式メモリ４の出力
５３  第一のサブブロックメモリ７の入力
５４  第一のサブブロックメモリ７の出力
５５  第四のマルチプレクサ段６の第一の入力
５６  第四のマルチプレクサ段６の第二の入力
５７  第四のマルチプレクサ段６の出力
５８  第二のサブブロックメモリ８の入力
５９  第二のサブブロックメモリ８の出力
６０  制御ユニット１８と出力レジスタ５との間のメモリコマンドに対する制御ライン
６１  制御ユニット１８と第一の中間結果メモリ３との間のメモリコマンドに対する制御ライン
６２  制御ユニット１８と簡約多項式メモリ４との間のメモリコマンドに対する制御ライン
６３  制御ユニット１８と第一のサブブロックメモリ７との間のメモリコマンドに対する制御ライン
６４  制御ユニット１８と第二のサブブロックメモリ８との間のメモリコマンドに対する制御ライン
６５  制御ユニット１８と第二の中間結果メモリ１６との間のメモリコマンドに対する制御ライン
６６  制御ユニット１８と第三のマルチプレクサ段２との間の選択信号に対する制御ライン
６７  制御ユニット１８と第四のマルチプレクサ段６との間の選択信号に対する制御ライン
６８  制御ユニット１８と第一のマルチプレクサ段１４との間の選択信号に対する制御ライン
６９  制御ユニット１８と第二のマルチプレクサ段１５との間の選択信号に対する制御ライン
７０  制御ユニット１８と中央処理ユニット２０との間のコマンドラインであり、例えば、乗算を独立に実行するためのコマンドを制御ユニット１８に送るため、或いは状態情報を中央処理ユニット２０に送るために用いられる
７１  第三の中間結果メモリ１９の入力
７２  第三の中間結果メモリ１９の出力
７３  第五のマルチプレクサ段１７の第一の入力
７４  第五のマルチプレクサ段１７の第二の入力
７５  第五のマルチプレクサ段１７の出力
７６  制御ユニット１８と第五のマルチプレクサ段１７との間の選択信号に対する制御ライン
７７  制御ユニット１８と第三の中間結果メモリ１９との間の格納コマンドに対する制御ライン
１０７  図２による第一の中間結果メモリであり、図１の第一の中間メモリと比べて、サブブロックＣ１を格納するためのセクションが省略されてる、つまり、（ｐ＋２）＊ｍビットなるメモリ空間を有するレジスタとして設計されている点で異なる。中間結果メモリ１０３のＴ及びＸＩとして示されている各セクションにはｍビットが割当てられ、セクションＺ（ｊ）にはｐ＊ｍビットなるメモリ空間が割当てられる
１４９  図２による第一の中間結果メモリ１０３の入力
１５０  図２による第一の中間結果メモリ１０３の出力
Ｃ  第ニの中間結果メモリ１６内に格納されるサブブロック
Ｃ１  第一の中間結果メモリ３のセクションであり、サブブロックはこの内或いは第三の中間結果メモリ１９内に格納される
ｉ  ランインデックスであり、ｉ＝１，…，ｐ
ｊ  ランインデックスであり、ｊ＝１，…，ｐ
ＬＳＢ  より下位のビット
ｍ  例えば、ガロア体ＧＦ（２ｍ＊ｐ）からの乗算されるべき係数の各々によって形成されるベクトルを形成するｐ個の各サブブロックの幅を表し、ｍは１より大きな正の整数から成る
ＭＳＢ  より上位のビット
ｎ  例えば、ガロア体ＧＦ（２ｍ＊ｐ）からの乗算されるべき係数の幅を表し、パラメータｐとｍの積から成る
ｐ  例えば、ガロア体ＧＦ（２ｍ＊ｐ）からの乗算されるべき係数の各々によって形成されるベクトルを形成するサブブロックの数を表し、各々ｍビットなる幅を有し、ｐは１より大きな正の整数から成る
ｒ  簡約多項式Ｒのより下位のサブブロックの数を表し、各々任意的に非零ベクトルのｍビットを含み、ｒはｐより小さな正の整数から成る
Ｒ  簡約多項式
Ｔ  第一の中間結果メモリ３の１セクションであり、サブブロックがこの内部に格納される
Ｘ  Ｙと乗算される係数
Ｘ（ｉ）  係数Ｘのサブブロックを表し、各々ｍビットなる幅を有し、ｉ＝１，…，ｐ
ＸＩ  第一の結果メモリ３の１セクションであり、サブブロックがこの内部に格納される
Ｙ  Ｘと乗算される係数
Ｙ（ｊ）  係数Ｙのサブブロックを表し、各々ｍビットなる幅を有し、ｊ＝１，…，ｐ
Ｚ（ｊ）  第一の結果メモリ３の１セクションであり、サブブロックがこの内部に格納される
【図１】
0004823467.tif 000002
【図２】
0004823467.tif 000003