JP2004519052A - 係数乗算を行うための方法と装置、および、係数乗算を行うための算術演算装置 - Google Patents

Abstract

係数（Ｎ）を使用して、被乗数（Ｃ）に乗数（Ｍ）を係数乗算するための方法では、被乗数、乗数、および、係数が、変数の多項式であり、乗算予測方法（２１０）が、乗算桁送り値（ｓ_Ｚ）を得るために実施される。中間結果多項式（Ｚ）は、桁送りされた中間結果多項式（Ｚ´）を得るために、乗算桁送り値（ｓ_Ｚ）の桁数だけ、左へ桁送り（２１４）される。さらに、換算桁送り値（ｓ_Ｎ）を得るために、換算予測方法（２１２）が実施される。換算桁送り値は、桁送りされた中間結果多項式（Ｚ´）の次数と、係数多項式（Ｎ）の次数との差に等しい。係数多項式は、桁送りされた係数多項式を得るために、換算桁送り値（２１６）に等しい桁数だけ桁送りされる。３演算数加算器（２１８）において、桁送りされた中間結果多項式（Ｚ´）、および、被乗数（Ｃ）が加算され、桁送りされた係数多項式（Ｎ´）は、更新された中間結果多項式（Ｚ）を得るために、減算される。上記工程を反復して実施すること（２２６）により、係数乗算は、乗算多項式の全ての累乗が処理されるまで、徐々に行われる。桁上げ遮断機能により、Ｚ／ＮＺ算術と、ＧＦ（２^ｎ）算術との双方を、唯一の長い数の算術演算装置により行える。

Description

本発明は、係数乗算、例えば、ＧＦ（２^ｎ）の楕円曲線の係数乗算を実施するための方法および装置に関するものである。
【０００１】
暗号化は、係数算術のための主な応用の１つである。基本的には、係数Ｎの形態に応じて、２つの暗号化方法に区別される。係数が整数の場合は、Ｚ／ＮＺ算術（Ｚ／ＮＺＡｒｉｔｈｍｅｔｉｋ）のことを言う。パラメータＮは、素数、または、素数の組み合わせを表している。パラメータＺは、整数を表している。係数が２つの素数の組み合わせである場合の例として、ＲＳＡ等式がある：
Ｃ＝Ｍ^Ｅｍｏｄ（Ｎ）
ただし、知られているように、Ｃは、符号化された情報、Ｍは、符号化されていない情報、Ｅは、公開鍵（ｏｅｆｆｅｎｔｌｉｃｈｅ Ｓｃｈｌｕｅｓｓｅｌ）、そして、Ｎは、係数である。
【０００２】
一方、ＧＦ（２^ｎ）算術は、係数Ｎ（ｘ）が変数ｘの多項式であることにより特徴づけられている。多項式は、累乗されたｘの和を含み、累乗されたｘには、それぞれ係数が割り当てられている。累乗されたｘの最大指数は、多項式の次数（Ｇｒａｄ）として示される。係数が、体（Ｋｏｒｐｅｒ）ＧＦ（２）からのものである場合、ＧＦ（２^ｎ）係数、または、より一般的にはＧＦ（２^ｎ）算術という。ＧＦ（２^ｎ）算術は、例えば、楕円曲線暗号化（Ｅｌｌｉｐｔｉｓｃｈｅ−Ｋｕｒｖｅｎ−Ｋｒｙｐｔｏｇｒａｐｈｉｅ）に対して使用される。
【０００３】
次数ｎ−１の多項式
【０００４】
【数１】

【０００５】
は、ｎ個の係数ａ_ｎ−１，．．．， ａ_０により規定され、ａ_ｉは、集合（Ｍｅｎｇｅ）ＧＦ（２）からのものである必要があり、ａ_ｎ−１は、定義により１であるので、
ｆ（ｘ）＝１^＊ｘ^ｎ−１＋ａ_ｎ−２ ^＊ｘ^ｎ−２＋．．．＋ａ_１ ^＊ｘ^１＋ａ_０ ^＊ｘ^０
となる。
【０００６】
体ＧＦ（２^ｎ）は、次数ｎの既約多項式、および、ｎ−１未満またはｎ−１に等しい次数のＧＦ（２^ｎ）の多項式により規定される。
【０００７】
ＧＦ（２^ｎ）に関する２つの要素、すなわち、多項式の加算は、長さｎをもつ上記２つの要素の、係数ベクトルのＸＯＲ結合（ＸＯＲ−Ｖｅｒｋｎｕｅｐｆｕｎｇ）によって規定されている。
【０００８】
ＧＦ（２^ｎ）に関する２つの要素、すなわち多項式の乗算は、多項式をＧＦ（２^ｎ）について乗算すること、および、続いて、得られる積を、次数ｎの既約多項式Ｎ（ｘ）を法として約分すること（Ｒｅｄｕｚｉｅｒｅｎ）により達成される。この多項式Ｎ（ｘ）は、相当する体を定義する。
【０００９】
それゆえ、積としての多項式、つまり、第１多項式ｆ（ｘ）と第２多項式ｇ（ｘ）との乗算により生じる多項式に対して係数の演算を実施するためには、除数として係数多項式Ｎ（ｘ）を用いた多項式の除算を行う必要がある。それゆえ、ｆ（ｘ）^＊ｇ（ｘ）ｍｏｄＮ（ｘ）の結果は、多項式の除算により生じる残りの多項式（Ｒｅｓｔｐｏｌｙｎｏｍ）となる。
【００１０】
Ｚ／ＮＺと、ＧＦ（２^ｎ）との双方についての係数乗算を効果的に実施するための様々な方法を説明する前に、Ｚ／ＮＺと、ＧＦ（２^ｎ）との双方に関する係数累乗法は、知られている平方および乗算アルゴリズム（Ｓｑｕａｒｅ−ａｎｄ−Ｍｕｌｔｉｐｌｙ−Ａｌｇｏｒｉｔｈｍ）を用いて、乗算に分解できる。これにより、以下の等式を解くことができる：
Ｃ（ｘ）＝（Ｍ（ｘ））^ＥｍｏｄＮ（ｘ）
平方および乗算アルゴリズムは、指数Ｅが２の累乗の和に分解されるということに基づいている：
【００１１】
【数２】

