Adleman-Manders-Miller算法

1.简介

原始的AMM算法主要关注于二次剩余问题。后来，提出了一个针对有限域F_q^m上的r次剩余求解问题的新算法（简称BV算法）

2.作用

常用于e和phi_n不互素的情况

3.数学原理

Ⅰ.二次剩余

$$m^2 \equiv c \pmod{p}，记p=2^t \cdot {s}，由Euler准则：$$

$$对于二次剩余：x^{(p-1)/2} \equiv 1 \pmod p,即x^{2^{(t-1)} \cdot {s}} \equiv 1 \pmod p$$

$$对于二次非剩余：y^{(p-1)/2} \equiv -1 \pmod p,即y^{2^{(t-1)} \cdot {s}} \equiv -1 \pmod p$$

(1)当t=1时

$$x^s \equiv 1 \pmod p,两边同时乘x再开方得：x^{(s+1)/2} \equiv x^{1/2} \pmod p$$

$$将c代入：c^{(s+1)/2} \equiv c^{1/2} \pmod p$$

$$故m \equiv c^{1/2} \equiv c^{(s+1)/2} \pmod p$$

(2)当t>1时

$$若直接开方：x^{2^{t-2} \cdot {s}} \equiv 1或-1 \pmod p, -1时不满足$$

$$考虑给负根配一个二次非剩余y，x^{2^{t-2} \cdot {s}} \cdot y^{2^{t-1} \cdot {s} \cdot k}\equiv 1 \pmod p$$

$$对于k：若x^{2^{t-2} \cdot {s}} \equiv 1 \pmod p，则k=0；若x^{2^{t-2} \cdot {s}} \equiv -1 \pmod p，则k=1$$

$$不断开根使得x的幂次中不再有2:x^s \cdot y^{s(2k_1 + 2^2k_2 + \cdots + 2^{t-2}k_{t-2})} \equiv 1 \pmod{p}$$

$$两边同乘s再开根并将c代入：m \equiv c^{1/2} \equiv c^{(s+1)/2} \cdot y^{s(k_1 + 2k_2 + \cdots + 2^{t-3}k_{t-2})} \equiv 1 \pmod{p}$$

（3）多个解

对于二次剩余，模p下应有两个解m和p-m

Ⅱ.e次剩余

$$m^e \equiv c \pmod{p}，记p-1=e^t \cdot {s}，由Euler准则：$$

$$由费马小定理：x^{p-1} \equiv 1 \pmod p,则有(m^e)^{(p-1)/e} \equiv c^{(p-1)/e} \equiv 1 \pmod p$$

$$找到的满足ed \equiv 1 \pmod p,则c^{(p-1)/e} \equiv (c^s)^{e^{(t-1)}} \equiv 1 \pmod p$$

$$(c^{ed-1})^{e^{(t-1)}} \equiv (c^{ks})^{e^{(t-1)}} \equiv 1^k \equiv 1 \pmod p$$

(1)当t=1时

$$c^{ed-1} \equiv 1 \pmod p,则c^{ed} \equiv {c} \pmod p$$

$$故m \equiv c^{1/e} \equiv c^d \pmod p$$

(2)当t>1时

涉及到循环群，等学了再来补充