整数分解
维库，知识与思想的自由文库
|
数学中，整数分解问题是指：给出一个正整数，将其写成几个素数的乘积。例如，给出45这个数，它可以分解成32 ×5。根据算术基本定理，这样的分解结果应该是独一无二的。这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。
[编辑] 因子分解完整的因子列表可以根据素数分解推导出，将幂从零不断增加直到等于这个数。例如，因为45= 32×51，45可以被30 ×50，30×51，31×50，31×51，32×50，和32×51，或者 1，5，3，15，9，和 45整除。相对应的，素数分解只包括素数因子。参见素数分解算法。 [编辑] 實際應用给出两个大素数，很容易就能将它们两个相乘。但是，给出它们的乘积，找出它们的因子就显得不是那么容易了。这就是许多现代密码系统的关键所在。如果能够找到解决整数分解问题的快速方法，几个重要的密码系统将会被攻破，包括RSA公钥算法和Blum Blum Shub隨機數發生器。 尽管快速分解是攻破这些系统的方法之一，仍然会有其它的不涉及到分解的其它方法。所以情形完全可能变成这样：整数分解问题仍然是非常困难，这些密码系统却是能够很快攻破。有的密码系统则能提供更强的保证：如果这些密码系统被快速破解（即能夠以多項式時間複雜度破解），则可以利用破解这些系统的算法来快速地（以多項式時間複雜度）分解整数。换句话说，破解这样的密码系统不会比整数分解更容易。这样的密码系统包括 Rabin密码系统（RSA的一个变体），以及 Blum Blum Shub 隨機數發生器。 [编辑] 當今的新進展2005年，作为公共研究一部分的有663个二进制数位之长的RSA-200已经被一种一般用途的方法所分解。 如果一个大的，有n个二进制数位长度的数是两个差不多大小相等的素数的乘积，现在还没有很好的算法来以多项式时间复杂度分解它。 这就意味着没有已知算法可以在O(nk)（k为常数）的时间内分解它。但是现在的算法也是比Θ(en)快的。换句话说，现在我们已知最好的算法比指數數量級时间要快，比多项式數量級时间要慢。已知最好的渐近线运行时间是普通数域筛选法(GNFS)。时间是： 对于平常的计算机，GNFS是我们已知最好的对付n个二进制数位大素数的方法。不过，对于量子计算机， 彼得·肖 在1994年发现了一种可以用多项式时间来解决这个问题的算法。如果大的量子计算机建立起来，这将对密码学有很重要的意义。这个算法在时间上只需要O(n3)，空间只要O(n)就可以了。 构造出这样一个算法只需要2n量子位。2001年，第一个7量子位的量子计算机第一个运行这个算法，它分解的数是15。 [编辑] 難度與複雜度现在还不确切知道整数分解属于那个复杂性等级。 我們知道這個問題的判定問題形式 ("請問 N 是否有一個比 M 小的因數?") 是在NP與co-NP 之中. 因為不管是答案為是或不是, 我們都可以用一個質因數以及該質因數的質數證明來驗證這個答案. 由 肖 的演算法, 我們得知這個問題在 BQP 中. 大部份的人則懷疑這個問題不在 P、NP-Complete、以及co-NP-Complete 這三個複雜性類別中. 如果這個問題可以被證明為 NP-Complete 或 co-NP-Complete, 則我們便可推得 NP = co-NP. 這將會是個很震憾的結果, 也因此大多數人猜想整數分解這個問題不在上述的複雜性類別中. 也有許多人嘗試去找出多項式時間的演算法來解決這個問題, 但是都尚未成功, 因此這個問題也被多數人懷疑不在 P 中. 有趣的是, 當判定問題為「N 是否為一 合數？」則比要找出 N 的因數這個問題要簡單的許多。有文章[1]指出前者這個問題可以在多項式時間中解決 (其中 n 為 N 的位數）。若允許微小的失誤，更有許多的隨機化演算法可以非常快速的測試出一個數是否為質數。測試一個數是否質數不難，這是RSA 演算法中非常重要的一環，因為它在一開始的時後需要找很大的質數。（参见素性测试）。 [编辑] 整數分解算法[编辑] 特殊用途算法一个特别的因子分解算法的运行时间依赖它本身的未知因子：大小，类型等等。在不同的算法之间运行时间也是不同的。
[编辑] 一般用途算法一般用途算法的运行时间仅仅依赖要分解的整数的长度。这种算法可以用来分解RSA数。大部分一般用途算法基于平方同余方法。
[编辑] 其他值得注意的算法 |
