Skip to content

数学常识

参考资料

  • 离散数学及其应用 - 翻译版, 包括 "离散数学" 和组合数学 / 初等数论 /... - 4

归纳与递归

  • 数学归纳法 \(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 始终为真

密码学常识

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

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

卷积

卷积的根本思想在于通过系统的滑动内积运算, 捕捉两个信号在不同相对位置上的局部相似性

  • 内积衡量两个向量的相似性, 结合模长和夹角
    • (\(\mathbf{a} \cdot \mathbf{b} = \|\mathbf{a}\| \|\mathbf{b}\| \cos\theta\))
  • 卷积则将这一概念扩展到动态场景, 通过滑动窗口计算局部内积
  • 卷积是不同位置上内积的集合
  • 连续卷积:
\[ (f * g)(t) = \int_{-\infty}^{\infty} f(\tau)g(t - \tau) d\tau \]