基于代数群的整数分解

对于大整数分解的 Pollard’s $p-1$ 和 Williams’ $p+1$ 算法，作为密码学民科，我一直都只知道它们的使用条件—— $p-1$ 或 $q-1$ 光滑，当作黑盒去使用. 最近打了 NeSE 升级赛，发现这种算法的思想是可以扩展的，在这里稍微深入学习一下.（我的代数基础约等于 0，所以下面的描述很可能会有问题，希望大家指正）

Pollard’s $p-1$

该算法的核心是 Fermat 小定理

考虑 RSA 的情形（$n=pq$）.

如果我们找到一个 $N$ 满足 $p-1\mid N$ 且 $q-1 \nmid N$，那么对于一个一般的 $a$，有 $a^N\equiv 1\pmod{p}$ 但 $a^N\not\equiv 1\pmod{q}$（当 $a$ 和 $n$ 互素时才偶然地不成立）. 因此在这种情况下，$\text{GCD}(a^N-1,n)=p$.

怎么找到这样的 $N$ 呢？令 $P$ 是 $p-1$ 的最大素因子， $Q$ 是 $q-1$ 的最大素因子，不失一般性地，$P<Q$. Pollard 告诉我们，下面这个 $N$ 可以分解 $n$

也就是所有小于 $P$ 的素因子的累乘.

Williams’ $p+1$

Pollard’s $p-1$ 依赖于 $p-1$，Williams 告诉我们，可以在 二次域中使用幂的迹替换普通的幂运算，这样就可以让 $p+1$ 代替 $p-1$ 的作用. 关键在于，这个域的阶数为 $p^2-1$，我们能从中选出阶为 $p+1$ 的元素.

对于给定的参数 $A$ 定义 Lucas 序列 $V_i$

我们知道 $V_m=C_1\alpha_1^m+C_2\alpha_2^m$，其中 $\alpha_1,\alpha_2$ 是特征方程 $t^2-At+1$ 的根

容易验证 $C_1=C_2=1$，我们得到公式

现在开始，假设计算在模 $p$ 下进行，可以把根 $\alpha_1,\alpha_2$ 看作域 $\mathbb{Z}_p[\sqrt{A^2 - 4}]$ 的两个元素. 接下来我们讨论一下 $\sqrt{A^2 - 4}$ 是不是二次剩余，这决定了这个域是不是「扩」了.

当 $\sqrt{A^2 - 4}$ 是二次非剩余的时候，$\mathbb{Z}_p[\sqrt{A^2 - 4}]$ 是一个二次域，这时 $V_n$ 是 $\alpha_1^n$ 的迹. 此外，$(A^2-4)^{(p-1)/2}\equiv -1\pmod{p}$，所以

因此 $\alpha_1^p=\alpha_2$，进而 $\alpha_1^{p+1}=\alpha_2^{p+1}=\alpha_1\alpha_2=1$. 立即推对于任意的 $c$ 都有

反之，当 $\sqrt{A^2 - 4}$ 是二次剩余的时候，$\mathbb{Z}_p[\sqrt{A^2 - 4}]$ 实际上没「扩」，「降维」成 $\mathbb{Z}_p$. 因此

因为 $\alpha_1\alpha_2=1$，我们有

因此 $V_{c(p+1)}\equiv 2\pmod{p}$ 当且仅当 $\alpha_1^{2c}\equiv \alpha_2^{2c}\equiv 1\pmod{p}$.

总结一下，对于一个一般的模 $p$ 二次非剩余 $A$，如果 $q\neq p$ 我们有 $V_{c(p+1)}\equiv 2\pmod{p}$ 但 $V_{c(q+1)}\not\equiv 2\pmod{q}$（当 $(q-1)/2\mid c$ 时才偶然地不成立）.

两种算法的本质

从更高更抽象的视角来看，这两个算法其实是很相似的，我们把它们的核心 idea 放在一起看看：

