Patent ID: 7076061

Claim:
A method of determining a public key having an optionally reduced length and a number p for a cryptosystem resident in a device that includes a memory, using a GF(p) or GF (p 2 ) arithmetic to achieve GF(p 6 ) security, without explicitly constructing GF(p 6 ), comprising the steps of: selecting a number q and the number p such that p 2 âˆ’p+1 is an integer multiple of the number q; selecting a number g of order q, where g and its conjugates can be represented by B, where F g (X)=X 3 âˆ’BX 2 +B p Xâˆ’1 and the roots are g, g pâˆ’1 , g âˆ’p ; representing the powers of the conjugates of g using their trace over the field GF(p 2 ): and providing p, q, and B for computation of the public key as a function of p, q, and B.