refere：1111.4877.pdf (arxiv.org)
AMM平方根提取算法可以被拓展到一般的\(r^{th}\)根提取问题上，并且要求
\(r\mid p -1，(m, r)=1\)
AMM算法的核心观点暨在有限域\(F_p\)上开2次方的方法
AMM在有限域\(F_p\)中开平方根，这要求\(p\)是一个素数，那么\(p\)就可以写成\(2^t\cdot s\)的形式，其中\(s\)是奇数。对于一个二次剩余\(\delta\)和二次非剩余\(\rho\)，我们有
\[(\delta^{s})^{2^{t - 1}}\equiv1\pmod{p}，(\rho^{s})^{2^{t - 1}}\equiv-1\pmod{p} \]如果\(t=1\)，\(\delta^{s}\equiv1\pmod{p}\)，两边乘\(\delta\)得到
\[(\delta^{\frac{s+1}{2}})^{2} \equiv \delta \pmod{p} \]所以\(\delta^{\frac{s+1}{2}}\)就是一个根。
当\(t\geq 2\)，那么 \((δ^s)^{2^{t−2}} (mod p)\in \{ 1, −1\}\)（虽然在是不知道这是为什么，可能是将他当成一个新的二次（非）剩余），引入\(k_1=\{0, 1\}\)，表示成
\[(\delta^s)^{2^{t-2}}(\rho^s)^{2^{t-1}\cdot k_1}\equiv1\pmod{p} \]当 \((δ^s)^{2^{t−2}} \equiv1(mod p)\)，\(k_1=0\)，\(k_1=1\)
然后我们继续对上面的式子开方， \((δ^s)^{2^{t−3}}(\rho^s)^{2^{t-2}\cdot k_1} \pmod{p}\in \{ 1, −1\}\)，并引入\(k_2\)
\[(\delta^s)^{2^{t-3}}(\rho^s)^{2^{t-2}\cdot k_1}(\rho^s)^{2^{t-1}\cdot k_2}\equiv1\pmod{p} \]一直这样下去得到
\[(\delta^s)(\rho^s)^{2k_1+2^2k_2+\cdots+2^{t-1}k_{t-1}}\equiv1\pmod{p} \]因此我们有
\[(\delta^{\frac{s+1}{2}})^2[(\rho^s)^{k_1+2k_2+\cdots+2^{t-2}k_{t-1}}]^2\equiv \delta \pmod{p} \]算法的过程
Example:
AMM算法在\(F_{p^m}\)上开2次方
AMM方法在\(F_p\)和\(F_{p^m}\)上的不同在于，不能通过勒让德符号来判断一个二次非剩余
令\(q=p^m\)，需要找到一个二次非剩余\(\rho\)，就要求\(\rho^{\frac{q-1}{2}}\neq1\)，如何去找呢，只要在\(F^*_{p^m}\)中随机取值验证就行了。
算法过程和上面的差不多
AMM开3次方
差不多就是把2变成3
直接贴算法过程吧
AMM开\(r^{th}\)方法
对于一般情况的等式\(X^r=\delta\)在有限域\(F_q\)中，分为两种情况
\[(1)(r, q - 1) = 1;\quad (2)r\mid {q-1} \]对第一种情况，就是RSA了，求出\(rd\equiv1\pmod{q}\)，\(\delta^d\equiv X\pmod{q}\)
所以只要充分考虑第二种情况即可。