已知Math.imul()运算结果，如何求解其中一个输入参数x？

求解步骤 #

1. 理解Math.imul的运算本质

Math.imul(x, y)是JavaScript的32位有符号整数乘法，等价于取x*y的低32位再转为有符号整数，即：

(x * y) & 0xFFFFFFFF

题目中的等式可转化为模2^32的同余方程：
$$x \times 2654435761 \equiv 1447829970 \pmod{2^{32}}$$

2. 确认乘法逆元存在

2654435761（十六进制0x9E3779B9）是奇数，与2^{32互质（最大公约数为1），因此它在模2}32下存在乘法逆元inv——满足：
$$2654435761 \times inv \equiv 1 \pmod{2^{32}}$$

3. 计算乘法逆元

通过扩展欧几里得算法可求得，2654435761的模2^32逆元为244002641（验证：Math.imul(2654435761, 244002641)结果为1）。

4. 求解x

将同余方程两边同时乘以逆元inv，得到：
$$x \equiv 1447829970 \times 244002641 \pmod{2^{32}}$$

直接用Math.imul计算该乘积的低32位：

const x = Math.imul(1447829970, 244002641);

5. 验证结果

代入原等式验证：

console.log(Math.imul(x, 2654435761)); // 输出1447829970，符合要求

最终满足条件的一个x值 #

十进制：1080503378，十六进制：0x40CA2C52

内容的提问来源于stack exchange，提问作者3jay1