試除法

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

給定一個待分解的正整數n，試除法是用小於等於${\sqrt {n}}$的每個素數去試除。如果找到一個數能夠整除除盡，這個數就是可分解整數的因數。若n為合數，則試除法一定能夠找到n的質因數，因為n最小的質因數不大於其平方根，所以如果這個演算法「失敗」，也就證明了n是個素數。

某種意義上說，試除法是個效率非常低的演算法，如果從2開始，一直算到${\sqrt {n}}$需要 $\pi ({\sqrt {n}})$次試除，這裡$\pi (x)$是小於x的素數的個數。這是不包括素性測試的。如果稍做變通——還是不包括素性測試——用小於${\sqrt {n}}$的奇數去簡單的試除，則需要${{\sqrt {n}} \over 2}$次。這意味着，如果n有大小接近的素因數（例如公鑰密碼學中用到的），試除法是不太可能實行的。但是，當n有至少一個小因數，試除法可以很快找到這個小因數。值得注意的是，對於隨機的n，2是其因數的概率是50％，3是33％，等等，88％的正整數有小於100的因數，91％的正整數有小於1000的因數。

參見

• 盧卡斯-萊默檢驗法
• 埃拉托斯特尼篩法
• 米勒-拉賓檢驗
• 費馬素性檢驗