• Pollard’s $p-1$
  • $\mathbb{Z}_p$ 的阶为 $p-1$
  • 对于一个一般的 $a$，有 $a^N\equiv 1\pmod{p}$ 但 $a^N\not\equiv 1\pmod{q}$（当 $a$ 和 $n$ 互素时才偶然地不成立）
  • 通过计算 $\text{GCD}(a^N-1,n)=p$ 分解出 $p$
• Williams’ $p+1$
  • $\mathbb{Z}_p[\sqrt{A^2 - 4}]$ 的阶为 $p^2-1$
  • 对于一个一般的模 $p$ 二次非剩余 $A$，如果 $q\neq p$ 我们有 $V_{c(p+1)}\equiv 2\pmod{p}$ 但 $V_{c(q+1)}\not\equiv 2\pmod{q}$（当 $(q-1)/2\mid c$ 时才偶然地不成立）
  • 通过计算 $\text{GCD}(V_N-2,n)=p$ 分解出 $p$

我们可以从中抽象出一个更一般的算法：

1. 构造一个模 $n$ 的代数群，它在某个 特别的因子 $p\mid n$ 下「降维」的群的 阶是可预测的；
2. 取群的 一般的元素 $a$ ，计算「$N$ 次幂」，得到一个 特别的元素 $a^N$；
3. 对 $n$ 和这个 特别的元素 $a^N$，通过 $\text{GCD}$ ，分解出 $p$.

注意我这里说的「可预测」指的不是我们知道阶的值。例如在没有分解 $n$ 的情况下，我们是不知道模 $p$ 乘法群的阶具体是多少的，但是我们知道它一定是 $p-1$.

Imaginary CTF 2023 - Sus

这是 maple 的一道 题目，要求分解 $n=pqr$，其中素数 $q=p^2+p+1$

第一次看到这个解法会觉得非常神奇，不过有了上面的抽象结果我想会稍微好理解一些：

Pick a random polynomial $f(x)=x^3+ax^2+bx+c$, and pick a random element $a$ in $\mathbb{R}=\mathbb{Z}_n[x]/f(x)$. If $f(x)$ is irreducible in $\mathbb{F}_p[x]$ then $\mathbb{K}=\mathbb{F}_p[x]/f(x)=\mathbb{F}_{p^3}$ will be a field with order $p^3-1=(p-1)(p^2+p+1)$.

We raise $a$ to the power of $n=pqr=p(p^2+p+1)r$ then $a^n$ would probably be of order $p-1$, which implies it will be in the form of $u+0x+0x^2$ in $\mathbb{K}$. This means we can take the degree 1 or 2 coefficient of $a^n$ in $\mathbb{R}$ and gcd it with $n$ to get $p$, then we can fully factor $n$ to decrypt the flag.

This is basically the same idea as Pollard’s p-1 or Williams’ p+1 factorization algorithm, but we are doing it in a field with higher degree.

用我们上面的抽象就是：

1. 构造一个模 $n$ 的代数群 $\mathbb{R} = \mathbb{Z}_n[x]/f(x)$，它在某个 特别的因子 $p\mid n$ 下「降维」的群 $\mathbb{K} = \mathbb{F}_p[x]/f(x) = \mathbb{F}_{p^3}$ 的 阶是可预测的，为 $p^3 - 1 = (p - 1)(p^2 + p + 1)$；
2. 取群的 一般的元素 $a$ ，计算「$n$ 次幂」，得到一个 特别的元素 $a^n$；
3. 对 $n$ 和这个 特别的元素 $a^n$，通过 $\text{GCD}(a^n的1次或2次系数,n)$ ，分解出 $p$.

当然这里面还有很多细节值得我们推导：为什么群 $\mathbb{K}$ 的阶数是 $p^3 - 1$？为什么 $a^n$ 的 1 次或 2 次系数是 0？可以看 糖醋小鸡块的分析（tql）. 我这里按我的想法梳理一下：

