• AMM算法简要理解（Adleman-Mander-Miller Method）

    概念引入：

    全称为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} =奇数时）

    两边同乘a值和（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) 得证

     

  • 相关阅读:
    python学习框架
    使用 Supervisor 配置 Laravel 运行队列处理器
    [JS Framework] 当前运行的基座不包含原生插件[XXX]，请在manifest中配置该插件，重新制作包括该原生插件的自定义运行基座
    Google Gmail Oauth Client ID 认证指南
    【Hbase】第一章——从原理剖析
    发布博客到互联网
    Java--基本语法
    十几年Java“老油条”，教你如何才能把Java学好学透彻
    Go，从命名开始！Go的关键字和标识符全列表手册和代码示例！
    Dart 3.5 更新详解
  • 原文地址：https://blog.csdn.net/shshss64/article/details/127580256