整数分解





在數學中，整數分解（英语：integer factorization）又稱質因數分解（prime factorization），是將一個正整數寫成幾個因數的乘積。例如，給出45這個數，它可以分解成32×5{displaystyle 3^{2}times 5}{displaystyle 3^{2}times 5}。根據算術基本定理，這樣的分解結果應該是獨一無二的。這個問題在代數學、密碼學、計算複雜性理論和量子計算機等領域中有重要意義。




目录






  • 1 因子分解


  • 2 實際應用


  • 3 當今的新進展


    • 3.1 難度與複雜度




  • 4 整數分解算法


    • 4.1 特殊用途算法


    • 4.2 一般用途算法


    • 4.3 其他算法




  • 5 參見





因子分解


完整的因子列表可以根據因數分解推導出，將冪從零不斷增加直到等於這個數。例如，因為45={displaystyle 45=,}{displaystyle 45=,}32×5{displaystyle 3^{2}times 5}{displaystyle 3^{2}times 5}，由此可知，45可以被30 ×50，30×51，31×50，31×51，32×50，和32×51，或者 1，5，3，9，15，和 45整除。相對應的，因數分解只包括因數因子。參見因數分解算法。



實際應用


給出兩個大因數，很容易就能將它們兩個相乘。但是，給出它們的乘積，找出它們的因子就顯得不是那麼容易了。這就是許多現代密碼系統的關鍵所在。如果能夠找到解決整數分解問題的快速方法，幾個重要的密碼系統將會被攻破，包括RSA公鑰算法和Blum Blum Shub（英语：Blum Blum Shub）隨機數發生器。


儘管快速分解是攻破這些系統的方法之一，仍然會有其它的不涉及到分解的其它方法。所以情形完全可能變成這樣：整數分解問題仍然是非常困難，這些密碼系統卻是能夠很快攻破。有的密碼系統則能提供更強的保證：如果這些密碼系統被快速破解（即能夠以多項式時間複雜度破解），則可以利用破解這些系統的算法來快速地（以多項式時間複雜度）分解整數。換句話說，破解這樣的密碼系統不會比整數分解更容易。這樣的密碼系統包括Rabin密碼系統（RSA的一個變體）以及Blum Blum Shub隨機數發生器。



當今的新進展


2005年，作為公共研究一部分的有663個二進制數位之長的RSA-200已經被一種一般用途的方法所分解。


如果一個大的，有n個二進制數位長度的數是兩個差不多大小相等的因數的乘積，現在還沒有很好的算法來以多項式時間複雜度分解它。


這就意味著沒有已知算法可以在O（nk）（k為常數）的時間內分解它。但是現在的算法也是比Θ(en)快的。換句話說，現在我們已知最好的算法比指數數量級時間要快，比多項式數量級時間要慢。已知最好的漸近線運行時間是普通數域篩選法（GNFS）。時間是：


Θ(exp⁡((649n)13(log⁡n)23)){displaystyle Theta left(exp left(left({frac {64}{9}}nright)^{frac {1}{3}}(log n)^{frac {2}{3}}right)right)}{displaystyle Theta left(exp left(left({frac {64}{9}}nright)^{frac {1}{3}}(log n)^{frac {2}{3}}right)right)}

對於平常的計算機，GNFS是我們已知最好的對付n個二進制數位大因數的方法。不過，對於量子計算機， 彼得·秀尔在1994年發現了一種可以用多項式時間來解決這個問題的算法。如果大的量子計算機建立起來，這將對密碼學有很重要的意義。這個算法在時間上只需要O(n3)，空間只要O(n)就可以了。 構造出這樣一個算法只需要2n量子位。2001年，第一個7量子位的量子計算機第一個運行這個算法，它分解的數是15。



難度與複雜度


現在還不確切知道整數分解屬於哪個複雜度類。


