数学补给 01：Shor 算法所需的整数分解与离散对数

状态：▶ 正在学习
触发位置：第 01 周第一讲——Shor 算法的结构性威胁
建议第一轮用时：90—120 分钟

返回第 01 周主线 · 返回学习工作区

一、为什么现在创建这个单元

学习路线采用“后量子先行、数学按需回补”。现在我们已经遇到三个会直接影响安全判断的问题：

整数分解究竟是什么问题？
为什么从公钥 $Q=[x]P$ 恢复私钥 $x$ 叫作离散对数？
循环群、有限阿贝尔群和 Shor 的周期查找是什么关系？

因此，这个单元已经不再是未来可能使用的占位内容，而是当前主线的实际前置知识。

第一轮学习边界

本轮目标是达到结构层：会做小参数计算，能读懂符号，能把数学困难问题映射到 ECDSA、Schnorr、BLS 和 KZG。

本轮暂不要求证明量子傅里叶变换、有限阿贝尔群结构定理、Shor 的成功概率或具体量子线路复杂度。

二、先建立一张依赖地图

text

整除、素数、最大公因数
        ↓
      模运算
        ↓
有限群、元素的阶、循环子群
      ↙                  ↘
整数分解 ← 阶查找       离散对数：y = g^x
      ↘                  ↙
       周期 / 隐藏子群结构
                ↓
             Shor 算法
                ↓
RSA 类机制          ECDSA / Schnorr / BLS / KZG

这里要先记住一个区分：整数分解和离散对数是两个不同问题，Shor 分别为它们提供了量子多项式时间算法。 这里的“多项式时间”按输入的比特长度计量，例如整数 $N$ 的输入长度约为 $\log_2N$ ，并不是把 $N$ 的数值本身当作输入长度。当前 Bitcoin 和 Ethereum 中列出的签名风险主要来自离散对数分支，并不是因为它们使用了 RSA。

三、整数、整除与最大公因数

3.1 因子、素数与整数分解

若存在整数 $k$ 使 $b=ak$ ，就称 $a$ 整除 $b$ ，记作 $a\mid b$ 。

$3\mid 15$ ，因为 $15=3\times5$ ；
$4\nmid 15$ ，因为不存在整数 $k$ 使 $15=4k$ ；
大于 1 且只有 1 和自身两个正因子的整数称为素数。

整数分解问题

给定一个大合数 $N$ ，找出它的素因子。例如：

$N=77=7\times11.$

把两个已知素数相乘得到 $N$ 很容易；只拿到一个足够大的 $N$ 时，反向找出这些因子在经典计算模型下被认为很困难。分解标准 RSA 模数足以恢复构造私钥所需的信息；但不要进一步误写成“RSA 反演与整数分解已经被一般性证明等价”。

每个大于 1 的整数都能唯一地写成素数乘积，忽略素因子的排列顺序。例如：

$84=2^2\times3\times7.$

密码学中的困难不在于小整数分解，而在于输入有数百或数千比特时，尚无已知经典多项式时间通用分解算法。

3.2 最大公因数不是整数分解

$\gcd(a,b)$ 表示 $a$ 与 $b$ 的最大公因数。例如：

$\gcd(18,30)=6.$

欧几里得算法可以高效计算 gcd。Shor 的整数分解流程并不是用量子计算直接输出两个因子；它先用量子部分寻找一个周期，再用经典 gcd 把周期转换为因子。

四、模运算：只关心余数

若 $a$ 和 $b$ 除以 $N$ 的余数相同，就写作：

$a\equiv b\pmod N.$

例如 $17\equiv2\pmod5$ 。模运算可以想成时钟：超过一圈便回到前面。

计算	普通结果	模 7 的结果
$5+4$	9	2
$5\times3$	15	1
$3^4$	81	4

在模 $N$ 乘法中，并非每个余数都有乘法逆元。与 $N$ 互素的余数组成：

$\mathbb Z_N^*=\{a:0<a<N,\ \gcd(a,N)=1\}.$

例如：

$\mathbb Z_{10}^*=\{1,3,7,9\}.$

其中 $3$ 的逆元是 $7$ ，因为 $3\times7\equiv1\pmod{10}$ 。

五、群、阿贝尔群与循环群

5.1 群只是在规定一种可逆运算

一个群由元素集合 $G$ 和一种运算组成，并满足：

