因数分解

概述

在数学中，因数分解，又称素因数分解，是把一个正整数写成几个约数的乘积。 例如，给出45这个数，它可以分解成3×3×5，根据算术基本定理，这样的分解结果应该是独一无二的。 因数分解是将一个正整数写成几个约数的乘积，在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。 因数分解的关键是寻找因子（约数），而完整的因子列表可以根据约数分解推导出，将幂从零不断增加直到等于这个数。例如，因为45= 3×3×5，45可以被 1，5，3，9，15，和 45整除。相对应的，约数分解只包括约数因子。

名词

中文名
因数分解
外文名
Factorization
领    域
树立科学
别    名
素因数分解;整数分解

实际应用

给出两个大约数，很容易就能将它们两个相乘。 但是，给出它们的乘积，找出它们的因子就显得不是那么容易了。 这就是许多现代密码系统的关键所在。如果能够找到解决整数分解问题的快速方法，几个重要的密码系统将会被攻破，包括RSA公钥算法和Blum Blum Shub随机数发生器。 尽管快速分解是攻破这些系统的方法之一，仍然会有其它的不涉及到分解的其它方法。所以情形完全可能变成这样：整数分解问题仍然是非常困难，这些密码系统却是能够很快攻破。有的密码系统则能提供更强的保证：如果这些密码系统被快速破解（即能够以多项式时间复杂度破解），则可以利用破解这些系统的算法来快速地（以多项式时间复杂度）分解整数。换句话说，破解这样的密码系统不会比因数分解更容易。这样的密码系统包括Rabin密码系统（RSA的一个变体）以及Blum Blum Shub随机数发生器。