有限域开根学习（未完成）

reference

目标：$x^r \equiv s (modq)$求解x。(或者引用中出现δ=s)

主流方法：the Adleman-Manders-Miller algorithm 和 the Cipolla-Lehmer algorithms

下面是amm，思想是找到一个原根并化成离散对数的问题。

将q-1分解为r×t×s的形式，其中(r,s)=1。

找到一个r次非剩余ρ，即满足ρ^(q-1)/r ≠ 1 (mod q)的数。（n次剩余系下的勒让德符号）

找到一个最小的非负整数α，使得s|(r^α-1)。

计算(δ(rα-1))^(t-1) (mod q)，得到一个r次单位根K_r-j，即满足(K_r-j)^r ≡ 1 (mod q)的数。

通过求解离散对数问题，找到j∈{0,1,…,r-1}，使得K_r-j ≡ ρ^(j×s×t-1) (mod q)。

重复第4和第5步，直到找到所有的j_1,j_2,…,j_t-1∈{0,1,…,r-1}，使得(δ(rα-1))^(t-i) ≡ ρ^(j_i×s×t-i) (mod q)，对于i=2,3,…,t-1。

计算x = δ^α × ρ(j_1+j_2×r+…+j_t-1×r(t-2)) (mod q)，则x是方程的一个根。
如果要求解所有的根，可以利用一个循环群的生成元来找到其他的根。具体来说，如果g是F_q*的一个生成元，则x,gx,g2x,…,g(r-1)x就是方程的所有根。

如果要求解更一般的情况，即r|q-1的情况，则需要使用另一种方法。该方法使用一个二次非剩余和一系列平方根提取来找到一个根，然后使用循环群的生成元来找到其他的根。具体步骤如下：

将q-1分解为r×t×s的形式，其中s是奇数。

找到一个二次非剩余ρ，即满足ρ^(q-1)/2 ≠ 1 (mod q)的数。

计算(δs)((q-1)/2) (mod q)，如果结果不等于1，则δ不是一个r次剩余，无解；否则继续下一步。

计算(δs)((q-1)/4) (mod q)，得到一个平方根K_0或-K_0，即满足(K_0)^2 ≡ δ^s (mod q)的数。

重复第4步，直到找到所有的K_0,K_1,…,K_t-2，使得(K_i)^2 ≡ δ^s × ρ^(i×s) (mod q)，对于i=0,1,…,t-2。

计算x = K_0 × K_1 × … × K_t-2 × δ × ρ^(t/2) (mod q)，则x是方程的一个根。

这种方法的其中一个应用场景是做rsa题目的时候e与fn不互质。（知道pqec，e为fn的一个因子）

# -*- coding:utf8 -*-
import gmpy2
from libnum import  *
import random
import math
from scipy.special import cbrt
import time

