相关疑难解决方法(0)

我正在尝试优化我的多项式实现.特别是我正在处理具有模数n(可能是>2^64)的多项式,并以形式x^r - 1(r是< 2^64)对多项式求模.目前我将系数表示为整数列表(*),并且我以最直接的方式实现了所有基本操作.

我希望取幂和乘法尽可能快,为了获得这个,我已经尝试了不同的方法.我目前的方法是将系数列表转换为大整数乘以整数并将系数解包.

问题是包装和拆包需要花费很多时间.

那么,有没有办法改善我的"打包/解包"功能？

def _coefs_to_long(coefs, window):
    '''Given a sequence of coefficients *coefs* and the *window* size return a
    long-integer representation of these coefficients.
    '''

    res = 0
    adder = 0
    for k in coefs:
        res += k << adder
        adder += window
    return res
    #for k in reversed(coefs): res = (res << window) + k is slower


def _long_to_coefs(long_repr, window, n):
    '''Given a long-integer representing coefficients …