JP4875700B2 - ランダム化されたモジュラー多項式のリダクション方法およびそのためのハードウェア - Google Patents

Description

この発明は、特に暗号アプリケーションにおいて用いられる、算術処理および計算システム、およびコンピュータで実行される方法に関する。この発明は、特定的には、有限フィールドＧＦ（２ⁿ）において多項式のモジュラーリダクション（modular reduction）を含む剰余計算に関し、特にバレットのリダクション方法（Barrett reduction method）から導かれる計算に関する。

多くの暗号アルゴリズムは、大きな整数の掛算（または累乗法）と、暗号キーに関連する特定の法に対して合同である剰余の値への積のリダクションとを利用する。ＡＥＳ／Rijndaelブロック暗号、並びに離散的対数および楕円曲線に基づいたものも含む、いくつかの暗号アルゴリズムは、バイナリフィールドＧＦ（２ⁿ）のような有限フィールドにおいて、多項式に対して算術演算を行なう。この算術演算には、このような多項式に対する掛算（または累乗法）およびモジュラーリダクション処理が含まれる。暗号システムによって行なわれる数学的計算は、べき乗解析やタイミング攻撃の影響を受けやすい場合がある。したがって、キーに関する情報が得られないように計算が保護されることが重要である。

同時に、これらの計算は速く、正確であることが重要である。大きい整数に対して行なわれるものであろうと、有限フィールドにおける多項式に対して行なわれるものであろうと、掛算およびリダクションは、通常、暗号アルゴリズムの計算上最も集中的な部分である。前計算およびテーブルルックアップを含む修正を伴って、クイスクォーター（Quisquater）の方法、バレットの方法、およびモンゴメリ（Montgomery）の方法として知られる技術を含む、いくつかの注目すべき計算技術が、効率的なモジュラーリダクションのために開発されている。これらの周知の技術は、先行技術において記載され比較される。たとえば、以下の文献を参照のこと。（１）ボッセラース等（Bosselaers et al.）、「３つのモジュラーリダクション関数の比較（Comparison of three modular reduction functions）」、アドバンシズ・イン・クリプトロジー／クリプト′９３（Advances in Cryptology/Crypto ′93）、ＬＮＣＳ７７３、シュプリンガー・フェアラーク（Springer-Verlag）、１９９４、ｐｐ．１７５−１８６。（２）ジャン・フランソワ・デム（Jean Francois Dhem）、「ＲＩＳＣに基づいたスマートカードのための効率的な公開鍵暗号ライブラリの設計（Design of an efficient public-key cryptographic library for RISC-based smart cards）」博士論文（doctoral dissertation）、ルヴァンカトリック大学（Universite catholique de Louvain）、ルヴァン・ラ・ヌーヴ（Louvain-la-Neuve）、ベルギー（Belgium）、５月、１９９８。（３）Ｃ．Ｈ．リム（C. H. Lim）等、「前計算を伴う高速モジュラーリダクション」、プレプリント（preprint）、１９９９（サイトシアー・サイエンティフィック・リテラチャー・デジタル・ライブラリ（CiteSeer Scientific Literature Digital Library）から入手可能、citeseer.nj.nec.com/109504.html）。（４）ホルマン等（Hollmann et al.）、「タイミング攻撃を阻止するために、標準化されたモジュラー累算を計算することを通して、復号機構を実行するための方法および装置（Method and Device for Executing a Decrypting Mechanism through Calculating a Standardized Modular Exponentiation for Thwarting Timing Attacks）」、米国特許６，３６６，６７３ Ｂ１、４月２日、２００２年（１９９８年９月１５日出願の特許出願に基づく）。

この発明の目的は、特に多項式に適用した際には、速く正確な結果を提供しながらも、
暗号解析攻撃に対してより安全である、バレットのリダクション方法および対応する計算装置の改良を提供することである。

この発明の別の目的は、多項式のモジュラーリダクションにおいて用いられる商の概算をスピードアップする、上述した改良方法および装置を提供することである。

発明の概要
これらの目的は、多項式の法の前計算された記数法の（scaled）逆数を乗数として用いて、リダクション計算のために用いられる多項式の商が（少なくとも正しい多項式の次数まで）概算される、バイナリの有限フィールドＧＦ（２ⁿ）におけるコンピュータで実行される多項式のモジュラーリダクションのための方法によって、達成される。このリダクションの結果得られる多項式の残余は、次数ｎの特定の既約多項式の法に対する対応する中間の積に常に合同であるが、典型的には（多項式の次数において）最小の剰余の値よりも大きく、各処理実行ごとにランダムな態様で異なる。概算エラーが故意にランダム化されるので、この方法は暗号解析に対してより安全である。その上、中間結果が数学的に等価（真の結果に合同）であり、最終結果は、ランダム化なしで最後の正確なリダクションを処理することにより得てもよい。これにより、暗号処理の変換性に必要とされる正確さを達成する。