【００１２】
以下の例は、このことを明らかにする。二進法表示では、
Ｅ＝１０１１
となる。
従って、以下の関係となる。
Ｃ（ｘ）＝Ｍ（ｘ）＾（１^＊２^３＋０^＊２^２＋１^＊２^１＋１^＊２^０）ｍｏｄＮ（ｘ）
従って、
Ｃ（ｘ）＝（Ｍ（ｘ））^８＊（Ｍ（ｘ））^０＊（Ｍ（ｘ））^２＊（Ｍ（ｘ））^０ｍｏｄＮ（ｘ）
となる。
【００１３】
Ｚ／ＮＺ算術においても上述の等式は当てはまるが、その場合、Ｍ（ｘ）の代わりにＭであり、Ｎ（ｘ）の代わりにＮである点で異なる。
【００１４】
モジュラー乗算を計算するために知られている、効果的で頻繁に使用される方法は、モンゴメリー乗算として知られており、例えば、「応用暗号化誌」（”Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｅｄ Ｃｒｙｐｔｏｇｒａｐｈｙ”， Ｍｅｎｅｚｅｓ， ｖｏｎ Ｏｏｒｓｃｈｏｔ， Ｖａｎｓｔｏｎｅ， ＣＲＣ Ｐｒｅｓｓ， ６００〜６０３ページ）に記載されている。モンゴメリー換算（Ｍｏｎｔｇｏｍｅｒｙ−Ｒｅｄｕｋｔｉｏｎ）は、従来のモジュラーの換算工程を統計立てて行うことなく、係数乗算を効果的に実施できる技術である。一般的に、モンゴメリー換算では、除算演算は、簡単な桁送り演算（Ｖｅｒｓｃｈｉｅｂｕｎｇｓｏｐｅｒａｔｉｏｎｅｎ）によって表現される。
【００１５】
一方、モンゴメリー乗算演算を有限体のＧＦ（２^ｎ）に拡張する（Ｅｒｗｅｉｔｅｒｕｎｇ）ことも知られている。この拡張は、「ＧＦ（２^ｋ）におけるモンゴメリー乗算」（”Ｍｏｎｔｇｏｍｅｒｙ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎｉｎ ＧＦ（２^ｋ）”， Ｋｏｃ， Ａｚａｒ， Ｄｅｓｉｇｎｓ， Ｃｏｄｅｓ ａｎｄ Ｃｒｙｐｔｏｇｒａｐｈｙ、１４巻、１９９８年、５７〜６９ページ）に記載されている。この拡張は、さらに、「有限体Ｚ／ＮＺおよびＧＦ（２^ｎ）のための測定可能な統合乗算設計」（”Ａ Ｓｃａｌａｂｌｅ ａｎｄ Ｕｎｉｆｉｅｄ Ｍｕｌｔｉｐｌｉｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｆｉｎｉｔｅ Ｆｉｅｌｄｓ Ｚ／ＮＺａｎｄＧＦ（２^ｎ）”，Ｅｒｋａｙ Ｓａｖａｓ他、Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ （ＣＨＥＳＳ２０００），２８１〜２８９ページ，Ｓｐｒｉｎｇｅｒ Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ）に記載されている。
【００１６】
Ｚ／ＮＺまたはＧＦ（２^ｎ）のモンゴメリー乗算の不利な点は、係数換算のためにハードウェアで実施する係数換算のための除算演算は、桁送り演算により回避することができるが、ハードウェアの係数乗算演算の速度を上げるための先見越し方法（Ｌｏｏｋ−Ａｈｅａｄ−Ｖｅｒｆａｈｒｅｎ）または予測方法（Ｖｏｒａｕｓｓｃｈａｕ−Ｖｅｒｆａｈｒｅｎ）は使用されないことにある。
【００１７】
ドイツ特許第３６３１９９２号Ｃ２（ＤＥ３６３１９９２Ｃ２）に、Ｚ／ＮＺの係数乗算を、乗算予測方法（Ｍｕｌｔｉｐｌｉｋａｔｉｏｎｓ−Ｖｏｒａｕｓｓｃｈａｕ−Ｖｅｒｆａｈｒｅｎｓ）と、換算予測方法（Ｒｅｄｕｋｔｉｏｎｓ−Ｖｏｒａｕｓｓｃｈａｕ−Ｖｅｒｆａｈｒｅｎｓ）とを使用することで速く行う方法が開示されている。ドイツ特許第３６３１９９２号Ｃ２に記載されている方法は、ＺＤＮ方法とも表され、図９を参考にして詳しく説明する。アルゴリズムの開始工程９００の後、広域変数（ｇｌｏｂａｌｅｎ Ｖａｒｉａｂｌｅｎ）Ｍ，Ｃ，およびＮを初期化する。この目的は、以下の係数乗算を計算するためである：
Ｚ＝Ｍ^＊ＣｍｏｄＮ
Ｍは、乗数を表し、一方、Ｃは、被乗数を示している。Ｚは、係数乗算の結果であり、一方、Ｎは、係数である。
【００１８】
このとき、次にすぐ処理する必要のない様々な局所変数（ｌｏｋａｌｅ Ｖａｒｉａｂｌｅｎ）は初期化される。続いて、２通りの予測方法を用いる。乗算予測方法ＧＥＮ＿ＭＵＬＴ＿ＬＡでは、様々な先見越し規則を用いて、乗算桁送り値ｓ_ｚおよび乗算予測パラメータａを計算する（９１０）。このとき、Ｚ記録器（Ｚ−Ｒｅｇｉｓｔｅｒｓ）の最新の内容は、左桁送り演算（Ｌｉｎｋｓ−Ｖｅｒｓｃｈｉｅｂｕｎｇｓ−Ｏｐｅｒａｔｉｏｎ）によりｓ_ｚ桁（ｓ_Ｚ−Ｓｔｅｌｌｅｎ）桁送りされる（９２０）。
【００１９】
これとほぼ並行して、換算桁送り値ｓ_Ｎおよび換算パラメータｂを計算するための換算予測方法ＧＥＮ＿Ｍｏｄ＿ＬＡ（９３０）を実施する。工程９４０において、係数記録器の最新の内容、すなわち、Ｎが、桁送りされた係数値Ｎ´を生成するために、ｓ_Ｎ桁だけ桁送りされる。ＺＤＮ方法の中央３演算数演算（Ｄｉｅ ｚｅｎｔｒａｌｅ Ｄｒｅｉ−Ｏｐｅｒａｎｄｅｎ−Ｏｐｅｒａｔｉｏｎ）は、工程９５０において行われる。このとき、工程９２０の後の中間結果Ｚ´は、乗算予測パラメータａが乗算されている被乗数Ｃと、換算予測パラメータｂが乗算されている係数Ｎ´とに加算される。現状に応じて、予測パラメータａおよびｂは、＋１、０、または、−１の値を有していてもよい。
【００２０】
乗算予測パラメータａが＋１であり、換算予測パラメータｂが−１である場合には、桁送りされた中間結果Ｚ´に被乗数Ｃが加算され、それから桁送りされた係数Ｎ´が減算される。乗算予測方法が、予め設定されている数より多くの個々の左への桁送りを許可するなら、つまり、ｓ_ｚが、ｋとしても示される、ｓ_ｚの最大許容値よりも大きい場合、ａは、０に等しい値を有することになる。ａが０に等しく、Ｚ´が、先の係数換算、つまり、桁送りされた係数の先の減算が原因で、まだかなり小さく、特に、桁送りされた係数Ｎ´よりも小さい場合には、換算を行う必要がない。その結果、パラメータｂは、０に等しくなる。
【００２１】
工程９１０〜９５０は、被乗数の全ての桁が処理される、すなわち、ｍが０に等しく、パラメータｎも０に等しくなるまでずっと実施される。パラメータｎは、桁送りされた係数Ｎ´が、もとの係数Ｎよりもまだ大きいかどうか、あるいは、すでに被乗数の全ての桁が処理されているという事実にもかかわらず、Ｚから係数を減算することにより、さらに他の換算工程を実施する必要があるかどうかを示している。
【００２２】
最後に、Ｚが０よりも小さいかどうかが決定される。Ｚが０よりも小さい場合には、換算が終了するように、係数ＮをＺに加える必要がある。これにより、係数乗算の正の結果Ｚが得られる。工程９６０において、ＺＤＮ方法を用いる係数乗算を終了する。
【００２３】
工程９１０において、乗算予測アルゴリズムにより計算される乗算桁送り値ｓ_Ｚおよび乗算パラメータａは、乗数の位相幾何学（Ｔｏｐｏｌｏｇｉｅ ｄｅｓ Ｍｕｌｔｉｐｌｉｋａｔｏｒｓ）、および、ドイツ特許第３６３１９９２号Ｃ２に記載の予測規則によって生じる。
【００２４】
換算桁送り値ｓ_Ｎおよび換算パラメータｂは、同じくドイツ特許第３６３１９９２号Ｃ２に記載されているように、Ｚ記録器の最新の内容を、値２／３×Ｎと比較することにより決定される。この比較をもとにＺＤＮ方法という名前が付けられている（ＺＤＮ＝Ｎの３分の２（ＺＤＮ＝Ｚｗｅｉ Ｄｒｉｔｔｅｌ Ｎ））。
【００２５】
ＺＤＮ方法では、図９に示すように、係数乗算を、３演算数加算（図９のブロック９５０）に戻す。この場合、計算時間を速めるために、乗算予測方法と同時に換算予測方法が用いられる。従って、Ｚ／ＮＺのモンゴメリー換算と比べて、３桁の大きさ（Ｇｒｏｅｓｓｅｎｏｒｄｎｕｎｇ ｖｏｎ ３）の因数によって、計算時間を有利にすることができる。
【００２６】
既に説明したように、ドイツ特許３６３１９９２号Ｃ２に記載されているＺＤＮ方法は、Ｚ／ＮＺ算術に対してのみ有効に作用するものであり、ＧＦ（２^ｎ）算術には適していない。従って、現在のところ、ＧＦ（２^ｎ）算術の、ＧＦ（２^ｎ）に関する係数乗算の速度を速くするために用いられる、計算時間の速い先見越し方法はない。
【００２７】
本発明の目的は、ＧＦ（２^ｎ）の係数乗算を迅速に行うための概念を提供することにある。
【００２８】
この目的は、特許請求項１に記載の係数乗算を行うための方法、特許請求項７に記載の係数乗算を行うための装置、または、特許請求項１１に記載の算術演算装置により達成される。
【００２９】
本発明は、乗算予測方法と換算予測方法との双方を使用することにより、ＧＦ（２^ｎ）の係数乗算を速く行えるということに基づいている。乗算予測方法では、乗算桁送り値が計算される。乗算予測方法と並行して行われることが有利である換算予測方法では、換算桁送り値が計算される。この場合、換算桁送り値は、乗算桁送り値だけ桁送りされた中間結果の多項式の次数と、実際の係数多項式の次数との差に等しい。乗算桁送り値により累乗されている変数を、中間結果の多項式に乗算する一方、換算桁送り値により累乗されている変数を、係数多項式に乗算する。これにより、ＧＦ（２^ｎ）算術の３演算数加算が公式化される。そうして、乗算桁送り値だけ桁送りされた最後の中間結果の多項式を被乗数に足し合わせ、次に、更新された中間結果の多項式を得るために、この足し合わされたものから、換算桁送り値だけ桁送りされた係数多項式を減算することにより、新しい中間結果の多項式を計算することができる。次に、全ての工程を繰り返す。ただし、今度は更新された中間結果の多項式および最後の工程において桁送りされた係数多項式を用いて、全ての部分の積を続けて加算するため、すなわち、乗数の全ての累乗が処理されてしまうまで、全ての工程を繰り返す。
【００３０】
ＧＦ（２^ｎ）算術における変数ｘの累乗の係数が、「０」または「１」のどちらかの値を有していてもよいということにより、３演算数加算は、とりわけ簡易化される。これにより、加算と減算との双方は、簡単なＸＯＲ結合となる。その結果、単にＧＦ（２^ｎ）の加算のための算術装置としての算術演算装置は、加算器を必要とせず、３演算数のビット毎の（ｂｉｔｗｅｉｓｅ）ＸＯＲ結合のみを必要とする。
【００３１】
双数の算術演算装置、すなわち、Ｚ／ＮＺの係数乗算と、ＧＦ（２^ｎ）の係数乗算との双方を行う算術演算装置の場合、加算器の各ビットのための桁上げを行わない、つまり考慮しないことによって、ＺＤＮ方法のために、既存の３演算数加算器を、ＧＦ（２^ｎ）演算用に簡単に変更できる。
【００３２】
ただし、ＧＦ（２^ｎ）の係数乗算を計算するための本発明に基づく方法は、直列並列構造（Ｓｅｒｉｅｌｌ−Ｐａｒａｌｌｅｌ−Ａｒｃｈｉｔｅｋｔｕｒ）を有している。３演算数加算は、好ましくは、常に並行して行われる、すなわち、一般的に、幅１５０〜１１００ビットを有する、加数の全てのビットに対して行われることである。従って、次の連続した、本発明に基づく方法の反復において、新しい部分積が計算され、続く並行した３演算数加算において、既存の中間結果に加えられる。
【００３３】
係数乗算を計算するための本発明に基づく概念は、ＧＦ（２^ｎ）のためのモンゴメリー乗算と比較して、２桁の因数により、速度を最大にできるという長所がある。
【００３４】
本発明に基づく概念の他の長所は、既に提供したＧＦ（２^ｎ）の係数乗算のための効果的な方法により、例えば、ＧＦ（２^ｎ）のＥＣＤＳＡアルゴリズム（ＥＣＤＳＡ＝楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ＝Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｇｏｒｉｔｈｍ））を計算できることにある。このアルゴリズムは、「金融サービス産業のための公開鍵暗号法：楕円曲線Ｄ．Ｓ．Ａ．」（”Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ｆｏｒ ｔｈｅ Ｆｉｎａｎｃｉａｌ Ｓｅｒｖｉｃｅｓ Ｉｎｄｕｓｔｒｙ： Ｔｈｅ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄ．Ｓ．Ａ．”， ＡＮＳＩ Ｘ９．６２−１９９８）に記載されている。
【００３５】
楕円曲線暗号化は、整数に関連した係数算術を基礎とする暗号化と比べ、非常に小さな数であっても、類似した安全基準を得られるという点で、好まれている。Ｚ／ＮＺについてのＲＳＡ方法では、１０２４ビット幅数で、確かな安全基準が得られる一方で、ＧＦ（２）についての多項式では、変数ｘの１５０〜３００累乗の次数で、十分に確かな安全基準が得られる。
【００３６】
本発明に基づく他の長所は、係数乗算を計算するための本発明の概念を、ＺＤＮ方法のための既存の算術演算装置に難なく簡単に統合できることにある。なぜなら、実際に長い数の算術演算装置（Ｌａｎｇｚａｈｌｒｅｃｈｅｎｗｅｒｋ）、つまり、３演算数加算器を、ビット毎の桁上げを抑制することにより、ＧＦ（２^ｎ）に簡単に適合できるからである。ＧＦ（２^ｎ）のための、換算予測アルゴリズム算術装置および乗算予測アルゴリズム算術装置は、Ｚ／ＮＺのための、換算予測アルゴリズム算術装置および乗算予測アルゴリズム算術装置とは異なっているが、このことは、算術演算装置の全体的な特性に対しては決定的に重要なことではない。なぜなら、ここでは、たった８または１６ビット幅程度の小さな数の加算、桁送り、または、減算の結果、制御装置とも称される算術装置の集積回路領域（ｄｉｅ Ｃｈｉｐｆｌａｅｃｈｅ）は、長い数を演算する算術演算装置と比較して、すなわち、２０４８ビット幅を十分に越えていてもよい（Ｚ／ＮＺおよびＧＦ（２^ｎ）のための双数の実施）３演算数加算器と比較して、あまり重要ではないからである。
【００３７】
ＧＦ（２^ｎ）についての係数乗算のための本発明に基づく概念の他の長所は、Ｚ／ＮＺ算術にのみ機能するＺＤＮ方法と比べ、多数の演算を簡易化できることにある。それゆえ、本発明に基づくＧＦ（２^ｎ）係数乗算では、係数の２／３倍との比較を行う必要がない。中間結果の多項式の次数と係数多項式の次数との比較により、ＧＦ（２^ｎ）についての比較を簡単に行える。乗算桁送り値の期待値、および、換算桁送り値の期待値が同一なので、２つの予測方法は相互に切り離されており、その結果、２つの予測方法は、相互に独立して作用することが可能であり、これに伴って、計算時間は速くなる。
【００３８】
本発明の好ましい実施例を、以下に、添付の図を参考にして詳しく説明する。
【００３９】
図１は、ＧＦ（２^ｎ）についての係数累乗法を具体的に説明するためのフローチャートを示す。図２は、本発明に基づく方法の高レベルのフローチャートを示す。図３は、乗算桁送り値を計算するための、乗算予測方法のフローチャートを示す。図４は、換算桁送り値を計算するための、換算予測方法のフローチャートを示す。図５は、ＧＦ（２^ｎ）算術またはＺ／ＮＺ算術のための３演算数加算器の一部を示す。図６は、桁上げ遮断機能（Ｃａｒｒｙ−Ａｂｓｃｈａｌｔ−Ｆｕｎｋｔｉｏｎ）の詳細な図を示す。図７は、Ｚ／ＮＺ−ＧＦ（２^ｎ）算術演算装置のブロック図を示す。図８ａ〜図８ｂは、換算桁送り値の計算を具体的に説明するための概略的な図を示す。図９は、Ｚ／ＮＺについての係数乗算を行うためのＺＤＮ方法の概要を示す図である。
【００４０】
図１は、係数累乗法
Ｃ（ｘ）＝（Ｍ（ｘ））^ＥｍｏｄＮ（ｘ）
を、一続きの乗算に分解するための一般的なフローチャートを示す。Ｍ（ｘ）およびＮ（ｘ）は、変数ｘの多項式である。Ｅは、ビット長Ｌ（Ｅ）を有する二進法表示の指数である。
【００４１】
アルゴリズムは、基本的には、指数Ｅのビット、すなわちＥ（ｅ）が１に等しいかどうかを調べるものである。Ｅ（ｅ）＝１である場合、結果として生じる記録器の現在の内容に、Ｍ（ｘ）を掛け算する。続いてすぐに、係数多項式Ｎ（ｘ）を用いて係数換算を行う。これに対し、指数のビットが０に等しい場合には、Ｍ（ｘ）を掛け算しない。Ｅ（ｅ）＝１である場合もそうでない場合も、記録器Ｃ（ｘ）の最新の内容を、それ自身により乗算、すなわち、２乗し、これに基づいて係数換算を行う。その結果、指数の桁の標数、すなわちｅは、１だけ上昇される。そうして、繰り返し、指数Ｅのビットが１に等しいかどうかを調べる。このことを、指数Ｅの全ての桁を処理してしまうまで、つまり、ｅ＝Ｌ（Ｅ）となるまでずっと実施する。そうしてからアルゴリズムを終了すると、Ｃ（ｘ）の記録器には、係数累乗法の結果が生じている。従って、係数累乗法の中央演算は、被乗数Ｃ（ｘ）に乗数Ｍ（ｘ）を掛ける係数乗算である。
【００４２】
図２は、被乗数に乗数を係数乗算するための本発明に基づく方法の高レベルのブロック図を示す。この方法は、開始ブロック２００から始める。ブロック２０２において、変数ｘの多項式である広域変数Ｍ、Ｃ、および、Ｎを初期化する。次に、ブロック２０４において、中間結果の多項式Ｚを、０に初期化する。ブロック２０６において、制御変数（Ｌａｕｆｖａｒｉａｂｌｅ）ｍを、Ｌ（Ｍ）に初期化する。Ｌ（Ｍ）は、乗数Ｍの長さをビットで表している。従って、Ｌ（Ｍ）は、乗数多項式の次数に相当している。さらに、ブロック２０８において、制御変数ｎを０に初期化する。制御変数ｎの意味については、後で説明する。続いて、乗算予測方法２１０と換算予測方法２１２とを、好ましくは並行して実施する。乗算桁送り値ｓ_Ｚを計算するために、乗算予測方法を用いる。好ましくは、乗算予測パラメータａを計算するために、同様に、乗算予測方法を用いることである。
【００４３】
換算桁送り値ｓ_Ｎを計算するために、換算予測方法を用いる。好ましくは、換算予測パラメータｂを計算するために、換算予測方法を用いることである。
【００４４】
ブロック２１４において、乗算桁送り値ｓ_Ｚにより累乗されている変数ｘを、実際の中間結果の多項式Ｚに乗算することによって、桁送りされた中間結果の多項式Ｚ´を計算する。
【００４５】
好ましくはこれと並行して、ブロック２１６において、換算桁送り値ｓ_Ｎにより累乗されている変数ｘを、実際の係数多項式Ｎに乗算することによって、桁送りされた係数多項式Ｎ´を計算する。
【００４６】
次に、ブロック２１８において、本発明に基づく乗算方法の中央演算である、いわゆる３演算数加算を実施する。ブロック２１８において、更新された中間結果の多項式Ｚを計算する。この多項式Ｚは、中間結果多項式Ｚ´を、乗算予測パラメータａが乗算されている被乗数Ｃ、および、換算予測パラメータｂが乗算されている桁送りされた係数多項式Ｎ´に加算することによって得られる。
【００４７】
ブロック２２０において、制御変数ｍが０に等しいかどうか、および、制御変数ｎが０に等しいかどうかを同時に調べる。制御変数ｍが０に等しい場合は、乗数Ｍ（ｘ）の全てのビットが処理されていることを意味している。制御変数ｎが０に等しい場合は、桁送りされた係数多項式Ｎ´が、ブロック２０２のもともとの多項式Ｎと同じであることを意味している。
【００４８】
制御変数ｍが０に等しく、制御変数ｎが０に等しければ、ブロック２２０では、「はい」を応答し、その結果、係数乗算の結果、すなわち、Ｚ（ｘ）を、ブロック２２２に出力できる。従って、係数乗算のためのこの方法は、ブロック２２４で終了する。
【００４９】
これに対し、ブロック２２０にて「いいえ」が応答されれば、このことは、処理されていない乗数のビットがまだ存在しているか、あるいは、係数多項式用の記録器に保たれる係数多項式Ｎ´が、ブロック２０２で定義されたもともとの係数多項式よりもさらに大きいということを意味している。言い換えれば、このことは、係数多項式の記録器に保たれている、最新の多項式の次数は、ブロック２０２で定義されたもともとの係数多項式Ｎの次数よりも大きいことを意味している。この場合には、図２に折り返し線２２６として示すように、乗算予測方法と、換算予測方法とを改めて実施するために、もとに戻る。Ｚ記録器がブロック２０４における初期化により０に設定されている第１工程とは逆に、この場合には、Ｚ記録器には、先の工程における３演算数演算２１８の結果が生じている。
【００５０】
この場合、同じく、係数記録器Ｎには、ブロック２０２で定義されたもともとの係数Ｎはもはや無く、換算桁送り値ｓ_Ｎだけ桁送りされた係数多項式Ｎ´がある。従って、ブロック２０２で定義されたもともとの係数Ｎ（ｘ）は、第１初期化工程の間だけ、Ｎ記録器にある。この場合、反復工程（折り返し線２２６）の間に、係数記録器には常に桁送りされた係数多項式、すなわち、換算桁送り値ｓ_Ｎにより累乗されている変数ｘが乗算されている係数多項式が存在する。
【００５１】
以下に図３について説明する。図３は、乗算予測方法、すなわち、図２のブロック２１０の詳細な図を示している。この乗算予測方法は、ブロック３００から始まる。広域変数として、図２のパラメータｍ、後でさらに説明する他の制御変数ｃｕｒ_ｋ、および、乗数Ｍが含まれている。このことを、図３のブロック３０２に示す。次に、ブロック３０４において、乗算桁送り値ｓ_Ｚを０に初期化する。さらに、後でさらに説明する乗算予測パラメータａを、値＝１に初期化する（ブロック３０６）。
【００５２】
次に、ブロック３０８において、現在論議の対象となっているビット、または、現在処理されているｘの累乗の係数が、０に等しいかどうか調べる。ブロック３０８において、現在処理されている乗数のビットが０に等しくないと決定されると、すなわち、ブロック３０８で「はい」を応答すると、制御変数ｍは、ブロック３１０において、１だけ上昇される。さらに、乗算桁送り値ｓ_Ｚは、同じくブロック３１２において、１だけ上昇される。次に、ブロック３１４において、乗算予測方法、すなわち、乗算予測パラメータａおよび乗算桁送り値ｓ_Ｚの結果パラメータが出力される。
【００５３】
ブロック３０８において、「いいえ」を応答すると、他の判断ブロック３１６に進む。ここで、制御変数ｍが、乗数Ｍの長さ、つまり、次数よりもさらに小さいかどうかを決定する。さらに、現在の乗算桁送り値ｓ_Ｚがより小さいか、あるいは、パラメータｃｕｒ_ｋに等しくないかどうかを調べる。２つの質問に対して「はい」が応答されると、パラメータｍを１だけ上昇させるために、ブロック３１８に進む。さらに、ブロック３２０において、乗算桁送り値ｓ_Ｚも１だけ上昇される。これに続いて、乗数Ｍの次数のビットを調べる。このことを、図３において、折り返し線３２２で表している。
【００５４】
これに対し、ブロック３１６にて、ブロック３１６の２つの質問のうち１つに対して、「いいえ」を応答すると、ブロック３２４に進む。このブロック３２４において、乗算予測パラメータａを０に設定する。それゆえ、ブロック３１４に出力される乗算予測パラメータａは、０であっても１であってもよい。そして、乗算予測方法は、ブロック３２６にて終了する。
【００５５】
以下に、乗算予測パラメータの機能形態について説明する。本発明に基づいて使用される乗算予測方法は、０を上回る変数の桁送りによるＧＦ（２^ｎ）乗算のための先見越しアルゴリズムであり、変数の桁送り数を任意に増やすことはできず、多くても、値ＣＵＲ_ｋに等しいはずである。「ＣＵＲ_ｋ」は、「現在のｋ（”Ｃｕｒｒｅｎｔ ｋ”）」を表し、すなわち、「パラメータｋの現在の値」を意味している。
【００５６】
以下に、例として、係数「１０００１」を有する乗数多項式を調査する。まず、その最上位ビットを調べる。このビットは、「１」の値を有している。その結果、ブロック３０８では「はい」を応答する。すると、パラメータｍが１だけ上昇されることになり、乗算桁送り値ｓ_Ｚも同じく１だけ上昇されることになる。これにより、乗算予測アルゴリズムは終了してしまう。なぜなら、調べた乗数のビットは、被乗数Ｃの３演算数加算により加算される必要のある「１」の値を有していたからである。
【００５７】
次に乗算予測アルゴリズムを実施する際に、第２ビットを調べる。このビットは、０の値を有している。その結果、ブロック３０８において、「いいえ」が応答される。調べられたビットは、ちょうど被乗数の第２ビットであり、乗算桁送り値ｓ_Ｚは、ブロック３０４における初期化により、このとき０であるので、ブロック３１６では「はい」を応答する。その結果、制御変数ｍは、１だけ上昇され（３１８）、同じく、乗算桁送り値は、１だけ上昇され（３２０）、次に、折り返し線３２２を介して、ブロック３０８に進む。次のビットは、同じく値「０」を有しているので、このブロックでもまた「いいえ」を応答し、ブロック３１６では、ＣＵＲ_ｋである。Ｍは、Ｌ（Ｍ）よりまだ小さいので、質問に対して「はい」が応答される。ｓ_Ｚは、ちょうど１の値を有している。ＣＵＲ_ｋの値が２であっても、この質問に対して、「はい」が応答される。その結果、ブロック３１８および３２０において、ｍおよびｓ_Ｚの上昇が改めて行われる。ブロック３２０を通った後、このとき、ｓ_Ｚは、２の値を有している。それから、支線３２０を介して、次のビットが１を有しているか０を有しているか決定するために、改めてブロック３０８に進む。上記実施例では、ブロック３０８で改めて「いいえ」を応答する。なぜなら、ここでは、０が連続した第３ビットが調べられるからである。しかし、ブロック３１６では、この場合、「いいえ」を応答する。なぜなら、ｓ_Ｚは２であり、変数ＣＵＲ_ｋは同じく２であるからである。第３の０が新しい桁送りのために使用できるとしても、このことは、乗算予測方法が実際は取り消されていることを意味している。しかし、ｓ_Ｚの上限は決められている必要がある。そうでなければ、図２の工程２１４において計算される、桁送りされる中間結果の多項式Ｚ´を格納できるように、無限に長いＺ記録器を備える必要があるからである。従って、ＣＵＲ_ｋは、Ｚ記録器の現在の動きに応じて、つまり、速い速度が得られるようなできるだけ大きな桁送り値ｓ_Ｚが許容されるように、しかし、同時に、桁送りされた中間結果の多項式Ｚ´のために制限されている記録器の長さで事足りるように設定される。図２のブロック２１８における３演算数演算は、演算数演算になる。なぜなら、図３のブロック３２４のパラメータａが０に設定されているからである。
【００５８】
図３から分かるように、ブロック３２４の支線において、ｍはこれ以上、上昇されない。その結果、乗算予測アルゴリズムを改めて実施するときには、第３番目の０ビットを、ブロック３０８で連続して調べる。このビットは、０の値を有しているので、ブロック３０８では、再び「いいえ」を応答する。その結果、乗算桁送り値ｓ_Ｚは、１だけ増加され、制御変数も、ブロック３１８において上昇される。このとき、乗数の最後のビット、つまり「１」が調べられる。このビットは、０ではないので、ブロック３０８では、「はい」を応答し、制御変数が最後に増加され、この反復のための乗算予測アルゴリズムが終了するまで（ブロック３２６）、乗算桁送り値ｓ_Ｚは、同じくもう一度増加される。このとき、被乗数の全てのビットは調べられているので、その結果、図２の繰り返し線２２６は終了する。なぜなら、この例では、ブロック２２０において、ｍが０に等しいかどうか調べられるからである。
【００５９】
以下に、図２に参照番号２１２により示す換算予測方法を説明するため、図４について説明する。ブロック４００から換算予測方法を開始する。ブロック４０２において、様々な広域変数を定義する。これら広域変数のうち、特に、ＮおよびＺに注目する。Ｎは、先の工程の係数多項式の記録値であり、一方、Ｚは、同じく先の工程の更新された中間結果の多項式である。ｋは、Ｚの最大桁送り値、ＣＵＲ_ｋは、Ｚの現在の桁送り値、および、ＭＡＸは、長さ、すなわち、左へ桁送りされた多項式ＮおよびＺを格納するために存在している過剰緩衝記憶装置（ｏｖｅｒｆｌｏｗ ｂｕｆｆｅｒ）のビット数を表している。図２のブロック２１６を考慮すれば、任意の大きな換算桁送り値ｓ_Ｎが存在する場合、乗算予測方法の場合と同じように、Ｎのための任意に大きな記録器を備える必要があるということが分かる。しかし、このことは、空間および効率を考えた場合、望ましくない。その結果、パラメータＭＡＸにより、係数多項式は、同じく、特定のビット数だけ左へ、すなわち、上へ桁送りされてもよいことも考慮される。
【００６０】
次に、ブロック４０４において、後に説明するパラメータＳ_ｉを、０に初期化する。これにより、ブロック４０６において、過剰緩衝記憶装置にある、Ｎのビット数を示しているパラメータｎが、０に等しいかどうか、あるいは、Ｓ_ｉがｋに等しいかどうかが決定される。ブロック４０６で「はい」を応答すると、ブロック４０８に進む。ブロック４０８において、換算予測パラメータｂを、０に設定する。これに対し、ブロック４０６の質問に対して「いいえ」を応答すると、パラメータｎは、１だけ増加する（ブロック４１０）。同時に、パラメータＳ_ｉも、ブロック４１２に示すように、１だけ増加する。続いて、ブロック４１４において、中央比較が行われる。この中央比較により、３演算数演算（図２のブロック２１８）において、中間結果の多項式の係数換算を行うために、係数多項式をどれだけ桁送りしなければならないかを決定する必要がある。このため、補助換算桁送り値Ｓ_ｉは、ｘの乗算（ただし、ｘは、Ｓ_ｉにより累乗されている）の多項式の次数に、先の工程の更新された中間結果の多項式を乗算して、現在の係数多項式の次数に等しくなるように特定される。このことは、段階的に、折り返し線４１６が示すように、ブロック４０６において、「はい」という結果が得られるまで、あるいは、ブロック４１４において、「はい」という結果が得られるまでの間ずっと実施される。ブロック４１４で、「はい」を応答すると、ブロック４１８において、換算予測パラメータｂを、１に設定する。次に、ブロック４２０において、新しいパラメータｎを、乗算桁送り値ｓ_Ｚと、実際の値ｎとの差から計算する。次に、事実上の換算桁送り値Ｓ_Ｎが、乗算桁送り値ｓ_Ｚと補助換算桁送り値ｓ_ｉとの差を形成することによって、ブロック４２２において計算される。
【００６１】
ただし、乗算桁送り値ｓ_Ｚは、図２の矢印２３０に示すような、実際に並行して行われる乗算予測アルゴリズムにより与えられる。補助換算パラメータｓ_ｉを導入しなければ、実際には乗算予測方法とこれに続く換算予測方法とを連続して実施できるのみであり、効率のうえからはこれは望ましくない。従って、補助換算パラメータｓ_ｉを使用し、この補助換算パラメータｓ_ｉにより、換算桁送り値ｓ_Ｎの事実上の計算をする限り、費用のかかる折り返し線（図４の折り返し４１６）を、乗算予測アルゴリズムと実際に並行して処理でき、一方で、換算桁送り値Ｓ_Ｎの実際の計算は、２つの短い数ｓ_Ｚとｓ_ｉとの差を得ることにより、迅速に行うことができる。従って、順序は以下のようにある。ｓ_Ｚとｓ_ｉとを並行して計算する。次に、ｓ_Ｚを、図２の支線２３０（図４にも示されている）を介して、乗算予測アルゴリズムから、換算予測アルゴリズムへと供給する。その結果、次の周期において、換算桁送り値ｓ_Ｎもすぐ利用できる。これについては、後で、図８ａ〜図８ｃを参考にして詳しく説明する。
【００６２】
ブロック４２２の後、ブロック４２４において、ｎが、ＭＡＸ−ｋよりも大きいかどうかを決定する。この質問に対して「はい」が応答されると、ブロック４２６において、新しいｃｕｒ_ｋを計算する。ブロック４２４の質問に対して、「いいえ」が応答されると、ブロック４２８において、ｃｕｒ_ｋがｋに等しくなるように設定される。次に、ブロック４３０において、換算予測方法の結果値、すなわち、ｂおよびｓ_Ｎが出力される。そうして、換算予測方法は、ブロック４３２で終了する。
【００６３】
乗算予測パラメータａおよび換算予測パラメータｂ、ならびに、メモリー管理パラメータｎ、ＭＡＸ、ｋ、およびｃｕｒ_ｋの詳細な説明について、ドイツ特許３６３１９９２号Ｃ２が参照される。パラメータａおよびｂが＋１、０、および−１の値をとってもよいＺ／ＮＺのためのＺＤＮ方法とは異なり、本発明に基づく方法における相当するパラメータａ、ｂは、０および１の値のみをとることができる。予測パラメータａおよびｂは、本発明にかかる係数乗算のためには、任意にのみ必要である。つまり、任意に大きくない格納場所をＮおよびＺのために使用できる。しかし、本発明の方法は、任意の大きさの記録器を使用できるという条件下において、一般的に何の困難もなく実施される。この場合、乗算予測方法が取り消されてしまうことはなく、乗数の「１」が再び見出されるまでの間ずっと実施されている。そのときまで、図２のブロック２１４を参照すると、ｓ_Ｚは、特定のできる限り大きな数を有している。その結果、桁送りされた中間結果の多項式Ｚ´は、極めて大きな値を取ることが可能である。次に、ブロック２１８において、乗数１が見出されたという事実に基づき、被乗数を、桁送りされた中間結果多項式Ｚ´に加える。
【００６４】
しかし、重要な特徴は、それぞれの乗算工程と同時に、係数換算も行われることであり、これにより、数値全てを許容限度（ｅｒｔｒａｅｇｌｉｃｈｅｎ Ｇｒｅｎｚｅｎ）に含むことができる。
【００６５】
このため、本発明に基づく換算桁送り値ｓ_Ｎは、桁送りされた係数多項式の次数が、実際の中間結果の多項式の次数に等しくなるように択される。桁送りされた係数多項式が、Ｚ´（ｘ）とＣ（ｘ）との和から減算される場合、通常、更新された中間結果Ｚは、Ｚ´よりもずっと小さい。これにより換算が行われ、図２の工程２１８で計算される、更新された中間結果の多項式Ｚは、ブロック２０２のもともとの係数多項式と必ずしも関連して換算されるのではなく、例えば、全ての反復の間に、左へと桁送りされた係数多項式、すなわち、より高い次数を有する係数多項式にのみ関連して換算されていてもよいことが分かる。しかし、必ずしもそうである必要はない。しかし、このような場合が生じると、ｎが０に等しいかどうか、すなわち、Ｎビットが過剰緩衝記録装置にあるかどうかを決定する工程２２０により、更新された中間結果から係数の他の減算を行い、その結果、次に、Ｚは、少しずつもともとの余剰群（Ｒｅｓｔｋｌａｓｓｅ）へと返送される。つまり、ｎが０に等しい場合は、Ｎのビットが、もはや過剰緩衝記憶装置に存在しないことを意味している。このことは、最終的に得られる桁送りされた係数多項式が、ブロック２０２のもともとの係数多項式に等しいことを同じく意味している。
【００６６】
従って、係数乗算をするための本発明に基づく方法は、基本的には、予測パラメータａおよびｂがなくても実施できる。しかし、任意の乗数が想定されている場合には、ＺおよびＮのための、論理的に無限の記録器が必要となる。
【００６７】
ＺおよびＮの格納限界がある場合、すなわち、予測パラメータａおよびｂが０でもよい場合には、乗算予測パラメータａは０に等しいことを意味し、被乗数は、桁送りされたＺ´に加えられない。これと同じように、０に等しい換算予測パラメータｂは、桁送りされた係数多項式が、桁送りされた中間結果の多項式Ｚ´よりも大きいことを意味するので、換算する必要はない。従って、係数減算を、同じく省略することができる。このような場合には、３演算数演算は、完全になくなる。
【００６８】
ただし、この際、記録器ＺおよびＮの緩衝記憶装置が制限されている場合、変数ｍが、０の値に達しない限り、Ｎは、そのもともとのＭＳＢ（Ｈｏｍｅ−ＭＳＢ）から少なくともｋビット遠ざかっているということにも注意しなければならない。
【００６９】
さらに、ＧＦ（２^ｎ）算術の場合、すなわち、多項式の係数が、０または１だけでよい場合、加算演算は、減算演算に相当し、一般的に、ＸＯＲ結合として実施できる。しかし、多項式の係数が、他の数の方式、例えば、８進数方式（Ｏｋｔａｌ−Ｓｙｓｔｅｍ）、または、１０進数方式（Ｄｅｚｉｍａｌ−Ｓｙｓｔｅｍ）に含まれている場合、当然、減算は加算に相当していない。
【００７０】
補助換算桁送り値ｓ_ｉを用いる換算桁送り値ｓ_Ｚの計算を示すために、以下に、図８ａ〜図８ｃについて説明する。図８ａには、中間結果の多項式Ｚおよび係数多項式Ｎを示す。単なる例として、中間結果の多項式は、次数４、すなわち、４ビットを有しており、一方、係数多項式は、次数９、すなわち、９ビットを有している。図２のブロック２１４において、桁送りされた中間結果の多項式Ｚ´を計算する。この計算は、ｓ_Ｚにより累乗されている変数ｘを乗算することにより行う。従って、乗数に８個の０があり、これにより、乗算桁送り値ｓ_Ｚは８となる。係数換算を行うためには、係数Ｎは、桁送りされた中間結果の多項式Ｚ´の桁数（Ｇｒｏｅｓｓｅｎｏｒｄｎｕｎｇ）になっている必要がある。本発明に基づき、係数多項式Ｎは、桁送りされた中間結果の多項式Ｚ´の次数と、桁送りされた係数多項式Ｎの次数とが同じくなる程度にまで桁送りされている。このためには、図８ｂから分かるように、ｓ_Ｎの換算桁送り値は３に等しくなければならない。
【００７１】
図８ｂから、同じく、ｓ_Ｎの調査は、実際には、ｓ_Ｚが計算されている場合にはじめて行えることが分かる。すなわち、本発明にとって好ましいように、図２のブロック２１０と２１２とを並行して実施することはできない。この理由により、補助予測パラメータｓ_ｉが挿入される。図８ａから分かるように、補助桁送りパラメータｓ_ｉは、中間結果の多項式Ｚと、係数多項式Ｎとの次数の差に等しい。実際の工程のｓ_Ｚを知らなくてもこの値を計算できることがｓ_ｉの利点である。
【００７２】
図８ｃから、ｓ_Ｚは、ｓ_ｉとｓ_Ｎとの和に常に等しいということが分かる。従って、ｓ_Ｎは、以下の等式が当てはまるようにｓ_Ｚおよびｓ_ｉと常に関連している。
ｓ_Ｎ＝ｓ_Ｚ−ｓ_ｉ
従って、ｓ_Ｎを決定するための時間のかかる反復方法を、ｓ_ｉを決定するための時間のかかる反復方法（折り返し線４１６）と、迅速な差演算（図４のブロック４２２）とに分解できる。これにより、２つの予測方法をほぼ並行して実施できる。この際、唯一の連続している構成部分は、ブロック４２２の（図４）の計算の前に、ｓ_Ｚの実際の値が乗算予測アルゴリズムにより既に計算され、供給されている（図２の矢印２３０）ことである。
【００７３】
既に説明したように、ＧＦ（２^ｎ）についての係数乗算を計算するための本発明に基づく概念の重要な利点は、この概念をＺＤＮ方法のための既存の長い数の算術演算装置に統合できることである。図５は、本発明に基づき適合されている、Ｚ、ａＣ、および、ｂＮによる３演算数加算を行うための３演算数算術演算装置の一部を示す。
【００７４】
図５に、相互に接続されている３つのビット片［ｉ］、［ｉ−１］、［ｉ−２］を示す。各ビット片は、出力部側において、更新された中間結果多項式の１ビットＺ［ｉ］、Ｚ［ｉ−１］、または、Ｚ［ｉ−２］を得るために、３ビット計数器５００および、全加算器５１０を備えている。全加算器は、さらに、次に高い全加算器の桁上げ入力部のための桁上げ出力部（キャリー（Ｃａｒｒｙ）＝桁上げ）を備えている。例えば、多項式が、次数２００により処理されている場合、図５の２００ビット片加算器は、並列に接続されている必要がある。
【００７５】
図５のビット片を、ＧＦ（２^ｎ）のために変更するために、図５に示すように、ＵＮＤ格子５２０を、３ビット計数器の上側の出力部と、次に高い段階の全加算器の下から２番目の入力部との間に挿入する必要がある。０が、イネーブル入力部５３０に格納されると、ｘの値は、常に０になっている。次に、ｙおよび０の加算のために、全加算器５１０の機能は常に衰退する。これに対して、Ｚ／ＮＺの場合、ＵＮＤ格子のイネーブル入力部に、「１」が提供される。その結果、ＵＮＤ格子は、他の作用を有していない。
【００７６】
従って、ＧＦ（２^ｎ）では、ＵＮＤ格子の出力が０に等しい。これに対し、Ｚ／ＮＺでは、Ｘが必要であり、ＵＮＤ格子の出力が０に等しくなくてもよい。それゆえ、イネーブルは、ＵＮＤ格子により実現される。これに対し、ＧＦ（２^ｎ）、つまり、イネーブル入力部５３０において０の場合、全加算器における加算は些細なことである。
【００７７】
図６は、ＵＮＤ格子５２０の状態を示す。図５に部分的に示す算術演算装置は、イネーブル信号ＳＣ＝１である場合、標準加算器として機能する。これに対し、算術演算装置は、イネーブル信号ＳＣ＝０である場合、ＸＯＲ回路として機能する。
【００７８】
図７は、Ｚ／ＮＺおよびＧＦ（２^ｎ）のための算術演算装置の概略的なブロック図を示す。算術演算装置は、長い数の算術装置７００の周りに分類されている。この算術装置７００は、既述の３演算数演算を、Ｚ／ＮＺまたはＧＦ（２^ｎ）のために実施する。
【００７９】
算術演算装置は、Ｚ／ＮＺ制御装置７１０、ＧＦ（２^ｎ）制御装置７２０、および、モード選択装置７３０をさらに含んでいる。算術演算装置が、演算に、整数の係数を計算する場合、モード選択７３０は、算術装置７００を、第８番目の加算演算が実施され、この場合、算術装置は、Ｚ／ＮＺ制御装置７１０と出力部側および入力部側において接続されているように駆動する。これに対し、算術演算装置は、ＧＦ（２^ｎ）算術を行う場合、モード選択７３０は、算術装置７００を、加算の代わりにＸＯＲ演算が実施されるように起動し、算術装置の入力部と出力部とは、ＧＦ（２^ｎ）制御装置と接続されている。
【００８０】
それゆえ、整数係数算術と、多項式係数算術との双方を算術演算装置に組み込むために、別個の算術装置を必要とはしない。
【００８１】
ただし、３演算数演算が、全てのビットのために並行して行われるという事実に基づき、ほとんどの集積回路領域は、算術装置７００によって消費され、一方で、制御装置７１０および７２０では、より短い数で、より小さな計算が実施されるのでビット領域は特に重要ではなくなる。
【００８２】
従って、整数算術と多項式算術との双方のために、独自の算術演算装置を必要とする算術演算装置とは反対に、係数乗算を計算するための本発明に基づく概念によれば、集積回路領域を５０％近く減少できる。特にスマートカードに対して、この集積回路領域の節約は、競争上の優位性を導く。
【図面の簡単な説明】
【図１】
ＧＦ（２^ｎ）における係数累乗法を具体的に説明するためのフローチャートである。
【図２】
本発明に基づく方法の高レベルのフローチャートである。
【図３】
乗算桁送り値を計算するための、乗算予測方法のフローチャートである。
【図４】
換算桁送り値を計算するための、換算予測方法のフローチャートである。
【図５】
ＧＦ（２^ｎ）算術またはＺ／ＮＺ算術のための３演算数加算器の一部を示す図である。
【図６】
桁上げ遮断機能の詳細な図である。
【図７】
Ｚ／ＮＺ−ＧＦ（２^ｎ）算術演算装置のブロック図である。
【図８】
ａ〜ｂは、換算桁送り値の計算を具体的に説明するための概略的な図である。
【図９】
Ｚ／ＮＺにおいて係数乗算を行うためのＺＤＮ方法の概要を示す図である。
【符号の説明】
２００ 係数乗算のための方法の開始
２０２ 広域変数
２０４ 中間結果多項式の初期化
２０６ ｍの初期化
２０８ ｎの初期化
２１０ 乗算予測方法
２１２ 換算予測方法
２１４ 中間結果多項式の生成
２１６ 桁送りされた係数多項式の生成
２１８ ３演算数加算
２２０ アルゴリズムが終了したかどうかの調査
２２２ Ｚの出力
２２４ 係数乗算するための方法の終了
２２６ 折り返し線
２３０ ｓ_Ｚ桁上げ
３００ 乗算予測方法の開始
３０２ 広域変数
３０４ ｓ_Ｚの初期化
３０６ ａの初期化
３０８ 処理されたビットが０または１であるかどうかの決定
３１０ ｍの増加
３１２ ｓ_Ｚの増加
３１４ ａおよびｓ_Ｚの出力
３１６ さらに桁送りできるかどうかの決定
３１８ ｍの増加
３２０ ｓ_Ｚの増加
３２２ 折り返し線
３２４ ａの設定
３２６ 乗算予測方法の終了
４００ 換算予測方法の開始
４０２ 広域変数
４０４ Ｓｉの初期化
４０６ 換算できるかどうかの決定
４０８ ｂの設定
４１０ ｎの増加
４１２ Ｓｉの増加
４１４ 桁送りされた中間結果の多項式の次数の調査
４１６ 折り返し線
４１８ ｂの設定
４２０ ｎの設定
４２２ ｓ_Ｎの計算
４２４ ｎの調査
４２６ ｃｕｒｋの設定
４２８ ｃｕｒｋの設定
４３０ ｂ、ｓ_Ｎの出力
４３２ 換算予測方法の終了
５００ ３ビット計数器
５１０ 全加算器
５２０ スイッチ
５３０ 制御
７００ ３演算数算術演算装置
７１０ Ｚ／ＮＺ制御装置
７２０ ＧＦ（２^ｎ）制御装置
７３０ モード選択
９００ ＺＤＮ方法の開始
９１０ ＺＤＮアルゴリズムのための乗算予測方法
９２０ Ｚの左への桁送り
９３０ ＺＤＮアルゴリズムのための換算予測方法
９４０ 係数の左または右への桁送り
９５０ ＺＤＮアルゴリズムのための３演算数加算
９６０ ＺＤＮアルゴリズムの終了

