# Rolling hash hacking

The hash value of a string $$s$$ is given by

$$h(s) = \sum^{|s|}_{i = 1} s_i \cdot p^{|s| - i} \mod m; \text{ m is prime, m < 10^{12}}.$$

The string $$s$$, $$p$$, $$m$$ is given, $$|s| \le 14$$, alphabet size $$= 62$$ (letters and digits).

I need to find a string $$s^{\prime}$$:

$$s^{\prime} \neq s$$, but $$h(s^{\prime}) = h(s)$$

$$s^{\prime}$$ must meet the same requirements as $$s$$. The answer is always exist.

I know about Birthday-attack, but $$m$$ is too large and if I generate random strings, probability of collision is too small. Simple brute-force is also not suitable, because the string may be too long (14 characters).

Hint: Write out the condition for $$h(s)=h(s')$$, expressed in terms of the variables $$s_1,\dots,s_{14},s'_1,\dots,s'_{14}$$. Use linear algebra.