中文
Sign in
AI tools
聊天
热门问题
时间线
Loading AI tools
全部
文章
字典
引用
地图
Pollard's rho algorithm
来自维基百科,自由的百科全书
Found in articles
整数分解
factorization) 波拉德
RHO
算法(英语:
Pollard's
rho
algorithm
) 代数群因式分解算法(英语:Algebraic-group factorisation algorithms),其中包括
Pollard's
p − 1算法(英语:
Pollard's
p − 1
algorithm
)、Williams'
安全素数
(OEIS數列A005385) 之所以叫它们是“安全”素数,是因为它们在加密算法中的运用:某些因數分解的演算法(如
Pollard
Rho
演算法(英语:
Pollard's
rho
algorithm
))的計算時間部份取決於被分解數的質因數減去一的因數大小,而若被分解的數以一個安全質數2p+1作為因數,由於
數論主題列表
卢卡斯-莱默检验法在梅森素数上的运用 AKS素性检验 NewPGen(英语:NewPGen) 整数分解
Pollard
p-1法
Pollard's
rho
algorithm
(英语:
Pollard's
rho
algorithm
) Lenstra 椭圆曲线分解法 二次筛选法 特殊数域筛选法 普通数域筛选法 秀爾演算法
光滑數
Pollard's
p − 1
algorithm
),這類演算法一般會應用在光滑數中,但不會特別標示光滑數的B是多少。此時的B需是一個較小的整數,若B增加,演算法的效率就會迅速的變差。例如計算離散對數的Pohlig–Hellman演算法(英语:Pohlig–Hellman
algorithm
)的時間複雜度是O(B1/2)。
輾轉相除法
{1}{7}}}}=[2;3,7]} 计算最大公约数是很多整数分解算法的重要步骤,如
Pollard's
rho
算法(英语:
Pollard's
rho
algorithm
)、Shor算法、Dixon分解法(英语:Dixon'
s
factorization method)以及Lenstra椭圆曲线分解(英语:Lenstra