Rolling hash hacking

Question

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).

Answer 1

Running birthday attack should be faster than writing the question: sqrt(1e12) = 1e6

Also note that your question have nothing with rolling hashes, moreover, with rolling hash len(s) is fixed. So it may be that you missed some condtitions from the original question.

Answer 2

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.