Method and apparatus for basis conversion in finite field

Details Method and apparatus for basis conversion in finite field Method and apparatus for basis conversion in finite field

2003-11-07

2008-03-18

Malzahn, D. H. (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

07346641

ABSTRACT:
There are provided efficient basis conversion matrices Dsdand Ddsand a basis conversion method in a finite field GF(2n) using the basis conversion matrices for a case where a defining polynomial is a pentanomial, xn+xk(3)+xk(2)+xk(1)+1, and the exponents n, k(3), k(2), and (k1) satisfy the condition, n−k(3)>k(3)−k(1). In addition, an apparatus for the basis conversion in the finite field GF(2n) is provided. Since a pentanomial having a general form in an arbitrary degree is used as the defining polynomial, basis conversion between a standard representation and a dual representation is efficiently performed. Consequently, a dual basis multiplier can be efficiently implemented.

REFERENCES:
patent: 4994995 (1991-02-01), Anderson et al.
patent: 5854759 (1998-12-01), Kaliski, Jr. et al.
patent: 6286022 (2001-09-01), Kaliski, Jr. et al.
patent: 2001/0056452 (2001-12-01), Kaliski et al.
patent: 2004/0078407 (2004-04-01), Naslund et al.
patent: 2006/0072743 (2006-04-01), Naslund et al.
patent: 2000-0026250 (2000-05-01), None
Berlekamp, Elwyn, “Bit-Serial Reed—Solomon Encoders”, IEEE Transactions on Information Theory, vol. IT-28, No. 6, pp. 869-874 (Nov. 1982).
Fenn, S.T.J., et al., “Bit-serial dual basis systolic multipliers for GF(2m)”, IEEE 0-7803-2570-2/95, pp. 2000-2003 (1995).
Fenn, S.T.J., et al., “Dual basis systolic multipliers for GF(2m)”, IEE Proc.-Comput. Digit. Tech., vol. 144, No. 1, pp. 43-46, (Jan. 1997).
Fenn, S.T.J., et al., “Finite Field Inversion Over the Dual Basis”, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 4, No. 1, pp. 134-137, (Mar. 1996).
Fenn, Sebastian T.J., et al., “GF(2m) Multiplication and Division Over the Dual Basis”, IEEE Transactions on Computers, vol. 45, No. 3, pp. 319-327 (Mar. 1996).
Gollmann, D., “Equally Spaced Polynomials, Dual Bases, and Multiplication in F2n”, IEEE Transactions on Computers, vol. 51, No. 5, pp. 588-591 (May 2002).
Hasan, M.A., et al., “Division and bit-serial multiplication over GF(qm)” IEE Proceedings-E, vol. 139, No. 3, pp. 230-236, (May 1992).
Hsu, I.S., et al., “A Comparison of VLSI Architecture of Finite Field Multipliers Using Dual, Normal, or Standard Bases”, IEEE Transactions on Computers, vol. 37, No. 6, pp. 735-739, (Jun. 1988).
Kwon, Soonhak, et al., “Efficient Bit Serial Multiplication Using Optimal Normal Bases of Type II in GF(2m)”, Information Security. International Conference: Proceedings ISC, pp. 300-308 (Sep. 30, 2002).
Morii, Masakatu, et al., “Efficient Bit-Serial Multiplication and the Discrete-Time Wiener-Hopf Equation Over Finite Fields”, IEEE Transactions on Information Theory, vol. 35, No. 6, pp. 1177-1183, (Nov. 1989).
Scott, P. Andrew, et al., “A Fast VLSI Multiplier for GF(2m)”, IEEE Journal on Selected Areas in Communication, vol. SAC-4, No. 1, pp. 62-65, (Jan. 1986).
Stinson, D.R., “On Bit-Serial Multiplication and Dual Bases in GF(2m)”, IEEE Transactions on Information Theory, vol. 37, No. 6, pp. 1733-1736 (Nov. 1991).
Wang, Charles C., “VLSI Architectures for Computing Multiplications and Inverses in GF(2m)”, IEEE Transactions on Computers, vol. C-34, No. 8, pp. 709-717, (Aug. 1985).
Wozniak, J.J., “Systolic dual basis serial multiplier”, IEE Proc.Comput. Digit. Tech., vol. 145, No. 3, pp. 237-241 (May 1998).
Wu, Waupeng, “New Low-Complexity Bit-Parallel Finite Field Multipliers Using Weakly Dual Bases”, IEEE Transactions on Computers, vol. 47, No. 11, pp. 1223-1234, (Nov. 1998).

Affiliated with

Also associated with

Rating

Method and apparatus for basis conversion in finite field does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3976496