« 米国特許4542293(質量分析)の要約・発明の背景・独立クレームの翻訳(再編集版) | トップページ | 米国特許5960411(ワンクリック特許)の要約・発明の背景・独立クレームの翻訳(再編集版) »

米国特許6286022(有限体の基底変換)の要約・発明の背景・独立クレームの翻訳(再編集版)

本稿は、 [nouse] において、[ゑびすや] が2005年6月26日(日)、2005年7月5日(火)、2005年7月11日(月)にそれぞれ公表した「米国特許6286022(有限体の基底変換)要約」、「米国特許6286022(有限体の基底変換)発明の背景」、「米国特許6286022(有限体の基底変換)独立クレーム」をまとめて一本にし、英文と和訳文とがパラグラフ毎に並記されるよう再編集したものである。また、この機会に翻訳の補正を行なった(元になった3つの記事に就いても対応する補正をしてある)。

本件は、楕円曲線暗号等で用いられる有限体の基底変換計算の効率化に関する米国特許 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) の一環としての外部化基底変換において利用することができる。この基底シフタは、シフト型基底生成器の代替物を得るのに利用することもできる。本発明の基底変換技法は、暗号方式その他の応用において双対基底操作の記憶及び計算効率を大幅に改善する。


FIELD OF THE INVENTION
発明の分野

The present invention relates generally to techniques for converting signals of a finite field having one basis to signals of a finite field having another basis, and more particularly to finite field basis conversion techniques which involve a dual basis.
本発明は、概括的には、或る基底を有する有限体の信号を、他の基底を有する有限体の信号に変換する技法に関し、特に、双対基底に関する有限体基底変換技法に関する。



BACKGROUND OF THE INVENTION
発明の背景

As described in U.S. application Ser. No. 08/851,045, filed in the name of inventors Burton S. Kaliski Jr. and Yiqun Lisa Yin on May 5, 1997 and entitled "Methods and Apparatus for Efficient Finite Field Basis Conversion," and which is incorporated by reference herein, conversion between different choices of basis for a finite field is an important problem in today's computer systems, particularly for cryptographic operations. While it is possible to convert between two choices of basis by matrix multiplication, the matrix may be too large for some applications, hence the motivation for more storage-efficient techniques.
Burton S. Kaliski Jr. 及び Yiqun Lisa Yin によって発明されたとして、1997年5月5日に出願された米国特許出願番号 08/851,045 "Methods and Apparatus for Efficient Finite Field Basis Conversion" (「効率的な有限体基底変換方法及び装置」) -- ここで参照することで、その内容が本明細書に編入されたものとする -- に記載されている如く、別々に選定された有限体基底間の変換は、現代のコンピュータ・システム、特に暗号演算のためのコンピュータ・システムにとり、重要な課題である。行列の乗算によるなら、選定された2つの基底間の変換は可能だとは言え、応用によっては行列は大規模になりすぎることがあるため、記憶効率が優れた技法が望まれていた。


Elements of a finite field can be represented in a variety of ways, depending on the choice of basis for the representation. Let GF(q.sup.m) be the finite field, and let GF(q) be the ground field over which it is defined, where q is a prime or a prime power. The characteristic of the field is p where q=p.sup.r for some r.gtoreq.1. For even-characteristic fields, p=2. The degree of the field is m; its order is q.sup.m. A basis for the finite field is a set of m elements .omega..sub.0, . . . , .omega..sub.m-1 .epsilon.GF(q.sup.m) such that every element of the finite field can be represented uniquely as a linear combination of basis elements:
##EQU1##
where B[0], . . . , B[m-1] .epsilon. E GF(q) are the coefficients.
有限体の要素は、選定される表現基底に応じて、様々に表現される。GF(qm) をそうした有限体、GF(q) をその基礎体とし(ただし、q は、素数又は素数の冪乗である)、体の標数を p とすると、q=pr かつ r≧1 なる r が存在する。標数が偶数の体では、p=2 となる。体の次数は m であり、位数は、qm である。有限体の基底とは、m 個の要素 ω0, . . . , ωm-1 ∈ GF(qm) からなる集合であって、有限体の全ての要素が、B[0], . . . , B[m-1] ∈ GF(q) を係数とする基底要素の線型結合

  ε =∑i=0m-1B[i]ωi

として一意に表わせるようなもののことである。

