Skip to Content
文档UnitaryLab 算法用户手册密码学算法

密码学算法

概述

unitarylab_algorithms.cryptology 包含三个量子密码学算法，展示了量子计算在数论与隐藏周期问题上相对于经典方法的优势：

算法类求解问题
Shor 质因数分解算法ShorAlgorithm合数 的质因数分解
离散对数算法DiscreteLogAlgorithm求解
Simon 周期掩码算法SimonAlgorithm在 中找隐藏掩码

三个算法均继承自 unitarylab_algorithms.algo_base.BaseAlgorithm，.run() 返回值遵循统一结构：

{
    'status': 'ok' | 'failed',   # 是否成功，由算法自身的验证逻辑决定
    'circuit_path': '/path/to/xxx_circuit.svg',  # 线路图完整路径；部分算法在无需构建线路的分支下为 None
    'plot': [{'format': 'txt', 'filename': 'xxx_algorithm_result.txt'}],  # 结果文本文件，filename 为**不含目录的文件名**
    'circuit': <Circuit 对象 或 None>,
    # ... 以下为各算法通过 update_output() 附加的专属字段（见各小节）
}

Shor 质因数分解算法

背景

Shor 算法以多项式时间复杂度将合数 分解为质因数。经典最优算法（如通用数域筛法）需要次指数时间，而 Shor 算法在量子计算机上可在 时间内完成。

该算法结合了：

  1. 基于量子傅里叶变换（QFT）的量子周期查找
  2. 从周期中提取质因数的经典后处理

导入

from unitarylab_algorithms import ShorAlgorithm

.run() 参数

def run(self, N: int, method: str = "matrix", max_retries: int = 15,
        backend='torch', device='cpu', dtype=np.complex128) -> Dict[str, Any]
参数类型默认值说明
Nint— （必填）待分解的合数（如 15、21）
methodstr'matrix'求解方法：'matrix' 或 'operator'，传入其他值会抛出 ValueError
max_retriesint15单次 .run() 调用内，对基底 重新采样并重试的最大次数

parameters.json（网页端参数面板）仅暴露 N（取值范围 2–300）与 method 两个参数，不提供 max_retries 的 UI 输入；如需自定义重试次数，需直接调用 Python API。

