离散pallard_p.cpp

用vc编写的实现密码学中Pollard p离散对数算法的小程序。

#include<iostream.h>
#include<stdio.h>
#include<math.h>
typedef __int64 INT;


//求gcd
INT gcd(INT a,INT b){
	if(a<0) a=-a;
	if(b<0) b=-b;
	INT a0=a,b0=b,t0=0,t=1,q=a0/b0,r=a0-q*b0;
	while(r>0){
		INT temp=(t0-q*t)%a;
		t0=t;
		t=temp;
		a0=b0;
		b0=r;
		q=a0/b0;
		r=a0-q*b0;
	}
//	if(b0!=1) { printf("%d 没有模%d 的逆\n",b,a); t=-1;}// 
//	else if(t<0) t=t+a;
//	return t;
	r=b0;
	return r;
}


INT multiplicative_inverse(INT a,INT b){
	if(b<0) b=(b%a)+a;
	INT a0=a,b0=b,t0=0,t=1,q=a0/b0,r=a0-q*b0;
	while(r>0){
		INT temp=(t0-q*t)%a;
		t0=t;
		t=temp;
		a0=b0;
		b0=r;
		q=a0/b0;
		r=a0-q*b0;
	}
	if(b0!=1) { printf("%d 没有模%d 的逆\n",b,a); t=-1;}// 
	else if(t<0) t=t+a;
	return t;
}

//数字转换为二进制数
INT num_to_bit(INT x,INT A[]){
	INT B[20];
	INT mul=2;
	INT j=0;
	while(x!=0){
		B[j]=x%mul;
		x=x/mul;
		j++;
	}
	for(INT i=0;i<j;i++) A[i]=B[j-i-1];
	return j;
}


//平方乘
INT square_and_multiply(INT x,INT b,INT n){//x的 b次方 mod n
	INT z=1;
	INT l;
	INT c[64];
	l=num_to_bit(b,c);
	for(INT i=0;i<l;i++){
		z=z*z%n;
		if(c[i]==1) z=(z*x)%n;
	//	if(z<0) z=z+n;
	}
	return z;
}

class element{
public:
	INT x;
	INT a;
	INT b;
	int operator != (element &y){ if(x==y.x) return 0;else return 1;}
};

element f(element z,INT r,INT ba,INT p,INT n){
	element y;
	if(z.x%3==1){ y.x=(ba*z.x)%p;	y.a=z.a;	y.b=(z.b+1)%n;	}
	else if(z.x%3==0){ y.x=(z.x*z.x)%p;	y.a=(2*z.a)%n;	y.b=(2*z.b)%n;	}
	else { y.x=(r*z.x)%p;	y.a=(z.a+1)%n;	y.b=z.b;	}
	return y;
}

INT pollard_p(INT n,INT r,INT ba,INT p){
	element y1,y2;
	INT count=1;
	y1.x=1;
	y1.a=0;
	y1.b=0;
	y1=f(y1,r,ba,p,n);
	y2=f(y1,r,ba,p,n);
	while(y1!=y2){
		y1=f(y1,r,ba,p,n); 
		y2=f(y2,r,ba,p,n);
		y2=f(y2,r,ba,p,n); 
		count++;}
	INT t;
//	if(y1.b>y2.b) 	
		t=y2.b-y1.b;
//	else t=y1.b-y2.b;
	if(gcd(t,n)!=1) return -1;
	else{
        printf("a1=%d\n",y1.a);
        printf("a2=%d\n",y2.a);
        printf("b1=%d\n",y1.b);
        printf("b2=%d\n",y2.b);
        printf("x=%d\n",y1.x);
		printf("i=%d\n",count);
		INT m=multiplicative_inverse(n,y2.b-y1.b);
		return ((y1.a-y2.a+n)*m)%n;
	}
}

		
	

void main(){
	INT n=0,r=0,p=0,ba=0,y;
	printf("输入p：");
	scanf("%d",&p);
	printf("输入n：");
	scanf("%d",&n);
	printf("输入a：");
	scanf("%d",&r);
	printf("输入b：");
	scanf("%d",&ba);
   y=pollard_p(n,r,ba, p);
	 if(y==-1)
		printf("无解!");
	 else 	
		printf("%d\n",y);

}