def onemod(e,q):
    p=random.randint(1,q-1)
    while(pow(p,(q-1)//e,q)==1):#(r,s)=1
         p=random.randint(1,q)
    return p

def AMM_rth(o,r,q):# r|(q-1)
    print('start to calculate primitive root...')
    start=time.time()
    assert((q-1)%r==0)
    p=onemod(r,q)
    print('p:%d'%p)

    t=0
    s=q-1
    while(s%r==0):
        s=s//r
        t+=1
    k=1    
    while((s*k+1)%r!=0):
        k+=1
    alp=(s*k+1)//r
    
    print('s:%d,t:%d r:%d alp:%d'%(s,t,r,alp))
    a=pow(p,r**(t-1)*s,q)
    b=pow(o,r*a-1,q)
    c=pow(p,s,q)
    h=1
    
    for i in range(1,t-1):
        d=pow(int(b),r**(t-1-i),q)
        print('d:%d'%d)
        if d==1:
            j=0
        else:
            j=(-math.log(d,a))%r
        b=(b*(c**(r*j)))%q
        h=(h*c**j)%q
        c=(c*r)%q
    result=(pow(o,alp,q)*h)
    end=time.time()
    
    print('result:%d'%result)
    print('Finish in {} seconds'.format(end-start))
    return result
#2020.4.3 finish

        
def ALL_Solution(m,q,rt,cq,e):
    print('start to calculate all root...')
    start=time.time()
    mp=[]
    for pr in rt:
        r=(pr*m)%q
        assert(pow(r,e,q)==cq)
        mp.append(r)
    end=time.time()
    print('Finish in {} seconds'.format(end-start))
    return mp
       
def calc(mp,mq,e,p,q):
    print('satrting crt... ')
    i=1
    j=1
    start=time.time()
    t1=gmpy2.invert(q,p)
    t2=gmpy2.invert(p,q)
    for mp1 in mp: 
        if(j%1000==0):
            print(j)
        j+=1           
        for mq1 in mq:
            ans=(mp1*t1*q+mq1*t2*p)%(p*q)
            if check(ans):
                print('Finish in {} seconds'.format(time.time()-start))
                return 
                      
    return 
    
def check(m):
    global sta
    try:
        a=n2s(m)
        #print(a)
        if a.startswith(sta):
            print(a)
            return True
        else:
            return False
    except:
        return False


def ALL_ROOT2(r,q):#use function set() and .add() ensure that the generated elements are not repeated
    print('start to find all primitive root...')
    start=time.time()
    li=set()
    while(len(li)<r):
        p=pow(random.randint(1,q-1),(q-1)//r,q)
        li.add(p)
    end=time.time()
    print('Finish in {} seconds'.format(end-start))
    return li
    
        
if __name__=='__main__':
    c = 
    p = 
    q = 
    e = 
    sta = ''
    cp=c%p
    cq=c%q
    
    mp=AMM_rth(cp,e,p)
    mq=AMM_rth(cq,e,q)
    
    
    rt1=ALL_ROOT2(e,p)
    rt2=ALL_ROOT2(e,q)
         
    amp=ALL_Solution(mp,p,rt1,cp,e)
    amq=ALL_Solution(mq,q,rt2,cq,e)
       
    calc(amp, amq,e,p,q)

注意以上脚本理论上能跑但是可能有瑕疵。

同时如果指数有特殊的性质的话我们或许可以不经过爆破就解出其中以一个根。

$q\equiv 3(mod4)$则有其中一个根$x\equiv c^\frac{q+1}{4}(modq)$

证明：费马小定理加勒让德符号。
$q\equiv 5(mod8)$在对于二次剩余的根下有：

$$
1:b\equiv(2a)^\frac{q-5}{8}\
2:i=2ab^2\
3:x=ab(i-1)
$$

$q\equiv 9(mod16)$在同样是二次剩余的根下：

$$
1:b\equiv(2a)^\frac{q-5}{8}\
2：random .d. st. -b \equiv(\frac{a}{p}) \equiv a^{\frac{p-1}{2}}\
3:u\equiv (2ad^2)^\frac{q-9}{16}\
4:i\equiv 2u^2d^2a\
5:x\equiv uda(i-1)
$$

在有限域中 Fq 开 r^s 根 [ q ≡ lr^s + 1 (mod r^(s+1)) ]

下面还没看。

首先我们需要一个质数q，并且有一个r，满足 r | (q-1)，（如果r与q-1互质，那问题就很简单了，r的逆用欧拓很快就能找到）然后会存在一个s，s是满足的最大的正整数

即会满足

定理1：在域Fq中，给定一个r次幂c，存在一个b，使得c^(r-1)·b^r 具有r^t阶，（t<s）
证明：
我们设一个l，满足gcd(l,r)=1,那么存在β (0≤β<l)，满足 rβ+r−1 ≡ 0 (mod l) 即存在α，满足 rβ + r−1 = lα.

然后，我们设一个 ζ 为，

则有

其中，

因为c是域Fq中的r次幂，故ζ拥有r^t阶，(0≤t<s) （为啥这里t就小于s了，求指点~）

利用：
在域Fq中，我们令 ξ 为一个r^2阶本原单位根，ξ可以通过公式计算得到，其中d为域Fq中的非r次幂，这样的d可以随机选取，在域Fq中找到它的概率为(r-1)/r

由此，我们设是一个r^t阶的本原单位根，则存在一对唯一确定的i，j满足

因为

所以我们有

由此我们将展现一个新的定理，在合适的情况下，我们用一次指数运算可以找到r次剩余的一个r次根，

定理2：定义u ≡ j·(r^t −1)·r^(s−t−1 ) ≡−jr^(s−t−1) (mod r^(s−1)). 那么在域Fq中c的一个r次根为 cbξ^u ，其中b在定理1中给出。
证明：

（由于，由费马小定理，故在域Fq中易证，)

证毕。

注1： rβ + r −1 = lα 即 r(β + l) + r −1 = l(α + r)。这说明，α （mod r ）是确定的，β（mod l）是确定的，所以对于任意的α 满足 ,都有唯一确定的β满足。作者在这里还加了一句，事实上，条件rβ + r−1−lα = 0 可以转化为 rβ + r−1−lα ≡ 0 (mod (q-1)/r）因为（难道是欧拉判别定理的推广？)

注2：cb的值可以化成

其中α是一个整数（0<α<r），满足所以b也可以表示为

注3：对于 ij ≡ 1 (mod r^t) ，当r^t很大（t>1 并且在r^t阶循环群中的离散对数很难处理）时，其中的i和j找起来是比较困难的，所以这个方法适合在r和t都比较小的时候，也可以被视作是另一个版本的Adleman-Manders-Miller algorithm。