CODEWITHSUNDEEP
pythonhashmodulopolynomials
fact
fact

Reputation: 557

Evaluating polynomials in modulo arithmetic

I need to repeatedly evaluate a polynomial of the form

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

where k is an integer, p is a large prime number and c(0),...,c(p) are between 1 and p. For my applications, k=10, p should be greater than 1000.

I would prefer to do this in Python and as fast as possible. I don't know enough about modulo arithmetic in Python to implement this efficiently (e.g. how to exploit that we can use Mersenne primes p=2^q-1 in which case about should use that multiplication is a register shift, avoid trouble by adding integers over different orders of magnitude,...).

Motivation: k-independent hashing, see https://en.wikipedia.org/wiki/K-independent_hashing. This seems to a very popular academic subject but I was not able to find any implementations for k>2.

Upvotes: 0

Views: 2040

Answers (1)

Vatine
Vatine

Reputation: 21288

In general, you can compute the value of a polynomial using the following construction:

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

To evaluate this modulo a value, we can simply change the inner loop to v = v * x + poly[ix] % p (and pass our modulus as the parameter p).

We can show that the example polynom (x^2 + 2x + 3) is computed correctly by unwinding the loop and see that what we have is (((1) * x + 2) * x + 3) (each parenthesis level is one iteration through the loop), this can be simplified to 1 * x * x + 2 * x + 3, which is clearly the expected polynomial.

By using this, we should never end up with an intermediate value larger than p * x.

Upvotes: 1

Related Questions