试除法是
整数分解算法中最简单和最容易理解的算法,用小于等于n的每个素数去试除待分解的整数。
给定一个
合数n(这里,n是待分解的整数),试除法看成是用小于等于n的每个素数去试除待分解的整数。如果找到一个数能够整除除尽,这个数就是待分解整数的因子。试除法一定能够找到n的因子。因为它检查n的所有可能的因子,所以如果这个算法“失败”,也就证明了n是个素数。
某种意义上说,试除法是个效率非常低的算法,如果从2开始,一直算到需要pi(x)次试除,这里pi(x)是小于x的素数的个数。这是不包括
素性测试的。如果稍做变通——还是不包括素性测试——用小于的奇数去简单的试除,则需要次。
但是,当n有至少一个小因子,试除法可以很快找到这个小因子。值得注意的是,对于随机的n,2是其因子的
概率是50%,3是33%,等等。88%的正整数有小于100的因子,91%的有小于1000。