数论中的欧拉定理-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 ) 。