RSA加密算法数学基础

1.同余类

• 概念：给定正整数，全体整数可按照模是否同余分成若干两两不相交的集合，使得每一个集合中的任意两个正整数对模一定同余，而属于不同集合的任意两个整数对模不同余，每一个这样的集合称为模的同余类或剩余类。
• 例子：取，则是模7的同余类。
• 定理：对于给定的正整数，有且恰有个不同的模的剩余类。
• 模的m个剩余类可分别记为，为该剩余类中整数除所得的余数，可分别如下表示：
  
  
  
  ...
  

2.完全剩余系

• 概念：在整数模的所有剩余类中各取一个代表元素，则称为模的完全剩余系。完全剩余系。
• 例子：为模7的一组完全剩余系。为模的最小非负完全剩余系。
• 表示由的最小非负完全剩余系集合。中的加法、减法、乘法都是模下的运算。
• 定理：设是正整数，整数满足，是任意整数。若遍历模的一个完全剩余系，则也遍历模的一个完全剩余系。
• 定理：设是两个互素的正整数。如果遍历模的一个完全剩余系，遍历模的一个完全剩余系，则遍历模的一个完全剩余系。

3.欧拉函数

• 在模的一个剩余类当中，如果有一个数与互素，则该剩余类中所有的数均与互素，这时称该剩余类与互素。
• 概念：与互素的剩余类的个数称为欧拉函数，记为。等于当中与互素的数的个数。对于任意一个素数，。
• 例子：，表示中与互素的数的个数，既。

4.简化剩余系

• 概念：在与互素的个模的剩余类中各取一个代表元，它们组成的集合称为模的一个既约剩余系或简化剩余系。中与互素的数构成模的一个既约剩余系，称为最小非负既约剩余系。
• 定理：设是正整数。整数满足。若遍历模的一个既约剩余系，则也遍历模的一个既约剩余系。
• 定理：设是两个互素的正整数。如果遍历模的一个既约剩余系，遍历模的一个既约剩余系，则遍历模的一个既约剩余系。

5.欧拉定理

• 推论：设是两个互素的整数，则。
• 定理：若，则。
  证明：当为单个素数的方幂时，在模的完全剩余系的整数中与不互素的只有的倍数，共有，因此与互素的数共有，即，根据上面的推论有。
• 例子：
• 定理：设是正整数，，若，则存在整数，使得，整数也成为模整数下的乘法逆元。
• 例子：求的乘法逆元。
  解：与互素，存在乘法逆元。做辗转相除法，可得：
  
  
  
  
  由此有：
  
  
  
  
  
  
  
  所以的乘法逆元为。
• 欧拉定理：设是正整数，，若，则。

参考文献：

电子科技大学-现代密码学课件。