mimo.cpp

本代码能实现密码学领域中的大数幂模运算

#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#define maxnum 800
//////////////////////////////////////////////////////////////////////////////////////////////////
void init(char * str)//初始化数组，用0表示
{
	int i;
	for(i=0;i<=maxnum-2;i++)
		str[i]='0';
	str[maxnum-1]='\0';
}
//////////////////////////////////////////////////////////////////////////////////////////////////
void format(char * str1,char * r)//先把str1值给strr,然后再给r
{
	char *p,strr[maxnum];
	int i=0;
	p=str1;
	while(*p!='\0')
	{
		if (*p!='0')
			break;
		p++;
	}
	while(*p!='\0')
	{
		strr[i]=*p;
		p++;
		i++;
	}
	if(i==0)
	{
		*r='0';
		*(r+1)='\0';
		return;
	}
	strr[i]='\0';
	strcpy(r,strr);
}
//////////////////////////////////////////////////////////////////////////////////////////////////
void multi(char * str,char ch, int i,char * r)
{
	char *p,*q;
	int mul1,mul2,a1=0,a2=0,n=0;
	q=r+maxnum-1-i;
	p=str;
	while(*p!='\0') p++;
	while(p>str){
		p--;q--;
		mul1=(*p-'0')*(ch-'0')+a1;
		a1=mul1/10;
		mul1%=10;		
		mul2=(*q-'0')+mul1+a2;
		a2=mul2/10;
		mul2%=10;
		*q=mul2+'0';
	}
	if(a1!=0||a2!=0){
		q--;
		*q=*q+a1+a2;
	}
}
//////////////////////////////////////////////////////////////////////////////////////////////////
void multiply(char * str1,char * str2,char * r)
{
	char *p;
	int i;
	init(r);
	p=str2;
	while(*p!='\0') p++;
	i=0;
	while(p>str2){
		p--;
		if(*p!='0'){
			multi(str1,*p,i,r);
		}
		i++;
	}
	format(r,r);
}

//////////////////////////////////////////////////////////////////////////////////////////////////
void sub1(char *str1,char *str2,char * r)
{
	char *p,*q,re[maxnum];
	int a1=0,add,i=0;
	p=str1;
	while(*p!='\0') {p++;  i++;}
	q=str2;
	while(*q!='\0') q++;
    re[i]='\0';
	while(p>str1&&q>str2){
		p--;  q--;
		add=(*p-'0')-(*q-'0')+a1;
		if(add<0){
			a1=-1;
			add=(add+10)%10;
		}
		else{
			a1=0;
			add%=10;
		}
		i--;	
    	re[i]=add+'0';
		
	}
    while(p>str1){
		p--;
		add=(*p-'0')+a1;
		if(add<0){
			a1=-1;
			add=(add+10)%10;
		}
		else{
			a1=0;
			add%=10;
		}
		i--;	
    	re[i]=add+'0';
	}
	format(re,r);
}

//////////////////////////////////////////////////////////////////////////////////////////////////
int com(char *str1,char *str2)
{
	int len1,len2;
	len1=strlen(str1);
	len2=strlen(str2);
	if(len1>len2) return 1;
	if(len1<len2) return -1;
	do{
		if((*str1)>(*str2)) return 1;
		if((*str1)<(*str2)) return -1;
		str1++;
		str2++;
	}while(*str1!='\0');
	return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////
int div(char *str1,char *str2,char * r)////str1与str2相除
{ 
	int i,q=0;
	if(com(str1,str2)<0){
		strcpy(r,str1);
		return 0;
	}
	i=com(str1,str2);
	while(i==1||i==0){
		sub1(str1,str2,r);///str1-str2=strs
		strcpy(str1,r);
		q++;
	    i=com(str1,str2);
	}
	if(*r==0){
			*r='0';
			*(r+1)='\0';}
	return q;
}
//////////////////////////////////////////////////////////////////////////////////////////////////
void divide(char *str1,char *str2,char * r,int f)
{
	char *p,*q,a[maxnum],b[maxnum],r1[maxnum];
	int len,len2,i=0;	
	if(com(str1,str2)<0){
		if(f==1)
		{
			b[0]='0';b[1]='\0';
			strcpy(r,b);
		}
		else strcpy(r,str1);	
		return;
	}
	len=strlen(str2);
	len2=strlen(str1);
    if(len==len2){
		strcpy(a,str1);
		goto aa;
	}
	strncpy(a,str1,len);
	a[len]='\0';
	p=str1+len;
	do{
		b[i]=div(a,str2,r1)+'0';
		strcpy(a,r1);
		len=strlen(a);
		q=a+len;
		*q=*p;
		*(q+1)='\0';
		format(a,a);
		p++;
	    i++;
	}while(*p!='\0');
aa:	b[i]=div(a,str2,r1)+'0';
	b[++i]='\0';
	if(f==1)
		format(b,r);
	else if(f==2){
		if(*r1==0){
			*r1='0';
			*(r1+1)='\0';
		}else
		strcpy(r,r1);
	}
}
char * func(char *str1,char * b,char *str2)
{
	int a[maxnum],i=0;
	char r[maxnum]={'1'},temp[maxnum],m[maxnum],er[maxnum]={'2'};
	for(;;){
		divide(b,er,m,2);
		a[i]=*m-'0';
		i++;
		divide(b,er,b,1);
		if(*b=='0')
			break;
	}
	i--;
	for(;i>=0;)
	{
		if(a[i]!=1)
		{
            multiply(r,r,er);
     		divide(er,str2,r,2);	
		}
		else
		{
		    multiply(r,r,er);
			multiply(er,str1,temp);
     		divide(temp,str2,r,2);	
		}
		i--;
	}   
	if(*r==0){
		*r='0';
		*(r+1)='\0';
	}
	return r;
}

     
void main()
{
	char str1[maxnum],str2[maxnum],str3[maxnum],*x;
	printf("请输入底数：\n");
	scanf("%s",str1);
	printf("请输入模数：\n");
	scanf("%s",str2);
	printf("请输入指数：\n");
	scanf("%s",str3);
	x=func(str1,str3,str2);
	printf("运算结果为：\n%s\n",x);	
}