在模算术中评估多项式

Question

我需要重复计算

形式的多项式

f(x)=c(0)+c(1)*x+...+c(k-1)*x^(k-1) mod p

其中k是整数，p是大质数，c(0),...,c(p)在1和p之间。对于我的应用，k=10，p应该大于1000。

我希望在 Python 内尽快完成此操作。我对 Python 中的 modulo 算术知之甚少，无法有效地实现这一点（例如，如何利用我们可以使用梅森素数 p=2^q-1 在这种情况下应该使用该乘法是寄存器移位，通过将不同数量级的整数相加来避免麻烦，...)。

动机：k 独立散列，参见 https://en.wikipedia.org/wiki/K-independent_hashing。这似乎是一个非常受欢迎的学术主题，但我找不到 k>2 的任何实现。

Answer 1

通常，您可以使用以下构造计算多项式的值：

def value(poly, x):
  """Evaluates a polynomial POLY for a given x.

  The polynomial is expressed as a list of coefficients, with 
  the coefficient for x ** N at poly[N].

  This means that x ** 2 + 2*x + 3 is expressed as [3, 2, 1].
  """
  v = 0

  # Bit messy, but we're basically generating the indexes of 
  # our polynomial coefficients from highest to lowest
  for coeff in reverse(poly):
    v = v * x + coeff

  return v

为了评估这个模 a 值，我们可以简单地将内部循环更改为 v = v * x + poly[ix] % p（并将我们的模作为参数 p 传递）。

我们可以通过展开循环来证明示例多项式 (x^2 + 2x + 3) 的计算是正确的，并且可以看到我们得到的是 (((1) * x + 2) * x + 3)（每个括号级别是循环中的一次迭代), 这可以简化为 1 * x * x + 2 * x + 3，这显然是预期的多项式。

通过使用它，我们永远不会得到大于 p * x 的中间值。

在模算术中评估多项式

Evaluating polynomials in modulo arithmetic

python

hash

modulo

polynomials