规则	直觉
封闭性	两个群元素运算后仍在群内
结合律	改变括号位置不改变结果
单位元	存在一个“不改变其他元素”的元素 $e$
逆元	每个元素都能通过另一个元素回到 $e$

若还满足 $a\circ b=b\circ a$ ，它就是阿贝尔群，也称交换群；若群中只有有限个元素，它就是有限群。

5.2 循环群由一个元素生成

生成元、循环群与元素的阶

在本页讨论的有限群中，如果存在 $g\in G$ ，使群中每个元素都能写成 $g^k$ ，那么 $G$ 是循环群， $g$ 是生成元：

$G=\langle g\rangle=\{g^k:k\in\mathbb Z\}.$

使 $g^r=e$ 成立的最小正整数 $r$ 称为 $g$ 的阶，记作 $\operatorname{ord}(g)=r$ 。若 $g$ 生成整个有限群，那么 $r=|G|$ ；从这一步开始，幂会以 $r$ 为周期重复。

以模 7 的非零余数乘法群为例，取 $g=3$ ：

$k$	0	1	2	3	4	5	6
$3^k\bmod7$	1	3	2	6	4	5	1

$3$ 在回到 1 前生成了全部 6 个元素，因此：

$\operatorname{ord}(3)=6,\qquad \mathbb Z_7^*=\langle3\rangle.$

循环群一定是阿贝尔群，因为 $g^a g^b=g^{a+b}=g^b g^a$ 。反过来不一定成立，例如 $\mathbb Z_2\times\mathbb Z_2$ 是有限阿贝尔群，却不存在一个能生成全部四个元素的生成元。

六、离散对数到底“离散”在哪里

6.1 乘法记号

在循环群 $G=\langle g\rangle$ 中选择秘密整数 $x$ ，计算：

$y=g^x.$

已知 $g$ 和 $x$ 时，计算 $y$ 很容易。离散对数问题要求在只知道 $g$ 和 $y$ 时恢复 $x$ ：

$x=\log_g y.$

这里的“对数”只是对 $g^x=y$ 中指数 $x$ 的反求；“离散”表示我们在有限、离散的群元素上运算，而不是求实数函数 $\ln y$ 。

在刚才的玩具群中：

$3^4\equiv4\pmod7,$

所以 $4$ 以 $3$ 为底的离散对数是 $x=4\pmod6$ 。真实密码系统使用的群极大，不能依靠列完整张表来求解。

6.2 椭圆曲线改用加法记号

椭圆曲线群通常把群运算写成点加法。对应关系是：

乘法群写法	椭圆曲线加法写法
生成元 $g$	基点 $P$
重复相乘 $g^x$	重复相加 $[x]P$
公钥 $y=g^x$	公钥 $Q=[x]P$
从 $g,y$ 求 $x$	从 $P,Q$ 求 $x$

$[x]P$ 表示把 $P$ 重复相加 $x$ 次，不是普通整数乘法。ECDSA、Schnorr 和 BLS 的私钥—公钥关系都可以先抽象成：

text

秘密标量 x
    ↓ 与公开基点做标量乘法
公开群元素 Q = [x]P

这三个签名方案的密钥恢复问题都包含相应群中的离散对数：一旦能从 $P,Q$ 求出 $x$ ，就足以恢复签名密钥并破坏方案。它们完整的不可伪造性论证还涉及各自的安全假设与证明模型，不能简单写成“签名安全与离散对数完全等价”。

七、整数分解为什么会变成阶查找

完整的整数分解算法会先用经典方法处理偶数、素数和完全幂。下面的阶查找分支假设 $N$ 是奇合数且不是素数幂；RSA 型半素数属于重点情形。

取待分解整数 $N=15$ ，随机选择与它互素的 $a=2$ ，观察：

$k$	0	1	2	3	4
$2^k\bmod15$	1	2	4	8	1

序列在 4 步后回到 1，所以 $r=4$ 是 2 在模 15 乘法下的阶。因为 $r$ 是偶数：

$2^r-1=(2^{r/2}-1)(2^{r/2}+1).$

再做经典 gcd 计算：

$\gcd(2^{2}-1,15)=\gcd(3,15)=3,$

$\gcd(2^{2}+1,15)=\gcd(5,15)=5.$

于是得到 $15=3\times5$ 。

Shor 整数分解的概念流程

