线性关系(linear  relatition) (linear\;relatition)

线性关系在不同的领域有不同的解释：

  1. 在数学函数或数量关系领域，函数的图像呈现出一条直线

  2. 在代数学和数分中，运算如果满足"加性"和"齐性"则该运算是现行的：
    可加性：L(x+t)=L(x)+L(t)L(x+t) = L(x) + L(t)
    齐次性：L(mx)=mL(x)L(mx) = mL(x)

线性规划 (linear  programming(LP))(linear\; programming(LP))

参考：Link；最优化原理基础(教材)没找到是哪本..

线性规划问题的目标函数及约束条件均为线性函数，决策变量可以为任意实数；一般用来解决最优解问题。

  • 约束条件记为 s.t.(subject to),其不等号可以是小于号也可以是大于号；
  • 目标函数可以是求最大值，也可以是求最小值。

alt

< 对简单的（变量少的线性规划问题，可以通过图解来简单清晰的解决问题，如下图：

alt

在一般情况下，变量可能会有很多，无法用简单的图解来描述该数量关系，所以引入矩阵，将目标函数和约束关系均表示为矩阵-向量形式，就得到了线性规划的标准形式：

注意以下定义：

  • A的秩r(A)=m，且A的列向量不含0向量；A 的秩 r(A) = m，且 A 的列向量不含 0 向量；

  • aj为A的第j个列向量，即为Xj的系数；a_j 为 A 的第 j 个列向量，即为 X_j 的系数；

  • S={x∈Rn∣Ax=b,x>=0}叫做可行域(Feasible  Domain)；Ax=b叫做主约束(Main  Constraint);X≥0叫做非零约束(None−Zero  constraint)S=\left\{x \in R^n | Ax = b,x >= 0 \right\} 叫做可行域(Feasible\;Domain)；Ax = b 叫做主约束(Main\;Constraint);X\geq0叫做非零约束(None-Zero\;constraint)

alt


举个例子： 图解法可以放在此后再理解

alt

：解释一下，

  • 决策变量：x1,x2x_1,x_2
  • 目标函数：max  z=4x1+3x2      式(1) max\;z = 4x_1 +3 x_2 \;\;\;式(1)
  • 约束条件：式(2)式 (2)
 这里如果看作等，列出的增广矩阵为 $$\begin{gathered}\begin{bmatrix} 0 & 0 & -1\\ 1 & 0 & 2\\0 & 1 & 7\end{bmatrix}\quad\end{gathered}$$是无解的，但考虑是不等式便有解__(No-Understand)

整数线性规划(integer  Linear  Programming(ILP))(integer\;Linear\;Programming(ILP))

从线性规划的定义进一步，整数线性规划问题的目标函数及约束条件均为线性函数，决策变量也必须为整数. 如上面例子中 (2) 式中的全部未知变量需为整数.(整数线性规划也叫做纯整数线性规划)

混合整数线性规划(Mixed  integer  Linger  Programming(MILP))(Mixed\;integer\;Linger\;Programming(MILP))

从线性规划的定义再进一步，混合整数线性规划问题的目标函数及约束条件均为线性函数，决策变量需有整数，但也可包含非整数. 如上面例子中 (2) 式中的全部未知变量需有整数，但也可包含非整数.

MILP  In  CryptanalysisMILP\;In\;Cryptanalysis

在密码领域，往往使用 MILP 刻画加密算法，并用特定的求解器，如 python Sagemath，Gurobi 等求得小活跃数据量（大多数情况，其在差分分析中表示为活跃 S-box 数量）
需要注意的是，活跃是设计者期望达到的状态，这使得差分概率很大程度上减小，对分组密码而言，每一轮活跃的数量越多（可以结合 RijndaelRijndael 的每一轮理解）需要累乘的小于 1 概率就越多。
另外需要注意的是，使用MILP或SAT等求解器获得最小活跃数据量，并不参与分析复杂度的统计，其目的就是寻找到最小活跃路径，老师讲只要找到就行。
下面举个使用 MILP 寻找 AES 最小活跃 S 盒的例子 :