转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720098311658625/
RSA加密系统，实际上基于这样一个基本事实。大数的素性测试要比因子分解简单的多，因子分解是一个难问题。
素数测试
如何测试一个数n是不是素数呢？简单的办法就是试一下它能否整除比它小的那些数，当然可以优化只检测小于sqare(n),但是无论如何优化，需要检测的数的个数都将不会小于小于sqare(n)的素数的个数。根据拉格朗日定理，小于n的素数的个数大概=n/ln(n)，也就是说这个数目很大，数量级上很接近n了。所以这个路子实际上很难降低复杂度。
先看一个定理，1640年费马小定理：
对于一个素数p,所有的 1<a<p 满足 a^(p-1) = 1 mod p
正是这个定理被用来进行素数测试，用它进行测试，还得满足另一个条件如果p是合数等式不成立，当然最好是对于所有的a都不成立。但是实际上只能保证有一部分a不成立。比如合数341=11*31 但是2^340 = 1 mod 341.这样只能退而求其次，如果能保证对绝大多数的a不成立也可以啊。实际上这点是成立的。
可以证明，对于一个合数我们至少可以找到让它不满足费马等式的a占到一半。
这个事实可以这样证明。我们首先假设存在某一个数a，a^(p-1) != 1 mod p.这样我们在假设所有满足的数b 对于每一个满足的数b我们都可以找到一个对应的数a*b，而这个数刚好不满足费马等式。因为(ab)^(p-1) = b^(p-1) != 1 mod p.
当然也保证这个结论成立，还得有一些知识，首先对于固定的a，当它乘以不同的b时，它们mod p的结果都是不同的，实际上这又基于另一个结论:{对于 1< x < p ,将它们变成nx%p，实际上是进行了一个新的映射，也就是说不会出现重复值。}这样呢，就保证了a*b mod p之后不会是重复的数，也就保证了它们的个数不会缩水。
我们可以看到每找到一个满足的，就可以找到一个不满足的，这就说明不满足的数目起码不会比满足的数目少。当也有意外情况，实际上也有一类合数n很特殊对于它们来说，对于所有与n互素的数a，它们都满足a^(n-1) = 1 mod n，这样的数被叫做卡迈克尔数。最起码这种数会降低测试的准确度，严重的可能导致存在一个可以完全通过费马测试的合数。
针对这种情况，Rabin and Miller测试又加了项，基于如下定理：如果一个数!= 正负1 mod N，但它的平方=1 mod N,那么这个数是合数。所以在计算a^(N-1)的时候，首先把N-1写成了2^t*u的形式，然后逐步计算a^u mod N, a^2u mod N…a^(N-1) mod N，当首次发现1时，检查它的前一项结果是不是1或者-1.这样就可以进一步提供测试的精度。
实际的测试，只要看a=2就可以了，因为只有很少一部分合数可以通过这个测试。
RSA系统
因为它有一个公钥和私钥，这个是可以公开的，这样就不需要一个秘密会面，只要把自己的公钥公布，这样其他人就可以利用这个公钥直接加密，第三者即使拿到公钥也还是无法知道内容，只有利用私钥才能解密。
传统的加密方法，是发送者和接受者使用同一个密钥。
现在RSA由于效率不够高，还主要用作开头传递密钥方面。然后用这个传统密钥进行传输的加密。
实际上这样一个全新的加密系统，正是基于了素数测试和因子分解这两个问题的不对称性。
首先信息的接受者生成两个大素数p q，方法就是随机生成大数，然后用素数测试它是不是素数，因为素数的分布密度是很高的，所以可以很快得到两个大素数。
然后计算N=pq,同时选择一个与(q-1)(p-1)互素的数e，计算出一个d值，ed = 1 mod (q-1)(p-1)，实际上就是求e的逆元，这个可以利用扩展欧几里德算法求解。然后把(N,e)作为公钥发布，(N,d)则是私钥。
假设要发送的信息为x(x<N)，则x’ = x^e mod N,这样x’就是加密后的数，发送它,
然后接受者x’,计算x’^d mod N ,这个结果就等于x.
实际上这里面依赖于一个等式 x = x^ed mod N,而之所以选择(q-1)(p-1)正是为了保证这个等式的成立。下面来证明为什么 x = x^ed mod N。
因为ed= 1 mod (q-1)(p-1)，可以写成ed = 1+k(q-1)(p-1)
我们需要证明x^ed – x = 0 mod N 即x^(1+k(q-1)(p-1)) – x = 0 mod N
而x^(1+k(q-1)(p-1)) – x = x*(x^k(q-1)(p-1) – 1)
而根据费马小定理，我们又有x^(p-1) = 1 mod p,x^(q-1) = 1 mod q，p,q是素数所以mod它们的乘积也满
足x^k(q-1)(p-1) = 1 mod pq = 1 mod N，这样x^k(q-1)(p-1) -1 = 0 mod N，很明显x*(x^k(q-1)(p-1) – 1) = 0 mod N,证明完毕。
实际上正是通过选择ed= 1+k(q-1)(p-1)，保证了x^k(q-1)(p-1) mod N =1 也就保证了x = x^ed mod N