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] SVP: vét cạn vector ngắn nhất (bình phương chuẩn)

    Shortest Vector Problem (SVP) yêu cầu tìm vector khác 0 ngắn nhất trong lattice. Với lattice nhỏ, ta vét cạn mọi tổ hợp nguyên các vector cơ sở với hệ số trong [−C,C][-C, C][−C,C]:

    v=∑a=0k−1ca ba,ca∈{−C,…,C},  v≠0.v = \sum_{a=0}^{k-1} c_a\, b_a, \qquad c_a \in \{-C,\dots,C\}, \; v \ne 0.v=∑a=0k−1​ca​ba​,ca​∈{−C,…,C},v=0.

    Hãy in bình phương chuẩn Euclid nhỏ nhất min⁡∥v∥2\min \lVert v\rVert^2min∥v∥2.

    Ví dụ: cơ sở (2,0),(0,2)(2,0),(0,2)(2,0),(0,2), C=1C=1C=1: vector ngắn nhất khác 0 là (2,0)(2,0)(2,0) với ∥v∥2=4\lVert v\rVert^2=4∥v∥2=4.

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

      Dòng 1: k dim C. Tiếp theo k dòng, mỗi dòng dim số nguyên là một vector cơ sở.

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

      1≤k≤51 \le k \le 51≤k≤5; 1≤dim≤61 \le dim \le 61≤dim≤6; 1≤C≤41 \le C \le 41≤C≤4; toạ độ trong [−20,20][-20,20][−20,20].

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

      Một số nguyên: bình phương chuẩn Euclid nhỏ nhất của vector lattice khác 0.

    Ví dụ:

    Đầu vào:

    2 2 1
2 0
0 2

    Đầu ra:

    4

    Giải thích:

    Các vector khác 0: (±2,0),(0,±2),(±2,±2). Nhỏ nhất ‖v‖²=4.

    Đang tải editor...