pollard p-1.cpp

大数计算器

#include<iostream>
#include<string>
using namespace std;



int Max(int x, int y)//求最大值
{
	if(x>y)
		return x;
	else return y;}

int compare(string A,string B)///比较字符串形式的数的大小
{
	int lenA,lenB;
	int dxd=0;

	lenA=A.length();
	lenB=B.length();
	if(lenA>lenB)
		dxd=1;
	if(lenA<lenB)
		dxd= -1;
	if(lenA==lenB) 
	{
		if(A>B)
			dxd= 1;
		if(A<B)
			dxd=-1;
		if(A==B)
			dxd=0;}
	return dxd;}



string Add(string a, string b)///加法
{
	int lena,lenb,round,i,j;  
	int numa[100]={0},numb[100]={0},sum[100]={0},sumrev[100]={0},carry[100]={0};//！！如计算的位数较多要修改此行中所有数组空间的大小
	string result=" ";
	lena=a.length();  //求字符串长度
	lenb=b.length();
	round=Max(lena,lenb);
	for(i=0;i<lena;i++)       //将字符串中的每个数字分别作为数组的一个元素
		numa[i]=a[lena-1-i]-48;
	for(i=0;i<lenb;i++)
		numb[i]=b[lenb-1-i]-48;
	for(i=0;i<round;i++)
	{
		sum[i]=carry[i]+numa[i]+numb[i];  //每一位的加法运算
		if(sum[i]>10)
		{carry[i+1]=1;
		sum[i]=sum[i]-10;}}
	j=0;                      //j为sum[1024]中经过计算的元素个数
	if(carry[round]=1)
        j=round;
	else j=round-1;
	

	for(i=0;i<100;i++)             //!!修改处
	{sumrev[i]=(sum[99-i]+48);}     //把数字转化成相应字符的ASCII码
  
	for(i=30-j;i<100;i++)         //!!修改处
	{result=result+char(sumrev[i]);}  //强制转换成字符串格式
	cout<<result<<endl;
	return 0;
}






string Sub(string a,string b)//减法
{
	int numa[100]={0},numb[100]={0},carry[100]={0},dif[100]={0},difrev[100]={0};//！！如计算的位数较多要修改此行中所有数组空间的大小

	int lena,lenb,round,i,j;    

	string result=" ";

	lena=a.length();
	lenb=b.length();
    round=Max(lena,lenb);
	for(i=0;i<lena;i++)
		numa[i]=a[lena-1-i]-48;
	for(i=0;i<lenb;i++)
		numb[i]=b[lenb-1-i]-48;

	for(i=0;i<round;i++)                      
	{if(lena>lenb||((lena==lenb)&&(a>b)))    //第一个数大于第二个数时
	   {if(numa[i]-numb[i]<0)
	      carry[i+1]=1;
	      dif[i]=carry[i+1]*10+numa[i]-numb[i]-carry[i];}    //每一位的减法运算
	 if(lena<lenb||((lena==lenb)&&(a<=b)))    //第一个数小等于第二个数时
	    {if(numb[i]-numa[i]<0)
   	   	  carry[i+1]=1;
	      dif[i]=carry[i+1]*10+numb[i]-numa[i]-carry[i];}}

	 for(i=0;i<100;i++)           //!!修改处
		 difrev[i]=dif[100-1-i]+48;      //数字转化为ASCII码
	 j=0;
	 while(difrev[j]==48)
         j=j+1;
	 for(i=j;i<100;i++)               //!!修改处
		 result=result+char(difrev[i]);
	 cout<<result<<endl;
	 return 0;
	}


string Div(string a,string b)//求整数商的函数
{
	string ti,mid;
	mid=a;ti="0";
	do
	{
		mid=Sub(mid,b);    //调用减法函数
		ti=Add(ti,"1");     //记录进行减法操作的次数，即为商
	}
	while(compare(mid,b)!=-1);
	return ti;
}


string Mul(string mula,string mulb)    //乘法（调用加法，错位相加）
{
     int num[200]={0};

	int lena,lenb,i,j,k;    

	string sum=" ";
	string pro=" ";
  
	lena=mula.length();
	lenb=mulb.length();
    
    if(compare(mula,mulb)>=0)         //比较哪个数位数比较多，位数小的作为循环次数
	{
	 for(i=0;i<lenb;i++)
		num[i]=mulb[lenb-1-i]-48;}

    if(compare(mula,mulb)==-1)
	{for(i=0;i<lena;i++)
       	num[i]=mula[lena-1-i]-48;}
	 
	for(i=0;i<lenb;i++)
	{
	 for(j=0;j<num[i];j++)
		 sum=Add(sum,mula);
	 for(k=0;k<i;k++)             //错位相加，高位后面前添0再相加
	 {
		 sum=sum+"0";}
		 pro=Add(sum,pro);
	}
	cout<<pro<<endl;
	return 0;
	}
	 

string Rem(string tot,string m)   //取余（多次调用减法）
{
	string remind=" ";
	string mid=" ";

	if(compare(tot,m)==1)
	{
		do
		{mid=Sub(tot,m);
		 tot=mid;}
		while(compare(tot,m)==1);
		remind=tot;
	}

	if(compare(tot,m)==0)
		remind="0";
	if(compare(tot,m)==-1)
	    remind=tot;
	cout<<remind<<endl;
	return 0;
	}


string Pow(string a,string exp)  //乘方，用平方乘的方法，调用乘法函数
{
    string result="1";
	do                              //每执行一次指数要减2
	{
		result=Mul(result,Mul(result,result));
	    exp=Sub(exp,"2");
	}
	while(compare(exp,"2")==1);
	if(compare(exp,"1")==0)
	{
		result=Mul(result,result);
		cout<<result<<endl; 
	}
	if(compare(exp,"0")==0)
		cout<<result<<endl;
    return 0;  
}

string Inv(string ini,string m)     //求逆（扩展欧几里德算法p136）
{
	string r,temp,a0,b0,q,t,t0;
	a0=ini;b0=m;t0="0";t="1";
	q=Div(a0,b0);
	r=Rem(ini,m);
    while(compare(r,"0")==1)
	{
		temp=Rem(Sub(t0,Mul(q,t)),ini);
		t0=t;
		t=temp;
		a0=b0;
		b0=r;
		q=Div(a0,b0);
		r=Sub(a0,Mul(q,b0));
	}
	if(b0!="1")
		cout<<"所求的逆不存在"<<endl;
	else return t;
}





string gcd(string a,string b)  //求最大公约数
{
	string temp=" ";
	if (compare(a,b)==-1)
	{
		temp=a;
		a=b;
		b=temp;
	}
	while(Rem(a,b)!="0")
	{
		temp=Rem(a,b);
		a=b;
		b=temp;
	}
	return b;
}

string pol(string num,string ran)   //Pollard的p-1算法
{
	string a="2";
	string j="2";
	string d=" ";
	do
	{
		a=Rem(Pow(a,j),num);
		j=Add(j,"1");
	}
	while(compare(j,ran)==-1);
	d=gcd(Sub(a,"1"),num);
	if((compare(d,"1")==-1)&&(compare(d,num))==1)
		return d;
	else cout<<"failure"<<endl;
	    return 0;
}



int main() //主程序
{
	string num,ran;
	cout<<"请输入要分解的（奇）整数n和一个预先指定的“界”B"<<endl;
	cin>>num>>ran;
	pol(num,ran);
	return 0;
}