rsa加密算法原理

rsa加密算法原理：1、数和互为素数，任何大于1的整数a能被因式分解为如下唯一形式：a=p1p2…pl(p1,p2，…，pl为素数)。

2、模运算：{[a(mod n)]×[b(mod n)]}modn≡(a×b)(mod n)。

3、费马定理：若p是素数，a与p互素，则a^(p-1)≡1 (mod p)。

4、欧拉定理：欧拉函数φ(n)表示不大于n且与n互素的正整数的个数。当n是素数，φ(n)=n-1。n=pq,p,q均为素数时，则φ(n)= φ(p)φ(q)=(p-1)(q-1)。对于互素的a和n，有a^φ(n)≡1(mod n)。