Pollard Rho因子分解方法的實施

每次使用Pollard Rho因子分解方法對數字進行因子分解時，是否需要在Pollard Rho因子分解之前檢查它的素數？如果是的話，那麼每次我想要分解任何數字，並且必須要處理強僞指數時，我必須實施米勒拉賓的素性檢驗或任何素性檢驗，是不是很複雜？有沒有簡單的方法來處理這個問題？（我正在使用這些測試的數字高達10位數字）Pollard Rho因子分解方法的實施

來源

2012-05-31 SlashGeek

如果你有內存（600 MB，如果我正確計算的話），十個數字篩是最快的測試，否則我會用簡單的試用分區去做，不需要miller rabin :-) – hirschhornsalz

如果我有在100 MB內存中查找所有數字因素？ – SlashGeek

，如果數字是abt 20？ – SlashGeek

是的，你必須檢查，然後再應用Pollard Rho，你的因數是複合。如果它是素數，則gcd步驟將始終返回1，因爲質數總是與其他數字共素數，並且Pollard Rho將永遠運行而沒有結果。

對於最多十位數的數字，Pollard Rho是沒有必要的。簡單的試用部門將足夠快，因爲你只需要小於100000的素數，而且只有9592個。

來源

2012-05-31 13:02:59 user448810

Pollard Rho因子分解方法的實施

回答

相關問題