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] RSA - Ước chung lớn nhất

    RSA - Ước chung lớn nhất

    Để chọn số mũ công khai (e) hợp lệ, ta cần (\gcd(e, \varphi(n)) = 1).

    Cho hai số nguyên dương (a) và (b), hãy tính (\gcd(a, b)) bằng thuật toán Euclid:

    gcd⁡(a,b)=gcd⁡(b,a mod b),gcd⁡(a,0)=a\gcd(a, b) = \gcd(b, a \bmod b), \quad \gcd(a, 0) = agcd(a,b)=gcd(b,amodb),gcd(a,0)=a

    Ví dụ

    Input:

    20 7

    Output:

    1

    Vì (\gcd(20, 7) = 1).

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

      Một dòng gồm hai số nguyên dương (a) và (b).

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

      (1 \le a, b \le 10^{18})

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

      In ra (\gcd(a, b)).

    Ví dụ:

    Đầu vào:

    20 7

    Đầu ra:

    1

    Giải thích:

    gcd(20,7)=1 nên e=7 hợp lệ với phi=20

    Đang tải editor...