这篇文章上次修改于 1476 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

RSA是一种公钥加密算法，选择公钥和密匙的要求有：

• 有两个较大的素数p和q(大于100¹⁰⁰)
• 让n = pq、z = (p-1)(q-1)
• 选择d与z互质(互质是公约数只有1的两个整数，叫做互质整数)

• 选择e，e要满足e*d = 1(mod z)

   Q:什么是e*d = 1(mod z)？
   A:同余关系，a = b(mod n)可以解释为a与b二数的差值(即a-b)是n的整数倍数
   例如：25 = 10(mod 5)，25-10=15,15除以5可以得到整数
   同理e*d = 1(mod z)为e*d-1的值除以z可以得到整数
  

加密时就计算：
C = P^e (mod n)
公钥为(e,n)
解密是就计算：
P = C^d (mod n)
私钥为(d,n)

Q:举个例子？
A:例如p=3,q=11,n=33,z=20,e=3,d=7
C = P³ (mod 33) = 2³ (mod 33) = 8
P = C⁷ (mod 33) = 8⁷ (mod 33) = 2