Patent ID: 7299253
Filing Date: 2007-11-20
Classification: G06F,H04L

Abstract:
1. A method for converting an element of a finite field of characteristic q stored in a cryptographic system from a representation in a first basis defined by a first irreducible polynomial to a representation in a second basis defined by a second irreducible polynomial, wherein said representation in said second basic is to be used in a cryptographic scheme, said method comprising the steps of: a) obtaining said element from said cryptographic system; b) representing said element of said finite field in said first basis as a polynomial a(x); c) determining a root r of said second irreducible polynomial; d) evaluating said polynomial a(x) at said root r to obtain a representation a(r) of a(x) in said second basis for use in said cryptographic system; said evaluation being characterised by the steps of: e) partitioning said polynomial a(x) into a plurality of component polynomials, such that said polynomial a(x) is recoverable by combining said plurality of component polynomials using the operations of multiplication by x and exponentiation by q; f) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r; g) computing the value of a(r) from said values of said component polynomials at said root r, using the operations of multiplication by r and exponentiation by q and; h) providing said representation a(r) in said second basis to said cryptographic scheme.