《密码技术与物联网安全：mbedtls开发实战》 —3.6　欧拉函数

3.6　欧拉函数

定义3-12

若m是一个正整数，则从1到m中与m互素的整数的个数，记作φ(m)，通常叫作欧拉（Euler）函数。

两个数互素也就是它们最大公约数为1，gcd(a,b)=1表示a和b互素。

例3-12　计算φ(6)

当m=6时，计算小于m并且与m互素的正整数的个数。从表3-14的结果可以看出，只有整数1和5与6互为素数，所以φ(6)=2。

表3-14　φ(6)计算过程

例3-13　计算φ(7)

当m=7时，计算小于m并且与m互素的正整数的个数。从表3-15的结果可以看出，整数1到6均与7互为素数，所以φ(7)=6。

表3-15　φ(7)计算过程

很明显，对于素数p而言，φ(p)=p-1。而当存在两个不相等的素数p和q，假设n=pq，则有φ(n)=φ(p·q)=φ(p)·φ(q)=(p-1)·(q-1)。

例3-14　计算φ(15)

当m=15时，计算小于m并且与m互素的正整数个数。从表3-16的结果可以看出，整数1、2、4、7、8、11、13和15都与15互为素数，与15互为素数的个数为8，所以φ(15)=φ(3)×φ(5)=2×4=8。

表3-16　φ(15)计算过程