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] Nghịch đảo modular

    Nghịch đảo modular

    Khi ký số ta thường cần nghịch đảo k−1 mod nk^{-1} \bmod nk−1modn (ElGamal/DSA).

    xxx là nghịch đảo của aaa theo modulo nnn nếu a⋅x≡1(modn)a \cdot x \equiv 1 \pmod{n}a⋅x≡1(modn).

    Thuật toán: Euclid mở rộng, hoặc pow(a, -1, n) (Python 3.8+). Nếu gcd⁡(a,n)≠1\gcd(a, n) \ne 1gcd(a,n)=1 thì không tồn tại, in -1.

    Ví dụ: 3−1 mod 11=43^{-1} \bmod 11 = 43−1mod11=4 vì 3⋅4=12≡13 \cdot 4 = 12 \equiv 13⋅4=12≡1.

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

      Một dòng gồm 2 số nguyên a n.

    • Ràng buộc đầu vào:
      • 1≤a<n1 \le a < n1≤a<n
      • 2≤n≤1092 \le n \le 10^{9}2≤n≤109
    • Định dạng đầu ra:

      Nghịch đảo trong [1,n−1][1, n-1][1,n−1], hoặc -1 nếu không tồn tại.

    Ví dụ:

    Đầu vào:

    3 11

    Đầu ra:

    4

    Giải thích:

    3*4=12 ≡ 1 (mod 11).

    Đang tải editor...