Classifying and generating exact coset representatives of in

详细信息    查看全文

• 作者：Yuqing Zhu^a ; ^b ; ^{zhuyuqing@iie.ac.cn" class="auth_mail" title="E-mail the corresponding author} ; Jincheng Zhuang^a ; ^c ; ^{zhuangjincheng@iie.ac.cn" class="auth_mail" title="E-mail the corresponding author} ; Chang Lv^a ; ^{lvchang@iie.ac.cn" class="auth_mail" title="E-mail the corresponding author} ; Dongdai Lin^a ; ^{ddlin@iie.ac.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：11Y16 ; 15A33
• 刊名：Finite Fields and Their Applications
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：42
• 期：Complete
• 页码：118-127
• 全文大小：296 K

文摘

Generating coset representatives of 071579716300491&_mathId=si1.gif&_user=111111111&_pii=S1071579716300491&_rdoc=1&_issn=10715797&md5=e0c12b3e7c5d5e0535d732f5aac1c453" title="Click to view the MathML source">PGL₂(F_q)${\mathrm{PGL}}_2({\mathbb{F}}_q)$ in 071579716300491&_mathId=si135.gif&_user=111111111&_pii=S1071579716300491&_rdoc=1&_issn=10715797&md5=d4d9b936fbba89f5edd16a25ae39248c" title="Click to view the MathML source">PGL₂(F_q²)${\mathrm{PGL}}_2({\mathbb{F}}_{q^2})$ 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 071579716300491&_mathId=si1.gif&_user=111111111&_pii=S1071579716300491&_rdoc=1&_issn=10715797&md5=e0c12b3e7c5d5e0535d732f5aac1c453" title="Click to view the MathML source">PGL₂(F_q)${\mathrm{PGL}}_2({\mathbb{F}}_q)$ in 071579716300491&_mathId=si135.gif&_user=111111111&_pii=S1071579716300491&_rdoc=1&_issn=10715797&md5=d4d9b936fbba89f5edd16a25ae39248c" title="Click to view the MathML source">PGL₂(F_q²)${\mathrm{PGL}}_2({\mathbb{F}}_{q^2})$. Based on the classification, we design a deterministic algorithm that generates the exact coset representatives of 071579716300491&_mathId=si1.gif&_user=111111111&_pii=S1071579716300491&_rdoc=1&_issn=10715797&md5=e0c12b3e7c5d5e0535d732f5aac1c453" title="Click to view the MathML source">PGL₂(F_q)${\mathrm{PGL}}_2({\mathbb{F}}_q)$ in 071579716300491&_mathId=si135.gif&_user=111111111&_pii=S1071579716300491&_rdoc=1&_issn=10715797&md5=d4d9b936fbba89f5edd16a25ae39248c" title="Click to view the MathML source">PGL₂(F_q²)${\mathrm{PGL}}_2({\mathbb{F}}_{q^2})$ with 071579716300491&_mathId=si4.gif&_user=111111111&_pii=S1071579716300491&_rdoc=1&_issn=10715797&md5=3ab984761678a623bd1a9b6eb1156654" title="Click to view the MathML source">O(q³)$O(q^3)$ field operations.