Given a hash function how to find all/some inputs that hash to 0? [duplicate]

Question

Say I have a simple hash function where $x$ is a sequence of integers:

$$h(x)=(a_1\cdot x_1+...+ a_n\cdot x_n) \bmod N=\sum_i a_i\cdot x_i \bmod N$$

where $a_1,a_2,a_3,...,a_n$ is the coefficient known.

n can be any number less than 256.

How to find 2 different inputs that hashes to 0 in particular?

I guess I understand how to make them hash to some random hash, but hash to a particular value, 0, seems like I need to solve linear equation?

and the complexity would be exponential in terms of the size of the ouput sequence?

Answer 1

Select $x=(x_1,...,x_{n-1})$ at random and then compute:

$$x_n=({a_n}^{-1}\cdot(0-\sum_{i=1}^{n-1}a_i\cdot x_i)) \bmod N$$

Now, select $x'=(x_1',...,x_{n-2}',x_n')$ at random and then compute:

$$x_{n-1}'=({a_{n-1}}^{-1}\cdot(0-a_n\cdot x_n'-\sum_{i=1}^{n-2}a_i\cdot x_i')) \bmod N$$

Now we have $h(x)=h(x')=0$.

• Note that this question was a special case ($k=0$) of your question at here