### Sugar_fan's blog

By Sugar_fan, 5 weeks ago,

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})$:

$M=\begin{bmatrix} Q & I\\ P & 0 \end{bmatrix}.$

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

$M=\begin{bmatrix} \lambda Q & I\\ \lambda P & 0 \end{bmatrix}.$

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:

• +328

 » 5 weeks ago, # |   -19 Please delete this and never hack any hash solution again
•  » » 5 weeks ago, # ^ |   +13 Please write suffix array template and never submit hashing solution again
•  » » » 5 weeks ago, # ^ |   0 it cant solve all the problems solvable with hashes
 » 5 weeks ago, # |   +180 New fear unlocked
 » 5 weeks ago, # | ← Rev. 2 →   +43 Orz!It seems that people use the rolling hash formula $\sum_{j = 0}^{n - 1} q^{n - 1 - j} s_j$ more frequently than $\sum_{j = 0}^{n - 1} q^{j} s_j$. Probably it would be better to have an "reverse the result" option.
•  » » 5 weeks ago, # ^ |   +40 Well, it's added.
 » 5 weeks ago, # |   +79 Please no GOD no please. I won't play Genshin any more. Please don't hack my Hash.
 » 5 weeks ago, # |   +38 the hero we do not deserve
 » 5 weeks ago, # |   +46