Claims (13)

1. 係数（Ｎ）を使用して、被乗数（Ｃ）に乗数（Ｍ）を係数乗算するための方法において、
   上記被乗数（Ｃ）、上記乗数（Ｍ）、および、上記係数（Ｎ）は、変数（ｘ）の多項式であり、
   （ａ）乗算桁送り値（ｓ_Ｚ）を得るために、乗算予測方法を実施（２１０）し、上記乗数多項式に存在していない乗数の累乗で、上記乗算桁送り値ｓ_Ｚが増加される工程と、
   （ｂ）桁送りされた中間結果の多項式（Ｚ´）を得るために、上記乗算桁送り値（ｓ_Ｚ）により累乗されている上記変数（ｘ）に、中間結果の多項式（Ｚ）を乗算する（２１４）工程と、
   （ｃ）換算桁送り値（ｓ_Ｎ）を得るために換算予測方法（２１２）を実施し、上記換算桁送り値（ｓ_Ｎ）は、上記桁送りされた中間結果の多項式（Ｚ）の次数と上記係数多項式（Ｎ）の次数との差に等しい工程と、
   （ｄ）桁送りされた係数多項式（Ｎ´）を得るために、上記換算桁送り値（ｓ_Ｎ）により累乗されている上記変数（ｘ）に、上記係数多項式（Ｎ）を乗算する（２１６）工程と、
   （ｅ）更新された中間結果の多項式（Ｚ）を得るために、上記桁送りされた中間結果の多項式（Ｚ´）と上記被乗数（Ｃ）とを加算し（２１８）、上記桁送りされた係数多項式（Ｎ´）を減算する工程と、
   （ｆ）上記乗数（Ｍ）の全ての累乗が処理されるまで、工程（ａ）〜（ｅ）を繰り返す（２２６）工程とを含み、
   上記工程（ａ）〜（ｅ）を繰り返す場合に、
   上記工程（ｄ）において、上記中間結果の多項式（Ｚ）として、先の上記工程（ｅ）の上記更新された中間結果の多項式（Ｚ）を使用し、
   上記工程（ｃ）において、係数多項式（Ｎ）として、先の上記工程（ｄ）の上記桁送りされた係数多項式を使用する方法。
