Formulas for p-th root computations in finite fields of characteristic p using polynomial basis

Abstract

Motivado por algoritmos criptográficos de emparelhamento bilinear, a computação da raiz cúbica em corpos finitos de característica 3 já fora abordada na literatura. Adicionalmente, novos estudos sobre a computação da raiz p-ésima em corpos finitos de característica p, onde p é um número primo, têm surgido. Estas contribuições estão centradas na computação de raízes para corpos de característica fixa ou para polinômios irredutíveis com poucos termos não nulos. Esta dissertação propõe novas famílias de polinômios irredutíveis em ??p, com k termos não nulos onde k = 2 e p = 3, para a computação eficiente da raiz p-ésima em corpos finitos de característica p. Além disso, para o caso onde p = 3, são obtidas novas extensões onde a computação da raiz cúbica é eficiente e polinômios cujo desempenho é ligeiramente melhor em comparação aos resultados da literatura. Palavras-chave: Criptografia, Teoria de Números, Aritmética em Corpos Finitos.<br>

Abstract : Efficient cube root computations in extensions fields of characteristic three have been studied, in part motivated by pairing cryptography implementations. Additionally, recent studies have emerged on the computation of p-th roots of finite fields of characteristic p, where p prime. These contributions have either considered a fixed characteristics for the extension field or irreducible polynomials with few nonzero terms. We provide new families of irreducible polynomials over ??p, taking into account polynomials with k = 2 nonzero terms and p = 3. Moreover, for the particular case p = 3, we slightly improve some previous results and we provide new extensions where efficient cube root computations are possible.