《A Gentle Introduction to Lattice-Based Cryptography》（格密码学温和入门）是密码学界知名学者、滑铁卢大学（University of Waterloo）教授Alfred Menezes编写的一份高质量开源讲义。
这份讲义专门为高年级本科生和初入学的研究生设计，旨在用最通俗易懂、循序渐进的方式，揭开后量子密码学（Post-Quantum Cryptography, PQC）中“格密码”的神秘面纱。
练习 4.1
编写一个程序，寻找满足以下实例的所有解
：
思路：对于这种小规模的 LWE 实例，我们依旧可以使用暴力搜索。但是，如果同时搜索（共
种可能）和
（共
种可能），总的组合数会达到
。
我们可以利用公式的等价变形来极大缩减搜索空间：
由于误差向量 $e$ 的每一个分量都必须落在临界的区间内（即模 $53$ 意义下的
）。
我们只需要对秘密向量的所有可能进行网格搜索（只需搜索
万个点）：
对每个候选的
，计算出对应的误差
。
检查这个
的每个分量是否都满足临界条件：
。
如果满足，则该
为可行解，对应的
也能直接算出来。
完整代码如下所示
import numpy as np # ==================== 1. 初始化输入数据 ==================== A = np.array([ [24, 4, 37], [51, 41, 17], [ 2, 11, 13], [44, 52, 50], [ 1, 0, 2] ]) b = np.array([5, 3, 12, 10, 6]) m = 5 n = 3 q = 53 B = 2 # ==================== 2. 生成 s 的全部搜索空间 ==================== # s 的每个分量取值在 [0, q-1] s_vals = np.arange(q) # 使用 meshgrid 生成 3 维网格，并重塑为 (53^3, 3) grid = np.meshgrid(s_vals, s_vals, s_vals, indexing='ij') S_space = np.stack(grid, axis=-1).reshape(-1,3) # ==================== 3. 批量计算并求解误差 e ==================== # 计算 A * s (mod q) # A 形状为 (5, 3)，S_space.T 形状为 (3, 148877) -> AS 形状为 (5, 148877) AS = np.dot(A, S_space.T) % q # 计算误差 e = (b - As) (mod q)，结果形状为 (5, 148877) E_space = (b.reshape(-1,1) - AS) % q # ==================== 4. 筛选满足短整数约束的列 ==================== # 在模 53 意义下，满足 |e_i| <= 2 的合法误差取值集合为 {0, 1, 2, 51, 52} vaild_errors = [0, 1, 2, q-2, q-1] # 使用 np.isin 检查 E_space 中每个元素是否在合法集合中 # np.isin 得到一个形状相同的布尔矩阵，再用 np.all(..., axis=0) 确保该列的所有 5 个误差全都合规 mask1 = np.isin(E_space, vaild_errors) mask = np.all(mask1, axis=0) # ==================== 5. 输出最终解 (s, e) ==================== matching_s = S_space[mask] matching_e = E_space[:, mask].T # 将模 53 下的误差 [51, 52] 映射回负数 [-2, -1] 便于直观观察 matching_e_mapped = np.where(matching_e > q // 2, matching_e - q, matching_e) print(f"共找到 {len(matching_s)} 组解：\n") for i in range(len(matching_s)): print(f"解对 {i+1}:") print(f" s = {matching_s[i]}") print(f" e = {matching_e_mapped[i]}")练习 4.2
寻找满足以下实例的所有解
：
具体思路可以参考上一题的解题思路
import numpy as np # ==================== 1. 初始化数据 ==================== A = np.array([ [ 5, 22, 14, 47], [45, 25, 17, 49], [39, 14, 26, 51], [31, 9, 46, 24] ]) b = np.array([36, 14, 46, 30]) q = 53 B = 3 # 边界 beta = 3 # ==================== 2. 生成短秘密 s 的搜索空间 ==================== s_vals = np.array(range(-B, B + 1)) # [-3, -2, -1, 0, 1, 2, 3] grid = np.meshgrid(s_vals, s_vals, s_vals, s_vals, indexing='ij') S_space = np.stack(grid, axis=-1).reshape(-1,4) # ==================== 3. 批量计算误差 e ==================== AS = np.dot(A, S_space.T) % q E_space = (b.reshape(-1,1) - AS) % q # ==================== 4. 筛选合格的误差 e ==================== # 合法误差值在 [-3, 3] 区间，模 53 映射为 {0, 1, 2, 3, 50, 51, 52} vaild_errors = [0, 1, 2, 3, q-3, q-2, q-1] mask = np.all(np.isin(E_space, vaild_errors),axis=0) # ==================== 5. 输出结果 ==================== matching_s = S_space[mask] matching_e = E_space[:, mask].T matching_e_mapped = np.where(matching_e > q // 2, matching_e - q, matching_e) print(f"共找到 {len(matching_s)} 组解：\n") for i in range(len(matching_s)): print(f"解对 {i+1}:") print(f" s = {matching_s[i]}") print(f" e = {matching_e_mapped[i]}")
