关于Pohlig-Hellmen算法喵

标签：1p frac Hellmen Pohlig 算法 原根时 equiv mod

\(g^x\equiv a(mod\;p )\)

当\(g\)为原根时

1. 拆分\(p-1=\prod_{i=1}p_i^{ki}\)

2. 对于每一个\(p_i\)进行处理

   1. 将\(x\)转化为\(p\)进制数 \(x=c_0+c_1p_i+c_2p_i^2+...+c_{k_i-1}p_i^{k_i-1}\)

   2. \(g^{x( \frac{p-1}{p_i} )}\equiv a^{\frac{p-1}{p_i}}(mod\;p )\)

   3. 用1展开2中的x，发现从\(c_1p_i\)开始的每一项指数都是\(p-1\)的倍数，取余为1，可以扔掉

   4. \(g^{c_0 \frac{p-1}{p_i} }\equiv a^{\frac{p-1}{p_i}}(mod\;p )\) 通过\(BSGS\)求出\(c_0\)

   5. \(g^{x( \frac{p-1}{p_i^2} )}\equiv a^{\frac{p-1}{p_i^2}}(mod\;p )\)

   6. 同理得到\(g^{c_1 \frac{p-1}{p_i^2} }\equiv a^{\frac{p-1}{p_i^2}} inv(g^{c_0 \frac{p-1}{p_i} })(mod\;p )\)通过\(BSGS\)求出\(c_1\)

   7. ...

3. \(CRT\)搞一下

当不为原根时

\[a^x\equiv b(mod\;p ) \]

\[ \left\{ \begin{matrix} a \equiv g^A (mod \; p) \\ b \equiv g^B (mod \; p) \end{matrix} \right. \]

\[g^{Ax}\equiv g^B(mod \;p) \]

\[Ax\equiv B(mod \; p-1) \]

\(exgcd\)搞一下

标签：1p,frac,Hellmen,Pohlig,算法,原根时,equiv,mod
From： https://www.cnblogs.com/Kuroniko/p/17728714.html