Generating sets for the multiplicative groups of algebras over finite fields and expander graphs. (March 2018)

• Record Type: Journal Article
• Authors: Huang, Ming-Deh; Liu, Lian
• Is Part Of: Journal of symbolic computation. Volume 85(2018)
• Page Start: 170
• Page End: 187
• Publication Date: 2018-03
• Subjects: Generating set -- Expander graph -- Cayley graph -- Algebra -- Character sum; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.07.008
• Languages: English
• ISSNs: 0747-7171

Abstract

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.