pohlig_hellman.cpp

在VC中编程实现密码学中Pohlig－Hellman算法的小程序

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

//数字转换为二进制数
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;
}

//求逆
int multiplicative_inverse(int b,int a){//b-1 mod 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 pohlig_hellman(int n, int p,int a,int b,int q,int c,int A[]){

	int j=0;
	int bp=b;
	int q1=1;
	while(j<c){
	//	int t1=square_and_multiply(q,j+1,n);
		q1=q1*q;
		int t2=n/q1;
		int f1=square_and_multiply(bp,t2,p);
		int i=0;
		int m=square_and_multiply(a,i*n/q,p);
		while(f1!=m && i<q){
			i++;
			m=square_and_multiply(a,i*n/q,p);
		}
		if(f1==m) A[j]=i;
		else { printf("失败\n"); return -1;}

	//	int l2=square_and_multiply(q,j,p);
		int l2=q1/q;
		int l3=square_and_multiply(a,A[j]*l2,p);
		int l1=multiplicative_inverse(l3,p);
		bp=(bp*l1)%p;
		j=j+1;
	}

	return j;

}

void main(){
	int p=0,q=0,a=0,b=0,c=0,n=0;
//	int A[1000];
	int A[100];
	for(int k=0;k<100;k++) A[k]=0;
	printf("输入p:");
	scanf("%d",&p);
	n=p-1;
	printf("输入a:");
	scanf("%d",&a);
	printf("输入b:");
	scanf("%d",&b);
	printf("输入q:");
	scanf("%d",&q);
	printf("输入c:");
	scanf("%d",&c);
	int y=0;
	y=pohlig_hellman(n,p,a,b, q, c,A);
//	y=text(n);
	printf("hg\n");
	for( k=0;k<c;k++){
	//	int z=A[k];
	//	int m=&z;
//		printf("c%d = %d\n",k,A[k]);
		cout<<"c"<<k<<"= "<<A[k]<<endl;
	}
	//if(y!=-1){

	//}
//	return;
}