初等数论中模幂运算加解密成立的条件

```
创建: 2016-04-08 13:24
更新: 2023-12-04 17:32
https://scz.617.cn/misc/201604081324.txt
```

从初等数论角度看，为使模幂运算加解密成立，需要满足何种条件？数学专业的肯定不会在此问题上犯低级错误，计算机专业的，在此问题上或许会犯低级错误。

对于正整数n，在[1,n]中，有多少个整数与n互素？计算该值的方法叫做欧拉函数，以φ(n)或phi(n)表示。

欧拉定理:

若a、n>1都是正整数，且gcd(a,n)=1，则:

```
a^φ(n)≡1(mod n)
a^(φ(n)+1)≡a(mod n)
```

上述运算成立的「充要条件」里并未要求n为合数。

欧拉定理可进一步推广成Carmichael定理。设正整数n的素因子分解为:

```
n=(p1^k1)*(p2^k2)*...(pr^kr)
```

对于所有a属于Zn*(即[1,n-1])，有:

```
λ(n)=lcm(φ(p1^k1),φ(p2^k2),...,φ(pr^kr))
a^λ(n)≡1(mod n)
λ(n)|φ(n)
```

设n的素因子分解为:

n=p*q

有:

```
λ(n)=lcm(p-1,q-1)
```

RSA算法只是欧拉定理(也可以说是Carmichael定理)很小的一次应用。在RSA算法场景中，出于安全考虑，确实要求n是两个大素数的积，但这个要求不是欧拉定理本身的要求，不是模幂运算加解密成立的约束条件。

当n是单素数时，存在符合欧拉定理的情形，其中一种充分条件是:

gcd(m,n)=1

对于任意m<n的正整数，m均与n互素，从而模幂运算加解密成立。

设n为单素数，检验如下运算:

```
n=29
φ(n)=n-1=28
e=3
d=pow(e,-1,28)=19
m=16
c=pow(m,e,n)=7
pow(c,d,n)=16
```

上例完全符合欧拉定理，有n、e、d，能完成m、c之间的转换，与p、q是否存在无关。这种看上去很安全，其实跟没加密一样，因为φ(n)=n-1，进而轻松求d。不过单素数很容易被素性检测发现，不够隐蔽。这种想法是不对的，我不是教大家学坏。

原文始发于微信公众号（青衣十三楼飞花堂）：初等数论中模幂运算加解密成立的条件