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 groupCosetsDiscrete logarithmPrimitive 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2015/764}},
      url = {https://eprint.iacr.org/2015/764}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.