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

Jincheng Zhuang; Qi Cheng

Paper 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.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Projective linear group Cosets Discrete logarithm Primitive elements
Contact author(s): zhuangjincheng @ iie ac cn
qcheng @ ou edu
History: 2015-08-08: revised; 2015-07-31: received; See all versions
Short URL: https://ia.cr/2015/764
License: CC BY

BibTeX

@misc{cryptoeprint:2015/764,
      author = {Jincheng Zhuang and Qi Cheng},
      title = {On Generating Coset Representatives of {PGL_2}(\F_q) in {PGL_2}(\F_{q^2})},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/764},
      year = {2015},
      url = {https://eprint.iacr.org/2015/764}
}