试除法 试除法是整数分解演算法中最简单和最容易理解的演算法首次出現於義大利數學家費波那契出版於年的著作 给定一个待分解的正整數n试除法是用小于等于 n displaystyle sqrt n 的每个素数去试除如果找到一个数能够整除除尽这个数就是可分解整数的因數若n為合數則试除法一定能够找到n的質因數因為n最小的質因數不大於其平方根所以如果这个演算法失败也就证明了n是个素数 某种意义上说试除法是个效率非常低的演算法如果从开始一直算到 n displaystyle sqrt n 需要 π  n  displaystyle pi sqrt n 次试除这里 π  x  displaystyle pi x 是小于x的素数的个数这是不包括素性测试的如果稍做变通还是不包括素性测试用小于 n displaystyle sqrt n 的奇数去简单的试除则需要 n  displaystyle sqrt n over  次这意味着如果n有大小接近的素因數例如公钥密码学中用到的试除法是不太可能实行的但是当n有至少一个小因數试除法可以很快找到这个小因數值得注意的是对于随机的n是其因數的概率是是等等的正整数有小于的因數的正整数有小于的因數