Efficient finite field basis conversion involving a dual basis

摘要

The invention provides apparatus and methods for use in basis conversion involving a dual basis, such as a dual of a polynomial basis or dual of a normal basis. The invention in an illustrative embodiment includes basis generators for generating elements of a dual of a polynomial or a normal basis of a finite field GF(q^m), where q is a prime number or power of a prime number and m is an integer greater than or equal to 2. The basis generators can be used in “import” basis conversion, such as converting a representation in an external basis to a representation in an internal dual of a polynomial basis or dual of a normal basis, as part of a generate-accumulate algorithm, or in “export” basis conversion, such as converting a representation in an internal dual of a polynomial basis or dual of a normal basis to a representation in an external basis, as part of a generate-evaluate algorithm. The invention also includes basis shifters which generate a shifted version of a representation in an internal polynomial or normal basis. The basis shifters may be used in import basis conversion as part of a shift-insert algorithm, or in export basis conversion as part of a shift-extract algorithm. The basis shifters may also be used to provide alternative shift-based basis generators. The basis conversion techniques of the invention significantly increase the storage and computational efficiency of dual basis operations in cryptographic systems and other applications.