shundebo图书馆

Pollard Rho 算法详解

2025-11-08 · 11 min read
Pollard Rho 算法详解

Pollard Rho 算法详解

Pollard Rho 算法是一种用于分解合数的概率性算法，由 John Pollard 在 1975 年提出。它基于弗洛伊德循环查找算法，是分解中等大小整数（特别是那些有小质因子的数）的高效方法。 

    <h2>算法核心思想</h2>
    <h3>1. 基本思路</h3>
    <p>算法基于<strong>生日悖论</strong>：在一组随机数中，找到两个数在模 <code>p</code>（<code>n</code> 的一个真因子）下同余的概率比我们想象的要高。</p>

    <h3>2. 核心原理</h3>
    <ul>
        <li>使用一个伪随机函数生成序列</li>
        <li>序列最终会进入循环（形状像希腊字母 <strong>ρ</strong>，因此得名）</li>
        <li>在模 <code>p</code> 下，序列进入循环的速度比在模 <code>n</code> 下更快</li>
        <li>通过检测循环来找到因子</li>
    </ul>

    <h2>算法详细步骤</h2>
    <h3>数学原理</h3>
    <p>我们想要分解合数 <code>n</code>。假设 <code>p</code> 是 <code>n</code> 的一个真因子（<code>p &lt; n</code>）。</p>
    <ol>
        <li>选择伪随机函数：通常使用 <code>f(x) = (x² + c) mod n</code>，其中 <code>c</code> 是常数</li>
        <li>生成序列：<code>x₀, x₁, x₂, ...</code> 其中 <code>xᵢ₊₁ = f(xᵢ)</code></li>
        <li>序列在模 <code>p</code> 下会进入循环，因为值域有限</li>
        <li>使用 <strong>Floyd 循环检测法</strong>：维护两个指针，一个慢指针（每次一步），一个快指针（每次两步）</li>
        <li>当 <code>gcd(|x - y|, n) ≠ 1</code> 且 <code>≠ n</code> 时，找到了一个因子</li>
    </ol>

    <h2>Python 实现</h2>
    <h3>基础版本</h3>
    <pre><code>import math

import random

def pollard_rho_basic(n, max_iterations=100000):
"""
Pollard Rho 算法基础版本
"""
if n == 1:
return None
if n % 2 == 0:
return 2

# 伪随机函数 f(x) = (x^2 + c) mod n
def f(x, c):
    return (x * x + c) % n

# 初始化
x = random.randint(2, n-2)
y = x
c = random.randint(1, n-1)
d = 1

iterations = 0
while d == 1 and iterations < max_iterations:
    # 慢指针走一步
    x = f(x, c)
    
    # 快指针走两步
    y = f(y, c)
    y = f(y, c)
    
    # 计算 gcd
    d = math.gcd(abs(x - y), n)
    iterations += 1
    
    # 如果找到 n 本身，重新开始
    if d == n:
        return pollard_rho_basic(n, max_iterations)

if d != 1 and d != n:
    return d
return None

测试基础版本

def test_basic():
n = 8051
factor = pollard_rho_basic(n)
if factor:
print(f"Pollard Rho 找到 {n} 的因子: {factor}, 另一个因子: {n // factor}")
else:
print(f"未能分解 {n}")

test_basic()

输出: Pollard Rho 找到 8051 的因子: 97, 另一个因子: 83



Pollard Rho 找到 8051 的因子: 97, 另一个因子: 83

    <h2>算法详细分析</h2>
    <h3>1. 为什么选择 <code>f(x) = x² + c</code>？</h3>
    <p>这个函数具有很好的伪随机性质：</p>
    <ul>
        <li>计算简单快速</li>
        <li>能产生足够复杂的序列</li>
        <li>在实践中表现良好</li>
    </ul>

    <h3>2. Floyd 循环检测法原理</h3>
    <pre><code>def demonstrate_floyd_cycle():
"""
演示 Floyd 循环检测法
"""
# 模拟一个会进入循环的序列
sequence = [2, 5, 26, 677, 7474, 2833, 8713, 1806, 8713, 1806, 8713, ...]

# 慢指针和快指针
slow = 0  # 索引
fast = 0

# 模拟 Floyd 算法
while True:
    slow += 1  # 慢指针走一步
    fast += 2  # 快指针走两步
    
    if sequence[slow] == sequence[fast]:
        print(f"在位置 {slow} 和 {fast} 检测到循环")
        break

实际算法中，我们不需要存储整个序列，只需要计算 gcd

    <div class="rho-svg">
        <h3>ρ 形状示意图</h3>
        <svg viewBox="0 0 300 200" xmlns="http://www.w3.org/2000/svg">
            <path d="M 50 100 Q 50 50 100 50 Q 150 50 150 100 Q 150 150 100 150 Q 50 150 50 100" 
                  fill="none" stroke="#3b82f6" stroke-width="4"/>
            <path d="M 150 100 L 220 100" fill="none" stroke="#3b82f6" stroke-width="4"/>
            <circle cx="220" cy="100" r="40" fill="none" stroke="#3b82f6" stroke-width="4"/>
            <text x="120" y="45" font-size="16" fill="#475569">尾部</text>
            <text x="200" y="95" font-size="16" fill="#475569">环部</text>
            <text x="20" y="110" font-size="14" fill="#94a3b8">slow: 1步</text>
            <text x="230" y="80" font-size="14" fill="#94a3b8">fast: 2步</text>
        </svg>
    </div>

    <h3>3. 时间复杂度</h3>
    <ul>
        <li><strong>期望时间复杂度</strong>：O(√p)，其中 p 是 n 的最小质因子</li>
        <li><strong>最坏情况</strong>：O(√n)</li>
        <li><strong>空间复杂度</strong>：O(1)，只需要常数空间</li>
    </ul>

    <h2>手写笔记重点解读</h2>
    <div class="handnote">
        <p><strong>一、检测循环：</strong></p>
        <p style="margin-left: 20px;">slow 走1步<br>fast 走2步</p>
        <p><strong>二、关键数学原理：</strong></p>
        <p style="margin-left: 20px;">当龟兔相遇：<br><code>xᵢ ≡ xⱼ (mod p)</code><br>⇒ <code>xᵢ - xⱼ ≡ 0 (mod p)</code><br>⇒ <code>p 整除 (xᵢ - xⱼ)</code></p>
        <p style="margin-left: 20px;">同时：<br><code>xᵢ - xⱼ ≠ 0 (mod n)</code><br>因为 n 可能有其他质因子。</p>
        <p style="margin-left: 20px;"><strong>因此：</strong><br><code>p 能整除 |xᵢ - xⱼ|</code><br><code>n 不能整除</code><br>⇒ <code>gcd(|xᵢ - xⱼ|, n) ≥ p</code></p>
        <p style="color: #dc2626; font-weight: bold; text-align: center; margin-top: 15px;">如果这个 gcd 不是 1 也不是 n，那么它就是 n 的一个真因子！</p>
    </div>

    <footer>
        <p>© 2025 Pollard Rho 算法学习笔记 | 基于 OI Wiki 与经典教材整理</p>
        <p><a href="https://oi-wiki.org/math/number-theory/factorization/" style="color: #3b82f6;">OI Wiki - 分解质因数</a></p>
    </footer>
</div>