python - 优化整数系数列表与其长整数表示之间的转换

Question

我正在尝试优化我的多项式实现。特别是我正在处理系数模 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 of size *window*, return
    the list of coefficients modulo *n*.
    '''

    mask = 2**window - 1
    coefs = [0] * (long_repr.bit_length() // window + 1)
    for i in xrange(len(coefs)):
        coefs[i] = (long_repr & mask) % n
        long_repr >>= window

    # assure that the returned list is never empty, and hasn't got an extra 0.
    if not coefs:
        coefs.append(0)
    elif not coefs[-1] and len(coefs) > 1:
        coefs.pop()

    return coefs

请注意，我没有选择 n ，它是来自用户的输入，我的程序想要证明它的素性(使用 AKS 测试)，所以我不能分解它。

---

(*) 我尝试了几种方法:

1. 使用 numpy数组而不是列表并使用 numpy.convolve 相乘. n < 2^64 很快但对于 n > 2^64 来说非常慢[我也想避免使用外部库]
2. 使用 scipy.fftconvolve .对 n > 2^64 根本不起作用.
3. 从一开始就将系数表示为整数(无需每次都进行转换)。问题是我不知道有什么简单的方法可以执行 mod x^r -1操作而不将整数转换为系数列表(这违背了使用这种表示的原因)。

Answer 1

除非您这样做是为了学习，否则为什么要重新发明轮子？一种不同的方法是为其他一些多项式库或程序编写一个 python 包装器，如果这样的包装器尚不存在的话。

试试 PARI/GP。它的速度快得惊人。我最近写了一个自定义的 C 代码，我花了两天时间写，结果只比两行 PARI/GP 脚本快 3 倍。我敢打赌，调用 PARI 的 python 代码最终会比你单独在 python 中实现的任何代码都要快。甚至还有一个用于从 python 调用 PARI 的模块: https://code.google.com/p/pari-python/