执行流程

  1. 经典预检：若 N 为偶数，直接返回因子 [2, N//2]；若随机采样的基底 a 与 N 存在公因子，直接经典分解——这两种情形下不构建量子线路，circuit_path 为 None。
  2. 否则构建相位估计线路（method='matrix' 使用受控置换矩阵；method='operator' 使用模乘法器线路，量子比特数更多但线路更”物理”），执行并测量。
  3. 对测量结果做连分数展开提取周期 ，若 为偶数且 ，计算 得到因子。
  4. 若单次尝试未能提取到有效因子，重新采样基底 并重复，最多 max_retries 次。

返回值

与其他 BaseAlgorithm 子类一致，status 真实反映算法是否成功找到因子（经典捷径分支与量子分支成功时均为 'ok'；耗尽 max_retries 后未成功则为 'failed'）。update_output() 附加的字段依分支而异：

# 经典捷径分支（N 为偶数 / 随机基底与 N 有公因子）
{'factors': [p, q], 'period': None, 'Selected base': a_or_None}

# 量子分支成功
{
    'factors': [p, q], 'period': r, 'Selected base': a,
    'Computation time (s)': 0.1234, 'Measurement': 42, 'Total qubits': 12,
}

# 重试耗尽仍失败
{
    'factors': None, 'period': None, 'Selected base': a,
    'Computation time (s)': 0.1234, 'Measurement': 42, 'Total qubits': 12,
}

示例

from unitarylab_algorithms import ShorAlgorithm
 
algo = ShorAlgorithm()
result = algo.run(N=15)
print(result['status'])          # 'ok'
print(result['factors'])         # 例如 [3, 5]

快速演示

from unitarylab_algorithms.cryptology.shor.algorithm import test
test(N=15, method='matrix', max_retries=15)

注意事项

  • N 必须是具有至少两个不同质因子的合数。传入 1 会在首次尝试内部调用 random.randint(2, N - 1)（即 random.randint(2, 0)）时直接抛出 ValueError: empty range for randrange()，而非进入重试循环；传入 2（或其他偶数）会被 N % 2 == 0 分支直接短路，立即以 status='ok' 返回 factors=[2, N//2]，同样不会进入重试循环。只有传入奇质数（如 7）才会真正进入重试循环，并在耗尽 max_retries 次尝试后以 status='failed' 结束。
  • 'matrix' 方法直接构造受控置换矩阵，量子比特数较少，适合小 ；'operator' 方法使用模乘法器线路，量子比特数更多。
  • N 为偶数或随机基底恰好与 N 有公因子时，算法走经典捷径直接返回，不会构建/保存量子线路（circuit_path=None），这种情况下不能用返回值判断”量子算法是否成功”。
  • status 真实反映因子分解是否成功，可放心用于业务逻辑判断（这与 fundamental_algorithm 中部分算法「status 恒为 'ok'」的情况不同）。

离散对数算法

背景

离散对数问题：给定 、 和 ，求 使得 。这是许多经典密码系统（如 Diffie–Hellman、DSA）的安全基础。量子算法利用量子相位估计和连分数后处理高效求解，且仅执行一次量子线路（不像 Shor 算法那样有重试机制）。

导入

from unitarylab_algorithms import DiscreteLogAlgorithm

.run() 参数

def run(self, g: int, y: int, P: int,
        backend='torch', device='cpu', dtype=np.complex128) -> Dict[str, Any]
参数类型默认值说明
gint— （必填）幂运算的底数，需与 P 互质
yint— （必填）目标值，需与 P 互质
Pint— （必填）模数（通常为质数）

g、y、P 在 .run() 中均无默认值，必须显式传入。若 或 ，会直接抛出 ValueError("g and y must be coprime with P")。

模块级 test() 函数与网页端 parameters.json 的默认示例不一致：test() 默认 g=3, y=6, P=7（对应 ，答案 ）；而 parameters.json 的默认值是 g=3, y=13, P=17。下方示例采用与 test() 一致的 g=3, y=6, P=7。

返回值

status 反映真实成功/失败（is_success = found_x is not None）：

{
    'status': 'ok',
    'circuit_path': '/path/to/discrete_logarithm_algorithm_circuit.svg',
    'plot': [{'format': 'txt', 'filename': 'discrete_logarithm_algorithm_result.txt'}],
    'circuit': <Circuit>,
    'Computation time (s)': 0.0456,
    'Detected period r': 3,
    'Found x': 3,
}

若连分数后处理未能找到满足 的解，status='failed'，Found x' 为 None。

示例

from unitarylab_algorithms import DiscreteLogAlgorithm
 
# 求解 3^x ≡ 6 (mod 7)，答案为 x = 3
algo = DiscreteLogAlgorithm()
result = algo.run(g=3, y=6, P=7)
print(result['status'])    # 'ok'
print(result['Found x'])   # 3

快速演示

from unitarylab_algorithms.cryptology.discrete_log.algorithm import test
test(g=3, y=6, P=7)

注意事项

  • g、y 必须同时与 P 互质，否则在参数准备阶段直接抛出 ValueError，不会构建线路。
  • 与 Shor 算法不同，该算法没有重试机制——单次量子测量若未能通过连分数后处理找到解，直接返回 status='failed'。
  • 网页端参数面板默认值（g=3, y=13, P=17）与源码 test()/__main__ 的默认值（g=3, y=6, P=7）不同，调用 Python API 时请以实际传参为准。

Simon 周期掩码算法

背景

Simon 问题：给定函数 ，已知存在隐藏掩码 满足 ，求 。经典算法需要指数级查询次数，而 Simon 算法仅需 次量子查询加上经典高斯消元即可求解。

导入

from unitarylab_algorithms import SimonAlgorithm

.run() 参数

def run(self, s: str = "1010", backend='torch', device='cpu', dtype=np.complex128) -> Dict[str, Any]
参数类型默认值说明
sstr'1010'表示待查找隐藏掩码的二进制字符串，长度即比特数

.run() 自身的默认值 '1010' 与模块级 test() 函数及网页端 parameters.json 的默认值 '1101' 不一致。直接调用 SimonAlgorithm().run()（不传 s）会使用 '1010'；调用 test() 或通过网页端运行则默认使用 '1101'。

返回值

{
    'status': 'ok',
    'circuit_path': '/path/to/simon_algorithm_circuit.svg',
    'plot': [{'format': 'txt', 'filename': 'simon_algorithm_result.txt'}],
    'circuit': <Circuit>,
    'Computed s': '1101',
    'Valid states': 8,
    'computation time (s)': 0.0321,   # 注意：键名为小写 computation，且未四舍五入（与另外两个算法的 'Computation time (s)' 不同）
    'Register size': 4,
    'Equations': 3,
}

示例

from unitarylab_algorithms import SimonAlgorithm
 
algo = SimonAlgorithm()
result = algo.run(s='1101')
print(result['status'])       # 'ok'
print(result['Computed s'])   # '1101'

快速演示

from unitarylab_algorithms.cryptology.simon.algorithm import test
test(s='1101')

注意事项

  • s 必须是长度为 的二进制字符串（如 '1010' 对应 ），且必须至少包含一个 '1'——全零字符串（如 '0000'）会直接触发 ValueError("Secret string s cannot be all zeros")，算法不会运行到底。
  • 输出字典中的计算耗时字段名为小写的 'computation time (s)'，且是未经四舍五入的原始浮点数，与 Shor / 离散对数算法中大写、已四舍五入到 4 位小数的 'Computation time (s)' 写法不一致，读取时需注意大小写。
  • status 由 found_s == s 的真实比对结果决定，可用于判断本次测量-求解是否成功还原出掩码 。
最后更新于
API 使用总览基础量子算法