数论中的欧拉定理-RSA算法数学基础
日期:2014-05-28 18:27:48
最后更新日期:2014-10-26 11:41:40
该欧拉定理的证明参考百度百科。数学中引入概念往往是为让证明看起来简洁，《第五项修炼》一书中对抽象的是这样认为的，抽象前提是了解概念由具体到抽象的过程，否则抽象反而成为你的羁绊。
需要了解的几个概念，这几个概念是其他人引入的:互质：
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。
a)互质不一定要是质数，8和9就互质。
b)1和任何数都互质。
欧拉数：
正整数n的欧拉数φ(n)定义：小于n且与n互质的正整数。
a)质数p的欧拉数为p-1。
剩余系:
如果有个正整数n，所有小于n的正整数，且每个正整数都与n互质的正整数集合{x1,x2,x3...xφ(n)}，则称集合{x1,x2,...,xφ(n)}为数n的剩余系。
a)给定正整数n，剩余系是唯一的。
证明:
数n的剩余系为:{x1,x2,x3,...,xφ(n)},φ(n)为n的欧拉数。给定一个与n互质的数a，那么{a*x1 , a*x2 , a*x3,...,a*xφ(n) } (mod n)，还是数n的剩余系。因为：
a)xi与n互质，那么a*xi必定也与n互质。
b)若xi不等于xj，则a*xi mod n 必定也不等于a*xj mod n。若相等，则 (a*xi - a*xj) == 0 (mod n)，那么xi==xj，与前提矛盾。
所以这两个集合是相等的。
a*x1*a*x2...*a*xφ(n) mod n == x1*x2*x3...xφ(n) mod n。而a*x1*a*x2...*a*xφ(n) mod n可以表示为a^φ(n) * x1*x2...*xφ(n) mod n。即证明a^φ(n) == 1 ( mod n ) 。