JP3939658B2

JP3939658B2 - モジュラー乗算を行うための装置、および、モジュラー乗算を行うための算術演算装置

Info

Publication number: JP3939658B2
Application number: JP2002566769A
Authority: JP
Inventors: エルベ，アスリット; ゼドラック，ホルガー; ジャンセン，ノーベルト; ピエールザイフェルト，ジャン
Original assignee: Infineon Technologies AG
Current assignee: Infineon Technologies AG
Priority date: 2001-02-16
Filing date: 2002-01-24
Publication date: 2007-07-04
Anticipated expiration: 2022-01-24
Also published as: TW550498B; ATE357016T1; EP1360579B1; US20040019622A1; EP1360579A2; US6920473B2; WO2002067108A2; CN1489726A; DE10107376A1; CN1296817C; DE50209713D1; WO2002067108A3; JP2004519052A

Description

本発明は、モジュラー乗算、例えば、ＧＦ（２^ｎ）の楕円曲線のモジュラー乗算を実施するための方法および装置に関するものである。
【０００１】
暗号化は、モジュラー算術のための主な応用の１つである。基本的には、モジュロＮの形態に応じて、２つの暗号化方法に区別される。モジュロが整数の場合は、Ｚ／ＮＺ算術（Ｚ／ＮＺArithmetik）のことを言う。パラメータＮは、素数、または、素数の組み合わせを表している。パラメータＺは、整数を表している。モジュロが２つの素数の組み合わせである場合の例として、ＲＳＡ等式がある：
Ｃ＝Ｍ^Ｅｍｏｄ（Ｎ）
ただし、知られているように、Ｃは、符号化された情報、Ｍは、符号化されていない情報、Ｅは、公開鍵（oeffentliche Schluessel）、そして、Ｎは、モジュロである。
【０００２】
一方、ＧＦ（２ ^ｎ）算術は、モジュロＮ（ｘ）が変数ｘの多項式であることにより特徴づけられている。多項式は、累乗されたｘの和を含み、累乗されたｘには、それぞれ係数が割り当てられている。累乗されたｘの最大指数は、多項式の次数（Grad）として示される。係数が、体（Korper）ＧＦ（２）からのものである場合、ＧＦ（２^ｎ）係数、または、より一般的にはＧＦ（２^ｎ）算術という。ＧＦ（２^ｎ）算術は、例えば、楕円曲線暗号化（Elliptische-Kurven-Kryptographie）に対して使用される。
【０００３】
次数ｎ−１の多項式
【０００４】
【数１】
【０００５】
は、ｎ個の係数ａ_ｎ−１,..., ａ_０により規定され、ａ_ｉは、集合（Menge）ＧＦ（２）からのものである必要があり、ａ_ｎ−１は、定義により１であるので、
ｆ（ｘ）＝１^＊ｘ^ｎ−１＋ａ_ｎ−２ ^＊ｘ^ｎ−２＋...＋ａ_１ ^＊ｘ^１＋ａ_０ ^＊ｘ^０
となる。
【０００６】
体ＧＦ（２^ｎ）は、次数ｎの既約多項式、および、ｎ−１未満またはｎ−１に等しい次数のＧＦ（２^ｎ）の多項式により規定される。
【０００７】
ＧＦ（２^ｎ）に関する２つの要素、すなわち、多項式の加算は、長さｎをもつ上記２つの要素の、係数ベクトルのＸＯＲ結合（XOR-Verknuepfung）によって規定されている。
【０００８】
ＧＦ（２^ｎ）に関する２つの要素、すなわち多項式の乗算は、多項式をＧＦ（２^ｎ）について乗算すること、および、続いて、得られる積を、次数ｎの既約多項式Ｎ（ｘ）をモジュロ（法）として約分すること（Reduzieren）により達成される。この多項式Ｎ（ｘ）は、相当する体を定義する。
【０００９】
それゆえ、積としての多項式、つまり、第１多項式ｆ（ｘ）と第２多項式ｇ（ｘ）との乗算により生じる多項式に対してモジュラー演算を実施するためには、除数としてモジュロ多項式Ｎ（ｘ）を用いた多項式の除算を行う必要がある。それゆえ、ｆ（ｘ）＊ｇ（ｘ）ｍｏｄＮ（ｘ）の結果は、多項式の除算により生じる残りの多項式（Restpolynom）となる。
【００１０】
Ｚ／ＮＺと、ＧＦ（２^ｎ）との双方についてのモジュラー乗算を効果的に実施するための様々な方法を説明する前に、Ｚ／ＮＺと、ＧＦ（２^ｎ）との双方に関するモジュラー累乗法は、知られている平方および乗算アルゴリズム（Square-and-Multiply-Algorithｍ）を用いて、乗算に分解できる。これにより、以下の等式を解くことができる：
Ｃ（ｘ）＝（Ｍ（ｘ））^ＥｍｏｄＮ（ｘ）
平方および乗算アルゴリズムは、指数Ｅが２の累乗の和に分解されるということに基づいている：
【００１１】
【数２】
【００１２】
以下の例は、このことを明らかにする。二進法表示では、
Ｅ＝１０１１
となる。
従って、以下の関係となる。
Ｃ（ｘ）＝Ｍ（ｘ）^（１^＊２^３＋０^＊２^２＋１^＊２^１＋１^＊２^０）ｍｏｄＮ（ｘ）
従って、
Ｃ（ｘ）＝（Ｍ（ｘ））^８＊（Ｍ（ｘ））^０＊（Ｍ（ｘ））^２＊（Ｍ（ｘ))^０ｍｏｄＮ(ｘ)
となる。
【００１３】
Ｚ／ＮＺ算術においても上述の等式は当てはまるが、その場合、Ｍ（ｘ）の代わりにＭであり、Ｎ（ｘ）の代わりにＮである点で異なる。
【００１４】
モジュラー乗算を計算するために知られている、効果的で頻繁に使用される方法は、モンゴメリー乗算として知られており、例えば、「応用暗号化誌」（"Handbook of Applied Cryptography", Menezes, von Oorschot, Vanstone, CRC Press, ６００〜６０３ページ）に記載されている。モンゴメリー簡約（Montgoｍery-Reduktion）は、古典的なモジュラーの簡約工程を明示的に行うことなく、モジュラー乗算を効果的に実施できる技術である。一般的に、モンゴメリー簡約では、除算演算は、簡単な桁送り演算（Verschiebungsoperationen）によって表現される。
【００１５】
一方、モンゴメリー乗算演算を有限体のＧＦ（２^ｎ）に拡張する（Erweiterung）ことも知られている。この拡張は、「ＧＦ（２^ｋ）におけるモンゴメリー乗算」（"Montgoｍery Multiplicationin ＧＦ（２^ｋ）", Koc, Azar, Designs, Codes and Cryptography、１４巻、１９９８年、５７〜６９ページ）に記載されている。この拡張は、さらに、「有限体Ｚ／ＮＺおよびＧＦ（２^ｎ）のための測定可能な統合乗算設計」（"Ａ Scalable and Unified Multiplier Architecture for Finite Fields Ｚ／ＮＺandＧＦ(２^ｎ)",Erkay Savas他、Cryptographic Hardware and Eｍbedded Systeｍs (CHESS２０００),２８１〜２８９ページ,Springer Lecture Notes）に記載されている。
【００１６】
Ｚ／ＮＺまたはＧＦ（２^ｎ）のモンゴメリー乗算の不利な点は、モジュラー簡約のための除算演算は、桁送り演算により回避することができるがハードウェアへの実装が困難であって、ハードウェアのモジュラー乗算演算の速度を上げるための先読み法が使用されないことにある。
【００１７】
ドイツ特許第３６３１９９２号Ｃ２（ＤＥ３６３１９９２Ｃ２）（日本国特許第３０１４３９１号）に、Ｚ／ＮＺのモジュラー乗算を、乗算予測方法（乗算の先読み法）（Multiplikations-Vorausschau-Verfahrens）と、簡約予測方法（モジュロの先読み法）（Reduktions-Vorausschau-Verfahrens）とを使用することで速く行う方法が開示されている。ドイツ特許第３６３１９９２号Ｃ２に記載されている方法を、本明細書ではＺＤＮ方法（後述）と称することにし、図９を参考にして詳しく説明する。アルゴリズムの開始工程９００の後、広域変数（globalen Variablen）Ｍ，Ｃ，およびＮを初期化する。この目的は、以下のモジュラー乗算を計算するためである：
Ｚ＝Ｍ^＊ＣｍｏｄＮ
Ｍは、乗数を表し、一方、Ｃは、被乗数を示している。Ｚは、モジュラー乗算の結果であり、一方、Ｎは、モジュロである。
【００１８】
このとき、次にすぐ処理する必要のない様々な局所変数（lokale Variablen）は初期化される。続いて、２通りの予測方法を用いる。乗算予測方法ＧＥＮ＿ＭＵＬＴ＿ＬＡでは、様々な先読み規則を用いて、乗算桁送り値Ｓ_Ｚおよび乗算予測パラメータａを計算する（９１０）。このとき、Ｚ用レジスタ（Ｚ−Registers）の最新の内容は、左桁送り演算（Links-Verschiebungs-Operation）によりＳ_Ｚ桁（Ｓ_Ｚ-Stellen）桁送りされる（９２０）。
【００１９】
これとほぼ並行して、簡約桁送り値Ｓ_Ｎおよび簡約パラメータｂを計算するための簡約予測方法ＧＥＮ＿Ｍｏｄ＿ＬＡ（９３０）を実施する。工程９４０において、Ｎ用レジスタの最新の内容、すなわち、Ｎが、桁送りされたモジュロ値Ｎ´を生成するために、Ｓ_Ｎ桁だけ桁送りされる。ＺＤＮ方法の中央３演算数演算（Die zentrale Drei-Operanden-Operation）は、工程９５０において行われる。このとき、工程９２０の後の中間結果Ｚ´は、乗算予測パラメータａが乗算されている被乗数Ｃと、簡約予測パラメータｂが乗算されているモジュロＮ´とに加算される。現状に応じて、予測パラメータａおよびｂは、＋１、０、または、−１の値を有していてもよい。
【００２０】
乗算予測パラメータａが＋１であり、簡約予測パラメータｂが−１である場合には、桁送りされた中間結果Ｚ´に被乗数Ｃが加算され、それから桁送りされたモジュロＮ´が減算される。乗算予測方法が、予め設定されている数より多くの個々の左への桁送りを許可するなら、つまり、Ｓ_Ｚが、ｋとしても示される、Ｓ_Ｚの最大許容値よりも大きい場合、ａは、０に等しい値を有することになる。ａが０に等しく、Ｚ´が、先のモジュラー簡約、つまり、桁送りされたモジュロの先の減算が原因で、まだかなり小さく、特に、桁送りされたモジュロＮ´よりも小さい場合には、簡約を行う必要がない。その結果、パラメータｂは、０に等しくなる。
【００２１】
工程９１０〜９５０は、被乗数の全ての桁が処理される、すなわち、ｍが０に等しく、パラメータｎも０に等しくなるまでずっと実施される。パラメータｎは、桁送りされたモジュロＮ´が、もとのモジュロＮよりもまだ大きいかどうか、あるいは、すでに被乗数の全ての桁が処理されているという事実にもかかわらず、Ｚからモジュロを減算することにより、さらに他の簡約工程を実施する必要があるかどうかを示している。
【００２２】
最後に、Ｚが０よりも小さいかどうかが決定される。Ｚが０よりも小さい場合には、簡約が終了するように、モジュロＮをＺに加える必要がある。これにより、モジュラー乗算の正の結果Ｚが得られる。工程９６０において、ＺＤＮ方法を用いるモジュラー乗算を終了する。
【００２３】
工程９１０において、乗算予測アルゴリズムにより計算される乗算桁送り値Ｓ_Ｚおよび乗算パラメータａは、乗数の位相幾何学（Topologie des Multiplikators）、および、ドイツ特許第３６３１９９２号Ｃ２に記載の予測規則によって生じる。
【００２４】
簡約桁送り値Ｓ_Ｎおよび簡約パラメータｂは、同じくドイツ特許第３６３１９９２号Ｃ２に記載されているように、Ｚ用レジスタの最新の内容を、値２／３×Ｎと比較することにより決定される。本明細書では、この比較方法に、ＺＤＮ方法という名前を付けている（ＺＤＮ＝Ｎの３分の２（ＺＤＮ＝Zwei Drittel Ｎ））。
【００２５】
ＺＤＮ方法では、図９に示すように、モジュラー乗算を、３演算数加算（図９のブロック９５０）に戻す。この場合、計算時間を速めるために、乗算予測方法と同時に簡約予測方法が用いられる。従って、Ｚ／ＮＺのモンゴメリー簡約と比べて、３桁の大きさ（Groessenordnung von 3）の因数によって、計算時間を有利にすることができる。
【００２６】
既に説明したように、ドイツ特許３６３１９９２号Ｃ２に記載されているＺＤＮ方法は、Ｚ／ＮＺ算術に対してのみ有効に作用するものであり、ＧＦ（２^ｎ）算術には適していない。従って、現在のところ、ＧＦ（２^ｎ）算術の、ＧＦ（２^ｎ）に関するモジュラー乗算の速度を速くするために用いられる、計算時間の速い先読み方法はない。
【００２７】
本発明の目的は、ＧＦ（２^ｎ）のモジュラー乗算を迅速に行うための概念を提供することにある。
【００２８】
この目的は、特許請求項に記載のモジュラー乗算を行うための装置、または、算術演算装置により達成される。
【００２９】
本発明は、乗算予測方法と簡約予測方法との双方を使用することにより、ＧＦ（２^ｎ）のモジュラー乗算を速く行えるということに基づいている。乗算予測方法では、乗算桁送り値が計算される。乗算予測方法と並行して行われることが有利である簡約予測方法では、簡約桁送り値が計算される。この場合、簡約桁送り値は、乗算桁送り値だけ桁送りされた中間結果の多項式の次数と、実際のモジュロ多項式の次数との差に等しい。乗算桁送り値により累乗されている変数を、中間結果の多項式に乗算する一方、簡約桁送り値により累乗されている変数を、モジュロ多項式に乗算する。これにより、ＧＦ（２^ｎ）算術の３演算数加算が公式化される。そうして、乗算桁送り値だけ桁送りされた最後の中間結果の多項式を被乗数に足し合わせ、次に、更新された中間結果の多項式を得るために、この足し合わされたものから、簡約桁送り値だけ桁送りされたモジュロ多項式を減算することにより、新しい中間結果の多項式を計算することができる。次に、全ての工程を繰り返す。ただし、今度は更新された中間結果の多項式および最後の工程において桁送りされたモジュロ多項式を用いて、全ての部分の積を続けて加算するため、すなわち、乗数の全ての累乗が処理されてしまうまで、全ての工程を繰り返す。
【００３０】
ＧＦ（２^ｎ）算術における変数ｘの累乗の係数が、「０」または「１」のどちらかの値を有していてもよいということにより、３演算数加算は、とりわけ簡易化される。これにより、加算と減算との双方は、簡単なＸＯＲ結合となる。その結果、単にＧＦ（２^ｎ）の加算のための算術装置としての算術演算装置は、加算器を必要とせず、３演算数のビット毎の（bitweise）ＸＯＲ結合のみを必要とする。
【００３１】
双数の算術演算装置、すなわち、Ｚ／ＮＺのモジュラー乗算と、ＧＦ（２^ｎ）のモジュラー乗算との双方を行う算術演算装置の場合、加算器の各ビットのための桁上げを行わない、つまり考慮しないことによって、ＺＤＮ方法のために、既存の３演算数加算器を、ＧＦ（２^ｎ）演算用に簡単に変更できる。
【００３２】
ただし、ＧＦ（２^ｎ）のモジュラー乗算を計算するための本発明に基づく方法は、直列並列構造（Seriell-Parallel-Architektur）を有している。３演算数加算は、好ましくは、常に並行して行われる、すなわち、一般的に、幅１５０〜１１００ビットを有する、加数の全てのビットに対して行われることである。従って、次の連続した、本発明に基づく方法の反復において、新しい部分積が計算され、続く並行した３演算数加算において、既存の中間結果に加えられる。
【００３３】
モジュラー乗算を計算するための本発明に基づく概念は、ＧＦ（２^ｎ）のためのモンゴメリー乗算と比較して、２桁の因数により、速度を最大にできるという長所がある。
【００３４】
本発明に基づく概念の他の長所は、既に提供したＧＦ（２^ｎ）のモジュラー乗算のための効果的な方法により、例えば、ＧＦ（２^ｎ）のＥＣＤＳＡアルゴリズム（ＥＣＤＳＡ＝楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ＝Elliptic Curve Digital Signature algorism）を計算できることにある。このアルゴリズムは、「金融サービス産業のための公開鍵暗号法：楕円曲線Ｄ．Ｓ．Ａ．」（"Public Key Cryptography for the Financial Services Industry： The Elliptic Curve D.S.Ａ.", ANSI X９.６２-１９９８）に記載されている。
【００３５】
楕円曲線暗号化は、整数に関連したモジュラー算術を基礎とする暗号化と比べ、非常に小さな数であっても、類似した安全基準を得られるという点で、好まれている。Ｚ／ＮＺについてのＲＳＡ方法では、１０２４ビット幅数で、確かな安全基準が得られる一方で、ＧＦ（２）についての多項式では、変数ｘの１５０〜３００累乗の次数で、十分に確かな安全基準が得られる。
【００３６】
本発明に基づく他の長所は、モジュラー乗算を計算するための本発明の概念を、ＺＤＮ方法のための既存の算術演算装置に難なく簡単に統合できることにある。なぜなら、実際に長い数の算術演算装置（Langzahlrechenwerk）、つまり、３演算数加算器を、ビット毎の桁上げを抑制することにより、ＧＦ（２^ｎ）に簡単に適合できるからである。ＧＦ（２^ｎ）のための、簡約予測アルゴリズム算術装置および乗算予測アルゴリズム算術装置は、Ｚ／ＮＺのための、簡約予測アルゴリズム算術装置および乗算予測アルゴリズム算術装置とは異なっているが、このことは、算術演算装置の全体的な特性に対しては決定的に重要なことではない。なぜなら、ここでは、たった８または１６ビット幅程度の小さな数の加算、桁送り、または、減算の結果、制御装置とも称される算術装置の集積回路領域（die Chipflaeche）は、長い数を演算する算術演算装置と比較して、すなわち、２０４８ビット幅を十分に越えていてもよい（Ｚ／ＮＺおよびＧＦ（２^ｎ）のための双数の実施）３演算数加算器と比較して、あまり重要ではないからである。
【００３７】
ＧＦ（２^ｎ）についてのモジュラー乗算のための本発明に基づく概念の他の長所は、Ｚ／ＮＺ算術にのみ機能するＺＤＮ方法と比べ、多数の演算を簡易化できることにある。それゆえ、本発明に基づくＧＦ（２^ｎ）モジュラー乗算では、モジュロの２／３倍との比較を行う必要がない。中間結果の多項式の次数とモジュロ多項式の次数との比較により、ＧＦ（２^ｎ）についての比較を簡単に行える。乗算桁送り値の期待値、および、簡約桁送り値の期待値が同一なので、２つの予測方法は相互に切り離されており、その結果、２つの予測方法は、相互に独立して作用することが可能であり、これに伴って、計算時間は速くなる。
【００３８】
本発明の好ましい実施例を、以下に、添付の図を参考にして詳しく説明する。
【００３９】
図１は、ＧＦ（２^ｎ）についてのモジュラー累乗法を具体的に説明するためのフローチャートを示す。図２は、本発明に基づく方法の高レベルのフローチャートを示す。図３は、乗算桁送り値を計算するための、乗算予測方法のフローチャートを示す。図４は、簡約桁送り値を計算するための、簡約予測方法のフローチャートを示す。図５は、ＧＦ（２^ｎ）算術またはＺ／ＮＺ算術のための３演算数加算器の一部を示す。図６は、桁上げ遮断機能（Carry-Abschalt-Funktion）の詳細な図を示す。図７は、Ｚ／ＮＺ-ＧＦ（２^ｎ）算術演算装置のブロック図を示す。図８ａ〜図８ｂは、簡約桁送り値の計算を具体的に説明するための概略的な図を示す。図９は、Ｚ／ＮＺについてのモジュラー乗算を行うためのＺＤＮ方法の概要を示す図である。
【００４０】
図１は、モジュラー累乗法
Ｃ（ｘ）＝（Ｍ（ｘ））^ＥｍｏｄＮ（ｘ）
を、一続きの乗算に分解するための一般的なフローチャートを示す。Ｍ（ｘ）およびＮ（ｘ）は、変数ｘの多項式である。Ｅは、ビット長Ｌ（Ｅ）を有する二進法表示の指数である。
【００４１】
アルゴリズムは、基本的には、指数Ｅのビット、すなわちＥ（ｅ）が１に等しいかどうかを調べるものである。Ｅ（ｅ）＝１である場合、結果として生じるレジスタの現在の内容に、Ｍ（ｘ）を掛け算する。続いてすぐに、モジュロ多項式Ｎ（ｘ）を用いてモジュラー簡約を行う。これに対し、指数のビットが０に等しい場合には、Ｍ（ｘ）を掛け算しない。Ｅ（ｅ）＝１である場合もそうでない場合も、レジスタ内のＣ（ｘ）の最新の内容を、それ自身により乗算、すなわち、２乗し、これに基づいてモジュラー簡約を行う。その結果、指数の桁の標数、すなわちｅは、１だけ上昇される。そうして、繰り返し、指数Ｅのビットが１に等しいかどうかを調べる。このことを、指数Ｅの全ての桁を処理してしまうまで、つまり、ｅ＝Ｌ（Ｅ）となるまでずっと実施する。そうしてからアルゴリズムを終了すると、Ｃ（ｘ）用のレジスタには、モジュラー累乗法の結果が生じている。従って、モジュラー累乗法の中央演算は、被乗数Ｃ（ｘ）に乗数Ｍ（ｘ）を掛けるモジュラー乗算である。
【００４２】
図２は、被乗数に乗数をモジュラー乗算するための本発明に基づく方法の高レベルのブロック図を示す。この方法は、開始ブロック２００から始める。ブロック２０２において、変数ｘの多項式である広域変数Ｍ、Ｃ、および、Ｎを初期化する。次に、ブロック２０４において、中間結果の多項式Ｚを、０に初期化する。ブロック２０６において、制御変数（Laufvariable）ｍを、Ｌ（Ｍ）に初期化する。Ｌ（Ｍ）は、乗数Ｍの長さをビットで表している。従って、Ｌ（Ｍ）は、乗数多項式の次数に相当している。さらに、ブロック２０８において、制御変数ｎを０に初期化する。制御変数ｎの意味については、後で説明する。続いて、乗算予測方法２１０と簡約予測方法２１２とを、好ましくは並行して実施する。乗算桁送り値Ｓ_Ｚを計算するために、乗算予測方法を用いる。好ましくは、乗算予測パラメータａを計算するために、同様に、乗算予測方法を用いることである。
【００４３】
簡約桁送り値Ｓ_Ｎを計算するために、換算予測方法を用いる。好ましくは、換算予測パラメータbを計算するために、換算予測方法を用いることである。
【００４４】
ブロック２１４において、乗算桁送り値Ｓ_Ｚにより累乗されている変数ｘを、実際の中間結果の多項式Ｚに乗算することによって、桁送りされた中間結果の多項式Ｚ´を計算する。
【００４５】
好ましくはこれと並行して、ブロック２１６において、換算桁送り値Ｓ_Ｎにより累乗されている変数ｘを、実際のモジュロ多項式Ｎに乗算することによって、桁送りされたモジュロ多項式Ｎ´を計算する。
【００４６】
次に、ブロック２１８において、本発明に基づく乗算方法の中央演算である、いわゆる３演算数加算を実施する。ブロック２１８において、更新された中間結果の多項式Ｚを計算する。この多項式Ｚは、中間結果多項式Ｚ´を、乗算予測パラメータａが乗算されている被乗数Ｃ、および、換算予測パラメータｂが乗算されている桁送りされたモジュロ多項式Ｎ´に加算することによって得られる。
【００４７】
ブロック２２０において、制御変数ｍが０に等しいかどうか、および、制御変数ｎが０に等しいかどうかを同時に調べる。制御変数ｍが０に等しい場合は、乗数Ｍ（ｘ）の全てのビットが処理されていることを意味している。制御変数ｎが０に等しい場合は、桁送りされたモジュロ多項式Ｎ´が、ブロック２０２のもともとの多項式Ｎと同じであることを意味している。
【００４８】
制御変数ｍが０に等しく、制御変数ｎが０に等しければ、ブロック２２０では、「はい」を応答し、その結果、モジュラー乗算の結果、すなわち、Ｚ（ｘ）を、ブロック２２２に出力できる。従って、モジュラー乗算のためのこの方法は、ブロック２２４で終了する。
【００４９】
これに対し、ブロック２２０にて「いいえ」が応答されれば、このことは、処理されていない乗数のビットがまだ存在しているか、あるいは、モジュロ多項式用のレジスタに保たれるモジュロ多項式Ｎ´が、ブロック２０２で定義されたもともとのモジュロ多項式よりもさらに大きいということを意味している。言い換えれば、このことは、モジュロ多項式用のレジスタに保たれている、最新の多項式の次数は、ブロック２０２で定義されたもともとのモジュロ多項式Ｎの次数よりも大きいことを意味している。この場合には、図２に折り返し線２２６として示すように、乗算予測方法と、簡約予測方法とを改めて実施するために、もとに戻る。Ｚ用レジスタがブロック２０４における初期化により０に設定されている第１工程とは逆に、この場合には、Ｚ用レジスタには、先の工程における３演算数演算２１８の結果が生じている。
【００５０】
この場合、同じく、Ｎ用レジスタには、ブロック２０２で定義されたもともとのモジュロＮはもはや無く、換算桁送り値Ｓ_Ｎだけ桁送りされたモジュロ多項式Ｎ´がある。従って、ブロック２０２で定義されたもともとのモジュロＮ（ｘ）は、第１初期化工程の間だけ、Ｎ用レジスタにある。この場合、反復工程（反復ループ２２６）の間に、Ｎ用レジスタには常に桁送りされたモジュロ多項式、すなわち、簡約桁送り値Ｓ_Ｎにより累乗されている変数ｘが乗算されているモジュロ多項式が存在する。
【００５１】
以下に図３について説明する。図３は、乗算予測方法、すなわち、図２のブロック２１０の詳細な図を示している。この乗算予測方法は、ブロック３００から始まる。広域変数として、図２のパラメータｍ、後でさらに説明する他の制御変数ＣＵＲｋ、および、乗数Ｍが含まれている。このことを、図３のブロック３０２に示す。次に、ブロック３０４において、乗算桁送り値Ｓ_Ｚを０に初期化する。さらに、後でさらに説明する乗算予測パラメータａを、値＝１に初期化する（ブロック３０６）。
【００５２】
次に、ブロック３０８において、現在論議の対象となっているビット、または、現在処理されているｘの累乗の係数が、０に等しいかどうか調べる。ブロック３０８において、現在処理されている乗数のビットが０に等しくないと決定されると、すなわち、ブロック３０８で「はい」を応答すると、制御変数ｍは、ブロック３１０において、１だけ上昇される。さらに、乗算桁送り値Ｓ_Ｚは、同じくブロック３１２において、１だけ上昇される。次に、ブロック３１４において、乗算予測方法、すなわち、乗算予測パラメータａおよび乗算桁送り値Ｓ_Ｚの結果パラメータが出力される。
【００５３】
ブロック３０８において、「いいえ」を応答すると、他の判断ブロック３１６に進む。ここで、制御変数ｍが、乗数Ｍの長さ、つまり、次数よりもさらに小さいかどうかを決定する。さらに、現在の乗算桁送り値Ｓ _Ｚが、パラメータＣＵＲｋより小さいか、すなわち、現在の乗算桁送り値Ｓ _Ｚが、パラメータＣＵＲｋに一致してないか否かを調べる。２つの質問に対して「はい」が応答されると、パラメータｍを１だけ上昇させるために、ブロック３１８に進む。さらに、ブロック３２０において、乗算桁送り値Ｓ_Ｚも１だけ上昇される。これに続いて、乗数Ｍの次数のビットを調べる。このことを、図３において、折り返し線３２２で表している。
【００５４】
これに対し、ブロック３１６にて、ブロック３１６の２つの質問のうち１つに対して、「いいえ」を応答すると、ブロック３２４に進む。このブロック３２４において、乗算予測パラメータａを０に設定する。それゆえ、ブロック３１４に出力される乗算予測パラメータａは、０であっても１であってもよい。そして、乗算予測方法は、ブロック３２６にて終了する。
【００５５】
以下に、乗算予測パラメータの機能形態について説明する。本発明に基づいて使用される乗算予測方法は、０を上回る変数の桁送りによるＧＦ（２ｎ）乗算のための先読みアルゴリズムであり、変数の桁送り数を任意に増やすことはできず、多くても、値ＣＵＲｋに等しいはずである。「ＣＵＲｋ」は、「現在のｋ（"Current ｋ"）」を表し、すなわち、「パラメータｋの現在の値」を意味している。
【００５６】
以下に、例として、係数「１０００１」を有する乗数多項式を考察する。まず、その最上位ビットを調べる。このビットは、「１」の値を有している。その結果、ブロック３０８では「はい」を応答する。すると、パラメータｍが１だけ上昇されることになり、乗算桁送り値Ｓ_Ｚも同じく１だけ上昇されることになる。これにより、乗算予測アルゴリズムは終了してしまう。なぜなら、調べた乗数のビットは、被乗数Ｃの３演算数加算により加算される必要のある「１」の値を有していたからである。
【００５７】
次に乗算予測アルゴリズムを実施する際に、第２ビットを調べる。このビットは、０の値を有している。その結果、ブロック３０８において、「いいえ」が応答される。調べられたビットは、ちょうど被乗数の第２ビットであり、乗算桁送り値Ｓ_Ｚは、ブロック３０４における初期化により、このとき０であるので、ブロック３１６では「はい」を応答する。その結果、制御変数ｍは、１だけ上昇され（３１８）、同じく、乗算桁送り値は、１だけ上昇され（３２０）、次に、折り返し線３２２を介して、ブロック３０８に進む。次のビットは、同じく値「０」を有しているので、このブロックでもまた「いいえ」を応答し、ブロック３１６が再び実行対象ブロックとなる。ｍは、Ｌ（Ｍ）よりまだ小さいので、質問に対して「はい」が応答される。Ｓ_Ｚは、ちょうど１の値を有している。ＣＵＲｋの値が２であっても、この質問に対して、「はい」が応答される。その結果、ブロック３１８および３２０において、ｍおよびＳ_Ｚの上昇が改めて行われる。ブロック３２０を通った後、このとき、Ｓ_Ｚは、２の値を有している。それから、支線３２２を介して、次のビットが１を有しているか０を有しているか決定するために、改めてブロック３０８に進む。上記実施例では、ブロック３０８で改めて「いいえ」を応答する。なぜなら、ここでは、０が連続した第３ビットが調べられるからである。しかし、ブロック３１６では、この場合、「いいえ」を応答する。なぜなら、Ｓ_Ｚは２であり、変数ＣＵＲｋは同じく２であるからである。第３の０が新しい桁送りのために使用できるとしても、このことは、乗算予測方法が実際は取り消されていることを意味している。しかし、Ｓ_Ｚの上限は決められている必要がある。そうでなければ、図２の工程２１４において計算される、桁送りされる中間結果の多項式Ｚ´を格納できるように、無限に長いＺ用レジスタを備える必要があるからである。従って、ＣＵＲｋは、Ｚ用レジスタの現在の動きに応じて、つまり、速い速度が得られるようなできるだけ大きな桁送り値Ｓ_Ｚが許容されるように、しかし、同時に、桁送りされた中間結果の多項式Ｚ´のために制限されているレジスタの長さで事足りるように設定される。図２のブロック２１８における３演算数演算は、被演算数が２つの演算になる。なぜなら、図３のブロック３２４のパラメータａが０に設定されているからである。
【００５８】
図３から分かるように、ブロック３２４の支線において、ｍはこれ以上、上昇されない。その結果、乗算予測アルゴリズムを改めて実施するときには、第３番目の０ビットを、ブロック３０８で連続して調べる。このビットは、０の値を有しているので、ブロック３０８では、再び「いいえ」を応答する。その結果、乗算桁送り値Ｓ_Ｚは、１だけ増加され、制御変数も、ブロック３１８において上昇される。このとき、乗数の最後のビット、つまり「１」が調べられる。このビットは、０ではないので、ブロック３０８では、「はい」を応答し、制御変数が最後に増加され、この反復のための乗算予測アルゴリズムが終了するまで（ブロック３２６）、乗算桁送り値Ｓ_Ｚは、同じくもう一度増加される。このとき、被乗数の全てのビットは調べられているので、その結果、図２の繰り返し線２２６は終了する。なぜなら、この例では、ブロック２２０において、ｍが０に等しいかどうか調べられるからである。
【００５９】
以下に、図２に参照番号２１２により示す簡約予測方法を説明するため、図４について説明する。ブロック４００から簡約予測方法を開始する。ブロック４０２において、様々な広域変数を定義する。これら広域変数のうち、特に、ＮおよびＺに注目する。Ｎは、先の工程のモジュロ多項式の記録値であり、一方、Ｚは、同じく先の工程の更新された中間結果の多項式である。ｋは、Ｚの最大桁送り値、ＣＵＲｋは、Ｚの現在の桁送り値、および、ＭＡＸは、長さ、すなわち、左へ桁送りされた多項式ＮおよびＺを格納するために存在しているオーバーフローバッファ（overflow buffer）のビット数を表している。図２のブロック２１６を考慮すれば、任意の大きな簡約桁送り値Ｓ_Ｎが存在する場合、乗算予測方法の場合と同じように、Ｎのための任意に大きなレジスタを備える必要があるということが分かる。しかし、このことは、空間および効率を考えた場合、望ましくない。その結果、パラメータＭＡＸにより、モジュロ多項式は、同じく、特定のビット数だけ左へ、すなわち、上へ桁送りされてもよいことも考慮される。
【００６０】
次に、ブロック４０４において、後に説明するパラメータＳ_ｉを、０に初期化する。それから、ブロック４０６において、オーバーフローバッファにある、Ｎのビット数を示しているパラメータｎが、０に等しいかどうか、あるいは、Ｓ_ｉがｋに等しいかどうかが決定される。ブロック４０６で「はい」を応答すると、ブロック４０８に進む。ブロック４０８において、簡約予測パラメータｂを、０に設定する。これに対し、ブロック４０６の質問に対して「いいえ」を応答すると、パラメータｎは、１だけ増加する（ブロック４１０）。同時に、パラメータＳ_ｉも、ブロック４１２に示すように、１だけ増加する。続いて、ブロック４１４において、中心的な比較が行われる。この中心的な比較により、３演算数演算（図２のブロック２１８）において、中間結果の多項式のモジュラー簡約を行うために、モジュロ多項式をどれだけ桁送りしなければならないかが決定される。このため、補助簡約桁送り値Ｓ_ｉは、Ｓ _ｉ乗されたｘを先の工程で更新された中間結果の多項式Ｚに乗算して得られる多項式の次数と、現在のモジュロ多項式の次数とが、等しくなるように決められる。このことは、ブロック４０６において、「はい」という結果が得られるまで、あるいは、ブロック４１４において、「はい」という結果が得られるまで繰り返される反復ループ４１６により示されているように、段階的に実行される。ブロック４１４で、「はい」を応答すると、ブロック４１８において、簡約予測パラメータｂを、１に設定する。次に、ブロック４２０において、新しいパラメータｎを、乗算桁送り値Ｓ_Ｚと、実際の値ｎとの差から計算する。次に、実際の簡約桁送り値Ｓ_Ｎが、乗算桁送り値Ｓ_Ｚと補助簡約桁送り値Ｓ_ｉとの差を形成することによって、ブロック４２２において計算される。
【００６１】
ただし、乗算桁送り値Ｓ_Ｚは、図２の矢印２３０に示すような、実際に並行して行われる乗算予測アルゴリズムにより与えられる。補助簡約桁送り値Ｓ_ｉを導入しなければ、実際には乗算予測方法とこれに続く簡約予測方法とを連続して実施できるのみであり、効率のうえからはこれは望ましくない。従って、補助簡約桁送り値Ｓ_ｉを使用し、この補助簡約桁送り値Ｓ_ｉにより、実際の簡約桁送り値Ｓ_Ｎの計算をする限り、時間のかかるループ（図４の折り返し４１６）を、乗算予測アルゴリズムと実際に並行して処理でき、一方で、簡約桁送り値Ｓ_Ｎの実際の計算は、２つの短い数Ｓ_ＺとＳ_ｉとの差を得ることにより、迅速に行うことができる。従って、順序は以下のようにある。Ｓ_ＺとＳ_ｉとを並行して計算する。次に、Ｓ_Ｚを、図２の支線２３０（図４にも示されている）を介して、乗算予測アルゴリズムから、簡約予測アルゴリズムへと供給する。その結果、次の周期において、簡約桁送り値Ｓ_Ｎもすぐ利用できる。これについては、後で、図８ａ〜図８ｃを参考にして詳しく説明する。
【００６２】
ブロック４２２の後、ブロック４２４において、ｎが、ＭＡＸ−kよりも大きいかどうかを決定する。この質問に対して「はい」が応答されると、ブロック４２６において、新しいＣＵＲｋを計算する。ブロック４２４の質問に対して、「いいえ」が応答されると、ブロック４２８において、ＣＵＲｋがｋに等しくなるように設定される。次に、ブロック４３０において、簡約予測方法の結果値、すなわち、ｂおよびＳ_Ｎが出力される。そうして、簡約予測方法は、ブロック４３２で終了する。
【００６３】
乗算予測パラメータａおよび簡約予測パラメータb、ならびに、メモリー管理パラメータｎ、ＭＡＸ、ｋ、およびＣＵＲｋの詳細な説明について、ドイツ特許３６３１９９２号Ｃ２が参照される。パラメータａおよびｂが＋１、０、および−１の値をとってもよいＺ／ＮＺのためのＺＤＮ方法とは異なり、本発明に基づく方法における相当するパラメータａ、ｂは、０および１の値のみをとることができる。予測パラメータａおよびｂは、本発明にかかるモジュラー乗算のためには、場合により必要となる。つまり、任意に大きくない格納場所をＮおよびＺのために利用する場合に必要となる。しかし、本発明の方法は、一般的に言えば、任意の大きさのレジスタを使用できるという条件下においても、何の困難もなく実施される。この場合、乗算予測方法が省略されてしまうことはなく、乗数の「１」が再び見出されるまでの間ずっと実施されている。そのときまで、図２のブロック２１４を参照すると、Ｓ_Ｚは、特定のできる限り大きな数を有している。その結果、桁送りされた中間結果の多項式Ｚ´は、極めて大きな値を取ることが可能である。次に、ブロック２１８において、乗数１が見出されたという事実に基づき、被乗数を、桁送りされた中間結果多項式Ｚ´に加える。
【００６４】
しかし、重要な特徴は、それぞれの乗算工程と同時に、モジュラー簡約も行われることであり、これにより、数値全てを許容限度(ertraeglichen Grenzen)に含むことができる。
【００６５】
このため、本発明に基づく簡約桁送り値Ｓ_Ｎは、桁送りされたモジュロ多項式の次数が、実際の中間結果の多項式の次数に等しくなるように選択される。桁送りされたモジュロ多項式が、Ｚ´（ｘ）とＣ（ｘ）との和から減算される場合、通常、更新された中間結果Ｚは、Ｚ´よりもずっと小さくなり、これにより簡約が完了する。図２の工程２１８で計算される、更新された中間結果の多項式Ｚは、必ずしも、ブロック２０２のもともとのモジュロ多項式により簡約される必要はなく、反復工程全体を通して、左へと桁送りされた１つのモジュロ多項式、すなわち、より高い次数を有する１つのモジュロ多項式により簡約されてもよいことが分かる。しかし、必ずしも、そうである必要はない。この場合には、工程２２０において、ｎが０に等しいかどうか、すなわち、Ｎがオーバーフローバッファにビットを有するかどうかが判定され、更新された中間結果からモジュロ多項式の更なる減算を行ってＺを本来の余剰群（ Restklasse ）に漸進的に簡約していくことによって、簡約が達成される。ｎが０に等しい場合は、Ｎのビットが、もはやオーバーフローバッファに存在しないことを意味している。このことは、最終的に得られる桁送りされたモジュロ多項式が、ブロック２０２のもともとのモジュロ多項式に等しいことを同じく意味している。
【００６６】
従って、モジュラー乗算をするための本発明に基づく方法は、基本的には、予測パラメータａおよびｂを用いることなく実施できる。しかし、任意の乗数が想定されている場合には、ＺおよびＮのための、論理的に無限のレジスタが必要となる。
【００６７】
ＺおよびＮの格納限界がある場合、すなわち、予測パラメータａおよびｂが０を取り得る場合には、乗算予測パラメータａが０に等しいことは、被乗数が桁送りされたＺ´に加えられないことを意味する。これと同じように、０に等しい簡約予測パラメータｂは、桁送りされたモジュロ多項式が、桁送りされた中間結果の多項式Ｚ´よりも大きく、もう簡約する必要がないことを意味する。従って、モジュロ減算を、同じく省略することができる。このような場合には、３演算数演算は、完全になくなる。
【００６８】
ただし、この際、Ｚ用レジスタおよびＮ用レジスタのオーバーフローバッファが制限されている場合、変数ｍが、０の値に達しない限り、Ｎは、そのもともとのＭＳＢ（Hoｍe-MSB）から少なくともｋビット遠ざかっているということにも注意しなければならない。
【００６９】
さらに、ＧＦ（２ｎ）算術の場合、すなわち、多項式の係数が、０または１だけでよい場合、加算演算は、減算演算に相当し、一般的に、ＸＯＲ結合として実施できる。しかし、多項式の係数が、他の数の方式、例えば、８進数方式（Oktal-Systeｍ）、または、１０進数方式（Deziｍal-Systeｍ）に含まれている場合、当然、減算は加算に相当していない。
【００７０】
補助簡約桁送り値Ｓ_ｉを用いる簡約桁送り値Ｓ_Ｚの計算を示すために、以下に、図８ａ〜図８ｃについて説明する。図８ａには、中間結果の多項式Ｚおよびモジュロ多項式Ｎを示す。単なる例として、中間結果の多項式は、次数４、すなわち、４ビットを有しており、一方、モジュロ多項式は、次数９、すなわち、９ビットを有している。図２のブロック２１４において、桁送りされた中間結果の多項式Ｚ´を計算する。この計算は、Ｓ_Ｚにより累乗されている変数ｘを乗算することにより行う。従って、乗数に８個の０があり、これにより、乗算桁送り値Ｓ_Ｚは８となる。モジュラー簡約を行うためには、モジュロＮは、桁送りされた中間結果の多項式Ｚ´の桁数（Groessenordnung）になっている必要がある。本発明に基づき、モジュロ多項式Ｎは、桁送りされた中間結果の多項式Ｚ´の次数と、桁送りされたモジュロ多項式Ｎの次数とが同じくなる程度にまで桁送りされている。このためには、図８ｂから分かるように、Ｓ_Ｎの簡約桁送り値は３に等しくなければならない。
【００７１】
図８ｂから、同じく、Ｓ_Ｎの調査は、実際には、Ｓ_Ｚが計算されている場合にはじめて行えることが分かる。すなわち、本発明にとって好ましいように、図２のブロック２１０と２１２とを並行して実施することはできない。この理由により、補助予測パラメータＳ_ｉが挿入される。図８ａから分かるように、補助桁送りパラメータＳ_ｉは、中間結果の多項式Ｚと、モジュロ多項式Ｎとの次数の差に等しい。実際の工程のＳ_Ｚを知らなくてもこの値を計算できることがＳ_ｉの利点である。
【００７２】
図８ｃから、Ｓ_Ｚは、Ｓ_ｉとＳ_Ｎとの和に常に等しいということが分かる。従って、Ｓ_Ｎは、以下の等式が当てはまるようにＳ_ＺおよびＳ_ｉと常に関連している。
Ｓ_Ｎ＝Ｓ_Ｚ−Ｓ_ｉ
従って、Ｓ_Ｎを決定するための時間のかかる反復方法を、Ｓ_ｉを決定するための時間のかかる反復方法（折り返し線４１６）と、迅速な差演算（図４のブロック４２２）とに分解できる。これにより、２つの予測方法をほぼ並行して実施できる。この際、唯一の連続している構成部分は、ブロック４２２の（図４）の計算の前に、Ｓ_Ｚの実際の値が乗算予測アルゴリズムにより既に計算され、供給されている（図２の矢印２３０）ことである。
【００７３】
既に説明したように、ＧＦ（２^ｎ）についてのモジュラー乗算を計算するための本発明に基づく概念の重要な利点は、この概念をＺＤＮ方法のための既存の長い数の算術演算装置に統合できることである。図５は、本発明に基づき適合されている、Ｚ、ａＣ、および、ｂＮによる３演算数加算を行うための３演算数算術演算装置の一部を示す。
【００７４】
図５に、相互に接続されている３つのビット片［ｉ］、［ｉ−１］、［ｉ−２］を示す。各ビット片は、出力部側において、更新された中間結果多項式の１ビットＺ［ｉ］、Ｚ［ｉ−１］、または、Ｚ［ｉ−２］を得るために、３ビット計数器５００および、全加算器５１０を備えている。全加算器は、さらに、次に高い全加算器の桁上げ入力部のための桁上げ出力部（キャリー（Carry）＝桁上げ）を備えている。例えば、２００次の多項式を処理する場合、図５のビット片の全加算器が並列に２００個接続される必要がある。
【００７５】
図５のビット片を、ＧＦ（２^ｎ）のために変更するために、図５に示すように、ＡＮＤゲート５２０を、３ビット計数器の上側の出力部と、次に高い段階の全加算器の下から２番目の入力部との間に挿入する必要がある。（ＡＮＤゲート５２０の）イネーブル入力部５３０に０が入力されると、（全加算器５１０に供給される）値ｘは、常に０になる。すなわち、全加算器５１０の機能は、ｙと０とを加算するだけになる。これに対して、Ｚ／ＮＺの場合、ＡＮＤゲートのイネーブル入力部に、「１」が提供される。その結果、ＡＮＤゲートは、他の作用を有していない。
【００７６】
従って、ＧＦ（２^ｎ）では、ＡＮＤゲートの出力が０に等しい。これに対し、Ｚ／ＮＺでは、Ｘが必要であり、ＡＮＤゲートの出力が０に等しくなくてもよい。それゆえ、イネーブルは、ＡＮＤゲートにより実現される。これに対し、ＧＦ（２^ｎ）、つまり、イネーブル入力部５３０に０が与えられる場合、全加算器における加算は自明な演算になる。
【００７７】
図６は、ＡＮＤゲート５２０の状態を示す。図５に部分的に示す算術演算装置は、イネーブル信号ＳＣ＝１である場合、標準加算器として機能する。これに対し、算術演算装置は、イネーブル信号ＳＣ＝０である場合、ＸＯＲ回路として機能する。
【００７８】
図７は、Ｚ／ＮＺおよびＧＦ（２^ｎ）のための算術演算装置の概略的なブロック図を示す。上記算術演算装置は、長い数の算術装置７００の周りに集約されている。この算術装置７００は、既述の３演算数演算を、Ｚ／ＮＺまたはＧＦ（２^ｎ）のために実施する。
【００７９】
算術演算装置は、Ｚ／ＮＺ制御装置７１０、ＧＦ(２^ｎ)制御装置７２０、および、モード選択装置７３０をさらに含んでいる。上記算術演算装置が整数のモジュロに対する演算を行う場合、モード選択部７３０は、真の加算演算を実行するように算術装置７００を制御し、該算術装置７００の入力側と出力側とをＺ／ＮＺ制御装置７１０に接続する。一方、上記算術演算装置がＧＦ（２ ^ｎ）算術を行う場合、モード選択部７３０は、加算の代わりにＸＯＲ演算を実行するよう算術装置７００を制御し、該算術装置７００の入力側と出力側とをＧＦ（２ ^ｎ）制御装置に接続する。
【００８０】
それゆえ、整数モジュラー算術と、多項式モジュラー算術との双方を算術演算装置に組み込むために、別個の算術装置を必要とはしない。
【００８１】
ただし、３演算数演算が、全てのビットのために並行して行われるという事実に基づき、ほとんどの集積回路領域は、算術装置７００によって消費され、一方で、制御装置７１０および７２０では、より短い数で、より小さな計算が実施されるのでビット領域は特に重要ではなくなる。
【００８２】
従って、整数算術と多項式算術との双方のために、独自の算術演算装置を必要とする算術演算装置とは反対に、モジュラー乗算を計算するための本発明に基づく概念によれば、集積回路領域を５０％近く減少できる。特にスマートカードに対して、この集積回路領域の節約は、競争上の優位性を導く。
【図面の簡単な説明】
【図１】ＧＦ（２^ｎ）におけるモジュラー累乗法を具体的に説明するためのフローチャートである。
【図２】本発明に基づく方法の高レベルのフローチャートである。
【図３】乗算桁送り値を計算するための、乗算予測方法のフローチャートである。
【図４】簡約桁送り値を計算するための、簡約予測方法のフローチャートである。
【図５】ＧＦ（２^ｎ）算術またはＺ／ＮＺ算術のための３演算数加算器の一部を示す図である。
【図６】桁上げ遮断機能の詳細な図である。
【図７】Ｚ／ＮＺ-ＧＦ（２^ｎ）算術演算装置のブロック図である。
【図８】Ａ〜Ｃは、簡約桁送り値の計算を具体的に説明するための概略的な図である。
【図９】Ｚ／ＮＺにおいてモジュラー乗算を行うためのＺＤＮ方法の概要を示す図である。
【符号の説明】
２００モジュラー乗算のための方法の開始
２０２広域変数
２０４中間結果多項式の初期化
２０６ｍの初期化
２０８ｎの初期化
２１０乗算予測方法
２１２簡約予測方法
２１４中間結果多項式の生成
２１６桁送りされたモジュロ多項式の生成
２１８３演算数加算
２２０アルゴリズムが終了したかどうかの調査
２２２Ｚの出力
２２４モジュラー乗算するための方法の終了
２２６折り返し線
２３０Ｓ_Ｚ桁上げ
３００乗算予測方法の開始
３０２広域変数
３０４Ｓ_Ｚの初期化
３０６ａの初期化
３０８処理されたビットが０または１であるかどうかの決定
３１０ｍの増加
３１２Ｓ_Ｚの増加
３１４ａおよびＳ_Ｚの出力
３１６さらに桁送りできるかどうかの決定
３１８ｍの増加
３２０Ｓ_Ｚの増加
３２２折り返し線
３２４ａの設定
３２６乗算予測方法の終了
４００簡約予測方法の開始
４０２広域変数
４０４Ｓ_iの初期化
４０６簡約できるかどうかの決定
４０８ｂの設定
４１０ｎの増加
４１２Ｓ_iの増加
４１４桁送りされた中間結果の多項式の次数の調査
４１６折り返し線
４１８ｂの設定
４２０ｎの設定
４２２Ｓ_Ｎの計算
４２４ｎの調査
４２６ＣＵＲｋの設定
４２８ＣＵＲｋの設定
４３０ｂ、Ｓ_Ｎの出力
４３２簡約予測方法の終了
５００３ビット計数器
５１０全加算器
５２０スイッチ
５３０制御
７００３演算数算術演算装置
７１０Ｚ／ＮＺ制御装置
７２０ＧＦ（２^ｎ）制御装置
７３０モード選択
９００ＺＤＮ方法の開始
９１０ＺＤＮアルゴリズムのための乗算予測方法
９２０Ｚの左への桁送り
９３０ＺＤＮアルゴリズムのための簡約予測方法
９４０モジュロの左または右への桁送り
９５０ＺＤＮアルゴリズムのための３演算数加算
９６０ＺＤＮアルゴリズムの終了

