Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2007-10-04
2011-12-27
Malzahn, David H (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
08086656
ABSTRACT:
This invention describes a method for evaluating a polynomial in an extension field FqM, wherein the method comprises the steps of partitioning the polynomial into a plurality of parts, each part is comprised of smaller polynomials using a q−thpower operation in a field of characteristic q; and computing for each part components of q−thpowers from components of smaller powers. A further embodiment of the invention provides for a method of converting a field element represented in terms of a first basis to its representation in a second basis, comprising the steps of partitioning a polynomial, being a polynomial in the second basis, into a plurality of parts, wherein each part is comprised of smaller polynomials using a q−thpower operation in a field of characteristic q; evaluating the polynomial at a root thereof by computing for each part components of q−thpowers from components of smaller powers; and evaluating the field element at the root of the polynomial.
REFERENCES:
patent: 4031370 (1977-06-01), Catherall
patent: 4417338 (1983-11-01), Davida
patent: 4847801 (1989-07-01), Tong
patent: 4866716 (1989-09-01), Weng
patent: 5485474 (1996-01-01), Rabin
patent: 5761102 (1998-06-01), Weng
patent: 6026420 (2000-02-01), DesJardins et al.
patent: 6058500 (2000-05-01), DesJardins et al.
patent: 6192497 (2001-02-01), Yang et al.
patent: 6219815 (2001-04-01), DesJardins et al.
patent: 6895422 (2005-05-01), Walster et al.
patent: 7299253 (2007-11-01), Lambert
patent: 2002/0041682 (2002-04-01), Lambert
patent: 2008/0077645 (2008-03-01), Lambert
patent: 2008/0177814 (2008-07-01), Lambert
patent: 0806838 (1997-11-01), None
Lu, E-H. et al.; “VSLI Architectures for Computing Polynomials in GF(2n)”; International Conference on Systems Engineering; 1987; pp. 555-558; IEEE; New York; U.S.A.
Kovac, M. et al.; “Ace: A VSLI Chip for Galois Field GF(2n) Based Exponentiation”; IEEE Transactions on Circuits and Systems II: Analog and Digital Processing; Apr. 1996; pp. 289-297; vol. 43, No. 4; IEEE; New York; U.S.A.
Weisstein, Eric W.; “Polynomial.” from MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/Polynomial.html.
Agnew, G.B. et al.; “An implementation of elliptic curve cryptosystems over F2155”; IEEE Journal on Selected Communications; Jun. 1993; pp. 804-813; vol. 11, No. 5; IEEE; New York; U.S.A.
Search Report from PCT/CA0/00256 dated Jul. 7, 2000.
Blake Cassels & Graydon LLP
Certicom Corp.
Malzahn David H
Orange John R. S.
Slaney Brett J.
LandOfFree
System and method for efficient basis conversion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for efficient basis conversion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for efficient basis conversion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4312598