math - 在有限域上实现FFT

我想使用NTT实现多项式的乘法。我遵循了Number-theoretic transform (integer DFT)，它似乎可以工作。

现在，我想在有限域Z_p[x]上实现多项式的乘法，其中p是任意质数。

与以前的无限制情况相比，它是否改变了系数现在受p限制的任何内容？

特别是，原始NTT需要找到质数N作为大于(magnitude of largest element of input vector)^2 * (length of input vector) + 1的工作模数，以便结果永不溢出。如果结果无论如何都会受到该p质数的限制，则模数可以是多少？请注意，p - 1不必为(some positive integer) * (length of input vector)形式。

编辑：我从上面的链接复制粘贴了源代码来说明问题：

#
# Number-theoretic transform library (Python 2, 3)
#
# Copyright (c) 2017 Project Nayuki
# All rights reserved. Contact Nayuki for licensing.
# https://www.nayuki.io/page/number-theoretic-transform-integer-dft
#

import itertools, numbers

def find_params_and_transform(invec, minmod):
    check_int(minmod)
    mod = find_modulus(len(invec), minmod)
    root = find_primitive_root(len(invec), mod - 1, mod)
    return (transform(invec, root, mod), root, mod)

def check_int(n):
    if not isinstance(n, numbers.Integral):
        raise TypeError()

def find_modulus(veclen, minimum):
    check_int(veclen)
    check_int(minimum)
    if veclen < 1 or minimum < 1:
        raise ValueError()
    start = (minimum - 1 + veclen - 1) // veclen
    for i in itertools.count(max(start, 1)):
        n = i * veclen + 1
        assert n >= minimum
        if is_prime(n):
            return n

def is_prime(n):
    check_int(n)
    if n <= 1:
        raise ValueError()
    return all((n % i != 0) for i in range(2, sqrt(n) + 1))

def sqrt(n):
    check_int(n)
    if n < 0:
        raise ValueError()
    i = 1
    while i * i <= n:
        i *= 2
    result = 0
    while i > 0:
        if (result + i)**2 <= n:
            result += i
        i //= 2
    return result

