Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] NTRU: nhân đa thức trong Z_q[x]/(x^N − 1)

    Trong hệ mật NTRU, các đa thức nhân trong vành Zq[x]/(xN−1)\mathbb{Z}_q[x]/(x^N-1)Zq​[x]/(xN−1) (tích chập vòng — cyclic convolution):

    hk=(∑a+b≡k  (mod N)fa gb) mod q.h_k = \Big(\sum_{a+b \equiv k \;(\mathrm{mod}\,N)} f_a\, g_b\Big) \bmod q.hk​=(∑a+b≡k(modN)​fa​gb​)modq.

    Do xN≡1x^N \equiv 1xN≡1, các số hạng bị "cuộn vòng" về chỉ số (a+b) mod N(a+b)\bmod N(a+b)modN.

    Ví dụ: N=3,q=7N=3,q=7N=3,q=7, f=1+xf=1+xf=1+x, g=1g=1g=1: h=1+x=(1,1,0)h = 1 + x = (1,1,0)h=1+x=(1,1,0).

    • Định dạng đầu vào:

      Dòng 1: N q. Dòng 2: N hệ số của f (bậc tăng dần). Dòng 3: N hệ số của g.

    • Ràng buộc đầu vào:

      1≤N≤2001 \le N \le 2001≤N≤200; 2≤q≤1092 \le q \le 10^92≤q≤109; hệ số nguyên trong [0,q)[0, q)[0,q).

    • Định dạng đầu ra:

      Một dòng gồm N số nguyên là hệ số của h trong khoảng [0, q).

    Ví dụ:

    Đầu vào:

    3 7
1 1 0
1 0 0

    Đầu ra:

    1 1 0

    Giải thích:

    g=1 nên h=f=(1,1,0).

    Đang tải editor...