Efficient finite field basis conversion involving a dual basis

Details Efficient finite field basis conversion involving a dual basis Efficient finite field basis conversion involving a dual basis

1998-11-18

2001-09-04

Mai, Tan V. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06286022

ABSTRACT:

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.
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
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
r
for some r≧1. For even-characteristic fields, p=2. The degree of the field is m; its order is q
m
. A basis for the finite field is a set of m elements &ohgr;
0
, . . . , &ohgr;
m−1
&egr;GF(q
m
) such that every element of the finite field can be represented uniquely as a linear combination of basis elements:
ϵ
=
∑
i
=
0
m
-
1
⁢
 
⁢
B
⁡
[
i
]
⁢
ω
i
where B[0], . . . , B[m−1] &egr; E GF(q) are the coefficients. 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 &ggr;, called the generator:
&ohgr;
i
=&ggr;
i
.
A polynomial ƒ of degree m, called the minimal polynomial of &ggr;, relates the successive powers:
&ggr;
m
+ƒ
m−1
&ggr;
m−1
+ƒ
m−2
&ggr;
m−2
+ . . . +ƒ
1
&ggr;+ƒ
0
=0.
In a normal basis, the basis elements are successive exponentiations of an element &ggr;, again called the generator:
&ohgr;
i
=&ggr;
q
i
.
Another common type of basis is a dual basis. Let &ohgr;
0
, . . . , &ohgr;
m−1
be a basis and let h be a nonzero linear function from GF(q
m
) to GF(q), i.e., a function such that for all &egr;, &phgr;,
h
(&egr;+&phgr;)=
h
(&egr;)+
h
(&phgr;).
The dual basis of the basis &ohgr;
0
, . . . , &ohgr;
m−1
with respect to h is the basis &xgr;
0
, . . . , &xgr;
m−1
such that for all i,j,
h
⁡
(
ω
i
⁢
ξ
j
)
=
{
1
0
⁢
if
⁢
 
⁢
i
=
j
;
otherwise
.
The dual basis is uniquely defined, and duality is syrnnetric: the dual basis with respect to h of the basis &xgr;
0
, . . . , &xgr;
−1
is the basis &ohgr;
0
, . . . , &ohgr;
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).
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:
 Import problem. Given an internal basis and an external basis for a finite field GF(q
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”).
 Export problem. Given an internal basis and an external basis for a finite field GF(q
m
) and the internal representation A of a field element, determine the corresponding external representation B of the same field element.
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 &ohgr;
0
, . . . , &ohgr;
m−1
, and let &xgr;
0
, . . . , &xgr;
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
(&egr;&xgr;
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 &xgr;
0
, . . . , &xgr;
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
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.
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
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
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&egr; GF(2
m
)) times the polynomial basis has as few “1” entries as possible, efficient bit-serial multiplication is possible. Given the minimal polynomial of &agr;, 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.
The above-cited U.S. application Ser. No. 08/851,045 intr

Affiliated with

Also associated with

Rating

Efficient finite field basis conversion involving a dual basis does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient finite field basis conversion involving a dual basis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient finite field basis conversion involving a dual basis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2523127