Bài tập | NEU OJ

Độ khó của bài toán logarit rời rạc là nền tảng an toàn của Diffie-Hellman và ElGamal: biết $a, b, p$ nhưng việc tìm $x$ sao cho $a^x \equiv b \pmod p$ là khó về mặt tính toán khi $p$ đủ lớn. Với $p$ nhỏ (tối đa $10^6$ ), ta có thể giải bằng thuật toán Baby-step Giant-step với độ phức tạp $O(\sqrt{p})$ .

Cho số nguyên tố $p$ và hai số nguyên $a, b$ với $0 < a, b < p$ . Hãy tìm số nguyên $x$ nhỏ nhất, $0 \le x \le p-2$ , sao cho $a^x \equiv b \pmod p$ . Nếu không tồn tại $x$ nào thỏa mãn, in ra $-1$ .

Định dạng đầu vào:
Một dòng duy nhất chứa ba số nguyên $p, a, b$ cách nhau bởi khoảng trắng ( $2 \le p < 10^6$ , $p$ là số nguyên tố, $0 < a, b < p$ ).
Định dạng đầu ra:
Một số nguyên duy nhất: giá trị $x$ nhỏ nhất thỏa $a^x \equiv b \pmod p$ , hoặc $-1$ nếu không tồn tại.

solution

Đề bài: [An toàn thông tin] Logarit rời rạc