试除法
![本页使用了标题或全文手工转换](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