python - 使用长整数将两个多项式 mod n,x^r-1 相乘 : what is the correct window size?

Question

使用窗口乘法算法将两个多项式相乘[Z/nZ中的系数]和整个多项式模 x^r-1对于某些使用长整数乘法的 r]，我应该给窗口多大的大小？

其中“窗口”是指系数应在初始长整数中使用的位长度，以便长整数乘法的结果包含结果的正确系数[系数之和“don”不重叠”]。

一开始我以为ceil(log(n**2,2)) + 1就足够了，因为每个系数最多为 n-1所以这些系数的乘积最多是 (n-1)**2 。 然后我意识到，在进行长整数乘法时，这些系数可能会有一些和，因此窗口应该是 ceil(log(number-of-additions * n**2,2)) + 1 .

我认为最多可能有两个多项式加法的次数之和，但是使用 ceil(log((deg_a + deg_b + 1) * n**2,2)) +1工作了一段时间，但最终系数重叠，我得到了不正确的结果。

那么这个“窗口”应该有多大呢？

顺便说一下，这是当前的(python)代码:

def __mul__(self, other):
    new = ModPolynomial(self._mod_r, self._mod_n)
    #new = x mod self._mod_n,x^(self._mod_r -1)
    try:
        new_deg = self._degree + other.degree
        new_coefs = []
        # i've also tried with (new_deg + 1) ** 2 * ...
        window = int(math.ceil(math.log((new_deg + 1) * self._mod_n**2,2))) + 1
        A = 0
        for i,k in enumerate(self._coefs):
            A += k << (window * i)
        B = 0
        for i,k in enumerate(other.coefficients):
            B += k << (window * i)

        res = A * B
        mask = 2**window - 1
        while res:
            new_coefs.append((res & mask) % self._mod_n)
            res >>= window
        new._coefs = new_coefs
        new._degree = self._finddegree(new_coefs)
    except AttributeError:
        new._coefs = [(c * other) % self._mod_n for c in self._coefs]
        new._degree = self._finddegree(new._coefs)
    new._mod()
    return new

编辑 1: 我开始认为窗口大小可能不是问题。 我尝试将其增加到 ceil(log2((new_deg+1)**3 * self._mod_n ** 5))+1这会产生与使用 ceil(log2((new_deg+1) * self._mod_n**2))+1 相同的结果，并且由于这两个大小之间的差异非常大[在我的测试中大约有 55-60 位差异，如果你认为这很大......]，这意味着如果已经可以的话，可能是这些大小中最小的，但是有某处还有其他问题。

编辑2: 错误结果的一个例子是:

#ModPolynomial(r,n) = x mod n, x^r-1
>>> pol = polys.ModPolynomial(20,100)      # uses integer-multiplication
>>> pol += 2
>>> pol2 = polynomials.ModPolynomial(20,100)   #uses the naive algorithm
>>> pol2 += 2
>>> (pol2**52).coefficients      #should be the correct result[first is coef of x^0]
(76, 76, 44, 0, 0, 16, 16, 4, 0, 0, 24, 24, 81, 0, 0, 80, 80, 20)
>>> (pol**52).coefficients       #the wrong result
(12L, 52L, 8L, 20L, 60L, 12L, 92L, 28L, 60L, 80L, 68L, 48L, 22L, 0L, 0L, 20L, 20L, 80L)

我会尝试找到一些较小的示例，以便我可以手动验证它。

编辑3: 好吧，我发现学位有问题。我发现了一个例子，其中度数变为负数，这显然不应该是。因此，我将尝试更多地检查度数何时以及为何以这种意想不到的方式发生变化。

编辑4: 我发现了这个错误。创建整数时，我迭代了所有 _coefs序列，但我的实现并不能保证与多项式次数 > 次数对应的所有系数均为 0。这解决了问题。

编辑 5: 只是我测试此实现时获得的一些性能结果。

1) 使用长整数乘法比使用 numpy.convolve 更快 当且仅当系数大于整数。否则numpy.convolve更快。

2) 大约 80% 的时间花在将系数列表转换为整数以及将整数转换为系数列表上。对此您无能为力，因为这些操作的复杂度为 O(n)。

现在我想知道是否有一种方法可以仅使用长整数以有效的方式实现“mod x^r-1”操作...这可能会带来很大的加速，因为那时点您不必再进行转换。

Answer 1

正确的计算是

window = int(math.ceil(math.log((max(self._degree, other.degree) + 1) *
                                (self._mod_n - 1)**2, 2)))

但是，这肯定会小于您计算的窗口，因此一定还有其他原因导致您得到不正确的结果。您确定学位计算正确吗？你能给出一个计算错误的多项式的例子吗？

除非有特别充分的理由使用长整数乘法，否则我建议使用 NumPy:

new.coeffs = np.convolve(self.coeffs, other.coeffs) % self.mod

这通常至少与长整数乘法(无论如何，这是卷积的一种形式)一样高效，并且您需要担心的 Python 代码要少得多。事实上 NumPy 有一个 polynomial library ;尽管它是为浮点系数设计的，但您可以查看它以了解如何有效地实现代码。