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] Kiểm tra tính hợp lệ của số mũ công khai

    Trong RSA, sau khi tính n=pqn = pqn=pq và φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1)φ(n)=(p−1)(q−1), số mũ công khai eee chỉ được chấp nhận nếu thỏa đồng thời hai điều kiện:

    1. 1<e<φ(n)1 < e < \varphi(n)1<e<φ(n)
    2. gcd⁡(e,φ(n))=1\gcd(e, \varphi(n)) = 1gcd(e,φ(n))=1 (tức eee và φ(n)\varphi(n)φ(n) nguyên tố cùng nhau)

    Cho hai số nguyên tố p,qp, qp,q và một số nguyên eee, hãy xác định eee có phải là số mũ công khai hợp lệ hay không.

    Ví dụ: p=61p = 61p=61, q=53q = 53q=53 ⇒φ(n)=3120\Rightarrow \varphi(n) = 3120⇒φ(n)=3120. Với e=17e = 17e=17: 1<17<31201 < 17 < 31201<17<3120 và gcd⁡(17,3120)=1\gcd(17, 3120) = 1gcd(17,3120)=1, nên eee hợp lệ.

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

      Một dòng gồm ba số nguyên p q ep\ q\ ep q e cách nhau bởi khoảng trắng (2≤p,q≤1062 \le p, q \le 10^62≤p,q≤106, p,qp, qp,q nguyên tố, p≠qp \ne qp=q, 0≤e≤1070 \le e \le 10^70≤e≤107).

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

      In ra "YES" (không có dấu ngoặc) nếu eee hợp lệ, ngược lại in ra "NO".

    Ví dụ:

    Đầu vào:

    61 53 17

    Đầu ra:

    YES

    Đầu vào:

    61 53 3120

    Đầu ra:

    NO

    Đang tải editor...