この発明の方法のステップを実行するのに用いるハードウェアは、ランダムなエラーを商の概算へ注入するよう、乱数発生器を含む。メモリへのアクセスを伴う計算ユニットは、マルチワードの多項式の掛算およびモジュラーリダクションの、ワード幅の掛算−累算ステップを行なうよう、ファームウェアを実行する演算シーケンサの制御下で動作する。計算ユニットは、有限フィールドの多項式演算専用の掛算−累算ハードウェアを含んでもよく、または自然数もしくは多項式演算を行なうよう選択可能であってもよい。

発明の詳細な説明
図１を参照すると、計算ハードウェアは、メモリ（ＲＡＭ）１２およびワーキングレジスタ１４から読出される多項式のオペランドに対してワード幅の有限フィールド掛算および掛算−累算ステップを行ない得る計算ユニット１０を含む。レジスタ１４は、通常の整数処理において桁に数を入れることに関与するのと同じハードウェアレジスタであってもよい。演算シーケンサ１６は、既約多項式の基底を用いてマルチワードの有限フィールドの多項式掛算（または累算）およびモジュラーリダクションを行なう処理の組のためのファームウェアまたはソフトウェアの命令に従って計算ユニット１０を制御する論理回路を含む。演算シーケンサ１６によってアクセス可能なレジスタ１８に格納される演算パラメータは、演算シーケンサ１６がＲＡＭ１２の中のオペランドを特定することを可能とするポインタと、オペランドの長さ（ワードの数）に関する情報と、中間結果の宛先アドレスとに存在する。

ここまで述べたように、この装置は、マルチワードの多項式算術演算に適合する他の入手可能なハードウェアに実質的に同様である。バイナリの有限フィールドＧＦ（２ⁿ）において行なわれる多項式演算は、桁上げを無視する点および足算と引算が同じ値となる点において、自然数演算と異なる。計算ユニットは、有限フィールド多項式処理専用の掛算−累算ハードウェアを含んでもよく、または自然数／多項式演算を行なうよう選択され得る２つの目的を兼ねた自然数／多項式演算ハードウェアであってもよい。後述するリダクションステップの詳細以外は、ファームウェアまたはソフトウェアの命令も、ワード幅のセグメントにおいて、効率的なマルチワードの多項式掛算または累算を実行する先行技術
のプログラムに似ている。

このタイプの先行技術のハードウェアと異なり、図１に示すハードウェアは、たとえばどのような公知の疑似乱数発生器回路でもあり得る、乱数発生器２０も含む。この乱数発生器は計算を行ない、乱数を出力する。その乱数のビットは、この方法で利用されるランダムな多項式のバイナリ係数として解釈される。ここで、以下に記載するように、この乱数発生器２０は、この発明の方法を実行するプログラム命令に従った演算シーケンサ１６が指示するように、ランダム化されたエラー量を商の概算へ注入するよう、計算ユニット１０によってアクセスされる。

図２を参照して、この発明の方法は、より速い商の概算と暗号解析攻撃に対する抵抗とを提供するという、バレットのモジュラーリダクション技術の改良であり、そのモジュラーリダクション技術をバイナリの有限フィールドＧＦ（２ⁿ）における多項式に適用する。この方法は、図１に示すハードウェアによって実行される。

