c - 我无法理解扩展字段GF(p ^ n)中的Horner规则实现

我试图从this (old) implementation on github中理解Shamir的秘密共享方案的实现，并且我在扩展域GF（p^n）中与Horner规则作斗争：

void horner(int n, mpz_t y, const mpz_t x, const mpz_t coeff[])
{
  int i;
  mpz_set(y, x);
  for(i = n - 1; i; i--) {
    field_add(y, y, coeff[i]);
    field_mult(y, y, x);
  }
  field_add(y, y, coeff[0]);
}

为什么add先到后到算法是什么？为什么不说：

  mpz_set(y,coeff[n-1]);
  for(i = n - 2; i!=-1; i--) {
    field_mult(y, y, x);
    field_add(y,y,coeff[i]);
  }

最佳答案

用正常的加法和乘法符号转换这个函数，我们得到：

y = x;                     // mpz_set(y, x);
for(i = n - 1; i; i--) {
    y = y + coeff[i];      // field_add(y, y, coeff[i]);
    y = y * x              // field_mult(y, y, x);
}
y = y + coeff[0]           // field_add(y, y, coeff[0]);

因此，计算如下：

你可以看到它不计算任何多项式，但它是霍纳计算amonic polynomial的算法的变体。
现在你的建议是：

y = coeff[n-1];               // mpz_set(y,coeff[n-1]);
for(i = n - 2; i!=-1; i--) {
    y = y * x;                // field_mult(y, y, x);
    y = y + coeff[i];         // field_add(y,y,coeff[i]);
}

因此，计算如下：

你可以看到最高阶的词不见了。
如果你想让所有的操作都在循环体中，你可以。
毕竟，分解一系列交替指令的方式只有两种：

operation    value of y                                    loop iteration
                                                 add-mult loop      mult-add loop
                x                               initialization         n-1
add       x + coeff[n-1]                             n-1               n-1
mult     (x + coeff[n-1]) * x                        n-1               n-2
add      (x + coeff[n-1]) * x + coeff[n-2]           n-2               n-2
mult    ((x + coeff[n-1]) * x + coeff[n-2]) * x      n-2               n-3
          ...etc...

但是您需要显式地将horner初始化为值y（这是隐式的1），这样您就可以从乘以coeff[n]开始，得到正确的最高阶项。

y = 1;                        // mpz_set(y,1);
for(i = n - 1; i!=-1; i--) {  // NOTICE n - 1 NOT n - 2
    y = y * x;                // field_mult(y, y, x);
    y = y + coeff[i];         // field_add(y,y,coeff[i]);
}

你可以计算出你现在又执行了一个乘法运算，它正在乘法运算。在有限域上，这通常是用对数表和反对数表来完成的，所以您最好避免这种无用的乘法运算，特别是如果您要经常计算多项式。
博士：这种编写霍纳算法的方法把最后一个加法和第一个乘法放在循环体之外。因为最高阶系数x这个乘法就被完全去掉了。
澄清：保留最高阶项，但随后是1 * x而不是1。你省去了一次乘法运算得到完全相同的结果。