试除法

试除法是整数分解演算法中最简单和最容易理解的演算法。首次出現於義大利數學家費波那契出版於1202年的著作。

给定一个待分解的正整數n，试除法是用小于等于${\displaystyle {\sqrt {n}}}$的每个素数^[1][2]去试除。如果找到一个数能够整除除尽，这个数就是可分解整数的因數。若n為合數，則试除法一定能够找到n的質因數，因為n最小的質因數不大於其平方根，所以如果这个演算法“失败”，也就证明了n是个素数。

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

参见

• 卢卡斯-莱默检验法
• 埃拉托斯特尼筛法
• 米勒-拉宾检验
• 费马素性检验

參考文獻

1. Chris K. Caldwell. . The PrimePages. [2023-02-12]. （原始内容存档于2023-02-12） （英语）. just divide by all the primes less than (or equal to) its square root. 
2. Trial division. PlanetMath. [2023-02-12] （英语）. where a given integer ${\displaystyle n}$  is tested for divisibility by each prime ${\displaystyle p_{i}}$  in order until all its factors are discovered