訳注
::現在の cocolog は、数式の表現能力が貧弱で、上記も、総和記号が旨く表わせなかった。その意とするところは、B[i]ωi の i=0 から i=m-1 までの総和である。mimeTeX と云う CGI を使うと、html 文書においても TeX もどきの数式表現ができるらしいが、cocolog ではサポートされていないようだ。ちなみに「はてなダイアリー」では使えるとのこと。また、どのような実装によっているかは不明だが、Wikipedia でも、TeX による数式表示が可能である。
::本来の米国特許公報では、上記の ##EQU1## 相当部分に有限体の任意の要素が、基底の線型結合で表わされることを示す式が書かれている。


Two common types of basis are a polynomial basis and a normal basis. In a polynomial basis, the basis elements are successive powers of an element .gamma., called the generator:
.omega..sub.i =.gamma..sup.i.
基底として良く知られているのは、多項式基底と正規基底の2種類である。多項式基底では、基底の要素は、生成元と呼ばれる或る要素 γ の逐次冪乗

   ωii

からなる。


A polynomial .function. of degree m, called the minimal polynomial of .gamma., relates the successive powers:
.gamma..sup.m +.function..sub.m-1.gamma..sup.m-1 +.function..sub.m-2.gamma..sup.m-2 + . . . +.function..sub.1.gamma.+.function..sub.0 =0.
前記の一連の冪乗を以下のように関連付ける γ の最小多項式と呼ばれる次数 m の多項式 f がある:

   γm + fm-1γm-1 + fm-2γm-2 + . . . +f1γ1 + f0 = 0


In a normal basis, the basis elements are successive exponentiations of an element .gamma., again called the generator:
.omega..sub.i =.gamma..sup.q.sup..sup.i .
正規基底では、基底の要素は、やはり生成元と呼ばれる要素 γ の逐次指数乗

   ωiqi

からなる。


Another common type of basis is a dual basis. Let .omega..sub.0, . . . , .omega..sub.m-1 be a basis and let h be a nonzero linear function from GF(q.sup.m) to GF(q), i.e., a function such that for all .epsilon., .phi.,
h(.epsilon.+.phi.)=h(.epsilon.)+h(.phi.).
基底として、これらの他に良く知られているものとしては、双対基底がある。これを説明するために、まず ω0, . . . , ωm-1 を或る基底とし、h を、GF(qm) から GF(q) への零写像でない線型関数であるとする。つまり、すべての ε 及び φ に対して、

   h(ε+φ)=h(ε)+h(φ)

が成り立つものとする。


The dual basis of the basis .omega..sub.0, . . . , .omega..sub.m-1 with respect to h is the basis .xi..sub.0, . . . , .xi..sub.m-1 such that for all i,j,
##EQU2##
基底 ω0, . . . , ωm-1 の h に関する双対基底とは、全ての i, j に対して

   h(ωiξj) = 1 (i=j の時); 0 (i=j でない時)

を満たすような ξ0, . . . , ξm-1 のことである。

訳注
::本来の米国特許公報では、上記の ##EQU2## 相当部分に ωi と ξi との h に関する双対性を示す式が書かれている。そして、その式では、場合分けを、大きな左ブレースを用いて表わしているが、現在の cocolog では、それが不可能なようなので、上記のように「= 1 (i=j の時); 0 (i=j でない時)」とした。この問題も、cocolog が mimeTeX (又は、TeX そのもの)をサポートすれば、解決されるはず。


The dual basis is uniquely defined, and duality is syrnnetric: the dual basis with respect to h of the basis .xi..sub.0, . . . , .xi..sub.-1 is the basis .omega..sub.0, . . . , .omega..sub.m-1. A dual basis can be defined for a polynomial basis, a normal basis, or any other choice of basis, and with respect to a variety of functions (including, as an example, the function that evaluates to a particular coefficient of the representation of the field element in some basis).
双対基底は一意に定まる。また、双対性は対称的である。つまり、h に関する ξ0, . . . , ξm-1 の双対基底は、ω0, . . . , ωm-1 である。双対基底は、多項式基底にも、正規基底にも、その他の如何なる基底に対しても、そして、(例えば、体要素の或る基底における表現の特定の係数を評価する関数と云ったような)様々な関数に関して、定めることができる。


訳注
::上記 ".xi..sub.-1" は --.xi..sub.m-1-- と読み替えてある。


The basis conversion or change-of-basis problem is to compute the representation of an element of a finite field in one basis, given its representation in another basis. The problem has two forms, which distinguish between the internal basis in which finite field operations are performed, and the external basis to and from which one is converting:
基底変換、つまり基底の変更とは、有限体の或る要素の或る基底に対する表現を、他の基底に対する表現から計算することである。有限体の演算が行なわれる内部基底と、変換先・変換元の外部基底とを区別すると、この課題は、2通りの形式で表わされる:


