試除法
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
試除法是整數分解演算法中最簡單和最容易理解的演算法。首次出現於義大利數學家費波那契出版於1202年的著作。
給定一個待分解的正整數n,試除法是用小於等於的每個素數[1][2]去試除。如果找到一個數能夠整除除盡,這個數就是可分解整數的因數。若n為合數,則試除法一定能夠找到n的質因數,因為n最小的質因數不大於其平方根,所以如果這個演算法「失敗」,也就證明了n是個素數。
某種意義上說,試除法是個效率非常低的演算法,如果從2開始,一直算到需要 次試除,這裡是小於x的素數的個數。這是不包括素性測試的。如果稍做變通——還是不包括素性測試——用小於的奇數去簡單的試除,則需要次。這意味着,如果n有大小接近的素因數(例如公鑰密碼學中用到的),試除法是不太可能實行的。但是,當n有至少一個小因數,試除法可以很快找到這個小因數。值得注意的是,對於隨機的n,2是其因數的概率是50%,3是33%,等等,88%的正整數有小於100的因數,91%的正整數有小於1000的因數。
參見
參考文獻
- ^ Chris K. Caldwell. trial division. The PrimePages. [2023-02-12]. (原始內容存檔於2023-02-12) (英語).
just divide by all the primes less than (or equal to) its square root.
- ^ Trial division. PlanetMath. [2023-02-12] (英語).
where a given integer is tested for divisibility by each prime in order until all its factors are discovered