Classifying and generating exact coset representatives of PGL2(Fq)PGL2(Fq) in PGL2(Fq2)PGL2(Fq2)

Generating coset representatives of PGL2(Fq)PGL2(Fq) in PGL2(Fq2)PGL2(Fq2) 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 PGL2(Fq)PGL2(Fq) in PGL2(Fq2)PGL2(Fq2). Based on the classification, we design a deterministic algorithm that generates the exact coset representatives of PGL2(Fq)PGL2(Fq) in PGL2(Fq2)PGL2(Fq2) with O(q3)O(q3) field operations.