Import problem. Given an internal basis and an external basis for a finite field GF(q.sup.m) and the representation B of a field element in the external basis (the "external representation"), determine the corresponding representation A of the same field element in the internal basis (the "internal representation").
内部化: 有限体 GF(qm) の内部基底及び外部基底が与えられ、更に或る体要素の外部基底による表現 B (「外部表現」)が与えられた際に、前記要素の内部基底による対応表現 A (「内部表現」)を決定すること。


Export problem. Given an internal basis and an external basis for a finite field GF(q.sup.m) and the internal representation A of a field element, determine the corresponding external representation B of the same field element.
外部化: 有限体 GF(qm) の内部基底及び外部基底が与えられ、更に或る要素の内部表現 A が与えられた際に、前記体要素の対応外部表現 B を決定すること。


A conventional solution to both problems is to apply a change-of-basis matrix relating the two a bases. However, as the matrix is potentially quite large, and as the operations involved are not necessarily implementable with operations in either basis, the matrix-based conversion process may be inefficient in many important applications.
二つの課題に対する従来の解決策は、双方の基底に関する基底変換行列を適用することであった。しかし、この行列は非常に大規模になることがあり、また、必要となる演算が、基底のどちら側でも演算として実行に適するとは限らないため、行列に基づく変換方法は、多くの重要な応用において効率的でないことがあった。


Another approach to conversion is to compute with a dual basis. Consider the problem of converting to the basis .omega..sub.0, . . . , .omega..sub.m-1, and let .xi..sub.0, . . . , .xi..sub.m-1 be its dual basis with respect to some linear function h. Then by the definition of the dual basis and the linearity of h, it follows that for all i,
B[]=h(.epsilon..xi..sub.i).
変換を行う他の手法としては、双対基底でもって計算すると云うものがあった。基底 ω0, . . . , ωm-1 への変換を行う場合、或る線型関数 h に関するその双対基底を ξ0, . . . , ξm-1 とするなら、双対基底の定義及び h の線型性により、全ての i に対して、次の式が成り立つ。

   B[i]=h(εξi)

訳注
::上記の式の左辺で "B[]" を --B[i]-- と読み替えてある。


One can therefore convert by multiplying by elements of the dual basis and evaluating the function h, another straightforward and effective solution, which is efficient provided that the elements of the dual basis .xi..sub.0, . . . , .xi..sub.m-1 can be generated efficiently and that the function h can be computed efficiently. But this approach is again limited by a number of difficulties. First, the approach requires the elements of the dual basis, which must either be stored in the form of m.sup.2 coefficients, or computed. Second, it requires the computation of the function h, which may or may not be efficient. More practical choices of h have been suggested, such as a particular coefficient of the representation in some basis. See, for example, S. T. J. Fenn, M. Benaissa, and D. Taylor, "Finite Field Inversion Over the Dual Basis," IEEE Transactions on VLSI, 4(1):134-137, March 1996, which is incorporated by reference herein. But even with a more practical h, there still remains the problem of determining the dual basis efficiently. Moreover, the Fenn et al. method is efficient only when m is very small, and no general efficient conversion algorithm is given.
つまり、双対基底の要素を乗算し、関数 h を評価すると変換が行なえる訣だから、直接的で有効な解決策であり、双対基底要素 ξ0, . . . , ξm-1 が効率的に生成され、関数 h が効率的に計算できるなら、効率も良いものとなる。しかし、この手法にも、幾つかの制限がある。第1に、この手法では、双対基底の要素を m2 個の係数の形式で記憶しておくか、計算するかする必要がある。第2に、関数 h の計算が必要だが、これは効率的なことも非効率的なこともありうる。ある基底における表現の特定の係数と云うような、ヨリ実際的な h の選定も提案されている。例えば、S. T. J. Fenn, M. Benaissa 及び D. Taylor による "Finite Field Inversion Over the Dual Basis「双対基底上の有限体逆元決定」" (IEEE Transactions on VLSI, 4(1):134-137, 1996年3月) を見られたい(ここで参照することで、その内容が本明細書に編入されたものとする)。しかし、ヨリ実際的な関数 h によっても、双対基底を効率的に決定すると云う課題が残っている。更に「Fenn 他」の方法は、m が非常に小さい時にのみ効率的に過ぎず、包括的かつ効率的な変換アルゴリズムは知られていなかった。


