On Generating Coset Representatives of $$PGL_{2}\mathbb {F}_{q}$$PGL2Fq in $$PGL_{2}\mathbb {F}_{q^{2}}$$PGL2Fq2

There are $$ q^3 + q $$q3+q right $$ PGL_{2}{\mathbb F}_{q}-$$PGL2Fq-cosets in the group $$ PGL_{2}{\mathbb F}_{q^2} $$PGL2Fq2. In this paper, we present a method of generating all the coset representatives, which runs in time $$ \tilde{O}q^3 $$O~q3, thus achieves the optimal time complexity upi¾?to a constant factor. Our algorithm has applications in solving discrete logarithms and finding primitive elements in finite fields of small characteristic.