# 密码学入门

> source: 文章/cryptography-intro/index.md

# 密码学入门

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

<!-- more -->

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

->黎曼函数->理解黎曼函数解析延拓，漫士沉思录这个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)$
