试除法 - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for 试除法.

试除法

维基百科,自由的百科全书

试除法整数分解算法中最简单和最容易理解的算法。首次出现于意大利数学家费波那契出版于1202年的著作。

给定一个合数n(这里,n是待分解的正整数),试除法看成是用小于等于的每个素数去试除待分解的整数。如果找到一个数能够整除除尽,这个数就是可分解整数的约数。试除法一定能够找到n的约数。因为它检查n的所有可能的约数,所以如果这个算法“失败”,也就证明了n是个素数。试除法可以从几条途径来完善。例如,n的末位数不是0或者5,那么算法中就可以跳过末位数是5的约数。如果末位数是2,检查偶数约数就可以了。

某种意义上说,试除法是个效率非常低的算法,如果从2开始,一直算到需要 次试除,这里pi(x)是小于x的素数的个数。这是不包括素性测试的。如果稍做变通——还是不包括素性测试——用小于的奇数去简单的试除,则需要次。这意味着,如果n有大小接近的素约数(例如公钥密码学中用到的),试除法是不太可能实行的。但是,当n有至少一个小约数,试除法可以很快找到这个小约数。值得注意的是,对于随机的n,2是其约数的概率是50%,3是33%,等等,88%的正整数有小于100的约数,91%的正整数有小于1000的约数。

参见

{{bottomLinkPreText}} {{bottomLinkText}}
试除法
Listen to this article