We present a method for computing pth roots using a polynomial basis over finite fields mathbb Fq{mathbb F_q} of odd characteristic p, p ≥ 5, by taking advantage of a binomial reduction polynomial. For a finite field extension mathbb Fqm{mathbb F_{q^m}} of mathbb Fq{mathbb F_q} our method requires p − 1 scalar multiplications of elements in mathbb Fqm{mathbb F_{q^m}} by elements in mathbb Fq{mathbb F_q}. In addition, our method requires at most (p-1)ém/p ù{(p-1)lceil m/p rceil} additions in the extension field. In certain cases, these additions are not required. If z is a root of the irreducible reduction polynomial, then the number of terms in the polynomial basis expansion of z 1/p , defined as the Hamming weight of z 1/p or wt(z1/p ){{rm wt}left(z^{1/p} right)}, is directly related to the computational cost of the pth root computation. Using trinomials in characteristic 3, Ahmadi et al. (Discrete Appl Math 155:260–270, 2007) give wt(z1/3 ){{rm wt}left(z^{1/3} right)} is greater than 1 in nearly all cases. Using a binomial reduction polynomial over odd characteristic p, p ≥ 5, we find wt(z1/p) = 1{{rm wt}left(z^{1/p}right) = 1} always.
展开▼
机译：我们提出了一种利用二项式约简多项式对具有奇数特性p，p≥5的有限域mathbb F q {mathbb F_q}使用多项式基础计算pth根的方法。对于有限域扩展mathbb F q {mathbb F_q}的mathbb F q m {mathbb F_ {q ^ m}} p − 1 mathbb F q m {mathbb F_ {q ^ m}}中元素的标量乘以mathbb F q {mathbb F_q}。此外，我们的方法最多需要在扩展字段中添加（p-1）ém/ p {{（p-1）lceil m / p rceil}个加法。在某些情况下，不需要这些添加。如果z是不可约化多项式的根，则z 1 / p 的多项式基础展开中的项数，定义为z 1 / p 或wt（z 1 / p ）{{rm wt} left（z ^ {1 / p} right）}，与第p个根计算的计算成本直接相关。 Ahmadi等人在特征3中使用三项式。 （Discrete Appl Math 155：260–270，2007）给出wt（z 1/3 ）{{rm wt} left（z ^ {1/3} right）}几乎大于1所有情况。在奇数特性p，p≥5上使用二项式多项式，我们发现wt（z 1 / p ）= 1 {{rm wt} left（z ^ {1 / p} right）= 1 }总是。
展开▼
