On Generating Coset Representatives of PGL_2(F_q) in PGL_2(F_(q~2))

摘要

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 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.