本篇是看完公开课后做的课程作业，答案没有对，希望我写的东西是对的。
由于是跟着英语教材做的，发上来就不想用英语，所以答案存在中英混杂的情况；由于懒得插图，所以以数学描述为主，也会缺一部分严格的叙述。
题目使用的教材是 Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Thomson Course Technology, 2006. ISBN: 0534950973.
本人用作参考的教材为该书的第三版
终于有时间好好学学格论的基础部分，做一个笔记。 本文目前重点介绍格基约化的LLL算法。其他部分可能另外进行更新。
欧几里得空间上上一个离散加法子群称为格\(L\)。其可由一组格基的整系数线性组合生成。
事实上，一个格是同一组基下的线性空间的一个特殊子集。
通常来说，当我们需要解决格中最短向量问题（SVP）、最近向量问题（CVP），及其近似问题（apprSVP、apprCVP）时，我们希望有一组尽可能正交的基，并称基的正交程度为基的质量。而LLL算法是优化基的质量的一个可行方法。
方便起见（同时基于其基本应用），我们局限于讨论维数与基的数量相同的格。
本文仅为思路简述，具体过程参考参考文献所述
一个对称密钥密码通常需要在加密网络中引入非线性部分以保证密码的安全性。而如果可用线性关系去近似表达非线性关系，那么问题必然能够进行简化。我们将在基于按位异或(xorKey)、分组替代(sbox)与位重排(permutation)一个简单的的分组密码上考虑这种思想。
考虑一个关于密码部分输入输出位的异或和关系式\(\sum input_i+\sum output_i=0\)，我们知道其不会恒成立，而理想非线性情况下，对于随机输出，其成立的概率应为0.5。如果这一概率产生明显偏移，即证明在正确加密的过程中，对于大量随机输入输出，线性趋势将会显著表现。
我们枚举部分密钥，然后考虑可求的两组过程值之间的有偏的线性趋势。可以通过类似假设检验的手法，验证枚举的密钥是否可能成立。
早啊 申了备案，拿持有的阿里云学生机搞了个新的个人博客，赶时间没去做服务器配置，抛弃了Wordpress直接开着hexo。现在一切都是默认，等我寒假再来整整。 旧博客的文章可能会慢慢搬过来，也可能就不管了；不过友链什么的会搬一搬（再请对面改下反链地址）； 到了高三以后原来的博客上都只有年终总结的杂文了，不知道新博客会不会写什么新东西。也许会有些没什么卵用的大学课程笔记，或者ctf的东西？ 希望自己不要咕咕咕。