多項式を含むモジュラー演算は、整数を含むモジュラー演算と、いくつかの点において似ているが、モジュラー演算をバイナリの有限フィールドＧＦ（２ⁿ）上の多項式へ拡張することは、基本的な処理への修正を必要とする。まず、多項式をフィールド上に導入する。フィールドＦの要素の倍数（ａ_m-1，…ａ₁，ａ₀）のいずれかに対して、次数（ｍ−１）のｘについての多項式を関連付け得る、すなわちａ_m-1ｘ^m-1＋…ａ₁ｘ¹＋ａ₀ｘ⁰。どんなバイナリフィールドの場合でも、フィールドの要素は｛０，１｝であり、よって、多項式の係数ａ_iは、同様に０または１である。この概念は、性質としてバイナリであるコンピュータハードウェアに特によく適合する、なぜならば、各ビットは、有限フィールドの要素として解釈され得るためである。たとえば、各バイナリバイト値［ａ₇ａ₆ａ₅ａ₄ａ₃ａ₂ａ₁ａ₀］を、次数７（または７より小さい）のＧＦ（２ⁿ）上の対応する多項式と関連付け得る、すなわちａ₇ｘ⁷＋ａ₆ｘ⁶＋ａ₅ｘ⁵＋ａ₄ｘ⁴＋ａ₃ｘ³＋ａ₂ｘ²＋ａ₁ｘ＋ａ₀。よって、たとえば、バイト値［０１１０００１１］は、バイナリ多項式ｘ⁶＋ｘ⁵＋ｘ＋１として解釈される。バイナリ有限フィールドＧＦ（２ⁿ）上で、多項式がそのフィールドに属するよう、多項式の次数（ｍ−１）はｎよりも小さいという条件下では、マルチバイトシーケンスが長いほど、高い次数の多項式であると同様に解釈されてもよい。（なお、多項式の相対的なサイズを比較する際には、比較は次数ごとに行なわれ、ｘについて最も大きい次数の多項式の係数から始める。）フィールドにおける多項式の足算および引算は、各次数ごとに別個に、係数を足算または引算する通常の態様で行なう。

しかしながら、どんなバイナリフィールドでも、要素は｛０，１｝であり、よってフィールド要素の足算および引算は、２を法として行なう（０±０＝０、０±１＝１±０＝１、１±１＝０）。なお、この場合、引算は足算と同じである。コンピュータハードウェアにおいて、法を２とする足算／引算は、論理ＸＯＲ演算を用いて、ビットのアレイに対して行なわれる。たとえば、（ｘ⁶＋ｘ⁴＋ｘ²＋ｘ１）＋（ｘ⁷＋ｘ＋１）＝（ｘ⁷＋ｘ⁶＋ｘ⁴＋ｘ²）、またはバイナリ表記では

。多項式の掛算は通常（有限フィールドに対して）以下の式で規定される。

しかしながら、有限フィールドでは、この定義は、積もそのフィールドに属するよう修正されなければならない。特に、通常の多項式掛算の後には、次数ｎの法ｍ（ｘ）によるモジュラーリダクションが行なわれる（ＧＦ（２ⁿ）でのように、ｎは有限フィールドの次元である）。法ｍ（ｘ）は、好ましくは、既約多項式（素数の多項式のアナログ、すなわち同じフィールド上で非自明な多項式へと因数分解し得ないもの）となるよう選択される。たとえば、ＡＥＳ／Rijndael共通鍵ブロック暗号においては、特定の既約多項式ｍ（ｘ）＝ｘ⁸＋ｘ⁴＋ｘ³＋ｘ＋１を、多項式掛算を行なうときのモジュラーリダクションの選択された基底として用いて、バイナリ有限フィールドＧＦ（２⁸）におけるバイト（次数７以下の多項式）に対して処理を行なう。ＡＥＳ用に指定された特定のｍ（ｘ）を用いたバイナリ有限フィールドにおける多項式掛算の例として、（ｘ⁶＋ｘ⁴＋ｘ²＋ｘ＋１）・（ｘ⁷＋ｘ＋１）＝（ｘ¹³＋ｘ¹¹＋ｘ⁹＋ｘ⁸＋ｘ⁶＋ｘ⁵＋ｘ⁴＋ｘ³＋１）があり、これは、リダクション後は、（ｘ⁷＋ｘ⁶＋１）を与える。

Ｆ［ｘ］を、すべての係数がフィールドＦの要素である多項式の組とする。法ｍ（ｘ）がＦ［ｘ］において次数ｄの多項式であるならば、ｐ（ｘ），ｒ（ｘ）∈Ｆ［ｘ］の多項式ｐ（ｘ）、ｒ（ｘ）について、ｍ（ｘ）で多項式ｐ（ｘ）−ｒ（ｘ）を割るときかつそのときに限り、ｐ（ｘ）はｍ（ｘ）を法としてｒ（ｘ）と合同であるという（ｐ（ｘ）≡ｒ（ｘ）（ｍｏｄ ｍ（ｘ））と書く）。言い換えれば、ｐ（ｘ）−ｒ（ｘ）はｍ（ｘ）の多項式の倍数である、すなわち、ある多項式ｑ（ｘ）∈Ｆ［ｘ］について、ｐ（ｘ）−ｒ（ｘ）＝ｑ（ｘ）・ｍ（ｘ）が成り立つ。

