This invention describes a method for evaluating a polynomial in an extension field F.sub.q.sup.M, wherein the method comprises the steps of partitioning the polynomial into a plurality of parts, each part is comprised of smaller polynomials using a q.sup.-th power operation in a field of characteristic q; and computing for each part components of q.sup.-th powers from components of smaller powers. A further embodiment of the invention provides for a method of converting a field element represented in terms of a first basis to its representation in a second basis, comprising the steps of partitioning a polynomial, being a polynomial in the second basis, into a plurality of parts, wherein each part is comprised of smaller polynomials using a q.sup.-th power operation in a field of characteristic q; evaluating the polynomial at a root thereof by computing for each part components of q.sup.-th powers from components of smaller powers; and evaluating the field element at the root of the polynomial.