我們知道這個問題的判定問題形式（「請問N是否有一個比M小的因數?」）是在NP與反NP之中。因為不管是答案為是或不是，我們都可以用一個質因數以及該質因數的質數證明來驗證這個答案。由秀爾演算法可知，這個問題在BQP中。大部份的人則懷疑這個問題不在P、NP完全、以及反NP完全這三個複雜性類別中。如果這個問題可以被證明為NP完全或反NP完全，則我們便可推得NP=反NP。這將會是個很震憾的結果，也因此大多數人猜想整數分解這個問題不在上述的複雜性類別中。也有許多人嘗試去找出多項式時間的演算法來解決這個問題，但是都尚未成功，因此這個問題也被多數人懷疑不在P中。


有趣的是，判定一個整數是否是質數則比分解該整數簡單許多。AKS算法証明前者可以在多項式時間中解決。 測試一個數是否為質數是RSA演算法中非常重要的一環，因為它在一開始的时候需要找很大的質數。



整數分解算法



特殊用途算法


一個特別的因子分解算法的運行時間依賴它本身的未知因子：大小，類型等等。在不同的算法之間運行時間也是不同的。



  • 試除法

  • 车轮分解（英语：Wheel factorization）

  • 波拉德RHO算法（英语：Pollard's rho algorithm）


  • 代数群因式分解算法（英语：Algebraic-group factorisation algorithms），其中包括Pollard's p − 1算法（英语：Pollard's p − 1 algorithm）、Williams' p + 1算法（英语：Williams' p + 1 algorithm）和Lenstra橢圓曲線分解法（英语：Lenstra elliptic curve factorization）

  • 費馬質數判定法

  • 欧拉因式分解法（英语：Euler's factorization method）

  • 特殊數域篩選法（英语：Special number field sieve）



一般用途算法


一般用途算法的運行時間僅僅依賴要分解的整數的長度。這種算法可以用來分解RSA數。大部分一般用途算法基於平方同余方法。



  • Dixon算法（英语：Dixon's algorithm）


  • 連分數分解法（英语：Continued fraction factorization）（CFRAC）

  • 二次篩選法（英语：Quadratic sieve）

  • 理性筛选法（英语：Rational sieve）

  • 普通數域篩選法


  • Shanks' square forms factorization（英语：Shanks' square forms factorization）（SQUFOF）



其他算法


  • 秀尔算法


參見


  • 質因數表















































  • 查

  • 论

  • 编



数论算法

素性测试


  • AKS質數測試

  • APR test

  • Baillie–PSW

  • 椭圆曲线素性

  • Pocklington

  • 费马素性检验

  • 卢卡斯素性测试

  • 卢卡斯-莱默检验法

  • Lucas–Lehmer–Riesel

  • 普罗斯定理

  • Pépin's

  • Quadratic Frobenius test

  • Solovay–Strassen

  • 米勒-拉宾检验
素数生成


  • 阿特金筛法

  • 埃拉托斯特尼筛法

  • Sieve of Sundaram

  • Wheel factorization
整数分解


  • Continued fraction (CFRAC)

  • Dixon's

  • Lenstra elliptic curve (ECM)

  • 欧拉因式分解法

  • Pollard's rho


  • p − 1


  • p + 1

  • Quadratic sieve (QS)

  • 普通数域筛选法

  • Special number field sieve (SNFS)

  • Rational sieve

  • 费马因式分解法

  • Shanks's square forms

  • 试除法

  • 秀爾演算法
乘法算法（英语：Multiplication algorithm）


  • 古埃及乘算

  • 长乘法

  • Karatsuba算法

  • Toom–Cook

  • Schönhage–Strassen

  • Fürer's
离散对数


  • Baby-step giant-step

  • Pollard rho

  • Pollard kangaroo

  • Pohlig–Hellman

  • Index calculus

  • Function field sieve
最大公因數


  • 二进制最大公因数算法

  • 輾轉相除法

  • 扩展欧几里得算法

  • Lehmer's
二次剩余


  • Cipolla

  • Pocklington's

  • Tonelli–Shanks
