1、III数论算法 -2方法Fermat的方法连分数法组合方程数域筛法RSARSA: Rivest， Shamir， Adelman（ 1978年）基于 大数分解的困难性RSA算法的步骤如下：随机选择两个大的秘密素数 p与 q计算公开的模数 r=p*q计算秘密的欧拉函数 (r)=(p-1)(q-1)能选择一个与 (r)互素的 K， K可以定义为秘密密钥 SK或公开密钥 PK，计算模 (r)即的 K的乘法逆元素，这个量规定为秘密密钥 SK或公开密钥 PK，它取决于第 4步的选择。将明文 X自乘 PK次幂后按 r取模进行加密运算，从而产生密文 Y：将密文 Y自乘 SK次幂后按 r取模进行解密运算，从而
2、产生明文 XRSA例 例：取 p=23,q=43，则 注意，取 ，则有 ，求得其逆 求得 以 e为明钥， d为密钥 假定欲发送的明文为 将明文分段RSA例续 加密 解密原理：若 N为合数，则 N至少有一个因子自然算法复杂度：Pollard的 方法 若 d1，则 d为非平凡的解，停止；令定义序列： 满足对 i做Pollard的 方法实例例： N=1387=19*73i 1 2 3 4 5 6 7 8 9 10XXi 1 2 5 26 677 620 202 582 297 829X2i2 26 620 582 829 yi 1 24 615 556 152 gcd 1 1 1 1 19 i 1 2 3 4 5 6 7 8 9 10复杂度命题：如果映射 被映射代换，其中 f为随机函数， 因子 p可在 步分解，即Fermat的方法 求解 ，其中由于每项均非 ，从而得到非平凡的解比较小Fermat的方法：找到 q使小的数是平方的可能性较大
