NTRU note

\(N = 11\)
\(p = 3\)
\(q = 8\)

NTRU

Spec
只需要看 NTRU-HPS

擴展歐幾里得算法(Python)

def ext_euclid(a, b):
    old_s,s=1,0
    old_t,t=0,1
    old_r,r=a,b
    if b == 0:
        return 1, 0, a
    else:
        while(r!=0):
            q=old_r//r
            old_r,r=r,old_r-q*r
            old_s,s=s,old_s-q*s
            old_t,t=t,old_t-q*t
    return old_s, old_t, old_r

此函數得 a 模 b
\(a \equiv old_s\ \ mod\ \ b \\ if \ old_r = 1, \\ else \ not\ exist\)

Xilinx C

Xilinx Standalone Library Documentation