RSA加密算法数学基础
2019-12-09 本文已影响0人
不懂球的2大业
1.同余类
- 概念:给定正整数,全体整数可按照模是否同余分成若干两两不相交的集合,使得每一个集合中的任意两个正整数对模一定同余,而属于不同集合的任意两个整数对模不同余,每一个这样的集合称为模的同余类或剩余类。
- 例子:取,则是模7的同余类。
- 定理:对于给定的正整数,有且恰有个不同的模的剩余类。
- 模的m个剩余类可分别记为,为该剩余类中整数除所得的余数,可分别如下表示:
...
2.完全剩余系
- 概念:在整数模的所有剩余类中各取一个代表元素,则称为模的完全剩余系。完全剩余系。
- 例子:为模7的一组完全剩余系。为模的最小非负完全剩余系。
- 表示由的最小非负完全剩余系集合。中的加法、减法、乘法都是模下的运算。
- 定理:设是正整数,整数满足,是任意整数。若遍历模的一个完全剩余系,则也遍历模的一个完全剩余系。
- 定理:设是两个互素的正整数。如果遍历模的一个完全剩余系,遍历模的一个完全剩余系,则遍历模的一个完全剩余系。
3.欧拉函数
- 在模的一个剩余类当中,如果有一个数与互素,则该剩余类中所有的数均与互素,这时称该剩余类与互素。
- 概念:与互素的剩余类的个数称为欧拉函数,记为。等于当中与互素的数的个数。对于任意一个素数,。
- 例子:,表示中与互素的数的个数,既。
4.简化剩余系
- 概念:在与互素的个模的剩余类中各取一个代表元,它们组成的集合称为模的一个既约剩余系或简化剩余系。中与互素的数构成模的一个既约剩余系,称为最小非负既约剩余系。
- 定理:设是正整数。整数满足。若遍历模的一个既约剩余系,则也遍历模的一个既约剩余系。
- 定理:设是两个互素的正整数。如果遍历模的一个既约剩余系,遍历模的一个既约剩余系,则遍历模的一个既约剩余系。
5.欧拉定理
- 推论:设是两个互素的整数,则。
- 定理:若,则。
证明:当为单个素数的方幂时,在模的完全剩余系的整数中与不互素的只有的倍数,共有,因此与互素的数共有,即,根据上面的推论有。 - 例子:
- 定理:设是正整数,,若,则存在整数,使得,整数也成为模整数下的乘法逆元。
- 例子:求的乘法逆元。
解:与互素,存在乘法逆元。做辗转相除法,可得:
由此有:
所以的乘法逆元为。 - 欧拉定理:设是正整数,,若,则。
参考文献:
电子科技大学-现代密码学课件。