其他算法


  • Chakravala

  • Cornacchia

  • LLL

  • 整数平方根

  • 模幂运算

  • Schoof's


  • 斜体表示该算法只适用于特殊形式的数字


Template:Divisor classes







Comments

Post a Comment

Popular posts from this blog

Information security

Image
This article is part of a series on Information security Related security categories Internet security Cyberwarfare Computer security Mobile security Network security Threats Computer crime Vulnerability Eavesdropping Malware Spyware Ransomware Trojans Viruses Worms Rootkits Bootkits Keyloggers Screen scrapers Exploits Backdoors Logic bombs Payloads Denial of service Defenses Computer access control Application security Antivirus software Secure coding Secure by default Secure by design Secure operating systems Authentication Multi-factor authentication Authorization Data-centric security Encryption Firewall Intrusion detection system Mobile secure gateway Runtime application self-protection (RASP) v t e Information security , sometimes shortened to InfoSec , is the practice of preventing unauthorized access, use, disclosure, disruption, modification, inspection, recording or destruction of information. Th...
Read more

Lambak Kiri

Image
For Lambak Kiri public housing area, see Lambak Kiri Landless Indigenous Citizens' Housing Scheme. Village in Brunei-Muara, Brunei Lambak Kiri Village Location in Brunei Coordinates: 4°59′26″N 114°57′04″E  /  4.990472°N 114.951114°E  / 4.990472; 114.951114 Coordinates: 4°59′26″N 114°57′04″E  /  4.990472°N 114.951114°E  / 4.990472; 114.951114 Country Brunei District Brunei-Muara Mukim Berakas A Government  • Village head Hamdani Omar Postcode BB1214 Lambak Kiri is a populated place in Brunei-Muara District, Brunei. It is officially a village subdivision under Berakas A, a mukim in the district. Lambak Kiri may also refer to the greater area which includes the Lambak Kiri public housing area of the Landless Indigenous Citizens' Housing Scheme (Malay: Skim Tanah Kurnia Rakyat Jati ), although the latter is a separate subdivision. Contents 1 Name 2 Administration 3 See also 4 References Name ...
Read more

章鱼与海女图

Image
本条目 可参照英語維基百科相應條目来扩充 。 （2014/5/25） 若您熟悉来源语言和主题，请协助参考外语维基扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记 {{Translated page}} 标签。 本条目 需要擴充。 （2013年8月15日） 请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 《 章鱼与海女 》（日语： 蛸と海女 ／ たことあま   Tako to ama ）是一幅由日本畫家葛饰北斋创作的浮世绘，出自1814年（文化4年）出版的艳本《喜能会之故真通》（日语： 喜能会之故真通 ／ きのえのこまつ   Kinoe no Komatsu ）。畫中有兩隻章鱼以觸手攻擊一名採珠的海女，並進行擬似戀獸癖的交媾行為。作品尺寸为6½" × 8¾" （16.51 cm × 22.23 cm）。 [1] 在此之前的类似作品还有北尾重政的艳本《謡曲色番組》及勝川春潮的艳本《艳本千夜多女志》等，有被北斋作为参考的可能性。 《章鱼与海女图》有不同英文翻译，一般称The Dream of the Fisherman's Wife，又作Girl Diver and Octopi、Diver and Two Octopi，Richard Douglas Lane称其为 Girl Diver and Octopi [2] ，Mathi Forrer 称其为 Pearl Diver and Two Octopi [3] ，Danielle Talerico 称其为 Diver and Two Octopi 。 [4] 目录 1 作品介绍 1.1 画中对话 1.2 解释 2 评价 3 影响 3.1 模仿作品 4 另见 5 参考来源 6 外部連結 作品介绍 画中对话 原文 译文 大蛸： いつぞハいつぞハとねらいすましてゐたかいがあつて、けふといふけふ、とうとうとらまへたア。てもむつくりとしたいいぼぼだ。いもよりハなをこうぶつだ。サアサア、すつてすつてすいつくして...
Read more