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] Định lý Euler

    Định lý Euler

    Định lý Euler khẳng định: nếu gcd⁡(a,n)=1\gcd(a,n)=1gcd(a,n)=1 thì:

    aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod naφ(n)≡1(modn)

    Đây là tổng quát hóa của Fermat nhỏ và là nền tảng giảm số mũ trong RSA.

    Cho aaa và nnn với gcd⁡(a,n)=1\gcd(a,n)=1gcd(a,n)=1. Hãy in giá trị aφ(n) mod na^{\varphi(n)}\bmod naφ(n)modn (luôn bằng 111, nhưng bạn phải tự tính φ(n)\varphi(n)φ(n) rồi lũy thừa để xác minh).

    Ví dụ

    a=3a=3a=3, n=10n=10n=10: φ(10)=4\varphi(10)=4φ(10)=4, 34=81≡1(mod10)3^4=81\equiv1\pmod{10}34=81≡1(mod10).

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

      Một dòng gồm hai số nguyên aaa, nnn với gcd⁡(a,n)=1\gcd(a,n)=1gcd(a,n)=1.

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

      2≤a<1092 \le a < 10^{9}2≤a<109, 2≤n≤10122 \le n \le 10^{12}2≤n≤1012, gcd⁡(a,n)=1\gcd(a,n)=1gcd(a,n)=1.

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

      Một số nguyên là aφ(n) mod na^{\varphi(n)}\bmod naφ(n)modn.

    Ví dụ:

    Đầu vào:

    3 10

    Đầu ra:

    1

    Giải thích:

    phi(10)=4, 3^4=81≡1 (mod 10).

    Đang tải editor...