随机递归整数分解算法的计算复杂度与递归层概率问题

我正在研究递归第j层找到因数p和q的概率PN。核心思路是将N表示为x² + bx + c的形式，求解该二次方程需要找到满足delta相关条件及N的因数条件的随机变量x的取值。我已证明c < sqrt(N)：若delta为完全平方数，则b与sqrt(delta)奇偶性相同，进而得到整数解x₁和x₂。现在的问题是：在[1, floor(sqrt(N))]范围内随机抽取x时，抽到使得delta(x)为完全平方数的x的概率是多少？

Function Factorize(N):
    // 基准情况：小整数N
    If N <= 3:
        Return N 

    // 1. 在[1, floor(sqrt(N))]范围内选取x
    x = RandomInteger(1, floor(sqrt(N)))

    // 2. 基于N = x^2 + bx + c计算系数
    // b = floor((N - x^2) / x)
    // c = N - x^2 - (b * x)
    b = floor((N - x^2) / x)
    c = N - x^2 - (b * x)

    // 3. 求解二次判别式delta = b^2 - 4c
    delta = b^2 - (4 * c)

    // 4. 若delta为完全平方数，尝试提取因数
    If delta >= 0 AND IsPerfectSquare(delta):
        sqrt_delta = sqrt(delta)
        x1 = (-b - sqrt_delta) / 2
        x2 = (-b + sqrt_delta) / 2

        p = x + abs(x1)
        q = x + abs(x2)

        If (p * q) == N:
            Return (p, q)

    // 5. 递归步骤：对余数c进行分解
    Return Factorize(c)

概率分析思路 #

要计算该概率，需先明确delta(x)的化简表达式：
将代码中b和c的定义代入delta，令k = floor((N - x²)/x)，则delta可化简为：
delta = (2x + k)² - 4N

要使delta为完全平方数，设delta = m²（m为非负整数），则可推导出：
(2x + k - m)(2x + k + m) = 4N
由于等式两边的因子同奇偶，可进一步转化为A*B = N（其中A、B为N的因数对，A≤B），即满足条件的x必然对应N的某一对因数。

具体概率推导 #

概率等于满足delta为完全平方数的x的个数除以floor(sqrt(N))，但无法给出统一的闭合式，需结合N的因数结构分析：

• 若N为素数：仅存在(1, N)一组因数对，满足条件的x数量极少，概率约为O(1/√N)。
• 若N为合数：因数对数量越多，满足条件的x的数量通常越多，概率也会相应提升。例如当N是平方数时，因数对数量更多，对应满足条件的x可能更多。

内容的提问来源于stack exchange，提问作者daniele dessolis