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

首先，需要理解NTRUsign算法的原理和流程。NTRUsign算法是一种基于格的密码学算法，用于数字签名。它的主要思想是利用格结构中的难解问题来实现签名和验证的过程。

以下是一个简单的带输出的NTRUsign算法的实现，使用Python语言编写：

import numpy as np
from sympy import Matrix

# 定义NTRU参数
N = 503
p = 3
q = 32

# 生成NTRU公钥和私钥

def generate_keys():
    # 生成随机多项式f、g、h
    f = np.random.randint(low=-1, high=2, size=N)
    g = np.random.randint(low=-1, high=2, size=N)
    h = np.random.randint(low=-1, high=2, size=N)

    # 计算f的逆多项式f_inv
    f_inv = np.zeros(N)
    f_inv[0] = 1
    for i in range(N-2, -1, -1):
        f_inv[i+1] = -f_inv[i] * f[i+1] % p
    f_inv[0] = -f_inv[0] % p

    # 计算矩阵A、B、C
    A = np.zeros((N, N))
    B = np.zeros((N, N))
    C = np.zeros((N, N))
    for i in range(N):
        for j in range(N):
            A[i][j] = pow(p, q-1, q) * f[i] * f_inv[j] % q
            B[i][j] = pow(p, q-1, q) * g[i] * f_inv[j] % q
            C[i][j] = pow(p, q-1, q) * h[i] * f_inv[j] % q

    # 计算公钥和私钥
    public_key = (Matrix(A) * Matrix(B) % q).applyfunc(lambda x: x % 3 - 1)
    private_key = (f, g, h, f_inv)

    return public_key, private_key

# 签名函数

def sign(message, private_key):
    f, g, h, f_inv = private_key

    # 随机选择r
    r = np.random.randint(low=-1, high=2, size=N)

    # 计算多项式e、s、t、u
    e = (Matrix(message) - Matrix(g) * Matrix(r) % q).applyfunc(lambda x: x % 3 - 1)
    s = (Matrix(f) * Matrix(r) % q).applyfunc(lambda x: x % 3 - 1)
    t = (Matrix(h) * Matrix(r) % q).applyfunc(lambda x: x % 3 - 1)
    u = (Matrix(e) * Matrix(f_inv) % q).applyfunc(lambda x: x % 3 - 1)

    # 将多项式s、t、u转换为向量形式
    s_vec = np.array(s.tolist()[0])
    t_vec = np.array(t.tolist()[0])
    u_vec = np.array(u.tolist()[0])

    # 计算签名
    signature = (s_vec + t_vec + u_vec) % 3 - 1

    # 输出签名和多项式e
    return signature.tolist(), e.tolist()[0]

# 验证函数

def verify(message, signature, public_key):
    A = np.array(public_key.tolist())

    # 将签名转换为向量形式
    signature_vec = np.array(signature)

    # 计算多项式v、w
    v = (Matrix(A) * Matrix(signature_vec).transpose() % q).transpose().applyfunc(lambda x: x % 3 - 1)
    w = (Matrix(message) - Matrix(v) % q).applyfunc(lambda x: x % 3 - 1)

    # 检查是否匹配
    if (w == np.zeros(N)).all():
        return True
    else:
        return False

使用示例：

# 生成公钥和私钥
public_key, private_key = generate_keys()

# 签名
message = np.random.randint(low=-1, high=2, size=N)
signature, e = sign(message, private_key)

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

需要注意的是，这个实现只是一个简单的示例，可能存在安全性问题，不应该用于生产环境。如果需要使用NTRUsign算法进行签名，应该使用经过严格测试和评估的成熟库或实现。