第九章 大整数因子分解算法 因子分解问题（ IFP）： 找到一个合数 N的 非平凡因子 f（不要求一定是素因子） 如果存在一个算法能检测出 N是否为素数，且 存在一个算法能找出合数 N的非平凡因子 f，则 存在一个简单的递归算法得到 N的素数幂分解 。 递归算法 如下： 1. 找出 N的一个非平凡因子 f 2. 算法递归的应用到 f和 N/f上 3. 将 f和 N/f的素数幂分解合在一起得到 N的素 数幂分解 数论里能应用计算机的所有问题中，可能没有比 整数因子分解更具影响力的问题了。 Hugh C. Williams 大整数分解是许多密码学算法和协议的安全依据 ，如 RSA密码体制。 方法 ： (1)穷举法； (2)分解算法。 找出 N的素因子或判定 N是否为素数都不是 一件容易的事情，因此，只要可能的话我 们都应当尽可能的避免分解大整数。 事实上，存在很多素性检测和整数因子分 解算法；唯一的问题是无论是素性检测还 是整数因子分解都没有找到有效（确定性 多项式时间）算法，也无人能够证明不存 在确定性多项式时间算法。 最有效的因子分解算法主要可归为以下 两大类 ： 运行时间主要 依赖于
