Which of the following statements are true? 1. Given a large modulus n, the exponential operation mod n is computationally difficult. 2. Given a large modulus n, the discrete logarithm problem is computationally difficult. 3. The discrete logarithm mod p always exists and is unique if p is a prime number. 4. Using the primitive roots of a prime modulus p yields the maximum p-1 possible outcome values for the discrete logarithm, which is desired for cryptography.

Đáp án đúng: "2 & 4". Phát biểu 2 đúng: với modulus lớn, bài toán logarit rời rạc (tìm x từ a^x mod n) là khó, nền của Diffie-Hellman. Phát biểu 4 đúng: căn nguyên thuỷ (primitive root) g của số nguyên tố p sinh ra đủ p − 1 giá trị khác nhau, ví dụ g = 3 mod 7 cho 3, 2, 6, 4, 5, 1, tức đủ 6 giá trị, nên logarit rời rạc theo g có nhiều kết quả nhất, điều mật mã cần. Phát biểu 1 sai: luỹ thừa modulo dễ tính bằng bình phương và nhân liên tiếp (square-and-multiply), ví dụ 3^4 mod 7 = (3^2)^2 mod 7 = 2^2 mod 7 = 4. Phát biểu 3 sai: với cơ số 2 mod 7, các luỹ thừa chỉ là 2, 4, 1 lặp lại, nên logarit của 3 không tồn tại, và 2^1 = 2^4 = 2 mod 7 nên cũng không duy nhất. Vì thế "1 & 2", "1 & 3", "1 & 4" đều chứa phát biểu 1 sai; "2 & 3" và "3 & 4" chứa phát biểu 3 sai.