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] Tìm căn nguyên thủy nhỏ nhất

    Căn nguyên thủy nhỏ nhất modulo p

    Phần tử sinh g tốt nhất là căn nguyên thủy modulo p: bậc của nó đúng bằng p-1, sinh ra toàn bộ nhóm. Cho p nguyên tố, hãy tìm căn nguyên thủy nhỏ nhất.

    g là căn nguyên thủy khi với mọi ước nguyên tố q của p-1, ta có g^{(p-1)/q} ≢ 1 (mod p).

    Ví dụ

    p = 7: thử g=2 (bậc 3, không), g=3 (sinh hết) → đáp án 3.

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

      Một số nguyên tố p.

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

      p nguyên tố, 3 ≤ p ≤ 10^9.

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

      Căn nguyên thủy nhỏ nhất modulo p.

    Ví dụ:

    Đầu vào:

    7

    Đầu ra:

    3

    Giải thích:

    2 có bậc 3; 3 sinh toàn nhóm Z_7* nên căn nguyên thủy nhỏ nhất là 3.

    Đang tải editor...