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] Baby-step Giant-step: phá khóa DH với modulus lớn

    Với ppp nhỏ, phép duyệt tuần tự (brute force) đủ để giải bài toán logarit rời rạc. Nhưng khi ppp lớn tới cỡ 101210^{12}1012, cách duyệt O(p)O(p)O(p) sẽ quá chậm; cần thuật toán Baby-step Giant-step (BSGS) chạy trong O(p)O(\sqrt{p})O(p​).

    Cho số nguyên tố ppp, cơ số ggg (1≤g≤p−11 \le g \le p-11≤g≤p−1) và giá trị hhh (0≤h≤p−10 \le h \le p-10≤h≤p−1), hãy tìm số nguyên xxx nhỏ nhất thỏa 0≤x≤p−20 \le x \le p-20≤x≤p−2 sao cho:

    gx mod p=hg^{x} \bmod p = hgxmodp=h

    Nếu không tồn tại xxx nào trong khoảng trên thỏa mãn, in ra −1-1−1.

    Ví dụ: p=23, g=5, h=8p=23,\ g=5,\ h=8p=23, g=5, h=8: đáp án là 666 vì 56 mod 23=85^{6} \bmod 23 = 856mod23=8.

    • Định dạng đầu vào:
      • Dòng đầu tiên chứa số nguyên TTT (1≤T≤51 \le T \le 51≤T≤5).
      • TTT dòng tiếp theo, mỗi dòng chứa ba số nguyên p g hp\ g\ hp g h, trong đó ppp là số nguyên tố (2≤p≤10122 \le p \le 10^{12}2≤p≤1012), 1≤g≤p−11 \le g \le p-11≤g≤p−1, 0≤h≤p−10 \le h \le p-10≤h≤p−1.
    • Định dạng đầu ra:

      In ra TTT dòng, dòng thứ iii là số nguyên xxx nhỏ nhất thỏa gx mod p=hg^{x} \bmod p = hgxmodp=h (0≤x≤p−20 \le x \le p-20≤x≤p−2), hoặc −1-1−1 nếu không tồn tại. Thuật toán duyệt tuần tự đơn giản sẽ không đủ nhanh với ppp lớn.

    Ví dụ:

    Đầu vào:

    1
23 5 8

    Đầu ra:

    6

    Đầu vào:

    1
7 3 1

    Đầu ra:

    0

    Đang tải editor...