Generating sets for the multiplicative groups of algebras over finite fields and expander graphs.

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 F q [ x ] / F , where q = p n is a prime power and F ∈ F q [ 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. [ABSTRACT FROM AUTHOR]