如何在PHP中逆向求解模运算：还原原始乘数-php教程-PHP中文网

如何在PHP中逆向求解模运算：还原原始乘数

本文介绍如何通过暴力枚举法逆向求解形如 $result = ($number * $factor) % $mod 的模运算，还原满足条件的最小正整数 $number，适用于因子与模数互质但无显式模逆元需求的实用场景。

本文介绍如何通过暴力枚举法逆向求解形如 `$result = ($number * $factor) % $mod` 的模运算，还原满足条件的最小正整数 `$number`，适用于因子与模数互质但无显式模逆元需求的实用场景。

在密码学、序列生成或哈希简化等场景中，我们常遇到类似 ($number × 683567) % 1000000 的线性同余变换。该运算不可逆（因模运算丢失高位信息），但若仅需最小正整数解（即满足同余方程的最小 $x$），且已知乘数 683567 与模数 1000000 互质（gcd(683567, 1000000) = 1，经验证成立），则可通过两种方式求解：数学法（扩展欧几里得算法求模逆元） 或 工程法（增量迭代匹配）。本文聚焦后者——简洁、鲁棒、无需额外依赖的实用方案。

核心思路是：由于结果仅取决于 ($number × 683567) % 1000000，而 number 每增加 1，中间积就增加 683567。因此可从 i = 1 开始累加 683567，每次检查 (i × 683567) % 1000000 是否等于目标值，直至匹配。

以下是优化后的 PHP 实现：

PHP

编写健壮的PHP代码，规避类型转换陷阱、数组怪癖及常见安全漏洞。

下载

function un_mod($result, $factor = 683567, $mod = 1000000) {
    // 输入校验：确保 result 在合法范围内
    if (!is_int($result) || $result = $mod) {
        throw new InvalidArgumentException("Result must be an integer in [0, {$mod}).");
    }

    $total = $factor;
    $i = 1;
    // 最多尝试 mod 次（根据鸽巢原理，必在 mod 步内循环，有解则必出现）
    $max_attempts = $mod;

    while ($i <p>⚠️ <strong>重要注意事项</strong>：  </p>

该函数返回的是满足同余关系的最小正整数解，不一定是原始输入（例如若原始 number = 1000001，其结果与 number = 1 完全相同）。这是模运算固有的多对一特性决定的，无法规避。
时间复杂度为 $O(\text{mod})$，在 mod = 10^6 时最多循环 100 万次，实际通常远少于该值（本例中最大解为 999999，但平均约 50 万次），性能可接受；若 mod 达到 $10^9$ 级别，应改用扩展欧几里得算法求模逆元。
函数内置了输入合法性检查与循环上限保护，避免无限循环，增强健壮性。

总结：当面对简单线性模运算逆向需求且模数适中时，增量匹配法是最直观、易维护、零依赖的解决方案。它牺牲了理论最优性，换取了代码清晰度与部署简易性，是典型“够用就好”的工程实践范例。