標籤: 暫無標籤

1試除法

它是整數分解演算法中最簡單和最容易理解的演算法。
給定一個合數n(這裡,n是待分解的整數),試除法看成是用小於等於n的每個素數去試除待分解的整數。如果找到一個數能夠整除除盡,這個數就是待分解整數的因子。試除法一定能夠找到n的因子。因為它檢查n的所有可能的因子,所以如果這個演算法「失敗」,也就證明了n是個素數。
試除法可以從幾條途徑來完善。例如,n的末位數不是0或者5,那麼演算法中就可以跳過末位數是5的因子。如果末位數是2,檢查偶數因子就可以了。
某種意義上說,試除法是個效率非常低的演算法,如果從2開始,一直算到需要pi(x)次試除,這裡pi(x)是小於x的素數的個數。這是不包括素性測試的。如果稍做變通——還是不包括素性測試——用小於的奇數去簡單的試除,則需要次。
這意味著,如果n有大小接近的素因子(例如公鑰密碼學中用到的),試除法是不太可能實行的。
但是,當n有至少一個小因子,試除法可以很快找到這個小因子。值得注意的是,對於隨機的n,2是其因子的概率是50%,3是33%,等等,88%的正整數有小於100的因子,91%的有小於1000。

2例子

可以這樣描述
7M((4M^2)×P^2)÷(7M^2)其結果為4MP^2
上一篇[三次函數]    下一篇 [分母]

相關評論

同義詞:暫無同義詞