A number of other references describe finite field basis conversion operations involving dual basis. For example, U.S. Pat. No. 4,994,995, issued Feb. 19, 1991 to R. W. Anderson, R. L. Gee, T. L. Nguyen, and M. A. Hassner, entitled "Bit-Serial Division Method and Apparatus," describes hardware for a converter which converts an element in GF(2.sup.m) in a polynomial basis representation to a scalar multiple of its dual basis representation, where the scalar is an element of the field. The scalar is chosen so that the scalar multiple of the dual has many of the same elements as the polynomial basis. The hardware consists of AND gates, XOR gates, and a table for computing the trace function. Again, no general conversion algorithm is suggested. I. S. Hsu, T. K. Truong, L. J. Deutsch, and I. S. Reed, "A Comparison of VLSI Architecture of Finite Field Multipliers using Dual, Normal, or Standard Bases," IEEE Transactions on Computers, 37(6):735-739, June 1988, discloses conventional techniques for converting between polynomial and dual bases. D. R. Stinson, "On Bit-Serial Multiplication and Dual Bases in GF(2.sup.m)," IEEE Transactions on Information Theory, 37(6):1733-1737, November 1991, describes change-of-basis matrices between polynomial and dual bases. Given it polynomial basis such that the change-of-basis matrix M from the dual basis to some scalar (c.epsilon. GF(2.sup.m)) times the polynomial basis has as few "1" entries as possible, efficient bit-serial multiplication is possible. Given the minimal polynomial of .alpha., a generator of the polynomial basis, the Stinson reference gives simple formulae computing a scalar c and the weight of the matrix M. Although the above-cited references disclose numerous conventional techniques for converting between a polynomial basis and its dual basis, these techniques are generally inefficient in terms of memory, and may also be inefficient in terms of computation time.
双対基底を用いる有限体基底変換演算に就いて記載する文献は、ほかにも幾つかある。例えば、R. W. Anderson, R. L. Gee, T. L. Nguyen 及び M. A. Hassner による米国特許 4,994,995 "Bit-Serial Division Method and Apparatus「ビットシリアル除算方法及び装置」"(1991年2月19日)には、GF(2m) の要素の、多項式基底による表現を、その双対基底表現のスカラー倍(ただし、このスカラーは体の要素)に変換する変換器が記載されている。このスカラーは、双対をこのスカラー倍したものが、多項式基底と同一の要素を多く含むよう選定されている。この変換器は、AND ゲート群、XOR ゲート群、及びトレース関数を計算するための表からなる。やはり包括的ではない変換アルゴリズムであるが、I. S. Hsu, T. K. Truong, L. J. Deutsch 及び I. S. Reed による"A Comparison of VLSI Architecture of Finite Field Multipliers using Dual, Normal, or Standard Bases 「双対、正規又は標準基底を用いる有限体乗算器の VLSI アーキテクチャの比較」"(IEEE Transactions on Computers, 37(6):735-739, 1988年6月)では、多項式基底と双対基底との間を変換する従来技術が開示されている。D. R. Stinson による "On Bit-Serial Multiplication and Dual Bases in GF(2m)「GF(2m) におけるビットシリアル乗法と双対基底に就いて」" (IEEE Transactions on Information Theory, 37(6):1733-1737, 1991年11月)には、多項式基底と双対基底との間の基底変換行列に就いて記載されている。双対基底から多項式基底のスカラー(c ∈ GF(2m))倍への基底変換行列 M ができる限り少ない "1" 要素を有するような多項式基底に就いては、効率的なビットシリアル乗算が可能である。Stinson は、多項式基底の生成元 α の最小多項式が分っている場合に、スカラー c 及び行列 M の重みを計算する単純な公式を示している。上記の文献は、多項式基底とその双対基底との間を変換する様々な従来技術を開示しているが、こうした技術は、メモリーの観点からは概して非効率的であり、また計算時間の観点からも非効率的でありうる。


The above-cited U.S. application Ser. No. 08/851,045 introduced the "shift-extract" technique of basis conversion, and also provided several storage-efficient and computation-efficient algorithms based on that technique for converting to and from a polynomial or normal basis. The conversion algorithms described therein overcome many of the problems associated with the previously-described conventional approaches. However, a need remains for further improvements in finite field basis conversion, particularly with regard to techniques involving dual basis.
上記の米国特許出願番号 08/851,045 では、基底変換での「シフト・取り出し」技法が導入されて、その技法に基づく多項式基底又は正規基底への、又は多項式基底又は正規基底からの変換を行うことで記憶に就いても計算に就いても効率的なアルゴリズムが幾つか示されている。そこに記載されている変換アルゴリズムは、前記の従来手法に伴う問題点の多くを解消するものである。しかし、特に双対基底を用いる技法に関しては、有限体基底変換に対する一層の改善が必要であった。


