Изменение коэффициентов по модулю p в полиноме SymPy - PullRequest
Новая
       63

Изменение коэффициентов по модулю p в полиноме SymPy

0 голосов
/ 13 декабря 2018

В этом семестре в аспирантуре я проходил курс криптографии, и одной из тем, которые мы затронули, был NTRU.Я пытаюсь закодировать это на чистом Python, просто как хобби.Когда я пытаюсь найти обратный полином по модулю p (в данном примере p = 3), SymPy всегда возвращает отрицательные коэффициенты, когда я хочу строго положительные коэффициенты.Вот код, который у меня есть.Я объясню, что я имею в виду. 

import sympy as sym
from sympy import GF

def make_poly(N,coeffs):
    """Create a polynomial in x."""
    x = sym.Symbol('x')
    coeffs = list(reversed(coeffs))
    y = 0
    for i in range(N):
        y += (x**i)*coeffs[i]
    y = sym.poly(y)
    return y

N = 7
p = 3
q = 41
f = [1,0,-1,1,1,0,-1]

f_poly = make_poly(N,f)

x = sym.Symbol('x')

Fp = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(p))
Fq = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(q))

print('\nf =',f_poly)
print('\nFp =',Fp)
print('\nFq =',Fq)

В этом коде f_poly - это многочлен со степенью не более 6 (его степень не более N-1), чьи коэффициенты взяты из списка f (первая запись в f - это коэффициент наивысшей степени x, продолжающийся в порядке убывания).

Теперь я хочу найти обратный полином f_poly в сверткекольцо полиномов Rp = (Z/pZ)[x]/(x^N - 1)(Z/pZ)[x] (аналогично для q).Ниже приводятся операторы печати: 

f = Poly(x**6 - x**4 + x**3 + x**2 - 1, x, domain='ZZ')
Fp = Poly(x**6 - x**5 + x**3 + x**2 + x + 1, x, modulus=3)
Fq = Poly(8*x**6 - 15*x**5 - 10*x**4 - 20*x**3 - x**2 + 2*x - 4, x, modulus=41)

Эти многочлены являются правильными по модулю, но я хотел бы, чтобы везде были положительные коэффициенты, так как позже в алгоритме используется некоторая центральная атлетика, поэтомуМне нужно иметь положительные коэффициенты.Результаты должны быть 

Fp = x^6 + 2x^5 + x^3 + x^2 + x + 1
Fq = 8x^6 + 26x^5 + 31x^4 + 21x^3 + 40x^2 + 2x + 37

Ответы, которые я получаю, являются правильными по модулю, но я думаю, что invert в SymPy меняет некоторые коэффициенты на отрицательные варианты вместо того, чтобы оставаться внутри мода.

Можно ли как-нибудь обновить коэффициенты этого многочлена, чтобы иметь только положительные коэффициенты в модуле, или это просто артефакт функции SymPy?Я хочу сохранить формат SymPy Poly, чтобы в дальнейшем я мог использовать некоторые из его встроенных функций.Любое понимание будет высоко ценится!

1 Ответ

0 голосов
/ 13 декабря 2018

Это, похоже, объясняется тем, как объект конечного поля, реализованный в GF, "оборачивает" целые числа вокруг заданного модуля.Поведение по умолчанию - symmetric, что означает, что любое целое число x, для которого x % modulo <= modulo//2 отображается на x % modulo, а в противном случае - на (x % modulo) - modulo.Так что GF(10)(5) == 5, тогда как GF(10)(6) == -4.Вы можете сделать так, чтобы GF всегда отображалось на положительные числа, передав аргумент symmetric=False: 

import sympy as sym
from sympy import GF

def make_poly(N, coeffs):
    """Create a polynomial in x."""
    x = sym.Symbol('x')
    coeffs = list(reversed(coeffs))
    y = 0
    for i in range(N):
        y += (x**i)*coeffs[i]
    y = sym.poly(y)
    return y

N = 7
p = 3
q = 41
f = [1,0,-1,1,1,0,-1]

f_poly = make_poly(N,f)

x = sym.Symbol('x')

Fp = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(p, symmetric=False))
Fq = sym.polys.polytools.invert(f_poly,x**N-1,domain=GF(q, symmetric=False))

print('\nf =',f_poly)
print('\nFp =',Fp)
print('\nFq =',Fq)

Теперь вы получите нужные полиномы: 

f = Poly(x**6 - x**4 + x**3 + x**2 - 1, x, domain='ZZ')
Fp = Poly(x**6 + 2*x**5 + x**3 + x**2 + x + 1, x, modulus=3)
Fq = Poly(8*x**6 + 26*x**5 + 31*x**4 + 21*x**3 + 40*x**2 + 2*x + 37, x, modulus=41)

В основном какпримечание для моей справки, вот как вы можете получить Fp с помощью Mathematica: 

Fp = PolynomialMod[Algebra`PolynomialPowerMod`PolynomialPowerMod[x^6 - x^4 + x^3 + x^2 - 1, -1, x, x^7 - 1], 3]

вывод: 

1 + x + x^2 + x^3 + 2 x^5 + x^6
...