Skip to main content

RSA

· One min read

前提相关定义​

质数的集合为$Pri$

rsa 的证明​

M是需要任意整数 , $e,d$需要满足

$$
e·d\equiv  1 \pmod{\phi(n)}     \qquad(1)
$$
我们要证明
$$
M^{e·d} ≡ M^{k·\phi(n)+1} \equiv M \pmod{n} \qquad(2)
$$
其中
#### 欧拉函数$\phi(x)$
$\phi(x)$定义是小于或等于n的正整数中与n互质的数的数目.
其中,如果`x`是质数,则欧拉函数的求值结果为`x-1`
$$\phi(x)=x-1 , x\in Pri $$

下面我们来证明公式$(2)$的右边部分 , 也就是:

$$
M^{k·\phi(n)+1} \equiv M \pmod{n} \qquad(3)
$$
- 当M可以被n整除的时候,也就是满足
$$
M ≡ 0 (mod p)
$$

成立

相关阅读​