mutiplymod.cpp

1024位的大整数进行相乘（N方）取模

#include "StdAfx.h"
#include ".\mutiplymod.h"
#include<iostream>
#include<string>
#include<stdio.h>
#define MAXLENGTH 1024

MutiplyMod::MutiplyMod(void)
: m_strOutput(NULL)
{
}

MutiplyMod::~MutiplyMod(void)
{
}


int MutiplyMod::length(char*a){
	int i;
	for(i=strlen(a)-1; i>=0;i--){
		if(a[i]>='1')
		{
			return i+1;
		}
	}
	return 0;
}


void MutiplyMod::rolleft( char *c, int length,int n ){
	int i;
	for( i=length-1;i>=n;i-- ){
		c[i]=c[i-n];
	}
	for( i=0;i<n;i++ ){
		c[i]='0';
	}
}


int MutiplyMod::cmp(char*a,char*b){
	int n,m,i;
	n=length(a);
	m=length(b);
	if(n>m)
		return 1;
	else if(n<m)
		return -1;
	else{
		for(i=m-1;i>=0;i--){
			if(a[i]!=b[i])
				return a[i]-b[i];
		}
		return 0;
	}
	

}



void MutiplyMod::turnover( char c[],int rlength ){
	int c_length=length(c);
	int i;
	for(i=0;i<c_length;i++){
		c[i]='0'+'1'-c[i];
	}

	for(i=c_length;i<rlength;i++){
		c[i]='1';
	}

	c[0]+=1;

	for(i=0;i<rlength;i++){
		c[i+1]+=(c[i]-'0')/2;
		c[i]=(c[i]-'0')%2+'0';
	}
	c[ rlength ]=0;
} 

void MutiplyMod::copyclear( char*n, char* cn,int rlength ){
	int n_length = length(n);
	int i;
	for( i=0;i<n_length;i++ ){
		cn[i]=n[i];
	}
	for( i=n_length;i<rlength;i++ ){
		cn[i]='0';
	}
}

void MutiplyMod::mod(char*a,char*n,int a_old_length){
	int i,a_length,n_length;
	char cn[MAXLENGTH];


	a_length=length(a);
	n_length=length(n);
	//There is no need to mod n
	int result = cmp(a,n);
		
	if( result<0 )
		return;
	//set a to 0
	if( result==0 ){
		for( int j=0;j<a_old_length;j++ )
			a[j]='0';
		a[a_old_length]=0;
		return;
	}
		
	cn[a_length]=0;
	
	while(cmp(a,n)>=0){
		int temp=length(a)-length(n)-1;
		copyclear( n,cn,a_length );
	
		if( temp>0 )
			rolleft( cn,a_length,temp );
	
		turnover( cn,a_length );
	
		for(i=0;i<a_length-1;i++){
			a[i]+=cn[i]-'0';
			a[i+1]+=(a[i]-'0')/2;
			a[i]=(a[i]-'0')%2+'0';
		}
		a[a_length-1]+=cn[a_length-1]-'0';
		a[a_length-1]=(a[a_length-1]-'0')%2+'0';

	}
	
	for( int i=a_length;i<a_old_length;i++ ){
		a[i]='0';
	}
	a[a_old_length]=0;
}

void MutiplyMod::reverse(char * temp){
	int i,n;
	char r[MAXLENGTH];
	n=strlen(temp);
	for(i=0;i<n;i++){
		r[i]=temp[n-1-i];
	}
	for(i=0;i<n;i++){
		temp[i]=r[i];
	}
}

void MutiplyMod::cmod(char* a,char* b,char*n,char*c){
	char b1[MAXLENGTH];
	strcpy( b1,b );
	int b_length=length(b1 );
	mod(b1,n,b_length);
	b_length=length(b1);

	int i,j;
	int a_length=length(a);
	int n_length=length(n);
	int	c_length=n_length+2;
	
	for(i=0;i<c_length;i++){
		c[i]='0';
	}
	c[c_length]=0;

	for(i=a_length-1;i>=0;i--){

		rolleft(c,c_length,1);


		// if a[i]=='0',there is no need for multiply
		if( a[i]=='1' ){
			for(j=0;j<b_length;j++){
				c[j]+=b1[j]-'0';
				c[j+1]+=(c[j]-'0')/2;
				c[j]=(c[j]-'0')%2+'0';
			}
		}

		
		if(c[b_length]=='2'){
		// in this case ,n_length>=b_length	,c_length=n_length+2	
			for( int j=b_length;j<n_length+1;j++ ){
				if( c[j]=='2' ){
					c[j+1]+=1;
					c[j]='0';
				}
					
			}
		}
		mod(c,n,c_length);
	}

}

void MutiplyMod::showcmod(char* a,char* b,char*n,char*c){
	char b1[MAXLENGTH];
	char temp[MAXLENGTH];
	strcpy( b1,b );
	int b_length=length(b1 );
	mod(b1,n,b_length);
	b_length=length(b1);

	int i,j;
	int a_length=length(a);
	int n_length=length(n);
	int	c_length=n_length+2;
	
	for(i=0;i<c_length;i++){
		c[i]='0';
	}
	c[c_length]=0;

	for(i=a_length-1;i>=0;i--){

		rolleft(c,c_length,1);
		// if a[i]=='0',there is no need for multiply
		if( a[i]=='1' ){
			for(j=0;j<b_length;j++){
				c[j]+=b1[j]-'0';
				c[j+1]+=(c[j]-'0')/2;
				c[j]=(c[j]-'0')%2+'0';
			}
		}

		
		if(c[b_length]=='2'){
		// in this case ,n_length>=b_length	,c_length=n_length+2	
			for( int j=b_length;j<n_length+1;j++ ){
				if( c[j]=='2' ){
					c[j+1]+=1;
					c[j]='0';
				}
					
			}
		}
		mod(c,n,c_length);

		(*this->m_strOutput).Append( _T("B* ") );
		for( int j=a_length-1;j>=i;j-- ){
			*this->m_strOutput+=a[j];
		}
		(*this->m_strOutput).Append( _T(" Mod N:\r\n") );
		strcpy( temp,c );
		temp[ this->length( temp ) ]=0;
		this->reverse( temp );
		(*this->m_strOutput).Append(temp);
		(*this->m_strOutput).Append( "\r\n\r\n");


	}

}