умножение полиномов над конечным полем с использованием отрицательной сверточной свертки и теоретико-числового преобразования

Question

Я пытаюсь выполнить полиномиальное умножение по кольцу Zp[x]/(x^n+1)с использованием теоретико-числового преобразования и отрицательной свернутой свертки. Я использовал код, доступный в https://www.nayuki.io/res/number-theoretic-transform-integer-dft/numbertheoretictransform.py, чтобы выполнить NTT и псевдокод в https://eprint.iacr.org/2014/646.pdf для полиномиального умножения. я выбираю n=8 (размер многочлена), и в соответствии с этой статьей я выбрал модуль p=17 таким образом, что p≡1 mod (2*n).

Сначала я выполнил умножение полиномов с помощью numpy и Python для проверки результатов.

      x=np.random.randint(0, p, n).astype(int)
y=np.random.randint(0, p, n).astype(int)
poly_modulus = ([1] + ((n - 1) * [0]) + [1]) 
mul_res=np.polymul(np.array(x),np.array( y))%p
after_reduction=(np.polydiv(mul_res,poly_modulus)[1])%p

и вот результаты, которые я получил:

      x=[ 4 3 10 12 11 14 10 6 ]
y=[ 14 6 14 11 3 15 7 14 ]
mul_res=[ 5 15 10 8 3 14 1 10 9 13 7 12 16 12 16 ]
after_reduction=[ 13 2 3 13 4 2 2 10 ]

Я попытался умножить эти два многочлена, как описано в статье, с помощью NTT.

      N=find_modulus(n, p)
w = find_primitive_root(n, N - 1, N)
->N=17
->w=9

Используя эти параметры, в соответствии с алгоритмом, описанным в статье, я рассчитал Φ=3 поскольку Φ^2≡w mod (2*n) где w - примитивный корень n-й степени из единицы.

после этого я умножил каждый элемент полинома x[i]Φ^i

      for i in range(0,n):
    x[i]=x[i]*(pow(phi,i))%p
    y[i]=y[i]*(pow(phi,i))%p
->x=[ 15 14 2 7 1 5 9 4 ]
->y=[ 1 3 7 5 8 7 1 14 ]

выполнил NTT

      nttx=np.array(transform(x, w, N))
ntty=np.array(transform(y, w, N))
->nttx=[ 1 5 10 12 15 13 10 12 ]
->ntty=[ 1 5 10 12 15 13 10 12 ]

поэлементное умножение

      m=(nttx*ntty)%p
->m=[ 16 13 15 2 1 3 16 4 ]

обратный NTT

      m_inv=inverse_transform(m,w,N)
m_inv=[ 8 13 10 1 11 10 6 13 ]

а затем умножил каждый элемент на Φ^(-i)

      for i in range (0,n):
   mul_res[i]=(m_inv[i]*phi_inv_table[i])%p
->mul_res=[10 2 2 4 13 3 2 13]

Однако этот результат не соответствует результатам numpy. Я придерживался этого несколько дней, и я очень ценю вашу помощь.

Я также прикрепил сюда части кода и алгоритма

      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 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):
            print("k="+str(i))
            return n

Ссылка: DD Chen et al., «High-Speed ​​Polynomial Multiplication Architecture for Ring-LWE and SHE Cryptosystems», в IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 62, нет. 1, стр. 157-166, январь 2015 г., DOI: 10.1109 / TCSI.2014.2350431.