精华内容
下载资源
问答
  • 离散对数求解相关算法计算方法介绍以及使用Python3实现...

    博客:https://blog.slight-wind.com/

    密码学笔记:离散对数求解相关算法实现

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-G2ZOYqwR-1584639702715)(01.png)]

    在整数中,离散对数(英语:Discrete logarithm)是一种基于同余运算和原根的一种对数运算。而在实数中对数的定义 log ⁡ b a \log_ba logba 是指对于给定的 a 和 b,有一个数 x,使得 b x b^{x} bx = a。相同地在任何群 G 中可为所有整数 k 定义一个幂数为 b k b^{k} bk,而离散对数 log ⁡ b a \log_ba logba 是指使得 b k b^{k} bk = a 的整数 k。 离散对数在一些特殊情况下可以快速计算。然而,通常没有具非常效率的方法来计算它们。公钥密码学中几个重要算法的基础,是假设寻找离散对数的问题解,在仔细选择过的群中,并不存在有效率的求解算法。Wikipedia

    索引

    • Shank’s Babystep-Giantstep Algorithm (BSGS离散对数算法)

    • 中国剩余定理(Chinese remainder theorem)

    • Pollard’s rho (分解质因数算法)

    • Pohlig-Hellman Algorithm (Pohlig-Hellman 离散对数算法)

    Shanks’s Babystep-Giantstep Algorithm

    对于同余式 g x ≡ h g^x ≡ h gxh (mod p) ,g 为质数 p 的一个原根,这种情况便可以使用 Shanks 算法。令 N = p-1,相比于暴力枚举法 O ( N ) O(N) O(N) 的时间复杂度,Shanks 算法可以将时间复杂度降到 O ( N ) O(\sqrt{N}) O(N ) .

    求解过程

    1. 计算 n = ⌊ N ⌋ \lfloor {\sqrt{N}} \rfloor N + 1 .
    2. 构造出两个列表:
      1. List1 = [ 1 1 1 , g g g , g 2 g^2 g2 , g 2 g^2 g2 , . . . ... ... , g n g^n gn ]
      2. List2 = [ h h h , h h h ⋅ \cdot g − n g^{-n} gn , h h h ⋅ \cdot g − 2 n g^{-2n} g2n , h h h ⋅ \cdot g − 3 n g^{-3n} g3n , . . . ... ... , h h h ⋅ \cdot g − n 2 g^{-n^2} gn2 ]
    3. 在 List1 和 List2 中找到两个相同的元素,即 List1[ i ] == List2[ j ] ,那么就会有 g i = h g − j n g^i = hg^{-jn} gi=hgjn.
    4. 那么 x = i + jn 便是 g x = h g^x = h gx=h 的一个解.

    Python 3 实现

    #python3.7.6
    #Author:Am473ur
    #调用函数 sDLP(g,h,p) 返回 g^x≡h (mod p) 的一个解
    #Shanks's Babystep-Giantstep Algorithm
    from gmpy2 import invert,iroot
    from Crypto.Util.number import getPrime
    
    class node:
        def _init_(self):
            self.vue=0
            self.num=0
    def cmp(a):
          return a.vue
    def init_list(first,g,n,p):
          List=[]
          temp=node()
          temp.vue,temp.num=first,0
          List.append(temp)
          for i in range(1,n+1):
                temp=node()
                temp.num = i
                temp.vue = List[i-1].vue * g % p
                List.append(temp)
          List.sort(key=cmp)
          return List
    def sDLP(a,b,p):
        ans=p
        n=iroot(p,2)[0]+1
        L1=init_list(1,a,n,p)
        aa=pow(invert(a,p),n,p)
        L2=init_list(b,aa,n,p)
        i = 0
        j = 0
        while True :
            if (i>=n or j>=n): break
            while (L1[i].vue < L2[j].vue and i<n): i += 1
            while (L1[i].vue > L2[j].vue and j<n): j += 1
            if L1[i].vue == L2[j].vue :
                x=L1[i].num+L2[j].num*n
                return int(x)
    p = 552022109
    g = 520158203
    h = 525148510
    print(sDLP(g,h,p))
    

    中国剩余定理(Chinese remainder theorem)

    其实这里应该介绍 Pohlig–Hellman 离散对数算法了,但是其主要过程利用了中国剩余定理(CRT),所以也在这里提一下,相关计算和证明过程在百度百科就很容易找到,在此不做赘述。

    这里引用 A n I n t r o d u c t i o n t o M a t h e m a t i c a l C r y p t o g r a p h y AnIntroductiontoMathematicalCryptography AnIntroductiontoMathematicalCryptography 书中的一段话:

    In addition to being a theorem and an algorithm, we would suggest to the
    reader that the Chinese remainder theorem is also a state of mind.

    CRT更是一种解决问题的思想,把一个大的问题分解为若干个小的问题分别求解,CRT使得若干个子问题的解可以再组合成原问题的解(同余方程组)。这种算法应用到解决离散对数问题显得非常巧妙。这就是 Pohlig-Hellman 离散对数算法。

    Python 3 实现 CRT

    #python3.7.6
    #Author:Am473ur
    # m 和 a 为两个列表,表示同余方程组 x mod m = a (m1,a1;m2,a2;...)
    from functools import reduce
    from gmpy2 import invert
    
    def CRT(m,a):
          Num=len(m)
          M=reduce(lambda x,y: x*y, m)
          Mi=[M//i for i in m]
          t=[invert(Mi[i], m[i]) for i in range(Num)]
          x=0
          for i in range(Num):
                x+=a[i]*t[i]*Mi[i]
          return x%M
    

    Pollard’s rho (分解质因数算法)

    同样是为了实现 Pohlig-Hellman 离散对数算法,我们还需要了解一种分解质因数算法——Pollard’s rho Algorithm 。

    Python 3 实现 Pollard’s rho

    #python3.7.6
    #Author:Am473ur
    #通过调用 Factor(n) 进行质因数分解,返回值是因数列表。
    from Crypto.Util.number import isPrime
    from math import gcd
    
    def f(x):
        return x**2 + 1
    
    def pollard_rho(N):
        xn = 2
        x2n = 2
        d = 1
        while d == 1:
            xn = f(xn) % N
            x2n = f(f(x2n)) % N
            abs_val = abs(xn - x2n)
            d = gcd(abs_val, N)
        return d
    
    def Factor(n):
        ans=[]
        while True:
            temp=pollard_rho(n)
            ans.append(temp)
            n=n//temp
            if n==1:return ans
            if isPrime(n):
                ans.append(n)
                return ans
    '''
    n=12345678754345678765456789876587654567899876
    print(Factor(n))
    output:[4, 3109, 3553454208763, 279372423577347576184497407]
    '''
    

    Pohlig-Hellman Algorithm (Pohlig-Hellman 离散对数算法)

    若 p-1 是一个 B-smooth number ,Pohlig-Hellman 离散对数算法只有在 B 较小的时候表现良好,所以对于解决离散对数问题(DLP)来说,其仍是微不足道的。同时也说明了如果在加密过程中选择了 p-1 的最大质因子较小的质数 p,那么此时的 DLP 可能容易受到Pohlig-Hellman 算法的攻击。

    In number theory, a n-smooth (or n-friable) number is an integer whose prime factors are all less or equal to n.–Wikipedia

    Pohlig-Hellman 离散对数算法

    对于离散对数问题 g x g^x gx ≡ ≡ h h h (mod p) , N = p-1 为 G 的秩,根据 唯一分解定理 : N N N = = = q 1 e 1 q_1^{e_1} q1e1 ⋅ \cdot q 2 e 2 q_2^{e_2} q2e2 ⋅ ⋅ ⋅ \cdot\cdot\cdot q t e t q_t^{e_t} qtet

    1. 对 N 进行分解,得到因数列表 List q e q^e qe . 即 qe = [ q 1 e 1 q_1^{e_1} q1e1, q 2 e 2 q_2^{e_2} q2e2 , ⋅ ⋅ ⋅ \cdot\cdot\cdot , q t e t q_t^{e_t} qtet]
    2. 用已知的每一项 q i e i q_i^{e_i} qiei 计算 List g ( p − 1 ) / q e g^{(p-1)/q^e} g(p1)/qe 和 List h ( p − 1 ) / q e h^{(p-1)/q^e} h(p1)/qe .
    3. 对于每一组 g ( p − 1 ) / q e g^{(p-1)/q^e} g(p1)/qe h ( p − 1 ) / q e h^{(p-1)/q^e} h(p1)/qe ,计算出 ( g ( p − 1 ) / q e g^{(p-1)/q^e} g(p1)/qe) x ^x x = h ( p − 1 ) / q e h^{(p-1)/q^e} h(p1)/qe 中的 x x x ,并存入 List x x x .
    4. 最后一步利用CRT算法,对于 List 中对应的各 i 项, x x x = = = List x x x[i] (mod List q e q^e qe[i]) 构成同余方程组 .

    Python 3 实现 Pohlig-Hellman Algorithm

    有了前面的 CRT 算法和 Pollard’s rho 质因数分解算法的铺垫,实现 Pohlig-Hellman 离散对数算法就会容易很多。

    #python3.7.6
    #Author:Am473ur
    from Crypto.Util.number import long_to_bytes
    from functools import reduce
    from gmpy2 import gcd,invert
    from ShanksDLP import sDLP
    from PollardRhoFactor import Factor
    import time
    #g^x = h (mod p)
    
    def CRT(m,a):
          Num=len(m)
          M=reduce(lambda x,y: x*y, m)
          Mi=[M//i for i in m]
          t=[invert(Mi[i], m[i]) for i in range(Num)]
          x=0
          for i in range(Num):
                x+=a[i]*t[i]*Mi[i]
          return x%M
    def BruteForceDLP(A,B,P):
          for i in range(P):
                if pow(A,i,P)==B:
                      return int(i)
    def PohligHellman(g,h,p):
          qe=Factor(p-1)
          assert reduce(lambda x,y: x*y, qe) == p-1
          print(qe)
          Lg=[pow(g,(p-1)//i,p) for i in qe]
          Lh=[pow(h,(p-1)//i,p) for i in qe]
          length=len(qe)
          La=[]
          for i in range(length):
                if p<1000000000000:#p较小Shanks's算法可以接受就使用Shanks's解决
                      La.append(sDLP(Lg[i],Lh[i],p))
                else:#p-1的最大质因子较小的话暴力枚举法也有很好的表现
                      La.append(BruteForceDLP(Lg[i],Lh[i],p))
                #print(Lg[i],Lh[i],La[i])
          X=CRT(qe,La)
          if pow(g,X,p)==h:
                print("x is Right ! x = ",X)
          else:print("Wrang Answer")
    
    print("g^x = h (mod p)")
    p=int(input("p= "))
    g=int(input("g= "))
    h=int(input("h= "))
    start_time=time.time()
    PohligHellman(g,h,p)
    print("it takes ",time.time()-start_time," seconds",)
    

    参考

    欢迎来康康我的博客

    展开全文
  • sage之离散对数求解

    千次阅读 2020-06-19 11:07:20
    sage中求解离散对数我目前知道的三个函数:discrete_log(a,base,ord,operation),discrete_log_rho(a,base,ord,operation),discrete_log_lambda(a,base,bounds,operation);这三个函数分别是通用的求离散对数的方法...

    sage中求解离散对数我目前知道的四个函数:

    (1)discrete_log:通用的求离散对数的方法:discrete_log(a,base,ord,operation)

    (2)discrete_log_rho:求离散对数的Pollard-Rho算法:discrete_log_rho(a,base,ord,operation)

    (3)discrete_log_lambda:求离散对数的Pollard-kangaroo算法(也称为lambda算法):discrete_log_lambda(a,base,bounds,operation)

    (4)bsgs:小步大步法:bsgs(base,a,bounds,operation)

    参数说明:求解以base为底,a的对数;ord为base的阶,可以缺省,operation可以是'+'与'*',默认为'*';bounds是一个区间(ld,ud),需要保证所计算的对数在此区间内。

    下面分别举例使用这些函数对ElGamal的分析与Ecc的分析。

    #生成64位的素数p作为模数,int为32位,超过int要在数字后加L
    p=random_prime(2L**64)
    
    #定义有限域GF(p)
    G=GF(p)
    
    #找一个模p的原根
    gp ('znprimroot('+str(p)+')')
    #输出Mod(rt,p),则x是模p的原根
    g=G(rt)
    
    #生成私钥
    x=G(ZZ.random_element(p-1))
    
    #公钥y=g^x mod p,由于已经定义在GF(p)上,因此g**x就是g^x mod p
    y=g**x
    
    #计算离散对数的通用方法
    discrete_log(y,g)==x
    
    #计算离散对数的lambda方法
    discrete_log_lambda(y,g,(floor(ZZ(x)/2),2*ZZ(x)))==x
    
    #小步大步法计算离散对数
    bsgs(g,y,(floor(ZZ(x)/2),2*ZZ(x)))==x

    上面是以discrete_log举例,discrete_log_rho参数列表与discrete_log一致,因此用法相同;只不过,由于discrete_log_rho是基于随机性的概率型算法,因此不一定每次都能找到,不过多一个方法总归是好的;其次,https://xz.aliyun.com/t/2780里面详细介绍了Pollard Rho算法,这个算法起作用是有条件的。

    此算法适用于生成元的阶的素因子都是大数的情形,计算元素的阶的函数如下。

    #加法阶
    n=g.order();n
    #乘法阶
    n=g.multiplicative_order();n

    可以看到加法阶比乘法阶大1。

    下面介绍在椭圆曲线上求解离散对数。下例为2013年SECCON CTF quals 中的 Cryptanalysis。

    a = 1234577
    b = 3213242
    n = 7654319
    #有限域GF(n)上的椭圆曲线y^2 = x^3 + a*x + b mod n
    E = EllipticCurve(GF(n), [0, 0, 0, a, b])
    #生成元
    base = E([5234568, 2287747])
    #公钥
    pub = E([2366653, 1424308])
    #求解私钥,通用方法;注意这里的运算要换成加法
    discrete_log(pub,base,operation='+')
    
    #求解私钥,Rho方法;此情形Rho方法也可以求解,而且可以感觉到比通用方法要快
    discrete_log_rho(pub,base,operation='+')
    
    #求解私钥,lambda方法
    discrete_log_lambda(pub,base,(floor(1584718/2),2*1584718),operation='+')
    
    #小步大步法计算离散对数
    bsgs(base,pub,(floor(1584718/2),2*1584718),operation='+')

     

    展开全文
  • 离散对数求解算法

    千次阅读 2015-01-21 20:00:47
    求解一个最小的x满足给定的方程 B x == N (mod P) 使用baby_step_giant_step算法。也就是先小步后大步算法。 1、令x=i*m+j (m=ceil(sqrt(p))), 那么原式化为 B^(i*m)*B^j==N(MOD P) B^j==N*B^(-i*m)...


    求解一个最小的x满足给定的方程Bx == N (mod P)

    使用baby_step_giant_step算法。也就是先小步后大步算法。

    1、令x=i*m+j  (m=ceil(sqrt(p))),

    那么原式化为 B^(i*m)*B^j==N(MOD P)

    B^j==N*B^(-i*m)(MOD P)---------->B^j==N*B^m^(-i)(MOD P)

    2、先预处理B^0,B^1,B^2……B^(m-1),存入HASH表,我使用结构体排序然后二分查找,这一步就是baby_step,每次移动1

    3、然后快速幂求出B^-m,枚举i,如果存在N*B^(-i*m)存在于HASH表中,说明存在解x=i*m+j,这一步为giant_step,每次移动m

    注意以上解法是最基本的,只能对于gcd(B,P)==1,算法的时间复杂度是O(sqrt(P)*log(sqrt(P)))

    样题:poj2417

    ps:参考cxlove博客,密码学里面貌似叫做shanks算法 点击打开链接

    模板:

    ///大步小步算法
    struct baby///小步算法预存的结构体定义
    {
        long long b,j;
        bool operator < (const baby &other)const{
            if(b==other.b)return j<other.j;
            return b<other.b;
        }
    }babyv[100005];
    ///快速幂,x^y%mod
    long long q_pow(long long x,long long y,long long mod)
    {
        long long ans=1;
        while(y>0)
        {
            if(y&1)ans=(ans*x)%mod;
            x=(x*x)%mod;
            y>>=1;
        }
        return ans;
    }
    ///小步预存的个数为m的结构体里面查找num
    long long find(long long num,long long m)
    {
        long long l=0,r=m-1,ans=-1;
        while(r>=l)
        {
            long long mid=(r+l)/2;
            if(babyv[mid].b>=num){
                if(babyv[mid].b==num)
                    ans=babyv[mid].j;
                r=mid-1;
            }
            else l=mid+1;
        }
        return ans;
    }
    ///B^x=N(modP)求解x,无解返回-1
    long long babystep_giantstep(long long B,long long N,long long P)
    {
        long long m=ceil(sqrt(P)),ans=1;
        for(long long j=0;j<m;j++)///预存操作
        {
            babyv[j].b=ans;
            babyv[j].j=j;
            ans=(ans*B)%P;///递推
        }
        ans=1;
        sort(babyv,babyv+m);///预存排序
        long long _Bm=q_pow(q_pow(B,P-2,P),m,P);///算出B^(-m)%P的值
        for(long long i=0;i<m;i++)
        {
            long long j=find(N*ans%P,m);///二分查找
            if(j!=-1)return i*m+j;///找到返回答案
            ans=(ans*_Bm)%P;///继续递推
        }
        return -1;///找不到答案
    }

    poj2417代码:点击打开链接

    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<string>
    #include<cstdlib>
    #include<utility>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define Inf (1<<29)
    #define LL long long
    using namespace std;
    const int MM=110;
    const long long MOD=1000000007;
    ///大步小步算法
    struct baby///小步算法预存的结构体定义
    {
        long long b,j;
        bool operator < (const baby &other)const{
            return b<other.b;
        }
    }babyv[100005];
    ///快速幂,x^y%mod
    long long q_pow(long long x,long long y,long long mod)
    {
        long long ans=1;
        while(y>0)
        {
            if(y&1)ans=(ans*x)%mod;
            x=(x*x)%mod;
            y>>=1;
        }
        return ans;
    }
    ///小步预存的个数为m的结构体里面查找num
    long long find(long long num,long long m)
    {
        long long l=0,r=m-1;
        while(r>=l)
        {
            long long mid=(r+l)/2;
            if(babyv[mid].b==num)return babyv[mid].j;
            else if(babyv[mid].b>num)r=mid-1;
            else l=mid+1;
        }
        return -1;
    }
    ///B^x=N(modP)求解x,无解返回-1
    long long babystep_giantstep(long long B,long long N,long long P)
    {
        long long m=ceil(sqrt(P-1)),ans=1;
        for(long long j=0;j<m;j++)///预存操作
        {
            babyv[j].b=ans;
            babyv[j].j=j;
            ans=(ans*B)%P;///递推
        }
        ans=1;
        sort(babyv,babyv+m);///预存排序
        long long _Bm=q_pow(q_pow(B,P-2,P),m,P);///算出B^(-m)%P的值
        for(long long i=0;i<m;i++)
        {
            long long j=find(N*ans%P,m);///二分查找
            if(j!=-1)return i*m+j;///找到返回答案
            ans=(ans*_Bm)%P;///继续递推
        }
        return -1;///找不到答案
    }
    int main()
    {
        long long B,N,P;
        //freopen("D:\\o.txt","r",stdin);
        while(~scanf("%lld%lld%lld",&P,&B,&N))
        {
            long long ans=babystep_giantstep(B,N,P);
            if(ans==-1)puts("no solution");
            else printf("%lld\n",ans);
        }
        return 0;
    }
     
    

    求解一个最小的x满足给定的方程Ax == B (mod C)

    其中C任意,即C不一定是素数

    算法 : 扩展小步大步攻击

    扩展小步大步攻击:A ^ x = B (mod C)

    1 :  i = 0-> 100 if A^i mod C == B return i;///做这一步是第四步有一个n

    2 :  消因子, 将A^x = B mod C 划为 d * A ^ (x – n) = B (modC)

    3 : m = ceil (sqrt(C))

    4 : 将 A ^ (x - n) 化为  A ^ (I * m + j)(原x 化为了 n + I * m + j)这里与小步大步攻击不同

    5 : for j = 0 ->m   hash(j,A ^ j mod  C)

    6 : for i = 0 ->m   AA = B/(d * A ^ m ^i)

    7 :在hash表中查找AA,若有,取AA对应的j,则答案为I * m + j + n

    样题:poj3243 hdu2815

    ps:参考点击打开链接有详细证明的方法

    模板:

    ///扩展大步小步算法
    struct baby///小步算法预存的结构体定义
    {
        long long b,j;
        bool operator < (const baby &other)const{
            if(b==other.b)return j<other.j;
            return b<other.b;
        }
    }babyv[100005];
    long long extended_euclid(long long a,long long b,long long &x,long long &y)
    {
         long long d;
         if(b == 0) {x = 1;     y = 0;     return a;}
         d = extended_euclid(b, a % b, y, x);
         y -= a / b * x;
         return d;
    }
    long long Inv(long long a,long long n)
    {
         long long d, x, y;
         d = extended_euclid(a, n, x, y);
         if(d == 1)	return (x%n + n) % n;
         else			return -1; // no solution
    }
    long long gcd(long long x,long long y)
    {
        if(y==0)return x;
        return gcd(y,x%y);
    }
    ///快速幂,x^y%mod
    long long q_pow(long long x,long long y,long long mod)
    {
        long long ans=1;
        while(y>0)
        {
            if(y&1)ans=(ans*x)%mod;
            x=(x*x)%mod;
            y>>=1;
        }
        return ans;
    }
    ///小步预存的个数为m的结构体里面查找num
    long long find(long long num,long long m)
    {
        long long l=0,r=m-1,ans=-1;
        while(r>=l)
        {
            long long mid=(r+l)/2;
            if(babyv[mid].b>=num){
                if(babyv[mid].b==num)
                    ans=babyv[mid].j;
                r=mid-1;
            }
            else l=mid+1;
        }
        return ans;
    }
    ///A^x=B(modC)求解x,gcd(A,C)不一定等于1,无解返回-1
    long long ex_babystep_giantstep(long long A,long long B,long long C)
    {
        for(long long i=0;i<=100;i++)///先在小于100的数里面测试
            if(q_pow(A,i,C)==B%C)return i;
        ///消因子, 将A^x=B%C化为d*A^(x – n)=B%C
        long long g,n=0,d=1;
        while((g=gcd(A,C))!=1)
        {
            if(B%g)return -1;///无解
            n++;
            B/=g;
            C/=g;
            d=(d*A/g)%C;
        }
        ///无扩展小步大步操作
        long long m=ceil(sqrt(C)),ans=1;
        for(long long j=0;j<m;j++)///预存操作
        {
            babyv[j].b=ans;
            babyv[j].j=j;
            ans=(ans*A)%C;///递推
        }
        ans=1;
        sort(babyv,babyv+m);///预存排序
        long long Bm=q_pow(Inv(A,C),m,C);///算出A^(-m)%C的值
        for(long long i=0;i<m;i++)
        {
            long long j=find(Inv(d,C)*B%C*ans%C,m);///二分查找
            if(j!=-1)return i*m+j+n;///找到返回答案
            ans=(ans*Bm)%C;///继续递推
        }
        return -1;///找不到答案
    }


    poj3243点击打开链接

    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<string>
    #include<cstdlib>
    #include<utility>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define Inf (1<<29)
    #define LL long long
    using namespace std;
    const int MM=110;
    const long long MOD=1000000007;
    ///扩展大步小步算法
    struct baby///小步算法预存的结构体定义
    {
        long long b,j;
        bool operator < (const baby &other)const{
            if(b==other.b)return j<other.j;
            return b<other.b;
        }
    }babyv[100005];
    long long extended_euclid(long long a,long long b,long long &x,long long &y)
    {
         long long d;
         if(b == 0) {x = 1;     y = 0;     return a;}
         d = extended_euclid(b, a % b, y, x);
         y -= a / b * x;
         return d;
    }
    long long Inv(long long a,long long n)
    {
         long long d, x, y;
         d = extended_euclid(a, n, x, y);
         if(d == 1)	return (x%n + n) % n;
         else			return -1; // no solution
    }
    long long gcd(long long x,long long y)
    {
        if(y==0)return x;
        return gcd(y,x%y);
    }
    ///快速幂,x^y%mod
    long long q_pow(long long x,long long y,long long mod)
    {
        long long ans=1;
        while(y>0)
        {
            if(y&1)ans=(ans*x)%mod;
            x=(x*x)%mod;
            y>>=1;
        }
        return ans;
    }
    ///小步预存的个数为m的结构体里面查找num
    long long find(long long num,long long m)
    {
        long long l=0,r=m-1,ans=-1;
        while(r>=l)
        {
            long long mid=(r+l)/2;
            if(babyv[mid].b>=num){
                if(babyv[mid].b==num)
                    ans=babyv[mid].j;
                r=mid-1;
            }
            else l=mid+1;
        }
        return ans;
    }
    ///A^x=B(modC)求解x,gcd(A,C)不一定等于1,无解返回-1
    long long ex_babystep_giantstep(long long A,long long B,long long C)
    {
        for(long long i=0;i<=100;i++)///先在小于100的数里面测试
            if(q_pow(A,i,C)==B%C)return i;
        ///消因子, 将A^x=B%C化为d*A^(x – n)=B%C
        long long g,n=0,d=1;
        while((g=gcd(A,C))!=1)
        {
            if(B%g)return -1;///无解
            n++;
            B/=g;
            C/=g;
            d=(d*A/g)%C;
        }
        ///无扩展小步大步操作
        long long m=ceil(sqrt(C)),ans=1;
        for(long long j=0;j<m;j++)///预存操作
        {
            babyv[j].b=ans;
            babyv[j].j=j;
            ans=(ans*A)%C;///递推
        }
        ans=1;
        sort(babyv,babyv+m);///预存排序
        long long Bm=q_pow(Inv(A,C),m,C);///算出A^(-m)%C的值
        for(long long i=0;i<m;i++)
        {
            long long j=find(Inv(d,C)*B%C*ans%C,m);///二分查找
            if(j!=-1)return i*m+j+n;///找到返回答案
            ans=(ans*Bm)%C;///继续递推
        }
        return -1;///找不到答案
    }
    int main()
    {
        long long X,Z,K;
        //freopen("D:\\o.txt","r",stdin);
        while(~scanf("%lld%lld%lld",&X,&Z,&K))
        {
            if(X==0&&Z==0&&K==0)break;
            long long ans=ex_babystep_giantstep(X,K,Z);
            if(ans==-1)puts("No Solution");
            else printf("%lld\n",ans);
        }
        return 0;
    }
    
    
    
    

    hdu2815 点击打开链接

    注意:K>=Z


    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<string>
    #include<cstdlib>
    #include<utility>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define Inf (1<<29)
    #define LL long long
    using namespace std;
    const int MM=110;
    const long long MOD=1000000007;
    ///扩展大步小步算法
    struct baby///小步算法预存的结构体定义
    {
        long long b,j;
        bool operator < (const baby &other)const{
            if(b==other.b)return j<other.j;
            return b<other.b;
        }
    }babyv[100005];
    long long extended_euclid(long long a,long long b,long long &x,long long &y)
    {
         long long d;
         if(b == 0) {x = 1;     y = 0;     return a;}
         d = extended_euclid(b, a % b, y, x);
         y -= a / b * x;
         return d;
    }
    long long Inv(long long a,long long n)
    {
         long long d, x, y;
         d = extended_euclid(a, n, x, y);
         if(d == 1)	return (x%n + n) % n;
         else			return -1; // no solution
    }
    long long gcd(long long x,long long y)
    {
        if(y==0)return x;
        return gcd(y,x%y);
    }
    ///快速幂,x^y%mod
    long long q_pow(long long x,long long y,long long mod)
    {
        long long ans=1;
        while(y>0)
        {
            if(y&1)ans=(ans*x)%mod;
            x=(x*x)%mod;
            y>>=1;
        }
        return ans;
    }
    ///小步预存的个数为m的结构体里面查找num
    long long find(long long num,long long m)
    {
        long long l=0,r=m-1,ans=-1;
        while(r>=l)
        {
            long long mid=(r+l)/2;
            if(babyv[mid].b>=num){
                if(babyv[mid].b==num)
                    ans=babyv[mid].j;
                r=mid-1;
            }
            else l=mid+1;
        }
        return ans;
    }
    ///A^x=B(modC)求解x,gcd(A,C)不一定等于1,无解返回-1
    long long ex_babystep_giantstep(long long A,long long B,long long C)
    {
        for(long long i=0;i<=100;i++)///先在小于100的数里面测试
            if(q_pow(A,i,C)==B%C)return i;
        ///消因子, 将A^x=B%C化为d*A^(x – n)=B%C
        long long g,n=0,d=1;
        while((g=gcd(A,C))!=1)
        {
            if(B%g)return -1;///无解
            n++;
            B/=g;
            C/=g;
            d=(d*A/g)%C;
        }
        ///无扩展小步大步操作
        long long m=ceil(sqrt(C)),ans=1;
        for(long long j=0;j<m;j++)///预存操作
        {
            babyv[j].b=ans;
            babyv[j].j=j;
            ans=(ans*A)%C;///递推
        }
        ans=1;
        sort(babyv,babyv+m);///预存排序
        long long Bm=q_pow(Inv(A,C),m,C);///算出A^(-m)%C的值
        for(long long i=0;i<m;i++)
        {
            long long j=find(Inv(d,C)*B%C*ans%C,m);///二分查找
            if(j!=-1)return i*m+j+n;///找到返回答案
            ans=(ans*Bm)%C;///继续递推
        }
        return -1;///找不到答案
    }
    int main()
    {
        long long X,Z,K;
        while(~scanf("%I64d%I64d%I64d",&X,&Z,&K))
        {
            //if(X==0&&Z==0&&K==0)break;
            if(K>=Z){puts("Orz,I can’t find D!");continue;}
            long long ans=ex_babystep_giantstep(X,K,Z);
            if(ans==-1)puts("Orz,I can’t find D!");
            else printf("%I64d\n",ans);
        }
        return 0;
    }
    

    给定k,m,newx,其中m是素数,求出满足x^k mod m = newx 所有 x 的值

    预备:

    a、模mod的群G的元的阶的定义:a^m%mod==e的最小整数m叫做元a的阶
    b、原根(本原元素)的定义:a^phi(m)%m==e,phi(m)是a的阶,则称a是模m的一个原根

    原根的性质:{1,2,...,m-1} = {g,g^2,...,g^(m-1)}其中g是原根

    原根的判定定理(欧拉定理):p(大于2)是一个素数,a是本原元素当且仅当a的(p-1)╱q次方(模p)不等于1,q是p-1的所有因子

    求解问题的算法步骤如下

    1) 先暴力求m的原根g
     2) 大步小步求g^t = newx mod m
     3) 则g^(t+v*m1) = newx mod m, m1 = p - 1
     4) 设x = g^u mod p, x^k = (g^u)^k = g^(uk) = g^(t+v*m1)

    化成uk+vm=t,可以用扩展欧几里得求得

    样题:hdu3930 点击打开链接

    参考自点击打开链接

    代码如下:

    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<string>
    #include<cstdlib>
    #include<utility>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    long long cnt=0;
    long long p[2000001];
    bool isprime[2000001];
    ///求a*b%c,因为a,b很大,所以要先将b写成二进制数
    long long mul_mod(long long a, long long b, long long mod )
    {
        long long ans = 0, d = a % mod;
        while( b )
        {
            if( b & 1 )
            {
                ans += d;
                if( ans > mod )ans -= mod;
            }
            d += d;
            if( d > mod )d -= mod;
            b >>= 1;
        }
        return ans;
    }
    void init()
    {
        isprime[0]=isprime[1]=true;
        for(int i=2; i<=1000000; i++)
        {
            if(isprime[i])continue;
            p[cnt++]=i;
            for(int j=i+i; j<=1000000; j+=i)
                isprime[j]=true;
        }
    }
    long long num=0;
    long long f[200];
    void factor(long long n)
    {
        num=0;
        for(long long i=0; i<cnt&&p[i]*p[i]<=n; i++)
        {
            if(n%p[i]==0)
            {
                f[num++]=p[i];
                while(n%p[i]==0)n/=p[i];
            }
        }
        if(n>1)f[num++]=n;
    }
    ///扩展大步小步算法
    struct baby///小步算法预存的结构体定义
    {
        long long b,j;
        bool operator < (const baby &other)const
        {
            if(b==other.b)return j<other.j;
            return b<other.b;
        }
    } babyv[4000005];
    long long extended_euclid(long long a,long long b,long long &x,long long &y)
    {
        long long d;
        if(b == 0)
        {
            x = 1;
            y = 0;
            return a;
        }
        d = extended_euclid(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
    long long Inv(long long a,long long n)
    {
        long long d, x, y;
        d = extended_euclid(a, n, x, y);
        if(d == 1)	return (x%n + n) % n;
        else			return -1; // no solution
    }
    long long gcd(long long x,long long y)
    {
        if(y==0)return x;
        return gcd(y,x%y);
    }
    ///快速幂,x^y%mod
    long long q_pow(long long x,long long y,long long mod)
    {
        long long ans=1;
        while(y>0)
        {
            //if(y&1)ans=(ans*x)%mod;
            if(y&1)ans=mul_mod(ans,x,mod);
            //x=(x*x)%mod;
            x=mul_mod(x,x,mod);
            y>>=1;
        }
        return ans;
    }
    ///小步预存的个数为m的结构体里面查找num
    long long find(long long num,long long m)
    {
        long long l=0,r=m-1,ans=-1;
        while(r>=l)
        {
            long long mid=(r+l)/2;
            if(babyv[mid].b>=num)
            {
                if(babyv[mid].b==num)
                    ans=babyv[mid].j;
                r=mid-1;
            }
            else l=mid+1;
        }
        return ans;
    }
    ///A^x=B(modC)求解x,gcd(A,C)不一定等于1,无解返回-1
    long long ex_babystep_giantstep(long long A,long long B,long long C)
    {
        for(long long i=0; i<=100; i++) ///先在小于100的数里面测试
            if(q_pow(A,i,C)==B%C)return i;
        ///消因子, 将A^x=B%C化为d*A^(x – n)=B%C
        long long g,n=0,d=1;
        while((g=gcd(A,C))!=1)
        {
            if(B%g)return -1;///无解
            n++;
            B/=g;
            C/=g;
            //d=(d*A/g)%C;
            d=mul_mod(d,A/g,C);
        }
        ///无扩展小步大步操作
        long long m=ceil(sqrt(C+0.0)),ans=1;
        for(long long j=0; j<m; j++) ///预存操作
        {
            babyv[j].b=ans;
            babyv[j].j=j;
            //ans=(ans*A)%C;///递推
            ans=mul_mod(ans,A,C);
        }
        ans=1;
        sort(babyv,babyv+m);///预存排序
        long long Bm=q_pow(Inv(A,C),m,C);///算出A^(-m)%C的值
        for(long long i=0; i<m; i++)
        {
            long long temp=mul_mod(Inv(d,C),B,C);//Inv(d,C)*B%C*ans%C
            temp=mul_mod(temp,ans,C);
            long long j=find(temp,m);///二分查找
            if(j!=-1)return i*m+j+n;///找到返回答案
            //ans=(ans*Bm)%C;///继续递推
            ans=mul_mod(ans,Bm,C);
        }
        return -1;///找不到答案
    }
    bool judge(long long g,long long mod)
    {
        long long i;
        for(i=0; i<num; i++)
            if(q_pow(g,(mod-1)/f[i],mod)==1)break;
        if(i>=num)return true;
        return false;
    }
    long long find_g(long long mod)
    {
        factor(mod-1);
        for(long long g=2;; g++)
            if(judge(g,mod))return g;
    }
    vector<long long>res;
    int main()
    {
        init();
        long long Case=1;
        long long newx,k,m;
        while(scanf("%I64d%I64d%I64d",&k,&m,&newx)!=EOF)
        {
            printf("case%I64d:\n",Case++);
            long long u,v;
            long long g=find_g(m);
            long long t=ex_babystep_giantstep(g,newx,m);
            long long GCD=extended_euclid(k,m-1,u,v);
            if(t%GCD||newx>=m)puts("-1");
            else
            {
                res.clear();
                long long up=t/GCD;
                long long down=(m-1)/GCD;
                u=(u*up%down+down)%down;
                for(long long i=0; i<GCD; i++)
                {
                    long long temp=u+down*i;
                    res.push_back(q_pow(g,temp,m));
                }
                sort(res.begin(),res.end());
                for(long long i=0; i<res.size(); i++)
                    printf("%I64d\n",res[i]);
            }
        }
        return 0;
    }


    展开全文
  • 离散对数求解实验

    2020-10-11 20:34:20
    数据如下: p= 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 g= ...


    数据如下:

    p=
    13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
    
    g=
    11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
    
    h=
    3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333
    

    python代码如下:
    1.基础版本

    import gmpy2
    import time
    
    # 初始参数
    p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
    g = 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
    h = 3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333
    B = 2 ** 20  # 1048576
    
    # 创建空字典
    left_result = {}
    
    # 优化前,令x=Bx0+x1
    start = time.process_time()
    
    s0 = gmpy2.f_mod(h, p)#定值,放在循环体外,减小计算次数,提高运算速度
    for x1 in range(1048577):
        s1 = gmpy2.powmod(g,x1,p)
        s2 = gmpy2.invert(s1,p)
        s3 = gmpy2.f_mod(s0*s2,p)
        left_result[s3] = x1  # key-value
    
    r = gmpy2.powmod(g, B, p)
    for x0 in range(len(left_result)):
        c = gmpy2.powmod(r, x0, p)
    
        if c in left_result:
            x = gmpy2.mul(B, x0) + left_result[c]
            print("x0=", x0)
            print("x1=", left_result[c])
            print("x=", x)
            break
    end = time.process_time()
    print("The running time totals is",end - start, "s")
    

    2.优化

    import gmpy2
    import time
    
    #初始参数
    p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
    g = 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
    h = 3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333
    B = 2 ** 20#1048576
    
    #创建空字典
    left_result = {}
    
     #优化后,令x=Bx0-x1
    start=time.process_time()
    s0 = gmpy2.f_mod(h, p)#定值,只需计算一次,放在循环外
    for x1 in range(1048577):
        s1 = gmpy2.powmod(g,x1,p)
        s2 = gmpy2.f_mod(s1*s0,p)
        left_result[s2] = x1 #key-value
    
    r = gmpy2.powmod(g,B,p)
    for x0 in range(len(left_result)):
        c = gmpy2.powmod(r,x0,p)
    
        if c in left_result:
            x = gmpy2.mul(B,x0) - left_result[c]
            print("x0=",x0)
            print("x1=", left_result[c])
            print("x=", x)
            break
    end=time.process_time()
    print("The running time totals is",end - start, "s")
    
    

    可得结果如下:
    1.基础

    2.优化

    注意:由于数据太大,必须简化处理,否则运行时间指数增长。程序中用到的函数解释:
    在这里插入图片描述
    文末给出gmpy2的参考文档(英文),有兴趣可以阅读:
    链接:gmpy2使用英文版.pdf
    提取码:1234

    展开全文
  • 本周的任务是写一个程序来计算模素数p的离散对数。 二.解题思路 根据实验文档中提供的思路,令B=q=220B=\sqrt{q}=2^{20}B=q​=220,x=x0B+x1x=x_0B+x_1x=x0​B+x1​,其中x0,x1∈[0,B)x_0,x_1\in[0,B)x0​,x1​∈[0,B...
  • 包括狭义的离散对数问题,和椭圆曲线上的点的数乘的逆运算,都算广义离散对数问题,他们的求解方案都差不多。 为了能够用统一的语言来描述,我们首先考虑,如何把广义离散对数问题,规约成狭义离散对数问题。 二,...
  • 可以快速求解离散对数问题,形如,C是素数。 BSGS算法使用了一个重要的引理: 重要的引理 如果,那么。 证明这个引理需要用到欧拉定理 欧拉定理 如果,那么。 证明(十分精彩的证明): ...
  • 离散对数赛题

    2018-11-30 17:23:34
    第三届全国高校面挑战赛的试题,由D—H氏密码协议引出的DLP问题
  • 一、离散对数问题 1.定义 设a=gx  mod  pa = g ^ x\;mod\;pa=gxmodp,记logg,  pa=xlog_{g,\;p} a = xlogg,p​a=x,称x为a的对数(以g为底,模p)。 给定p, g, a计算x称为离散对数问题。 2.应用之一:加密 若g,...
  • 离散对数求解(bsgs)

    2017-04-16 18:38:00
    bsgs算法 主要用来解决${A^x} = B(\bmod C)$(c是质数),都是整数,已知A、B、C求x。 例:poj 2417Discrete Logging 具体步骤如下: 先把$x = i*m - j$,其中$m = ceil(\sqrt C )$,(ceil是向上取整)。...
  • 生日攻击是个概率性问题,以下代码可能只能实现部分离散对数求解问题,通过修改随机数种子可能会解决不同的问题… // BirthdayAttack.cpp : 定义控制台应用程序的入口点。 //生日攻击 #include "stdafx.h"...
  • bytes_to_long(flag), n),由于已知:M,C,N 未知:bytes_to_long(flag) 由此可见这是密码学中一个基于求离散对数困难性的问题 解决方法: # -*- coding: cp936 -*- import random import gmpy2 def discreteLog(g,p,...
  • 离散对数问题,英文是Discrete logarithm Problem,有时候简写为Discrete log,该问题是十几个开放数学问题(Open Problems in Mathematics, [0.a], [0.b])中的一个。为什么要从离散对数问题说起?因为后面的内容中会...
  • 熟练求解椭圆曲线上的离散对数问题。 二、实验原理 (1)有限域GF§上的椭圆曲线:对于固定的a和b,满足形如方程 y2≡x3+ax+b(mod p) ( a,b,x,yGF§且4a3+27b2(mod p)≠0). (2)椭圆曲线Ep(a,b)上的加法定义如下:...
  • Pollard ρ\rhoρ 算法求解离散对数问题 离散对数(DLP)问题:设有群(G,⋅)(G,\cdot)(G,⋅),α∈G\alpha \in Gα∈G是一个nnn阶元素。给定β∈<α>\beta \in \left< \alpha \right>β∈⟨α⟩,找到指数...
  • 使用指数演算法求解离散对数问题 描述 使用指数演算法求解离散对数问题(β=αamod p)。 任务是找到一个已知的β值。 您将使用p = 10930889,并对由α= 2317547形成的子组执行计算。该子组的阶次为59407。请注意,...
  • 小步大步算法(BSGS)求解离散对数问题 众所周知,离散对数问题(Discrete Logarithm Problem,DLP)一直被认为是困难问题。...但是在循环群上,离散对数求解却是难之又难。 问题分析和算法主要思想 根
  • 求解某些奇异椭圆曲线上的椭圆曲线离散对数问题
  • 挑战一(10分) p=11706593258111142827 g= 2 y_a=3415549615389079368 y_b= 1082766791154604642 挑战二(10分) p= 370756802785317561520353987266610526324057108255786051911240331296054004463699 g=2 y_a= ...
  • Pohlig-Hellman算法求解离散对数问题

    千次阅读 2021-02-12 10:11:33
    Pohig-Hellman算法求解离散对数问题 离散对数(DLP)问题: ax≡b(modp) a^{x} \equiv b \pmod{p} ax≡b(modp) ppp是大素数。 前面已经介绍了求解离散对数问题的小步大步算法(BSGS)(时间复杂度是O(p)O(\sqrt{p})O(p​)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,500
精华内容 3,800
关键字:

离散对数求解