云氏算法

Question

我想尝试实现 Yun's algorithm 以实现多项式的无平方因式分解。来自维基百科（f 是多项式）：

a0 = gcd(f, f'); b1 = f/a0; c1 = f'/a0; d1 = c1 - b1'; i = 1
repeat
ai = gcd(bi, di); bi+1 = bi/ai; ci+1 = di/ai; i = i + 1; di = ci - bi'
until b = 1

但是，我不确定第二步。我想将它用于具有整数系数的多项式（不需要 monic 或 primitive）。是否可以仅使用整数来实现除法 b1 = f/a0？

我找到了 synthetic division 的代码：

def extended_synthetic_division(dividend, divisor):
    '''Fast polynomial division by using Extended Synthetic Division. Also works with non-monic polynomials.'''
    # dividend and divisor are both polynomials, which are here simply lists of coefficients. Eg: x^2 + 3x + 5 will be represented as [1, 3, 5]

    out = list(dividend) # Copy the dividend
    normalizer = divisor[0]
    for i in xrange(len(dividend)-(len(divisor)-1)):
        out[i] /= normalizer # for general polynomial division (when polynomials are non-monic),
                             # we need to normalize by dividing the coefficient with the divisor's first coefficient
        coef = out[i]
        if coef != 0: # useless to multiply if coef is 0
            for j in xrange(1, len(divisor)): # in synthetic division, we always skip the first coefficient of the divisor,
                                              # because it is only used to normalize the dividend coefficients
                out[i + j] += -divisor[j] * coef

    # The resulting out contains both the quotient and the remainder, the remainder being the size of the divisor (the remainder
    # has necessarily the same degree as the divisor since it is what we couldn't divide from the dividend), so we compute the index
    # where this separation is, and return the quotient and remainder.
    separator = -(len(divisor)-1)
    return out[:separator], out[separator:] # return quotient, remainder.

我的问题是out[i] /= normalizer。对于 Yun 的 b1 = f/a0，它总是适用于整数（下限）除法吗？是不是总是可以除f/gcd(f, f')？ out[separator:]（余数）总是归零吗？

Answer 1

“p/GCD(p, p') 中的除法将始终有效（即 "exact"，在 Z 中没有余数）”这一事实遵循定义的 GCD。对于任何多项式 p 和 q，它们的 GCD(p,q) 可以精确地除以 p 和 q。这就是为什么它被称为 GCD 即 Greatest Common Divisor:

A greatest common divisor of p and q is a polynomial d that divides p and q and such that every common divisor of p and q also divides d.

P.S。在更专业的 https://math.stackexchange.com/

上问这样的纯数学问题更有意义

云氏算法

Yun's algorithm

math

polynomial-math

factorization

polynomials