It is therefore an object of the present invention to provide efficient finite field basis conversion techniques involving dual basis which do not require an excessively large amount of storage or an excessively large number of operations, and which take advantage of the built-in efficiency of finite field operations in one basis, rather than implementing new operations such as matrix multiplications.
従って、本発明の目的は、行列乗算のような演算を別途実装せずに、一つの基底における有限体演算の本来的な効率性を活用するることで、過度に大容量の記憶や過度に多数の演算を必要としない、双対基底を用いる有限体基底変換技術を提供することにある。


独立クレーム

1. An apparatus for determining elements in a dual of a normal basis for a finite field, the apparatus comprising:
an exponentiator which is operative to raise one of an input value and an output of a multiplier to a power; and
the multiplier which is operative to multiply one of the input value and an output of the exponentiator by a function of a generator of the dual basis, wherein the multiplier and exponentiator are configured to operate such that one of the multiplier and exponentiator generates an output value corresponding to a shifted version of the input value in the dual of the normal basis.
1. 有限体の正規基底の双対基底により要素を決定する装置であって、
入力値又は乗算器の出力の一方を冪乗するよう動作する指数冪乗器からなり、
前記乗算器は、前記入力値又は前記指数冪乗器出力の一方に、双対基底生成元の関数を乗算し、前記乗算器と前記指数冪乗器とは、前記乗算器又は前記指数冪乗器の一方が、前記正規基底の双対基底に関して入力値をシフトしたものに対応する出力値を生成するよう構成されてなることを特徴とする有限体の正規基底の双対基底による要素決定装置。


16. An apparatus for determining elements of a dual of a normal basis for a finite field, the apparatus comprising:
an exponentiator which raises an input value to a power, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and
a multiplier which is operative to multiply an output of the exponentiator, generated after the designated number of repetitions, by a scaling factor which is a function of a (q-1).sup.st root of S, where S is a generator of the normal basis and q is a prime or a power of a prime, such that an output of the multiplier corresponds to an element of the dual of the normal basis.
16. 有限体の正規基底の双対基底の要素を決定する装置であって、
入力値を冪乗し、冪乗演算が指定回数繰り返されるよう自身の出力が自身の入力に印加される指数冪乗器と、
前記指定回数の繰り返し後に生成された前記指数冪乗器の出力に、q を素数又は素数の冪乗として、前記正規基底の生成元 S の (q-1) 乗根の関数である調整倍率を乗算して、出力が前記正規基底の双対基底の或る要素に対応するようにしてなる乗算器とからなることを特徴とする有限体の正規基底の双対基底の要素決定装置。


19. An apparatus for determining elements of a dual of a normal basis for a finite field, the apparatus comprising:
an exponentiator which raises an input value to a power, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and
a multiplier which is operative to multiply an output of the exponentiator, generated after the designated number of repetitions, by one of an initial value and a previously-generated output of the multiplier, such that a current output of the multiplier corresponds to an element of the dual of the normal basis.
19. 有限体の正規基底の双対基底の要素を決定する装置であって、
入力値を冪乗し、冪乗演算が指定回数繰り返されるよう自身の出力が自身の入力に印加される指数冪乗器と、
前記指定回数の繰り返し後に生成された前記指数冪乗器の出力に、初期値又は自身の以前の出力の一方を乗算して、現在の出力が前記正規基底の双対基底の或る要素に対応するようにしてなる乗算器とからなることを特徴とする有限体の正規基底の双対基底の要素決定装置。


25. A method for determining elements in a dual of a normal basis for a finite field, the method comprising:
exponentiating one of a signal corresponding to an input value and a signal corresponding to an output of a multiplier in an exponentiator; and
multiplying one of a signal corresponding to the input value and a signal corresponding to an output of the exponentiator by a function of a generator of the dual basis in the multiplier, wherein the multiplier and exponentiator are configured to operate such that one of the multiplier and exponentiator generates an output value corresponding to a shifted version of the input value in the dual of the normal basis.
25. 有限体の正規基底の双対基底により要素を決定する方法であって、
指数冪乗器内において、入力値に対応する信号又は乗算器の出力に対応する信号の一方を指数冪乗する段階と、
前記乗算器内において、前記入力値に対応する信号又は前記指数冪乗器出力に対応する信号の一方に、双対基底生成元の関数を乗算するが、ここで前記乗算器及び前記指数冪乗器は、前記乗算器又は前記指数冪乗器の一方が、前記正規基底の双対基底に関して入力値をシフトしたものに対応する出力値を生成するよう構成されてなる段階とからなることを特徴とする有限体の正規基底の双対基底による要素決定方法。


