Classifying and generating exact coset representatives of PGL 2 ( F q ) in PGL 2 ( F q 2 )

Generating coset representatives of PGL 2 ( F q ) in PGL 2 ( F q 2 ) is a key ingredient in certain algorithms of determining primitive elements and computing discrete logarithms in finite fields of small characteristic. In this paper, we describe a simple classification of the right cosets of PGL 2 ( F q ) in PGL 2 ( F q 2 ) . Based on the classification, we design a deterministic algorithm that generates the exact coset representatives of PGL 2 ( F q ) in PGL 2 ( F q 2 ) with O ( q 3 ) field operations.