\(g^x\equiv a(mod\;p )\)
-
拆分\(p-1=\prod_{i=1}p_i^{ki}\)
-
对于每一个\(p_i\)进行处理
-
将\(x\)转化为\(p\)进制数 \(x=c_0+c_1p_i+c_2p_i^2+...+c_{k_i-1}p_i^{k_i-1}\)
-
\(g^{x( \frac{p-1}{p_i} )}\equiv a^{\frac{p-1}{p_i}}(mod\;p )\)
-
用1展开2中的x，发现从\(c_1p_i\)开始的每一项指数都是\(p-1\)的倍数，取余为1，可以扔掉
-
\(g^{c_0 \frac{p-1}{p_i} }\equiv a^{\frac{p-1}{p_i}}(mod\;p )\) 通过\(BSGS\)求出\(c_0\)
-
\(g^{x( \frac{p-1}{p_i^2} )}\equiv a^{\frac{p-1}{p_i^2}}(mod\;p )\)
-
同理得到\(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\)
-
...
-
-
\(CRT\)搞一下