质数
质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。
来自 https://zh.wikipedia.org/wiki/质数
互质
互质是公约数只有1的两个整数，也可记gcd(a,b)=1, 叫做互质整数。
欧拉
在数论中，对正整数n，欧拉函数phi(n)是小于等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。
来自 https://zh.wikipedia.org/wiki/欧拉函数
例如 11 的欧拉:
比11小且与11互质的正整数有: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
所以phi(11) = 10 = 11-1由上例子同时可知, 质数的欧拉是他本身减1: phi(N) = N - 1
同时 歐拉函數是積性函數，即是说若m,n互質，則 phi(mn) = phi(m)phi(n)
欧几里得算法
也叫辗转相除法，用来找出两个数的最大公约数gcd(a,b)
商记作qi, 余数记作ri, 欧几里得算法可写为 ri-1 = qi * ri + ri+1
eg1: 寻找160, 11 的最大公约数
ri-1 = qi * ri + ri+1 | 商qi | 余数ri |
|---|---|---|
| 160 | ||
| 11 | ||
| 160 = 14 * 11 + 6 | 14 | 6 |
| 11 = 1 * 6 + 5 | 1 | 5 |
| 6 = 1 * 5 + 1 | 1 | 1 |
| 5 = 5 * 1 + 0 | 5 | 0 |
可得最大公约数为1, 同时因为gcd(160,11) = 1, 所以 160, 11 互质
eg2: 寻找 160, 122 的最大公约数
ri-1 = qi * ri + ri+1 | 商qi | 余数ri |
|---|---|---|
| 160 | ||
| 122 | ||
| 160 = 1 * 122 + 38 | 1 | 38 |
| 122 = 3 * 38 +8 | 3 | 8 |
| 38 = 4 * 8 + 6 | 4 | 6 |
| 8 = 1 * 6 + 2 | 1 | 2 |
| 6 = 3 * 2 + 0 | 3 | 0 |
所以最大公约数为2
模反元素
模逆元也称为模倒数，或者模逆元。<- 模反元素
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。
如3关于20的模反元素是7，(3*7)%20=1 https://zh.wikipedia.org/wiki/模反元素
拓展欧几里得算法
计算欧几里得同时多计算si-1 = qi *si + si+1和si-1 = qi *si + si+1, 初始分别为s0 = 1,s1 = 0和t0 = 0, t1 = 1，
寻找出满足 ax + by = gcd(x,y)的a,b, 同时还可用来求模乘逆元
eg1: 寻找160, 11 的最大公约数
ri-1 = qi * ri + ri+1 | 商qi | 余数ri | si-1 = qi * si + si+1 | si | ti-1 = qi * si + ti+1 | ti |
|---|---|---|---|---|---|---|
| 160 | 1 | 0 | ||||
| 11 | 0 | 1 | ||||
| 160 = 14 * 11 + 6 | 14 | 6 | 1 = 14 * 0 + 1 | 1 | 0 = 14 * 1 - 14 | -14 |
| 11 = 1 * 6 + 5 | 1 | 5 | 0 = 1 * 1 - 1 | -1 | 1 = 1 * (-14) + 15 | 15 |
| 6 = 1 * 5 + 1 | 1 | 1 | 1 = 1 * (-1) + 2 | 2 | -14= 1 * 15 - 29 | -29 |
| 5 = 5 * 1 + 0 | 5 | 0 | -1 = 5 * 2 - 11 | 11 | 15 = 5 * (-29) + 130 | 130 |
可得 gcd(160,11) = 1 = 2 * 160 + (-29) * 11 = 320 - 319,
所以
2是160关于11的模乘逆元
131 = -29 + 160是11关于160的模乘逆元, 因为-29为负数需要加上模变成正数
欧拉定理
在数论中，欧拉定理（也称费马-欧拉定理或欧拉phi函数定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互素（即gcd(a,n)=1），则
a^phi(n) = 1 (mod n)
即 a^phi(n)与1在模n下同余。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。
gcd: greatest common divisor(最大公约数)
RSA
- 隨意選擇兩個大的質數 p和q,p不等于q,计算N=pq.
- 求N的欧拉，r = phi(N) = phi(q) x phi(p) = (p-1)(q-1)
- 选择一个小于r的整数e，使e与r互质。並求得e关于r的模反元素，命名为d。
- (N,e)是公钥，(N,d)是私钥。
- 加密原文m, 得到密文 x = (m^e)%N
- 解密公式为 m = (x^d)%N
只能加密比N小的数字，比N大的数字无法加密。
eg：
选择两个质数3,11。
计算得到N=3*11=33
计算N的欧拉，r=phi(N)=phi(3)*phi(11)=(3-1)(11-1)=20
选择一个小于的r且与r互质的整数3，求得3关于20的模反元素7
得到公钥(33,3),私钥(33,7)
加密：
加密数字24，(24^3)%33 = 30, 获得加密后的密文 30
解密：
对密文30解密，(30^7)%33 = 24, 获得解密后的明文24