2. 上記乗算桁送り値（ｓ_Ｚ）に等しい桁数で、上記中間結果の多項式（Ｚ）を桁送りすることで、工程（ｄ）における上記乗算（２１０）を実施し、
   上記換算桁送り値（ｓ_Ｎ）に等しい桁数で、上記係数多項式（Ｍ）を桁送りすることにより、上記工程（ｄ）における乗算（２１６）を実施する、請求項１に記載の方法。
3. 上記多項式の係数は、「０」または「１」の値のみを有することができ、
   上記工程（ｅ）における加算および減算（２１８）は、上記中間結果の多項式（Ｚ´）、上記被乗数（Ｃ）、および、上記桁送りされる係数多項式（Ｎ´）のビット毎のＸＯＲ結合により実施される、請求項１または２に記載の方法。
4. 上記換算予測方法（２１２）において換算桁送り値（ｓ_Ｎ）を得るための工程は、
   上記係数多項式（Ｎ）の次数と、上記補助桁送り値（ｓ_ｉ）により累乗されている変数が乗算されている、上記先の工程（ｅ）の上記更新された中間結果の多項式（Ｚ）との次数とが等しくなるように、補助桁送り値（ｓ_ｉ）を決定する（４１４）工程と、
   上記換算桁送り値（ｓ_Ｎ）を得るために、上記乗算桁送り値（ｓ_Ｚ）と、上記補助桁送り値（ｓ_ｉ）との差を形成する（４２２）工程とを含む、請求項１〜３のいずれかに記載の方法。
5. 上記乗算予測方法を実施する上記（２１０）工程と、上記補助桁送り値（ｓ_ｉ）を決定する上記（４１４）工程とを相互に並行して実施する、請求項４に記載の方法。
6. 上記乗算桁送り値（ｓ_Ｚ）は、最大乗算桁送り値（ｋ）に制限されており、
   上記乗算桁送り方法を実施する上記（２１０）工程は、
   上記乗算桁送り値が、上記最大乗算桁送り値（ｋ）に等しい場合、上記乗算桁送り値（ｓ_Ｚ）を、上記最大桁送り値（ｋ）に等しく設定し、所定の値を有する乗算予測パラメータ（ａ）を生成する（３０６，３２４）工程を含み、
   上記加算工程は、
   上記乗算予測パラメータ（ａ）が、所定の値を有している場合、
   上記所定の中間結果の多項式（Ｚ´）および上記桁送りされた係数多項式（Ｎ´）のみを加算する工程を含む、請求項１〜５のいずれかに記載の方法。
7. 係数（Ｎ）を使用して、被乗数（Ｃ）に乗数（Ｍ）を係数乗算するための装置において、
   上記被乗数（Ｃ）、上記乗数（Ｍ）、および、上記係数（Ｎ）は、変数（ｘ）の多項式であり、
   （ａ）乗算桁送り値（ｓ_Ｚ）を得るために、乗算予測方法を実施（２１０）し、上記乗数多項式に存在していない乗数の累乗で、上記乗算桁送り値ｓ_Ｚを増加させる装置と、
   （ｂ）桁送りされた中間結果の多項式（Ｚ´）を得るために、上記乗算桁送り値（ｓ_Ｚ）により累乗されている上記変数（ｘ）に、中間結果の多項式（Ｚ）を乗算する（２１４）装置と、
   （ｃ）換算桁送り値（ｓ_Ｎ）を得るために換算予測方法（２１２）を実施し、上記換算桁送り値（ｓ_Ｎ）は、上記桁送りされた中間結果の多項式（Ｚ）の次数と上記係数多項式（Ｎ）の次数との差に等しい装置と、
   （ｄ）桁送りされた係数多項式（Ｎ´）を得るために、上記換算桁送り値（ｓ_Ｎ）により累乗されている上記変数（ｘ）に、上記係数多項式（Ｎ）を乗算する（２１６）装置と、
   （ｅ）更新された中間結果の多項式（Ｚ）を得るために、上記桁送りされた中間結果の多項式（Ｚ´）と上記被乗数（Ｃ）とを加算し（２１８）、上記桁送りされた係数多項式（Ｎ´）を減算する装置と、
   （ｆ）上記乗数（Ｍ）の全ての累乗が処理されるまで、上記装置（ａ）〜（ｅ）を繰り返し駆動する（２２６）装置とを含み、
   上記装置（ａ）〜（ｅ）を繰り返し駆動する場合に、
   上記中間結果の多項式（Ｚ）として、上記加算する（２１８）ための装置を先行して駆動することにより生じる更新された中間結果の多項式（Ｚ）を使用するために、桁送りされた中間結果の多項式を得るための乗算をする（２１４）装置が配置されており、
   桁送りされた係数多項式を得るために、上記の繰り返し駆動の際に、係数多項式（Ｎ）として、乗算をする（２１６）ための装置を先行して駆動することにより生じる桁送りされた係数多項式を使用するために、換算予測方法（２１２）を実施するための装置とが配置されている装置。
