之前在RSA题目中遇到过的和phi不互素的问题，可以采用AMM开根算法来解决这个问题，来了解有限域上的AMM开根算法。

放一篇论文压一压：1111.4877.pdf (arxiv.org)

费马小定理

若$p$为素数，$gcd(a,p)=1$，则$a^{p-1}\equiv 1\;(mod\;p)$。

另一个形式：对于任意整数$a$，有$a^p\equiv a\;(mod\;p)$。

二次剩余（Quadraticresidue）

通俗来说，二次剩余可以认为是在取模意义下的开平方，即满足方程$x^2\equiv a(mod\;p)$的$x$的值。

一个数$a$，如果不是$p$的倍数，且模$p$同余于某个数的平方，则称$a$为模$p$的二次剩余。
一个数$b$，如果不是$p$的倍数，且模$p$不同余于任何数的平方，则称$b$为模$p$的二次非剩余。
一个数$c$，是$p$的倍数，那么容易得到$c\equiv 0(mod\;p)$，显然这个方程$x^2 \equiv c$的解仅有$x = 0$了。

一般这种问题只讨论$p$为奇数的情况

欧拉准则

$(\frac {a}{p}) \equiv a^{\frac {p-1}{2}} (mod p)$

勒让德符号（Legendre Symbol）

