Cryptology ePrint Archive: Report 2015/764

On Generating Coset Representatives of PGL_2(\F_q) in PGL_2(\F_{q^2})

Jincheng Zhuang and Qi Cheng

Abstract: 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 \tilde{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.

Category / Keywords: Projective linear group, Cosets, Discrete logarithm, Primitive elements

Date: received 30 Jul 2015, last revised 7 Aug 2015

Contact author: zhuangjincheng at iie ac cn;qcheng@ou edu

Available format(s): PDF | BibTeX Citation

Version: 20150808:020418 (All versions of this report)

Short URL: ia.cr/2015/764

Discussion forum: Show discussion | Start new discussion