8. 桁送りされた中間結果の多項式（Ｚ´）を得るために乗算をするための上記装置（２１４）、および、桁送りされた係数多項式（Ｎ´）を得るために乗算をするための上記装置（２１６）は、上記乗算桁送り値（ｓ_Ｚ）または上記換算桁送り値（ｓ_Ｎ）に関係なく、相当する桁数だけ記録内容を桁送りするために制御可能な桁送り記録装置として実施されている、請求項７に記載の装置。
9. 加算および減算するための上記装置（２１８）は、上記中間結果の多項式（Ｚ´）、上記被乗数（Ｃ）、および、上記桁送りされた係数多項式（Ｎ´）のビット毎のＸＯＲ結合として実施されている、請求項７または８に記載の装置。
10. 加算および減算するための上記装置（２１８）は、
    第１入力部配線に、上記中間結果の多項式（Ｚ）のビットを印加でき、第２入力部配線に、上記被乗数（Ｃ）のビットを印加でき、第３入力部配線に、上記桁送りされた係数多項式（Ｎ´）のビットを印加できる、３つの入力部配線および２つの出力部配線を有する計数器（５００）と、
    上記計数器（５００）の低い値の出力部が、全加算器（５１０）の高い値の入力部配線に接続されている、３つの入力部および１つの出力部を有する全加算器（５１０）と、
    上記計数器（５００）の高い値の出力部配線と、全加算器（５１０）の中間入力部との間に、高い値のビットのために接続されているスイッチ（５２０）と、
    多項式を処理できる場合、スイッチ（５２０）を開けるための、制御装置（５３０）とを有する、請求項７または８に記載の装置。