$L(a,p)=\left(\frac ap\right)=\left\{\begin{array}{cl}1,&\mbox{若 } a\mbox{ 是 } p \mbox{ 的二次剩余}\newline -1, &\mbox{若 }a \bmod p = 0\newline 0,&\mbox{若 } a\mbox{ 是 } p \mbox{ 的二次非剩余}\end{array}\right.$

性质

$\left(\frac{a}{p}\right)=\left(\frac{a\pm b}{p}\right)=\left(\frac{a\;modp}{p}\right)$ $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)*\left(\frac{b}{p}\right)$ $\left(\frac {-1}p\right)=\left\{\begin{array}{cl}1,& p \equiv 1 \pmod 4 \newline -1, & p \equiv 3 \pmod 4 \end{array}\right.\left(\frac {-1}p\right)=\left\{\begin{array}{cl}1,& p \equiv 1 \pmod 4 \newline -1, & p \equiv 3 \pmod 4 \end{array}\right.$ $\left(\frac 2p\right)=\left\{\begin{array}{cl}1,& p \equiv \pm 1 \pmod 8 \newline -1,& p \equiv \pm 3 \pmod 8 \end{array}\right.$ $\left(\cfrac pq\right)\left(\cfrac qp\right) = (-1)^{\frac{p-1}2{\frac{q-1}2}}$ $\sum\limits_{x=0}^{p-1}\left(\cfrac{ax+b}p\right)=0,p\nmid a$ $\sum\limits_{x=0}^{p-1}\left(\cfrac{ax^2+bx+c}p\right) = \left\{\begin{array}{cl}-\left(\cfrac ap\right),& p \nmid b^2-4ac \newline (p-1)\left(\cfrac ap\right), & p \mid b^2-4ac \end{array}\right.$

雅可比符号（Jacobi Symbol）

$J(a,p) = \left(\cfrac an\right)= \prod\limits_{i=1}^{m} \left(\cfrac a{p_i}\right)^{t_i},n = \prod\limits_{i=1}^{m} p_i^{t_i}$

性质

$\left(\cfrac an\right) = \left(\cfrac {a \pm n}n\right) = \left(\cfrac {a \bmod n}n\right)$ $\left(\cfrac {ab}n\right) = \left(\cfrac an\right)\left(\cfrac bn\right)$ $\left(\cfrac {-1}n\right)= (-1)^{\frac{n-1}2}$ $\left(\cfrac 2n\right)= (-1)^{\frac{n^2-1}8}$

详细性质等参考：初等数论(八): 二次剩余 - 知乎 (zhihu.com)

AMM算法

$m^e \equiv c\;mod\;p$

p在已知e下易分解得到s

$p-1 = e^t * s$

开二次方（e = 2）

欧拉准则：

$x^{\frac{p-1}{2}} = (x^s)^{e^{t-1}}$

二次剩余x：

$(x^s)^{2^{t-1}}\equiv 1\;mod\;p$

二次非剩余y：

$(y^s)^{2^{t-1}}\equiv-1\;mod\;p$

若$t=1$：

二次剩余的式子左右同时乘$x$，并开方

$x^{s+1}\equiv x\;mod\;p$ $x^{\frac{s+1}{2}}\equiv x^{\frac{1}{2}}\;mod\;p$

由条件$m^2\equiv c\;mod\;p$，代入c

$c^{\frac{x+1}{2}}\equiv m\;mod\;p$

即开方结果为

$c^{\frac{s+1}{2}}$

若$t\geq2$：

$\left(x^s\right)^{2^{(t-1)}}\equiv 1\;mod\;p$

对上式开根，有以下结果：

$\left(x^s\right)^{2^{(t-1)}}\equiv 1\;mod\;p$ $\left(x^s\right)^{2^{(t-2)}}\equiv 1\;mod\;p$ $\left(x^s\right)^{2^{(t-2)}}\equiv-1\;mod\;p$

我们不与要负根，所以配上一个二次非剩余

$\left(x^s\right)^{2^{(t-2)}}\equiv-1\;mod\;p$ $\left(y^s\right)^{2^{(t-1)}}\equiv -1\;mod\;p$ $\left(x^s\right)^{2^{(t-2)}}*(y^s)^{2^{(t-1)}*k}\equiv 1\;mod\;p$

当开出负根$k=1$，开出正根$k=0$，取决于下式：

$(x^s)^{2^{(t-i)}}mod\;p$

接下来重复上述操作，直到不能开二次方，即2的指数为0。

总计$t-1$个k

$(x^s)*(y^s)^{k_1+2*k_2+......+2^{t-2}*k_{t-1}}\equiv 1\;mod\;p$

然后左右同乘二次剩余x，开平方

$x^{\frac{s+1}{2}}*(y^s)^{k_1+2*k_2+......+2^{t-2}*k_{t-1}}\equiv x^{\frac{1}{2}}\;mod\;p$

import random
def amm2(x,p):
    #开二次方的代码
    #示例：2^2 = 4 mod 7  7-1 = 2 * 3 
    # 4 ^((3+1)/2) mod 7 = 2
    y = random.randint(1, p) 
    #生成二次非剩余
    #while y ** ((p-1) // 2) == 1:
    while pow(y, ((p-1) // 2), p) == 1:
        y = random.randint(1, p)
    #计算t s 
    t = 1
    s = 0
    while p % 2 == 0:
        t += 1
    s = p // (2**t)
    #计算a = y^s b = x^s h =1
    #h为二次非剩余部分的积
    a = pow(y, s, p)
    b = pow(x, s, p)
    h = 1
    #判断k值
    for i in range(1,t):
        tmp = 2**(t - 1 - i)
        d = pow(b, tmp, p)
        if d == 1 :
            k = 0
        else:
            k = 1
        b = b * pow(pow(a, 2, p), k, p)
        h = h * pow(a, k, p)
        a = pow(a, 2, p)
    return (pow(x,((s + 1) // 2),p) * h )% p
print(amm2(4,7))

开e次方

我们知道$m^e=c\;mod\;p$肯定有解，e次剩余x等同于c

由费马小定理得：

$x^{\frac{p-1}{e}}=(x^s)^{e^{t-1}}\equiv 1\;mod\;p$

e次非剩余

$y^{\frac{p-1}{e}}=(y^s)^{e^{t-1}}=?\;mod\;p$

考虑开e次方，类比开二次方，我们只需要对$x^{s+1}$开e次方即可

因此，需要找到一个值$\alpha$使得：$e\alpha-1=ks$

对e次剩余扩展，从$s$扩展到$ks$

$(x^{k*s})^{e^{t-1}}=1\;mod\;p$ $(x^{e*\alpha-1})^{e^{t-1}}=1\;mod\;p$

同理，不断对剩余开e次，但是现在开e次有e种选择,即1的r次根$(1,y_1,y_2…,y_{e-1})$

我们已知该类元素的e次方都为1，以及费马小定理

$(y_e)^e=1\;mod\;p$ $y^{p-1}=1\;mod\;p$

可以直接构造非二次剩余y的循环群

$(y_0,y_1...,y_{e-1})$ $\{1,(y^{\frac{p-1}{e}})^1,(y^{\frac{p-1}{e}})^2...,(y^{\frac{p-1}{e}})^{e-1}\}$ $((y^s)^{e^{t-1}})^i$

而对于$i\geq 1$有结论

$y_i*y_{e-1}=1$

只需要在每次开e次方的时候补上y即可

$x^{(e*\alpha-1)}*(y^s)^{k_1+2*k_2...+2^{t-2}*k_{t-1}}=1\;mod\;p$

同二次k值的获取来自开e次方的结果：

$(x^s)^{2^{t-i}}mod\;p$

对上面的值关于y取log即可得到是循环群里的第几个元素再取逆mod e

最后一步两边乘上x开e次根

$(x^{\alpha})*(y^s)^{k_1+2 * k_2 +...+2^{t-2}* k_{t-1}}*x=x^{\frac{1}{e}}\;mod\;p$

import random
import math
import libnum
import time
from Crypto.Util.number import bytes_to_long,long_to_bytes
p = 0
#设置模数
def GF(a):
    global p
    p = a
#乘法取模
def g(a,b):
    global p
    return pow(a,b,p)


def AMM(x,e,p):
    GF(p)
    y = random.randint(1, p-1)
    while g(y, (p-1)//e) == 1:
        y = random.randint(1, p-1)
        print(y)
    print("find")
    #p-1 = e^t*s
    t = 1
    s = 0
    while p % e == 0:
        t += 1
        print(t)
    s = p // (e**t)
    print('e',e)
    print('p',p)
    print('s',s)
    print('t',t)
    # s|ralpha-1
    k = 1    
    while((s * k + 1) % e != 0):
        k += 1
    alpha = (s * k + 1) // e
    #计算a = y^s b = x^s h =1
    #h为e次非剩余部分的积
    a = g(y, (e ** (t - 1) ) * s)
    b = g(x, e * alpha - 1)
    c = g(y, s)
    h = 1
    #
    for i in range(1, t-1):
        d = g(b,e**(t-1-i))
        if d == 1:
            j = 0
        else:
            j = (-math.log(d,a) % e)
        b = b * (g(g(c, e), j))
        h = h * g(c, j)
        c = g(c,e)
    return (g(x,alpha * h)) % p
print(AMM(4,2,7))