def find_primitive_root(degree, totient, mod):
    check_int(degree)
    check_int(totient)
    check_int(mod)
    if not (1 <= degree <= totient < mod):
        raise ValueError()
    if totient % degree != 0:
        raise ValueError()
    gen = find_generator(totient, mod)
    root = pow(gen, totient // degree, mod)
    assert 0 <= root < mod
    return root

def find_generator(totient, mod):
    check_int(totient)
    check_int(mod)
    if not (1 <= totient < mod):
        raise ValueError()
    for i in range(1, mod):
        if is_generator(i, totient, mod):
            return i
    raise ValueError("No generator exists")

def is_generator(val, totient, mod):
    check_int(val)
    check_int(totient)
    check_int(mod)
    if not (0 <= val < mod):
        raise ValueError()
    if not (1 <= totient < mod):
        raise ValueError()
    pf = unique_prime_factors(totient)
    return pow(val, totient, mod) == 1 and all((pow(val, totient // p, mod) != 1) for p in pf)

def unique_prime_factors(n):
    check_int(n)
    if n < 1:
        raise ValueError()
    result = []
    i = 2
    end = sqrt(n)
    while i <= end:
        if n % i == 0:
            n //= i
            result.append(i)
            while n % i == 0:
                n //= i
            end = sqrt(n)
        i += 1
    if n > 1:
        result.append(n)
    return result

def transform(invec, root, mod):
    check_int(root)
    check_int(mod)
    if len(invec) >= mod:
        raise ValueError()
    if not all((0 <= val < mod) for val in invec):
        raise ValueError()
    if not (1 <= root < mod):
        raise ValueError()

    outvec = []
    for i in range(len(invec)):
        temp = 0
        for (j, val) in enumerate(invec):
            temp += val * pow(root, i * j, mod)
            temp %= mod
        outvec.append(temp)
    return outvec

def inverse_transform(invec, root, mod):
    outvec = transform(invec, reciprocal(root, mod), mod)
    scaler = reciprocal(len(invec), mod)
    return [(val * scaler % mod) for val in outvec]

def reciprocal(n, mod):
    check_int(n)
    check_int(mod)
    if not (0 <= n < mod):
        raise ValueError()
    x, y = mod, n
    a, b = 0, 1
    while y != 0:
        a, b = b, a - x // y * b
        x, y = y, x % y
    if x == 1:
        return a % mod
    else:
        raise ValueError("Reciprocal does not exist")

def circular_convolve(vec0, vec1):
    if not (0 < len(vec0) == len(vec1)):
        raise ValueError()
    if any((val < 0) for val in itertools.chain(vec0, vec1)):
        raise ValueError()
    maxval = max(val for val in itertools.chain(vec0, vec1))
    minmod = maxval**2 * len(vec0) + 1
    temp0, root, mod = find_params_and_transform(vec0, minmod)
    temp1 = transform(vec1, root, mod)
    temp2 = [(x * y % mod) for (x, y) in zip(temp0, temp1)]
    return inverse_transform(temp2, root, mod)

vec0 = [24, 12, 28, 8, 0, 0, 0, 0]
vec1 = [4, 26, 29, 23, 0, 0, 0, 0]

print(circular_convolve(vec0, vec1))

def modulo(vec, prime):
    return [x % prime for x in vec]

print(modulo(circular_convolve(vec0, vec1), 31))

印刷品：

[96, 672, 1120, 1660, 1296, 876, 184, 0]
[3, 21, 4, 17, 25, 8, 29, 0]

但是，在将minmod = maxval**2 * len(vec0) + 1更改为minmod = maxval + 1的地方，它停止工作：

[14, 16, 13, 20, 25, 15, 20, 0]
[14, 16, 13, 20, 25, 15, 20, 0]

为了按预期工作，最小的minmod（在上面的链接中的N）是多少？

最佳答案

如果您输入的n整数绑定到某个素数q（任何mod q不仅是素数都将是相同的），您可以将其用作max value +1，但是请注意，您不能将其用作素数p具有特殊属性。他们都在这里：


Translation from Complex-FFT to Finite-Field-FFT


因此，每个输入的最大值为p，但是在您的任务计算过程中（对2个NTT结果进行卷积），第一层结果的大小可以提高到q-1，但是当我们对它们进行卷积时，最终iNTT的输入大小将上升到：

m = n.((q-1)^2)

如果您在NTT上执行不同的操作，则n.(q-1)公式可能会发生变化。

现在让我们回到m，简而言之，您可以使用支持这些的任何素数p：

p mod n == 1
p > m

并且存在p这样：

p mod (L-1) = 0
r^(L*i) mod p == 1 // i = { 0,n }
r^(L*i) mod p != 1 // i = { 1,2,3, ... n-1 }

如果满足所有条件，则1 <= r,L < p是单位的第n个根，可以用于NTT。要找到这样的素数和p，请查看上面的链接（有C ++代码可以找到这样的素数）。

例如，在字符串乘法期间，我们对它们进行2个字符串NTT处理，然后对结果进行卷积，然后iNTT返回结果（即两个输入大小之和）。因此，例如：

                                99999999999999999999999999999999
                               *99999999999999999999999999999999
----------------------------------------------------------------
9999999999999999999999999999999800000000000000000000000000000001

r,L和两个操作数均为9 ^ 32，因此q = 10因此为n=32，找到的素数为m = 9*9*32 = 2592。如您所见，结果匹配，因此不会发生溢出。但是，如果我使用仍然适合所有其他条件的任何较小的质数，则结果将不匹配。我专门用它来尽可能地拉伸NTT值（所有值均为p = 2689，大小等于2的幂）

如果您的NTT是快速的，并且q-1不是2的幂，那么对于每个NTT，您都需要将零填充到最接近或等于2大小的幂。但这不会影响n值，因为零填充不应该增加值的大小。我的测试证明了这一点，因此对于卷积可以使用：

m = (n1+n2).((q-1)^2)/2

其中m是零填充之前的原始输入大小。

有关实现NTT的更多信息，您可以在C ++中进行检查（广泛优化）：


Modular arithmetics and NTT (finite field DFT) optimizations


因此，回答您的问题：


是的，您可以利用输入为n1,n2的事实，但是不能将mod q用作q！
您只能将p用于单个NTT（或NTT的第一层），但是当您在NTT使用过程中将它们与卷积链接在一起时，就不能将其用于最后的INTT阶段！


但是，正如我在评论中提到的那样，最简单的方法是使用最大可能的minmod = n * (maxval + 1)来适合您正在使用的数据类型，并且可用于支持2种输​​入大小的所有幂。

基本上，这使您的问题变得无关紧要。我只能想到不可能/不希望出现这种情况的唯一情况是在没有“最大”限制的任意精度数字上。绑定到变量p的过程中有很多性能问题，因为对p的搜索确实很慢（甚至可能比NTT本身还要慢），并且变量p禁用了许多使NTT真正需要的模块化算法的性能优化。慢。