密码学基础
数论基础
-------------------------------- 数论的简单基础 --------------------------------
一、整除性
1、整除的定义：
设 a,b ∈ Z ,如果存在一个 q ∈ Z 使得 a = qb; 则称 "b整除a" ,记作 "b|a"。
(或称 "b是a的因子","a是b的倍数","a被b整除")
2、整除的性质：
对于任意的a,b,c ∈ Z,有以下性质：
(1) 基本性质：
- b|0, (任意一个整数都是0的因子)
- 1|a, (1是任意整数的因子)
- 0|a 等价于 a=0, (0是a的因子，等价于a=0)
- b|a 等价于 b|-a 等价于 -b|a,
(2) 自反性： a|a
(3) 传递性： b|a 且 a|c 则 b|c
(4) 相乘性： b|a 则 bc|ac
(5) 消去性： bc|ac 且 c≠0 则 b|a
(6) 线性性： b|a 且 b|c ，则对任意的 s,t∈ Z 有 b|(sa ± tc)
(7) 比较性：b|a 且 a,b ∈ N ，则 b ≤ a
定理1
设 a,b ∈ Z ;
当且仅当 a = ±b 时 , a|b 并且 b|a
特别的： 当且仅当 a = ±1 时 a|1
3、练习题：
证明对于任意自然数x，其各位上的数字相加之和如果能被3整除，那么该自然数也能被3整除。
设 a = a0 + a1*10 + ... + ak*10^k、b = a0 + a1 + ... + ak
则，证明上述结论即证明 "如果 3|b ,则 3|a"
将a化简如下：
a = a0 + a1*10 + a2*10^2 + ... + ak*10^k
= a0 + (a1 + 9*a1) + (a2 + 99*a2) + ... + (ak + 9...9*ak)
= (a0 + a1 + a2 + ... + ak) + (9*a1 + 99*a2 + ... + 9...9*ak)
= b + 3 * (3*a1 + 33*a2 + ... + 3...3*ak)
因为 3|b ，因此 存在q ∈ Z 使得 b = 3*q 。 将其代入上式可得：
a = 3*q + 3 * (3*a1 + 33*a2 + ... + 3...3*ak)
= 3 * (q + 3*a1 + 33*a2 + ... + 3...3*ak)
所以 3|a 。
二、素数
1、素数的定义
设 n ∈ N ,且 n ≥ 2 。如果除了 1 和 n 外，没有其他正整数能整除n。称 n 为素数。
素数通常用 p 表示。除素数外的正整数称为合数。（1既不是素数也不是合数）
2、素数相关的定理：
(1) 如果 n 不是素数(即n是合数)，则 n = ab , 其中 1 < a < n , 1 < b < n 。
(2) 任何大于一的整数必有素因子
(3) 任何合数都有一个不超过 "根号n" 的素因子
(4) 算术基本定理：
任何非零整数 n 都可以表示成 一些素数的乘积，并且表示形式唯一。
(5) 欧几里得定理：
素数有无穷多个。
补充：
(6) 设有一个"由素数组成的公差为d长度为k的等差数列"，则d能被小于k的所有素数整除
推论：
不存在无穷长的素数等差数列
(7) 存在任意长度的素数等差数列
三、模运算
1、模运算的定义：
设 a,b ∈ Z 且 b > 0 , 如果 q,r ∈ Z 并且满足 "a = qb + r , 且 0 ≤ r < b"、
则 a mod b := r ，读作： a 模 b 得 r
2、模运算得性质：
(1) 如果 b|a , 那么 a mod b = 0
(2) (a + b) mod n = (a mod n + b mod n) mod n
(3) (a - b) mod n = (a mod n - b mod n) mod n
(4) (a * b) mod n = (a mod n * b mod n) mod n
四、最大公约数
1、最大公约数的定义
设 a,b ∈ Z , 如果 d ∈ Z 且 d|a , d|b , 则称 d 是 a和b 的公因子(公约数)。
如果 d >= 0 且 a 和 b的所有公因子都整除 d ，则称 d 是 a和b 的最大公约数，
记作 gcd(a,b) = d 。
注意：
- 公因子可以是任意整数（包括0和负整数）。
- 最大公约数显然大于等于0
2、最大公约数的性质：
(1) gcd(-a,-b) = gcd(-a,b) = gcd(a,-b) = gcd(a,b)
(2) 设 a,b,c不全为0,且 a = b*q + c , 则 gcd(a,b) = gcd(b,c)
推论： a,b的公因数 等价于 gcd(a,b)的因数
(3) 设a,b为不全为0的整数，则：
- 对于任意的正整数m，有gcd(am,bm) = gcd(a,b)*m
- 若 m 是a，b的公因数，gcd(a/m,b/m) = (a,b) / |m|
(4) 若 a,b,c是三个整数，且b和c至少有一个不为0，且gcd(a,b) = 1,则：
- a*b 与 c的公因数与 b和c的公因数相同
- gcd(ab,c) = gcd(b,c)
(5) 设 a,b ∈ Z, d = gcd(a,b) , 则 存在 s,t∈Z , 使得 as + bt = d .
特别的： 当 gcd(a,b) = 1 ,存在 s,t∈Z , 使得 as + bt = 1 .
(不定方程： ax + by = c 有整数解的充要条件是 gcd(a,b) | c )
3、互素的定义
设 a,b ∈ Z , 如果 gcd(a,b) = 1 ,称 a和b 互素。
注意：
互素的两个数公因子只有 ±1
性质：
(1) 设 gcd(a,b) = d ,则存在 q1,q2 ∈ Z , 使得 a = q1*d , b = q2*d
且 gcd(q1,q2) = 1 。(当gcd(q1,q2) = t > 1 时 gcd(a,b) = t*d > d ,
与gcd(a,b) = d 矛盾)
(2) 若p是质数，a是任意整数，则 要么 p|a , 要么 gcd(a,p) = 1
(一个整数与一个质数只存在整除与互素两种关系)
4、欧几里得算法(辗转相除法)求最大公约数：
设 a,b ∈ Z ,该算法用来求 gcd(a,b)。
因为 gcd(-a,-b)=gcd(-a,b)=gcd(a,-b)=gcd(a,b)、不失一般性设 a >= b >= 0
(1) gcd(a,0) = a;
(2) gcd(a,b) = gcd(b,r); 其中 r = a mod b
证明：
- 因为 a|a 且 a|0 、 所以 gcd(a,0) = a。
- 因为 r = a mod b , 所以 a = q*b + r
对于 a 和 b 的公因子d、存在q1,q2 ∈ Z, 使得 a = q1 * d , b = q2 * d
即 q1 * d = q * q2 * d + r
即 r = d * (q1 - q * q2)
即 d 是 r 的因子
所以 d 是 b和r 的因子
所以 a和b 的公因子一定是 b和r 的公因子
所以 gcd(a,b) = gcd(b,r)
根据(1)(2)可知，求两个较大数的最大公约数可以转换为其余两个较小数的最大公约数，即
gcd(a,b) = gcd(b,r)。令 r1 = b mod r 则 gcd(a,b) = gcd(b,r) = gcd(r,r1)
依次迭代，最终 rk 必等于0 ，根据(1)，gcd(a,b) = r(k-1).这就是欧几里得算法的思路。
关于 rk 必定等于0 ，这里解释一下：
容易看出 对于任意的k、 满足 rk < r(k-1)、且 rk >= 0 , 因此不断迭代下去，必
定存在一个k使得 rk = 0。
5、扩展的欧几里得算法：
- 最大公约数表示定理：
设 a,b ∈ Z, d = gcd(a,b) , 则 存在 s,t∈Z , 使得 as + bt = d .
特别的： 当 gcd(a,b) = 1 ,存在 s,t∈Z , 使得 as + bt = 1 .
推论： 如果 d|v 则，存在 s,t∈Z , 使得 as + bt = v .
- 扩展的欧几里得算法是 计算 as + bt = gcd(a,b) 中的 s和t , 从而求出 gcd(a,b)
具体的求解可使用如下方法迭代求得：
首先介绍欧几里得算法，如下所示：
初始时：
a = r0 , b = r1;
辗转相除：
r0 = r1 * q1 + r2 ;
15 = 10 * 1 + 5
r1 = r2 * q2 + r3 ;
10 = 5 * 2 + 0
r2 = r3 * q3 + r4 ;
...
...
r(i-1) = ri * qi + r(i+1) ;
...
...
r(n-3) = r(n-2) * q(n-2) + r(n-1) ;
r(n-2) = r(n-1) * q(n-1) + rn ;
r(n-1) = rn * qn ;
当 rn|r(n-1) 时，求得最终结果为 rn
扩展的欧几里得算法：
设 s0 = 1 ,s1 = 0 ; t0 = 0 , t1 = 1 ;
则:
s(i+1) = s(i-1) - si * qi ; (i = 1,2,...,n)
t(i+1) = t(i-1) - ti * qi ; (i = 1,2,...,n)
易知上述s,t满足：
a * si + b * ti = ri ; (i = 0,1,2,...,n)
可用数学归纳法证明如下：
归纳奠基：
当 i = 0 时，a*s0 + b*t0 = a = r0 成立
当 i= 1 时， a*s1 + b*t1 = b = r1 成立
归纳递推：
假设 a * s(i-1) + b * t(i-1) = ri 成立，那么：
a * si + b * ti
= a * (s(i-2)-s(i-1)*q(i-1)) + b * (t(i-2)-t(i-1)*q(i-1))
= a * s(i-2) + b * t(i-2) - (a*s(i-1)+b*t(i-1)) * q(i-1)
= r(i-2) - r(i-1) * q(i-1)
由辗转相除的步骤可知: r(i-2) = r(i-1) * q(i-1) + ri ;代入上式可得
a * si + b * ti = ri
得出结论：
a * si + b * ti = ri ; (i = 0,1,2,...,n) 成立
在欧几里得算法的基础上，每一步都求出相应的 si 和 ti ，最终即可求出 s,t
满足 as + bt = gcd(a,b)
五、最小公倍数(Least Common Multiple)
1、最小公倍数的定义
设 a,b ∈ Z , 如果 m ∈ Z 且m既是a的倍数，又是b的倍数 , 则称m是a和b的公倍数。
若 ab ≠ 0 , 且m是a和b的正的公倍数中，最小的那个，称 m 是 a和b 的最小公倍数。
记作 lcm(a,b)
性质：
(1) a,b的公倍数 等价于 lcm(a,b)的倍数。
(2) 如果 gcd(a,b) = 1 , 则 lcm(a,b) = ab ;
(3) lcm(a,b) = ab / gcd(a,b)
2、求最小公倍数的方法：
对于 a,b 。
- 首先令 m = a;n = b;
- 如果 m < n ,那么 令 m = m + a;否则，令 n = n + b;
- 循环第二步，直到 m = n 为止，此时 m 即为最小公倍数。
六、同余
1、等价关系
设有集合S和定义在S上的二元关系R。如果R满足如下性质，则称他为等价关系：
- 自反性: 对于任意 a ∈ S ,都有(a,a) ∈ R
- 对称性: 对于任意 a,b ∈ S ,若(a,b) ∈ R , 则 (b,a) ∈ R
- 传递性: 对于任意 a,b,c ∈ S,若(a,b) ∈ R,(b,c) ∈ R,则(a,c) ∈ R
练习：
S = R ,二元关系 R = {(a,b):x² = y², x,y ∈ S} , 问 R 是不是等价关系?
- 对于任意的 a ∈ S , a² = a² , 即 (a,a) ∈ R , R 满足自反性
- 对于任意的 a,b ∈ S , 若 (a,b) ∈ R, 则 a² = b² , 即 b² = a² ,
所以 (b,a) ∈ R , 即R满足对称性。
- 对于任意的 a,b,c ∈ S ,若 (a,b) ∈ R,(b,c) ∈ R, 则 a² = b²,b² = c²
所以 a² = c²，所以 (a,c) ∈ R , 即 R 满足传递性。
综上所述，R是等价关系。
2、同余(Congreuence)
同余定义：
设 n 为正整数, a和b分别模n, 如果得到的余数相等, 则称 a和b在模n的条件下满足
同余关系。简称同余。记作 a≡b(mod n) 。 这里 n 叫做 "模数"
同余关系的严格数学定义：
设 a,b,n ∈ Z, n > 0, 若 n | (a-b), 就称a和b在模n下同余,记作 a≡b(mod n)
说明：
这与上述同余的定义是一样的, a和b分别模n,假设得到的余数分别为r1,r2
则 a = q1 * n + r1 ;
b = q2 * n + r2 ;
由同余的定义可知，r1 = r2
所以 a-b = (q1 - q2) * n + (r1 - r2)
= (q1 - q2) * n
即 n | (a-b)
同余的性质：
" a≡b (mod n)" 等价于 "存在 q ∈ Z , a = q*n + b" 。
同余关系是等价关系，具有
自反性: 对任意的a∈Z ：a ≡ a(mod n) 则
对称性: 对任意的a,b∈Z : 若 a ≡ b(mod n) 则 b ≡ a(mod n)
传递性: 对任意的a,b,c∈Z : 若 a ≡ b(mod n) , b ≡ c(mod n),
则 a ≡ c(mod n)
推论：若a ≡ 1(mod n), 则 a^k ≡ 1(mod n) (k = 1,2,3...)
证明：
因为 a ≡ 1(mod n)
由性质(2)的推论， a² ≡ a(mod n)
由传递性得： a² ≡ 1(mod n)
同理可证k=3,4,.....
四则运算
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a ^ b) % p = ((a % p)^b) % p
(1) 若a1 ≡ b1(mod m),a2 ≡ b2(mod m),则(a1 ± a2) ≡ (b1 ± b2)(mod m)
(可加减性)
证明：
因为 a1 ≡ b1(mod m)
所以存在 q1,q2 ∈ Z ,使得 a1 = q1 * m + r1 ; b1 = q2 * m + r1
同理存在 q3,q4 ∈ Z ,使得 a2 = q3 * m + r2 ; b2 = q4 * m + r2
故 a1+a2 = (q1+q3)*m + r1 + r2; b1 + b2 = (q2+q4)*m + r1 + r2
故 a1+a2 与 b1+b2 的余数都是 r1+r2,即 (a1+a2) ≡ (b1 + b2)(mod m)
(2) 若 a1 ≡ b1(mod m) ,a2 ≡ b2(mod m) ,则 (a1*a2) ≡ (b1*b2)(mod m).
(可乘性)
证明：
因为 a1 ≡ b1 (mod m)
所以 存在 q1,q2 ∈ Z ,使得 a1 = q1 * m + r1 ; b1 = q2 * m + r1
同理 存在 q3,q4 ∈ Z ,使得 a2 = q3 * m + r2 ; b2 = q4 * m + r2
所以 a1 * a2 = q1*q3*m^2 + q1*r2*m + r1*q3*m + r1*r2
= ( q1 * q3 * m + q1 * r2 + r1 * q3 ) * m + r1 * r2
同理 b1*b2 = (q2 * q4 * m + q2 * r2 + r1 * q4) * m + r1 * r2
故 a1*a2 与 b1*b2 的余数都是 r1*r2,即 (a1*a2) ≡ (b1*b2)(mod m)
推论：
a ≡ b(mod m) ,则 ka ≡ kb(mod m)成立。
a ≡ b(mod m) ,则 a^k ≡ b^k(mod m)成立。
a ≡ b(mod m) ,gcd(d,m) = 1 ,则 (a / d) ≡ (b / d)(mod m)。
证明：
因为 gcd(d,m) = 1
所以 d在模m下存在乘法逆元，设为d1
由同余的自反性可知 d1 ≡ d1(mod m)
又因为 a ≡ b(mod m)
所以得 a*d1 ≡ b*d1(mod m)
即 (a / d) ≡ (b / d) (mod m)
(3) 若 a ≡ b(mod m) ,则 ka ≡ kb(mod km)
(同乘性)
证明：
因为 a ≡ b(mod m)
所以 存在 q1,q2 ∈ Z ,使得 a = q1 * m + r ; b = q2 * m + r
所以 ka = q1 * k * m + r * k ; kb = q2 * k * m + r * k
即 ka 和 kb 模 km 的余数都是 r * k , 即 ka ≡ kb(mod km)
(4) 若 a ≡ b(mod m) ,d是a,b,m的公因数 , 则 a/d ≡ b/d (mod m/d)
(同除性)
证明：
因为 a ≡ b(mod m)
所以 m | (a-b)
所以 m / d | (a /d - b/d)
即 a/d ≡ b/d (mod m/d)
(5) 若 a ≡ b(mod m) ,若 d|m 且 d > 0 ,则 a ≡ b(mod d)
(两个数在模m下同余，则这两个数在在模m的因子下也同余)
证明：
因为 a ≡ b(mod m)
所以 m|a-b , 即 a-b = k1 * m ;
因为 d|m ,即 m = k2 * d ;
所以 a-b = k1 * k2 * d ;
即 d | a-b
所以 a ≡ b(mod d)
(6) 若 a ≡ b(mod mi)(i = 1,2,...,k),则 a ≡ b(mod lcm(m1,m2,...,mk))
(两个数在一些模下同余，则在这些模的最小公倍数下也同余)
证明：
因为 a ≡ b(mod mi) (i = 1,2,...,k)
所以 mi | (a-b) (i = 1,2,...,k)
(7) 若 ac ≡ bc(mod m)且gcd(a,c) = 1,gcd(c,m) = d,则 a ≡ b (mod m/d)
(解方程可以用到)
特别的，当 d = 1 时,即 c和m 互素 , 则 a ≡ b(mod m)
即，同余式两边可以同时除以一个和模数互质的数。
证明：
条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq 也就是
说(a-b)c = m(p-q)。这表明，(a-b)c里需要含有因子m，但c和m互质，因此
只有可能是a-b被m整除，也即a≡b(mod m)。(一派胡言)
(8) 若 a ≡ b(mod m) ,则 gcd(a,m) = gcd(b,m)
(模m同余的两个数与m的最大公约数相同)
3、乘法逆元(Modular inverse)
设 a,z ∈ Z , n ∈ N , 如果 az ≡ 1(mod n) , 称 z 是a在模n下的乘法逆元。
注意：
- 一般乘法逆元取 [1,n)之间的数。
- a 在模n 下的乘法逆元是唯一的。
- 乘法逆元并不是一定存在的，乘法逆元存在的条件是 gcd(a,n) = 1
证明：
假设 gcd(a,n) = d ; (d > 1) 时，a 有乘法逆元，设为 b
则 ab ≡ 1(mod n) , 即 ab = qn + 1 ; 即 ab - qn = 1 ;
由于 d|a 且 d|n
所以 ab - qn 可提出一个因子 d
所以 d|1 , 而 d > 1 ，这是不可能的
故假设有误，d = 1 (d是最大公因数，故d > 0，而d <= 1，故d = 1)
* 乘法逆元的求法：
可用扩展的欧几里得算法求乘法逆元
假设a在模n下存在乘法逆元 ， 即 gcd(a,n) = 1 ;
根据最大公约数表示定理 , 存在 s,t ∈ Z ,使得 as + nt = 1
等式两边同时模n可得 (as + nt) mod n = 1 mod n
即 as mod n = 1 mod n ,
即 as ≡ 1(mod n)
所以s即为a在模n下的乘法逆元
4、一次同余方程
一次同余方程的一般形式为 ax ≡ b(mod n) ;
一次同余方程有解的充要条件是：gcd(a,n) | b ;
解方程可用上述介绍的同余性质。
例如：
解方程：105x - 62 ≡ 1(mod 6)
化为一般形式为： 105x ≡ 63(mod 6)
gcd(105,63,6) = 3 ,根据性质(4)得： 35x ≡ 21(mod 2)
又因为 gcd(7,2) = 1 ; 根据性质(5)得： 5x ≡ 3(mod 2)
因为 gcd(5,2) = 1 ; 故 5在模2下存在乘法逆元，计算可得乘法逆元为 1
两边同乘乘法逆元得：x ≡ 3(mod 2)
即 x ≡ 1(mod 2)
所以解为 {...,-3,-1,1,3,5,7,...}
定理：
假设解方程前模数为n,最终模数为m,设 n/m = d;则 [0,n-1] 之间的解恰好有 d 个。
上述例子中 n = 6, m = 2;故 d = 3;而解中在 [0,5]之间得解为1,3,5正好 d 个。
七、剩余类（Residue Class）
1、等价类：
- 定义：
设 ~ 是集合 S 上的等价关系， 对于 a ∈ S,定义 a 的等价类为：
{ x ∈ S | x ~ a }
即 S 中与 a 满足 等价关系 的元素的集合。
- 性质：
集合S上的所有等价类形成集合S的一个划分。
S中的每一个元素都存在于唯一的一个等价类中
所有等价类的并集恰好是集合S
2、剩余类：
- 定义：
设 x ∈ Z,定义它的剩余类为：
{ x ∈ Z | x ≡ a (mod n) }
即 a的剩余类就是 "与a同余的正数集合"。（ 易知：剩余类是等价类的一种。）
- 代表元：
剩余类中的每个元素都叫做这个剩余类的代表元。
- 小提示：
模n下含有正数a的剩余类记作 [a]n,不引起歧义时简记为 [a], 一般取a ∈ [0,n]
- 剩余类集合：
Zn = {[0],[1],...[n-1]}
- 剩余类运算的定义：
在模n下：
加法：
[a] + [b] := [(a + b) mod n] (其中a,b ∈ Z)
乘法：
[a] * [b] := [(a * b) mod n] (其中a,b ∈ Z)
乘法逆元
设u = [a],v = [b] ∈ Zn,若 u*v = [1],则称 u和v互为乘法逆元、
(对于剩余类[a],他有乘法逆元的充要条件是：gcd(a,n) = 1)
- 含有乘法逆元的剩余类 Zn*
Zn* = {Zn中含有乘法逆元的剩余类}
- Zn 和 Zn* 之间的关系
当n为素数时：
Zn* = Zn \ {[0]} （ 即 Zn* 是 Zn中去掉[0] ）
当n为合数时：
Zn* 是 Zn \ {[0]} 的真子集
八、中国剩余定理
1、中国剩余定理
设两两互素的模数n1,...,nm ∈ N,以及任意整数 a1,...,am ∈ Z, n = n1*...*nm。
则：一次同余方程组：
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
...
x ≡ am (mod nm)
必有解，且解集为：
{ k*M + ∑(ai*ti*Mi);k ∈ Z } 其中 M = n1*n2*...*nm; Mi = M/ni;
ti是Mi在ni下的乘法逆元
2、设两两互素的模数 n1,n2,...,nm ∈ N, n = n1*n2*...*nm;则下面的映射是一个双射
Zn → Zn1×Zn2×...×Znm 即（ a → (a mod n1,a mod n2,...,a mod nm) ）
3、欧拉函数
对于所有正整数 n ∈ N,欧拉函数 ф(n) := |Zn*| 。即所有小于n且与n互素的正整数
(不包括0)的个数。且规定 ф(n) = 1
欧拉函数的性质:
(1) 对于两两互素的正整数n1,n2,...nm , 设 n = n1*n2*...*nm;
则 ф(n) = ф(n1)*ф(n2)*...*ф(m) ; (使用中国剩余映射证明)
(2) 对于一个素数p , ф(p^k) = p^(k-1)*ф(p) = p^(k-1)*(p-1);
(使用算数基本定理和(1)易证)
(3) 对于一个素数p , ф(p) = p-1 ;
(由欧拉函数的定义，这是显然的)
(4) 设 d1,...,dr 是整数n的所有因子，则F(n) = ф(d1) + ... + ф(dr) = n
计算 ф(n) 的方法：
(1) 利用算数基本定理将n分解为素数的乘积，即 n = p1^k1 * ... * pn^kn
(2) 则 ф(n) = ф(p1^k1 * p2^k2 * ... * pn^kn)
(3) 利用上面三个公式轻松搞定
4、乘法阶 (Multiplicative order)
设 a ∈ Zn* ,使得 a^k ≡ 1(mod n) 的最小正整数k 称作a在模n下的乘法阶。
简称a的阶. （ 记作ep(a) = k ）
推论：
(1) 设 a ∈ Zn* 的乘法阶为k,则在模n运算中，若i不同则 a^i(mod n)(i ∈ [1,k-1])
的值各不相同且不等于1.
证明：
假设存在 i < j < k, 使得 a^i ≡ a^j(mod n)
则 由同余的性质(2)推论可得： a^i / a^j ≡ a^j / a^j(mod n)
即 a^(i-j) ≡ 1(mod n)
所以a的乘法阶为 i-j < k ，这与a的乘法阶是k矛盾
所以 当i不同时, a^i(i = 1,...,k-1) 各不相同
它们的值显然不能等于1，否则和乘法阶为k矛盾。得证
(2) a^i ≡ 1 (mod n) 等价于 k | i
证明：
充分性：
因为 a^i ≡ 1 (mod n)
所以 i >= k
假设 k | i 不成立，则 i可以写成 i = x*k + y 其中 0 < y < k
则 a^i ≡ 1 (mod n) 化简为 (a^xk) * (a^y) ≡ 1 (mod n)
即 ( (a^k)^x (mod n) * a^y (mod n) ) (mod n) = 1 (mod n)
即 1 * a^y (mod n) = 1
即 a^y ≡ 1(mod n) ,此时 y<k 是a的阶,矛盾
因此 k | i
必要性：
因为 k | i
所以 i = x*k
因为 a^k ≡ 1(mod n)
由同余传递性的推论可知： a^i ≡ 1(mod n)
(3) a^i ≡ a^j(mod n) 等价于 i ≡ j(mod k)
即 a^i(mod n) = a^(i mod k)(mod n) (当i很大时,可用此公式减小运算量)
证明：
(4) 设a ∈ Zn*,m ∈ Z,且a在模n下的乘法阶为k,则a^m在模n下的乘法阶为k/(gcd(m,k))
证明：
暂时不会 0.0
5、欧拉定理
设 a ∈ Zn*,则 a^ф(n) ≡ 1(mod n),且 k|ф(n)，k是a在模n下的阶。
(也可表述为：如果 gcd(a,n) = 1 , 则a^ф(n) ≡ 1(mod n))
注意：
由于 a ∈ Zn* ,所以 gcd(a,n) = 1,这时才有欧拉定理
欧拉定理的简单应用：
a^i(mod n) = a^( i mod ф(n) )(mod n)
(当i很大且不知道a的乘法阶时，可以用此公式减小运算量)
6、费马小定理
对于任意素数p和整数 a ∈ Zp,都有 a^p ≡ a(mod p) (也可写成 a^(p-1) ≡ 1(mod p))
7、幂模p与原根
离散对数：
对于一个素数p，设a,b是模p的非0整数，设 a^x ≡ b(mod p), 如果x是
满足 a^x ≡ 1(mod p)的最小正整数，
假设 0 <= x < p;则 记 x = La(b),读作 "与a相关的b的离散对数等于x"。
次整除性质：
设a是不被p整除的整数，假设 a^n ≡ 1(mod p),则 ep(a) | n .
原根的定义：
具有最高次数 ep(g) = p-1 的数g 称为模p下的原根。
若a是模p下的原根（ 即ep(a) = p-1 ）则 a,a^2,a^3,...,a^(p-1)余数各不相同。
原根定理：
如果整数a有原根，则a的原根数量为 ф(ф(p))
特别的：每个素数p都有原根，且原根的个数恰好为 ф(p-1)
指标：
模素数p的原根设为g，则指标I(a)满足 g^I(a) ≡ a(mod p) ,1 <= a < p;
指标法则：
- I(ab) = I(a) + I(b) (mod p-1)
- I(a^k) = k*I(a) (mod p-1)
九、二次剩余
设 a ∈ Zn* ，如果存在正整数 b ，使得 b² ≡ a(mod n) , 则称 a 为模n下的二次剩余。
并称 b 为 a 在模n下的平方根。否则称为二次非剩余。
如：1，2，4是模7下的二次剩余。3，5，6是模7下的二次非剩余。
奇素数p下的二次剩余
引言：
对于任意的奇素数p， b² ≡ (p-b)²(mod p) 总成立、
证明：
因为 (p-b)² = p² - 2*p*b + b²
而 p | p² 且 p | 2*p*b
所以 p | (p² - 2*p*b)
所以 p² - 2*p*b (mod p) ≡ 0(mod p)
所以 b² ≡ (p-b)²(mod p)
性质：
- 设 b ∈ Zp, 则 b² = 1 等价于 b = ±1
- 设 b,c ∈ Zp*,则 b² = c² 等价于 b = ±c
- | (Zp*)² | = φ(p) / 2 (模p下二次剩余的数量)
- 设p为奇素数，a,b ∈ Zp*,则：
当a,b都是二次剩余时，a*b 也是二次剩余
当a,b都是二次非剩余时，a*b也是二次非剩余。
欧拉准则：
设 p 是奇素数，设 a ∈ Zp* 则 a^( (p-1)/2 ) = ±1
- 当且仅当 a^( (p-1)/2 ) = +1 时，a是二次剩余。
- 当且仅当 a^( (p-1)/2 ) = -1 时，a是非二次剩余。
设p为奇素数，则模p^k下的二次剩余
性质：
- 设 b ∈ Zp^k, 则 b² = 1 等价于 b = ±1
- 设 b,c ∈ Zp^k*,则 b² = c² 等价于 b = ±c
- | (Zp^k*)² | = φ(p^k) / 2 (模p^k下二次剩余的数量)
- 设p为奇素数，a,b ∈ Zp^k*,则：
当a,b都是二次剩余时，a*b 也是二次剩余
当a,b都是二次非剩余时，a*b也是二次非剩余。
判断a是否是二次剩余：
设 p 是奇素数，设 a ∈ Zp* 则 a^( φ(p^k)/2 ) = ±1
- 当且仅当 a^( φ(p^k)/2 ) = +1 时，a是二次剩余。
- 当且仅当 a^( φ(p^k)/2 ) = -1 时，a是非二次剩余。
设n为奇数，则模n下的二次剩余：
则 |(Zn*)²| = φ(n) / 2^m (其中m是n经过算数基本定理分解后，不同质因子的数量)
如：
n = 45 时，模n下二次剩余的数量为 φ(45) / 2^2 = 6
这里不同的质因子分别为 3,5。因为 45 = 3²·5; 所以 m = 2
群论基础
初等群论
一、
1、命题
可谈论(但未必能确定)其真假值得语句。
二、集合
1、定义
某些恰当得群体。
如：
N{s|s是正整数}
Z{s|s是整数}
Q{s|s是有理数}
R{s|s是实数}
C{s|s是复数}
2、集合中得概念
- 空集合: 没有任何元素得集合。
- 子集: 如果T得元素都是S得元素，成T是S得子集。
- 幂集合: 对于一个集合S，它的所有子集构成的集合叫做它的幂集合，或幂集。
- 笛卡尔积: 给定两个集合 S,T、则S和T的笛卡尔积为 S×T = {(s,t) | s∈S 且 t∈T}
- 映射: 映射是指一种规则，这种规则规定了"集合S中的元素与集合T中元素的对应关系。
S称为该映射的逆像集(或称定义域)，T叫做该映射的象集(或称值域)。映射可以用小写
字母表示。如f,g,h等。映射并不一定有公式表达，只需表达清楚映射规则即可。
- 单射: S中任意两个相异的元素被映射到T中后，得到的两个元素仍然相异。
- 满射: T中的每个元素都被某个S中的元素映射到。
- 对射: 既是单设又是漫射的映射。
- 复合映射: 给定两个映射f和g，则形如 g(f(x))的映射叫做复合映射。
- 集合的基数: 将有限元素的集合S中，元素的个数记作 |S|.
如果说集合S和集合T拥有相同的基数，意思是存在一个S到T的对射。
如果说集合S的基数不大于集合T的基数，意思是存在一个S到T的单射。
- 可数集: 如果S是有限集或者S和自然数N有相同的基数，则称S是可数集。
三、群
1、二元运算
定义：
集合S上的一个二元运算是指一个 "由 S×S 到 S 的映射" ，记作 "(S,▢)"。
(其中S×S是S与自身的笛卡尔积)
约定：
假设 s1,s2∈S, 当s1和s2做该二元运算时，可简单的写作 "s1 ▢ s2"。
这里▢可以是任意符号如 "*" , "+" , "÷"等等。
2、结合律
当我们说二元关系(S,▢)是结合的，意思是说：对于S中的任意三个元素a、b、c,
总有 (a ▢ b) ▢ c = a ▢ (b ▢ c) 。
3、单位元
定义：
如果s中的某个元素e在二元运算(S,▢)上满足：
任意一个S中的元素s有 s▢e = e▢s = s 称e是二元运算(S,▢)下的单位元。
注意：
二元运算下的单位元要么没有，要么只有一个。
(假设有e1,e2两个单位元，则e1▢e2 = e2▢e1 = e1 = e2,即这两个单位元一样)
4、可逆
假设二元运算(S,▢)有单位元e , 如果对于S中某个元素s,S中存在一个元素s' ，
使得 s▢s' = s'▢s = e，则称s在(S,▢)下可逆。并且称 s' 是 s 在二元运
算(S,▢)下的逆元（或称反元素）
5、群
群的定义
有一个集合G和定义在G上的一种运算 ▢ , 如果 G 对 ▢ 满足以下四个条件：
(1) 封闭性 （ 即▢是G上的二元运算 ）
(2) 结合律
(3) 单位元
(4) 可逆性 （每一个G中的元素都有逆元）
那么称集合G是一个群。集合中的元素叫做群元。
群的性质：
(1) 单位元E的逆元是其本身
(2) 逆元的逆等于群元本身
(3) (a▢b)^-1 = b^-1 ▢ a^-1
子群
定义：
对于一个群(G,·)，若G的一个子集H满足下面两个条件，称H是G的子群
(1) "·" 是H上的二元运算
(2) (H,·) 是一个群
性质：
- 子群的单位元等于群的单位元。
- 子群中任意元素的逆元等于群中该元素的逆元。
群中一子集生成的子群
假设(G,·)是一个群，T是G的一个子集，定义包含集合T的最小子群为:
<T> := 所有G的子群的交集。则：
<T> = {t1^a1·t2^a2...tn^an | t1,t2...tn都是T的元素,a1,a2...an是整数}
补充：
假设(S,·)是一个群，对于S中的一个元素s，则
s·s·s·...·s(k个s) k > 0
s^k := e k = 0
s^-1·...·s^-1(k个s^-1) k < 0
特别的：
当T只含有一个元素g时，即 T = {g},则称 <T> = {g^k | k ∈ Z} 为由元素g
生成的子群。可简单记作 <g>
阿贝尔群
如果一个群 (G,▢)中，对于G中任意的两个元素a,b满足，a▢b = b▢a , 那么称该群
为交换群(或 阿贝尔群)
循环群
设a是群G的一个元素，则a的所有幂的集合 { a^n | n∈Z } 构成G的一个子群，称为
由 a 生成的循环子群，记作<a> 。若群G恰好可有由它的一个元素a所生成，即存在a，
使得G = <a>，则称群 G 为循环群， a 为群 G 的生成元。
定理：每个循环群都是 Abel 群。
分类：
无限循环群：<a>中的元素彼此各不相同，a的周期为无穷大。
有限循环群：<a>中出现重复的元素，即存在 s ≠ t,使得 a^s = a^t ,
令 n = min|s-t|,则 a 的周期为 n
称 <a> = {a,a^2,a^3...a^(n-1)} 为 n阶循环群。
性质：
设群G中元素a的周期为n
(1) e的周期为1
(2) a^-1 的周期为n
(3) <a>的元素个数为n，且 <a> = {e,a,a^2,a^3...a^(n-1)}
(4) a^m = e;当且仅当 n|m
(5) a^s = a^t; 当且仅当 n|(s-t)
循环群的生成元
① 若 G 是无限循环群，则 G 只有两个生成元，即 a 和 a^-1 ；
② 若 G 是 n 阶循环群，则 a^k 是 G 的生成元，当且仅当 k 与 n 互质。
因此， G 含有 φ(n) 个生成元。
循环群的子群
① 若 G 是循环群，则 G 的子群仍是循环群；
② 若 G 是无限循环群，则 G 的子群除 {e} 以外都是无限循环群；
③ 若 G 是n阶循环群，则对于n的每个正因子d，G 恰好含有一个 n/d 阶子群。
半群
有一个集合G和定义在G上的一种运算 ▢ , 如果 G 对 ▢ 满足以下两个条件：
(1) 封闭性
(2) 结合律
则称 (G,▢)是一个半群。
四、环
1、环的定义：
在集合R上定义了两种二元运算 + 和 · 且满足：
(1) (R,+) 是一个阿贝尔群.
(2) (R,·) 是一个半群。
(3) + 和 · 满足分配律。即，对于R中的任意三个元素a,b,c 有：
(a+b)·c = a·c + b·c （左结合律）
a·(b+c) = a·b + a·c （右结合律）
则称(R,+,·)是一个环。
交换环：
如果环中的二元运算 · 满足交换律，则称这个环为交换环。
含单位元的环
当环R中存在元素e，使得对环R中任意一个元素a都有e·a=a·e=a时，我们称e为环R的
单位元，并且称环R为含单位元的环。通常在不会产生混淆时，a·b简记为ab。
注意，在环中，二元运算+的单位元通常记为0，叫做零元
除环(或称斜环)
如果一个环中除非零元素外，其他元素在二元运算·下构成群，称该环为除环(或叫做斜环)
域：
域是一个非空集合，其上定义两种二元运算"+"和"·"，该集合关于二元运算"+"构成Abel群
该集合中的非零元素关于乘法运算也构成Abel群。(即"域是可交换的除环")
椭圆曲线
待补充。。。
双线性映射
双线性映射的定义
注意：现在的密码学相关论文中，习惯将$G_1$, $G_2$设置为乘法循环群。但是，基于椭圆曲线的双线性群构造中，$G_1$, $G_2$是加法群。在大约2005年以前的论文中，$G_1$，$G_2$是加法循环群。双线性映射可以通过有限域上的超椭圆曲线上的Tate对或Weil对来构造。
双线性映射的分类
根据$\mathbb{G}_1$与$\mathbb{G}_2$是否为同一个群，可以划分为 对称式与非对称式，具体分类见下表。
| 符号 | 介绍 | 备注 |
|---|---|---|
| $G_1×G_1→G_T$ | $G_1=G_2$，被称为对称型双线性映射 | Type-1型配对"：安全性最低 |
| $G_1×G_2→G_T$ | $G_1\neq G_2$但存在$G_1到G_2$的同态映射 | Type-2型配对"：安全性适中 |
| $G_1×G_2→G_T$ | $G_1\neq G_2$且它们之间不存在同态关系 | Type-3型配对"：安全性较高 |
值得注意的是：Type-3配对在带宽和计算效率方面提供了最有效的实现选择。非对称的双线性映射由于两个群$G_1, G_2$的大小可以取为不一样的，这样就会导致在两个群上计算点乘运算的计算开销不同。合理利用这一点，可以实现一些特殊的功能。【参考SM9算法】
双线性映射的性质：
假设加法循环群**$G_1$的生成元为$P$，则
- $e(A+B, C)=e(A, C)*e(B, C)$
- $e(A, B+C)=e(A, B)*e(A, C)$
- $e(xA, B)=e(A, xB)=e(A, B)^x$
- $e(A+B, C+D)=e(A, C)*e(A, D)*e(B, C)*e(A, D)$
- $e(A, B)^x*e(A, B)^y=e(A, B)^{x+y}$
- $e(A, B)*e(C, D)=e(A+C, B+D)*e(A, D)^{-1}*e(B, C)^{-1}$
这里给出$e(A+B, C)=e(A, C)*e(B, C)$的证明，其余定理证明同理。
证明： 由于$A$和$B$是群$G_1$上的两个元素，故存在a, b满足 $A=aP，B=bP$；则
$e(A+B, C)=e((a+b)P, C)=e(P, C)^{a+b}=e(P, C)^a*e(P, C)^b$. 即，
$e(A+B, C)=e((a+b)P, C)=e(aP, C)*e(bP, C)=e(A, C)*e(B, C)$
补充：用上述的证明方法可以证明，在非对称的双线性映射中，上述性质也是成立的。即：
- $e(A+B, C)=e(A, C)*e(B, C)$
- $e(A, B+C)=e(A, B)*e(A, C)$
- $e(A^x, B)=e(A, B^x)=e(A, B)^x$
- $e(A+B, C+D)=e(A, C)*e(A, D)*e(B, C)*e(A, D)$
- $e(A, B)^x*e(A, B)^y=e(A, B)^{x+y}$
- $e(A, B)*e(C, D)=e(A+C, B+D)*e(A, D)^{-1}*e(B, C)^{-1}$
伪随机函数（PRF）与（OPRF）
概念
简要介绍：
正式定义：
基于PRF的CPA加密方案
证明备注：
- 当D面对的是一个真随机函数时，A为了在游戏中获得优势，选择$m_0, m_1$之前一共进行了q(n)次Oracle查询，如果他这q(n)次全部查询的是$m_0$的密文，最好的情况是：A每次询问得到的密文$<r, y\oplus m>$中 r都不同，则他能获得$m_0$的q(n)个不同的密文。由于加密时选择的$r$一共有$2^n$种可能，也就是$m_0$至少有$2^n$个不同的密文。所以A区分$m_0$的密文成功率不超过$q(n)/2^n$, 故
- 上面的$ε(n)$表示当D面对的是伪随机函数的时候，A赢得游戏的优势
参考文献：
PRF的应用
参考文献：