« 米国特許4542293(質量分析)独立クレーム | トップページ | 米国特許6286022(有限体の基底変換)発明の背景 »

米国特許6286022(有限体の基底変換)要約


本件は、楕円曲線暗号等で用いられる有限体の基底変換計算の効率化に関する。

米国特許 No.6,286,022 (Kaliski, Jr. et al. September 4, 2001) の要約の訳文。

Efficient finite field basis conversion involving a dual basis

Abstract
The invention provides apparatus and methods for use in basis conversion involving a dual basis, such as a dual of a polynomial basis or dual of a normal basis. The invention in an illustrative embodiment includes basis generators for generating elements of a dual of a polynomial or a normal basis of a finite field GF(q.sup.m), where q is a prime number or power of a prime number and m is an integer greater than or equal to 2. The basis generators can be used in "import" basis conversion, such as converting a representation in an external basis to a representation in an internal dual of a polynomial basis or dual of a normal basis, as part of a generate-accumulate algorithm, or in "export" basis conversion, such as converting a representation in an internal dual of a polynomial basis or dual of a normal basis to a representation in an external basis, as part of a generate-evaluate algorithm. The invention also includes basis shifters which generate a shifted version of a representation in an internal polynomial or normal basis. The basis shifters may be used in import basis conversion as part of a shift-insert algorithm, or in export basis conversion as part of a shift-extract algorithm. The basis shifters may also be used to provide alternative shift-based basis generators. The basis conversion techniques of the invention significantly increase the storage and computational efficiency of dual basis operations in cryptographic systems and other applications.

有限体での双対基底に関わる効率的基底変換

要約
本発明は、多項式基底の双対基底又は正規基底の双対基底などの双対基底に関わる基底変換のための装置及び方法を提供する。本発明を説明するのに都合の良い実施例としては、有限体 GF(qm) -- ただし、q は素数又は素数の冪乗、m は 2 以上の整数とする -- の多項式基底又は正規基底の双対基底要素を生成する基底生成器を用いるものが挙げられる。この基底生成器は、生成・蓄積アルゴリズム (generate-accumulate algorithm) の一環として、外部基底による表現を、多項式基底の内部双対又は正規基底の内部双対による表現に変換すると云ったような「内部化」基底変換や、あるいは、生成・評価アルゴリズム (generate-evaluate algorithm) の一環として、多項式基底の内部双対又は正規基底の内部双対による表現を、外部基底による表現に変換すると云ったような「外部化」基底変換において使用することができる。本発明は、また、内部多項式基底又は内部正規基底による表現をシフトしたものを発生する基底シフタを用いる。この基底シフタは、シフト・挿入アルゴリズム (shift-insert algorithm) の一環としての内部化基底変換や、シフト・取り出しアルゴリズム (shift-extract algorithm) の一環としての外部化基底変換において利用することができる。この基底シフタは、シフト型基底生成器の代替物を得るのに利用することもできる。本発明の基底変換技法は、暗号方式その他の応用において双対基底操作の記憶及び計算効率を大幅に改善する。

参考
1. "Efficient Finite Field Basis Conversion Techniques (Submission to IEEE P1363a)" Burt Kaliski, Moses Liskov and Yiqun Lisa Yin (RSA Laboratories)

|
|

« 米国特許4542293(質量分析)独立クレーム | トップページ | 米国特許6286022(有限体の基底変換)発明の背景 »

数学」カテゴリの記事

知的財産」カテゴリの記事

翻訳」カテゴリの記事

英語/English」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/40172/4708689

この記事へのトラックバック一覧です: 米国特許6286022(有限体の基底変換)要約:

« 米国特許4542293(質量分析)独立クレーム | トップページ | 米国特許6286022(有限体の基底変換)発明の背景 »