shanks.cpp

用VC实现非平凡的时间－存储平衡算法Shanks算法的小程序

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


//求逆
INT multiplicative_inverse(INT a,INT 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;
}


//平方乘
INT square_and_multiply(INT x,INT c[],INT n,INT l){//x bmod n b->C
	INT z=1;
	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 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 shanks(INT n, INT a, INT b){
	INT m=0;
	m=INT(sqrt(n))+1;
	INT L1[1000],L2[1000];
	for(INT j=0;j<m;j++){
		INT f=m*j;
		INT C[1000];
		INT l=num_to_bit(f,C);
		L1[j]=square_and_multiply(a,C,n,l);
	}		
	INT t=multiplicative_inverse(n,a);	
	for(INT i=0;i<m;i++){
		INT C[1000];
		INT l=num_to_bit(i,C);	
		INT k=square_and_multiply(t,C,n,l);
	
		L2[i]=(b*k)%n;
	}
	for(j=0;j<m;j++)
	{
		for(i=0;i<m;i++)
			if(L1[j]==L2[i])
			{
				printf("j=%d\n",j);
				printf("i=%d\n",i);
				printf("L1[j]=%d\n",L1[j]);
				return (m*j+i)%n;
			}
	}
	return -1;
}


 void main() {
	 INT a=0,b=0,n=0,y;
	printf("输入n:");
	 scanf("%d",&n);
	 printf("输入a:");
	 scanf("%d",&a);
	 printf("输入b:");
	 scanf("%d",&b);
	// n=p-1;
///	 m=INT(sqrt(n))+1;
	 //INT L1[1000],L2[1000];
	 y=shanks(n, a, b);
	 printf("%d\n",y);

 }