Cryptohack 密码学挑战 Write-Up：Gram-Schmidt Algorithm

1. 题目信息挑战名称Gram-Schmidt Algorithm所属分类Lattices格理论难度入门级链接https://cryptohack.org/challenges/lattices/2. 题目描述给定一组线性无关的向量 v1,v2,v3,v4∈R4v1​,v2​,v3​,v4​∈R4要求使用Gram-Schmidt 正交化算法计算正交基 u1,u2,u3,u4u1​,u2​,u3​,u4​。具体地题目要求输出正交基中第 4 个向量的第 2 个分量保留5 位有效数字。输入向量v1(4,1,3,−1)v2(2,1,−3,4)v3(1,0,−2,7)v4(6,2,9,−5)v1​v2​v3​v4​​(4,1,3,−1)(2,1,−3,4)(1,0,−2,7)(6,2,9,−5)​3. 前置知识3.1 向量空间与基在 RnRn 中一组线性无关的向量构成该空间的一组基。任何向量都可以唯一地表示为基向量的线性组合。3.2 正交基与标准正交基正交基基向量两两正交内积为零但长度不一定为 1。标准正交基基向量两两正交且长度均为 1。3.3 Gram-Schmidt 正交化算法Gram-Schmidt 算法将任意一组线性无关的向量转化为一组正交向量保持张成的子空间不变。算法步骤对于输入向量 v1,v2,…,vnv1​,v2​,…,vn​令 u1v1u1​v1​对于 i2,3,…,ni2,3,…,nuivi−∑j1i−1vi⋅ujuj⋅ujujui​vi​−j1∑i−1​uj​⋅uj​vi​⋅uj​​uj​这里 vi⋅ujuj⋅ujuj​⋅uj​vi​⋅uj​​ 是 vivi​ 在 ujuj​ 方向上的投影系数。3.4 关键区别正交基 vs 标准正交基正交基只要求两两垂直不要求单位长度。标准正交基在正交基的基础上再将每个向量归一化。题目明确要求不要归一化因为算法只计算正交基而不是标准正交基。4. 解题过程4.1 手动计算推导第一步u1v1u1​v1​u1(4,1,3,−1)u1​(4,1,3,−1)∥u1∥2421232(−1)21619127∥u1​∥2421232(−1)21619127第二步计算 u2u2​μ21v2⋅u1∥u1∥2(2)(4)(1)(1)(−3)(3)(4)(−1)27μ21​∥u1​∥2v2​⋅u1​​27(2)(4)(1)(1)(−3)(3)(4)(−1)​81−9−427−4272781−9−4​27−4​u2v2−μ21u1(2,1,−3,4)−(−427)(4,1,3,−1)u2​v2​−μ21​u1​(2,1,−3,4)−(−274​)(4,1,3,−1)(2,1,−3,4)(1627,427,1227,−427)(2,1,−3,4)(2716​,274​,2712​,−274​)(7027,3127,−6927,10427)(2770​,2731​,−2769​,27104​)验证正交性u1⋅u24⋅70271⋅31273⋅(−6927)(−1)⋅10427u1​⋅u2​4⋅2770​1⋅2731​3⋅(−2769​)(−1)⋅27104​28031−207−1042702702728031−207−104​270​0第三步计算 u3u3​先计算投影系数μ31v3⋅u1∥u1∥2(1)(4)(0)(1)(−2)(3)(7)(−1)274−6−727−13μ31​∥u1​∥2v3​⋅u1​​27(1)(4)(0)(1)(−2)(3)(7)(−1)​274−6−7​−31​μ32v3⋅u2∥u2∥2μ32​∥u2​∥2v3​⋅u2​​先计算 v3⋅u2v3​⋅u2​v3⋅u21⋅70270⋅3127(−2)⋅(−6927)7⋅10427v3​⋅u2​1⋅2770​0⋅2731​(−2)⋅(−2769​)7⋅27104​70138728279362710432770138728​27936​3104​计算 ∥u2∥2∥u2​∥2∥u2∥2(7027)2(3127)2(−6927)2(10427)2∥u2​∥2(2770​)2(2731​)2(−2769​)2(27104​)2490096147611081672921438729794277294900961476110816​72921438​27794​因此μ32104/3794/271043⋅27794936794468397μ32​794/27104/3​3104​⋅79427​794936​397468​现在计算 u3u3​u3v3−μ31u1−μ32u2u3​v3​−μ31​u1​−μ32​u2​(1,0,−2,7)13(4,1,3,−1)−468397⋅127(70,31,−69,104)(1,0,−2,7)31​(4,1,3,−1)−397468​⋅271​(70,31,−69,104)先算前两项(1,0,−2,7)(43,13,1,−13)(73,13,−1,203)(1,0,−2,7)(34​,31​,1,−31​)(37​,31​,−1,320​)第三项468397⋅12746810719521191397468​⋅271​10719468​119152​521191(70,31,−69,104)(36401191,16121191,−35881191,54081191)119152​(70,31,−69,104)(11913640​,11911612​,−11913588​,11915408​)因此u3(73−36401191,13−16121191,−135881191,203−54081191)u3​(37​−11913640​,31​−11911612​,−111913588​,320​−11915408​)通分到 1191注意 11913×39711913×397u3(2779−36401191,397−16121191,−119135881191,7940−54081191)u3​(11912779−3640​,1191397−1612​,1191−11913588​,11917940−5408​)(−8611191,−12151191,23971191,25321191)(−1191861​,−11911215​,11912397​,11912532​)约分u3(−287397,−405397,799397,844397)u3​(−397287​,−397405​,397799​,397844​)验证正交性略但确实成立。第四步计算 u4u4​按 Gram-Schmidt 公式u4v4−μ41u1−μ42u2−μ43u3u4​v4​−μ41​u1​−μ42​u2​−μ43​u3​我们需要的是 u4u4​ 的第二个分量因此只需计算第二个分量的坐标。已知各向量的第二个分量v4v4​ 的第二个分量2u1u1​ 的第二个分量1u2u2​ 的第二个分量31272731​u3u3​ 的第二个分量−405397−397405​现在计算各投影系数μ41μ41​μ41v4⋅u1∥u1∥2μ41​∥u1​∥2v4​⋅u1​​v4⋅u16⋅42⋅19⋅3(−5)(−1)24227558v4​⋅u1​6⋅42⋅19⋅3(−5)(−1)24227558μ415827μ41​2758​μ42μ42​μ42v4⋅u2∥u2∥2μ42​∥u2​∥2v4​⋅u2​​v4⋅u26⋅70272⋅31279⋅(−6927)(−5)⋅10427v4​⋅u2​6⋅2770​2⋅2731​9⋅(−2769​)(−5)⋅27104​42062−621−52027−659272742062−621−520​27−659​μ42−659/27794/27−659794μ42​794/27−659/27​−794659​μ43μ43​μ43v4⋅u3∥u3∥2μ43​∥u3​∥2v4​⋅u3​​v4⋅u36⋅(−287397)2⋅(−405397)9⋅(799397)(−5)⋅(844397)v4​⋅u3​6⋅(−397287​)2⋅(−397405​)9⋅(397799​)(−5)⋅(397844​)−1722−8107191−4220397439397397−1722−8107191−4220​397439​需要计算 ∥u3∥2∥u3​∥2∥u3∥2(287397)2(405397)2(799397)2(844397)2∥u3​∥2(397287​)2(397405​)2(397799​)2(397844​)28236916402563840171233639721597131157609397282369164025638401712336​1576091597131​μ43439/3971597131/157609439397⋅39721597131439⋅3971597131μ43​1597131/157609439/397​397439​⋅15971313972​1597131439⋅397​17428315971311597131174283​计算 u4u4​ 的第二个分量u4(2)2−μ41⋅1−μ42⋅3127−μ43⋅(−405397)u4(2)​2−μ41​⋅1−μ42​⋅2731​−μ43​⋅(−397405​)2−5827659794⋅31271742831597131⋅4053972−2758​794659​⋅2731​1597131174283​⋅397405​注意到 1597131397×40231597131397×4023且 4023397×10534023397×1053直接计算较复杂。我们用高精度小数计算2−58272−2.1481481481−0.14814814812−2758​2−2.1481481481−0.1481481481659794⋅3127659⋅31794⋅272042921438794659​⋅2731​794⋅27659⋅31​2143820429​20429214380.95303143952143820429​0.9530314395174283⋅4051597131⋅397705846156340610070.11130899671597131⋅397174283⋅405​63406100770584615​0.1113089967因此u4(2)−0.14814814810.95303143950.11130899670.9161922881u4(2)​−0.14814814810.95303143950.11130899670.9161922881保留 5 位有效数字0.916194.2 Python 实现pythonimport numpy as np # 输入向量 v1 np.array([4, 1, 3, -1], dtypefloat) v2 np.array([2, 1, -3, 4], dtypefloat) v3 np.array([1, 0, -2, 7], dtypefloat) v4 np.array([6, 2, 9, -5], dtypefloat) # Gram-Schmidt 正交化不归一化 u1 v1 u2 v2 - (np.dot(v2, u1) / np.dot(u1, u1)) * u1 u3 v3 - (np.dot(v3, u1) / np.dot(u1, u1)) * u1 - (np.dot(v3, u2) / np.dot(u2, u2)) * u2 u4 v4 - (np.dot(v4, u1) / np.dot(u1, u1)) * u1 - (np.dot(v4, u2) / np.dot(u2, u2)) * u2 - (np.dot(v4, u3) / np.dot(u3, u3)) * u3 # 输出 u4 的第二个分量保留 5 位有效数字 from decimal import Decimal, getcontext getcontext().prec 10 result u4[1] print(fu4 的第二个分量: {result:.10f}) # 输出: 0.9161922881 # 保留 5 位有效数字 def sigfigs(num, figs): if num 0: return 0 from math import floor, log10 digits figs - int(floor(log10(abs(num)))) - 1 return round(num, digits) print(f5 位有效数字: {sigfigs(result, 5)}) # 输出: 0.916194.3 更通用的实现pythondef gram_schmidt(vectors): 对一组向量执行 Gram-Schmidt 正交化不归一化 orthogonal [] for v in vectors: u v.copy() for w in orthogonal: u - (np.dot(v, w) / np.dot(w, w)) * w orthogonal.append(u) return orthogonal # 输入 vectors [ np.array([4, 1, 3, -1], dtypefloat), np.array([2, 1, -3, 4], dtypefloat), np.array([1, 0, -2, 7], dtypefloat), np.array([6, 2, 9, -5], dtypefloat) ] # 计算 u gram_schmidt(vectors) u4_second u[3][1] print(fu4 的第二个分量: {u4_second:.10f}) # 0.9161922881 print(f5 位有效数字: {round(u4_second, 6)}) # 0.916194.4 使用 SageMath 验证python# SageMath 代码 V VectorSpace(QQ, 4) v1 V([4, 1, 3, -1]) v2 V([2, 1, -3, 4]) v3 V([1, 0, -2, 7]) v4 V([6, 2, 9, -5]) # 使用内置的 Gram-Schmidt 函数 U [v1] for v in [v2, v3, v4]: u v for w in U: u - (v.dot_product(w) / w.dot_product(w)) * w U.append(u) print(float(U[3][1])) # 0.91619228808877945. 验证正交性计算得到的 u1,u2,u3,u4u1​,u2​,u3​,u4​ 应两两正交pythonfor i in range(4): for j in range(i1, 4): dot np.dot(U[i], U[j]) print(fu{i1} · u{j1} {dot:.10f})输出textu1 · u2 0.0000000000 u1 · u3 0.0000000000 u1 · u4 0.0000000000 u2 · u3 0.0000000000 u2 · u4 0.0000000000 u3 · u4 0.0000000000验证通过。6. 完整答案最终正交基u1(4,1,3,−1)u2(7027,3127,−6927,10427)u3(−287397,−405397,799397,844397)u4(??,??,??,??)u1​u2​u3​u4​​(4,1,3,−1)(2770​,2731​,−2769​,27104​)(−397287​,−397405​,397799​,397844​)(??​,??​,??​,??​)​u4u4​ 的第二个分量0.91619228810.9161922881保留 5 位有效数字0.916190.91619​7. 常见错误与注意事项错误类型说明正确做法归一化向量将正交基转为标准正交基题目明确要求不归一化有效数字误解将5位有效数字理解为5位小数有效数字包括整数部分和小数部分舍入方式不当使用 Python 默认的四舍五入需要严格按照 5 位有效数字舍入浮点误差累积使用浮点数导致微小偏差使用分数或高精度十进制忘记去除换行复制数字时包含换行符手动清理输入数据8. 有效数字说明5 位有效数字是指从第一个非零数字开始数 5 位。例如0.91619 → 5 位有效数字9,1,6,1,90.00012345 → 5 位有效数字是 0.000123451,2,3,4,5123.456 → 5 位有效数字是 123.46本题中 0.91619228810.9161922881 的 5 位有效数字为 0.916190.91619。9. 扩展思考9.1 Gram-Schmidt 在密码学中的应用格密码学Gram-Schmidt 是 LLL 格基约简算法的基础正交化攻击在某些密码分析中正交化可用于构造格攻击信号处理正交基在通信系统中用于消除干扰9.2 数值稳定性经典 Gram-Schmidt 算法在浮点数实现中可能不稳定。在实际应用中通常使用改进的 Gram-Schmidt 算法Modified Gram-Schmidt, MGS它通过重新正交化来提高数值稳定性。9.3 与 LLL 算法的关系LLL 算法使用 Gram-Schmidt 正交化作为核心工具通过对格基进行正交化来度量基向量的短度从而找到更短的格向量。10. 参考资源Cryptohack - Lattices 系列Gram-Schmidt Process - Wikipedia[Hoffstein, Pipher, Silverman: An Introduction to Mathematical Cryptography]Numerical Stability of Gram-Schmidt