关于原根

P4454 [CQOI2018] 破解D-H协议

个人理解,$g$ 是原根能唯一确定 $K$ 是因为离散指数方程解集模阶同余,$g$ 是原根,阶就是 $\varphi(P)$。根据扩展欧拉定理,解集内的解怎么降幂都是唯一确定的。如果不是原根,好像就,不太行。
by RyexAwl @ 2023-01-27 19:31:40


可以啊,解出来的 $a, b$ 是在模 $\operatorname{ord}_P(g)$ 意义下的,同时已知 $c \equiv a b \pmod{\operatorname{ord}_P(g)}$ 确定了唯一的 $K \equiv g^c \pmod{P}$
by 小粉兔 @ 2023-01-27 22:27:03


|