We consider computational problems concerning algebras over finite fields. In particular, we propose an algorithm for finding a small generating set for the multiplicative group of Fq[x]/F, where q=pn is a prime power and F∈Fq[x] is a polynomial not necessarily irreducible. Based on this result, a new set of expander graphs can be explicitly constructed. In addition, we present algorithms for basis construction and decomposition of a given element with respect to the basis.
Financed by the National Centre for Research and Development under grant No. SP/I/1/77065/10 by the strategic scientific research and experimental development program:
SYNAT - “Interdisciplinary System for Interactive Scientific and Scientific-Technical Information”.