先用经典方法检查偶数、素数和完全幂；
对剩余的奇合数选择 $1<a<N$ ，计算 $\gcd(a,N)$ ；
若 gcd 已经不是 1，就直接找到因子；
否则寻找最小的 $r>0$ ，使 $a^r\equiv1\pmod N$ ；
若 $r$ 为偶数，并且 $a^{r/2}\not\equiv-1\pmod N$ ，计算 $\gcd(a^{r/2}\pm1,N)$ ；
得到非平凡因子；若条件不满足，就换一个 $a$ 重试。

其中第 4 步的阶查找是量子加速的核心，其余步骤都是经典计算。

玩具例子可以直接列举周期，但真实密码参数不能。Shor 使用叠加、模幂运算和量子傅里叶变换，从测量结果中恢复周期候选，再由经典算法完成后处理。

八、离散对数为什么属于隐藏周期问题

设 $G=\langle g\rangle$ 是阶为 $r$ 的有限循环群，并且公开 $y=g^x$ 。对 $a,b\in\mathbb Z_r$ ，定义函数：

$F:\mathbb Z_r\times\mathbb Z_r\longrightarrow G,\qquad F(a,b)=g^a y^b=g^{a+bx}.$

对两组输入 $(a,b)$ 与 $(a',b')$ ，令 $\Delta a=a'-a$ 、 $\Delta b=b'-b$ 。当它们满足：

$\Delta a+x\Delta b\equiv0\pmod r,$

它们会映射到同一个群元素。所有这种“不会改变函数值的位移”构成隐藏子群：

$H=\{(u,v)\in\mathbb Z_r^2:u+xv\equiv0\pmod r\}.$

Shor 离散对数的概念流程

text

公开 g 与 y = g^x
        ↓
构造带有隐藏线性周期的函数 F(a,b)
        ↓
在有限阿贝尔群上进行量子傅里叶采样
        ↓
收集关于隐藏周期的多个线性关系
        ↓
经典模运算恢复秘密指数 x

这里的有限阿贝尔群视角描述的是量子算法寻找隐藏结构的统一框架。具体离散对数仍是在 $g$ 生成的循环子群中定义的。

第一次阅读不必推导量子态振幅。你现在只需看出共同模式：

整数分解被转化为模 $N$ 乘法中的阶查找；
离散对数被转化为指数对之间的隐藏线性周期；
两者都不是无结构穷举，因此 Shor 能获得不同于 Grover 平方级加速的结构性优势。

九、把数学映射回区块链

机制	可抽象的公开关系	Shor 对应的困难问题	直接后果
RSA 类公钥机制	$N=pq$	整数分解	恢复私钥所需的秘密因子
Bitcoin ECDSA	$Q=[x]P$	椭圆曲线离散对数	恢复支出私钥并伪造签名
Bitcoin Schnorr	$Q=[x]P$	椭圆曲线离散对数	恢复 Taproot key-path 私钥
Ethereum EOA ECDSA	$Q=[x]P$	椭圆曲线离散对数	恢复账户私钥并伪造交易
Ethereum 验证者 BLS	$Q=[x]P$	配对友好曲线群中的离散对数	冒充验证者签署共识消息
Ethereum KZG	SRS 含 $[\tau^i]P$ 等公开点	对 SRS 公开群点求离散对数	从 $[\tau]P$ 等公开点恢复 $\tau$ ，使相关证明假设失效并破坏求值绑定性
SHA-256 等哈希	没有 $Q=[x]P$ 关系	不属于上述两类	应单独分析 Grover 等量子算法

当前最重要的安全判断

“Shor 能做整数分解”并不是 Bitcoin 和 Ethereum 交易签名失陷的直接原因。它们的核心风险是：当相应公钥或公开群点已经可得时，Shor 可以从 $Q=[x]P$ 高效恢复秘密标量 $x$ 。Taproot output key、验证者 BLS 公钥和 KZG SRS 天然公开；P2PKH/P2WPKH 输出和未发送过交易的 EOA 则要单独分析公钥暴露时点。

KZG 不是签名，但 Shor 可以先对 SRS 中的公开点求离散对数并恢复隐藏标量 $\tau$ ，继而使相关配对群安全假设和求值绑定性失效。因此，不能因为 KZG“没有用户签名私钥”就把它排除在量子迁移清单之外。

十、本次练习

练习 A：术语与计算

