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

好的，下面是用Python实现带输出的NTRUsign算法的代码：

import numpy as np
import random

def gen_key(n, p, q):
    # 生成私钥f和公钥h
    f = np.array([random.randint(-(p-1)//2, (p-1)//2) for i in range(n)])
    while True:
        g = np.array([random.randint(-(q-1)//2, (q-1)//2) for i in range(n)])
        if np.gcd(q, np.polyval(g, 1)) == 1:
            break
    h = np.polydiv(np.poly1d(np.concatenate(([1], f))), np.poly1d(np.concatenate(([1], g))))[1]
    return f, g, h

def sign(msg, f, g, h, p, q):
    # 签名
    while True:
        r = np.array([random.randint(-(q-1)//2, (q-1)//2) for i in range(len(h)-1)])
        e = np.array([random.randint(-(p-1)//2, (p-1)//2) for i in range(len(h)-1)])
        a = np.polyval(f, 1) * np.polyval(np.concatenate(([1], r)), 1) + np.polyval(e, 1) % p
        if np.gcd(q, a) == 1:
            break
    s = np.poly1d(np.concatenate(([1], r))) * np.polydiv(np.poly1d(np.concatenate(([1], f))), np.poly1d(np.concatenate(([1], g))))[1] % q
    hash_msg = hash(msg)
    z = np.polyval(h, hash_msg) * s + np.poly1d(np.concatenate(([1], e))) % q
    return z, a

def verify(msg, z, a, h, p, q):
    # 验证签名
    hash_msg = hash(msg)
    s = np.polydiv(z, np.polyval(h, hash_msg))[1] % q
    if np.gcd(q, a) != 1:
        return False
    if np.polyval(f, 1) * np.polyval(np.poly1d(np.concatenate(([1], s))), 1) != a % q:
        return False
    return True

# 测试
n = 7
p = 3
q = 257
msg = 'Hello, world!'
f, g, h = gen_key(n, p, q)
z, a = sign(msg, f, g, h, p, q)
print('Signature:', z)
print('Verification:', verify(msg, z, a, h, p, q))

其中，`gen_key`函数用于生成私钥f和公钥h，`sign`函数用于签名，`verify`函数用于验证签名。具体实现过程中，使用了numpy库进行多项式运算。在测试中，我们使用了n=7、p=3、q=257这些较小的参数来进行演示。