关于使用多项式$f(x)=x^2$的Pollard’s rho方法中等价性命题的证明问询

嘿，我来帮你理清这个Pollard’s rho变体里的等价性证明问题。先明确下已知条件：我们要分解$n>1$，改用$f(x)=x^2$生成序列$a_1,a_2,\dots$，其中$a_1$是${0,1,\dots,n-1}$中与$n$互质的随机数，$a_i = a_{i-1}^2 \pmod{n}$（$i\geq2$）；$p$是$n$的素因子，$k$是$a_1$模$p$的乘法阶。我们要证明：当$j<i$时，$a_i ≡a_j \pmod{p}$ $\iff$ $2^{i−1} ≡2^{j−1} \pmod{k}$。

关键前置结论：序列模p的指数形式 #

首先我们可以用归纳法得出序列$a_i$模$p$的表达式：

• 基例：$i=1$时，$a_1 ≡ a_1^{2{0}} \pmod{p}$，显然成立；
• 归纳假设：假设$i=m$时，$a_m ≡ a_1^{2{m-1}} \pmod{p}$；
• 归纳步骤：$i=m+1$时，$a_{m+1} = a_m^2 ≡ (a_1^{2{m-1}})^2 = a_1^{2{m}} \pmod{p}$，成立。

所以对任意$i\geq1$，都有$a_i ≡ a_1^{2{i-1}} \pmod{p}$，这是整个证明的核心突破口。

正向推导：$a_i ≡a_j \pmod{p} \implies 2^{i−1} ≡2^{j−1} \pmod{k}$ #

已知$a_i ≡a_j \pmod{p}$，代入上面的指数形式可得：
$$a_1^{2{i-1}} ≡ a_1^{2{j-1}} \pmod{p}$$
因为$a_1$与$n$互质，$p$是$n$的素因子，所以$\gcd(a_1,p)=1$，$a_1$在模$p$的乘法群中有逆元。两边同时乘以$a_1^{2{j-1}}$的逆元，得到：
$$a_1^{2{i-1} - 2^{j-1}} ≡ 1 \pmod{p}$$
根据乘法阶的定义：$k$是满足$a_1^k ≡1 \pmod{p}$的最小正整数，且所有使得$a_1^t ≡1 \pmod{p}$的整数$t$都能被$k$整除。因此$k$整除$2^{i-1} - 2^{j-1}$，即：
$$2^{i−1} ≡2^{j−1} \pmod{k}$$

反向推导：$2^{i−1} ≡2^{j−1} \pmod{k} \implies a_i ≡a_j \pmod{p}$ #

已知$2^{i−1} ≡2^{j−1} \pmod{k}$，即存在整数$m$，使得：
$$2^{i-1} - 2^{j-1} = mk$$
将其代入$a_i$的指数形式：
$$a_1^{2{i-1}} = a_1^{2{j-1} + mk} = a_1^{2{j-1}} \cdot (a_1^k)m$$
根据乘法阶的定义，$a_1^k ≡1 \pmod{p}$，所以$(a_1^k)m ≡1^m = 1 \pmod{p}$，因此：
$$a_1^{2{i-1}} ≡ a_1^{2{j-1}} \pmod{p}$$
也就是$a_i ≡a_j \pmod{p}$。

对你之前尝试的补充说明 #

你之前尝试用差的因式分解来推导，其实绕了弯路——因为迭代平方的序列本质是指数不断翻倍，直接用指数形式结合乘法阶的定义是最直接的路径，不用去展开平方差哦。

备注：内容来源于stack exchange，提问作者Mzq