精华内容
下载资源
问答
  • 小步大步算法(BSGS)求解离散对数问题 众所周知,离散对数问题(Discrete Logarithm Problem,DLP)一直被认为是困难问题。离散对数问题可以是基于循环群的,也可以是基于椭圆曲线的,本篇以循环群上的离散对数问题为例...

    小步大步算法(BSGS)求解离散对数问题

    众所周知,离散对数问题(Discrete Logarithm Problem,DLP)一直被认为是困难问题。离散对数问题可以是基于循环群的,也可以是基于椭圆曲线的,本篇以循环群上的离散对数问题为例。主要描述的是这样一个问题:

    DLP问题

    求解同余方程
    A x ≡ B ( m o d P ) A^{x}\equiv B \pmod{P} AxB(modP)
    其中, P P P是大素数。

    如果是在整数上,求对数就可以解决。但是在循环群上,离散对数求解却是难之又难。小步大步(Baby Step Giant Step,BSGS)算法是求离散对数问题的一种方法(有的也称为Shanks算法)

    问题分析和算法主要思想

    根据费马小定理,我们知道
    A P − 1 ≡ 1 ( m o d P ) A^{P-1}\equiv 1\pmod{P} AP11(modP)
    所以,如果穷举搜索 x x x的值,算法的复杂度是 O ( P ) O(P) O(P)BSGS算法能够将任意离散对数问题的求解复杂度降至 O ( P ) O(\sqrt{P}) O(P )

    假设我们事先知道一个数 m m m,然后将 x x x表示成
    x = m i − j 并 且 有 j ∈ [ 0 , m − 1 ] x=mi-j\\ 并且有j\in\left[ 0,m-1 \right] x=mijj[0,m1]
    这样,原来的同余方程可以变化为:
    A x ≡ B ( m o d P ) A m i − j ≡ B ( m o d P ) A m i ≡ A j B ( m o d P ) A^{x}\equiv B \pmod{P}\\ A^{mi-j} \equiv B \pmod{P}\\ A^{mi}\equiv A^{j}B\pmod{P} AxB(modP)AmijB(modP)AmiAjB(modP)
    根据这个式子,可以做文章了。

    1. 由于 j ∈ [ 0 , m − 1 ] j\in\left[ 0,m-1 \right] j[0,m1],穷举 A j A^{j} Aj的所有可能取值,存在哈希表中。复杂度为 O ( m ) O(m) O(m)
    2. i i i的界是 [ 0 , P m ] [0,\frac{P}{m}] [0,mP],穷举每个可能的 i i i,计算 A m i A^{mi} Ami的值,我们就可以得到 A j A^{j} Aj的值,再查表,看那个匹配。复杂度是 O ( P m ) O(\frac{P}{m}) O(mP)
    3. 查到满足条件的 i i i j j j,计算 x = m i − j x=mi-j x=mij即可得到解。
      这个算法的时间复杂度是 O ( m + P m ) O(m+\frac{P}{m}) O(m+mP),通常我们选取 m = ⌈ P ⌉ m=\lceil \sqrt{P} \rceil m=P ,则算法的时间复杂度为 O ( P ) O(\sqrt{P}) O(P )

    算法代码

    这个代码来自[BSGS]大步小步算法,仅作参考。

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<map>
    using namespace std;
    typedef long long ll;
    int t,k;
    ll y,z,p;
    //模幂算法
    ll pow(ll a,ll b,ll p){
    	ll ans=1;
    	while(b){
    		if(b&1)ans=ans*a%p;
    		a=a*a%p;
    		b>>=1;
    	}
    	return ans;
    }
    //小步大步算法
    ll BSGS(ll a,ll b,ll p){
        if(!a)return b?-1:1;
        if(b==1)return 0;
        map<ll,ll>mp;
        ll m=ceil(sqrt(p)),ax=1;
        for(int i=0;i<m;i++){
            mp[ax]=i;
            ax=ax*a%p;
        }
        ll am=pow(a,m,p),aj=am*pow(b,p-2,p)%p;
        for(int i=1;i<=m;i++){
            if(mp.count(aj))return m*i-mp[aj];
            aj=aj*am%p;
        }
        return -1;
    }
    int main(){
    	scanf("%d%d",&t,&k);
    	while(t--){
    		scanf("%lld%lld%lld",&y,&z,&p);
    		if(k==1)printf("%lld\n",pow(y,z,p));
    		else if(k==2){
    			if(y%p==0)printf("Orz, I cannot find x!\n");
    			else printf("%lld\n",pow(y,p-2,p)*z%p);
    		}else{
    			ll ans=BSGS(y%p,z%p,p);
    			if(~ans)printf("%lld\n",ans);
    			else printf("Orz, I cannot find x!\n");
    		}
    	}
    }
    
    展开全文
  • baby step giant step简称为大步小步算法,是一个用来求解离散对数的方法,设a的b次对m取模得b,a与m互质时我们令x=At-B,a的At次等于b*a的B次,之后先对右边的数进行存储,,哈希map速度快一点,之后再从左边找,有...

    baby step giant step简称为大步小步算法,是一个用来求解离散对数的方法,设a的b次对m取模得b,a与m互质时我们令x=At-B,a的At次等于b*a的B次,之后先对右边的数进行存储,,哈希map速度快一点,之后再从左边找,有则返回值,这是一种类似于meet In the middle 的算法,不难验证我们取t为sqrt(fi(m))则可以搜索到所有数值,为了避免算欧拉函数我们令t=sqrt(m),

    扩展大步小步算法,当a与m不互质时,我们把式子写成a*a的x-1次+mn=b,同除d若b%d==0则有解,如d=1则互质BSGS求出,若不是继续递归,这里需要一些特判,如我们一般认为0的0次等于,所以log0 0=1;

    下面是代码:

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<string.h>
    #include<vector>
    #include<map> 
    using namespace std;
    typedef long long ll;
    const int N=1e5+10;
    ll qpow(ll a,ll b,ll p){
    	ll ans=1;
    	while(b){
    		if(b&1)ans=ans*a %p;
    		a=a*a %p;
    		b>>=1;
    	}
    	return ans%p;
    } 
    ll gcd(ll a,ll b){
    	if(b==0)return a;
    	return gcd(b,a%b);
    }
    ll oula(ll n ){
    	ll res=n;
    	for(int i=1;i*i<=n;i++){
    		if(n%i==0)res=res/i*(i-1);
    		while(n%i==0)n/=i;
    	}
    	if(n>1)res=res/n*(n-1);
    	return res;
    }
    ll exoula(ll a,ll b,ll m){
    	return qpow(a,b%oula(m)+oula(m),m);
    }
    ll BSGS(ll a,ll b,ll m,ll ,k=1){
    	unordered_map<ll ,ll>hs;
    	int t=sqrt(m)+1,cur=b*a%m;
    	for(int B=1;B<=t;B++){
    		hs[cur]=B;
    		(cur*=a)%=m;
    	}
    	ll at=qpow(a,t,m),now=at;
    	for(int A=1;A<=t;A++){
    		if(hs[now])return At-hs[now];
    		(now*=a)%=m;
    	}
    	return -100;/*负数要小一点防止不断加一溢出*/ 
    }
    ll exBSGS(ll a,ll b,ll m,ll k%m){
    	if(a==0&&b==0)return 1;
    	if(b==1)return 0;
    	int d=gcd(a,m);
    	if(b%d)return -100;
    	else if(d==1)return BSGS(a,b,m,k%m);
    	else return exBSGS(a,b/d,m/d,k*a/d%m)+1;
    }
    ll phim=oula(m);
    ll ans=exBSGS(a%m,b%m,m);
    if(ans>phim)ans=ans%phim+phim;
    else cout<<"No Solution"<<endl;

    展开全文
  • Pollard ρ\rhoρ 算法求解离散对数问题 离散对数(DLP)问题:设有群(G,⋅)(G,\cdot)(G,⋅),α∈G\alpha \in Gα∈G是一个nnn阶元素。给定β∈<α>\beta \in \left< \alpha \right>β∈⟨α⟩,找到指数...

    Pollard ρ \rho ρ 算法求解离散对数问题

    离散对数(DLP)问题:设有群 ( G , ⋅ ) (G,\cdot) (G,) α ∈ G \alpha \in G αG是一个 n n n阶元素。给定 β ∈ < α > \beta \in \left< \alpha \right> βα,找到指数 c , 0 ≤ c ≤ n − 1 c,0\le c\le n-1 c0cn1,满足
    α c = β \alpha ^{c} =\beta αc=β前面分享过因子分解的Pollard ρ \rho ρ 算法(为了更好地理解Pollard ρ \rho ρ 离散对数算法,建议读者先看Pollard ρ \rho ρ 因子分解算法),也分享过求解离散对数问题的小步大步算法Pohlig-Hellman算法
    Pollard ρ \rho ρ 算法是启发式的算法,不是确定性的数学证明算法,它可能得到较好的解,也可能会失败,这取决于攻击者选取的初始参数。

    算法思想

    类似Pollard ρ \rho ρ 因子分解算法。为了求解出 c = log ⁡ α β c=\log_{\alpha}\beta c=logαβ,直接求是困难的,我们希望构造出一个关于 c c c的一次同余方程,通过解方程间接得到 c c c。Pollard ρ \rho ρ的因子分解算法是寻找一个碰撞 x = x ′ x=x' x=x,所以这里也想找一个碰撞。

    准备工作

    1. S 1 ∪ S 2 ∪ S 3 S_{1} \cup S_{2}\cup S_{3} S1S2S3是群 G G G的一个划分,它们元素个数大致相同。

    2. 定义函数 f : < α > × Z n × Z n → < α > × Z n × Z n f:\left< \alpha \right> \times \mathbb{Z}_{n} \times \mathbb{Z}_{n} \rarr \left< \alpha \right> \times \mathbb{Z}_{n} \times \mathbb{Z}_{n} f:α×Zn×Znα×Zn×Zn如下
      在这里插入图片描述
      并且要求构造的三元组 ( x , a , b ) (x,a,b) (x,a,b)满足 x = α a β b x=\alpha^{a}\beta^{b} x=αaβb,比如 ( 1 , 0 , 0 ) (1,0,0) (1,0,0)可以看出如果 ( x , a , b ) (x,a,b) (x,a,b)满足这个性质,则 f ( x , a , b ) f(x,a,b) f(x,a,b)也满足这个性质


    3. 在这里插入图片描述

    算法核心

    计算三元组 ( x i , a i , b i ) (x_{i},a_{i},b_{i}) (xi,ai,bi) ( x 2 i , a 2 i , b 2 i ) (x_{2i},a_{2i},b_{2i}) (x2i,a2i,b2i),直到发现 x 2 i = x i , i ≥ 1 x_{2i}=x_{i},i\ge 1 x2i=xii1。此时有
    α a i β b i = α a 2 i β b 2 i \alpha^{a_{i}}\beta^{b_{i}}=\alpha^{a_{2i}}\beta^{b_{2i}} αaiβbi=αa2iβb2i因为 β = α c \beta = \alpha ^{c} β=αc,所以有
    α a i + c b i = α a 2 i + c b 2 i \alpha^{a_{i}+cb_{i}}=\alpha^{a_{2i}+cb_{2i}} αai+cbi=αa2i+cb2i因为 α \alpha α的阶是 n n n,所以有
    a i + c b i ≡ a 2 i + c b 2 i ( m o d n ) a_{i}+cb_{i} \equiv a_{2i}+cb_{2i} \pmod{n} ai+cbia2i+cb2i(modn) c ( b 2 i − b i ) ≡ a i − a 2 i ( m o d n ) c(b_{2i}-b_{i}) \equiv a_{i} - a_{2i} \pmod{n} c(b2ibi)aia2i(modn)如果 g c d ( n , b 2 i − b i ) = 1 gcd(n,b_{2i}-b_{i}) = 1 gcd(n,b2ibi)=1,则可以解出
    c = ( a i − a 2 i ) ( b 2 i − b i ) − 1 m o d    n c=(a_{i} - a_{2i})(b_{2i}-b_{i})^{-1}\mod{n} c=(aia2i)(b2ibi)1modn如果 g c d ( n , b 2 i − b i ) ≠ 1 gcd(n,b_{2i}-b_{i}) \ne 1 gcd(n,b2ibi)=1,可以利用扩展的 g c d gcd gcd解一次线性同余方程

    例子

    问题:群 G = Z 809 ∗ G=\mathbb{Z}_{809}^{*} G=Z809 α = 89 \alpha = 89 α=89 β = 618 \beta = 618 β=618 α \alpha α的阶 n = 101 n=101 n=101。下面计算 log ⁡ α β \log_{\alpha}\beta logαβ

    1. G G G做划分:
      S 1 = { x ∈ Z 809 ∗ : x ≡ 1 ( m o d 3 ) } S 2 = { x ∈ Z 809 ∗ : x ≡ 0 ( m o d 3 ) } S 3 = { x ∈ Z 809 ∗ : x ≡ 2 ( m o d 3 ) } S_{1} = \lbrace x\in \mathbb{Z}_{809}^{*}:x\equiv 1\pmod{3} \rbrace \\ S_{2} = \lbrace x\in \mathbb{Z}_{809}^{*}:x\equiv 0\pmod{3} \rbrace \\ S_{3} = \lbrace x\in \mathbb{Z}_{809}^{*}:x\equiv 2\pmod{3} \rbrace S1={xZ809:x1(mod3)}S2={xZ809:x0(mod3)}S3={xZ809:x2(mod3)}

    2. i = 1 , 2 , ⋯ i=1,2,\cdots i=1,2,,计算三元组 ( x i , a i , b i ) (x_{i},a_{i},b_{i}) (xi,ai,bi) ( x 2 i , a 2 i , b 2 i ) (x_{2i},a_{2i},b_{2i}) (x2i,a2i,b2i),有

    i i i ( x i , a i , b i ) (x_{i},a_{i},b_{i}) (xi,ai,bi) ( x 2 i , a 2 i , b 2 i ) (x_{2i},a_{2i},b_{2i}) (x2i,a2i,b2i)
    1 ( 618 , 0 , 1 ) (618,0,1) (618,0,1) ( 76 , 0 , 2 ) (76,0,2) (76,0,2)
    2 ( 76 , 0 , 2 ) (76,0,2) (76,0,2) ( 113 , 0 , 4 ) (113,0,4) (113,0,4)
    3 ( 46 , 0 , 3 ) (46,0,3) (46,0,3) ( 488 , 1 , 5 ) (488,1,5) (488,1,5)
    4 ( 113 , 0 , 4 ) (113,0,4) (113,0,4) ( 605 , 4 , 10 ) (605,4,10) (605,4,10)
    5 ( 349 , 1 , 4 ) (349,1,4) (349,1,4) ( 422 , 5 , 11 ) (422,5,11) (422,5,11)
    6 ( 488 , 1 , 5 ) (488,1,5) (488,1,5) ( 683 , 7 , 11 ) (683,7,11) (683,7,11)
    7 ( 555 , 2 , 5 ) (555,2,5) (555,2,5) ( 451 , 8 , 12 ) (451,8,12) (451,8,12)
    8 ( 605 , 4 , 10 ) (605,4,10) (605,4,10) ( 344 , 9 , 13 ) (344,9,13) (344,9,13)
    9 ( 451 , 5 , 10 ) (451,5,10) (451,5,10) ( 112 , 11 , 13 ) (112,11,13) (112,11,13)
    10 ( 422 , 5 , 11 ) (422,5,11) (422,5,11) ( 422 , 11 , 15 ) (422,11,15) (422,11,15)

    可以发现, x 10 = x 20 x_{10} = x_{20} x10=x20
    3. 解方程 c = ( 5 − 11 ) ( 15 − 11 ) − 1 m o d    101 = 49 c=(5-11)(15-11)^{-1}\mod{101}=49 c=(511)(1511)1mod101=49。所以z在 Z 809 ∗ \mathbb{Z}_{809}^{*} Z809 log ⁡ 89 618 = 49 \log_{89}618=49 log89618=49

    注意事项

    1. 在划分群 G G G时,必须保证 1 ∉ S 2 1\notin S_{2} 1/S2,否则根据 f f f的定义,对 ∀ i ≥ 0 \forall i \ge 0 i0,都有 ( x i , a i , b i ) = ( 1 , 0 , 0 ) (x_{i},a_{i},b_{i})=(1,0,0) (xi,ai,bi)=(1,0,0)
    2. 如果初始参数设置合理,在 n n n阶循环群情况下算法复杂度为 O ( n ) O(\sqrt{n}) O(n )

    参考书籍:Stinson D , 斯廷森, 冯登国. 密码学原理与实践[M]. 电子工业出版社, 2009.

    展开全文
  • 使用指数演算法求解离散对数问题 描述 使用指数演算法求解离散对数问题(β=αamod p)。 任务是找到一个已知的β值。 您将使用p = 10930889,并对由α= 2317547形成的子组执行计算。该子组的阶次为59407。请注意,...
  • 一、离散对数问题 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,...

    一、离散对数问题
    1.定义
    a = g x    m o d    p a = g ^ x\;mod\;p a=gxmodp,记 l o g g ,    p a = x log_{g,\;p} a = x logg,pa=x,称x为a的对数(以g为底,模p)。
    给定p, g, a计算x称为离散对数问题
    2.应用之一:加密
    若g,p已知,x为私钥,求a公钥很容易,即解密;
    若g,p已知,a为公钥,求x公钥很困难(p是很大的质数更难),即破解困难(下文将描述);

    二、简单算法
    根据费马小定理( a p − 1    m o d    p = 1 a^{p - 1}\;mod\;p = 1 ap1modp=1,p是质数,整数a不是p的倍数), x = 0 x = 0 x=0 x = p − 1 x = p - 1 x=p1计算 g x    m o d    p g ^ x\;mod\;p gxmodp重复,最坏的情况下,x从0~p-2都不重复;所以,简单算法的思想就是遍历x,找到满足 a = g x    m o d    p a = g ^ x\;mod\;p a=gxmodp的x(一般a不取0,所以遍历x从1~p-1)。

    代码如下:

    #include <cstdio>
    
    int dlog(int g, int a, int p) {
        int x = 0, y = 1;
        do{
            x++;
            y *= g;
        }while((a != y % p) && (x != p));
        return x;
    }
    
    int main() {
        //测试
        int g = 2, a = 6, p = 19;
        int ans = dlog(g, a, p);
        if(ans == p) printf("无解");
        else printf("x = %d", ans);
        return 0;
    }
    

    分析:
    当a = 14时, x = 7;意味着尝试了7次;
    当a = 7时,x = 14;意味着尝试了14次;
    也就是说,执行时间与a的取值相关。

    动机:用sherwood算法使得执行时间与a无关。

    三、sherwood算法
    1.一般算法f(x)改造成Sherwood算法:

    RH(x) {
         // 用Sherwood算法计算f(x)
         n ← length[x];             // x的size为n
         r ← uniform(An);           // 随机取一元素
         y ← u(x, r);                 //将原实例x转化为随机实例y
         s ← f(y);                  // 用确定算法求y的解s
         return v(r, s);                 // 将s的解变换为x的解
    }
    

    Sherwood算法的核是找到u,v方法
    这个伪码看不明白,看下面实例

    2.计算离散对数的改造思路
    (1)构造 : y = l o g g ,    p c y=log_{g,\;p}c y=logg,pc
    其中,
    c = b ⋅ a    m o d    p c = b·a \;mod\; p c=bamodp ( b = g r    m o d    p b = g^r\;mod\;p b=grmodp)
    r对应于uniform(An),实际是从0~p-2中随机选一个数。

    l o g g ,    p b = r log_{g,\;p} b = r logg,pb=r
    l o g g ,    p a = x log_{g,\;p} a = x logg,pa=x

    (2)推导过程
    y = l o g g ,    p c = l o g g ,    p ( b ⋅ a    m o d    p ) = ( l o g g ,    p b + l o g g ,    p a )    m o d   ( p − 1 ) = ( r + x )    m o d    ( p − 1 ) y =log_{g,\;p} c=log_{g,\;p}(b·a\;mod\;p)=(log_{g,\;p} b + log_{g,\;p} a)\;mod\:(p - 1)=(r+x)\;mod\;(p-1) y=logg,pc=logg,p(bamodp)=(logg,pb+logg,pa)mod(p1)=(r+x)mod(p1)

    推导依据的定理
    l o g g ,    p ( s ⋅ t    m o d    p ) = ( l o g g ,    p s + l o g g ,    p t )    m o d   ( p − 1 ) log_{g,\;p}(s·t\;mod\;p)=(log_{g,\;p} s + log_{g,\;p} t)\;mod\:(p - 1) logg,p(stmodp)=(logg,ps+logg,pt)mod(p1)

    总结:
    y = ( r + x )    m o d    ( p − 1 ) y=(r+x)\;mod\;(p-1) y=(r+x)mod(p1),得 x = ( y − r )    m o d    ( p − 1 ) x = (y - r) \;mod \;(p - 1) x=(yr)mod(p1)

    推导过程:
    r + x = k ⋅ ( p − 1 ) + y ( k 为 一 常 系 数 ) r + x = k·(p-1) + y (k为一常系数) r+x=k(p1)+y(k) x = k ⋅ ( p − 1 ) + y − r x = k·(p-1) + y - r x=k(p1)+yr, 故 x = ( y − r )    m o d    p x = (y-r)\;mod\;p x=(yr)modp

    上述提到的:
    u指的便是,把求x转化为求y,即 y = g c    m o d    p y=g^c\;mod\;p y=gcmodp c = u ( x , r ) = b ⋅ a    m o d    p c = u(x, r)=b·a \;mod\; p c=u(x,r)=bamodp
    v指的便是,已知y后求x,即 x = ( y − r )    m o d    ( p − 1 ) x = (y - r) \;mod \;(p - 1) x=(yr)mod(p1)

    3.代码

    #include <cstdio>
    #include <random>
    #include <ctime>
    
    int dlog(int g, int a, int p) {
        int x = 0, y = 1;
        do{
            x++;
            y *= g;
        }while((a != y % p) && (x != p));
        return x;
    }
    
    int uniform(int maxN) {
        return rand() % maxN;
    }
    
    int ModularExponent(int g, int r, int p) {
        long long sum = 1;
        for(int i = 1; i<= r; i++) sum *= g;
        return sum % p;
    }
    
    
    int dlogRH(int g, int a, int p) {
        int r = uniform(p - 1);
        int b = ModularExponent(g, r, p);
        int c = (b * a) % p;
        int y = dlog(g, c, p);  //这里y可能已经无解了;
        if(y == p) return -1;
        else return (y - r + p -1) % (p - 1);   //C++,y-r可能是负数,所以要加p - 1;
    }
    
    
    int main() {
        //测试
        srand((unsigned)time(NULL));
        int g = 2, a = 6, p = 19;
        printf("确定算法的结果:\n");
        int ans1 = dlog(g, a, p);
        if(ans1 == p) printf("无解\n");
        else printf("x = %d\n", ans1);
         printf("Sherwood算法的结果:\n");
        int ans2 = dlogRH(g, a, p);
        if(ans2 == -1) printf("无解\n");
        else printf("x = %d\n", ans2);
        return 0;
    }
    
    

    4.结果
    ①g = 2, a = 6, p = 19在这里插入图片描述
    ②g = 2, a = 3, p = 7在这里插入图片描述

    展开全文
  • 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​)...
  • 离散对数求解相关算法计算方法介绍以及使用Python3实现...
  • 数学 有限域 c语言 密码学 Pollard pho算法
  • 离散对数求解实验

    2020-10-11 20:34:20
    数据如下: p= 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 g= ...
  • 离散对数问题——指数演算法 离散对数(DLP)问题:设有群(G,⋅)(G,\cdot)(G,⋅),α∈G\alpha \in Gα∈G是一个nnn阶元素。给定β∈<α>\beta \in \left< \alpha \right>β∈⟨α⟩,找到指数a,0≤a≤...
  • 根据已学过的大步小步算法,编程求解下述两个离散对数问题,并输出解。 快速幂算法 long long Quick_Multiply(long long a, long long b, long long c) //快速积 { long long ans = 0, res = a; while (b) { ...
  • 包括狭义的离散对数问题,和椭圆曲线上的点的数乘的逆运算,都算广义离散对数问题,他们的求解方案都差不多。 为了能够用统一的语言来描述,我们首先考虑,如何把广义离散对数问题,规约成狭义离散对数问题。 二,...
  • 离散对数求解算法

    千次阅读 2015-01-21 20:00:47
    ///大步小步算法 struct baby///小步算法预存的结构体定义 { long long b,j; bool operator (const baby &other)const{ return b; } }babyv[100005]; ///快速幂,x^y%mod long long q_pow(long long x,long
  • 求解离散对数问题 使用Pohlig Hellman算法求解DLP 要用到Miller Rabin素性判定、pollard rho因子分解、CRT中国剩余定理。 // 求解离散对数 // Pohlig - Hellman 算法 #include<iostream> #include<ctime&...
  • BSGS算法求解离散对数

    2020-11-16 13:24:22
    小步大步算法:BSGS(Baby Step Giant Step)BSGS(Baby\ Step\ Giant\ Step)BSGS(Baby Step Giant Step) 拔山盖世算法,百度搜索谷歌搜索算法 用来求解离散对数(即模意义下的对数)的...
  • 接下来介绍分布式算法。  让多个机子,从点集合G中不同的起点进行出发,用QD法记录的桩点会被记录到一个公共表里,然后每个机子共享数据,也就是说每个机子可以知道一个桩点,是否曾经被自己或者其它机子产生出来...
  • 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);这三个函数分别是通用的求离散对数的方法...
  • Pollard-Rho算法详解

    2016-09-12 20:19:43
    Pollard-Rho算法详解
  •  椭圆曲线离散对数问题赛题介绍如下  任何一个熟悉密码学的人基本上都会了解椭圆曲线离散对数问题。它比较普通素数域离散对数问题更具有难解性。因此相当多的公钥密码体制都构建在这个问题的基础上,如EC-...
  • 本章的意义在于对因子分解和离散对数这些问题的有效算法 。这些算法本身是有趣 的 ,并可作为 己学过的数论知识的良好应用 。此外 ,理解这些算法的效率对于在实际应用中选择密码学参数是至关重要的 文章目录因式...
  • 离散对数(Discrete Logarithm)问题是这样一个问题,它是要求解模方程 ax≡b(modm)ax≡b(modm) ...这个问题是否存在多项式算法目前还是未知的,这篇文章先从 mm 是质数开始介绍大步小步法(Baby
  • 离散对数问题,英文是Discrete logarithm Problem,有时候简写为Discrete log,该问题是十几个开放数学问题(Open Problems in Mathematics, [0.a], [0.b])中的一个。为什么要从离散对数问题说起?因为后面的内容中会...
  • 求解离散对数——BSGS算法の板子

    千次阅读 2017-02-20 17:22:54
    BSGS算法(Baby Step Gaint Step)是用于求解离散对数(即 A L ≡ B ( m o d   C ) A^L \equiv B (mod\space C) 中的最小的 L L )的一种算法。它的实质是一种优化的枚举算法,但是它通过数学分析缩小了枚举的范围...
  • 文章目录前言sagemath用法1.sagemath计算离散对数2.sagemath求逆元3.sagemath扩展欧几里得算法4.sagemath孙子定理(中国剩余定理)5.sagemath求欧拉函数6.sagemath输出表达式近似值7.sagemath素数分布(Pi(x))8.sage...
  • 公开密钥算法总是要基于一个数学上的难题。比如RSA 依据的是:给定两个素数p、q 很容易相乘得到n,而对n进行因式分解却相对困难。RSA 算法原理具体如下: 找出两个“很大”的质数:P &amp; Q  N = P * Q  ...
  • 大步小步算法用于解决离散对数问题: 求满足a^x≡y(modp)的最小自然数x,其中a、p互质,或者报告无解。 根据欧拉定理,a^ϕ(p)≡1(modp),所以,如果有解,必然有一个在[0,ϕ(p))内。为了简单起见,直接考察[0,p−1...
  • 离散对数密码学原理

    千次阅读 2020-05-04 11:52:55
    这里写自定义目录标题简介离散对数基本概念离散对数密钥的产生离散对数加密离散对数系统的数字签名 简介 1976年,Diffifie和Hellman提出了首个离散对数系统,该方法是一种密钥协商协议。1984年,ElGamal提出了基于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,967
精华内容 3,186
关键字:

小步大步算法求解离散对数问题

友情链接: Virace0.3.1chs.rar