# Demo 3：CRT 恢复

> 第 9 章 高等代数与数论量子算法 · [本章演示](index.md) · [代码演示总索引](../index.md)

**可视化**：3 子图（子群轨道+CRT 流程） —— Z_3^* + Z_5^* 拆解后合并

**对应教程**：[第 9 章 高等代数与数论量子算法 中相关小节](https://tutorial.chenzhaoyun.com/quantum-tutorial/ch09-algebra-number-theory/) · 依赖安装：`pip install "unified-quantum[visualization,simulation]"`

## 实现要点

模型: N=15 = 3 * 5, a=2, 目标 g=8.
Shor DLP 在 N 为合数时, 可拆成在 p_i = 3, 5 上的子 DLP (量子周期查找),
然后用 CRT 拼回 x (mod ord_N(a)). 这里:
  Z_3^*: a=2, ord_3(2)=2, 轨道 1 -> 2 -> 1; 8 mod 3 = 2, 故 x_1 = 1.
  Z_5^*: a=2, ord_5(2)=4, 轨道 1 -> 2 -> 4 -> 3 -> 1; 8 mod 5 = 3, 故 x_2 = 3.
  CRT (n_1=2, n_2=4): x = 3 满足 x mod 2 = 1, x mod 4 = 3, 与期望 x=3 一致.

量子部分用 1-qubit S/T 门做"简化路径" eigenstate QPE, 对应各子群的阶:
  ord_3(2) = 2  -> S eigenstate phase 1/4 (对应 r=4 in S gate, 或换 T 适配 r=2)
  ord_5(2) = 4  -> S eigenstate phase 1/4.

## 完整源码

```{literalinclude} 03_crt_recovery.py
:language: python
:linenos:
:caption: demos/ch09-algebra-number-theory/03_crt_recovery.py
```

## 运行结果

![Demo 3：CRT 恢复](03_crt_recovery.png)

## 运行方式

```bash
# 仓库根目录执行；输出 PNG 到 demos/ch09-algebra-number-theory/03_crt_recovery.png，关键统计到 stdout
.venv/bin/python3 demos/ch09-algebra-number-theory/03_crt_recovery.py
```

---

[← 本章演示](index.md) · [↑ 代码演示总索引](../index.md) · [⌂ 教程门户](https://tutorial.chenzhaoyun.com/)