RSA算法的数论基础分析

下面介绍RSA算法中需要使用的几个术语。

1)素数

素数又称为质数，是指在大于1的自然数中，除了1和此数自身外，不能被其他自然数整除的数。例如，15=3×5，所以15不是素数;又如，12=6×2=4×3，所以12也不是素数。而13除了等于13×1以外，不能再表示为其他任何两个整数的乘积，所以13是一个素数。

2)互为素数

公约数只有1的两个自然数，叫作互质数，即互素数。两个自然数是否互为素数的判别方法主要有以下8种(不限于此)。

① 两个质数一定是互质数，例如，2与7，13与19。

② 一个质数如果不能整除另一个合数，那么这两个数为互质数，例如，3与10，5与26。

③ 1不是质数也不是合数，它和任何一个自然数都是互质数，例如，1和9908。

④ 相邻的两个自然数是互质数，例如，15与16。

⑤ 相邻的两个奇数是互质数，例如，49与51。

⑥ 大数是质数的两个数是互质数，例如，97与88。

⑦ 小数是质数，大数不是小数的倍数的两个数是互质数，例如，7与16。

⑧ 两个数都是合数(两数之差又较大)，小数所有的质因数都不是大数的约数，这两个数是互质数。例如，357与715，357=3×7×17，而3、7和17都不是715的约数，所以这两个数为互质数。

3)模运算

模运算是整数运算，有一个整数m，以n为模做模运算，即mmod n。令m被n整除，只取所得的余数作为结果，就叫作模运算。例如，10 mod 3=1，26 mod 6=2，28 mod 2=0等。

模运算有以下性质。

① 同余性：若amod n=bmod n，则正整数a与b同余。

② 对称性：若a=b mod n，则b=amod n。

③ 传递性：若a=b mod n，b=cmod n，则a=cmod n。

4)Euler函数

任意给定正整数n，计算在小于或等于n的正整数之中有多少个与n能构成互质关系的方法叫作欧拉函数，以φ(n)表示。例如，φ(8)=4，这是因为在1~8之中与8能形成互质关系的数有4个：1，3，5，7。

φ(n)的计算方法并不复杂，下面分情况对其进行讨论。

第一种情况：如果n=1，则φ(1)=1，因为1与任何数(包括其自身)都能构成互质关系。

第二种情况：如果n是素数，则φ(n)=n-1，因为质数与每个小于它的数都能构成互质关系。

第三种情况：如果n是素数的某一个次方，如n=pk，p为素数，k≥1，则

φ(pk)=pk-pk-1

例如，φ(8)=φ(23)=23-22=4。这是因为只有当一个数不包含素数p时，才能与n互质。而包含素数p的数一共有pk-1个，即1×p、2×p、…、pk-1×p。

第四种情况：如果n可以分解成两个互质的整数之积，例如，n=p1×p2，则φ(n)=φ(p1p2)=φ(p1)φ(p2)，即积的欧拉函数等于各个因子的欧拉函数之积。例如，φ(56)=φ(7×8)=φ(7)×φ(8)=6×4=24。

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!