US5854759A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for efficient finite field basis conversion
Assignee: EMC Corp
•
Filing: 1997-05-05
•
Granted: 1998-12-29
•
Expires: 2017-05-05
Abstract
Abstract Methods and apparatus for converting a value A representing in a first basis an element of a finite field GF(qm) to a value B representing the element in a second basis, where q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and where the value B includes a vector of m coefficients from a finite field GF(q). An exemplary apparatus, particularly well-suited for exporting the value A in an internal basis representation to the value B in an external basis representation, includes an externally shifted sequence generator for generating from the value A a sequence of intermediate values representing in the first basis elements of the finite field GF(qm) whose representations in the second basis are related to the value B by a predetermined external shift operation. An extractor coupled to the externally shifted sequence generator receives and processes the sequence of intermediate values to generate each coefficient of the value B.
Inventors
- 👤 Burton S. Kaliski, Jr.
- 👤 Yiqun Lisa Yin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 01:05
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/725
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
157 words
A method of generating in a digital data processor, from a value A representing in a first basis an element of a finite field GF(q m ), at least part of a value B representing said element in a second basis, wherein q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and wherein said value B includes a vector of m coefficients from a finite field GF(q), the method comprising the steps of: generating from said value A in an externally shifted sequence generator a sequence of intermediate values representing in said first basis elements of the finite field GF(q m ) whose representations in said second basis are related to said value B by at least one predetermined external shift operation; and generating from said sequence of intermediate values in an extractor at least a subset of the coefficients of said value B.
Claim 2
Independent Claim
157 words
A method of generating in a digital data processor, from a value A representing in a first basis an element of a finite field GF(q m ), at least part of a value B representing said element in a second basis, wherein q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and wherein said value B includes a vector of m coefficients from a finite field GF(q), the method comprising the steps of: generating from said value A in an externally shifted sequence generator a sequence of intermediate values representing in said first basis elements of the finite field GF(q m ) whose representations in said second basis are related to said value B by at least one predetermined external shift operation; and generating from said sequence of intermediate values in an extractor at least a subset of the coefficients of said value B.
Claim 3
Dependent Claim
45 words
The method of claim 1 wherein the step of generating from said value A a sequence of intermediate values includes sequentially applying a predetermined logic function to said value A, such that after a number of steps, each of said intermediate values has been generated.
Claim 4
Dependent Claim
12 words
The method of claim 2 wherein said number of steps is m-1.
Claim 5
Dependent Claim
26 words
The method of claim 2 wherein said number of steps is approximately .left brkt-bot.(m-1)/k.right brkt-bot., where k is an integer greater than or equal to 2.
Claim 6
Dependent Claim
38 words
The method of claim 1 wherein said second basis is a normal basis and said predetermined external shift operation is a rotation operation that rotates in the direction of increasing powers of a generator of the normal basis.
Claim 7
Dependent Claim
38 words
The method of claim 1 wherein said second basis is a polynomial basis and said predetermined external shift operation is a shift operation that shifts in the direction of decreasing powers of a generator of the polynomial basis.
Claim 8
Dependent Claim
34 words
The method of claim 1 wherein the step of generating the sequence of intermediate values further includes feeding back at least one of the intermediate values to a register previously storing the value A.
Claim 9
Dependent Claim
35 words
The method of claim 1 further including the step of feeding back at least one of the coefficients of said value B to an input of the externally shifted sequence generator performing the generating step.
Claim 10
Dependent Claim
43 words
The method of claim 1 further including the step of premultiplying the value A by a scaling factor, such that the step of generating the sequence of intermediate values and the step of generating the coefficients may be performed in a scaled basis.
Claim 11
Dependent Claim
36 words
The method of claim 1 wherein the step of generating the coefficients includes applying the sequence of intermediate values to a coefficient selector which processes the intermediate values to generate the coefficients of said value B.
Claim 12
Dependent Claim
37 words
The method of claim 10 wherein the step of generating the coefficients includes multiplying the sequence of intermediate values by at least one extraction factor prior to applying the sequence of intermediate values to the coefficient selector.
Claim 13
Dependent Claim
39 words
The method of claim 1 wherein the step of generating the coefficients includes generating a coefficient of said value B as a dot product of coefficients of an intermediate value and a corresponding set of values {s i }.
Claim 14
Dependent Claim
30 words
The method of claim 1 wherein the step of generating the coefficients includes generating a coefficient of said value B as an exclusive-or of selected coefficients of an intermediate value.
Claim 15
Dependent Claim
53 words
The method of claim 1 wherein the step of generating the coefficients includes applying an additional predetermined external shift operation to the sequence of intermediate values prior to computing the coefficients of said value B, wherein the additional predetermined external shift operation shifts subcoefficients in one or more coefficients of the intermediate value.
Claim 16
Dependent Claim
43 words
The method of claim 1 wherein the step of generating the sequence of intermediate values includes applying the value A to an exponentiator to generate the sequence of intermediate values in the form of a sequence of successive exponentiations of the value A.
Claim 17
Dependent Claim
72 words
The method of claim 1 wherein the step of generating the sequence of intermediate values includes applying the value A to a scalar subtractor, and multiplying the result by G -1 , where G -1 is an internal basis representation of an inverse of a generator for the external basis over GF(q m ), to perform a computation A←(A-tI)G -1 , where t is one of said coefficients of said value B.
Claim 18
Dependent Claim
78 words
The method of claim 1 wherein the step of generating the sequence of intermediate values includes applying the value A to a scalar multiplier/subtractor having an input scaling factor V, and multiplying the result by G -1 , where G -1 is an internal basis representation of an inverse of a generator for the external basis over GF(q m ), to perform a computation A←(A-tV)G -1 , where t is one of said coefficients of said value B.
Claim 19
Independent Claim
158 words
An apparatus for generating, from a value A representing in a first basis an element of a finite field GF(q m ), at least part of a value B representing said element in a second basis, wherein q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and wherein said value B includes a vector of m coefficients from a finite field GF(q), the apparatus comprising: an externally shifted sequence generator for generating from said value A a sequence of intermediate values representing in said first basis elements of the finite field GF(q m ) whose representations in said second basis are related to said value B by at least one predetermined external shift operation; and an extractor coupled to the externally shifted sequence generator and operative to generate at least a subset of the coefficients of said value B from said sequence of intermediate values.
Claim 20
Independent Claim
158 words
An apparatus for generating, from a value A representing in a first basis an element of a finite field GF(q m ), at least part of a value B representing said element in a second basis, wherein q is a prime number or power of a prime number and m is an integer greater than or equal to 2, and wherein said value B includes a vector of m coefficients from a finite field GF(q), the apparatus comprising: an externally shifted sequence generator for generating from said value A a sequence of intermediate values representing in said first basis elements of the finite field GF(q m ) whose representations in said second basis are related to said value B by at least one predetermined external shift operation; and an extractor coupled to the externally shifted sequence generator and operative to generate at least a subset of the coefficients of said value B from said sequence of intermediate values.
Claim 21
Dependent Claim
36 words
The apparatus of claim 18 wherein the externally shifted sequence generator sequentially applies a predetermined logic function to said value A, such that after a number of steps, each of said intermediate values has been computed.
Claim 22
Dependent Claim
12 words
The apparatus of claim 19 wherein said number of steps is m-1.
Claim 23
Dependent Claim
26 words
The apparatus of claim 19 wherein said number of steps is approximately .left brkt-bot.(m-1)/k.right brkt-bot., where k is an integer greater than or equal to 2.
Claim 24
Dependent Claim
38 words
The apparatus of claim 18 wherein said second basis is a normal basis and said predetermined external shift operation is a rotation operation that rotates in the direction of increasing powers of a generator of the normal basis.
Claim 25
Dependent Claim
38 words
The apparatus of claim 18 wherein said second basis is a polynomial basis and said predetermined external shift operation is a shift operation that shifts in the direction of decreasing powers of a generator of the polynomial basis.
Claim 26
Dependent Claim
34 words
The apparatus of claim 18 further including a feedback path within the externally shifted sequence generator for feeding back at least one of the intermediate values to a register previously storing the value A.
Claim 27
Dependent Claim
27 words
The apparatus of claim 18 further including a feedback path between at least one output of the extractor and an input of the externally shifted sequence generator.
Claim 28
Dependent Claim
27 words
The apparatus of claim 18 further including a premultiplier for multiplying the value A by a scaling factor before the sequence of intermediate values are generated therefrom.
Claim 29
Dependent Claim
32 words
The apparatus of claim 18 wherein the extractor includes a coefficient selector which receives the sequence of intermediate values and processes the intermediate values to generate the coefficients of said value B.
Claim 30
Dependent Claim
36 words
The apparatus of claim 27 wherein the extractor further includes a multiplier for multiplying the sequence of intermediate values by at least one extraction factor before applying the sequence of intermediate values to the coefficient selector.
Claim 31
Dependent Claim
37 words
The apparatus of claim 18 wherein the extractor is operative to generate a coefficient of said value B as a dot product of coefficients of an intermediate value and a corresponding set of values {s i }.
Claim 32
Dependent Claim
28 words
The apparatus of claim 18 wherein the extractor is operative to generate a coefficient of said value B as an exclusive-or of selected coefficients of an intermediate value.
Claim 33
Dependent Claim
51 words
The apparatus of claim 18 wherein the extractor is operative to apply an additional predetermined external shift operation to the sequence of intermediate values prior to generating the coefficients of said value B, wherein the additional predetermined external shift operation shifts subcoefficients in one or more coefficients of the intermediate value.
Claim 34
Dependent Claim
45 words
The apparatus of claim 18 wherein the externally shifted sequence generator includes an exponentiator arranged in a feedback loop with an input register, such that the sequence of intermediate values is generated in the form of a sequence of successive exponentiations of said value A.
Claim 35
Dependent Claim
73 words
The apparatus of claim 18 wherein the externally shifted sequence generator is operative to apply the value A to a scalar subtractor, and to multiply the result by G -1 , where G -1 is an internal basis representation of an inverse of a generator for the external basis over GF(q m ), so as to perform the computation A←(A-tI)G -1 , where t is one of said coefficients of said value B.
Claim 36
Dependent Claim
79 words
The apparatus of claim 18 wherein the externally shifted sequence generator is operative to apply the value A to a scalar multiplier/subtractor having an input scaling factor V, and to multiply the result by G -1 , where G -1 is an internal basis representation of an inverse of a generator for the external basis over GF(q m ), so as to perform the computation A←(A-tV)G -1 , where t is one of said coefficients of said value B.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-28 | 2002-06-29 | 2002-12-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-28 | 2006-06-29 | 2006-12-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-28 | 2010-06-29 | 2010-12-29 | $7700.00 | Window Closed / Lapsed |