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] Kích thước khoá công khai LWE

    Trong hệ mật dựa trên LWE, khoá công khai gồm ma trận A∈Zqm×nA \in \mathbb{Z}_q^{m\times n}A∈Zqm×n​ và vector b∈Zqmb \in \mathbb{Z}_q^{m}b∈Zqm​. Mỗi phần tử thuộc Zq\mathbb{Z}_qZq​ cần

    bits=⌈log⁡2q⌉=(q−1).bit_length()\text{bits} = \lceil \log_2 q\rceil = (q-1).\text{bit\_length()}bits=⌈log2​q⌉=(q−1).bit_length()

    bit để lưu. Tổng số phần tử là m⋅n+mm\cdot n + mm⋅n+m. Hãy tính tổng số bit và số byte (=⌈tổng bit/8⌉=\lceil \text{tổng bit}/8\rceil=⌈tổng bit/8⌉) để lưu khoá công khai.

    Ví dụ: n=2,m=2,q=7n=2,m=2,q=7n=2,m=2,q=7: bits=3=3=3, số phần tử=6=6=6, tổng =18=18=18 bit =3=3=3 byte.

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

      Một dòng gồm ba số nguyên n m q.

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

      1≤n,m≤1041 \le n,m \le 10^41≤n,m≤104; 2≤q≤2302 \le q \le 2^{30}2≤q≤230.

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

      Một dòng gồm hai số nguyên: tổng số bit và số byte.

    Ví dụ:

    Đầu vào:

    2 2 7

    Đầu ra:

    18 3

    Giải thích:

    bits=(6).bit_length()=3; phần tử=2·2+2=6; tổng=18 bit; byte=ceil(18/8)=3.

    Đang tải editor...