On Generating Coset Representatives of PGL 2 (F q ) in PGL 2 (F q 2 ).
Jincheng Zhuang, Qi Cheng · 2015
Abstract. There are q3+q right PGL2(Fq)−cosets in the group PGL2(Fq2). In this paper, we present a method of generating all the coset represen-tatives, which runs in time Õ(q3), thus achieves the optimal time com-plexity up to a constant factor. Our algorithm has applications in solving discrete logarithms and finding primitive elements in finite fields of small characteristic.