看了《数学之美》第17章 的谈谈密码学的数学原理，没搞清楚，整合一下网上搜到的知识，加深一下理解。

Crookes Radiometer（看视频时，一个有意思的东西）

当光照到玻璃里的叶片时，其便会自动旋转，为什么呢？
http://blog.sina.cn/dpool/blog/s/blog_b189037d0102yn3g.html
这里讲的很清楚了，并不是光压。
这个图片来自：很有意思的一篇文章，想着给自己桌子上也摆个这些小东西，哈哈哈。

欧拉定理在RSA公钥加密中的应用及原理

将信息变作一组数（例如ASCLL码），记作 m（message）
加密时： c≡ m^e mod N (c 就是加密后的信息）
解密时：c^d mod N≡m

在这个式子里 e，d就像是两把钥匙， 知道了e，n，便可加密，知道了d,n便可解密。
问题：
1.这两个式子是成立的吗？
2.怎么求各未知变量？
3.这样做，能够达到加密的效果吗？

1.这两个式子是成立的吗？

即求出式子中的未知变量：
c≡ m^e mod N①
c^d mod N≡m②

将①带入② 得：（m^e mod N）^d mod N=m^(e*d) mod N=m ③ 模的运算
即证明 m^(e*d) mod N=m 恒成立
1.当m和N互素
根据费马欧拉定理（则m，e，d，n均为正整数)④:费马欧拉定理

令 e*d=kφ(N)+1 即 e*d=1 mod φ(N)
即可求出 d=e^(-1) （1mod φ(N)）
此时，可有m^(e*d) mod N=m 恒成立
2.当m和N不互素
仍构造
e*d=kφ(N)+1即 e*d=1 mod φ(N)
即适当选择N，构造相同于费马欧拉定理下的形式
书上是这样构造的：
1.选择两个很大的素数P,Q
记 N=P*Q
----------------
note1.如果n可以分解成两个互质的整数之积，则
φ(n) = φ(p1p2) = φ(p1)φ(p2) （欧拉函数）
note2.如果n是质数，则 φ(n)=n-1 
----------------
令M=(P-1)(Q-1)=φ(N)
这时，因为N=P*Q，所以m=kQ或kP。
因为不互素，N,m存在非1公约数，而 N的约数为 1 Q P
所以m和N的公约数 为Q 或 P
当取N>>m时候 m的公约数应不存在 Q*P项
N须远远大于m
所以 m=KQ或者 m=KP，两者不可同时成立
这时，KQ和P 互素 /// KP和 Q互素
----------
一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系
----------
所以，根据欧拉定理 且不妨m=KQ
(KQ)^(P-1) ≡ 1 (mod P)
进一步，∵a ^ b % p = ((a % p)^b) % p
又∵ 1^k=1
∴KQ→KQ的k(P-1)次方 仍满足上式
[(KQ)^(P-1)]^(k(p-1)) ≡ 1 (mod P)
等式左右再×KQ
(KQ)^[k(Q-1)(p-1)+1] ≡ KQ (mod P)
∵ed=[k(Q-1)(p-1)+1]
∴(KQ)^(ed)=KQ (mod P)
∴(KQ)^(ed)=tP+KQ
tP=KQ( (KQ）^(ed-1) -1 )
所以t必然能被Q整除
所以 t=t'Q
∴(m)^(ed)=t'N+m
即 (m)^(ed)=m mod N 成立
综上 ，上述两式恒成立

2.怎么求各未知变量？

那么，对于各个未知变量的限制要求是什么，我们该如何构造这样的数呢？
选择两个很大的素数P,Q
构造方式：N=P*Q M=(P-1)(Q-1)
在这样情况下，由上面讨论，不论信息代码m与N互质与否，上式均成立，我们便在此条件下，计算未知变量 e ，d。

-1.一切变量都是正整数
Ⅰ将信息代码转为了一串正整数
Ⅱ费马欧拉定义也是在正整数的基础上
Ⅲ正整数也符合我们的思考方式
故一切变量都是正整数

1.式子e*d=1 mod φ(N)
所以e*d=1+kφ(N)
显然 e d 两个变量的关系仅有这个方程，我们如何选择更好的 “选一定一”？
先给定e，再找出d 显然二者选择时平权，随便选一个定下来
1.找到e，使得 gcd（e,M)=1,即e和M互素
2.找到整数d,有 e*d mod M=1即 d={k'M+1}/e

怎么保证 d求出为正整数？
M=(P-1)(Q-1) ∵ P、Q为素数，则M一定为偶数（M很大显然）
又∵ gcd（e,M)=1 ∴ e一定为奇数
k'M+1=ce? c为整数
问1：即 一个任意大的奇数，是否一定是某一较小奇数的整数倍？
偶数对于此问显然成立，任意偶数都是2的倍数
问2：当e和M不互质，则d一定不是整数？
当e，M存在公因数(偶数和奇数存在公因数，则该公因数肯定是奇数），
假设 一个奇数公因数为w且w＞1 则 M=yw, e=zw 显然，y为偶数 z为奇数
则 d={kM+1}/e={kyw+1}/zw= ky/z +1/zw
ky恒为偶数 ky/z>1/z>1/zw
所以 ky/z+1/zw<(ky+1)/z 奇数/奇数，
所以当e和M不互质,d一定不可成分子分母整数化简，d一定不是整数。
问3：e和M互质下，一定存在k 使得 d为整数？如何求？
e*d mod M=1 应化为 ed-1=kφ(N)=kM
即对 ed+Mk=1 二元一次方程求解
ex+My=1 扩展欧几里得算法
给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
即可解出 d值
综上，我们便可以解出 d，N，e
（d,N)作为私钥， （e,N)作为公钥 便可以用于加密和解密。
这便是"非对称加密算法"RSA算法。（介绍可以参看参考链接2）

3.这样做，能够达到加密的效果吗？

如何破解这个密码，即获得解密手段，公钥（N，e），当人们知道了N=P*Q,P,Q是哪两个元素时，相应 M会知道 则ed+Mk=1 ，d也就知道了。
进行快速的因式分解，是个庞大的计算量，一个个地试.
哈，套用知乎网友对破解RSA的时间回答，剩余有关RSA的问题，放到下一篇！。

附注·参考链接

附注·模的运算

附注·费马欧拉定理

---

费马-欧拉定理

费马-欧拉定理表明，若m,N为正整数，且m,N互素（即n，a最大公约数为1），则

m^φ(N)≡ 1 (mod N)
φ(N)为欧拉函数,即小于或等于N的正整数中与N互质的数的数目

∵ n为素数，φ(n)=n-1 则欧拉定理变为 费马小定理：
m^(N-1)≡1 (mod N)
a^N=a (mod N)

---