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 số mũ bí mật d bằng Euclid mở rộng

    Cho p,qp, qp,q nguyên tố và số mũ công khai eee thỏa gcd⁡(e,φ(n))=1\gcd(e, \varphi(n)) = 1gcd(e,φ(n))=1 với n=pqn = pqn=pq, φ(n)=(p−1)(q−1)\varphi(n) = (p-1)(q-1)φ(n)=(p−1)(q−1). Số mũ bí mật ddd của RSA là số nguyên dương nhỏ nhất thỏa:

    e⋅d≡1(modφ(n))e \cdot d \equiv 1 \pmod{\varphi(n)}e⋅d≡1(modφ(n))

    Hãy tính ddd bằng thuật toán Euclid mở rộng (nghịch đảo modulo).

    Ví dụ: p=61p = 61p=61, q=53q = 53q=53, e=17e = 17e=17 ⇒φ(n)=3120\Rightarrow \varphi(n) = 3120⇒φ(n)=3120, và d=2753d = 2753d=2753 vì 17×2753=46801=15×3120+117 \times 2753 = 46801 = 15 \times 3120 + 117×2753=46801=15×3120+1.

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

      Một dòng gồm ba số nguyên p q ep\ q\ ep q e (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, 1<e<φ(n)1 < e < \varphi(n)1<e<φ(n), gcd⁡(e,φ(n))=1\gcd(e,\varphi(n))=1gcd(e,φ(n))=1).

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

      In ra một số nguyên duy nhất là giá trị ddd (số mũ bí mật), với 0<d<φ(n)0 < d < \varphi(n)0<d<φ(n).

    Ví dụ:

    Đầu vào:

    61 53 17

    Đầu ra:

    2753

    Đầu vào:

    7 11 13

    Đầu ra:

    37

    Đang tải editor...