試除法

試除法是整數分解演算法中最簡單和最容易理解的演算法。首次出現於義大利數學家費波那契出版於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. trial division. 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