2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.