我找到了一种优化转换的方法，尽管我仍然希望有人能够帮助我进一步改进它们，并希望找到其他聪明的想法。
基本上，这些函数存在某种二次内存分配行为，当打包整数或解包整数时会出现问题。
（请参见Guido van Rossum的this帖子中的另一个此类行为的示例）。
在意识到这一点后，我决定尝试使用“分而治之”的原则，并获得了一些结果。我只是将数组分成两部分，分别进行转换，最后将结果合并（稍后我将尝试使用类似于Rossum帖子中的f5的迭代版本[编辑：似乎没有更快]）。
修改后的函数：
def _coefs_to_long(coefs, window):
"""Given a sequence of coefficients *coefs* and the *window* size return a
long-integer representation of these coefficients.
"""
length = len(coefs)
if length < 100:
res = 0
adder = 0
for k in coefs:
res += k << adder
adder += window
return res
else:
half_index = length // 2
big_window = window * half_index
low = _coefs_to_long(coefs[:half_index], window)
high = _coefs_to_long(coefs[half_index:], window)
return low + (high << big_window)
def _long_to_coefs(long_repr, window, n):
"""Given a long-integer representing coefficients of size *window*, return
the list of coefficients modulo *n*.
"""
win_length = long_repr.bit_length() // window
if win_length < 256:
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
if not coefs:
coefs.append(0)
elif not coefs[-1] and len(coefs) > 1:
coefs.pop()
return coefs
else:
half_len = win_length // 2
low = long_repr & (((2**window) ** half_len) - 1)
high = long_repr >> (window * half_len)
return _long_to_coefs(low, window, n) + _long_to_coefs(high, window, n)
结果如下：
>>> import timeit
>>> def coefs_to_long2(coefs, window):
... if len(coefs) < 100:
... return coefs_to_long(coefs, window)
... else:
... half_index = len(coefs) // 2
... big_window = window * half_index
... least = coefs_to_long2(coefs[:half_index], window)
... up = coefs_to_long2(coefs[half_index:], window)
... return least + (up << big_window)
...
>>> coefs = [1, 2, 3, 1024, 256] * 567
>>> # original function
>>> timeit.timeit('coefs_to_long(coefs, 11)', 'from __main__ import coefs_to_long, coefs',
... number=1000)/1000
0.003283214092254639
>>> timeit.timeit('coefs_to_long2(coefs, 11)', 'from __main__ import coefs_to_long2, coefs',
... number=1000)/1000
0.0007998988628387451
>>> 0.003283214092254639 / _
4.104536516782767
>>> coefs = [2**64, 2**31, 10, 107] * 567
>>> timeit.timeit('coefs_to_long(coefs, 66)', 'from __main__ import coefs_to_long, coefs',... number=1000)/1000
0.009775240898132325
>>>
>>> timeit.timeit('coefs_to_long2(coefs, 66)', 'from __main__ import coefs_to_long2, coefs',
... number=1000)/1000
0.0012255229949951173
>>>
>>> 0.009775240898132325 / _
7.97638309362875
正如您所看到的，此版本将转换速度提高了相当多，从4倍加快到8倍（输入越大，加速越快）。
第二个函数也可以得到类似的结果：
>>> import timeit
>>> def long_to_coefs2(long_repr, window, n):
... win_length = long_repr.bit_length() // window
... if win_length < 256:
... return long_to_coefs(long_repr, window, n)
... else:
... half_len = win_length // 2
... least = long_repr & (((2**window) ** half_len) - 1)
... up = long_repr >> (window * half_len)
... return long_to_coefs2(least, window, n) + long_to_coefs2(up, window, n)
...
>>> long_repr = coefs_to_long([1,2,3,1024,512, 0, 3] * 456, 13)
>>>
>>> timeit.timeit('long_to_coefs(long_repr, 13, 1025)', 'from __main__ import long_to_coefs, long_repr', number=1000)/1000
0.005114212036132813
>>> timeit.timeit('long_to_coefs2(long_repr, 13, 1025)', 'from __main__ import long_to_coefs2, long_repr', number=1000)/1000
0.001701267957687378
>>> 0.005114212036132813 / _
3.006117885794327
>>> long_repr = coefs_to_long([1,2**33,3**17,1024,512, 0, 3] * 456, 40)
>>> timeit.timeit('long_to_coefs(long_repr, 13, 1025)', 'from __main__ import long_to_coefs, long_repr', number=1000)/1000
0.04037192392349243
>>> timeit.timeit('long_to_coefs2(long_repr, 13, 1025)', 'from __main__ import long_to_coefs2, long_repr', number=1000)/1000
0.005722791910171509
>>> 0.04037192392349243 / _
7.0545853417694
我尝试避免在第一个函数中进行更多的内存重新分配，传递开始和结束索引并避免切片，但结果是对于小输入，这会使函数变慢很多，而对于实际情况的输入则稍微慢一些。也许我可以尝试混合它们，尽管我不认为我会获得更好的结果。
我最近修改了我的问题，因此有些人给了我一些与我最近所需不同的建议。我认为有必要澄清评论和答案中不同来源指出的结果，以便它们对其他寻求实现快速多项式和/或AKS测试的人有用。
正如J.F. Sebastian所指出的，AKS算法得到了许多改进，因此尝试实现旧版本的算法将始终导致非常缓慢的程序。这并不排除如果您已经有一个良好的AKS实现，可以通过改进多项式来加速它。
如果您对小n（即：字长数字）的系数感兴趣，并且不介意外部依赖，则可以使用numpy并使用numpy.convolve或scipy.fftconvolve进行乘法。它比您编写的任何内容都要快得多。不幸的是，如果n不是字长，则根本无法使用scipy.fftconvolve，而且numpy.convolve也会变得非常缓慢。
如果您不必对系数和多项式进行模运算，则可能使用ZBDDs是个好主意（正如harold所指出的），尽管我不能保证会有惊人的结果（尽管我认为这真的很有趣，您应该阅读Minato的论文）。
如果您不必对系数进行模运算，则可能使用RNS表示，如Origin所述，是个好主意。然后，您可以组合多个numpy数组以有效地操作。
如果您想要一个纯Python实现的具有大n模数系数的多项式，则我的解决方案似乎是最快的。尽管我没有尝试在Python中实现系数数组之间的fft乘法（可能会更快）。
