RSA中的数学概念
一、质数与互质
质数(Prime number,又称素数),指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数(也可定义为只有1与该数本身两个正因数的数)。互质:公约数只有1的两个整数,叫做互质整数。公约数只有1的两个自然数,叫做互质自然数,后者是前者的特殊情形。
二、费马小定理
描述:
证明:
1、构建集合X:X = { 1、2、......、p-1 }。显然,集合X中的每个元素都与p互质(互素),所以可得:
1*2*...*(p-1) = ((p-1)!) ≡ 1 (mod) p。
2、构建集合Y:Y = {a mod p, 2*a mod p, ...,(p-1)*a mod p} 。
①、集合Y中没有元素等于0:因为 a 不是 p 的整数倍,且,从1到(p-1)都与p互素,所以 Y 中任一元素都不会等于0。 即:( a * i ) ( mod p) != 0, 1 <= i <= ( p - 1 )。
②、集合 Y 中,意义两个元素都不相等:
令 Y 中两个元素为 yi,yj,1 <= i < j <= (p-1),则有yi = (i * a) (mod p),yj = (j * a) (mod p)。
假设,yi = yj,则,(i * a) (mod p) = (j * a) (mod p)。因为,a 与 p 互素,所以等式两边除以 a 后仍然相等。
即,i (mod p) = j (mod p),也即,i = j。而这个与初始假设 i < j 是矛盾的,所以,集合 Y 中,意义两个元素都不相等
③、集合 Y 等价于 X,只是元素顺序不同:根据集合 Y 的定义,以及①和②可以得到如下4个事实:
1)、集合 Y 中元素的个数为 (p-1) 个
2)、集合 Y 中元素的最小值为1
3)、集合 Y 中元素的最大值为(p-1)
4)、集合 Y 中,任意两个元素都不相等
由上可知,Y = {1,2 ... p-1} = X,不考虑集合中元素的顺序
3、将集合 X 中所有元素相乘,并对 p 取模。集合 Y 中所有元素相乘,并对 p 取模。
根据③,则有:
(a mod p) * ((2 * a) (mod p)) * ... * ((p-1) * a (mod p)) = (1 * 2 * ... (p-1)) (mod p)
等价于:(a * (2 * a) * ... * ((p-1) * a)) (mod p) = (1 * 2 * ... (p-1)) (mod p)
等价于:(ap-1 * ((p-1)!)) ≡ ((p-1)!) (mod p)
因为,((p-1)!) ≡ 1(mod p),所以,ap-1 ≡ 1(mod p)
费马小定理得证。
三、欧拉函数
欧拉函数φ(N)表示小于或等于N的正整数中与N互质的数的个数。又称φ函数、欧拉商数。以下为欧拉函数的性质:
可根据以上性质求出欧拉函数:
首先置φ(N)=N,然后枚举素数p,将p的整数倍的欧拉函数φ(kp)进行如下操作:
补充: