跳转至

数学常识

参考资料

  • 琐碎

归纳与递归

  • 数学归纳法 \(P(1) \land \left( \forall k \geq 1, P(k) \rightarrow P(k+1) \right) \Rightarrow \forall n \geq 1, P(n)\) 推下一个
  • 强归纳法 \(P(1) \land \left( \forall k \geq 1, \left( \bigwedge_{j=1}^k P(j) \right) \rightarrow P(k+1) \right) \Rightarrow \forall n \geq 1, P(n)\) 前面的所有推下一个
  • 良序性公理 任何非空非负整数集合都有最小元素
    • \(\forall S \subseteq \mathbb{N}^+, S \neq \emptyset \implies \exists m \in S, \forall x \in S, m \leq x\)
  • 递归定义函数 / 集合
  • 递归算法
  • \({ p }\ \text{S}\ { q }\) 指算法 S 输入满足 p, 输出满足 q, 即 S 对于 p, q 部分正确 称之为霍尔三元组
  • 循环不变量指对于一个循环, 命题 p 始终为真

不等式基础

  • 三角不等式: \(|a+b| \leq |a| + |b|\)
  • AM-GM 不等式: \(\frac{a_1 + \cdots + a_n}{n} \geq \sqrt[n]{a_1 \cdots a_n}\) (\(a_i \geq 0\)), 等号同值
  • 柯西-施瓦茨不等式: \((\sum a_i b_i)^2 \leq (\sum a_i^2)(\sum b_i^2)\)
  • 伯努利不等式: \((1+x)^r \geq 1 + rx\) (\(x \geq -1, r \geq 1\) 或 \(0 \leq r \leq 1\))

密码学常识

  • 密钥 加密算法中的常数
  • 单码密码 (一一对应) 分组密码 (多对多)
  • 密码系统: 明文集合, 密文集合, 密钥集合, 加密算法集合, 解密算法集合
  • 私钥密码系统
  • 公钥密码系统 (加密密钥公开) 需要一个难以逆计算的问题

RSA 密码系统

  • 密钥生成
    • \(n = p \times q\) (\(p, q\)为大素数)
    • $\phi(n) = (p-1)(q-1) $
    • 选择\(e\)满足\(\gcd(e, \phi(n)) = 1\)
    • 计算\(d \equiv e^{-1} \pmod{\phi(n)}\)
  • 加密过程
    • 明文分组为整数\(M < n\)
    • 密文\(C \equiv M^e \pmod{n}\)
  • 解密过程
    • \(M \equiv C^d \pmod{n}\)
    • 密钥为\(d\)

迪菲 - 赫尔曼密钥交换

  • 协商参数: 大素数\(p\)及其原根\(g\)(满足\(g^{p-1} \equiv 1 \pmod{p}\)且无更小周期)
  • 用户 A 生成私钥\(a\), 计算公钥\(A \equiv g^a \pmod{p}\)
  • 用户 B 生成私钥\(b\), 计算公钥\(B \equiv g^b \pmod{p}\)
  • 交换公钥后, 双方计算共享密钥:
    • A 计算\(K \equiv B^a \pmod{p}\)
    • B 计算\(K \equiv A^b \pmod{p}\)
  • \(K \equiv (g^b)^a \equiv g^{ab} \equiv (g^a)^b \pmod{p}\) 原理

同态加密

全同态加密, 允许对密文进行运算, 得到密文结果为对相应明文运算的结果的密文

\[ \forall m_1, m_2 \in \mathcal{M}, \quad \text{Dec}(\text{Enc}(m_1) \oplus \text{Enc}(m_2)) = m_1 + m_2\\ \forall m_1, m_2 \in \mathcal{M}, \quad \text{Dec}(\text{Enc}(m_1) \otimes \text{Enc}(m_2)) = m_1 \times m_2 \]
  • 其中\(\oplus, \otimes\)为密文域运算, \(+, \times\)为明文域运算
  • 部分满足则为偏同态加密, 如 RSA (乘法满足, 加法不满足)

欧拉公式

  • \(e^{i\theta} = \cos\theta + i\sin\theta\)

傅里叶 —— 莫茨金消元法

  • 从线性不等式中消除变量的数学方法
  • 消除所有变量可用于检测不等式系统是否有解

平衡三进制

  • 平衡三进制是三进制的一种变形, 它的基数为 3, 每位数码由−1, 0, 1 构成, 由于−1 书写不方便, 一般用字母 z 代替
  • 俄罗斯的科技人员曾经将其应用到计算机系统, 也被应用于光子计算机相关研究中 (它没有符号!)

zz z0 z1 z 0 1 1z 10 11