AMM算法简要理解（Adleman-Mander-Miller Method）-EW帮帮网

概念引入：

全称为Adleman-Mander-Miller Method。在1977年他们发表的论文里只涉及了开平方根的方法，开n次方根并没有很详细的介绍。《Adleman-Manders-Miller Root Extraction Method Revisited》里三位中国人补充了他们开n次方根的方法。

可参考论文：AMM算法论文原稿

算法思路：

一、平方根（ $x^{2}$ ≡ a mod p）

即是我们常说的二次剩余定理的求解，在AMM算法中求解思路如下：

求解步骤如下：

1、由二次剩余定理成立条件可知， $a^{\tfrac{p-1}{2}} = 1 \left ( mod p\right )$ ——（1）成立；

2、我们可以找到一个q值满足 $q^{\tfrac{p-1}{2}} = -1 \left ( mod p\right )$ ——（2）；

3、将（1）中表达式开方即可求得 $a^{\tfrac{p-1}{4}} = 1or-1 \left ( mod p\right )$ ——（3）

=>由a^2 = 1 mod p ==> a = 1or-1 mod p推导可得

4、判断 $a^{\tfrac{p-1}{4}} = 1or-1 \left ( mod p\right )$ 等于1还是-1：（且 $\tfrac{p-1}{4} \neq$ 奇数时）

当等于1时：不做任何多余操作；

但等于-1时：将（3）式和（2）式相乘成为新的（3）式；

5、将（3）进行重复上式中的3和4操作，直到我们推导得（ $\frac{p-1}{4} =$ 奇数时）

两边同乘（2）式，并开方即是我们所需的x值。

二、n次方根（ $x^{r} = a \left ( modp \right )$ ）

1、我们可知费马小定理： $x^{p-1}=1\left ( modp \right )$ ——（1）

=> $a^{\frac{p-1}{r}}=1\left ( modp \right )$ => 代入 $x^{e} = a \left ( modp \right )$ ，将a用 $x^{r}$ 替换即可代换为（1）式；

2、我们可知AMM算法求解的情况为 r | （p-1）的情况，所以我们可以写出以下条件：

p-1 = r^t * s

3、找到一个q值使其满足 $q^{\frac{p-1}{r}}\neq 1\left ( modp \right )$ ——（2）

4、找到一个 $\alpha$ 值，使其满足 s | (r* $\alpha$ -1)，可推导得： $(a^{r*\alpha -1})^{r^{t-1}}=1\left ( modp \right )$ ——（3）

分类讨论：

（1）t=1时：

直接两边同乘a值，再对两边同时开r次方导，带入（1）式，即可求得x的值；

（2）t>=2时：

=>取（2）式可推导得： $Ki=(q^{s})^{i*r^{t-1}} and\left (K=(K1,K2,K3......Kr-1)) \right )$

其中K是对（3）式开r次方所有可能解的集合

当我们算Ki^r时，通过欧拉定理，我们可知Ki^r == 1 mod p

=>Ki * Kr-i = $((q^{s})^{i*r^{t-1}})*((q^{s})^{(r-i))*r^{t-1}})=(q^{s})^{r^{t}}$ ,通过欧拉定理可得Ki*Kr-i == 1 mod p

接下来，开始像第一个中解平方根的思路开始求解第二种情况：

1、对（3）式开r次方，得到 $((a^{r*\alpha -1})^{r^{t-2}})^{r}=1\left ( modp \right )$

2、可得到 $(a^{r*\alpha -1})^{r^{t-2}}=Kr-j$

两边同时乘以Kj可得 $(a^{r*\alpha -1})^{r^{t-2}}*Kr-j=1 (modp)$

即是 $(a^{r*\alpha -1})^{r^{t-2}}*(p^{s})^{j*r^{t-1}}=1 (modp)$

判断r^(t-j)是否为r，重复进行上述的1和2操作

3、当结束后，我们可得以下等式:

$(a^{r*\alpha -1})*(p^{s})^{j1*r^{1}+j2*r^{2}+j3*r^{3}+......+jt-1*r^{t-1}}=1 (modp)$

4、两边同时乘以a值，可得 $(a^{r*\alpha })*(p^{s})^{j1*r^{1}+j2*r^{2}+j3*r^{3}+......+jt-1*r^{t-1}}=a (modp)$

带入（1）式，对两边同时开r次方，我们可以求得我们所需的x值：

$x=(a^{\alpha })*(p^{s})^{j1*r^{1}+j2*r^{2}+j3*r^{3}+......+jt-1*r^{t-1}}(modp)$ 得证