如果a|b且a|c，则对所有的整数s和t，a|sb+tc。
3
2021/2/12
yky_wenfeng@
数论：素数
如果整数p(p>1)只能被1或者是它本身整除，而不能够被其他整数 整除，则称整数p为素数。
素数定理：设π(x)是小于x的素数的个数，则 π(x) ≈ x / lnx
4
9
2021/2/12
yky_wenfeng@
数论：最大公约数
公约数：设a,b∈Z，a和b的公约数是能够同时整除a和b的整数。
最大公约数：设a,b∈Z，称正整数d为a和b的最大公约数，如果满 足
d是a和b的公约数；
对a和b的任何一个公约数c，有c|d。
记为gcd(a,b) = d。
11
2021/2/12
yky_wenfeng@
数论：扩展欧几里德定理
欧几里德定理的过失 丢弃了所有的中间商数
基于中间商数的推演 a = q1b + r1 a + b (-q1) = r1 aq2 + b (-q1q2) = r1q2 r1q2= b – r2 a(-q2) + b (1 + q1q2) = r2 aλi + bμi = ri aλk-1+ bμk-1 = rk-1 = gcd(a,b)
数论：完全剩余系
整数集合A是模m的完全剩余系的充要条件是： A中含有m个整数； A中任何两个整数对模m不同余。
由于xi的选取是任意的，则模m的完全剩余系有无穷多个 模m的最小非负完全剩余系：{0,1,2,… ,m-1}； 模m的绝对最小完全剩余系： {-m/2 + 1,…,0,1,…,m/2}(当2|m) 或{-(m-1)/2,…,0,1,…,(m-1)/2}(当2不整除m)。
并进行比较，确定其安全性。
2
2021/2/12
yky_wenfeng@
数论：整除
整除：设整数a和b，且a≠0。如果存在整数k使得b = ak，那么就说 b能被a整除，记做a|b，或者说b是a的倍数。
整除的性质 对所有的整数a，a|0和a|a成立。同理，对任意的整数b，1|b 成 立； 如果a|b且b|c，则a|c 成立；
互素数：如果gcd(a,b)=1，则称a和b互素。
定理：对于任何非负的
整数a和b，有
可以用欧几里德算法求两个非负整数的最大公约数。 gcb(a,b) = gcd(b,amodb)
10
2021/2/12
yky_wenfeng@
数论：欧几里德算法求最大公约数
假设a大于b，求a和b最大公约数c： 用a去除b：a = q1b + r1 如果 r1 = 0，那么a能够被b整除，最大公约数为b；如果r1 ≠ 0 则将b表示为如下形式：
a c b d, a c b d, ac bd (mod n)
7
2021/2/12
yky_wenfeng@
数论：剩余类／完全剩余系
定义一：给定正整数m，对于每个整数i，0≤i ≤ m-1，称集合 Ri(m) = {n; n≡i(mod m), n∈N}
是模m的一个剩余类。 定义二：设m是正整数，从模m的每一个剩余类中任取一个数xi (0 ≤
2021/2/12
yky_wenfeng@
数论：素数
算术基本定理：任何一个正整数都可以分解为几个素数的乘积， 且该因数分解是唯一的，除非颠倒因子的顺序。
a
p a1 1
p a2 2
p at t
(
p1,p2
,
,pt是素数)
补充定理：如果p是一个素数，且乘积ab能被p整除，那么p|a 或者 p|b。更一般地，如果乘积ab……z能够被素数p整除，那么ab……z 中某个数必能被p整除。
密码学数学引论
Page: 1
2021/2/12
yky_wenfeng@
密码学数学引论组成
数论：研究整数性质的一个数学分支，重ห้องสมุดไป่ตู้研究素数。 群论：一种代数系统，重点研究在整数上的代数运算。 有限域理论：一种代数系统，比群更加复杂。 计算复杂性理论：分析不同密码技术和算法的计算复杂性的方法，
5
2021/2/12
yky_wenfeng@
数论：带余除法
任意的a ∈ Z且a > 0，可找出两个唯一确定的整数q和r，使a = qm + r，0 ≤ r ≤ m，q和r分别称为m去除a所得到的商和余数。 例一：a = 13，m = 8， 13 = 1 × 8 + 5 例二：a = -13，m = 8， -13 = (-2) × 8 + 3
b = q2 r1 + r2
同理，一直进行下去，直到余数为0，步骤如下：
r1 = q3r2 + r3
……
rk-2 = qkrk-1 + rk
结论： gcd(a,b)=rk-1
int Gcd(int a, int b) {
if(b == 0) return a;
return Gcd(b, a % b); }
模的由来：如果a是一个整数，m是一个正整数，定义“a mod m” 为a除以m的余数。 例一：a = 13，m = 8， 5 ≡ 13 mod 8
6
2021/2/12
yky_wenfeng@
数论：同余
同余：设整数a,b,n(n≠0),如果a-b 是 n 的整数倍(正的或者负的)，我们就 说 a ≡b(modn)(读做a同余于b模n)。
同余命题一：设整数a,b,c,n(n≠0), 当且仅当n|a时，a ≡0(modn)； a ≡a(modn)； 当且仅当b ≡a(modn)时， a ≡b(modn); 如果a ≡b(modn) 且 b ≡c(modn)，那么a ≡c(modn)。
同余命题二：设整数a,b,c,d,n(n≠0),假设a ≡b(modn),c ≡d(modn),那么
i ≤ m-1)，称集合{x0, x1, …, xm-1}是模m的一个完全剩余系(或简称为 完全系)。
例一：m = 3，三个剩余类－R0(3) = {…,-3,0,3…}，R1(3) = {…,2,1,4…}，R2(3) = {…,-1,2,5…}；完全剩余类{0,1,2}。
8
2021/2/12
yky_wenfeng@