11. 係数多項式を使用して、被乗数多項式に乗数多項式を乗算するための算術演算装置において、
    上記被乗数多項式、上記乗数多項式、および、上記係数多項式は、変数の多項式であるか、あるいは、選択的に、係数整数を使用して、被乗数整数に乗数整数を乗算するために、
    （ａ）乗算桁送り値（ｓ_Ｚ）を得るために、乗算予測方法を実施（２１０）し、上記乗数の累乗が上記乗数多項式に存在していない場合、上記乗算桁送り値（ｓ_Ｚ）を増加させる装置と、
    （ｂ）桁送りされた中間結果の多項式を得るために、上記乗算桁送り値（ｓ_Ｚ）により累乗されている上記変数に、中間結果の多項式を乗算する（２１４）装置と、
    （ｃ）換算桁送り値（ｓ_Ｎ）を得るために換算予測方法（２１２）を実施し、上記換算桁送り値（ｓ_Ｎ）は、上記桁送りされた中間結果の多項式の次数と上記係数多項式の次数との差に等しい装置と、
    （ｄ）桁送りされた係数多項式を得るために、上記換算桁送り値（ｓ_Ｎ）により累乗されている上記変数（ｘ）に、上記係数多項式を乗算する（２１６）装置と、
    （ｅ）整数の中間結果、および、桁送りされた整数係数を得るために、整数演算数用の乗算予測方法、および、換算予測方法を実施するための装置（７１０）と、
    （ｆ）上記整数演算数または上記多項式の中間結果、上記桁送りされた係数多項式、および、上記多項式被乗数を組み合わせるために、桁上げ遮断装置（７３０）を有する３演算数加算器（７００）と、
    （ｇ）多項式演算数を処理する場合、桁上げは行われず、整数演算数を処理する場合、桁上げが行われるよう、上記桁上げ遮断装置を制御するための制御装置（７３０）とを有する装置。
12. 桁上げ遮断装置を有する上記３演算数加算器は、
    第１入力部配線に、上記中間結果多項式のビットを印加でき、第２入力部配線に、上記被乗数（Ｃ）のビットを印加でき、第３入力部配線に、上記桁送りされた係数多項式のビットを印加できる、３つの入力部配線および２つの出力部配線を有する計数器（５００）と、
    上記計数器（５００）の低い値の出力部が上記全加算器（５１０）の高い値の入力部配線に接続されている、３つの入力部および１つの出力部を有する全加算器（５１０）と、
    上記計数器（５００）の高い値の出力部配線と、全加算器（５１０）の中間入力部との間に、高い値のビットのために接続されているスイッチ（５２０）と、
    多項式を処理できる場合、上記スイッチ（５２０）を開くための、制御装置（５３０）とを有する、請求項１１に記載の算術演算装置。
13. 存在する３演算数加算器の数が、上記係数整数または上記多項式整数の桁数よりも大きいかあるいは同じである、複数の３演算数加算を備える、請求項１２に記載の算術演算装置。

Images