1

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

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

一开始我认为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并且这产生与 using 相同的结果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”操作......这可能会大大加快速度，因为那时你不'不必再进行转换了。

4

1 回答 1

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 有一个多项式库；尽管它是为浮点系数设计的，但您可以查看它以了解如何有效地实现您的代码。

于 2012-08-21T18:53:30.123 回答