第 8 章：已知私钥怎样随机分解模数

返回目录

8.1 私钥给了我们哪一条额外信息

沿用 $n=pq$ ，其中 $p,q$ 为不同奇质数。原对话的私钥关系给出

$K=ed-1>0,\qquad\varphi(n)\mid K.$

对于任意与 $n$ 互质的 $a$ ，欧拉定理保证 $a^K\equiv1\pmod n$ 。我们知道 $n,e,d$ ，所以能计算 $K$ ；这一步并不要求知道 $p,q$ 。证明中使用 $p,q$ 解释算法，算法本身不能预先使用它们。

把 $K$ 中的全部因子2提出，写成 $K=2^sr$ ，其中 $r$ 为奇数。由于 $\varphi(n)$ 是偶数，这里 $s\ge1$ 。接着构造连续平方序列

$x_0=a^r\bmod n,\qquad x_{j+1}=x_j^2\bmod n.$

第 $j$ 项同余于 $a^{2^jr}$ ，因此终点 $x_s\equiv a^K\equiv1$ 。我们不是盲目平方；终点已由指数条件保证，现在要研究第一次到1之前的一项。

8.2 为什么“平方为1”能产生因子

若某个 $x$ 满足 $x^2\equiv1\pmod n$ ，则 $n\mid(x-1)(x+1)$ 。模 $p$ 看， $p$ 是质数，所以 $p$ 必须整除 $x-1$ 或 $x+1$ ，即 $x\equiv1$ 或 $-1\pmod p$ 。模 $q$ 同理。

因此 $x$ 的两个CRT坐标只能是下面四种组合：

模 $p$	模 $q$	合并后的意义
$1$	$1$	$x\equiv1\pmod n$
$-1$	$-1$	$x\equiv-1\pmod n$
$1$	$-1$	两边符号不同
$-1$	$1$	两边符号不同

CRT保证每种组合对应一个根。因为 $p,q$ 都为奇数，模各个质数的1与 $-1$ 不同，所以这四个根也互不相同。

最后两种称为1的非平凡平方根。若 $x\equiv1\pmod p$ 、 $x\equiv-1\pmod q$ ，那么 $p\mid x-1$ ，但 $q\nmid x-1$ ；否则 $q$ 会同时整除 $x-1$ 与 $x+1$ ，进而整除它们的差2，与 $q$ 为奇质数矛盾。因此

$\gcd(x-1,n)=p,\qquad\gcd(x+1,n)=q.$

符号相反时两个因子互换。最大公约数提取因子，是因为两个质因子分别落在 $x-1$ 和 $x+1$ 中，不是仅凭“平方为1”就能分解。若 $x\equiv\pm1\pmod n$ ，得到的只是1或整个 $n$ ，没有拆出因子。

8.3 第一次到1之前的一项为什么值得检查

假设 $x_0\ne1$ ，并设 $x_j$ 是序列第一次出现的1，那么 $j\ge1$ 。它的前一项 $x_{j-1}$ 满足 $x_{j-1}^2\equiv1$ ，但 $x_{j-1}\not\equiv1$ ，因为这是第一次到1。

所以前一项只剩两种可能：它等于 $-1$ ，算法这次失败；或者它是非平凡平方根，可以提取因子。初始就为1时也失败，因为没有前一项可检查。

一个简短核对是 $n=55,e=3,d=27$ ，从而 $K=80=2^4\cdot5$ 。取 $a=2$ ，初始项 $2^5\equiv32$ ，随后平方得到 $34$ 、1。前一项34不是1或54，所以得到 $\gcd(33,55)=11$ 。它只是一般算法的一次实例；成功条件来自上一节的四种符号组合。

8.4 完整算法与失败分支

算法可以写成下面的顺序。所有余数均取 $0$ 至 $n-1$ 的代表，输入满足上面的指数条件。

从 $1,\ldots,n-1$ 均匀选取 $a$ ，计算 $g=\gcd(a,n)$ 。若 $g>1$ ，因 $a<n$ ， $g$ 已是一个真因子，输出 $g,n/g$ 。
若 $g=1$ ，计算 $x=a^r\bmod n$ 。若 $x=1$ ，本次失败，重新独立选取底数。
最多进行 $s$ 轮：令 $y=x^2\bmod n$ 。若 $y\ne1$ ，令 $x=y$ 继续；若 $y=1$ 且 $x=n-1$ ，本次失败；若 $y=1$ 且 $x\ne n-1$ ，输出 $\gcd(x-1,n)$ 及另一个因子。