我無法理解這樣的Horner的規則實施擴展字段GF（P^N）

Question

我試圖從this (old) implementation on github瞭解Shamir的祕密共享方案的執行情況，以及我與霍納規則掙扎在擴展字段GF （p^N）：

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放在第一位，然後才mult？算法是什麼？爲什麼不一樣的東西：

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

Answer 1

翻譯這個horner功能正常的加法和乘法符號，我們得到：

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]); 

因此，這個計算如下：

你可以看到它不計算任何多項式，但它是計算monic polynomial的Horner算法的變體。

你打算現在什麼：

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... 

但是，你需要明確初始化y的價值1（這是隱含coeff[n]），這樣就可以通過乘以啓動x並獲得正確的最高階的術語。

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]); 
} 

你可以指望你現在再執行一次乘法，它乘以1 * x。在有限域上，這通常是使用log和antilog表完成的，所以你最好避免這種無用的乘法，特別是如果你要評估多項式。

TL; DR：寫霍納算法的這種方式使在最後添加和循環體以外的第一個乘法。因爲最高階係數是1，所以這個乘法被完全刪除。

澄清：保留最高階的術語，但是x^n而不是1 * x^n。對於完全相同的結果，您可以使用一次乘法。