26. A method for determining elements of a dual of a normal basis for a finite field, the method comprising:
raising a signal corresponding to an input value to a power in an exponentiator, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and
multiplying an output of the exponentiator, generated after the designated number of repetitions, in a multiplier by a scaling factor which is a function of a (q-1).sup.st root of S, where S is a generator of the normal basis and q is a prime or a power of a prime, such that an output of the multiplier corresponds to an element of the dual of the normal basis.
26. 有限体の正規基底の双対基底の要素を決定する方法であって、
指数冪乗器内において、入力値に対応する信号を冪乗する際、前記指数冪乗器が冪乗演算を指定回数繰り返すよう、前記指数冪乗器出力を前記指数冪乗器入力に印加する段階と、
乗算器内において、前記指定回数の繰り返し後に生成された前記指数冪乗器の出力に、q を素数又は素数の冪乗として、前記正規基底の生成元 S の (q-1) 乗根の関数である調整倍率を乗算して、前記乗算器出力が前記正規基底の双対基底の或る要素に対応するようにする段階とからなることを特徴とする有限体の正規基底の双対基底の要素決定方法。


27. A method for determining elements of a dual of a normal basis for a finite field, the method comprising:
raising a signal corresponding to an input value to a power in an exponentiator, wherein the output of the exponentiator is applied to its input such that the exponentiator repeats the raising to a power operation a designated number of times; and
multiplying an output of the exponentiator, generated after the designated number of repetitions, in a multiplier by one of an initial value and a previously-generated output of the multiplier, such that a current output of the multiplier corresponds to an element of the dual of the normal basis.
27. 有限体の正規基底の双対基底の要素を決定する方法であって、
指数冪乗器内において、入力値に対応する信号を冪乗する際、前記指数冪乗器が冪乗演算を指定回数繰り返すよう、前記指数冪乗器出力を前記指数冪乗器入力に印加する段階と、
乗算器内において、前記指定回数の繰り返し後に生成された前記指数冪乗器の出力に、初期値又は前記乗算器の以前の出力の一方を乗算して、前記乗算器の現在の出力が前記正規基底の双対基底の或る要素に対応するようにする段階とからなることを特徴とする有限体の正規基底の双対基底の要素決定方法。


28. A method for determining elements in a dual of a normal basis for a finite field, the method comprising:
(a) multiplying a signal corresponding to an input value by a first function;
(b) raising a signal corresponding to a value resulting from step (a) to a power; and
(c) multiplying a signal corresponding to a value resulting from step (b) by a second function thereby generating an output value corresponding to a shifted version of the input value in the dual of the normal basis, wherein one of the first function and the second function is a function of a generator of the dual of the normal basis.
28. 有限体の正規基底の双対基底により要素を決定する方法であって、
(a) 入力値に対応する信号に、第1の関数を乗算する段階と、
(b) (a) 段階の結果の値に対応する信号を冪乗する段階と、
(c) (b) 段階の結果の値に対応する信号に、第2の関数を乗算して、前記正規基底の双対基底に関して入力値をシフトしたものに対応する出力値を生成するが、ここで前記第1の関数又は前記第2の関数の一方が、前記正規基底の双対基底の生成元の関数であるようにしてなる段階とからなることを特徴とする有限体の正規基底の双対基底による要素の決定方法。

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

|
|

« 米国特許4542293(質量分析)の要約・発明の背景・独立クレームの翻訳(再編集版) | トップページ | 米国特許5960411(ワンクリック特許)の要約・発明の背景・独立クレームの翻訳(再編集版) »

数学」カテゴリの記事

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

翻訳」カテゴリの記事

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

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: 米国特許6286022(有限体の基底変換)の要約・発明の背景・独立クレームの翻訳(再編集版):

« 米国特許4542293(質量分析)の要約・発明の背景・独立クレームの翻訳(再編集版) | トップページ | 米国特許5960411(ワンクリック特許)の要約・発明の背景・独立クレームの翻訳(再編集版) »