Hello, Codeforces!

For the convenience of hacking codes that incorrectly use rolling hashes (i.e., using fixed modulos and bases), I wrote a tool in Rust, which runs entirely on the frontend and requires WebAssembly support.

Try it here and feel free to create issues.

Explanation of parameters:

• length: the length of generated strings;
• $$$\lambda$$$ (lambda)：detail follows;
• $$$\delta$$$ (delta) and $$$\eta$$$ (eta) : parameters of $$$L^2$$$ algorithm;
• precision: floating-point precision in decimal.

Given the modulos $$$\lbrace p_i\rbrace_{i=0}^{n-1}$$$ and the bases $$$\lbrace q_i\rbrace_{i=0}^{n-1}$$$, define $$$h_i(a)=\Big(\sum\limits_{j=0}^{\text{length}-1} q_i^js_j\Big)\bmod p_i$$$, where $$$a$$$ is a string of $$$\text{length}$$$. We want to find two strings $$$a$$$ and $$$b$$$ of $$$\text{length}$$$ such that $$$h_i(a)=h_i(b)$$$ for every $$$i$$$.

If we find a integer array $$$d$$$ of $$$\text{length}$$$ satisfying that $$$h_i(d)=0$$$ for every $$$i$$$, $$$|d_j|<26$$$ for every $$$j$$$, and $$$d_j\ne 0$$$ for some $$$j$$$, we can easily construct $$$a$$$ and $$$b$$$ from $$$d$$$.

Construct a matrix $$$M$$$ of size $$$(n+\text{length})\times(n+\text{length})$$$:

where

• $$$Q$$$ is a matrix of size $$$\text{length} \times n $$$, where $$$Q_{ji}=q_i^j\bmod p_i$$$;
• $$$I$$$ is an identity matrix of size $$$(\text{length} \times \text{length})$$$;
• $$$P$$$ is a diagonal matrix of size $$$n\times n$$$, where $$$P_{ii}=p_i$$$,
• $$$0$$$ is a zero matrix of size $$$n\times \text{length}$$$.

We can find that the matrix $$$M$$$ has the following properties:

• For every row $$$R$$$ of $$$M$$$, that $$$h_i(R[n\cdots n+\text{length}])\equiv R[i] \pmod{p_i}$$$ holds for every $$$i$$$,
• $$$M$$$ is full rank.

Define the following operation:

• $$$R_i\leftarrow R_i-R_j\times k$$$, where $$$k\in \mathbb Z$$$.

We can find that this operation does not affect the properties of the matrix.

If after operations, there exists a row $$$R$$$ satisfying that $$$R[i]=0$$$ for every $$$i<n$$$ and $$$|R[i]|<26$$$ for every $$$i\ge n$$$, we can find a solution $$$d=R[n\cdots n+\text{length}]$$$.

Intuitively, we should find the "shortest" row $$$R^*$$$. To make it more likey that $$$R^*[i]=0$$$ for every $$$i<n$$$, multiply the first $$$n$$$ columns by a big integer $$$\lambda$$$, i.e.,

This is well known as Shortest Vector Problem (SVP). Here, we use the $$$L^2$$$ algorithm to reduce $$$M$$$. More details about $$$L^2$$$ algorithm can be found in the paper mentioned below.

References:

• On the mathematics behind rolling hashes and anti-hash tests
• An LLL Algorithm with Quadratic Complexity