演算法原理:
Pollard Rho 是一種用於整數分解的機率性演算法,特別適合找到合數的中等大小因子。演算法名稱來源於其執行軌跡形似希臘字母 ρ (rho)。
最佳化策略:
- 試除法最佳化:先用小素數(2, 3, 5, 7, 11...)進行試除,快速找到小因子
- Pollard Rho:對於較大的合數,使用偽隨機序列 x = (x² + c) mod n 找到因子
- Floyd 判圈演算法:使用快慢指標檢測序列中的環,最佳化空間複雜度
- Miller-Rabin 素性測試:在找到因子後,判斷是否為素數,避免繼續分解
- 遞迴分解:對找到的因子遞迴進行分解,直到所有因子都是素數
時間複雜度:
- 試除法:O(√n),適用於小數字或快速找到小因子
- Pollard Rho:期望時間 O(n^(1/4)),對於有中等因子的數字非常高效
- Miller-Rabin:O(k log³n),k 為測試輪數,用於素性判定