网站地图
因数分解

在数学中,因数分解,又称素因数分解,是把一个正整数写成几个约数的乘积。例如,给出45这个数,它可以分解成3×3×5,根据算术基本定理,这样的分解结果应该是独一无二的。

因数分解是将一个正整数写成几个约数的乘积,在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义 [1] 。因数分解的关键是寻找因子(约数),而完整的因子列表可以根据约数分解推导出,将幂从零不断增加直到等于这个数。例如,因为45= 3×3×5,45可以被 1,5,3,9,15,和 45整除。相对应的,约数分解只包括约数因子。

给出两个大约数,很容易就能将它们两个相乘。但是,给出它们的乘积,找出它们的因子就显得不是那么容易了。这就是许多现代密码系统的关键所在。如果能够找到解决整数分解问题的快速方法,几个重要的密码系统将会被攻破,包括RSA公钥算法和Blum Blum Shub随机数发生器。

尽管快速分解是攻破这些系统的方法之一,仍然会有其它的不涉及到分解的其它方法。所以情形完全可能变成这样:整数分解问题仍然是非常困难,这些密码系统却是能够很快攻破。有的密码系统则能提供更强的保证:如果这些密码系统被快速破解(即能够以多项式时间复杂度破解),则可以利用破解这些系统的算法来快速地(以多项式时间复杂度)分解整数。换句话说,破解这样的密码系统不会比因数分解更容易。这样的密码系统包括Rabin密码系统(RSA的一个变体)以及Blum Blum Shub随机数发生器。

2005年,作为公共研究一部分的有663个二进制数位之长的RSA-200已经被一种一般用途的方法所分解。

如果一个大的,有n个二进制数位长度的数是两个差不多大小相等的约数的乘积,现在还没有很好的算法来以多项式时间复杂度分解它。

这就意味着没有已知算法可以在

对于平常的计算机,GNFS是我们已知最好的对付n个二进制数位大约数的方法。不过,对于量子计算机,彼得秀尔在1994年发现了一种可以用多项式时间来解决这个问题的算法。如果大的量子计算机建立起来,这将对密码学有很重要的意义。这个算法在时间上只需要

现在还不确切知道整数分解属于哪个复杂度。

我们知道这个问题的判定问题形式(“请问N是否有一个比M小的约数?”)是在NP与反NP之中。因为不管是答案为是或不是,我们都可以用一个素因数以及该素因数的素数证明来验证这个答案。由秀尔算法可知,这个问题在BQP中。大部分的人则怀疑这个问题不在P、NP完全、以及反NP完全这三个复杂性类别中。如果这个问题可以被证明为NP完全或反NP完全,则我们便可推得NP=反NP。这将会是个很震憾的结果,也因此大多数人猜想整数分解这个问题不在上述的复杂性类别中。也有许多人尝试去找出多项式时间的算法来解决这个问题,但是都尚未成功,因此这个问题也被多数人怀疑不在P中。

有趣的是,判定一个整数是否是素数则比分解该整数简单许多。AKS算法证明前者可以在多项式时间中解决。 测试一个数是否为素数是RSA算法中非常重要的一环,因为它在一开始的时候需要找很大的素数。

一个特别的因子分解算法的运行时间依赖它本身的未知因子:大小,类型等等。在不同的算法之间运行时间也是不同的 [2]

试除法;

车轮分解;

波拉德RHO算法;

代数群因式分解算法;

费马素数判定法;

欧拉因式分解法;

特殊数域筛选法。

一般用途算法的运行时间仅仅依赖要分解的整数的长度。这种算法可以用来分解RSA数。大部分一般用途算法基于平方同余方法。

Dixon算法;

连分数分解法(CFRAC);

二次筛选法;

理性筛选法;

普通数域筛选法。

秀尔算法。


相关文章推荐:
数学 | 正整数 | 约数 | 乘积 | 算术基本定理 | 正整数 | 约数 | 乘积 | 代数学 | 密码学 | 计算复杂性理论 | 量子计算机 | 因子 | | 约数 | 因子 | 随机数发生器 | 多项式 | 时间复杂度 | 算法 | 时间复杂度 | 普通数域筛选法 | 量子计算机 | 彼得秀尔 | 多项式时间 | 复杂度 | 判定问题 | NP | 秀尔算法 | RSA | 试除法 | 代数群 | RSA | 普通数域筛选法 | 秀尔算法 |
相关词汇词典