×

System and method for efficient basis conversion

  • US 8,145,697 B2
  • Filed: 10/31/2007
  • Issued: 03/27/2012
  • Est. Priority Date: 03/12/1999
  • Status: Expired due to Term
First Claim
Patent Images

1. A non-transitory computer readable medium comprising computer executable instructions for a processor in a device converting an element of a finite field of characteristic q 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 basis is to be used in a cryptographic scheme, said computer readable medium comprising instructions for:

  • 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; and

    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 scheme;

    said evaluation being characterised by the steps of;

    i) 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 operations of multiplication by x and exponentiation by q;

    ii) obtaining values of each of said component polynomials by evaluating each of said component polynomials at said root r; and

    iii) computing the value of a(r) from said values of said component polynomials at said root r, using operations of multiplication by r and exponentiation by q.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×