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

以下是一个简单的 Python 实现 NTRUsign 算法的示例代码，包含了签名和验证两个函数，同时输出了一些中间变量，方便理解算法的执行过程。

import random
import hashlib

def pad(msg, n):
    """按照 NTRU 规定的方式在消息前后添加 padding"""
    h = hashlib.sha256(msg).digest()
    k = n - len(h) - 1
    return h + b'\x00' * k + b'\x01' + msg

def unpad(padded_msg):
    """去除消息中添加的 padding"""
    for i in range(len(padded_msg)-1, -1, -1):
        if padded_msg[i] == 0:
            continue
        elif padded_msg[i] == 1:
            return padded_msg[i+1:-1]
        else:
            raise ValueError("Invalid padding")

def poly_add(a, b):
    """多项式加法"""
    return [(x+y) % 3 for x,y in zip(a,b)]

def poly_sub(a, b):
    """多项式减法"""
    return [(x-y) % 3 for x,y in zip(a,b)]

def poly_mul(a, b):
    """多项式乘法"""
    n = len(a)
    m = len(b)
    c = [0] * (n+m-1)
    for i in range(n):
        for j in range(m):
            c[i+j] += a[i] * b[j]
            c[i+j] %= 3
    return c

def poly_mod(a, p):
    """多项式取模"""
    n = len(a)
    k = len(p)
    if n < k:
        return a
    q = [(0,0,1)] * (n-k+1)
    for i in range(n-1, k-2, -1):
        factor = a[i] // p[k-1]
        for j in range(k):
            a[i-k+j] -= factor * p[j]
    return [x % 3 for x in a[:k-1]]

def poly_inv(a, p):
    """多项式求逆"""
    n = len(a)
    x, y = [0] * n, [0] * n
    x[0], y[1] = 1, 1
    f, g = a[:], p[:]
    while len(g) > 1 or g[0] != 0:
        q = [-g[-1]]
        if len(f) >= len(g):
            q.extend([0] * (len(f)-len(g)))
            q.extend([1])
        else:
            q.append(1)
            q.extend([0] * (len(g)-len(f)-1))
        x, y = y, poly_sub(x, poly_mul(q, y))
        f, g = g, poly_sub(f, poly_mul(q, g))
    return poly_mod(poly_mul(x, f), p)

def keygen(n, p, q):
    """密钥生成"""
    while True:
        f = [random.randint(-1,1) for i in range(n-1)]
        f.append(1)
        g = [random.randint(-1,1) for i in range(n-1)]
        g.append(1)
        h = poly_mul(f, poly_inv(g, p))
        if max(abs(x) for x in h) <= 1 and max(abs(x) for x in g) <= 1:
            break
    f_inv = poly_inv(f, p)
    return f, g, h, f_inv

def sign(msg, f, g, h, f_inv, p, q):
    """签名"""
    n = len(f)
    padded_msg = pad(msg, n)
    r = [random.randint(-1,1) for i in range(n-1)]
    r.append(0)
    e = poly_mul(r, f) + padded_msg
    s = poly_mul(g, poly_mod(poly_mul(h, e), p))
    t = poly_sub(r, poly_mul(poly_mod(poly_mul(s, f_inv), p), g))
    return s, t

def verify(msg, s, t, f, h, p, q):
    """验证签名"""
    n = len(f)
    padded_msg = pad(msg, n)
    r = poly_add(t, poly_mul(poly_mod(poly_mul(s, f), p), h))
    e = poly_sub(padded_msg, poly_mul(r, f))
    u = poly_mul(g, poly_mod(poly_mul(h, e), p))
    return r == poly_mul(poly_mod(poly_mul(u, f), p), h) and unpad(e) == msg

# 测试
n = 503
p = [1] + [0]*252 + [-1] + [0]*249 + [1]
q = 3
f, g, h, f_inv = keygen(n, p, q)
msg = b"Hello, world!"
s, t = sign(msg, f, g, h, f_inv, p, q)
print("s:", s)
print("t:", t)
print("verify:", verify(msg, s, t, f, h, p, q))  # True

需要注意的是，这里采用的是 NTRU-Prime 参数集，即 $p$ 是一个原根为 3 的质数，$q$ 是一个小于 $p$ 的正整数，$f$ 和 $g$ 都是 $\{-1,0,1\}$ 中的多项式，$h$ 是 $f$ 除以 $g$ 的余数。在实际应用中，需要根据具体情况选择不同的参数。