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] Ring-LWE: nhân đa thức trong Z_q[x]/(x^n + 1)

    Ring-LWE làm việc trong vành Zq[x]/(xn+1)\mathbb{Z}_q[x]/(x^n+1)Zq​[x]/(xn+1) (tích chập âm — negacyclic). Vì xn≡−1x^n \equiv -1xn≡−1, khi a+b≥na+b \ge na+b≥n số hạng đổi dấu:

    hk=(∑a+b=kfagb  −  ∑a+b=k+nfagb) mod q.h_k = \Big(\sum_{a+b=k} f_a g_b \;-\; \sum_{a+b=k+n} f_a g_b\Big) \bmod q.hk​=(∑a+b=k​fa​gb​−∑a+b=k+n​fa​gb​)modq.

    Ví dụ: n=2,q=5n=2,q=5n=2,q=5, f=(0,1)=xf=(0,1)=xf=(0,1)=x, g=(0,1)=xg=(0,1)=xg=(0,1)=x: x⋅x=x2≡−1x\cdot x = x^2 \equiv -1x⋅x=x2≡−1, nên h=(−1,0)≡(4,0)h=(-1,0)\equiv(4,0)h=(−1,0)≡(4,0).

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

      Dòng 1: n q. Dòng 2: n hệ số của f. 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.

    • Đị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:

    2 5
1 0
0 1

    Đầu ra:

    0 1

    Giải thích:

    1·x = x, không cuộn vòng ⇒ h=(0,1).

    Đang tải editor...