$n = p \mathrm{\;mod\;} n$递推次数的上界？

原问题

这个问题我最开始是从知乎¹上看到的，里面提到了一种求逆元的方法，但是现在暂时没有方法能证明其复杂度。

众所周知，当我们选取一个质数$p$作为模数时，$1..n$的每个数都存在一个模$p$意义下的逆元。如何求出这些逆元呢？最简单粗暴的方法就是使用单个数求逆元的方法对$1..n$都用一遍。自然这种方法现在无法做到线性复杂度。但是我们有一种直接递推的办法来求出$1..n$的所有逆元。具体的，我们先考虑下$n$和$r = p \mathrm{\;mod\;} n$的关系。
首先，根据余数的定义，我们有：
$$ r = p - \left\lfloor \frac{p}n \right\rfloor n $$

将其放在模$p$意义下：
$$ r \equiv -\left\lfloor \frac{p}n \right\rfloor n \pmod{p} $$

如果$r^{-1}$和$n^{-1}$都存在（如果$p$是质数则显然成立），那么上式可以变为：
$$ n^{-1} \equiv -\left\lfloor \frac{p}n \right\rfloor r^{-1} \pmod{p} $$

又因为我们知道$1^{-1} = 1$并且$r < n$，所以我们可以以$1..n$的顺序递推出所有的逆元，时空复杂度均为$\Theta(n)$。

如果直接使用递推式来计算逆元，也就变成了下面的算法：

1
2
3
4

function INVERSE(n, p):
    if n == 1:
        return 1
    return -(p / n) * INVERSE(p % n, p)

需要注意一点，以上方法在$p$不是质数的时候很多情况下是无法使用的，即便$n$和$p$互质。一个反例就是当$n = 3$并且$p = 8$的时候。

算法复杂度

该算法的递归次数实际上就是$n = p \mathrm{\;mod\;} n$这个递推式要达到$n \leqslant 1$的次数，所以下面的分析都按照这个来。

实验数据

这个算法似乎并不能直接从表面上简单地看出它的迭代次数。通过对一个著名的质数$p = 10^9 + 7$做了一些测试后，得到了一些数据。

随机$10^6$个数来计算逆元的平均递归次数是$21.9734742$次。
强行计算出$1..p - 1$中每个数的递归次数，得到以下数据：

可以看出似乎递归次数$ \leqslant 2\log n$？尝试了其它的一些质数发现也满足这个上界。但是我并不会证明。如果有知道证明方法或者相关资料的可以与我联系，或者直接去回答知乎上的那个问题。

对于百度出来的一些答案，都是直接默认它每次$n \mathrm{\;mod\;} p$都会减半。但是实际上并非如此。如果真的达到了每次操作完$n$都会减半，那么上面的数据中也就不会出现$50$次的情况。并且就以上面最大的数字$642493787$为例，它的迭代过程中出现了这样的东西：

1
2
3
4
5
6
7

...
188
183
167
166
71
...

当$n = 188$并且$p = 10^9 + 7$时，经过$3$次迭代才使得$n$的规模减半。

根号上界

根据知乎上@徐老丝的回答，我们有一个证明其递归次数$\leqslant 2\sqrt{p}$的方法。

首先需要确定一个基本定理：

如果满足$\frac1m p \lt n \leqslant \frac1{m-1} p$，那么$p \mathrm{\;mod\;} n \lt \frac1m p$。

证明 证明过程比较简单，只用确认$p - (m - 1)n$的范围即可：
$$ p - \frac1m p \lt (m - 1)n \leqslant p \\ \frac1m p \gt p - (m - 1)n \geqslant 0 $$

由于$n \gt \frac1m p$，所以$p \mathrm{\;mod\;} n = p - (m - 1)n \lt \frac1m p$。

根据以上定理，我们可以得到，如果一开始$\frac1m p \lt n \leqslant \frac1{m-1} p$，那么经过$\sqrt{p}$次迭代后，就有$n \lt \frac1{m + \sqrt{p}} p$。所以对于任意的$1 \leqslant n \lt p$，经过$\sqrt{p}$次迭代后都有$n \lt \frac1{\sqrt{p}} p = \sqrt{p}$。由于每次取模$n$至少减$1$，所以之后最多$\sqrt{p}$步使得$n \leqslant 1$。所以该算法的一个上界是$2\sqrt{p}$的。

期望次数分析

我自己思考了一种思路，似乎可以提供一种为什么该算法的递归次数非常少的解释。

首先注意到对于任意的$0 \lt n \lt p$，设$r = p \mathrm{\;mod\;} n$，那么有$n \mid (p - r)$。
同时，对于任意的$0 \leqslant r \lt p$，所有满足$p \mathrm{\;mod\;} n = r$的$n$是$p - r$中所有大于$r$的因子。
更进一步，我们比较关注那种$r \leqslant n / 2$的$n$，从$r$的角度而言，这样的$n$都是$p - r$的大于等于$2r$的因子。

现在用一张图来划分这两种$n$：

上图是$p = 11$时的情况。图上的每一个黑点$(x,y)$表示$y \mid x$。这样每一个横坐标上方的点的纵坐标就是它的因子。图中并没有画出$1$的所有倍数。红色的直线是$y = 11 - x$，蓝色的直线是$y = 2 \times 11 - 2x$。此时红色直线和蓝色直线之间所夹的一片绿色区域（不包含蓝色直线和红色直线）中的点的纵坐标$n$满足$p \mathrm{\;mod\;} n > n / 2$，而剩余的黄色区域（包括蓝色直线）中的点的纵坐标$n$则满足$p \mathrm{\;mod\;} n \leqslant n / 2$。
从一个给定的$n$开始迭代，每次只能向下走到另外一个纵坐标。如果走到了黄色区域，那么此时$n$的规模减半。注意到对于固定的$n$，纵坐标为$n$的点之间的间距是相同的，而红线和蓝线之间的距离和蓝线到直线$y = p$的距离也是相同的。那么$p$随机的情况下，$p \mathrm{\;mod\;} n \leqslant n / 2$的概率可以近似为$1/2$。意思是在$n$和$p$都随机的情况下，期望$\sum_{k = 1}^\infty k/2^k = 2$步就可以使$n$规模减半。如果不那么严谨的话，可以认为期望步数是$O(\log n)$的。