前提相关定义
质数的集合为$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) $$ 成立
相关阅读
- rsa论文原文 http://people.csail.mit.edu/rivest/Rsapaper.pdf
- 部分证明来源