本章的意义在于对因子分解和离散对数这些问题的有效算法 。这些算法本身是有趣 的 ，并可作为 己学过的数论知识的良好应用 。此外 ，理解这些算法的效率对于在实际应用中选择密码学参数是至关重要的

文章目录

• • 因式分解算法
  • • Pollard的p - 1方法
    • Pollard的rho方法
    • 二次筛算法

因式分解算法

• 亚指数：如果f（n）= 2^o(n) ， 则f是关于n的亚指数
• Pollard的p - 1方法 ，当p-1有 “ 小 ” 素数因子时它是种有效的方法 。
• Pollard的rho方法， 这种方法适用于任意的N因此， 这种方法还被称为 “通用 ” 因子分解算法。对于本节开始部分讨论的那种类型的 整数N来 说 ， 它的时间复 杂度是O（N^1/4*polylog(N））
• 二次筛算法 ，这是一种通用因子分解算法，运行时间的复杂度为（关于N的长度）亚指数

Pollard的p - 1方法

整数N = pq且p - 1只有 “ 小 ” 因子时，能找到一个元素y属于Z*N且
所以gcd(y, N) = p，于是就得到了一个因子，求y的方法如下：假设能找到一个B使得 (p − 1)| B and (q − 1)！| B，令B=r（p-1）于是算法如下：
下面证明算法生成的y是不是满足上述条件

1. 证明 y=0modp
   

2. 证明 y!=0modq
   
   但如果xq是生成元的话上述结论结不成立（生成元的B次方有可能正好为1），但因为生成元的个数为φ（q - 1 ），modq的域大小为q-1，所以概率由下面定理得到Ω（1/ log q) = Ω( 1/n），即可忽略

   • 一个定理：通常认为
     

选择B的方法：

• pi表示第i个素数
• k代表一个范 围 ，它影响时间复杂度和算法成功的概率
• n是p的长度
• pi^ [n/log pi]表示能整除p-1的最大的pi的幂
• 只要q-1一个素数因子比Pk大，那么（q - 1) )！|B
• 所以当增加k的值，会增加运算复杂度，但会提高找到B的成功率

Pollard的rho方法

二次筛算法