第一步，随机选择两个不相等的质数p和q。 爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
第二步，计算p和q的乘积n。
第三步，计算n的欧拉函数φ(n)。 根据公式：
爱丽丝算出φ(3233)等于60×52，即3120。
第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
第五步，计算e对于φ(n)的模反元素d。 所谓”模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
这个式子等价于
于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。
扩展欧几里得算法
第六步，将n和e封装成公钥，n和d封装成私钥。 实际应用中，公钥和私钥的数据都采用ASN.1格式表达（实例）。
加密和解密 有了公钥和密钥，就能进行加密和解密了。 （1）加密要用公钥 (n,e)
（2）解密要用私钥(n,d)
至此，“加密—解密”的整个过程全部完成。
米勒-拉宾质数判定法
英语：Miller–Rabin primality test
这一算法可以被表示成如下伪代码：
Input #1: n > 3, an odd integer to be tested for primality; Input #2: k, a parameter that determines the accuracy of the test Output: composite if n is composite, otherwise probably prime
write n − 1 as 2_r_·d with d odd by factoring powers of 2 from n − 1 WitnessLoop: repeat k times: pick a random integer a in the range [2, n − 2] x ← a__d mod n if x = 1 or x = n − 1 then continue WitnessLoop repeat r − 1 times: x ← _x_2 mod n if x = n − 1 then continue WitnessLoop return composite return probably prime
扩展欧几里得
