Time-memory tradeoff in exponentiating a fixed element of GF(qn) requiring a short reference to the memory

Raising ¿¿x to the yth power over GF(qn) can be performed by calculating ¿¿y modulo the minimum polynomial of ¿¿xand then multiplying the result by an n ¿¿ n matrix over GF(q). The elements of the matrix are only a function of x and of the generating polynomial of the field. This principle offers a time-memory trade-off when exponentiating a fixed element of GF(qn), where the multiplications (not the squarings) involved in the standard squareand- multiply process are traded for a reference to a stored n ¿¿ n matrix. The operations which make use of the stored data consume time which is equivalent to a single multiplication operation over the field, and are performed continuously, where the timeconsuming part of the exponentiation process is performed independently of the stored data. It is then shown how the presented principle enables an efficient implementation over GF(qn) of some variations of Diffie-Hellman public-key distribution system.