《A Gentle Introduction to Lattice-Based Cryptography》格密码学温和入门是密码学界知名学者、滑铁卢大学University of Waterloo教授Alfred Menezes编写的一份高质量开源讲义。这份讲义专门为高年级本科生和初入学的研究生设计旨在用最通俗易懂、循序渐进的方式揭开后量子密码学Post-Quantum Cryptography, PQC中“格密码”的神秘面纱。目录练习3.1步骤一构建搜索空间Generate Search Space步骤二剔除无意义的平凡解Filter Zero Vector步骤三批量矩阵乘法与取模Batch Matrix Multiplication步骤四筛选满足条件的解Find Exact Solutions练习3.2步骤一构建全量解空间生成 5 维网格步骤二高维批量矩阵乘法计算 步骤三广播机制对比与掩码筛选Masking Filter练习3.1编写一个程序寻找满足以下实例的所有解步骤一构建搜索空间Generate Search Space每个分量的取值范围是一共有种可能的整数取值。因为是维向量所以总的搜索空间大小为vals np.array(range(-B, B1)) # [-5, -4, ..., 5] # 用 meshgrid 生成 6 维网格再 reshape 成 (1771561, 6) 的二维矩阵 grid np.meshgrid(vals, vals, vals, vals, vals, vals, indexingij) Z_space np.stack(grid, axis-1).reshape(-1, 6)步骤二剔除无意义的平凡解Filter Zero VectorSIS 问题要求解必须是非零的如果是全向量恒有这在密码学上是没有意义的平凡解。mask1 np.any(Z_space ! 0, axis1) # 找出不全为 0 的行 Z_filtered Z_space[mask1] # 过滤后剩余 1,771,560 个候选向量步骤三批量矩阵乘法与取模Batch Matrix Multiplication我们要验证所有的。在 NumPy 中将大小为与大小为做矩阵乘法。得到的结果矩阵大小为。每一列对应一个候选向量乘以后的维结果。AZ_mod np.dot(A, Z_filtered.T) % q步骤四筛选满足条件的解Find Exact Solutions寻找矩阵中整列都为 0的列。这代表该满足所有 4 个同余方程。mask2 np.all(AZ_mod 0, axis0) # 沿着第 0 轴行检查 4 个方程是否都为 True res Z_filtered[mask2] # 提取出最终满足条件的短向量 z完整程序如下所示import numpy as np A np.array([ [16, 12, 19, 0, 7, 3], [12, 6, 5, 1, 20, 11], [14, 9, 14, 15, 1, 10], [ 1, 0, 16, 19, 17, 2] ]) q 23 B 5 # 一次性生成 6 维空间中所有 1,771,561 个点的组合 vals np.array(range(-B, B1)) #print(vals) grid np.meshgrid(vals, vals, vals, vals, vals, vals, indexingij) # print(grid) Z_space np.stack(grid,axis-1).reshape(-1,6) # print(Z_space) # 过滤掉全零向量 mask1 np.any(Z_space ! 0, axis1) # print(mask1) Z_filtered Z_space[mask1] # print(Z_filtered) # print(Z_filtered.T.shape) # 批量矩阵乘法并求模 AZ_mod np.dot(A, Z_filtered.T) % q # 寻找 4 个方程余数全为 0 的行 mask2 np.all(AZ_mod0, axis0) res Z_filtered[mask2] print(res)练习3.2编写一个程序寻找满足以下实例的所有解步骤一构建全量解空间生成 5 维网格既然每个分量有种可能的取值到那么维向量的所有可能组合一共有np.meshgrid(..., indexingij)生成了 5 个高维坐标矩阵。np.stack(..., axis-1)将这 5 个坐标矩阵在最后一个维度拼接起来。.reshape(-1, 5)将其铺平最终得到一个形状为(161051, 5)的二维矩阵B2。此时B2的每一行都代表一个潜在的解向量。步骤二高维批量矩阵乘法计算有了所有可能的之后我们需要验证每一个是否满足。你的代码利用了矩阵乘法一次性算完了所有 16 万多个组合ans np.dot(A, B2.T) % q的形状是(3, 5)B2.T的形状是(5, 161051)。相乘并取模后得到的ans形状为(3, 161051)。ans的每一列就是对应的候选向量经过映射后得到的维向量。步骤三广播机制对比与掩码筛选Masking Filter最后一步我们要找出哪些列算出来的结果恰好等于。你的代码转置了ansmask np.all(ans.T b, axis1)ans.T的形状变回了(161051, 3)。ans.T b利用了 NumPy 的广播机制Broadcasting。它将b形状为(3,)自动广播为(161051, 3)的形状并将两张表里的每一个元素一一进行对比生成一个布尔矩阵。np.all(..., axis1)沿着列方向即每一个候选解对应的 3 个方程结果进行逻辑“与AND”运算。只有当某个解的 3 个同余方程全部计算正确时对应位置才会保留为True。最后用这个布尔遮罩mask去索引初始的解空间B2瞬间过滤出所有符合条件的短向量res B2[mask]完整代码如下所示import numpy as np # 导入初始数据 A np.array([ [7, 9, 6, 27, 15], [22, 9, 22, 19, 24], [0, 2, 16, 19, 11] ]) n, m A.shape q 29 B 5 b np.array([13, 25, 16]) # 将得到的数组摊开 vals np.array(range(-B, B1)) # print(B1) B1 np.meshgrid(vals, vals, vals, vals, vals, indexingij) # print(B1) B2 np.stack(B1,axis-1).reshape(-1,5) # print(B2.shape) # 矩阵相乘 ans np.dot(A,B2.T) % q # print(ans) # 筛选符合的结果 mask np.all(ans.T b, axis1) # print(mask) res B2[mask] print(res)