我试图从 this (old) implementation on github 了解 Shamir 的 secret 共享计划的实现,我在扩展字段 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
先出现,然后才出现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]);
}
最佳答案
用正常的加法和乘法符号翻译这个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
。在有限域上,这通常使用对数表和反对数表来完成,因此您最好避免这种无用的乘法,特别是如果您要经常计算多项式。
TL;DR:这种编写 Horner 算法的方法将最后一次加法和第一次乘法放在循环体之外。因为最高阶系数是 1
,所以这个乘法被完全删除。
澄清一下:保留了最高阶项,但它是 x^n
而不是 1 * x^n
。您为完全相同的结果节省了一次乘法。
关于c - 我无法理解这个 Horner 规则在扩展字段 GF(p^n) 中的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35753405/