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

NTRUSign算法是基于NTRU加密算法的一种数字签名算法，其具体实现可以分为以下几个步骤：

1. 生成公私钥对
2. 对消息进行哈希操作
3. 使用私钥对哈希值进行加密得到签名
4. 使用公钥对签名进行解密得到哈希值
5. 对比解密得到的哈希值和原哈希值是否相等，若相等则验证成功

具体代码实现如下：

import random
import hashlib

N = 107  # 阶数
q = 2**8  # 模数
p = 3  # 多项式系数

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def poly_add(a, b):
    c = [0] * N
    for i in range(N):
        c[i] = (a[i] + b[i]) % q
    return c

def poly_sub(a, b):
    c = [0] * N
    for i in range(N):
        c[i] = (a[i] - b[i]) % q
    return c

def poly_mul(a, b):
    c = [0] * N
    for i in range(N):
        for j in range(N):
            c[(i+j) % N] += a[i] * b[j]
    for i in range(N):
        c[i] = (c[i] % q + q) % q
    return c

def poly_mod(a):
    c = [0] * N
    for i in range(N):
        c[i] = a[i] % p
    return c

def poly_inv(a):
    b = [0] * N
    c = [0] * N
    b[0] = a[0]
    c[1] = 1
    for i in range(1, N):
        for j in range(i):
            c[N-i+j] -= b[N-j-1] * c[N-i+j-1]
        b[i] = -c[N-i]
    return poly_mod(c)

def gen_keys():
    f = [0] * N
    while True:
        while True:
            for i in range(N):
                f[i] = random.randint(-(q-1), q-1)
            if f[0] != 0:
                break
        G = poly_inv(f)
        if gcd(G[0], p) == 1:
            break
    return f, G

def hash_msg(msg):
    h = hashlib.sha256()
    h.update(msg.encode('utf-8'))
    return int.from_bytes(h.digest(), 'big') % q

def encrypt(f, msg_hash):
    r = [0] * N
    e = [0] * N
    while True:
        for i in range(N):
            r[i] = random.randint(-(q-1), q-1)
        if gcd(poly_mul(f, r)[0], p) == 1:
            break
    e = poly_mul(f, r)
    for i in range(N):
        e[i] = (e[i] - msg_hash) % q
    return e

def decrypt(G, e):
    r = poly_mul(G, e)
    for i in range(N):
        r[i] = (r[i] % q + q) % q
    return r

def verify(f, msg_hash, r):
    e = poly_mul(f, r)
    for i in range(N):
        e[i] = (e[i] - msg_hash) % q
    return sum([abs(e[i]) for i in range(N)]) <= q // 2

# 测试样例
msg = "Hello world"
msg_hash = hash_msg(msg)
f, G = gen_keys()
e = encrypt(f, msg_hash)
r = decrypt(G, e)
print("Verify:", verify(f, msg_hash, r))

注：由于NTRU算法的特殊性质，这里的多项式系数p不能为2，否则会出现无解的情况。