同等に、ｐ（ｘ）とｒ（ｘ）は、ｍ（ｘ）での割算の際には、同じ残余を持つ。Ｆ［ｘ］における多項式ａ（ｘ）およびｂ（ｘ）の通常の積となり得る多項式ｐ（ｘ）、すなわちｐ（ｘ）＝ａ（ｘ）・ｂ（ｘ）のモジュラーリダクションは、残余または剰余ｒ（ｘ）が、ｍ（ｘ）よりも小さい次数の多項式となるように、すなわちｄｅｇ（ｒ（ｘ））＜ｄとなるように、多項式の商ｑ（ｘ）を求めるステップを含む。この多項式の剰余ｒ（ｘ）は、ｐ（ｘ）と合同であり、最終的に欲しい多項式の値である。バイナリ有限フィールドＧＦ（２ⁿ）において、ｍ（ｘ）は次数ｎの既約多項式となり、求められる剰余多項式ｒ（ｘ）は次数がｎよりも小さいものとなる。しかし、ｐ（ｘ）においてはどんな次数でもあり得るため、ｑ（ｘ）においてもどんな次数でもあり得る。そして、たとえば、ｐ（ｘ）が積であるときのように、少なくとも、リダクションさせるべき多項式ｐ（ｘ）は、しばしばｍよりも大きい次数の多項式である。どんな場合でも、いかなるモジュラーリダクション方法における基本的な問題は、特に、大きい次数の多項式ｐ（ｘ）およびｍ（ｘ）に対する商を効率的に得ることにある。暗号アプリケーションの関係において、さらなる問題は、計算ハードウェアにおいて、べき乗解析攻撃から安全な方法で、リダクション処理を行なうことにある。

元々、整数リダクション処理のために考え出されたバレットの方法は、商を概算するよう、法の逆数Ｕの記数法の概算を前計算し記憶するステップと、長い割算を掛算およびワードまたはビットシフト（ｘで割る）に置き換えるステップとを含む。パラメータの適切な選択により、商の概算におけるエラーは最大でも２である。この発明は、バレットの方法をバイナリ有限フィールドにおける多項式のモジュラーリダクションに適合させ、さらにバレットの方法を、商のより速い概算をもって、かつ残余を計算する前に商にランダムなエラーを意図的に注入することにより、改良する。結果として生じるランダム化された残余は、（多項式の次数において）わずかに剰余値よりも大きくなるが、剰余値と合同である。

次数において、ｋを多項式の法ｍ（ｘ）のサイズとし、

ｐ（ｘ）を、次数ｌまでリダクションさせるべき多項式とする。

まず、法ｍ（ｘ）の記数法の逆数を示す定数の多項式ｕ（ｘ）を前計算し記憶する（図２のステップ３０）ことから始める。

ｕ（ｘ）＝ｘ^2k+1／ｍ（ｘ）
それから、この記憶された値は、この後、この特定の法ｍ（ｘ）についてのすべての多項式リダクション処理において用いられる。ｕ（ｘ）は、常に、ｘの単なる累乗でないあらゆる法ｍ（ｘ）のための次数ｋの多項式である。

