异想天开

What's the true meaning of light, Could you tell me why

数论中的欧拉定理-RSA算法数学基础

日期:2014-05-28 18:27:48
  
最后更新日期:2014-10-26 11:41:40
数论中,欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,则:
1 该欧拉定理的证明参考百度百科。数学中引入概念往往是为让证明看起来简洁,《第五项修炼》一书中对抽象的是这样认为的,抽象前提是了解概念由具体到抽象的过程,否则抽象反而成为你的羁绊 需要了解的几个概念,这几个概念是其他人引入的:
互质:
如果两个正整数,除了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 ) 。