用python语言实现带输出的NTRUsign算法，阶数N为107，用到的函数都要自己编写，并且要求输出密文、签名和密钥等参数

NTRUsign算法是一种基于NTRU密码系统的数字签名算法，其具体实现步骤如下：

1. 密钥生成阶段：

(1) 随机生成两个多项式$f,g\in R_q$，其中$q$为一个素数，$R_q=\mathbb{Z}_q[x]/(x^N-1)$为模$x^N-1$的整数环。

(2) 通过计算$f^{-1}\bmod\,3$，得到$f$的逆元$f^{-1}$。

(3) 计算$h=f^{-1}g\bmod\,3$，并将$h$转化为二进制形式。

(4) 随机生成一个偏移量$w\in\{0,1\}^N$，并将其转化为三进制形式。

(5) 返回公钥$(h,w)$和私钥$f$，其中$h,w$为公开参数，$f$为私有参数。

2. 签名生成阶段：

(1) 随机生成一个多项式$e\in R_q$。

(2) 计算多项式$t=ef+h\bmod\,3$，并将$t$转化为二进制形式。

(3) 将偏移量$w$和$t$进行异或运算，得到签名$s=t\oplus w$。

(4) 返回签名$s$。

3. 签名验证阶段：

(1) 将签名$s$转化为三进制形式，并将其与偏移量$w$进行异或运算，得到多项式$t=s\oplus w$。

(2) 计算多项式$v=ft\bmod\,3$，并将$v$转化为二进制形式。

(3) 如果$v=h$，则签名验证通过，否则签名验证失败。

下面是Python代码实现：

import random

N = 107
q = 3

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] * (2*N-1)
    for i in range(N):
        for j in range(N):
            c[i+j] += a[i] * b[j]
    for i in range(N, 2*N-1):
        c[i-N] -= c[i]
    return [c[i] % q for i in range(N)]

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

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

def poly_random():
    return [random.randint(0, q-1) for i in range(N)]

def poly_to_string(a):
    s = ''
    for i in range(N):
        s += str(a[i])
    return s

def string_to_poly(s):
    a = [0] * N
    for i in range(N):
        a[i] = int(s[i])
    return a

def key_generation():
    f = poly_random()
    while True:
        g = poly_random()
        h = poly_mod(poly_mul(poly_inv(f), g))
        if sum(h) > 0:
            break
    w = [random.randint(0, 1) for i in range(N)]
    h_str = poly_to_string(h)
    w_str = poly_to_string(w)
    f_str = poly_to_string(f)
    return (h_str, w_str), f_str

def sign_generation(message, public_key, private_key):
    h_str, w_str = public_key
    f_str = private_key
    e = poly_random()
    t = poly_mod(poly_add(poly_mul(e, string_to_poly(f_str)), string_to_poly(h_str)))
    t_str = poly_to_string(t)
    s_str = poly_to_string(poly_add(string_to_poly(t_str), string_to_poly(w_str)))
    return s_str

def sign_verification(message, signature, public_key):
    h_str, w_str = public_key
    t_str = poly_to_string(poly_sub(string_to_poly(signature), string_to_poly(w_str)))
    v_str = poly_to_string(poly_mod(poly_mul(string_to_poly(t_str), string_to_poly(f_str))))
    return v_str == h_str

其中，`poly_add`、`poly_sub`、`poly_mul`、`poly_inv`分别实现多项式的加、减、乘、求逆运算，`poly_mod`实现多项式模$q$运算，`poly_random`生成随机多项式，`poly_to_string`、`string_to_poly`实现多项式与字符串之间的转换，`key_generation`实现密钥生成，`sign_generation`实现签名生成，`sign_verification`实现签名验证。