I was reading this post https://senderek.com/SDLH/ about Shamir's hash function, which is defined as follows:
Let $p,q$ be positive prime integers and let $n=p\times q$. Let $\ell = \mathrm{lcm}(p-1, q-1)$. Find $g \in (\mathbb{Z}/n\mathbb{Z})^*$ such that $\ell$ is the smallest positive integer for which $g^\ell \equiv 1 \bmod n$, i.e., $\ell$ is the order of $g$ in $(\mathbb{Z}/n\mathbb{Z})^*$.
Set $H(m) = g^m \bmod n$ to be the hash function and discard $p$ and $q$.
Assuming that an adversary is able to find $m_1, m_2 \in \mathbb{Z}$ such that $m_1\neq m_2$ and $H(m_1) = H(m_2)$, this would mean that $g^{m_1} \equiv g^{m_2} \bmod n \implies g^{m_1-m_2}\equiv 1\bmod n$. From group theory, since $\ell$ is the order of $g$ in $(\mathbb{Z}/n\mathbb{Z})^*$, it follows that $m_1-m_2$ is multiple of $\ell$.
The post referenced earlier said that given a multiple of $\ell$, it is easy to factor $n$. However, I am struggling to figure out why it is the case.
My current intuition is that if we let $r$ be a multiple of $\ell$, one can recover $p-1$ and $q-1$ by enumerating all the divisors of $r$, and then by adding 1 to all those divisors, we can recover $p$ and $q$, and finally test which of those divisors are actually $p$ and $q$ by checking if they divide $n$. However, for large $p$ and $q$, this approach might still be tedious. Hence, is there a better way?