分解 $91$ ，并说明“验证答案容易”体现在哪里。
计算 $\gcd(35,64)$ ，判断 35 是否属于 $\mathbb Z_{64}^*$ 。
列出 $3^k\bmod7$ 从 $k=0$ 到首次回到 1 的结果，并写出 3 的阶。
在 $\mathbb Z_7^*=\langle3\rangle$ 中，求满足 $3^x\equiv5\pmod7$ 的 $x$ 。

练习 B：解释 Shor 的两条路线

不用公式，各用三句话解释：

整数分解如何转化为阶查找和 gcd；
离散对数如何转化为隐藏周期关系。

练习 C：映射区块链对象

把下面对象分别归入“整数分解”“离散对数”“需要单独分析”：

RSA 公钥中的模数；
Bitcoin Taproot output key；
Ethereum 验证者 BLS 公钥；
SHA-256 原像；
KZG 结构化参考串中的曲线点。

展开自查提示

A1： $91=7\times13$ ；相乘即可快速验证。
A2： $\gcd(35,64)=1$ ，所以 35 在 $\mathbb Z_{64}^*$ 中。
A3： $1,3,2,6,4,5,1$ ，阶为 6。
A4： $x=5\pmod6$ 。
C：依次为整数分解、离散对数、离散对数、需要单独分析、对公开群点求离散对数；最后一项会进一步使相关配对群证明假设失效。

十一、第一轮验收标准

能区分因子、素数、gcd、模同余和模逆；
能用 $N=15,a=2$ 的例子解释“阶查找如何给出因子”；
能解释群、有限群、阿贝尔群、循环群、生成元和元素的阶；
能在小循环群中列幂表并求一个离散对数；
能在 $y=g^x$ 与 $Q=[x]P$ 两种记号之间转换；
能说明为什么 ECDSA、Schnorr 和 BLS 主要对应离散对数，而不是整数分解；
能说明“有限阿贝尔群”是统一算法框架，“离散对数”具体发生在循环子群中；
能明确说出本轮暂未学习的内容，而不是假装已经掌握。

完成这些项目后，回到第 01 周第一讲的 Shor 风险表，重新解释每一行“公开对象 → 困难问题 → 秘密信息 → 系统后果”。

十二、以后何时继续拆分

目前只保留这一个 index.md。只有真正进入下面内容时，才在本目录增加相应文件：

整数分解归约、欧拉函数与连分数；
椭圆曲线群运算与配对；
量子态、相位估计与量子傅里叶变换；
有限阿贝尔群分解与隐藏子群算法；
Shor 线路、容错资源估算与现实攻击时间窗。

这样既补上当前缺失的数学桥梁，也不会重新回到“先把整本数论和抽象代数学完才能继续”的顺序。

一、为什么现在创建这个单元 ​

二、先建立一张依赖地图 ​

三、整数、整除与最大公因数 ​

3.1 因子、素数与整数分解 ​

3.2 最大公因数不是整数分解 ​

四、模运算：只关心余数 ​

五、群、阿贝尔群与循环群 ​

5.1 群只是在规定一种可逆运算 ​

5.2 循环群由一个元素生成 ​

六、离散对数到底“离散”在哪里 ​

6.1 乘法记号 ​

6.2 椭圆曲线改用加法记号 ​

七、整数分解为什么会变成阶查找 ​

八、离散对数为什么属于隐藏周期问题 ​

九、把数学映射回区块链 ​

十、本次练习 ​

练习 A：术语与计算 ​

练习 B：解释 Shor 的两条路线 ​

练习 C：映射区块链对象 ​

十一、第一轮验收标准 ​

十二、以后何时继续拆分 ​

一、为什么现在创建这个单元

二、先建立一张依赖地图

三、整数、整除与最大公因数

3.1 因子、素数与整数分解

3.2 最大公因数不是整数分解

四、模运算：只关心余数

五、群、阿贝尔群与循环群

5.1 群只是在规定一种可逆运算

5.2 循环群由一个元素生成

六、离散对数到底“离散”在哪里

6.1 乘法记号

6.2 椭圆曲线改用加法记号

七、整数分解为什么会变成阶查找

八、离散对数为什么属于隐藏周期问题

九、把数学映射回区块链

十、本次练习

练习 A：术语与计算

练习 B：解释 Shor 的两条路线

练习 C：映射区块链对象

十一、第一轮验收标准

十二、以后何时继续拆分