Chia cho $2$ hoặc gốc chính với DH oracle

chúng ta có thể tìm thấy $g^t \bmod p$ trong thời gian đa thức?

Chúng ta có thể tìm thấy một trong hai $g^t$ hoặc $-g^{t} = g^{t + (p-1)/2}$; rõ ràng, chúng tôi không thể biết cái nào là cái nào đúng với thông tin chúng tôi đã cung cấp.

Bởi vì $p \equiv 3 \pmod 4$ (bởi vì $(p-1)/2$ được coi là số nguyên tố và lấy $p=5$ khỏi bàn - có thể được xử lý như một trường hợp đặc biệt), sau đó [1] chúng ta có thể tính căn bậc hai mô-đun bằng phép tính đơn giản $\sqrt{x} = \pm x^{(p+1)/4}$.

Vì vậy chúng tôi có $g^t \in\{ -(g^{2t})^{(p+1)/4},+(g^{2t})^{(p+1)/4}\}$, dễ dàng thực hiện được trong đa thời gian.

[1]: Nếu $p \equiv 1 \bmod 4$, thì việc tính toán căn bậc hai mô-đun vẫn thực tế, nó liên quan nhiều hơn một chút.