使用长整数将两个多项式mod n，x ^ r-1相乘:正确的窗口大小是多少? [英] Multiplying two polynomials mod n,x^r-1 using long integers: what is the correct window size?

问题描述

使用窗口乘法算法，使用长整数乘法将两个多项式[Z/nZ中的系数和整个r的多项式mod x^r-1)与长整数相乘，我应该给窗口以多大的大小?

Using a window multiplication algorithm to multiply two polynomials[coefficients in Z/nZ and the whole polynomial mod x^r-1 for some r] using long-integer multiplications, what size should I give to the window?

这里的窗口"是指系数应在初始长整数中使用的位长，以使长整数乘法的结果包含结果的正确系数[系数之和't重叠"].

Where by "window" I mean the bit-length that the coefficients should use in the initial long-integers such that the result of the long-integer multiplication contains the correct coefficients of the result[the sums of the coefficients "don't overlap"].

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

At the beginning I thought that ceil(log(n**2,2)) + 1 would be enough, because each coefficient is at most n-1 so a product of these coefficients is at most (n-1)**2. Then I realized that when doing a long-integer multiplication there can be some sums of these coefficients, thus the window should be ceil(log(number-of-additions * n**2,2)) + 1.

我认为两个多项式相加的和最多为一个总和，但是使用ceil(log((deg_a + deg_b + 1) * n**2,2)) +1可以工作一段时间，但是最终系数重叠并且得到错误的结果.

I thought that there could be at most the sum of the degrees of the two polynomials additions, but using ceil(log((deg_a + deg_b + 1) * n**2,2)) +1 works for some time, but eventually the coefficients overlap and I get incorrect results.

那么这个窗口"应该有多大?

So how big should this "window" be?

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

By the way, here's the current (python) code:

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位的差异，这很多如果您认为...]，这意味着这些尺寸中的最小尺寸(如果已经可以)，但是在某个地方还有其他问题.

edit 1: I'm starting to think that the window size may not be the problem. I've tried to increase it up to ceil(log2((new_deg+1)**3 * self._mod_n ** 5))+1 and this yields the same results as using ceil(log2((new_deg+1) * self._mod_n**2))+1, and since the difference between these two size is really big[about 55-60 bits difference in my tests, which is a lot if you think...],this means that probably the smallest of these size if already okay, but there is some other problem somewhere.

修改2: 错误结果的示例是:

edit 2: An example of wrong result is:

#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)

我将尝试查找一些较小的示例，以便我可以手动进行验证.

I'll try to find some smaller example, so that I can verify it by hand.

修改3: 好吧，我发现学位有问题.我找到了一个例子，其中度数变为负数，这显然不应该是负数.因此，我将尝试挖掘更多检查时间以及为什么以这种意外的方式发生变化的原因.

edit 3: Okay, I found out that there is some problem with the degree. I found an example in which the degree becomes negative, which obviously shouldn't be. So i'll try to dig more checking when and why the degree changes in this unexpected way.

修改4: 我发现了这个错误.创建整数时，我在所有_coefs序列上进行迭代，但是我的实现并不能保证与多项式次数>对应的所有系数都为0.

edit 4: I've found the bug. When creating the integer I was iterating over all the _coefs sequence, but my implementation does not guarantee that all coefficients that correspond to a degree > of the polynomial degree are 0. This fixes the issue.

修改5: 我已经通过测试此实现获得了一些性能结果.

edit 5: Just some performance results I've obtained testing this implementation.

1)使用长整数乘法比使用numpy.convolve iff 更快更快，系数大于整数.否则numpy.convolve会更快.

1) Using long-integer multiplication is faster than using numpy.convolve iff the coefficients are bigger than ints. Otherwise numpy.convolve is faster.

2)大约有80％的时间用于将系数列表转换为整数，并将整数转换为系数列表.由于这些操作都是O(n)，因此您无能为力.

2) About 80% of the time is spent converting lists of coefficients to integers and integers to lists of coefficients. There is not much you can do about this, since these operations are O(n).

现在，我想知道是否有一种方法可以仅使用长整数来有效地实现"mod x ^ r-1"操作...这可能会大大提高速度，因为在那个时候点，您不必再进行转换.

Now i'm wondering if there is a way to implement the "mod x^r-1" operation in an efficient way using only long-integers... this could probably give a big speed-up, since at that point you don't have to do the conversions anymore.

推荐答案

正确的计算方法是

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

但是，这肯定会小于您计算出的窗口，因此肯定还有其他一些原因会导致结果不正确.您确定学位计算正确吗?您能举一个错误计算的多项式示例吗?

However this will definitely be less than the window you calculated, so there must be some other reason you're getting incorrect results. Are you sure the degree is being calculated correctly? Can you give an example of a polynomial that is calculated incorrectly?

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

Unless there's a particularly good reason to use long integer multiplication, I'd recommend using NumPy:

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

这通常至少和长整数乘法(无论如何都是卷积)一样有效，而且您要担心的Python代码要少得多.实际上，NumPy具有多项式库；尽管它是为浮点系数而设计的，但是您可以通过查看它来了解如何有效地实现代码.

This will usually be at least as efficient as long integer multiplication (which is a form of convolution anyway), and you've got a lot less Python code to worry about. In fact NumPy has a polynomial library; although it's designed for floating-point coefficients, you can look at it to get an idea how to implement your code efficiently.

这篇关于使用长整数将两个多项式mod n，x ^ r-1相乘:正确的窗口大小是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！