算術プロセッサ
【課題】有限体演算やモジュラ整数演算など一群の関連する算術演算をそれぞれパフォームする複数の算術回路を有するＡＬＵを含むことを特徴とする算術プロセッサを提供すること。
【解決手段】ＡＬＵは、オペランドデータを受信するオペランド入力データバスと、算術演算の結果を戻す結果データ出力バスとを有する。レジスタファイルはオペランドデータバスと結果データバスに結合されている。レジスタファイルは複数の算術回路によって共用されている。コントローラは、ＡＬＵおよびレジスタファイルに結合され、算術演算を要求するモード制御信号に応答して、複数の算術回路の１つを選択し、レジスタファイルとＡＬＵとの間でデータアクセスを制御し、それによりレジスタファイルが算術回路によって共用されるようにする。
【解決手段】ＡＬＵは、オペランドデータを受信するオペランド入力データバスと、算術演算の結果を戻す結果データ出力バスとを有する。レジスタファイルはオペランドデータバスと結果データバスに結合されている。レジスタファイルは複数の算術回路によって共用されている。コントローラは、ＡＬＵおよびレジスタファイルに結合され、算術演算を要求するモード制御信号に応答して、複数の算術回路の１つを選択し、レジスタファイルとＡＬＵとの間でデータアクセスを制御し、それによりレジスタファイルが算術回路によって共用されるようにする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有限体および整数の算術をパフォームする方法および装置に関する。
【背景技術】
【０００２】
有限体（finitefield）に対するＥＣ（Elliptic Curve）暗号法では、加算と、乗算と、二乗と、反転（inversion）の算術演算が必要となる。さらに、体（field）の標数が２でない場合には、減算も必要になる。例えば符号定数の計算では、モジュラ算術演算も必要になるが、このような演算は有限体の演算ほど必要にならない。例えばＥＣ暗号法では、モジュラおよび有限体演算、加算、減算、乗算、反転の完全な補集合（fullcomplement）が必要になる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
暗号法のための体のサイズは比較的大きくなる傾向があり、算術演算を許容時間内で実行するために高速の専用プロセッサが必要になる。したがって、高速モジュラ算術プロセッサか、Ｆ２ｎの算術演算をパフォームする専用プロセッサのいずれかが、多数インプリメントされている。特殊目的または専用プロセッサを使用することは、当技術分野では、周知のことである。こうしたプロセッサは一般にコプロセッサと呼ばれ、通常は、ホスト計算システムで利用されており、従って、命令および制御はメインプロセッサからコプロセッサに提供されている。
【０００４】
なかでもＲＳＡが暗号化システムとして慣用されていたが、優秀かつよりセキュアなＥＣ暗号法が登場したため、モジュラ冪法（modular exponentiation）専用のプロセッサの必要性は、薄らいで来ている。ユーザはＲＳＡ暗号法からＥＣ暗号法に移行しているものの、性能およびコストをほとんどあるいは全く犠牲にすることなくこれらの両方の演算をサポートする算術プロセッサに対するニーズがある。
【０００５】
本発明の第１の目的は、有限体算術と整数算術を組み合わせ、ＥＣ暗号法に必要な演算と、例えばＲＳＡ暗号法で必要なモジュラ冪法とを提供するプロセッサを提供することにある。
【０００６】
本発明の第２の目的は、異なる体またはレジスタサイズにスケーリングすることができる算術プロセッサ設計を提供することにある。
【０００７】
本発明の第３の目的は、異なる体サイズで使用することができる算術プロセッサを提供することにある。
【０００８】
本発明の第４の目的は、マルチシーケンス中の複数のステップを同時にパフォームすることによってマルチシーケンス演算実行を高速化するためにスケーリングすることができる算術プロセッサを提供することにある。
【課題を解決するための手段】
【０００９】
本発明によれば、
（ａ）一群の関連する算術演算をそれぞれ実行する複数の算術回路を有する論理演算装置であって、オペランドデータを受信するオペランド入力データバスと、前記算術演算の結果を戻す結果データ出力バスとを有する論理演算装置と、
（ｂ）前記オペランドデータバスおよび前記結果データバスに結合されたレジスタファイルと、
（ｃ）前記ＡＬＵおよび前記レジスタファイルに結合された制御装置であって、算術演算を要求するモード制御信号に応答して前記複数の算術回路の１つを選択し、かつ前記レジスタファイルと前記ＡＬＵの間でデータアクセスを制御することにより、前記レジスタファイルが前記算術回路によって共用されるようにする制御装置とを含む算術プロセッサが提供される。
【００１０】
本発明によれば、有限体回路および整数算術回路を含み、かつ汎用レジスタおよび専用レジスタを備えたプロセッサが提供される。
【００１１】
本発明によれば、有限体算術および整数算術を両方とも実行し、専用レジスタおよび汎用レジスタの両方ならびに算術回路を共用する算術プロセッサが提供される。この目的のために、多項式基底が整数の標準的な基数累乗基底（standard radix-power basis）と同様であるので、有限体ハードウェアについて多項式基底を想定する。
【発明の効果】
【００１２】
本発明によれば、有限体算術と整数算術を組み合わせ、ＥＣ暗号法に必要な演算と、例えばＲＳＡ暗号法で必要なモジュラ冪法とを提供するプロセッサを提供できる。
【００１３】
本発明によれば、異なる体またはレジスタサイズにスケーリングすることができる算術プロセッサ設計を提供できる。
【００１４】
本発明によれば、異なる体サイズで使用することができる算術プロセッサを提供できる。
【００１５】
本発明によれば、マルチシーケンス中の複数のステップを同時にパフォームすることによってマルチシーケンス演算実行を高速化するためにスケーリングすることができる算術プロセッサを提供できる。
【図面の簡単な説明】
【００１６】
【図１】有限体算術および整数算術をパフォームする算術プロセッサアーキテクチャのブロック図である。
【図２】図１に示すＡＬＵ（arithmetic logic unit）の概略ブロック図である。
【図３】有限体算術および整数算術をパフォームする算術プロセッサアーキテクチャの代替実施形態のブロック図である。
【図４】図３に示すＡＬＵの概略ブロック図である。
【図５】（ａ）、（ｂ）、および（ｃ）は図２に示すＡＬＵのビットスライスの実施形態のブロック図である。
【図６】図５に示すビットスライスの有限体乗算器の回路図である。
【図７】算術インバータのブロック図である。
【図８】組み合わせた有限体／整数乗算器の回路図である。
【図９】図１のマルチビットＡＬＵの実施形態を示す概略ブロック図である。
【図１０】図９のマルチビット有限体乗算器の回路図である。
【発明を実施するための形態】
【００１７】
図１を説明する。算術プロセッサの一実施形態は一般的に参照番号１で示してある。当然のことであるが、この算術プロセッサは総合計算システム中の汎用プロセッサとともに使用することができ、データはこの計算システムと算術プロセッサの間で交換される。算術プロセッサには、レジスタファイルと呼ばれる一群の汎用レジスタ（ＧＰ）２が含まれている。レジスタファイルはＥＣの点加算（point addition）、点倍加（point doubling）などのための中間記憶域として使用することができるものである。一群の汎用レジスタ２はデータ入力またはオペランドバス６を介してＡＬＵ（arithmeticlogic unit）４と通信を行なっている。ＡＬＵ４にはシェアード（shared）有限体および整数算術回路が含まれている。ＡＬＵ４による計算の結果をレジスタファイル２に書き込むため、データ出力または結果バス１４がＡＬＵ４とレジスタファイル２の間に設けてある。
【００１８】
ＡＬＵ４による計算オペレーションは、算術プロセッサ１のコントローラ８に駐在するマイクロプログラム化命令により制御されている。モード選択コントロール１０は有限体計算またはモジュラ整数計算を選択するために用意してある。体サイズ制御１２も、ＡＬＵ４を初期設定して、種々のオペランドベクトルサイズに適応させるために用意してある。そこで、コントローラ８はなかんずく次のタスク、すなわち、適正な算術モードおよび演算をＡＬＵ４に提供するタスクと、レジスタファイル２とＡＬＵ４の間のデータアクセスをコーディネートするタスクと、使用される適正な体のサイズをＡＬＵ４に提供するタスクとをパフォームする。
【００１９】
汎用レジスタは、少なくとも予想可能な最大のＦ２ｍＥＣ暗号システムをハンドルするだけのビット幅を有するように選択される。これら汎用レジスタは整数モジュラ算術で必要なビット長をサポートするために、組み合わせることができる。例えば、レジスタファイル２の単一レジスタのビット幅が５１２ビット幅である場合に、単一の２０４８ビットＲＳＡ量の記憶域を提供するため、４つのレジスタを使用することができる。これら汎用レジスタには、データのブロックがロードされ、例えば、２０４８ビットの計算をブロック単位で行い、ついで、再組み立てして、全幅結果（full width result）を得ることができる。典型的には、算術プロセッサ１は既存のホストコンピュータシステムで利用され、コントローラ８はこのホストコンピュータシステムから制御信号を受信し、適正なホストバスインタフェースを介して、ホストデータバスにデータを通信する。このようなインタフェースの詳細は当業者とって周知のことであり、説明は省略する。
【００２０】
図２を説明する。ＡＬＵ４には、幾つかの特殊レジスタ１６と、複数のサブＡＬＵ１８と、出力データバス３０と、コントローラ２０とが含まれている。複数のサブＡＬＵ１８には組み合わせロジックおよび算術回路が含まれていて、組み合わせロジックおよび算術回路は、特殊レジスタからデータバス２８を介して各サブＡＬＵに入力された１つ以上のビットをオペレートする。出力データバス３０はサブＡＬＵ１８と特殊レジスタとの間に設けてある。コントローラ２０は、なかんずく、次のタスク、すなわち、計算オペレーション中の各ステップを通してＡＬＵ４を順序づけるタスクと、特殊レジスタ１６からの制御ビットを監視するタスクと、使用してある体のサイズを決定するためにカウンタを制御レジスタ２２に実装するとともに、プロセッサハードウェアを設計し直さずに、プロセッサ１が異なる体サイズに対して使用することができる機構を実装するタスクとをパフォームする。これらの機能を提供するため、特殊レジスタ１６の制御ビット２６は制御ビット入力２４としてコントローラ２０に供給される。特殊レジスタ１６は、全て、個別にアドレス可能になっている。コントローラ２０はレジスタファイルから入力バス６を介してサブＡＬＵ１８または特殊レジスタ１６に入力されたデータも制御する。これらサブＡＬＵは、単一のビットにオペレートすることができ、複数のビットに一度にオペレートすることができる。これらのコンポーネントは後程より詳細に記述する。
【００２１】
図３を説明する。算術プロセッサの代替例は参照番号１′で示してある。本実施形態では、別個の有限体装置３４および整数モジュラ算術装置３６を提供する。このプロセッサは、レジスタファイル２′と、データ入力バス６′と、データ出力バス１４′と、コントローラ８′も含むが、制御１３ａおよび１３ｂがそれぞれコントローラ８′から各ＡＬＵ３４および３６に提供される。
【００２２】
図４を説明する。図４は図３のＡＬＵ３４および３６をより詳細に示す。ＡＬＵ３４および３６には、それぞれ、特殊レジスタ１６′ａおよび１６′ｂと、コントローラ２０′ａおよび２０′ｂとが含まれている。ＡＬＵ３４および３６には、それぞれ、サブＡＬＵ１８′ａおよび１８′ｂが含まれている。したがって、この実施形態では、特殊レジスタ１６′ａおよび１６′ｂと、算術および制御回路は、当然、共有されない。サブＡＬＵ１８′ａのうちの１つ以上のサブＡＬＵ１８′ａは、協働して、シフト左／右とＸＯＲシフトの機能を実行し、サブＡＬＵ１８′ｂのうちの１つ以上のサブＡＬＵ１８′ｂは、協働し、任意選択で、桁上げ保存技術または桁上げ伝搬（carry propagation）を使用して、整数加算および整数減算の機能を実行する。
【００２３】
図２を説明する。サブＡＬＵ１８は、特殊レジスタ１６から供給されたオペランドに対して、次の論理機能、すなわち、ＸＯＲと、シフト左／右と、ＸＯＲシフトと、整数加算と、整数減算を実行する。これらの機能は、１つのサブＡＬＵ１８か、マルチプル・サブＡＬＵに含めることができる。マルチプル・サブＡＬＵ１８を設けることにより、当該プロセッサは複数の演算（例えば、有限体反転）を同時にパフォームすることができる。
【００２４】
図５を説明する。図５は図２のＡＬＵ４のビットスライスを詳細に示す。図５ａの４１は、当該ビットスライスを示す。次の考察では、ビットスライス４１と関係付けをしたロジック回路と関連して、各特殊レジスタのセルを相互接続する、と言う。ビットスライスに含まれたロジック回路は、一般的に、図２に示すようなサブＡＬＵ１８のうちの１つで表される。ビットスライスの構成は、Ｎビットレジスタに対しては、Ｎ回繰り返えすことができる。さらに、明確にするため、Ｎをレジスタ内のセル数と定義し、レジスタ内の個別のセルを例えばＡｉという。ここで、０≦ｉ≦Ｎ−１であり、ＡＮ−１は特殊レジスタの最も右にあるセルである。レジスタの内容は小文字で参照され、例えば、長さｎのビットベクトルＡは、ａ０をＬＳＢとして、ビットにａ０，…ａｎ−１と番号が付けられることになる。ここで、特殊レジスタには特定の名前が付けられているが、これらのレジスタは、後程説明するが、実行されている算術演算に依存して異なる機能をとることができる、ことに留意されたい。
【００２５】
図５の特殊レジスタ１６に含まれるレジスタとしては、乗算演算中に、例えば、被乗数および乗数を個々に保持するための一対のオペランドレジスタＡ４２およびＢ４４と、累算器レジスタＣ４６と、モジュラスレジスタＭ４８と、桁上げ拡張（carry extension）レジスタＣext５０（整数算術で使用される）とがある。
【００２６】
これらのレジスタは、その中にロードされたビットベクトルの個々の２進数を保持するため、Ｎ個のセルを有する。これらのレジスタはシフトレジスタであるのが好ましい。図２に示すサブＡＬＵ１８は、後程説明するが、図５のブロック５２の回路により実装することができる。
【００２７】
乗算
ＡＬＵ４のオペレーションは、有限体乗算のような具体的な算術演算を参照することにより最も良く理解することができる。ここで、２つの元ａおよびｂの積Ｃを考察することにする。ここで、ａおよびｂはビットベクトルであり、ｂは多項式表現でｂ＝（ｂ０，…ｂn-1）の形態となり、ａは多項式表現でａ＝（ａ０，…ａn-1）の形態となる。モジュラスビットベクトルｍは、ｍ＝（ｍ０，…ｍｎ）の形態を有する。モジュラスレジスタは、モジュラスを表すのに必要なビット数より１ビット多い、ことに留意されたい。あるいはまた、最上位ビットｍｎが１であるので、この最上位ビットを暗黙に定義することができ、ｍを（ｍ０，…ｍn-1）で表すこともできる。Ｆ2nにおいて、乗算は、次のような疑似コードにより明確に記述される一連のステップとして実装することができる。
【００２８】
Ｃ＝０｛Ｃ-1＝０｝
For ifrom n-1 to 0 do
For jfrom n-1 to 0 do ｛ｃｊ＝ｃi-1＋ｂn-1ａi＋ｃn-1ｍｊ｝
この乗算を実行する際には、ＭＳＢ（most significant bit）からＬＳＢ（least significant bit）の順に、被乗数と乗数のｂｉの各ビットとの部分積を形成する。その前の部分積のＭＳＢがセットされた場合には、部分積はモジュラスによって簡約（reduce）される。
【００２９】
乗算の実装は、１×Ｎ乗算器を逐次使用することによって行なうことができ、この場合、上記疑似コードの内側の「ｆｏｒ」ループはパラレルに実行される。各セルがそれぞれ２進数ｍｉの１つを含むように、モジュラスレジスタＭには、ＭＳＢｍｎを剥ぎ取ったモジュラスビットベクトルｍがロードされる。図示の実装では、ビットｍｉは、ベクトルのＭＳＢを最も左側のビットとして、左から右に配列されている。すなわち、セルＭn-1はビットｍn-1を含む。Ｎ≠ｎである場合、スティルビット（still bit）Ｍn-1はＭN-1にストアされる、すなわち、データは左寄せされる。各セルが個々に２進数ａｉまたはｂｉの１つを含むように、シフトレジスタＡおよびＢには、有限体元（finitefield element）ビットベクトルａおよびｂがそれぞれロードされる。有限体元ａおよびｂは、左寄せされ、各レジスタにストアされ、乗数レジスタｂのＭＳＢが常に左境界セルのビット、すなわち（ａn-1，ａn-2，…ａ０）および（ｂn-1，ｂn-2，…ｂ０）で利用可能になっている。ベクトルａおよびｂの長さがレジスタの長さより短い場合には、残りのセルには０がパディングされる。以上、図２に示すコントローラ２０によって一般的に実行される。逐次乗算（被乗数を逐次小さくするなど）の他の構成も可能であるが、そのような構成では、体のサイズに柔軟性を持たせることができないし、同様に、制御ビット位置を固定することができない。この乗算アルゴリズムを対応して変化させれば、ＬＳＢからＭＳＢへのビット順序づけも可能である。
【００３０】
ここでは、ＡＬＵ４のビットスライス４１は、有限体において乗算を実装するために、記載されている。ビットスライス４１は第１および第２のコントローラブル加算器５４および５６を含み、第１および第２のコントローラブル加算器５４および５６は、それぞれ、ＸＯＲ機能を有する。レジスタＢの最上位のセルＢN-1は、加算制御信号ｂn-1５７を第１の加算器５４に供給する。第１の加算器５４への入力５８および６０は、レジスタセルＡｉおよびアキュムレータセルＣｉから得られる。第１の加算器５４からの出力６２は、モジュラスレジスタセルＭｉからの入力６４とともに、第２の加算器５６の入力に接続されている。加算器５４は出力６２＝入力６０＋（入力５８および制御５７）という演算をパフォームする。この演算を図５（ｂ）に詳細に示す。
【００３１】
ついで、第２の加算器５６からの出力はアキュムレータセルＣｉに接続されている。第２の加算制御信号６６はアキュムレータＣ４６の最上位のセルＣＮ−１から得られる。アキュムレータＣの最上位のビットＣＮ−１がセットされたとき、当然に、モジュラスベクトルｍによるアキュムレータＣでの部分積のモジュラ簡約が、第２の加算制御信号６６により実装される。図５（ｃ）に詳細に示すように、加算器５６は、出力＝入力６４＋（入力６２および制御６６）という演算を行う。Ｂレジスタはクロックシフトレジスタである。コントローラ２０から供給することができるクロック信号ＣＬＫ１ ６８は、部分積が計算される度に、このレジスタの内容を左にシフトさせる。
【００３２】
図６を説明する。図６は図５のビットスライス４１の詳細な回路実装を示す。この回路実装は有限体乗算を行なうためのものであって、参照番号７０で示す。図６のビットスライスｉ、７０を説明する。図６では、説明のために、ビットスライスは３つしか示していない。セルａｉは、ＡＮＤゲート７２により、加算制御信号ｂｎ−１とＡＮＤ演算される。ＡＮＤゲート７２の出力７４は、アキュムレータＣの隣接するセルＣｉ−１からの入力７８とともに、ＸＯＲゲート７６の入力に接続される。よって、項「ｃi-1＋ｂn-1ａi」の計算が実装される。項「ｃｎ−１ｍｊ」は、ＡＮＤゲートを利用して、信号ｃｎ８０とｍｉ８２をＡＮＤ演算することにより、実装される。ＡＮＤゲートの出力８６は、ＸＯＲゲート７６の出力８８とともに、ＸＯＲゲート８４の入力に接続される。ＸＯＲゲート８４の出力９０は、セルＣｉ９２に接続される。よって、式「ｃｊ＝ｃi-1＋ｂn-1ａi＋ｃｎ−１ｍｊ」が実装される。この汎用の逐次乗算器により、２つのｎビット有限体元の積がｎクロックサイクルで生成されることになる。同期カウンタは、コントローラ２０に含めることができるものであって、繰返し回数の制御を行うものが好ましい。以上の記述は、加算器５４が整数加算器のビットスライスであって、加算器５６が整数減算器のビットスライスであるときに、整数モジュラ乗算に適用される。このことは後程説明する。
【００３３】
加算
有限体Ｆ２ｎ中の乗算に関連して、回路を説明したが、その他の計算オペレーションも容易にパフォームすることができる。有限体加算は桁上げが生じないので、この点で、整数算術より有利である。有限体サム（sum）の計算では、有限体中の２つの元ａおよびｂの加算が、単に、ａとｂのＸＯＲであるので、ＸＯＲゲートを注目レジスタの各セルに導入するだけでよい。したがって、図５に戻ると、入力１００はセルＢｉから第１の加算器５４に供給され、第２の加算器５６は簡約に使用される。ついで、加算器５４からの出力はセルＣｉに直接書き込まれる。オペランドがレジスタａおよびｂに移動された後で、単一のクロックサイクルで、加算をパフォームすることができる。その加算をＡＬＵでパフォームするのは可能であり、その結果をレジスタファイルの汎用レジスタにライトバックするのも可能である。整数加算では、加算器５４は整数加算器のビットスライスであり、整数加算結果に基づきモジュラオーバフローか否かを検査しなければならない。この状態が生じた場合には、整数減算器のビットスライスである加算器５６は、その結果を簡約するのに用いられる。
【００３４】
二乗
ある数を二乗するには、異なる２つの数の乗算と同じ時間でパフォームすることができる。多項式基底における二乗は、特定の既約（irreducible）が二乗展開と明示的に結線された（hardwired）場合は、単一のクロックサイクルでパフォームすることができる。あるいはまた、同じ入力を乗算して二乗をパフォームすることができる。
【００３５】
反転
Ｆ２ｎの有限体元の反転は、ユークリッドの互除法を使用してパフォームすることができ、また、追加のコントロールロジックを有する４つの特殊レジスタを利用してパフォームすることができる。この反転は、シフトが加算と同時に行われる場合（これは加算の出力を次のレジスタセルに結線することによって容易に実装される）には、２ｎサイクルで完了する。
【００３６】
この反転で使用されるレジスタは、Ａ、Ｂ、Ｍ、およびＣである。便宜上、これらのレジスタを概略的に図７に示す。ＭにはＵＬ、ＣにはＬＬ、ＡにはＵＲ、ＢにはＬＲとラベル付けがしてある。再度、この反転を、ビットスライス１１０に関連して記述することができる。
【００３７】
反転のオペランドは、一般に、反転する元ｇと、既約多項式ｆまたはモジュラスｍ（後述）と、ビットベクトル「０」と、ビットベクトル「１」である。ＵＬレジスタ１１６にはｆまたはｍがロードされる。ＬＬレジスタ１１８にはｇがロードされ、ＵＲレジスタ１１２には「０」が、ＬＲレジスタ１１４には「１」がロードされる。ＵＲレジスタ１１２およびＬＲレジスタ１１４では、セルＵＲｉおよびＬＲｉはＸＯＲゲート１２０でＸＯＲ演算されて、出力１２２が生じる。制御信号１２４は、可能な３つの入力のうち１つがセルＵＲｉおよびＵＬｉに書き込まれるかどうかを決定する。入力は隣接するセルまたは出力１２２からの左または右シフトである。制御信号Ｂは後程記載する状態表によって決定される。ＵＬレジスタ１１６またはＬＬレジスタ１１８では、セルＵＬｉおよびＬＬｉはＸＯＲゲート１２６でＸＯＲ演算されて、出力１２８が生じる。制御信号１３０は、可能な２つの入力のうち１つがセルＵＬｉおよびＬＬｉに書き込まれるかどうかを決定する。入力は隣接するセル（ｉ−１）または出力１２８からの左シフトである。この場合も、制御信号１３０は後程記載する状態表によって決定される。
【００３８】
制御変数をＵＬレジスタの長さｋｕと、ＬＬレジスタの長さｋｌと仮定したとすると、Δ＝ｋｕ−ｋｌとなる。値ｋｌおよびｋｕは、好ましくは、同期ダウンカウンタで実装され、Δは好ましくは同期アップ／ダウンカウンタで実装される。カウンタレジスタｋｕ、ｋｌ、およびΔも用意されている。ＵＬおよびＬＬレジスタは左シフトレジスタであり、ＵＲおよびＬＲレジスタは、ともに、左および右シフトレジスタである。
【００３９】
さらに、カウンタレジスタでは、Δには０がロードされ、ｋｕはｎに初期化される。制御ビットラッチは、「１」がアップカウントを示し、「０」がダウンカウントを示すトグル機能を有する。Ｕ／Ｄ制御は、最初、「１」にセットされる。この場合、ＡＬＵで反転を実行する制御装置に含まれるシーケンサは、次のような出力を有する。
【００４０】
Deckl デクリメントｋｌ ｋｌ
Decku デクリメントｋｕ ｋｕ
decDelta デクリメントΔ
incDelta インクリメントΔ
toggle トグルアップ／ダウン
lsUL 左シフト左上レジスタ
lsLL 左シフト左下レジスタ
lsUR 左シフト右上レジスタ
lsLR 左シフト右下レジスタ
rsUR 右シフト右上レジスタ
rsLR 右シフト左下レジスタ
outLR 出力右下レジスタ
outUR 出力右上レジスタ
dadd-lsLL ダウンＸＯＲおよび左シフト左下レジスタ
uadd-lsUL アップＸＯＲおよび左シフト左上レジスタ
インバータのオペレーションの概要を表す状態表は次のようになっており、ＭｕおよびＣｌはそれぞれレジスタＵＬおよびＬＬの上位ビットであり、ＭｕおよびＣｌは現在の状態を決定する。レジスタおよびカウンタ上でアクションがパフォームされると、これによりインバータは新しい状態となる。このプロセスは、ｋｕまたはｋｌが０になるまで繰り返され、右レジスタＲＬまたはＲＵの一方はｇ−１を含み、もう一方はモジュラス自体を含むことになり、これは、後続の乗算または反転演算で使用するために、レジスタｍにリストア（restore）することができる。
【００４１】
【表１】
【００４２】
整数算術
多項式表現と整数表現は非常に良く似ていることから、ＡＬＵでハードウェアを共有することが可能でなる。加算では、整数算術は、桁上げが必要であることから、複雑になるだけである。ＡＬＵの整数算術演算は、例えば乗算演算を利用すれば、最もよく説明することができる。
【００４３】
疑似コードで表した次の一連のステップを参照して、Ｚにおける乗算を説明する。前述したのと同様に、ａおよびｂは乗算されるビットベクトルであり、ｃはａとｂの積であり、Ｃ＝（ｃ０，ｃ１，…，ｃｎ−１）である。
【００４４】
Ｃ＝０
Ｍ＝０
For ifrom 0 to n-1 do
Ｃext←Ｃ
For jfrom 0 to n-1 do
ｃｊ＝（ｂｉ（ａｊ）＋ｍｊ＋ｃｊ）mod２
ｍj+1＝（ｂｊ（ａｊ）＋ｍｊ＋ｃｊ）／２
ここで、
Ｃｅｘｔ←Ｃ:For j from n-1 to 0 do
ｃｊ−１＝ｃｊ
ｃｊ−１ｅｘｔ＝ｃｊｅｘｔ
となる。
【００４５】
同様に、このようにすれば、ＸＯＲを減算器で置換し、しかも、ｍレジスタに素数をロードした場合には、整数 modulo ｐ（integers modulo p）を反転させることができる。改善策であるが、桁上げ保存方法を採用することにより、桁上げ伝搬を遅らせることができる。
【００４６】
図６の実施形態で説明した有限体乗算の場合のビットスライス７０を修正して、整数表現に対する乗算を含むようにすることができる、ことを観測することができる。注意すべきことであるが、整数乗算では、レジスタには、ビットベクトルがＦ２ｍとは逆順でロードされる、すなわち、レジスタの最左端のセルがビットベクトルのＬＳＢを含む。整数乗算では、逐次（successive）部分積の間で、桁上げを実装する必要があり、さらに、部分積がモジュラスで簡約されていないので、逐次部分積の加算による桁上げを供給しなければならない。そこで、アキュムレータレジスタＣが拡張してあり、図５に示すように、新しいレジスタＣｅｘｔ４９が設けてある。各部分積が形成される前に、アキュムレータＣの最下位ビット（セルＣＭ）を拡張レジスタＣｅｘｔの最上位ビット（セルＣｅｘｔｌ）にシフトし、ついで、アキュムレータＣおよびＣｅｘｔは両方ともＬＳＢに向けて１ビットだけシフトされる。最終結果はＣおよびＣｅｘｔで獲得され、Ｃｅｘｔには、当該積の低位ビットが含まれる。このことは、上記オペレーションＣｅｘｔ←Ｃで表される。
【００４７】
図８を説明する。図８はビットスライス１７０を示す。ビットスライス１７０は図６のビットスライス７０に類似している。したがって、同様のコンポーネントは、識別するために、図６の説明で使用した参照番号を１００番台にして使用することにする。つまり、参照番号７０は１７０となる。図８の編成が図６と異なる点は、モジュラスレジスタｍが桁上げレジスタとして使用され、モード選択信号Ｚ／Ｆ２ｍ１７１が提供されるという、２つの重要な点である。
【００４８】
ここで、項ｃｊ＝ｃｊ−１＋ｂｉａｉ＋ｃｎ−１ｍｊは、既に説明した有限体乗算でそうであったように、制御信号ｂｍとレジスタセルＡｉの内容との積で実装され、この積はＡＮＤゲート１７２で実装される。ＡＮＤゲート１７２の出力１７４はレジスタセルｃｊ−１の内容とＸＯＲゲート１７６によりＸＯＲ演算され、参照番号１５８で示す出力項ｃｊ−１＋ｂｉ（ａｉ）が生成される。この出力信号は、ＡＮＤゲート１６０から得られた参照番号１８５で示す項ｃｎ−１（ｍｊ）と、ＸＯＲゲート１８４を使用してＸＯＲ演算され、項ｃｊが生成される。さらに、積’ｂｉａｉ，ｃｊ−１’１６２と、積（ｃｊ−１＋ｂｉａｉ，ｍｊ）１６３とのサム（sum）から、桁上げ項ｍｉが生成され、セルｍｉ１８２に書き込まれる。積の項１６２および１６３はＡＮＤゲート１６４および１６６によってそれぞれ実装される。積の項１６２と１６３のサムはＯＲゲート１６７によって実装される。
【００４９】
モード選択信号Ｚ１７１は、桁上げ入力信号ｃｎ１８０とＯＲ演算され、クロック信号１６９とＡＮＤ演算１６８される。したがって、Ｚ＝０をセットすることにより、有限体算術が実装され、Ｚ＝１をセットすることにより、整数算術が実装される。
【００５０】
図８は、図６で既に説明した有限体乗算を、組合せ有限体／整数乗算器に変換するのに必要な修正を示す。乗算の低位のビットを集めるため、出力レジスタＣが拡張されることに留意されたい。Ｚにおける計算はモジュラスなしでパフォームされるので、モジュラスレジスタＭは、部分積を簡約するためではなく、桁上げのホルダとして使用される。制御信号Ｚ／Ｆ２Ｍ１７１は、ＡＬＵのための整数乗算回路をイネーブルにする。
【００５１】
最終桁上げ伝搬（finalcarry propagation）は、マンチェスターキャリーチェーン（Manchester carry chain）によって提供することができ、レジスタ長が長いことから、１レイヤまたは２レイヤの桁上げスキップ機構によって拡張可能である。さらにｎサイクルだけクロックすることも可能であり、桁上げ保存加算器が桁上げを完全にマージすることが可能である。
【００５２】
１つの入力はその入力において条件付きで補数をとることができ、しかも、加算器のＬＳＢで「ホット」キャリインが行われる場合には、２の補数の減算は、桁上げ伝搬加算器で実装することができる。
【００５３】
乗算時のリップル桁上げは、桁上げスキップにより改良したとしても、許容できなくなるが、この桁上げ伝搬は、桁上げ保存加算器を使用すれば、ほぼ完全に除去することができる。このようにすると、部分積が冗長表現されるが、乗算が完了した後は解決される。
【００５４】
さらに別の実施形態では、ＡＬＵ４は、図９に示すように、計算速度が線形に増加するように修正することができる。これは、特殊レジスタ１６′からの連続ビットを一度に処理し、修正したサブＡＬＵ１９０で示す追加回路を実装し、図９に示すようにインクリメント加算を処理することによって達成される。複数のビットを処理すると、速度が線形増加することになる。例えば、計算が順次にパフォームされる場合は、その順序中の２つ以上のステップを同時に実行することができる。この場合、コントローラ２０′は特殊レジスタ１６′からの２ビット以上の制御ビット１９４を処理することになり、制御装置の入力１９２は図９にマルチビットラインとして示す。
【００５５】
有限体に対して一度に２ビット実行する乗算器（two-bit at a time multiplier）の回路図を図１０に示す。この実装では、ビットスライス２００はその数がＸＯＲゲート２１０の数の２倍であり、当該加算の２つの項を実装している。この乗算器は乗数から２ビットをとり、被乗数ａｉおよびａｉ−１を２回だけ隣接してシフトすることにより加算し、モジュラスＭｉおよびＭｉ−１を２回だけ隣接してシフトすることにより簡約する。このようにすると、モジュラス簡約（modulusreduction）で連続する２つの部分積が同時に生成され、したがって、全計算時間を半分にすることができるという効果がある。
【００５６】
特殊レジスタの上位（top）ビットがコントローラ２０または２０′用の制御ビットとして使用される、ことに留意されたい。このようにすると、オペランドがレジスタにロードされると、左揃えされ、したがって、制御が常に固定ビット位置から得られるという利点がある。しかし、その他のビット例えば下位（bottom）ビットを制御ビットとして使用することもできる。しかし、このようにすると、ハードウェアが複雑になることもある。
【００５７】
この場合も、Booth（または、修正Booth）記録などのオプションが可能となるので、マルチビット演算の計算速度がさらに線形的に増加する。
【００５８】
このようなＡＬＵは汎用レジスタに対して簡単な算術演算をパフォームする能力を有するものと仮定している。他の例のＡＬＵは全ての算術をＡＬＵ内部レジスタに対してパフォームするものであり、汎用レジスタはこれらのレジスタとの間でリード（read）およびライト（write）のみを行う能力を有する。
【００５９】
このようなＡＬＵの機能には、リップル桁上げや、桁上げスキップ加算と桁上げ完了の組合せなど、何らかの桁上げ伝搬方法を利用した、整数加算が含まれる。
【００６０】
このようなＡＬＵは、有限体加算で使用される単純なＸＯＲ機能も提供する。整数および有限体表現（ビット順序）が逆であるので、体から整数への変換と、整数から体への変換に使用されるビット逆転（bit reversal）機構を設けると有利である。２つのシフトレジスタの頂部どうしを接続することにより、ｎクロックサイクルでこの機能が提供される。ここで、ｎは算術オペランドの長さである。
【００６１】
本明細書で与えた一般的なアーキテクチャは、ＥＣとモジュラ指数算術との間でレジスタファイルを共用するだけでなく、共用制御レジスタに加えて、特殊レジスタおよび組み合わせロジックも共用する可能性がある。
【００６２】
以上、本発明の具体的な実施形態と具体的な用途について説明したが、種々の修正は、本発明の範囲を逸脱しない限り、当業者にとって可能である。例えば、記載の実施形態では、特定のロジック回路について言及したが、例えば、ド・モルガンの法則を使用して等価な回路を使用することもでき、反転ロジック（inverted logic）が実装された場合には、相補形回路を使用することもできる、ことに留意されたい。さらに、レジスタおよびビットベクトルのオリエンテーション、すなわち、左、右、上、下には、これらの方向の他の編成も含まれる。
【００６３】
本明細書で採用した項および式は、これらのものに限定されるものではなく、例として使用したものであり、これらの項および式を使用したことに、図示および記述した機構またはその一部分の均等物を排除する意図はなく、本発明の範囲内で種々の修正が可能であることを認識されたい。
【符号の説明】
【００６４】
１ 算術プロセッサ
２ レジスタファイル
４ 有限体／整数エンジン
８ コントローラ
【技術分野】
【０００１】
本発明は、有限体および整数の算術をパフォームする方法および装置に関する。
【背景技術】
【０００２】
有限体（finitefield）に対するＥＣ（Elliptic Curve）暗号法では、加算と、乗算と、二乗と、反転（inversion）の算術演算が必要となる。さらに、体（field）の標数が２でない場合には、減算も必要になる。例えば符号定数の計算では、モジュラ算術演算も必要になるが、このような演算は有限体の演算ほど必要にならない。例えばＥＣ暗号法では、モジュラおよび有限体演算、加算、減算、乗算、反転の完全な補集合（fullcomplement）が必要になる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
暗号法のための体のサイズは比較的大きくなる傾向があり、算術演算を許容時間内で実行するために高速の専用プロセッサが必要になる。したがって、高速モジュラ算術プロセッサか、Ｆ２ｎの算術演算をパフォームする専用プロセッサのいずれかが、多数インプリメントされている。特殊目的または専用プロセッサを使用することは、当技術分野では、周知のことである。こうしたプロセッサは一般にコプロセッサと呼ばれ、通常は、ホスト計算システムで利用されており、従って、命令および制御はメインプロセッサからコプロセッサに提供されている。
【０００４】
なかでもＲＳＡが暗号化システムとして慣用されていたが、優秀かつよりセキュアなＥＣ暗号法が登場したため、モジュラ冪法（modular exponentiation）専用のプロセッサの必要性は、薄らいで来ている。ユーザはＲＳＡ暗号法からＥＣ暗号法に移行しているものの、性能およびコストをほとんどあるいは全く犠牲にすることなくこれらの両方の演算をサポートする算術プロセッサに対するニーズがある。
【０００５】
本発明の第１の目的は、有限体算術と整数算術を組み合わせ、ＥＣ暗号法に必要な演算と、例えばＲＳＡ暗号法で必要なモジュラ冪法とを提供するプロセッサを提供することにある。
【０００６】
本発明の第２の目的は、異なる体またはレジスタサイズにスケーリングすることができる算術プロセッサ設計を提供することにある。
【０００７】
本発明の第３の目的は、異なる体サイズで使用することができる算術プロセッサを提供することにある。
【０００８】
本発明の第４の目的は、マルチシーケンス中の複数のステップを同時にパフォームすることによってマルチシーケンス演算実行を高速化するためにスケーリングすることができる算術プロセッサを提供することにある。
【課題を解決するための手段】
【０００９】
本発明によれば、
（ａ）一群の関連する算術演算をそれぞれ実行する複数の算術回路を有する論理演算装置であって、オペランドデータを受信するオペランド入力データバスと、前記算術演算の結果を戻す結果データ出力バスとを有する論理演算装置と、
（ｂ）前記オペランドデータバスおよび前記結果データバスに結合されたレジスタファイルと、
（ｃ）前記ＡＬＵおよび前記レジスタファイルに結合された制御装置であって、算術演算を要求するモード制御信号に応答して前記複数の算術回路の１つを選択し、かつ前記レジスタファイルと前記ＡＬＵの間でデータアクセスを制御することにより、前記レジスタファイルが前記算術回路によって共用されるようにする制御装置とを含む算術プロセッサが提供される。
【００１０】
本発明によれば、有限体回路および整数算術回路を含み、かつ汎用レジスタおよび専用レジスタを備えたプロセッサが提供される。
【００１１】
本発明によれば、有限体算術および整数算術を両方とも実行し、専用レジスタおよび汎用レジスタの両方ならびに算術回路を共用する算術プロセッサが提供される。この目的のために、多項式基底が整数の標準的な基数累乗基底（standard radix-power basis）と同様であるので、有限体ハードウェアについて多項式基底を想定する。
【発明の効果】
【００１２】
本発明によれば、有限体算術と整数算術を組み合わせ、ＥＣ暗号法に必要な演算と、例えばＲＳＡ暗号法で必要なモジュラ冪法とを提供するプロセッサを提供できる。
【００１３】
本発明によれば、異なる体またはレジスタサイズにスケーリングすることができる算術プロセッサ設計を提供できる。
【００１４】
本発明によれば、異なる体サイズで使用することができる算術プロセッサを提供できる。
【００１５】
本発明によれば、マルチシーケンス中の複数のステップを同時にパフォームすることによってマルチシーケンス演算実行を高速化するためにスケーリングすることができる算術プロセッサを提供できる。
【図面の簡単な説明】
【００１６】
【図１】有限体算術および整数算術をパフォームする算術プロセッサアーキテクチャのブロック図である。
【図２】図１に示すＡＬＵ（arithmetic logic unit）の概略ブロック図である。
【図３】有限体算術および整数算術をパフォームする算術プロセッサアーキテクチャの代替実施形態のブロック図である。
【図４】図３に示すＡＬＵの概略ブロック図である。
【図５】（ａ）、（ｂ）、および（ｃ）は図２に示すＡＬＵのビットスライスの実施形態のブロック図である。
【図６】図５に示すビットスライスの有限体乗算器の回路図である。
【図７】算術インバータのブロック図である。
【図８】組み合わせた有限体／整数乗算器の回路図である。
【図９】図１のマルチビットＡＬＵの実施形態を示す概略ブロック図である。
【図１０】図９のマルチビット有限体乗算器の回路図である。
【発明を実施するための形態】
【００１７】
図１を説明する。算術プロセッサの一実施形態は一般的に参照番号１で示してある。当然のことであるが、この算術プロセッサは総合計算システム中の汎用プロセッサとともに使用することができ、データはこの計算システムと算術プロセッサの間で交換される。算術プロセッサには、レジスタファイルと呼ばれる一群の汎用レジスタ（ＧＰ）２が含まれている。レジスタファイルはＥＣの点加算（point addition）、点倍加（point doubling）などのための中間記憶域として使用することができるものである。一群の汎用レジスタ２はデータ入力またはオペランドバス６を介してＡＬＵ（arithmeticlogic unit）４と通信を行なっている。ＡＬＵ４にはシェアード（shared）有限体および整数算術回路が含まれている。ＡＬＵ４による計算の結果をレジスタファイル２に書き込むため、データ出力または結果バス１４がＡＬＵ４とレジスタファイル２の間に設けてある。
【００１８】
ＡＬＵ４による計算オペレーションは、算術プロセッサ１のコントローラ８に駐在するマイクロプログラム化命令により制御されている。モード選択コントロール１０は有限体計算またはモジュラ整数計算を選択するために用意してある。体サイズ制御１２も、ＡＬＵ４を初期設定して、種々のオペランドベクトルサイズに適応させるために用意してある。そこで、コントローラ８はなかんずく次のタスク、すなわち、適正な算術モードおよび演算をＡＬＵ４に提供するタスクと、レジスタファイル２とＡＬＵ４の間のデータアクセスをコーディネートするタスクと、使用される適正な体のサイズをＡＬＵ４に提供するタスクとをパフォームする。
【００１９】
汎用レジスタは、少なくとも予想可能な最大のＦ２ｍＥＣ暗号システムをハンドルするだけのビット幅を有するように選択される。これら汎用レジスタは整数モジュラ算術で必要なビット長をサポートするために、組み合わせることができる。例えば、レジスタファイル２の単一レジスタのビット幅が５１２ビット幅である場合に、単一の２０４８ビットＲＳＡ量の記憶域を提供するため、４つのレジスタを使用することができる。これら汎用レジスタには、データのブロックがロードされ、例えば、２０４８ビットの計算をブロック単位で行い、ついで、再組み立てして、全幅結果（full width result）を得ることができる。典型的には、算術プロセッサ１は既存のホストコンピュータシステムで利用され、コントローラ８はこのホストコンピュータシステムから制御信号を受信し、適正なホストバスインタフェースを介して、ホストデータバスにデータを通信する。このようなインタフェースの詳細は当業者とって周知のことであり、説明は省略する。
【００２０】
図２を説明する。ＡＬＵ４には、幾つかの特殊レジスタ１６と、複数のサブＡＬＵ１８と、出力データバス３０と、コントローラ２０とが含まれている。複数のサブＡＬＵ１８には組み合わせロジックおよび算術回路が含まれていて、組み合わせロジックおよび算術回路は、特殊レジスタからデータバス２８を介して各サブＡＬＵに入力された１つ以上のビットをオペレートする。出力データバス３０はサブＡＬＵ１８と特殊レジスタとの間に設けてある。コントローラ２０は、なかんずく、次のタスク、すなわち、計算オペレーション中の各ステップを通してＡＬＵ４を順序づけるタスクと、特殊レジスタ１６からの制御ビットを監視するタスクと、使用してある体のサイズを決定するためにカウンタを制御レジスタ２２に実装するとともに、プロセッサハードウェアを設計し直さずに、プロセッサ１が異なる体サイズに対して使用することができる機構を実装するタスクとをパフォームする。これらの機能を提供するため、特殊レジスタ１６の制御ビット２６は制御ビット入力２４としてコントローラ２０に供給される。特殊レジスタ１６は、全て、個別にアドレス可能になっている。コントローラ２０はレジスタファイルから入力バス６を介してサブＡＬＵ１８または特殊レジスタ１６に入力されたデータも制御する。これらサブＡＬＵは、単一のビットにオペレートすることができ、複数のビットに一度にオペレートすることができる。これらのコンポーネントは後程より詳細に記述する。
【００２１】
図３を説明する。算術プロセッサの代替例は参照番号１′で示してある。本実施形態では、別個の有限体装置３４および整数モジュラ算術装置３６を提供する。このプロセッサは、レジスタファイル２′と、データ入力バス６′と、データ出力バス１４′と、コントローラ８′も含むが、制御１３ａおよび１３ｂがそれぞれコントローラ８′から各ＡＬＵ３４および３６に提供される。
【００２２】
図４を説明する。図４は図３のＡＬＵ３４および３６をより詳細に示す。ＡＬＵ３４および３６には、それぞれ、特殊レジスタ１６′ａおよび１６′ｂと、コントローラ２０′ａおよび２０′ｂとが含まれている。ＡＬＵ３４および３６には、それぞれ、サブＡＬＵ１８′ａおよび１８′ｂが含まれている。したがって、この実施形態では、特殊レジスタ１６′ａおよび１６′ｂと、算術および制御回路は、当然、共有されない。サブＡＬＵ１８′ａのうちの１つ以上のサブＡＬＵ１８′ａは、協働して、シフト左／右とＸＯＲシフトの機能を実行し、サブＡＬＵ１８′ｂのうちの１つ以上のサブＡＬＵ１８′ｂは、協働し、任意選択で、桁上げ保存技術または桁上げ伝搬（carry propagation）を使用して、整数加算および整数減算の機能を実行する。
【００２３】
図２を説明する。サブＡＬＵ１８は、特殊レジスタ１６から供給されたオペランドに対して、次の論理機能、すなわち、ＸＯＲと、シフト左／右と、ＸＯＲシフトと、整数加算と、整数減算を実行する。これらの機能は、１つのサブＡＬＵ１８か、マルチプル・サブＡＬＵに含めることができる。マルチプル・サブＡＬＵ１８を設けることにより、当該プロセッサは複数の演算（例えば、有限体反転）を同時にパフォームすることができる。
【００２４】
図５を説明する。図５は図２のＡＬＵ４のビットスライスを詳細に示す。図５ａの４１は、当該ビットスライスを示す。次の考察では、ビットスライス４１と関係付けをしたロジック回路と関連して、各特殊レジスタのセルを相互接続する、と言う。ビットスライスに含まれたロジック回路は、一般的に、図２に示すようなサブＡＬＵ１８のうちの１つで表される。ビットスライスの構成は、Ｎビットレジスタに対しては、Ｎ回繰り返えすことができる。さらに、明確にするため、Ｎをレジスタ内のセル数と定義し、レジスタ内の個別のセルを例えばＡｉという。ここで、０≦ｉ≦Ｎ−１であり、ＡＮ−１は特殊レジスタの最も右にあるセルである。レジスタの内容は小文字で参照され、例えば、長さｎのビットベクトルＡは、ａ０をＬＳＢとして、ビットにａ０，…ａｎ−１と番号が付けられることになる。ここで、特殊レジスタには特定の名前が付けられているが、これらのレジスタは、後程説明するが、実行されている算術演算に依存して異なる機能をとることができる、ことに留意されたい。
【００２５】
図５の特殊レジスタ１６に含まれるレジスタとしては、乗算演算中に、例えば、被乗数および乗数を個々に保持するための一対のオペランドレジスタＡ４２およびＢ４４と、累算器レジスタＣ４６と、モジュラスレジスタＭ４８と、桁上げ拡張（carry extension）レジスタＣext５０（整数算術で使用される）とがある。
【００２６】
これらのレジスタは、その中にロードされたビットベクトルの個々の２進数を保持するため、Ｎ個のセルを有する。これらのレジスタはシフトレジスタであるのが好ましい。図２に示すサブＡＬＵ１８は、後程説明するが、図５のブロック５２の回路により実装することができる。
【００２７】
乗算
ＡＬＵ４のオペレーションは、有限体乗算のような具体的な算術演算を参照することにより最も良く理解することができる。ここで、２つの元ａおよびｂの積Ｃを考察することにする。ここで、ａおよびｂはビットベクトルであり、ｂは多項式表現でｂ＝（ｂ０，…ｂn-1）の形態となり、ａは多項式表現でａ＝（ａ０，…ａn-1）の形態となる。モジュラスビットベクトルｍは、ｍ＝（ｍ０，…ｍｎ）の形態を有する。モジュラスレジスタは、モジュラスを表すのに必要なビット数より１ビット多い、ことに留意されたい。あるいはまた、最上位ビットｍｎが１であるので、この最上位ビットを暗黙に定義することができ、ｍを（ｍ０，…ｍn-1）で表すこともできる。Ｆ2nにおいて、乗算は、次のような疑似コードにより明確に記述される一連のステップとして実装することができる。
【００２８】
Ｃ＝０｛Ｃ-1＝０｝
For ifrom n-1 to 0 do
For jfrom n-1 to 0 do ｛ｃｊ＝ｃi-1＋ｂn-1ａi＋ｃn-1ｍｊ｝
この乗算を実行する際には、ＭＳＢ（most significant bit）からＬＳＢ（least significant bit）の順に、被乗数と乗数のｂｉの各ビットとの部分積を形成する。その前の部分積のＭＳＢがセットされた場合には、部分積はモジュラスによって簡約（reduce）される。
【００２９】
乗算の実装は、１×Ｎ乗算器を逐次使用することによって行なうことができ、この場合、上記疑似コードの内側の「ｆｏｒ」ループはパラレルに実行される。各セルがそれぞれ２進数ｍｉの１つを含むように、モジュラスレジスタＭには、ＭＳＢｍｎを剥ぎ取ったモジュラスビットベクトルｍがロードされる。図示の実装では、ビットｍｉは、ベクトルのＭＳＢを最も左側のビットとして、左から右に配列されている。すなわち、セルＭn-1はビットｍn-1を含む。Ｎ≠ｎである場合、スティルビット（still bit）Ｍn-1はＭN-1にストアされる、すなわち、データは左寄せされる。各セルが個々に２進数ａｉまたはｂｉの１つを含むように、シフトレジスタＡおよびＢには、有限体元（finitefield element）ビットベクトルａおよびｂがそれぞれロードされる。有限体元ａおよびｂは、左寄せされ、各レジスタにストアされ、乗数レジスタｂのＭＳＢが常に左境界セルのビット、すなわち（ａn-1，ａn-2，…ａ０）および（ｂn-1，ｂn-2，…ｂ０）で利用可能になっている。ベクトルａおよびｂの長さがレジスタの長さより短い場合には、残りのセルには０がパディングされる。以上、図２に示すコントローラ２０によって一般的に実行される。逐次乗算（被乗数を逐次小さくするなど）の他の構成も可能であるが、そのような構成では、体のサイズに柔軟性を持たせることができないし、同様に、制御ビット位置を固定することができない。この乗算アルゴリズムを対応して変化させれば、ＬＳＢからＭＳＢへのビット順序づけも可能である。
【００３０】
ここでは、ＡＬＵ４のビットスライス４１は、有限体において乗算を実装するために、記載されている。ビットスライス４１は第１および第２のコントローラブル加算器５４および５６を含み、第１および第２のコントローラブル加算器５４および５６は、それぞれ、ＸＯＲ機能を有する。レジスタＢの最上位のセルＢN-1は、加算制御信号ｂn-1５７を第１の加算器５４に供給する。第１の加算器５４への入力５８および６０は、レジスタセルＡｉおよびアキュムレータセルＣｉから得られる。第１の加算器５４からの出力６２は、モジュラスレジスタセルＭｉからの入力６４とともに、第２の加算器５６の入力に接続されている。加算器５４は出力６２＝入力６０＋（入力５８および制御５７）という演算をパフォームする。この演算を図５（ｂ）に詳細に示す。
【００３１】
ついで、第２の加算器５６からの出力はアキュムレータセルＣｉに接続されている。第２の加算制御信号６６はアキュムレータＣ４６の最上位のセルＣＮ−１から得られる。アキュムレータＣの最上位のビットＣＮ−１がセットされたとき、当然に、モジュラスベクトルｍによるアキュムレータＣでの部分積のモジュラ簡約が、第２の加算制御信号６６により実装される。図５（ｃ）に詳細に示すように、加算器５６は、出力＝入力６４＋（入力６２および制御６６）という演算を行う。Ｂレジスタはクロックシフトレジスタである。コントローラ２０から供給することができるクロック信号ＣＬＫ１ ６８は、部分積が計算される度に、このレジスタの内容を左にシフトさせる。
【００３２】
図６を説明する。図６は図５のビットスライス４１の詳細な回路実装を示す。この回路実装は有限体乗算を行なうためのものであって、参照番号７０で示す。図６のビットスライスｉ、７０を説明する。図６では、説明のために、ビットスライスは３つしか示していない。セルａｉは、ＡＮＤゲート７２により、加算制御信号ｂｎ−１とＡＮＤ演算される。ＡＮＤゲート７２の出力７４は、アキュムレータＣの隣接するセルＣｉ−１からの入力７８とともに、ＸＯＲゲート７６の入力に接続される。よって、項「ｃi-1＋ｂn-1ａi」の計算が実装される。項「ｃｎ−１ｍｊ」は、ＡＮＤゲートを利用して、信号ｃｎ８０とｍｉ８２をＡＮＤ演算することにより、実装される。ＡＮＤゲートの出力８６は、ＸＯＲゲート７６の出力８８とともに、ＸＯＲゲート８４の入力に接続される。ＸＯＲゲート８４の出力９０は、セルＣｉ９２に接続される。よって、式「ｃｊ＝ｃi-1＋ｂn-1ａi＋ｃｎ−１ｍｊ」が実装される。この汎用の逐次乗算器により、２つのｎビット有限体元の積がｎクロックサイクルで生成されることになる。同期カウンタは、コントローラ２０に含めることができるものであって、繰返し回数の制御を行うものが好ましい。以上の記述は、加算器５４が整数加算器のビットスライスであって、加算器５６が整数減算器のビットスライスであるときに、整数モジュラ乗算に適用される。このことは後程説明する。
【００３３】
加算
有限体Ｆ２ｎ中の乗算に関連して、回路を説明したが、その他の計算オペレーションも容易にパフォームすることができる。有限体加算は桁上げが生じないので、この点で、整数算術より有利である。有限体サム（sum）の計算では、有限体中の２つの元ａおよびｂの加算が、単に、ａとｂのＸＯＲであるので、ＸＯＲゲートを注目レジスタの各セルに導入するだけでよい。したがって、図５に戻ると、入力１００はセルＢｉから第１の加算器５４に供給され、第２の加算器５６は簡約に使用される。ついで、加算器５４からの出力はセルＣｉに直接書き込まれる。オペランドがレジスタａおよびｂに移動された後で、単一のクロックサイクルで、加算をパフォームすることができる。その加算をＡＬＵでパフォームするのは可能であり、その結果をレジスタファイルの汎用レジスタにライトバックするのも可能である。整数加算では、加算器５４は整数加算器のビットスライスであり、整数加算結果に基づきモジュラオーバフローか否かを検査しなければならない。この状態が生じた場合には、整数減算器のビットスライスである加算器５６は、その結果を簡約するのに用いられる。
【００３４】
二乗
ある数を二乗するには、異なる２つの数の乗算と同じ時間でパフォームすることができる。多項式基底における二乗は、特定の既約（irreducible）が二乗展開と明示的に結線された（hardwired）場合は、単一のクロックサイクルでパフォームすることができる。あるいはまた、同じ入力を乗算して二乗をパフォームすることができる。
【００３５】
反転
Ｆ２ｎの有限体元の反転は、ユークリッドの互除法を使用してパフォームすることができ、また、追加のコントロールロジックを有する４つの特殊レジスタを利用してパフォームすることができる。この反転は、シフトが加算と同時に行われる場合（これは加算の出力を次のレジスタセルに結線することによって容易に実装される）には、２ｎサイクルで完了する。
【００３６】
この反転で使用されるレジスタは、Ａ、Ｂ、Ｍ、およびＣである。便宜上、これらのレジスタを概略的に図７に示す。ＭにはＵＬ、ＣにはＬＬ、ＡにはＵＲ、ＢにはＬＲとラベル付けがしてある。再度、この反転を、ビットスライス１１０に関連して記述することができる。
【００３７】
反転のオペランドは、一般に、反転する元ｇと、既約多項式ｆまたはモジュラスｍ（後述）と、ビットベクトル「０」と、ビットベクトル「１」である。ＵＬレジスタ１１６にはｆまたはｍがロードされる。ＬＬレジスタ１１８にはｇがロードされ、ＵＲレジスタ１１２には「０」が、ＬＲレジスタ１１４には「１」がロードされる。ＵＲレジスタ１１２およびＬＲレジスタ１１４では、セルＵＲｉおよびＬＲｉはＸＯＲゲート１２０でＸＯＲ演算されて、出力１２２が生じる。制御信号１２４は、可能な３つの入力のうち１つがセルＵＲｉおよびＵＬｉに書き込まれるかどうかを決定する。入力は隣接するセルまたは出力１２２からの左または右シフトである。制御信号Ｂは後程記載する状態表によって決定される。ＵＬレジスタ１１６またはＬＬレジスタ１１８では、セルＵＬｉおよびＬＬｉはＸＯＲゲート１２６でＸＯＲ演算されて、出力１２８が生じる。制御信号１３０は、可能な２つの入力のうち１つがセルＵＬｉおよびＬＬｉに書き込まれるかどうかを決定する。入力は隣接するセル（ｉ−１）または出力１２８からの左シフトである。この場合も、制御信号１３０は後程記載する状態表によって決定される。
【００３８】
制御変数をＵＬレジスタの長さｋｕと、ＬＬレジスタの長さｋｌと仮定したとすると、Δ＝ｋｕ−ｋｌとなる。値ｋｌおよびｋｕは、好ましくは、同期ダウンカウンタで実装され、Δは好ましくは同期アップ／ダウンカウンタで実装される。カウンタレジスタｋｕ、ｋｌ、およびΔも用意されている。ＵＬおよびＬＬレジスタは左シフトレジスタであり、ＵＲおよびＬＲレジスタは、ともに、左および右シフトレジスタである。
【００３９】
さらに、カウンタレジスタでは、Δには０がロードされ、ｋｕはｎに初期化される。制御ビットラッチは、「１」がアップカウントを示し、「０」がダウンカウントを示すトグル機能を有する。Ｕ／Ｄ制御は、最初、「１」にセットされる。この場合、ＡＬＵで反転を実行する制御装置に含まれるシーケンサは、次のような出力を有する。
【００４０】
Deckl デクリメントｋｌ ｋｌ
Decku デクリメントｋｕ ｋｕ
decDelta デクリメントΔ
incDelta インクリメントΔ
toggle トグルアップ／ダウン
lsUL 左シフト左上レジスタ
lsLL 左シフト左下レジスタ
lsUR 左シフト右上レジスタ
lsLR 左シフト右下レジスタ
rsUR 右シフト右上レジスタ
rsLR 右シフト左下レジスタ
outLR 出力右下レジスタ
outUR 出力右上レジスタ
dadd-lsLL ダウンＸＯＲおよび左シフト左下レジスタ
uadd-lsUL アップＸＯＲおよび左シフト左上レジスタ
インバータのオペレーションの概要を表す状態表は次のようになっており、ＭｕおよびＣｌはそれぞれレジスタＵＬおよびＬＬの上位ビットであり、ＭｕおよびＣｌは現在の状態を決定する。レジスタおよびカウンタ上でアクションがパフォームされると、これによりインバータは新しい状態となる。このプロセスは、ｋｕまたはｋｌが０になるまで繰り返され、右レジスタＲＬまたはＲＵの一方はｇ−１を含み、もう一方はモジュラス自体を含むことになり、これは、後続の乗算または反転演算で使用するために、レジスタｍにリストア（restore）することができる。
【００４１】
【表１】
【００４２】
整数算術
多項式表現と整数表現は非常に良く似ていることから、ＡＬＵでハードウェアを共有することが可能でなる。加算では、整数算術は、桁上げが必要であることから、複雑になるだけである。ＡＬＵの整数算術演算は、例えば乗算演算を利用すれば、最もよく説明することができる。
【００４３】
疑似コードで表した次の一連のステップを参照して、Ｚにおける乗算を説明する。前述したのと同様に、ａおよびｂは乗算されるビットベクトルであり、ｃはａとｂの積であり、Ｃ＝（ｃ０，ｃ１，…，ｃｎ−１）である。
【００４４】
Ｃ＝０
Ｍ＝０
For ifrom 0 to n-1 do
Ｃext←Ｃ
For jfrom 0 to n-1 do
ｃｊ＝（ｂｉ（ａｊ）＋ｍｊ＋ｃｊ）mod２
ｍj+1＝（ｂｊ（ａｊ）＋ｍｊ＋ｃｊ）／２
ここで、
Ｃｅｘｔ←Ｃ:For j from n-1 to 0 do
ｃｊ−１＝ｃｊ
ｃｊ−１ｅｘｔ＝ｃｊｅｘｔ
となる。
【００４５】
同様に、このようにすれば、ＸＯＲを減算器で置換し、しかも、ｍレジスタに素数をロードした場合には、整数 modulo ｐ（integers modulo p）を反転させることができる。改善策であるが、桁上げ保存方法を採用することにより、桁上げ伝搬を遅らせることができる。
【００４６】
図６の実施形態で説明した有限体乗算の場合のビットスライス７０を修正して、整数表現に対する乗算を含むようにすることができる、ことを観測することができる。注意すべきことであるが、整数乗算では、レジスタには、ビットベクトルがＦ２ｍとは逆順でロードされる、すなわち、レジスタの最左端のセルがビットベクトルのＬＳＢを含む。整数乗算では、逐次（successive）部分積の間で、桁上げを実装する必要があり、さらに、部分積がモジュラスで簡約されていないので、逐次部分積の加算による桁上げを供給しなければならない。そこで、アキュムレータレジスタＣが拡張してあり、図５に示すように、新しいレジスタＣｅｘｔ４９が設けてある。各部分積が形成される前に、アキュムレータＣの最下位ビット（セルＣＭ）を拡張レジスタＣｅｘｔの最上位ビット（セルＣｅｘｔｌ）にシフトし、ついで、アキュムレータＣおよびＣｅｘｔは両方ともＬＳＢに向けて１ビットだけシフトされる。最終結果はＣおよびＣｅｘｔで獲得され、Ｃｅｘｔには、当該積の低位ビットが含まれる。このことは、上記オペレーションＣｅｘｔ←Ｃで表される。
【００４７】
図８を説明する。図８はビットスライス１７０を示す。ビットスライス１７０は図６のビットスライス７０に類似している。したがって、同様のコンポーネントは、識別するために、図６の説明で使用した参照番号を１００番台にして使用することにする。つまり、参照番号７０は１７０となる。図８の編成が図６と異なる点は、モジュラスレジスタｍが桁上げレジスタとして使用され、モード選択信号Ｚ／Ｆ２ｍ１７１が提供されるという、２つの重要な点である。
【００４８】
ここで、項ｃｊ＝ｃｊ−１＋ｂｉａｉ＋ｃｎ−１ｍｊは、既に説明した有限体乗算でそうであったように、制御信号ｂｍとレジスタセルＡｉの内容との積で実装され、この積はＡＮＤゲート１７２で実装される。ＡＮＤゲート１７２の出力１７４はレジスタセルｃｊ−１の内容とＸＯＲゲート１７６によりＸＯＲ演算され、参照番号１５８で示す出力項ｃｊ−１＋ｂｉ（ａｉ）が生成される。この出力信号は、ＡＮＤゲート１６０から得られた参照番号１８５で示す項ｃｎ−１（ｍｊ）と、ＸＯＲゲート１８４を使用してＸＯＲ演算され、項ｃｊが生成される。さらに、積’ｂｉａｉ，ｃｊ−１’１６２と、積（ｃｊ−１＋ｂｉａｉ，ｍｊ）１６３とのサム（sum）から、桁上げ項ｍｉが生成され、セルｍｉ１８２に書き込まれる。積の項１６２および１６３はＡＮＤゲート１６４および１６６によってそれぞれ実装される。積の項１６２と１６３のサムはＯＲゲート１６７によって実装される。
【００４９】
モード選択信号Ｚ１７１は、桁上げ入力信号ｃｎ１８０とＯＲ演算され、クロック信号１６９とＡＮＤ演算１６８される。したがって、Ｚ＝０をセットすることにより、有限体算術が実装され、Ｚ＝１をセットすることにより、整数算術が実装される。
【００５０】
図８は、図６で既に説明した有限体乗算を、組合せ有限体／整数乗算器に変換するのに必要な修正を示す。乗算の低位のビットを集めるため、出力レジスタＣが拡張されることに留意されたい。Ｚにおける計算はモジュラスなしでパフォームされるので、モジュラスレジスタＭは、部分積を簡約するためではなく、桁上げのホルダとして使用される。制御信号Ｚ／Ｆ２Ｍ１７１は、ＡＬＵのための整数乗算回路をイネーブルにする。
【００５１】
最終桁上げ伝搬（finalcarry propagation）は、マンチェスターキャリーチェーン（Manchester carry chain）によって提供することができ、レジスタ長が長いことから、１レイヤまたは２レイヤの桁上げスキップ機構によって拡張可能である。さらにｎサイクルだけクロックすることも可能であり、桁上げ保存加算器が桁上げを完全にマージすることが可能である。
【００５２】
１つの入力はその入力において条件付きで補数をとることができ、しかも、加算器のＬＳＢで「ホット」キャリインが行われる場合には、２の補数の減算は、桁上げ伝搬加算器で実装することができる。
【００５３】
乗算時のリップル桁上げは、桁上げスキップにより改良したとしても、許容できなくなるが、この桁上げ伝搬は、桁上げ保存加算器を使用すれば、ほぼ完全に除去することができる。このようにすると、部分積が冗長表現されるが、乗算が完了した後は解決される。
【００５４】
さらに別の実施形態では、ＡＬＵ４は、図９に示すように、計算速度が線形に増加するように修正することができる。これは、特殊レジスタ１６′からの連続ビットを一度に処理し、修正したサブＡＬＵ１９０で示す追加回路を実装し、図９に示すようにインクリメント加算を処理することによって達成される。複数のビットを処理すると、速度が線形増加することになる。例えば、計算が順次にパフォームされる場合は、その順序中の２つ以上のステップを同時に実行することができる。この場合、コントローラ２０′は特殊レジスタ１６′からの２ビット以上の制御ビット１９４を処理することになり、制御装置の入力１９２は図９にマルチビットラインとして示す。
【００５５】
有限体に対して一度に２ビット実行する乗算器（two-bit at a time multiplier）の回路図を図１０に示す。この実装では、ビットスライス２００はその数がＸＯＲゲート２１０の数の２倍であり、当該加算の２つの項を実装している。この乗算器は乗数から２ビットをとり、被乗数ａｉおよびａｉ−１を２回だけ隣接してシフトすることにより加算し、モジュラスＭｉおよびＭｉ−１を２回だけ隣接してシフトすることにより簡約する。このようにすると、モジュラス簡約（modulusreduction）で連続する２つの部分積が同時に生成され、したがって、全計算時間を半分にすることができるという効果がある。
【００５６】
特殊レジスタの上位（top）ビットがコントローラ２０または２０′用の制御ビットとして使用される、ことに留意されたい。このようにすると、オペランドがレジスタにロードされると、左揃えされ、したがって、制御が常に固定ビット位置から得られるという利点がある。しかし、その他のビット例えば下位（bottom）ビットを制御ビットとして使用することもできる。しかし、このようにすると、ハードウェアが複雑になることもある。
【００５７】
この場合も、Booth（または、修正Booth）記録などのオプションが可能となるので、マルチビット演算の計算速度がさらに線形的に増加する。
【００５８】
このようなＡＬＵは汎用レジスタに対して簡単な算術演算をパフォームする能力を有するものと仮定している。他の例のＡＬＵは全ての算術をＡＬＵ内部レジスタに対してパフォームするものであり、汎用レジスタはこれらのレジスタとの間でリード（read）およびライト（write）のみを行う能力を有する。
【００５９】
このようなＡＬＵの機能には、リップル桁上げや、桁上げスキップ加算と桁上げ完了の組合せなど、何らかの桁上げ伝搬方法を利用した、整数加算が含まれる。
【００６０】
このようなＡＬＵは、有限体加算で使用される単純なＸＯＲ機能も提供する。整数および有限体表現（ビット順序）が逆であるので、体から整数への変換と、整数から体への変換に使用されるビット逆転（bit reversal）機構を設けると有利である。２つのシフトレジスタの頂部どうしを接続することにより、ｎクロックサイクルでこの機能が提供される。ここで、ｎは算術オペランドの長さである。
【００６１】
本明細書で与えた一般的なアーキテクチャは、ＥＣとモジュラ指数算術との間でレジスタファイルを共用するだけでなく、共用制御レジスタに加えて、特殊レジスタおよび組み合わせロジックも共用する可能性がある。
【００６２】
以上、本発明の具体的な実施形態と具体的な用途について説明したが、種々の修正は、本発明の範囲を逸脱しない限り、当業者にとって可能である。例えば、記載の実施形態では、特定のロジック回路について言及したが、例えば、ド・モルガンの法則を使用して等価な回路を使用することもでき、反転ロジック（inverted logic）が実装された場合には、相補形回路を使用することもできる、ことに留意されたい。さらに、レジスタおよびビットベクトルのオリエンテーション、すなわち、左、右、上、下には、これらの方向の他の編成も含まれる。
【００６３】
本明細書で採用した項および式は、これらのものに限定されるものではなく、例として使用したものであり、これらの項および式を使用したことに、図示および記述した機構またはその一部分の均等物を排除する意図はなく、本発明の範囲内で種々の修正が可能であることを認識されたい。
【符号の説明】
【００６４】
１ 算術プロセッサ
２ レジスタファイル
４ 有限体／整数エンジン
８ コントローラ
【特許請求の範囲】
【請求項１】
明細書に記載の発明。
【請求項１】
明細書に記載の発明。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１１−１３４３４６（Ｐ２０１１−１３４３４６Ａ）
【公開日】平成２３年７月７日（２０１１．７．７）
【国際特許分類】
【出願番号】特願２０１１−４９６１０（Ｐ２０１１−４９６１０）
【出願日】平成２３年３月７日（２０１１．３．７）
【分割の表示】特願２００７−２４３１０７（Ｐ２００７−２４３１０７）の分割
【原出願日】平成１０年４月２０日（１９９８．４．２０）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
【公開日】平成２３年７月７日（２０１１．７．７）
【国際特許分類】
【出願日】平成２３年３月７日（２０１１．３．７）
【分割の表示】特願２００７−２４３１０７（Ｐ２００７−２４３１０７）の分割
【原出願日】平成１０年４月２０日（１９９８．４．２０）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
[ Back to top ]