Methods and apparatus for efficient finite field basis conversion

Abstract

Methods and apparatus for converting a value A representing in a first basis an element of a finite field GF(q.sup.m) 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(q.sup.m) 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.

Dependencies are inferred from the claim text.