给定一个除数序列\(M = \{ m_i | m_i \in N^* 且 m_i > 1, i \in N^*\}\),按照如下方式对整数值求得一个哈希结果序列\( R = \{ r_i | r_i \in N, i \in N^* \}\)。现在需要根据这个结果序列\(R\)和除数数列\(M\)求原值。
1 商数类哈希函数
根据哈希函数的结果序列\(R\),可以得到一个整数数值\(k^*\):
\[ k^* = (……(q_i \times m_i + r_i) \times m_{i-1} + ……+ r_2) \times m_1 + r_1 \quad (q_i = 0,\, 0 \le r_i \le m_i)\]
该值即为原始值。
2 余数类哈希函数
如果知道了除数序列和余数类哈希函数的结果,那么如何求解满足这样的数?设整数\(k\)满足上述条件,那么由题设可以得到:
\[ k = m_1 k_1 + r_1 = m_2 k_2 + r_2 = …… = m_n k_n + r_n \]
可设:
\[ t = \sum \limits_{i=1}^ n k_i = \frac{k-r_1}{m_1}+\frac{k-r_2}{m_2} + …… + \frac{k-r_n}{m_n} \]
可得:
\[ k \cdot \sum \limits_{i=1}^n \frac{1}{m_i} = t + \sum \limits_{i=1}^n \frac{r_i}{m_i} \quad (k_i \in N, t \in N)\]
由于\(k, t \)相互独立,可令\(k=t\)。其实就相当于求解两条直线\(y=x \cdot \sum \limits_{i=1} ^ n \frac{1}{m_i}\)和\(y=x+\sum \limits_{i=1}^n \frac{r_i}{m_i} \)的交点。
由于两条直线的斜率不一样,所以必存在一个交点。把求得的该特解记为\(B_M(R)\)。满足这样条件的通解\(k=B_M(R) + c \cdot D \quad (c \in N)\)。
例如:对于指定的除数数列\(M=\{2,3,5\}\)和余数数列\(R=\{1,2,3\}\),则\(B_M(R)=53\)。通解则为:\(k=53 + 30c\)。