Claims

モジュロ（Ｎ）を用いて、被乗数（Ｃ）に乗数（Ｍ）をモジュラー乗算するための装置において、
上記被乗数（Ｃ）、上記乗数(Ｍ)、および、上記モジュロ(Ｎ)は、体ＧＦ（２ ^ｎ）の要素、すなわち、０または１を係数とする変数 ( ｘ ) の多項式であり、
（ａ）乗算の先読み法（２１０）を実施する装置であって、上記乗数多項式（Ｍ）の注目項の係数が０であるときに乗算桁送り値Ｓ _Ｚを増加させることにより乗算桁送り値Ｓ _Ｚを得る装置と、
（ｂ）桁送りされた中間結果の多項式（Ｚ´）を得るために、上記乗算桁送り値（Ｓ_Ｚ）により累乗されている上記変数(ｘ)に、中間結果の多項式（Ｚ）を乗算する（２１４）装置と、
（ｃ）モジュロの先読み法（２１２）を実施する装置であって、上記桁送りされた中間結果の多項式（Ｚ´）の次数と上記モジュロ多項式（Ｎ）の次数との差に一致する簡約桁送り値（Ｓ _Ｎ）を、上記乗算先読み法（２１０）を実施する装置にて得られた乗算桁送り値Ｓ _Ｚと上記モジュロ多項式（Ｎ）とに基づいて算出する装置と、
（ｄ）桁送りされたモジュロ多項式（Ｎ´）を得るために、上記簡約桁送り値（Ｓ_Ｎ）により累乗されている上記変数（ｘ）に、上記モジュロ多項式（Ｎ）を乗算する（２１６）装置と、
（ｅ）更新された中間結果の多項式（Ｚ）を得るために、上記桁送りされた中間結果の多項式（Ｚ´）と上記被乗数(Ｃ)とを加算し（２１８）、上記桁送りされたモジュロ多項式（Ｎ´）を減算する装置と、
（ｆ）上記乗数（Ｍ）の全ての項が処理されるまで、上記装置（ａ）〜（ｅ）を繰り返し駆動する（２２６）装置とを含み、
上記繰り返しにおいて、上記中間結果の多項式（Ｚ）を乗算する（２１４）装置は、上記加算する（２１８）装置が前回生成した、更新された中間結果の多項式（Ｚ）を乗算するように構成されており、上記モジュロの先読み法（２１２）を実施する装置は、上記モジュロ多項式（Ｎ）を乗算する（２１６）装置が前回生成した、桁送りされたモジュロ多項式（Ｎ´）を上記モジュロ多項式（Ｎ）として使用するように構成されている、装置。
桁送りされた中間結果の多項式（Ｚ´）を得るために乗算をするための上記装置（２１４）、および、桁送りされたモジュロ多項式（Ｎ´）を得るために乗算をするための上記装置（２１６）は、上記乗算桁送り値（Ｓ_Ｚ）または上記簡約桁送り値（Ｓ_Ｎ）に関係なく、相当する桁数だけ記録内容を桁送りするために制御可能なシフトレジスタとして実装されている、請求項１に記載の装置。
加算および減算するための上記装置（２１８）は、上記中間結果の多項式（Ｚ´）、上記多項式被乗数（Ｃ）、および、上記桁送りされたモジュロ多項式(Ｎ´)のＸＯＲ結合のためのビット毎のＸＯＲ結合装置を含む、請求項１または２に記載の装置。
加算および減算するための上記装置（２１８）は、
第１入力部配線に、上記中間結果の多項式（Ｚ）のビットを印加でき、第２入力部配線に、上記被乗数（Ｃ）のビットを印加でき、第３入力部配線に、上記桁送りされたモジュロ多項式(Ｎ´)のビットを印加できる、３つの入力部配線および２つの出力部配線を有する計数器（５００）と、
上記計数器（５００）の低い値の出力部が、全加算器（５１０）の高い値の入力部配線に接続されている、３つの入力部および１つの出力部を有する全加算器(５１０)と、
上記計数器(５００)の高い値の出力部配線と、全加算器（５１０）の中間入力部との間に、高い値のビットのために接続されているスイッチ（５２０）と、
多項式が処理される場合、スイッチ（５２０）を開けるための、制御装置（５３０）とを有する、請求項１または２に記載の装置。
モジュロを使用して、被乗数に乗数を乗算するための算術演算装置として構成されており、
上記算術演算装置は、さらに、モジュロ整数を使用して、被乗数整数に乗数整数を乗算するために構成されており、
上記加算するための装置は、桁上げ遮断装置（７３０）を有する３演算数加算器（７００）として形成され、
上記加算するための装置は、整数演算数または多項式演算数を組み合わせるために構成されており、
上記算術演算装置は、上記加算するための装置によって上記多項式演算数を処理する場合、桁上げが行われず、上記加算するための装置によって上記整数演算数を処理する場合、桁上げが行われるよう、上記桁上げ遮断装置を制御するための制御装置(７３０)をさらに備える請求項１に記載の装置。
桁上げ遮断装置を有する上記３演算数加算器は、
第１入力部配線に、中間結果の多項式のビットを印加でき、第２入力部配線に、上記多項式被乗数（Ｃ）のビットを印加でき、第３入力部配線に、上記桁送りされたモジュロ多項式のビットを印加できる、３つの入力部配線および２つの出力部配線を有する計数器（５００）と、
上記計数器（５００）の低い値の出力部が上記全加算器（５１０）の高い値の入力部配線に接続されている、３つの入力部および１つの出力部を有する全加算器(５１０)と、
上記計数器(５００)の高い値の出力部配線と、全加算器（５１０）の中間入力部との間に、高い値のビットのために接続されているスイッチ（５２０）と、
多項式が処理される場合、上記スイッチ（５２０）を開くための、制御装置（５３０）とを有する、請求項５に記載の装置。
存在する３演算数加算器の数が、上記モジュロ整数または上記モジュロ多項式の桁数よりも大きいかあるいは同じである、複数の３演算数加算を備える、請求項６に記載の装置。
上記（ｂ）における乗算（２１４）のための装置は、上記乗算桁送り値（Ｓ_Ｚ）に等しい桁数で、上記中間結果の多項式（Ｚ）を桁送り可能であって、
上記（ｄ）における乗算のための装置（２１６）は、上記簡約桁送り値(Ｓ_Ｎ)に等しい桁数で、上記モジュロ多項式（Ｎ）を桁送り可能である、請求項１に記載の装置。
上記多項式の係数は、「０」または「１」の値のみを有することができ、
上記（ｅ）における加算および減算のための装置（２１８）は、上記中間結果の多項式（Ｚ´）、上記被乗数（Ｃ）、および、上記桁送りされるモジュロ多項式（Ｎ´）のビット毎のＸＯＲ結合を実施可能となっている、請求項１に記載の装置。
上記モジュロの先読み法（２１２）を実施する装置は、
上記モジュロ多項式（Ｎ）の次数と、補助桁送り値（Ｓ_ｉ）により累乗されている変数（ｘ）が乗算された、上記更新された中間結果の多項式（Ｚ）の次数とが等しくなるように、補助桁送り値（Ｓ_ｉ）を決定する（４１４）装置と、
上記簡約桁送り値（Ｓ_Ｎ）を得るために、上記乗算桁送り値（Ｓ_Ｚ）と、上記補助桁送り値（Ｓ_ｉ）との差を形成する（４２２）装置とを含んでいる、請求項１に記載の装置。
上記乗算の先読み法（２１０）を実施する装置と、上記補助桁送り値（Ｓ_ｉ）を決定する（４１４）装置とを相互に並行して動作させることが可能となっている、請求項１０に記載の装置。
上記乗算桁送り値（Ｓ_Ｚ）は、最大乗算桁送り値（ｋ）に制限されており、
上記乗算の先読み法（２１０）を実施する装置は、
上記乗算桁送り値が、上記最大乗算桁送り値（ｋ）に等しい場合、上記乗算桁送り値（Ｓ_Ｚ）を、上記最大桁送り値（ｋ）に等しく設定し、所定の値を有する乗算予測パラメータ（ａ）を生成する（３０６，３２４）工程を実施可能となっており、
上記加算する（２１８）装置は、
上記乗算予測パラメータ（ａ）が、所定の値を有している場合、上記所定の中間結果の多項式（Ｚ´）および上記桁送りされたモジュロ多項式（Ｎ´）のみを加算する工程を実施可能となっている、請求項１に記載の装置。