拓冰网站定制 
factoring_sqif 全解析基于 Schnorr 格分解与 QAOA 量子优化的整数分解实现【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research本文基于 factoring_sqif/README.md 及其配套源码系统讲解 Google Research 子项目 factoring_sqif一个将经典 Schnorr 格分解算法与量子优化QAOA / 穷举结合、用于整数分解的实现。你将掌握其环境搭建、命令行用法、lattice_parameter、precision_parameter、平滑界B₂等关键超参数的含义与取值策略并通过源码级调用链理解CVP 问题 → Ising 自旋玻璃哈密顿量 → 低能态采样 → SR-pair → 线性方程组 → 因子提取的完整流水线。一、项目定位与算法背景factoring_sqif 是 Google Research 仓库当前工作目录google-research下的一个独立子项目其核心是实现 arXiv 论文Sublinear Quantum Integer FactoringarXiv:2212.12372中提出的 SQIFSublinear Quantum Integer Factoring算法并在此基础上做了若干工程化改动。从代码结构看factoring_sqif/factoring_sqif该项目由以下模块组成模块职责main.pyCLI 入口、参数解析、完整分解流水线编排schnorr.pySR-pair 到因子提取的经典代数步骤含 GPU 上的 Z₂ 高斯消元closest_vector_problem.py格构造、目标向量生成、Babai 近似最近向量算法hamiltonian.py将 CVP 搜索问题编码为 Ising 哈密顿量并枚举低能态qaoa.pyQAOA 电路生成、参数优化与采样number_theory.py素数生成、光滑性判定、格维度计算等数论工具fpylll_helpers.pyfpylllFPLLL 的 Python 绑定的 LLL 规约封装算法思想可概括为把整数分解问题归约为在特定格上求解最近向量问题CVP再用量子优化手段在 Babai 给出的近似解附近搜索更优解从而收获足够多的光滑关系对SR-pair最终通过求解模 2 线性方程组还原出 N 的非平凡因子。需要说明的是README 明确指出 Schnorr 算法本身在经典密码学界仍有争议——在声称的亚线性格维度下能否产生足够多的优质 SR-pair 并不明确README 引用了经典密码社区的多处讨论。本仓库的价值在于提供了一个可复现的实验平台用于检验量子优化增强 CVP 求解这条技术路线而非宣称已经破解大整数。二、环境搭建与安装README 给出两条安装步骤均在factoring_sqif子项目根目录即包含 dependencies.yaml 和 pyproject.toml 的目录下执行。第一步用 conda 创建开发环境conda env create -f dependencies.yaml -n factoring conda activate factoringdependencies.yaml 中锁定的关键依赖包括python3.10、numpy1.21基础运行环境fpylll0.5.9FPLLL 的 Python 接口用于 LLL 格基规约与 Babai 近似最近向量sage9.8SageMath用于在-b模式下随机生成指定比特位的半素数见 main.py 中n_bit_integer对sage.arith.misc.random_prime的调用cudnn8.2.1、cudatoolkit11.3.1CUDA 环境对应 requirements.txt 中的cupy-cuda11xGPU 上的哈密顿量能量枚举依赖 CuPynumba对能量计算热路径的 JIT 加速。第二步安装库本体pip install .pip install .会依据 pyproject.toml 构建并安装factoring_sqif包。该文件的[project]段还揭示了项目元信息包名为factoring_sqif描述为 Implementation of sublinear quantum integer factorization algorithm要求python3.10作者为 Tanuj Khattar 与 Nour Yosri。requirements.txt中githttps://github.com/quantumlib/ReCirq表明其依赖 ReCirq 仓库中的优化器README 提到论文使用其中的 Model Gradient Descent详见下文 QAOA 小节。三、命令行用法与参数速查运行入口是main.py其命令行接口由 main.py 顶部的argparse定义。运行python factoring_sqif/main.py --help可查看完整用法usage: Integer factoring using Schnorrs algorithm quantum optimization. [-h] (-N NUMBER_TO_FACTOR | -b BITSIZE) [-l LATTICE_PARAMETER] [-c PRECISION_PARAMETER] [-s SEED] [-m {qaoa,bruteforce}] [-p QAOA_DEPTH] [-NS NUM_SAMPLES] Implementation of integer factoring algorithm described in https://arxiv.org/abs/2212.12372 options: -h, --help show this help message and exit -N NUMBER_TO_FACTOR, --number_to_factor NUMBER_TO_FACTOR Integer to factor. -b BITSIZE, --bitsize BITSIZE Bitsize of number to be factored. -l LATTICE_PARAMETER, --lattice_parameter LATTICE_PARAMETER Lattice parameter. -c PRECISION_PARAMETER, --precision_parameter PRECISION_PARAMETER Precision parameter. -s SEED, --seed SEED Seed for random number generation. -m {qaoa,bruteforce}, --method {qaoa,bruteforce} Method to use for finding ground states of the hamiltonian. -p QAOA_DEPTH, --qaoa_depth QAOA_DEPTH Depth of qaoa circuit. -NS NUM_SAMPLES, --num_samples NUM_SAMPLES Number of low energy states to sample其中-N与-b构成互斥必选组要么直接指定待分解整数N要么指定比特位宽b此时程序会用 Sage 随机生成一个b比特的半素数见 main.py 的n_bit_integer。各参数在源码中的默认值如下来自 main.py 的add_argument定义参数默认值说明-l / --lattice_parameter1.5格维度缩放系数见第四节-c / --precision_parameter4格构造精度参数见第五节-s / --seed99随机数种子保证可复现-m / --methodbruteforce低能态求解方法可选qaoa/bruteforce-p / --qaoa_depth2QAOA 电路深度 p-NS / --num_samples2**15采样的低能态数量在solve内部会被截断为不超过2^nn 为格维度最小可运行示例README 用分解187 17 × 11演示了默认流程python factoring_sqif/main.py -N 18750 比特随机整数 穷举法python factoring_sqif/main.py -b 50 --method bruteforce50 比特随机整数 QAOA深度 3python factoring_sqif/main.py -b 50 --method qaoa -p 3分解成功时程序会输出形如Found factors (707933, 882727) for 624911573291 using 11 qubits via bruteforce.的结果该行即来自仓库自带的 40 比特运行日志见下文第七节。四、核心超参数一格维度与lattice_parameterSchnorr 算法广受讨论的要点之一是它声称可以在仅随待分解数比特位宽亚线性增长的格维度下找到足够多的优质 SR-pair——这也正是论文将其作为量子优化起点的原因。但在经典密码学社区求解声称维度格上的 CVP 是否真能产生足够 SR-pair 尚无定论README 引用了 crypto.stackexchange 与相关讨论。在量子化方案中格维度直接决定了所需的量子比特数每个格维度对应一个 qubit。本项目用可配置常数lattice_parameter控制格维度$$ n \mathrm{lattice_parameter} \cdot \frac{\log_2(N)}{\log_2(\log_2(N))} $$该公式在 number_theory.py 中实现为integer_to_lattice_dimensiondef integer_to_lattice_dimension(N, c1): logN round(math.log2(N)) return int(c * int(logN) // int(round(math.log2(logN))))number_theory_test.py 给出了三个基准校验对应 README 提到的论文复现样例integer_to_lattice_dimension(1961) 3integer_to_lattice_dimension(48567227) 5integer_to_lattice_dimension(261980999226229) 8一般来说格维度越高找到足够多优质 SR-pair 的概率越大分解越可能成功但算法的时间/空间复杂度也随之上升。值得注意的一个实现细节是main.py 中SchnorrFactoringConfig.from_arxiv_paper_defaults的函数签名默认lattice_parameter1而论文复现样例run_arxiv_examples依次使用[1, 1.5, 1.5]命令行默认值则是1.5。读者可以根据目标位数自由调节-l。五、核心超参数二精度参数c与格构造精度参数c控制构造格所使用的基向量。原版 Schnorr 算法中格 $B_{n,c}$ 构造为$$ B_{n,c} \begin{bmatrix} f(1) 0 \dots 0\ 0 f(2) \dots 0\ \vdots \vdots \ddots \vdots\ 0 0 \dots f(n) \ N^c\ln{p_1} N^c\ln{p_2} \dots N^c\ln{p_n} \end{bmatrix} $$其中 $f(i)$$i1,\dots,n$是 $(\sqrt{\ln{p_1}}, \sqrt{\ln{p_2}}, \dots, \sqrt{\ln{p_n}})$ 的随机排列。本项目依据 arXiv:2212.12372对其做了两处修改$$ B_{n,c} \begin{bmatrix} f(1) 0 \dots 0\ 0 f(2) \dots 0\ \vdots \vdots \ddots \vdots\ 0 0 \dots f(n) \ \lfloor10^c\ln{p_1}\rceil \lfloor10^c\ln{p_2}\rceil \dots \lfloor10^c\ln{p_n}\rceil \end{bmatrix} $$其中 $f(i)$ 改为 $(\lceil 1/2 \rceil, \lceil 2/2 \rceil, \dots, \lceil n/2 \rceil)$ 的随机排列末行从 $N^c\ln{p_i}$ 改为取整后的 $\lfloor 10^c\ln{p_i}\rceil$。对应实现位于 closest_vector_problem.py 的sample函数它按上述公式构造一个 $(n1)\times n$ 的IntegerMatrix并生成稀疏目标向量 $t$——$t$ 只有最后一个分量非零取值为 $\lfloor 10^c\ln{N}\rceil$。该函数 docstring 注明其构造方式对应论文第 13 页并限制格维度 $n\le 25$超出会报NotImplemented。READme 指出格的行列式与精度参数 $c$ 正相关论文猜想找到接近目标向量的格向量的概率与 $c$ 正相关但作者也坦承这一推断的理由并不显然。因此-c是一个值得实验调参的对象默认值 4。六、核心超参数三平滑界 $B_2$ 与采样数量在 Schnorr 算法中格上的每个点都可映射为一对整数 $(u,v)$且按构造 $u$、$v$ 均为 $p_n$-光滑即其素因子不超过第 $n$ 个素数 $p_n$$n$ 为格维度。算法要求找到足够多的 SR-pair $(u,v)$使得 $u$、$v$ 都是 $p_n$-光滑且 $|u - v\cdot N|$ 是 $p_{B_2}$-光滑素因子不超过第 $B_2$ 个素数。这里的 $B_2$ 是另一个超参数通常至少取 $n$。经验法则SR-pair 的数量只需比平滑界 $B_2$ 多几个。本实现默认设置$$ B_2 2n^2 $$$$ \mathrm{num_sr_pairs_to_sample} B_2 2 $$其中 $n$ 为格维度。源码中的对应关系在 main.pylinear_eq_system_dimension 1 2 * n**2num_sr_pairs_to_sample linear_eq_system_dimension 1而solve内的实际光滑界取smooth_bound config.linear_eq_system_dimension - 1即 $2n^2 B_2$。以 40 比特运行日志为例格维度 $n11$ 时日志显示smooth bound 242、243维线性方程组、需要244个 SR-pair——恰好满足 $2\times 11^2242$、$1242243$、$2431244$。$B_2$ 对算法的影响存在权衡$B_2$ 越大满足 $|u - v\cdot N|$ 为 $B_2$-光滑的约束越容易满足找到有效 SR-pair 的概率越高但 $B_2$ 越大需要采样的 SR-pair 数量越多整体运行时间越长。光滑性判定实现在 number_theory.py 的is_smoothSR-pair 过滤在 hamiltonian.py 的sr_pairs_from_uv_pairs对每个 UV-pair 检查abs(u - N*v)是否光滑。此外 number_theory.py 的pairs_to_sr_possiblities还实现了一个技巧按最大素因子下标排序 SR-pair一旦前缀数量超过该下标即可构成有效的方程组前缀。七、完整流水线从 CVP 到因子solve主循环main.py 的solve函数是整条流水线的核心其迭代逻辑可归纳为五步每一步都对应独立模块构造格与目标向量调用 closest_vector_problem.py 的cvp.sample(N, n, c, rs)得到 $(n{}1)\times n$ 的格B与目标向量tBabai 近似最近向量调用cvp.babai_algorithm(B, t)closest_vector_problem.py。该函数先用 fpylll 以delta0.75对格基做 LLL 规约再通过GSO.Mat(D).babai(t)得到近似解权重w、残差向量与rounding_direction决定后续在超立方体中搜索的方向封装为BabaiResult构造问题哈密顿量hamiltonian.hamiltonian_from_babai_result(qs, babai_result)hamiltonian.py把在 Babai 近似解附近寻找更优格向量编码为 Ising 型哈密顿量 $H \sum_j (r_j - \sum_i X_i D_{ji})^2$其中 $X_i$ 为投影算子$D$ 为 LLL 规约后的格基$r$ 为残差向量采样低能态并过滤 SR-pair按method选择bruteforce或qaoa得到低能态整数表示随后依次经过integer_states_to_lattice_vectors→u_v_pairs_from_lattice_vectors→sr_pairs_from_uv_pairs均位于 hamiltonian.py把低能态映射回格向量、再映射回 $(u,v)$ 光滑对、最后过滤出 SR-pair 并入集合循环直到收集够num_sr_pairs_to_sample个或达到max_lattice_iterations次迭代解线性方程组提取因子把 SR-pair 转成指数差向量schnorr.sr_pair_to_differences在GPUCuPy上做模 2 高斯消元schnorr.py 的_gaussian_elementation_Z2并枚举零空间_null_space得到指数组合再由exponents_to_candidates构造候选因子并math.gcd(p, N)校验——一旦得到非平凡因子即返回SchnorrFactoringResult。仓库results/目录下附带多组真实运行日志如 40bit_l1_bruteforce.txt、70bit_qaoa.txt、128bit_l1_bruteforce.txt等文件名即标注了比特位宽与lattice_parameter取值。以 40 比特日志为例可观察到典型行为每轮迭代从 2048 个 UV-pair 中过滤出 024 个 SR-pair40 轮迭代累计 247/244 个 SR-pair 后停止随后在 Z₂ 零空间搜索中成功找到因子707933与882727624911573291 707933 × 882727全程仅使用 11 个量子比特。八、寻找哈密顿量低能态的三种途径README 依次介绍了三种求解低能态即寻找接近目标向量的格向量的方案。8.1 暴力枚举Brute Force最简单的方法穷举全部 $2^n$ 个比特串作为输入态$n$ 为量子比特数/格维度。复杂度随 $n$ 指数增长并不具备可扩展性其作用是假设存在完美量子优化器时验证其余经典归约的正确性。运行方式python factoring_sqif/main.py -b 50 --method bruteforce实现上hamiltonian.py 的brute_force_lowest_energy_states对全部 $2^n$ 个整数态调用energy_from_integer_states计算能量并稳定排序取前num_samples个。energy_from_integer_states对单比特项Z与双比特项ZZ分别用 numba JIT 批量求值双比特项通过 CuPy 上 GPU 加速见_in_batches的cudaTrue分支。8.2 QAOA论文主推方法QAOA 是启发式算法性能取决于两个可配置的启发式因素电路深度 $p$默认 $p2$可通过--qaoa_depth调大。电路构造见 qaoa.py 的generate_qaoa_circuit先对所有 qubit 施加 Hadamard再交替叠加 $p$ 层gamma由哈密顿量各项分解为Z**与ZZ**门见get_gamma_layer与beta对所有 qubit 施加X**见get_beta_layer外层经典优化器用于寻找变分电路的最优参数。论文声称使用 Model Gradient DescentReCirq 中有对应实现但 README 说明作者尝试开箱即用的 MGD 实现并未收敛因此在 qaoa.py 的find_optimal_parameters中改为调用 ReCirq 的minimize并以BFGS作为优化方法代码注释保留了 TODO说明仍在调研 MGD 不收敛的原因欢迎读者自行尝试其他优化方法。QAOA 采样的完整路径为sample_low_energy_statesqaoa.py生成电路 → BFGS 优化参数 → 用qsimcirq.QSimSimulator8 线程重复采样 10000 次 → 按频率返回比特串。运行示例python factoring_sqif/main.py -b 50 --method qaoa -p 3此外 qaoa.py 还提供expected_energy_landscape与plot_energy_landspace可在 $(\gamma, \beta)\in[0,\pi]^2$ 网格上绘制期望能量热力图用于直观观察代价函数曲面——main.qaoa_main()10 比特示例问题演示了这一可视化流程。8.3 DCQF未来改进方向DCQF 是另一种启发式算法arXiv:2301.11005与 QAOA 不同它不需要外层经典优化循环。README 明确指出DCQF 的具体细节以论文为准本仓库尚未集成其实现留作未来改进方向。九、测试与验证仓库自带两组 pytest 测试是验证经典归约正确性的关键证据number_theory_test.py校验格维度公式1961→3、48567227→5、261980999226229→8hamiltonian_test.py覆盖三个层面——test_hamiltonian用 test_data/3q/hamiltonian.txt 与10q/下预计算的低能态基准比对暴力枚举结果test_hamiltonian_construction验证hamiltonian_from_babai_result与参考哈密顿量完全一致test_u_v_pairs_from_integer_states与test_sr_pairs_from_uv_pairs验证低能态 → 格向量 → (u,v) 对 → SR-pair 的逐级映射以 N1961 为例UV 对(1800,1),(1944,1),(2025,1),(3645,2)中仅前三个在平滑界 15 下构成 SR-pair。十、复现论文样例与进一步探索main.py 的run_arxiv_examples内置了论文的三个复现目标待分解数 Nlattice_parameter精度参数 c对应格维度196111.53485672271.5452619809992262291.548有兴趣的读者可以在此基础上围绕 README 与源码指出的开放问题做进一步实验调节-l、-c、-p观察 SR-pair 产出率与运行时间的变化尝试更换 qaoa.py 中的外层优化器如复现论文的 MGD或按 README 的启发探索比超立方体搜索更好的 CVP→量子优化归约方式。参考资源本文相关的背景文献均为 README 原文引用此处以文本形式列出Sublinear Quantum Integer FactoringarXiv:2212.12372——本实现所依据的核心论文A note on Integer Factorization using LatticesA. VeraarXiv:1003.5461Schnorrs Approach to Factoring via LatticesLéo DucasCWI RISC 讲座幻灯片SchnorrGate - Testing Schnorrs factoring Claim in SageMathLéo Ducas——对 Schnorr 格分解主张的 SageMath 检验DCQF 方法论文arXiv:2301.11005——README 中留作未来改进的量子优化方案。【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 factoring_sqif 全解析：基于 Schnorr 格分解与 QAOA 量子优化的整数分解实现
factoring_sqif 全解析基于 Schnorr 格分解与 QAOA 量子优化的整数分解实现【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research本文基于 factoring_sqif/README.md 及其配套源码系统讲解 Google Research 子项目 factoring_sqif一个将经典 Schnorr 格分解算法与量子优化QAOA / 穷举结合、用于整数分解的实现。你将掌握其环境搭建、命令行用法、lattice_parameter、precision_parameter、平滑界B₂等关键超参数的含义与取值策略并通过源码级调用链理解CVP 问题 → Ising 自旋玻璃哈密顿量 → 低能态采样 → SR-pair → 线性方程组 → 因子提取的完整流水线。一、项目定位与算法背景factoring_sqif 是 Google Research 仓库当前工作目录google-research下的一个独立子项目其核心是实现 arXiv 论文Sublinear Quantum Integer FactoringarXiv:2212.12372中提出的 SQIFSublinear Quantum Integer Factoring算法并在此基础上做了若干工程化改动。从代码结构看factoring_sqif/factoring_sqif该项目由以下模块组成模块职责main.pyCLI 入口、参数解析、完整分解流水线编排schnorr.pySR-pair 到因子提取的经典代数步骤含 GPU 上的 Z₂ 高斯消元closest_vector_problem.py格构造、目标向量生成、Babai 近似最近向量算法hamiltonian.py将 CVP 搜索问题编码为 Ising 哈密顿量并枚举低能态qaoa.pyQAOA 电路生成、参数优化与采样number_theory.py素数生成、光滑性判定、格维度计算等数论工具fpylll_helpers.pyfpylllFPLLL 的 Python 绑定的 LLL 规约封装算法思想可概括为把整数分解问题归约为在特定格上求解最近向量问题CVP再用量子优化手段在 Babai 给出的近似解附近搜索更优解从而收获足够多的光滑关系对SR-pair最终通过求解模 2 线性方程组还原出 N 的非平凡因子。需要说明的是README 明确指出 Schnorr 算法本身在经典密码学界仍有争议——在声称的亚线性格维度下能否产生足够多的优质 SR-pair 并不明确README 引用了经典密码社区的多处讨论。本仓库的价值在于提供了一个可复现的实验平台用于检验量子优化增强 CVP 求解这条技术路线而非宣称已经破解大整数。二、环境搭建与安装README 给出两条安装步骤均在factoring_sqif子项目根目录即包含 dependencies.yaml 和 pyproject.toml 的目录下执行。第一步用 conda 创建开发环境conda env create -f dependencies.yaml -n factoring conda activate factoringdependencies.yaml 中锁定的关键依赖包括python3.10、numpy1.21基础运行环境fpylll0.5.9FPLLL 的 Python 接口用于 LLL 格基规约与 Babai 近似最近向量sage9.8SageMath用于在-b模式下随机生成指定比特位的半素数见 main.py 中n_bit_integer对sage.arith.misc.random_prime的调用cudnn8.2.1、cudatoolkit11.3.1CUDA 环境对应 requirements.txt 中的cupy-cuda11xGPU 上的哈密顿量能量枚举依赖 CuPynumba对能量计算热路径的 JIT 加速。第二步安装库本体pip install .pip install .会依据 pyproject.toml 构建并安装factoring_sqif包。该文件的[project]段还揭示了项目元信息包名为factoring_sqif描述为 Implementation of sublinear quantum integer factorization algorithm要求python3.10作者为 Tanuj Khattar 与 Nour Yosri。requirements.txt中githttps://github.com/quantumlib/ReCirq表明其依赖 ReCirq 仓库中的优化器README 提到论文使用其中的 Model Gradient Descent详见下文 QAOA 小节。三、命令行用法与参数速查运行入口是main.py其命令行接口由 main.py 顶部的argparse定义。运行python factoring_sqif/main.py --help可查看完整用法usage: Integer factoring using Schnorrs algorithm quantum optimization. [-h] (-N NUMBER_TO_FACTOR | -b BITSIZE) [-l LATTICE_PARAMETER] [-c PRECISION_PARAMETER] [-s SEED] [-m {qaoa,bruteforce}] [-p QAOA_DEPTH] [-NS NUM_SAMPLES] Implementation of integer factoring algorithm described in https://arxiv.org/abs/2212.12372 options: -h, --help show this help message and exit -N NUMBER_TO_FACTOR, --number_to_factor NUMBER_TO_FACTOR Integer to factor. -b BITSIZE, --bitsize BITSIZE Bitsize of number to be factored. -l LATTICE_PARAMETER, --lattice_parameter LATTICE_PARAMETER Lattice parameter. -c PRECISION_PARAMETER, --precision_parameter PRECISION_PARAMETER Precision parameter. -s SEED, --seed SEED Seed for random number generation. -m {qaoa,bruteforce}, --method {qaoa,bruteforce} Method to use for finding ground states of the hamiltonian. -p QAOA_DEPTH, --qaoa_depth QAOA_DEPTH Depth of qaoa circuit. -NS NUM_SAMPLES, --num_samples NUM_SAMPLES Number of low energy states to sample其中-N与-b构成互斥必选组要么直接指定待分解整数N要么指定比特位宽b此时程序会用 Sage 随机生成一个b比特的半素数见 main.py 的n_bit_integer。各参数在源码中的默认值如下来自 main.py 的add_argument定义参数默认值说明-l / --lattice_parameter1.5格维度缩放系数见第四节-c / --precision_parameter4格构造精度参数见第五节-s / --seed99随机数种子保证可复现-m / --methodbruteforce低能态求解方法可选qaoa/bruteforce-p / --qaoa_depth2QAOA 电路深度 p-NS / --num_samples2**15采样的低能态数量在solve内部会被截断为不超过2^nn 为格维度最小可运行示例README 用分解187 17 × 11演示了默认流程python factoring_sqif/main.py -N 18750 比特随机整数 穷举法python factoring_sqif/main.py -b 50 --method bruteforce50 比特随机整数 QAOA深度 3python factoring_sqif/main.py -b 50 --method qaoa -p 3分解成功时程序会输出形如Found factors (707933, 882727) for 624911573291 using 11 qubits via bruteforce.的结果该行即来自仓库自带的 40 比特运行日志见下文第七节。四、核心超参数一格维度与lattice_parameterSchnorr 算法广受讨论的要点之一是它声称可以在仅随待分解数比特位宽亚线性增长的格维度下找到足够多的优质 SR-pair——这也正是论文将其作为量子优化起点的原因。但在经典密码学社区求解声称维度格上的 CVP 是否真能产生足够 SR-pair 尚无定论README 引用了 crypto.stackexchange 与相关讨论。在量子化方案中格维度直接决定了所需的量子比特数每个格维度对应一个 qubit。本项目用可配置常数lattice_parameter控制格维度$$ n \mathrm{lattice_parameter} \cdot \frac{\log_2(N)}{\log_2(\log_2(N))} $$该公式在 number_theory.py 中实现为integer_to_lattice_dimensiondef integer_to_lattice_dimension(N, c1): logN round(math.log2(N)) return int(c * int(logN) // int(round(math.log2(logN))))number_theory_test.py 给出了三个基准校验对应 README 提到的论文复现样例integer_to_lattice_dimension(1961) 3integer_to_lattice_dimension(48567227) 5integer_to_lattice_dimension(261980999226229) 8一般来说格维度越高找到足够多优质 SR-pair 的概率越大分解越可能成功但算法的时间/空间复杂度也随之上升。值得注意的一个实现细节是main.py 中SchnorrFactoringConfig.from_arxiv_paper_defaults的函数签名默认lattice_parameter1而论文复现样例run_arxiv_examples依次使用[1, 1.5, 1.5]命令行默认值则是1.5。读者可以根据目标位数自由调节-l。五、核心超参数二精度参数c与格构造精度参数c控制构造格所使用的基向量。原版 Schnorr 算法中格 $B_{n,c}$ 构造为$$ B_{n,c} \begin{bmatrix} f(1) 0 \dots 0\ 0 f(2) \dots 0\ \vdots \vdots \ddots \vdots\ 0 0 \dots f(n) \ N^c\ln{p_1} N^c\ln{p_2} \dots N^c\ln{p_n} \end{bmatrix} $$其中 $f(i)$$i1,\dots,n$是 $(\sqrt{\ln{p_1}}, \sqrt{\ln{p_2}}, \dots, \sqrt{\ln{p_n}})$ 的随机排列。本项目依据 arXiv:2212.12372对其做了两处修改$$ B_{n,c} \begin{bmatrix} f(1) 0 \dots 0\ 0 f(2) \dots 0\ \vdots \vdots \ddots \vdots\ 0 0 \dots f(n) \ \lfloor10^c\ln{p_1}\rceil \lfloor10^c\ln{p_2}\rceil \dots \lfloor10^c\ln{p_n}\rceil \end{bmatrix} $$其中 $f(i)$ 改为 $(\lceil 1/2 \rceil, \lceil 2/2 \rceil, \dots, \lceil n/2 \rceil)$ 的随机排列末行从 $N^c\ln{p_i}$ 改为取整后的 $\lfloor 10^c\ln{p_i}\rceil$。对应实现位于 closest_vector_problem.py 的sample函数它按上述公式构造一个 $(n1)\times n$ 的IntegerMatrix并生成稀疏目标向量 $t$——$t$ 只有最后一个分量非零取值为 $\lfloor 10^c\ln{N}\rceil$。该函数 docstring 注明其构造方式对应论文第 13 页并限制格维度 $n\le 25$超出会报NotImplemented。READme 指出格的行列式与精度参数 $c$ 正相关论文猜想找到接近目标向量的格向量的概率与 $c$ 正相关但作者也坦承这一推断的理由并不显然。因此-c是一个值得实验调参的对象默认值 4。六、核心超参数三平滑界 $B_2$ 与采样数量在 Schnorr 算法中格上的每个点都可映射为一对整数 $(u,v)$且按构造 $u$、$v$ 均为 $p_n$-光滑即其素因子不超过第 $n$ 个素数 $p_n$$n$ 为格维度。算法要求找到足够多的 SR-pair $(u,v)$使得 $u$、$v$ 都是 $p_n$-光滑且 $|u - v\cdot N|$ 是 $p_{B_2}$-光滑素因子不超过第 $B_2$ 个素数。这里的 $B_2$ 是另一个超参数通常至少取 $n$。经验法则SR-pair 的数量只需比平滑界 $B_2$ 多几个。本实现默认设置$$ B_2 2n^2 $$$$ \mathrm{num_sr_pairs_to_sample} B_2 2 $$其中 $n$ 为格维度。源码中的对应关系在 main.pylinear_eq_system_dimension 1 2 * n**2num_sr_pairs_to_sample linear_eq_system_dimension 1而solve内的实际光滑界取smooth_bound config.linear_eq_system_dimension - 1即 $2n^2 B_2$。以 40 比特运行日志为例格维度 $n11$ 时日志显示smooth bound 242、243维线性方程组、需要244个 SR-pair——恰好满足 $2\times 11^2242$、$1242243$、$2431244$。$B_2$ 对算法的影响存在权衡$B_2$ 越大满足 $|u - v\cdot N|$ 为 $B_2$-光滑的约束越容易满足找到有效 SR-pair 的概率越高但 $B_2$ 越大需要采样的 SR-pair 数量越多整体运行时间越长。光滑性判定实现在 number_theory.py 的is_smoothSR-pair 过滤在 hamiltonian.py 的sr_pairs_from_uv_pairs对每个 UV-pair 检查abs(u - N*v)是否光滑。此外 number_theory.py 的pairs_to_sr_possiblities还实现了一个技巧按最大素因子下标排序 SR-pair一旦前缀数量超过该下标即可构成有效的方程组前缀。七、完整流水线从 CVP 到因子solve主循环main.py 的solve函数是整条流水线的核心其迭代逻辑可归纳为五步每一步都对应独立模块构造格与目标向量调用 closest_vector_problem.py 的cvp.sample(N, n, c, rs)得到 $(n{}1)\times n$ 的格B与目标向量tBabai 近似最近向量调用cvp.babai_algorithm(B, t)closest_vector_problem.py。该函数先用 fpylll 以delta0.75对格基做 LLL 规约再通过GSO.Mat(D).babai(t)得到近似解权重w、残差向量与rounding_direction决定后续在超立方体中搜索的方向封装为BabaiResult构造问题哈密顿量hamiltonian.hamiltonian_from_babai_result(qs, babai_result)hamiltonian.py把在 Babai 近似解附近寻找更优格向量编码为 Ising 型哈密顿量 $H \sum_j (r_j - \sum_i X_i D_{ji})^2$其中 $X_i$ 为投影算子$D$ 为 LLL 规约后的格基$r$ 为残差向量采样低能态并过滤 SR-pair按method选择bruteforce或qaoa得到低能态整数表示随后依次经过integer_states_to_lattice_vectors→u_v_pairs_from_lattice_vectors→sr_pairs_from_uv_pairs均位于 hamiltonian.py把低能态映射回格向量、再映射回 $(u,v)$ 光滑对、最后过滤出 SR-pair 并入集合循环直到收集够num_sr_pairs_to_sample个或达到max_lattice_iterations次迭代解线性方程组提取因子把 SR-pair 转成指数差向量schnorr.sr_pair_to_differences在GPUCuPy上做模 2 高斯消元schnorr.py 的_gaussian_elementation_Z2并枚举零空间_null_space得到指数组合再由exponents_to_candidates构造候选因子并math.gcd(p, N)校验——一旦得到非平凡因子即返回SchnorrFactoringResult。仓库results/目录下附带多组真实运行日志如 40bit_l1_bruteforce.txt、70bit_qaoa.txt、128bit_l1_bruteforce.txt等文件名即标注了比特位宽与lattice_parameter取值。以 40 比特日志为例可观察到典型行为每轮迭代从 2048 个 UV-pair 中过滤出 024 个 SR-pair40 轮迭代累计 247/244 个 SR-pair 后停止随后在 Z₂ 零空间搜索中成功找到因子707933与882727624911573291 707933 × 882727全程仅使用 11 个量子比特。八、寻找哈密顿量低能态的三种途径README 依次介绍了三种求解低能态即寻找接近目标向量的格向量的方案。8.1 暴力枚举Brute Force最简单的方法穷举全部 $2^n$ 个比特串作为输入态$n$ 为量子比特数/格维度。复杂度随 $n$ 指数增长并不具备可扩展性其作用是假设存在完美量子优化器时验证其余经典归约的正确性。运行方式python factoring_sqif/main.py -b 50 --method bruteforce实现上hamiltonian.py 的brute_force_lowest_energy_states对全部 $2^n$ 个整数态调用energy_from_integer_states计算能量并稳定排序取前num_samples个。energy_from_integer_states对单比特项Z与双比特项ZZ分别用 numba JIT 批量求值双比特项通过 CuPy 上 GPU 加速见_in_batches的cudaTrue分支。8.2 QAOA论文主推方法QAOA 是启发式算法性能取决于两个可配置的启发式因素电路深度 $p$默认 $p2$可通过--qaoa_depth调大。电路构造见 qaoa.py 的generate_qaoa_circuit先对所有 qubit 施加 Hadamard再交替叠加 $p$ 层gamma由哈密顿量各项分解为Z**与ZZ**门见get_gamma_layer与beta对所有 qubit 施加X**见get_beta_layer外层经典优化器用于寻找变分电路的最优参数。论文声称使用 Model Gradient DescentReCirq 中有对应实现但 README 说明作者尝试开箱即用的 MGD 实现并未收敛因此在 qaoa.py 的find_optimal_parameters中改为调用 ReCirq 的minimize并以BFGS作为优化方法代码注释保留了 TODO说明仍在调研 MGD 不收敛的原因欢迎读者自行尝试其他优化方法。QAOA 采样的完整路径为sample_low_energy_statesqaoa.py生成电路 → BFGS 优化参数 → 用qsimcirq.QSimSimulator8 线程重复采样 10000 次 → 按频率返回比特串。运行示例python factoring_sqif/main.py -b 50 --method qaoa -p 3此外 qaoa.py 还提供expected_energy_landscape与plot_energy_landspace可在 $(\gamma, \beta)\in[0,\pi]^2$ 网格上绘制期望能量热力图用于直观观察代价函数曲面——main.qaoa_main()10 比特示例问题演示了这一可视化流程。8.3 DCQF未来改进方向DCQF 是另一种启发式算法arXiv:2301.11005与 QAOA 不同它不需要外层经典优化循环。README 明确指出DCQF 的具体细节以论文为准本仓库尚未集成其实现留作未来改进方向。九、测试与验证仓库自带两组 pytest 测试是验证经典归约正确性的关键证据number_theory_test.py校验格维度公式1961→3、48567227→5、261980999226229→8hamiltonian_test.py覆盖三个层面——test_hamiltonian用 test_data/3q/hamiltonian.txt 与10q/下预计算的低能态基准比对暴力枚举结果test_hamiltonian_construction验证hamiltonian_from_babai_result与参考哈密顿量完全一致test_u_v_pairs_from_integer_states与test_sr_pairs_from_uv_pairs验证低能态 → 格向量 → (u,v) 对 → SR-pair 的逐级映射以 N1961 为例UV 对(1800,1),(1944,1),(2025,1),(3645,2)中仅前三个在平滑界 15 下构成 SR-pair。十、复现论文样例与进一步探索main.py 的run_arxiv_examples内置了论文的三个复现目标待分解数 Nlattice_parameter精度参数 c对应格维度196111.53485672271.5452619809992262291.548有兴趣的读者可以在此基础上围绕 README 与源码指出的开放问题做进一步实验调节-l、-c、-p观察 SR-pair 产出率与运行时间的变化尝试更换 qaoa.py 中的外层优化器如复现论文的 MGD或按 README 的启发探索比超立方体搜索更好的 CVP→量子优化归约方式。参考资源本文相关的背景文献均为 README 原文引用此处以文本形式列出Sublinear Quantum Integer FactoringarXiv:2212.12372——本实现所依据的核心论文A note on Integer Factorization using LatticesA. VeraarXiv:1003.5461Schnorrs Approach to Factoring via LatticesLéo DucasCWI RISC 讲座幻灯片SchnorrGate - Testing Schnorrs factoring Claim in SageMathLéo Ducas——对 Schnorr 格分解主张的 SageMath 检验DCQF 方法论文arXiv:2301.11005——README 中留作未来改进的量子优化方案。【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考