Sadly, until today, many people use single $$$\rm{mod} = 10^9+7$$$ or so on for hashing, so why not write how to blow up them easily, with minimized thinking process?
The key idea is simple. Just use Birthday attack.
- Write a function to calculate the hash value
- Write a random generator of string
- When there are $$$k$$$ possible distinct hash values, look up $$$O(\sqrt{k})$$$ random candidates
- Now we get a pair of strings that has exactly the same hash value!
In this method, the only things we should consider are that $$$k$$$ is small enough (around $$$k \le 10^{12}$$$ ), and the number of possible candidates is large enough. We don't need to care about what the hashing function is!
Exercise:
Find two $$$18$$$-digit integers $$$x,y$$$ such that:
- Each digit of $$$x,y$$$ are $$$1,3,5,7,9$$$
- $$$x \equiv y \mod 998244353$$$