Importance

Loading Importance Indicators...

Abstract

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.sup.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.

Loading the Abstract Image...

First Claim