Generating sets for the multiplicative groups of algebras over finite fields and expander graphs. (March 2018) - Huang, Ming-Deh; Liu, Lian
Abstract: 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.