有限域的构造

基于这个方法，我们可以从 素域 $\mathbb{F}_p$ 出发，通过商环去构造 任意阶的域 $\mathbb{F}_q$.

需要注意的是，构造出的群有 $p^3$ 个元素，而在有限域中 除了零元素 以外的所有元素组成一个乘法群，所以这里说的

$\mathbb{K}=\mathbb{F}_p[x]/f(x)=\mathbb{F}_{p^3}$ will be a field with order $p^3-1=(p-1)(p^2+p+1)$

实际上是说 域的乘法群 $\mathbb{F}_{p^3}^*$ 的阶数是 $p^3-1$.

拉格朗日定理

（拉格朗日定理）若 $G$ 是一个有限群，而 $H$ 是 $G$ 的一个子群，则 $H$ 的阶整除 $G$ 的阶。

拉格朗日定理意味着，群中的每个元素的阶也会整除群的阶，而我们构造出的群的阶是 $p^3 - 1$，那么我们随机选择一个元素 $a$ ，它的阶就有可能是 $p^3-1$ 的因子 $p-1$.

现在假设我们从扩域 $\mathbb{K} = \mathbb{F}_p[x]/f(x) = \mathbb{F}_{p^3}$ 中 抽卡 抽到了一个元素 $a$ 使得 $a^n$ 阶为 $p-1$，$(a^n)^{p-1}=1$，也就是 $(a^n)^p=a^n$. 这让我想到最近学的一个概念，Frobenius 自同构.

Frobenius 自同构

从这个角度看，由 Fermat 小定理可以证明 $\sigma$ 的不动元就是元素 $a^n$ 所在的循环群的元素，也就是素域 $\mathbb{F}_p$ 的 $p$ 个元素， $a^n$ 的 1 次或 2 次系数是 0 似乎是不证自明的了.

NeSE 升级赛

本题的一部分难点抽象出来就是：

• 根据服务器提供的曲线上的 2 个点，从同余方程导出 $kp$ 和 $lq$，其中 $k$ 和 $l$ 都很大
• 有 $p$ 和 $q$ 的关系： $q=4p-1$，且保证 $p,q$ 是素数
• 我们需要得到 $p$ 的值.

类似地我们构造阶为 $q^2-1$ 的群即可. 同样套用我们前面的抽象来理解，由于 $4n=(q+1)q$

1. 构造一个模 $m=kp\cdot lq$ 的代数群 $\mathbb{R} = \mathbb{Z}_{m}[x]/f(x)$，它在某个 特别的因子 $q\mid m$ 下「降维」的群 $\mathbb{K} = \mathbb{F}_q[x]/f(x) = \mathbb{F}_{q^2}$ 的 阶是可预测的，为 $q^2 - 1 = (q - 1)(q + 1)$；
2. 取群的 一般的元素 $a$ ，计算「$4n$ 次幂」，得到一个 特别的元素 $a^{4n}$；
3. 对 $n$ 和这个 特别的元素 $a^{4n}$，通过 $\text{GCD}(a^n的1次系数,n)$ ，分解出 $q$.

需要注意的是这里 $m$ 还有一些从 $k,l$ 里面来的小因子 $p_i$，这样我们随机抽一个元素 $a$，得到 $a^{4n}$ 的阶就有可能被这些小因子影响，而我们想要的阶是 $q+1$，所以要先枚举一下小因子把它们从 $m$ 里面去掉.

但是我并不知道怎么说明在这种情况下 $a^{4n}$ 在 $\mathbb{K}$ 上的形式是 $u+0x$. 如果说 Sus 的情形是 $p-1$，可以类比到 Pollard’s $p-1$ 用费马小定理去证明，那从直觉上这种 $p+1$ 的情形也可以类比到 Williams’ $p+1$ 算法用 Lucas 序列去证明. 以后有机会再继续研究吧.