K-wise Independent Hash Sample

Problem

Evaluate a k-wise independent polynomial hash over a finite field on each input.

Coefficients a_0 through a_{degree-1} are drawn uniformly from 0 to prime-1 with random.Random(seed), and h(x) is their polynomial evaluated modulo prime. Return the list of hash values for inputs, which is empty for an empty input list.

Hint

A degree-(k-1) polynomial over a field gives k-wise independence, with coefficients as the secret.

Test cases

case 1

in: [97,3,5,[0,1,2,5,10]]

expected: [79,11,34,67,2]

case 2

in: [101,1,7,[3,4,5]]

expected: [41,41,41]

case 3

in: [97,2,0,[]]

expected: []

case 4

in: [97,4,42,[1]]

expected: [95]

Starter codePython

import random


def kwise_hash_sample(prime, degree, seed, inputs):
    # Your code here
    pass

4 test cases · run your code against them in the editor