On fast multiplication in normal bases of finite fields

We estimate the complexity of transition from normal bases to standard ones and discuss the related problems of effective realization of arithmetic operations in finite fields of high dimensionality.
The work was supported by the Russian Foundation for Basic Research, grant 99–01–01175, the Program of support of leading scientific schools, grant 00–15–96103, the Program ‘Universities of Russia,’ and by the Federal program ‘Integration,’ joint project A0110.