整数分解

正整数写成几个约数的乘积
image
在数学中，整数分解（英语：integer factorization）又称素因数分解（prime factorization），是将一个正整数写成几个约数的乘积。例如，给出45这个数，它可以分解成9×5。根据算术基本定理，这样的分解结果应该是独一无二的。这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。

因子分解

完整的因子列表可以根据约数分解推导出，将幂从零不断增加直到等于这个数。例如，因为
，45可以被
，
，
，
，
，和
，或者 1，5，3，9，15，和 45整除。相对应的，约数分解只包括约数因子。

实际应用

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