🔴 密码学入门

学习密码学首先要先了解密码学中最重要的概念：素数

妈咪叔在素数第二期提了欧拉证明素数有无穷多个的方法

->黎曼函数->理解黎曼函数解析延拓，漫士沉思录这个up主讲的非常透彻，做科学视频的那个up主也讲得不错，很直观

我们从一道题中引入密码学：

离散对数在密码学中有重要的应用。设\(p\)是素数，集合\(X = \{1,2,\cdots,p-1\}\)，若\(u,v \in X, m \in \mathrm{N}\)，记\(u\otimes v\)为\(uv\)除以\(p\)的余数，\(u^{m,\otimes}\)为\(u^m\)除以\(p\)的余数；设\(a \in X\)，\(1,a,a^{2,\otimes}, \cdots,a^{p-2,\otimes}\)两两不同，若\(a^{n,\otimes}=b(n\in \{0,1,\cdots,p-2\})\)，则称\(n\)是以\(a\)为底\(b\)的离散对数，记为\(n=\log(p)_ab\)

(1) 若\(p=11\)，\(a=2\)，求\(a^{p-1,\otimes}\)；

(2) 对\(m_1,m_2 \in \{0,1,\cdots,p-2\}\)，记\(m_1\oplus m_2\)为\(m_1 +m_2\)除以\(p-1\)的余数（当\(m_1+m_2\)能被\(p-1\)整除时，\(m_1\oplus m_2 = 0\).证明：\(log(p)_a(b\otimes c) = log(p)_ab\oplus log(p)_a c\)，其中\(b,c \in X\)；

(3) 已知\(n=log(p)_a b\). 对\(x \in X, k \in \{1,2,\cdots,p-2\}\)，令\(y_1 = a^{k,\oplus},y_2 = x\otimes b^{k,\otimes}\). 证明：\(x = y_2 \otimes y_1^{n(p-2), \otimes}\).

说人话就是对集合\(X = \{1,2,\cdots,p-1\}\)，给定元素\(a \in X\)，满足：\(1,a,a^2,\cdots,a^{p-2}\)两两不同余，如果满足\(a^n \equiv b(\mod p)\)，则计作\(n=\log _a b\)

(1) 求\(a^{p-1}(\mod p)\)

(2) 对于任意\(b,c \in X\)，下式成立： $$ \log_a(bc \mod p) \equiv \log_a b + \log_a c (\mod p-1) $$ (3) 已知\(n = \log_a b\)，对于\(x \in X, k \in \{1,2,\cdots, p-2\}\)，令\(y_1 = a^k, y_2 = xb^k\)，证明：\(x \equiv y_2y_1^{n(p-2)}(\mod p)\)