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

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

import random
import hashlib

# NTRU parameters
N = 503
p = 3
q = 256
d = 130
B = 1

# generate random polynomial with coefficients in {-1,0,1}
def generate_poly():
    return [random.choice([-1,0,1]) for i in range(N)]

# compute the inverse of a modulo p
def inverse(a, p):
    t, newt = 0, 1
    r, newr = p, a

    while newr != 0:
        quotient = r // newr
        t, newt = newt, t - quotient * newt
        r, newr = newr, r - quotient * newr

    if r > 1:
        return None

    if t < 0:
        t += p

    return t

# compute the hash of a message
def hash_message(message):
    return hashlib.sha256(message.encode()).hexdigest()

# generate public and private keys
def generate_keys():
    while True:
        f = generate_poly()
        g = generate_poly()
        h = [(p * c) % q for c in f]

        if inverse(2*d, q) is None:
            continue

        a = [(p * c) % q for c in g]
        b = [((c * h[i]) // q) % p for i, c in enumerate(a)]
        c = [(a[i] - (b[i] * f[i])) % p for i in range(N)]

        if max(max(a), max(b), max(c)) <= B:
            break

    return (f, h), (g, c)

# sign a message
def sign(message, private_key):
    g, c = private_key
    r = generate_poly()
    e = [(p * c) % q for c in r]
    t = hash_message(message)
    m = int(t, 16)

    while True:
        h = generate_poly()
        a = [(p * c) % q for c in h]
        b = [((c * g[i]) // q) % p for i, c in enumerate(a)]
        s = [(r[i] + (m * b[i])) % q for i in range(N)]

        if max(s) <= d:
            break

    return e + s

# verify a signature
def verify(message, signature, public_key):
    f, h = public_key
    e = signature[:N]
    s = signature[N:]
    t = hash_message(message)
    m = int(t, 16)
    v = [(p * c) % q for c in s]
    a = [(p * c) % q for c in e]
    b = [((c * h[i]) // q) % p for i, c in enumerate(a)]
    c = [(v[i] - (m * b[i])) % q for i in range(N)]
    d = [(c[i] * inverse(f[i], p)) % p for i in range(N)]

    if max(max(a), max(b), max(c), max(d)) <= B:
        return True

    return False

# test the implementation
message = "hello world"
public_key, private_key = generate_keys()
signature = sign(message, private_key)

if verify(message, signature, public_key):
    print("Signature is valid")
else:
    print("Signature is invalid")

上述代码中，我们采用了NTRU签名算法的标准参数，其中：

- N：多项式的次数
- p：多项式系数的模数
- q：多项式系数的模数
- d：密钥参数，用于限制签名多项式的系数大小
- B：签名参数，用于限制签名向量的元素大小

首先，我们定义了生成随机多项式、计算模数的逆元、计算消息哈希值等辅助函数。然后，我们定义了生成公私钥、签名和验证的主要函数。在签名函数中，我们首先生成一个随机多项式r，然后计算e=rh mod q和s=r+mb mod q，其中h是从f和g生成的多项式，m是消息的哈希值。我们生成随机多项式h，并根据它计算a=hg mod q和b=⌊a/p⌋，然后检查s的系数是否小于等于d。如果是，则返回e和s作为签名。在验证函数中，我们首先从签名中提取e和s，然后计算v=s-hed mod q，a=e，b=⌊ah/p⌋，c=v/md mod q，d=cf^-1 mod p，最后检查a、b、c和d的系数是否都小于等于B。如果是，则返回True，否则返回False。

最后，我们使用这些函数来签名和验证一个消息。如果验证成功，则说明签名是有效的。