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] Đếm khóa phiên hợp lệ cho chữ ký

    Bao nhiêu khóa phiên k hợp lệ?

    Trong chữ ký ElGamal, khóa phiên k phải thỏa 1 ≤ k ≤ p-2 và gcd(k, p-1) = 1. Số khóa hợp lệ chính là hàm Euler φ(p-1).

    Cho p, hãy tính φ(p-1).

    Ví dụ

    p = 23: p-1 = 22 = 2·11, φ(22) = 22·(1-1/2)·(1-1/11) = 10.

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

      Một số nguyên p.

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

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

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

      φ(p-1).

    Ví dụ:

    Đầu vào:

    23

    Đầu ra:

    10

    Giải thích:

    p-1=22=2*11, φ(22)=22*(1/2)*(10/11)=10.

    Đang tải editor...