ｐ（ｘ）の法のリダクションを行なうために、この記憶された値ｕ（ｘ）を用いて、多項式の商ｑ（ｘ）を以下のように概算する(ステップ３２）。

ｑ（ｘ）＝（（ｐ（ｘ）／ｘ^k-1）・ｕ（ｘ））／ｘ^k+2
高い次数（マルチワード）の法ｍ（ｘ）については、処理は、ビットシフトではなくワードシフトで行ない得る。ワードサイズをｗとすると、ｕ（ｘ）＝ｘ^2k+w／ｍ（ｘ）と定義し、商ｑ（ｘ）＝（（ｐ（ｘ）／ｘ^k-w）・ｕ（ｘ））／ｘ^k+2wを概算し得る。この場合、多項式ｐ（ｘ）は、ｄｅｇ（ｐ（ｘ））≦２・ｋ＋ｗのように、わずかにより大きい次数を有し得る。これにより、計算ハードウェアにおいて多項式量の扱いが簡素化される。この計算は、（リダクションのない）バイナリ有限フィールドの多項式の掛算と、多項式の次数のシフトとを必要とするのみである。

この段階（ステップ３６）で、ランダムな多項式エラーＥ（ｘ）が、計算された多項式
の商に入れられ、これによりランダム化された商ｑ′（ｘ）＝ｑ（ｘ）＋Ｅ（ｘ）を得る。このランダムな多項式エラーＥ（ｘ）は、発生されたバイナリ値がすでに上述した態様で多項式として解釈される場合は、公知のどのような乱数発生器または疑似乱数発生器（ハードウェアまたはソフトウェア）によって発生されてもよい(ステップ３４）。唯一の制約は、エラーの多項式の次数が、０≦ｄｅｇ（Ｅ（ｘ））＜ｗ／２のような特定の範囲内に入らなければならないことである。

高い次数（マルチワード）の法ｍ（ｘ）については、エラーは数ビット、たとえばワードの半分未満、すなわちｄｅｇ（Ｅ（ｘ））＜Ｗ／２、に制限されるべきである。これにより、商の概算自体から生じる任意のエラーに加えて、乱数発生器によって与えられた起こり得るエラーを、特定の数のビット、たとえばワードの半分へと制限する。

次に、（ｍ（ｘ）を法として）剰余ｒ（ｘ）と合同となる残余ｒ′（ｘ）を計算する（ステップ３８）。

ｒ′（ｘ）＝ｐ（ｘ）＋ｑ′（ｘ）・ｍ（ｘ）
ランダムな多項式のエラーＥが、多項式の商ｑ（ｘ）に導入されるので、計算された残余ｒ′（ｘ）は、次数において、法ｍ（ｘ）よりわずかに大きくなる。

残余ｒ′（ｘ）は、さらなる計算において用い得る。その計算の結果は、必要ならばもう一度リダクションさせてもよい。（エラーは有界のままである。）
代替的に、特定のアプリケーションの必要に応じて、剰余ｒ（ｘ）は、ｍ（ｘ）より小さい多項式の値を得るよう、通常のＧＦ（２ⁿ）多項式リダクションを法ｍ（ｘ）を用いて適用することにより、残余ｒ′（ｘ）から計算され得る。

モジュラーリダクションをランダム化することにより、法を判断するのに、べき乗使用の一貫性に頼っているさまざまな暗号解析攻撃に対する安全性を提供する。ここで、合同である中間の残余ｒ′（ｘ）を発生させつつも、ｍ（ｘ）を法とするｐ（ｘ）のバイナリフィールド多項式リダクションは、ある処理実行から次の処理実行へ、ランダムに変化する。最終の剰余値ｒ（ｘ）を生成する最後のバイナリフィールド多項式リダクションのシーケンスも、ある処理実行から次の処理実行へ、ランダムに変化する。なぜならばリダクションは異なった残余ｒ′（ｘ）に対して行なわれるからである。このようにリダクションされる多項式ｐ（ｘ）は、掛算、平方、累乗、足算などを含む、さまざまな異なった算術演算から得られ得る。用いられる法ｍ（ｘ）も、同様にさまざまな方法で導き得、暗号法においては、大抵は鍵から導き得る。この発明のランダム化されたモジュラーリダクション方法は、Rijnael／ＡＥＳ共通鍵ブロック暗号、および離散対数に基づいた公開鍵暗号システムを含む、このようなバイナリフィールドＧＦ（２ⁿ）多項式リダクションに頼る多くの暗号アルゴリズムにおいて、有用である。

この発明のモジュラーリダクション方法を実行するのに用いられる、この発明に従った（乱数発生器ユニットを含む）計算ハードウェアの概略平面図である。 このモジュラーリダクション方法における全体のステップを示すフロー図である。

Claims (11)

1. 暗号学的に安全で、コンピュータハードウェアで実施される、バイナリ有限フィールドＧＦ（２ⁿ）におけるモジュラー多項式リダクション方法であって、
   多項式の法ｍ（ｘ）のビットスケールの逆数を示す多項式定数ｕ（ｘ）を前計算し、メモリに記憶するステップと、
   ｍ（ｘ）を法としてリダクションさせる多項式ｐ（ｘ）について、おおよその多項式の商ｑを概算するステップとを含み、前記概算は、ＧＦ（２ⁿ）上での前記定数ｕ（ｘ）およびビットシフトによる多項式掛算によって、計算ユニットにおいてｐ（ｘ）に対して実行され、前記方法はさらに、
   ランダム化された多項式の商ｑ′（ｘ）＝ｑ（ｘ）＋Ｅ（ｘ）を得るよう、乱数発生器において、ランダムな多項式エラー値Ｅ（ｘ）を発生させ、前記多項式エラー値を前記おおよその多項式の商へ適用するステップと、
   前記計算ユニットにおいて、多項式の残余ｒ′（ｘ）＝ｐ（ｘ）＋ｑ′（ｘ）・ｍ（ｘ）を計算するステップとを含み、前記残余ｒ′（ｘ）は、前記ｍ（ｘ）よりも高い次数のものであるが、ｍ（ｘ）を法としてｐ（ｘ）に合同であり、ｐ（ｘ）の次数は、２ｋ＋１以下である、モジュラー多項式リダクション方法。
2. 前記多項式定数ｕ（ｘ）の前計算は、方程式ｕ（ｘ）＝Ｘ^2k+w／ｍ（ｘ）に従って行なわれる、請求項１に記載の方法。
3. 商ｑ（ｘ）の概算は、計算ユニットによって、方程式ｑ（ｘ）＝（（ｐ（ｘ）／ｘ^k-1）・ｕ（ｘ））ｘ^k+2に従って行なわれる、請求項２に記載の方法。
4. 前記ビットシフトは、ワードサイズシフトであり、多項式定数はｕ（ｘ）＝Ｘ^2k+w／ｍ（ｘ）として前計算され、商はｑ（ｘ）＝（（ｐ（ｘ）／ｘ^k-w）・ｕ（ｘ））／ｘ^k+2wとして概算され、ｗはビットを単位としたワードサイズであり、ｐ（ｘ）の次数は２ｋ＋ｗ以下である、請求項１に記載の方法。
5. 乱数発生器には、２分の１ワードという特定のエラー制限があり、よって０≦ｄｅｇ（Ｅ（ｘ））＜ｗ／２である、請求項４に記載の方法。
6. ｐ（ｘ）のモジュラーリダクションは、コンピュータハードウェアによって実行される暗号プログラムの一部である、請求項１に記載の方法。
7. 暗号学的に安全で、バイナリ有限フィールドＧＦ（２ⁿ）上でのモジュラー多項式リダクション方法を実行する計算ハードウェアであって、ハードウェアは、
   メモリから読出された多項式のオペランドと、ワーキングレジスタの組からの多項式係数の中間結果とに対してワード幅の有限フィールド掛算および累算ステップを行なうよう適合される計算ユニットと、
   ランダムな多項式エラー値Ｅ（ｘ）を発生する乱数発生器と、
   バイナリ有限フィールドＧＦ（２ⁿ）上で、法ｍ（ｘ）に対して、数ｐ（ｘ）の多項式のモジュラーリダクションを行なうよう、プログラムの命令に従って、計算ユニットと乱数発生器とを制御するための論理回路を含む演算シーケンサとを含み、前記多項式モジュラーリダクションは、少なくとも、法のビットスケールの逆数を示す前もって記憶された多項式定数ｕ（ｘ）からの多項式の商ｑ（ｘ）の概算と、ランダム化された多項式の商ｑ′（ｘ）＝ｑ（ｘ）＋Ｅ（ｘ）を得るよう前記おおよその多項式の商を前記ランダムな多項式エラーＥ（ｘ）でランダム化することと、多項式残余値ｒ′（ｘ）＝ｐ（ｘ）＋ｑ′（ｘ）・ｍ（ｘ）の計算とを含む、計算ハードウェア。
8. さらに、前記演算シーケンサによってアクセス可能な演算パラメータレジスタを含み、前記レジスタは、（ａ）前記メモリまたはワーキングレジスタ内の多項式のオペランドのワードサイズの係数を特定するポインタ、（ｂ）多項式のオペランドのワード長についての情報、および（ｃ）処理ステップの中間結果のための宛先アドレス情報のうちのいずれか１つまたはそれ以上を含む、請求項７に記載の計算ハードウェア。
9. 前記メモリに前もって記憶された多項式係数ｕ（ｘ）は、方程式ｕ（ｘ）＝Ｘ^2k+w／ｍ（ｘ）に従って前計算から得られ、ｗは、ビットを単位とした計算ユニットのワードサイズである、請求項７に記載の計算ハードウェア。
10. プログラム命令を実行する前記演算シーケンサの制御の下、前記計算ユニットによって行なわれる前記おおよその多項式の商ｑの概算は、方程式ｑ′（ｘ）＝（（ｐ（ｘ）・ｘ^k-w）・ｕ（ｘ））／ｘ^k+2wに従ってなされる、請求項９に記載の計算ハードウェア。
11. 乱数発生器には、２分の１ワードという特定のエラー制限があり、よって、０≦ｄｅｇ（Ｅ（ｘ）＜ｗ／２である、請求項１０に記載の方法。

Images