Efficient Computation of Roots in Finite Fields |
| |
| Authors: | Paulo S. L. M. Barreto José Felipe Voloch |
| |
| Affiliation: | 1. Laboratório de Arquitetura e Redes de Computadores (LARC), Escola Politécnica, Universidade de S?o Paulo, Brazil
2. Department of Mathematics, University of Texas, Austin, TX, 78712, USA
|
| |
| Abstract: | We present an algorithm to compute rth roots in $mathbb{F}_{q^m}We present an algorithm to compute rth roots in  with complexity ?[(log m + r log q) m log q] if (m,q) = 1 and either (q(q−1),r) = 1 or r|(q−1) and ((q−1)/r,r) = 1. This compares well to previously known algorithms, which need O(r m3 log3 q) steps. Paulo S. L. M. Barreto: Supported by Scopus Tecnologia S. A. José Felipe Voloch: Supported by NSA grant MDA904-03-1-0117. |
| |
| Keywords: | finite fields root computation efficient algorithms |
| 本文献已被 SpringerLink 等数据库收录！ |
|
