一、互质关系(coprime)
定义
如果两个正整数,除了 1 外,没有其他的公因数,那么称这两个正整数是 互质关系
比如:18 和 29 没有公因数,它们是互质关系
推论
1、任意两个质数一定构成互质关系
比如:5 和 7
2、一个是质数,另一个只要不是前者的倍数,也一定构成互质关系
比如:5 和 11
3、两个数,较大的那个是质数,那两者也构成互质关系
比如:41 和 20
4、1和任何一个自然数都构成互质关系
5、如果 p是大于 1的正整数,那么 p 和 p -1 一定构成互质关系
6、如果 p 是大于1的正奇数,那么 p 和 p-2 一定构成互质关系
二、欧拉函数
定义
任意一个正整数 n,在小于等于它的正整数中,寻找与它构成互质关系的整数的个数,称为欧拉函数,用Φ(n)表示
比如:1到9中,与 9 形成互质关系的有1、2、4、5、7、8
推论
- 1、如果 n是质数,那么它的互质整数个数为 n - 1
ϕ(n)=n−1
- 2、如果 n是某质数的某次方,n = p ^ k (p为质数, k为大于等于 1 的整数)
ϕ(pk)=pk−pk−1=pk(1−p1)=pk−1(p+1)
n=p1×p2
那么,积的欧拉函数 等于 各个因数的欧拉函数之积
ϕ(n)=ϕ(p1p2)=ϕ(p1)ϕ(p2)
n=p1k1p2k2...prkr
那么,
ϕ(n)=ϕ(p1k1)ϕ(p2k2)...ϕ(prkr)=(p1k1p2k2...prkr)(1−p11)(1−p21)...(1−pr1)=n(1−p11)(1−p21)...(1−pr1)
三、欧拉定理
定义
如果两个正整数 a 和 n 是互质关系,那么有下列恒等式
aϕ(n)≡1(mod n)
或
aϕ(n)−1≡kn
费马小定理
如果正整数 a 和 质数 p 是互质关系,那么 p 的欧拉函数的值等于 p - 1
aϕ(p)=ap−1
ap−1≡1(mod p)
四、模反元素
如果两个正整数 a 和 n 互质,那么一定可以找到整数 b,使得 (ab -1) 能够被 n 整除 或 ab被 n 整除的余数是1
ab≡1(mod n)
# 欧拉定理
# RSA算法核心