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] Cấp của phần tử modulo n

    Cấp (order) của một phần tử aaa modulo nnn, ký hiệu ordn(a)\text{ord}_n(a)ordn​(a), là số nguyên dương nhỏ nhất kkk sao cho ak≡1(modn)a^k \equiv 1 \pmod nak≡1(modn). Khái niệm này quyết định chu kỳ lặp lại của các dãy sinh bởi phép lũy thừa modulo, và liên quan trực tiếp đến việc chọn tham số an toàn cho Diffie-Hellman (căn nguyên thủy chính là phần tử có cấp φ(n)\varphi(n)φ(n)).

    Cho hai số nguyên n,an, an,a với gcd⁡(a,n)=1\gcd(a, n) = 1gcd(a,n)=1 (nên ordn(a)\text{ord}_n(a)ordn​(a) luôn tồn tại), hãy tính ordn(a)\text{ord}_n(a)ordn​(a).

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

      Một dòng duy nhất chứa hai số nguyên n,an, an,a cách nhau bởi khoảng trắng (2≤n≤1062 \le n \le 10^62≤n≤106, 1≤a<n1 \le a < n1≤a<n, gcd⁡(a,n)=1\gcd(a, n) = 1gcd(a,n)=1).

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

      Một số nguyên duy nhất - giá trị ordn(a)\text{ord}_n(a)ordn​(a).

    Ví dụ:

    Đầu vào:

    2 1

    Đầu ra:

    1

    Đầu vào:

    7 3

    Đầu ra:

    6

    Đang tải editor...