Paper 2015/764

On Generating Coset Representatives of PGL_2(\F_q) in PGL_2(\F_{q^2})

Jincheng Zhuang and Qi Cheng

Abstract

There are q^3 + q right PGL_2(\F_q)-cosets in the group PGL_2(\F_{q^2}). In this paper, we present a method of generating all the coset representatives, which runs in time \tilde{O}(q^3), thus achieves the optimal time complexity up to a constant factor. Our algorithm has applications in solving discrete logarithms and finding primitive elements in finite fields of small characteristic.