On constructing circuits for transforming the polynomial and normal bases of finite fields from one to the other

摘要

It is shown that the transformations of normal and polynomial bases of the field GF(pn) from one to the other can be performed by a circuit over GF(p) with complexity O(nJ -806) and depth O(logn).