RSA算法正确性证明
同时发布在知乎。
RSA算法的核心，在于大数因式分解这个问题的难于解决上。
为了解释起来比较方便，首先说明一下RSA算法的加密解密过程。
有两个大素数p和q，一般有1024位这么大，它们的乘积定为。
再取一个数e与互质，即。
另取一个数d，它是e在(p-1)*(q-1)模运算的逆元，即。
这就是RSA加密解密所需要的所有密钥了，在加密的时候，需要使用私钥e，假设M为明文，C为加密后的密文。那么有
在解密时，则需要使用公钥d。这时有
这样就实现了RSA加密解密的过程。
接下来是对RSA算法正确性的证明。首先还是需要一些背景知识的，比如著名的费马小定理
若p为素数，a为正整数且，那么有
这个定理的证明也很有趣，但是明显这里并不关注这个问题，让我们来使用这个定理证明RSA算法吧。
为了证明加密算法的正确性，要求证明下式总是恒成立的。
又因
所以
现在分情况讨论
1）
若M与n互质时，由欧拉定理有其中表示小于n且与n互质的数的总数。
由于且p，q均为素数，则有
所以得证。
2）
当M与n非互质时，由于，则必有
或
；
假设。
由费马小定理，有
所以
按照模运算定义，将上式改写为
由于,那么也必然能被p整除，即上式中t可表示为
所以有
即
在的情况下也是相同的证明。
综合上述两种情况就证明了RSA算法的正确性。
1、字节流通向字符流的桥梁：InputStreamReader
2、easyUI datagrid 不刷新问题
3、虚拟机无法上网的问题的解决
4、不同的风土民情 [搞笑]
5、about springmvc intergation jquery with ajax &no-ajax version