Methods and apparatus for efficient finite field basis conversion

摘要

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.