数论 | xurna

文章目录

1. 一些概念

一些概念

1.对称密钥

1 2	（1）甲方选择某一种加密规则，对信息进行加密；（2）乙方使用同一种规则，对信息进行解密。

这种加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。

2.非对称密钥

1
2
3

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

3.互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系。

4.欧拉函数

思考：任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）

计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。

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

2) 情况二
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

3) 情况三
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
φ(p^k) = p^k - p^(k-1) = p^k(1-1/p)
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
可以看出，上面的第二种情况是 k=1 时的特例。

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

5) 情况五
因为任意一个大于1的正整数，都可以写成一系列质数的积。

根据第四条结论，得到：

在根据第三条结论，得到：

也就等于：

这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：

5.欧拉定理

欧拉函数的用处，在于欧拉定理。欧拉定理指的是：
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：

也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。