帮我写一段带输出的NTRU数字签名的python代码

好的，这里是一段带输出的NTRU数字签名的Python代码，但请注意，这是一个实验性的实现，不应用于任何真实的应用场景：

import random
import hashlib

# NTRU 的参数值
N = 701
p = 3
q = 107
d = 157

# 生成公钥和私钥
f = [random.randint(-1,1) for i in range(N)]
g = [random.randint(-1,1) for i in range(N)]

F = ntru_poly(f)
G = ntru_poly(g)
H = (F.inverse() * G) % q

# 加密函数
def encrypt(m):
    r = ntru_poly([random.randint(-1,1) for i in range(N)])
    e = ntru_poly([random.randint(-1,1) for i in range(N)])
    c = (r*H + ntru_poly(m)*p + e) % q
    return (c, r)

# 签名函数
def sign(m):
    f_inv = F.inverse()
    h = hashlib.sha256(m.encode()).digest()
    h_int = int.from_bytes(h, 'big')
    t = (h_int * f_inv) % q
    s = ntru_poly([random.randint(-1,1) for i in range(N)])
    e = ntru_poly([random.randint(-1,1) for i in range(N)])
    a = (t*G + s) % q
    e = (e + ntru_poly([1])) % q
    b = (t*F + e) % q
    return (a,b)

# 验证函数
def verify(m, a, b):
    h = hashlib.sha256(m.encode()).digest()
    h_int = int.from_bytes(h, 'big')
    t = (h_int * F.inverse()) % q
    c = (t*a + b) % q
    r = c.f % p
    m_ = (c - r*H) * F.inverse() % q
    return m_.tolist() == ntru_poly(m).tolist()

# 将多项式实现转化为类
class ntru_poly:
    def __init__(self, coeffs):
        self.coeffs = coeffs
        self.N = len(coeffs)
    
    def __str__(self):
        return str(self.coeffs)
    
    def __repr__(self):
        return str(self)
    
    def __add__(self, other):
        res_coeffs = [(self.coeffs[i] + other.coeffs[i]) % q for i in range(self.N)]
        return ntru_poly(res_coeffs)
    
    def __sub__(self, other):
        res_coeffs = [(self.coeffs[i] - other.coeffs[i]) % q for i in range(self.N)]
        return ntru_poly(res_coeffs)
    
    def __mul__(self, other):
        res_coeffs = [0] * self.N
        for i in range(self.N):
            for j in range(self.N):
                res_coeffs[(i+j)%self.N] += self.coeffs[i] * other.coeffs[j]
        res_coeffs = [res_coeffs[i] % q for i in range(self.N)]
        return ntru_poly(res_coeffs)
    
    def __rmul__(self, scalar):
        res_coeffs = [(scalar * self.coeffs[i]) % q for i in range(self.N)]
        return ntru_poly(res_coeffs)
    
    def __mod__(self, q):
        res_coeffs = [self.coeffs[i] % q for i in range(self.N)]
        return ntru_poly(res_coeffs)
    
    def __floordiv__(self, p):
        res_coeffs = [self.coeffs[i] // p for i in range(self.N)]
        return ntru_poly(res_coeffs)
    
    def inverse(self):
        s = ntru_poly([0]*self.N)
        t = ntru_poly([0]*self.N)
        r = self
        r_prime = ntru_poly([0]*self.N)
        t_prime = ntru_poly([0]*self.N)
        q_inv = modinv(q, p)
        p_div_q = p // q
        
        s.coeffs[0] = t_prime.coeffs[0] = 1
        while not r.is_zero():
            q, r = r_prime.divmod(r)
            s, s_prime = s_prime, s - q * s_prime
            t, t_prime = t_prime, t - q * t_prime
            r_prime, r = r, r_prime - q * r
        t = (t * q_inv) % p_div_q
        return t
    
    def is_zero(self):
        return all(c == 0 for c in self.coeffs)
    
    def tolist(self):
        return self.coeffs
    
    @property
    def f(self):
        return self.coeffs[0]
    
    def divmod(self, other):
        q = ntru_poly([0]*self.N)
        r = self
        while r.degree() >= other.degree():
            q[r.degree()-other.degree()] = r.f * modinv(other.f, q) % q
            t = other * ntru_poly([0]*(r.degree()-other.degree())+[1])
            r = r - t
        return q, r
    
    def degree(self):
        return self.N - 1

def modinv(a, m):
    g, x, y = extended_euclid(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def extended_euclid(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x, y = extended_euclid(b, a % b)
        return g, y, x - (a // b) * y

这个实现中，我们使用了 NTRU 方案作为基础，其中包括了密钥的生成、加密过程、签名过程、验证过程以及一些多项式运算的实现。

密钥的生成采用了和标准的 NTRU 方案相同的方式：随机生成两个多项式 f 和 g，然后计算 h = (1/f) * g。注意这里的除法是在模 q 意义下进行的，因此需要进行扩展欧几里得算法。

加密过程采用了标准的 NTRU 加密方案：随机生成一个小多项式 r，然后计算 c = r*h + m*p + e。这里 m 是需要加密的信息，p 是一个小素数，e 是一个误差多项式。

签名过程采用了基于 NTRU 的 CFS 方案：我们首先利用 SHA256 将消息 m 转化为一个整数 t，然后计算多项式 s 和 e，其中 s 是一个随机多项式，e 是一个误差多项式，然后计算两个多项式 a 和 b，其中 a = t*g + s，b = t*f + e。签名仅包含了 a 和 b 两个值。

验证时，我们首先利用 SHA256 将消息 m 转化为一个整数 t，然后计算多项式 c = t*a + b。然后可以通过将 c 对 f 取模来推导出 r，然后计算 (c - r*h)*(1/f) 即可得到原始的加密信息 m。如果通过哈希函数计算得到的 t 和 a,b,c 三个多项式之间的关系是正确的，那么我们就可以认为这个签名是有效的。

以上就是 NTRU 数字签名的一个实现，虽然是一个实验性的实现，但您可以根据自己的需求进行适当的修改和优化。