Nếu g có bậc d nhỏ (d ước của p-1), thì A = g^a chỉ phụ thuộc a mod d. Kẻ tấn công có thể tìm a mod d bằng cách thử toàn bộ d giá trị.
Cho p, g, A với g có bậc d ≤ 10^6, hãy in d và a mod d (số mũ nhỏ nhất e trong [0, d-1] sao cho g^e ≡ A). Nếu A không thuộc nhóm con, in -1.
p=23, g=2, A=4: bậc của 2 là 11; 2^2 mod 23 = 4 → in 11 2.
Ba số nguyên p g A.
p nguyên tố, 2 ≤ p ≤ 10^9, 1 ≤ g,A < p, bậc của g ≤ 10^6.
Hai số d e (bậc và số mũ), hoặc -1.
Ví dụ:
Đầu vào:
23 2 4
Đầu ra:
11 2
Giải thích:
Đang tải editor...