给定大正整数n，求满足m-1≡n mod m的m的高效算法问询

让我们一步步拆解这个问题，先从同余式的等价变形入手，这是找到快速解法的核心：

给定同余条件：
$$m-1 \equiv n \pmod m$$

根据同余的定义，$a \equiv b \pmod m$等价于$m$能整除$(a - b)$。把这里的$a=m-1$、$b=n$代入，可得：
$$m \mid (m-1 - n)$$

化简右边的式子：
$$m-1 - n = m - (n+1)$$
因为$m$必然整除自身，所以$m$必须整除$(n+1)$（如果$m$整除$A$和$B$，则一定整除$A-B$，这里$A=m$，$B=m-(n+1)$，因此$m$整除$B-A=-(n+1)$，即$m \mid n+1$）。

反过来验证：如果$m$是$n+1$的因数（包括正、负因数），那么$n+1 = k \cdot m$（$k$为整数），代入原同余式：
左边$m-1 \equiv -1 \pmod m$，右边$n = k\cdot m -1 \equiv -1 \pmod m$，两边完全相等，满足原条件。

快速计算方法 #

问题最终转化为找出$n+1$的所有整数因数，具体步骤如下：

• 计算$N = n + 1$（由于$n$是极大正整数，$N$同样是极大正整数）
• 对$N$进行质因数分解，得到$N = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$，其中$p_i$为质数，$e_i$为对应指数
• 生成所有正因数：每个正因数可表示为$p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$，其中$0 \leq a_i \leq e_i$
• 对所有正因数取相反数，得到全部负因数

计算复杂度 #

整个流程的核心复杂度集中在极大整数$N$的质因数分解：

• 传统试除法的复杂度为$O(\sqrt{N})$，对于极大$N$完全不可行
• 目前处理大整数分解的高效算法是Pollard's Rho算法，其平均时间复杂度约为$O(N^{1/4})$（基于随机化实现），是当前处理极大整数分解的主流方案
• 生成因数的步骤复杂度极低：假设$N$分解后有$k$个不同质数，因数总数为$(e_1+1)(e_2+1)\dots(e_k+1)$，生成这些因数的时间与总数成正比，远小于分解的时间

如果$N$本身是质数，那么它的因数只有$\pm1$和$\pm N$，这种情况会非常容易处理。

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