大整數分解(Pollard Rho 演算法)

數字輸入

示例數字:

分解結果

輸入數字後點擊開始分解

Pollard Rho 演算法說明:

演算法原理: 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 為測試輪數,用於素性判定

應用場景:

  • 密碼學:分析 RSA 加密的安全性(破解弱金鑰)
  • 數論研究:研究數字的因子結構和分佈
  • 競賽程式設計:快速分解大整數,解決數論問題
  • 數學教育:理解整數分解和素數的性質