密码学 Chap.2 数论基础
本博文的创作目的是为博主本学期课程 密码学 做一个整体的知识梳理与总结, 并希望有助于后续进一步扩展知识面.
希望能够帮助到读到本文的读者.
之所以从第二章开始, 是因为本文是按照读者所受教学顺序进行梳理的, 第一章绪论暂且放下不表.
数论基础, 是以 整数的整除性 为中心的一部分知识. 至于为什么要在这里提及, 是因为 数论是密码学成立的基础 , 在古典密码学 / 公钥密码学等方面对数论均有涉及.
本章内容会与同博客中 信安数学基础_Fin 的内容高度重合, 在这里权当重新梳理了.
1. 整除
定义:
设 a, b 是两个整数, 其中 $ b \neq 0 $ , 如果存在整数 m 使得 $ a = bm $ 成立, 则我们称 b 整除 a 或 a 可被 b 整除 , b可称为a的因数, a可称为b的倍数. 上述关系还可记作:
$$ b \mid a $$
反之, 则可记作:
$$ b \nmid a $$
整除有以下几个性质:
- If $ a \mid 1 $ , then $ a = \pm 1 $
- If $ a \mid b $ , and $ b \mid a $ , then $ a = \pm b $
- For any $ b \neq 0 $ , $ b \mid 0 $
- If $ a \mid b $ and $ b \mid c $ , then $ a \mid c $ (传递性)
- If $ b \mid g $ and $ b \mid h $ , then for arbitary integers m, n, there is $ b \mid (mg+nh) $
2. 带余除法
定义:
如 a, n是两个整数, 其中 $ n>0 $ , 则存在两个整数 q, r, 使得 $ a = nq+r $ , 其中 $ 0 \leq r < n $ , $ q = [a/n] $ , 并且q与r是唯一的.
我们称q是 a被n除的不完全商 , r是 a被n除的余数 .
这带余除法有啥用呢?
整数分类
我们不扯那么多专业术语, 博主的理解, 就是以 n 为标尺, 将整数集合 根据除以n所得的余数 进行分类.
举个例子: 奇数偶数就相当于以2为标尺, 将整数集合分成了余数为 0 / 1 的两个类.
这就是信安数学基础那一章中 剩余类 的概念.
3. 最大公约数
定义:
两个数 a, b 的最大公约数 c 满足:
- c 是 a, b 的公约数, 即 $ c \mid a $ and $ c \mid b $
- a, b 的任意公约数均为 c 的因数, 即 If $ d \mid a $ and $ d \mid b $ , then $ d \mid c $ .
我们将最大公约数记为: $ gcd(a, b) $ , 特殊的, 如果 $ gcd(a, b) = 1 $ , 则称 a, b 互素 .
最大公约数有以下性质:
- $ gcd(a, b) = gcd(b, a) = gcd(a, -b) = gcd(\mid a\mid , \mid b \mid) = gcd(a, a-b) $
- $ gcd(0, a) = a $
怎么求最大公因数呢?
欧几里得算法
本质上是这个定理:
$$ gcd(a, b) = gcd(b, a-kb) = gcd(b, r) $$
也被称为 辗转相除法 .
进行一系列辗转相除后, 最后一个不等于0的余数 就是 $ gcd(a, b) $ 的值.
4. 模运算
模运算是专门用于余数运算的运算方式:
对于 $ a = nq+r $ , 我们通常将 r 记作: $ r = a \space mod \space n $
用模运算的方式表示剩余类:
$$ a \equiv b \space mod \space n $$
这说明 a, b 处于关于n的同一个剩余类内, 即 a, b 关于n同余.
模运算还有以下性质:
- $ [(a \space mod \space n)+(b \space mod \space n)] \space mod \space n = (a+b) \space mod \space n $
- $ [(a \space mod \space n)-(b \space mod \space n)] \space mod \space n = (a-b) \space mod \space n $
- $ [(a \space mod \space n) \times (b \space mod \space n)] \space mod \space n = (a \times b) \space mod \space n $
5. 剩余类
我们一般将关于n的全部剩余类 (即 n就是上文中进行整数分类的标尺 ) 记为 $ Z_n $ .
关于 $ Z_n $ , 上方的模运算有以下性质:
- 交换律
- $ (w+x)mod \space n = (x+w)mod \space n $
- $ (w \times x)mod \space n = (x \times w)mod \space n $
- 结合律
- $ [(w+x)+y]mod \space n = [w+(x+y)]mod \space n $
- $ [(w \times x) \times y]mod \space n = [w \times (x \times y)]mod \space n $
- 分配律
- $ [w \times (x+y)]mod \space n = [w \times x + w \times y]mod \space n $
- 单位元
- $ (0+w)mod \space n = w \space mod \space n $
- $ (1 \times w)mod \space n = w \space mod \space n $
关于可约律, 会在介绍完 加法 / 乘法逆元 后进行阐述.
6. 加法逆元 / 乘法逆元
对于 $ w \in Z_n $ , 存在 $ z \in Z_n $ , 使得 $ w+z \equiv 0 \space mod \space n $ , 则 w, z互为加法逆元 , 记为 $ z = -w $ .
类似的, 如果有 $ w \times z \equiv 1 \space mod \space n $ , 则 w, z互为乘法逆元 .
加法逆元总是存在的, 但并未每个w都能有乘法逆元.
事实上, 当且仅当w与当前标尺n互素时, w才有乘法逆元.(见下侧定理)
乘法逆元的存在性定理
设 $ a \in Z_n $ , 若 $ gcd(a, n) = 1 $ , 则 a 在 $ Z_n $ 中有乘法逆元.
根据上述定理, 可知任一素数 p 对应的 $ Z_p $ 中所有元素均有乘法逆元. (因为任何元素都与p互素)
需要明确, 可约率成立的前提是元素有逆元.
- 可约率
- $ (a+b) \equiv (a+c) \space mod \space n $ , 则 $ b \equiv c \space mod \space n $ , 该式恒成立, 因为加法总是有逆元.
- $ (a \times b) \equiv (a \times c) \space mod \space n $ , 则 $ b \equiv c \space mod \space n $ , 该式当且仅当 a有乘法逆元时成立 .
6.1 乘法逆元的求法
加法逆元很好求, 但乘法逆元不是很容易一眼瞪出来. 这时, 我们通常使用 扩展欧几里得算法 .
所谓 扩展欧几里得算法 , 意味着求出两数 a, b 的最大公约数 $ gcd(a, b) $ 后, 将整个过程逆着倒腾回去, 用 a, b 的线性组合表示出 $ gcd(a, b) $ , 即:
$$ gcd(a, b) = n \times a + m \times b $$
我们假设想求 a 关于 b 的乘法逆元:
- 利用欧几里得算法验证 $ gcd(a, b) = 1 $
- 利用扩展欧几里得算法倒回去求出 m, n
- 这个m就是b的乘法逆
具体过程读者可参考本博客中 信安数学基础_Fin 这一章.
7. 素数
如果整数p的因子只有 $ \pm 1, \pm p $ , 则p是素数.
引入素数是为了引入一个重要定理: 整数分解定理
任意整数 a 都能唯一的分解为下列形式:
$$ a = p_1^{a_1}p_2^{a_2}…p_t^{a_t} $$
其中 $ p_1, p_2, …, p_t $ 均为素数.
我们用更加简洁的语言描述一下上面的定理:
$$ a = \prod_{p \in P} p^{a_p} $$
这其中 $ P $ 是全体素数组成的集合. $ a_p $ 指的是对应素数的指数项(大部分取0) .
我们利用这种方式, 可以 利用一个唯一的非零指数列表来表示一个整数 :
$$ 11011 = \lbrace a_7 = 1, a_{11} = 2, a_{13} = 1 \rbrace $$
即 $ 11011 = 7^1 \times 11^2 \times 13^1 $
为啥要这么干呢, 因为这么表示整数可以很方便的表示两数的相乘, 将对应指数相加即可.
啥意思?
$ 12 = \lbrace a_2 = 2, a_3 = 1 \rbrace $ , $ 18 = \lbrace a_2 = 1, a_3 = 2 \rbrace $ . 则 $ 12 \times 18 = \lbrace a_2 = 2+1 = 3, a_3 = 1+2 = 3 \rbrace $ .
