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)。