用python语言实现带输出的NTRUsign算法，用到的函数都要自己编写

好的，以下是带输出的NTRUsign算法的python实现：

import random
from hashlib import sha256

def ntru_gen_params(q, n, p):
    """生成NTRU签名算法的参数"""
    while True:
        f = [random.randint(-(p-1)//2, (p-1)//2) for _ in range(n)]
        g = [random.randint(-(p-1)//2, (p-1)//2) for _ in range(n)]
        poly_f = Poly(f, n)
        poly_g = Poly(g, n)
        h = poly_f * poly_g % q
        if h.inv_mod_p(p) is not None:
            return f, g, h

def ntru_keygen(q, n, p):
    """NTRU签名算法的密钥生成过程"""
    f, g, h = ntru_gen_params(q, n, p)
    while True:
        s = [random.randint(-(p-1)//2, (p-1)//2) for _ in range(n)]
        poly_s = Poly(s, n)
        e = [random.randint(-(p-1)//2, (p-1)//2) for _ in range(n)]
        poly_e = Poly(e, n)
        v = (p * poly_s - poly_e) % q
        if v.inv_mod_p(p) is not None:
            break
    return f, g, h, v

def ntru_sign(m, f, g, h, v, q, p, d):
    """NTRU签名算法"""
    k = sha256(m.encode()).digest()
    k = [int.from_bytes(k[i:i+4], byteorder='big') for i in range(0, len(k), 4)]
    r = [random.randint(-(p-1)//2, (p-1)//2) for _ in range(n)]
    poly_r = Poly(r, n)
    e = [random.randint(-(p-1)//2, (p-1)//2) for _ in range(n)]
    poly_e = Poly(e, n)
    f_poly = Poly(f, n)
    h_poly = Poly(h, n)
    c = (f_poly * poly_r + p * poly_e) % q
    t = ((Poly(k, n) + d * c) * v) % q
    z = (t * h_poly.inv_mod_p(p)) % q
    return c, z

def ntru_verify(m, c, z, f, g, h, q, p, d):
    """NTRU签名算法的验证过程"""
    k = sha256(m.encode()).digest()
    k = [int.from_bytes(k[i:i+4], byteorder='big') for i in range(0, len(k), 4)]
    f_poly = Poly(f, n)
    h_poly = Poly(h, n)
    c_poly = Poly(c, n)
    t = ((Poly(k, n) + d * c_poly) * z.inv_mod_p(p)) % q
    u = (t * h_poly) % q
    r_prime = ((u - c_poly) * f_poly.inv_mod_p(p)) % q
    return r_prime.coeffs == r

class Poly:
    """多项式类"""
    def __init__(self, coeffs, n):
        self.coeffs = coeffs
        self.n = n
    
    def __add__(self, other):
        if isinstance(other, int):
            other = Poly([other], self.n)
        res_coeffs = [(self.coeffs[i] + other.coeffs[i]) % self.n for i in range(len(self.coeffs))]
        return Poly(res_coeffs, self.n)
    
    def __sub__(self, other):
        if isinstance(other, int):
            other = Poly([other], self.n)
        res_coeffs = [(self.coeffs[i] - other.coeffs[i]) % self.n for i in range(len(self.coeffs))]
        return Poly(res_coeffs, self.n)
    
    def __mul__(self, other):
        if isinstance(other, int):
            other = Poly([other], self.n)
        res_coeffs = [0] * (2 * self.n - 1)
        for i in range(len(self.coeffs)):
            for j in range(len(other.coeffs)):
                res_coeffs[i+j] += self.coeffs[i] * other.coeffs[j]
                res_coeffs[i+j] %= self.n
        while len(res_coeffs) > self.n:
            res_coeffs.pop()
        return Poly(res_coeffs, self.n)
    
    def inv_mod_p(self, p):
        """计算多项式在模p意义下的逆"""
        a = self.coeffs[:]
        b = [1] + [0] * (self.n - 1)
        c = [0] * self.n + [1]
        while True:
            while a[-1] == 0:
                a.pop()
            while b[-1] == 0:
                b.pop()
            while c[-1] == 0:
                c.pop()
            if len(a) == 1 and a[0] == 1:
                return Poly(b, self.n)
            f = a[-1]
            g = c[-1]
            if len(a) == len(b):
                f_inv = pow(f, p-2, p)
                a = [(a[i] * f_inv) % p for i in range(len(a))]
                b = [(b[i] * f_inv) % p for i in range(len(b))]
            elif len(b) > len(a):
                f_inv = pow(f, p-2, p)
                d = [(g * b[i]) % p for i in range(len(b)-len(a))]
                d += [(d[len(d)-1] + g*b[i+len(d)]) % p for i in range(len(a)-len(d)+1)]
                d = [(a[i] - d[i]) % p for i in range(len(a))]
                d = [(d[i] * f_inv) % p for i in range(len(d))]
                b = [(b[i] * f_inv) % p for i in range(len(b))]
                a, b = b, d
            else:
                f_inv = pow(g, p-2, p)
                d = [(f * a[i]) % p for i in range(len(a)-len(b))]
                d += [(d[len(d)-1] + f*a[i+len(d)]) % p for i in range(len(b)-len(d)+1)]
                d = [(b[i] - d[i]) % p for i in range(len(b))]
                d = [(d[i] * f_inv) % p for i in range(len(d))]
                c, b = b, d
    
    def __mod__(self, p):
        """多项式模p"""
        res_coeffs = [self.coeffs[i] % p for i in range(len(self.coeffs))]
        return Poly(res_coeffs, self.n)

其中，`ntru_gen_params`函数用于生成NTRU签名算法的参数，`ntru_keygen`函数用于生成NTRU签名算法的密钥，`ntru_sign`函数用于进行NTRU签名，`ntru_verify`函数用于验证NTRU签名。

`Poly`类实现了多项式的加减乘运算、逆元计算和模运算。在NTRU签名算法中，需要多次进行多项式的运算，因此实现一个多项式类可以方便地进行计算。

注意，在进行NTRU签名算法时，需要使用哈希函数对消息进行预处理，以保证签名的安全性。在代码中，我们使用了SHA256哈希函数进行预处理。另外，参数`d`用于对签名进行加密，可以使用随机数生成。