#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <malloc.h>
/************************************************************************
* RSA加密解密函数,自己建立的大数运算库
* 缺点:生成pq,n=p*q 无法确定密钥n的长度
************************************************************************/
#define MAX 100
#define LEN sizeof(struct slink) //结构体slink占用内存空间的大小
void sub(int a[MAX],int b[MAX] ,int c[MAX] );
struct slink
{
int bignum[MAX]; /*bignum[98]用来标记正负号,1 正,0 负 bignum[99]来标记实际长度*/
struct slink *next; //bignum存储的是随机生成的大数,next是指向后面的指针
};
/*/--------------------------------------建立的大数运算库-------------------------------------*/
//解决大数问题,借助数组来存储数字
void print( int a[MAX] )
{
int i;
for(i=0;i<a[99];i++)
printf("%d",a[a[99]-i-1]);
printf("\n\n");
return;
}
//大数比较函数
int cmp(int a1[MAX],int a2[MAX])
{
int I1, I2;
int i;
I1=a1[99];
I2=a2[99];
if (I1>I2)
return 1;
if (I1<I2)
return -1;
for(i=(I1-1);i>=0;i--)
{
if (a1[i]>a2[i])
return 1 ;
if (a1[i]<a2[i])
return -1;
}
return 0;
}
//大数类型转换函数
void mov(int a[MAX],int *b)
{
int j;
for(j=0;j<MAX;j++)
b[j]=a[j];
return ;
}
//大数乘积函数 c=a1*a2
void mul(int a1[MAX],int a2[MAX],int *c)
{
int i,j;
int y;
int x;
int z;
int w;
int I1, I2;
I1=a1[MAX-1];
I2=a2[MAX-1];
if (a1[MAX-2]=='-'&& a2[MAX-2]=='-')
c[MAX-2]=0;
else if (a1[MAX-2]=='-')
c[MAX-2]='-';
else if (a2[MAX-2]=='-')
c[MAX-2]='-';
for(i=0;i<I1;i++)
{
for(j=0;j<I2;j++)
{
x=a1[i]*a2[j];
y=x/10;
z=x%10;
w=i+j;
c[w]=c[w]+z;
c[w+1]=c[w+1]+y+c[w]/10;
c[w]=c[w]%10;
}
}
w=I1+I2;
if(c[w-1]==0)w=w-1;
c[MAX-1]=w;
return;
}
//大数相加函数
void add(int a1[MAX],int a2[MAX],int *c)
{
int i,l1,l2;
int len,temp[MAX];
int k=0;
l1=a1[MAX-1];
l2=a2[MAX-1];
if((a1[MAX-2]=='-')&&(a2[MAX-2]=='-'))
{
c[MAX-2]='-';
}
else if (a1[MAX-2]=='-')
{
mov(a1,temp);
temp[MAX-2]=0;
sub(a2,temp,c);
return;
}
else if (a2[MAX-2]=='-')
{
mov(a2,temp);
temp[98]=0;
sub(a1,temp,c);
return;
}
if(l1<l2)len=l1;
else len=l2;
for(i=0;i<len;i++)
{
c[i]=(a1[i]+a2[i]+k)%10;
k=(a1[i]+a2[i]+k)/10;
}
if(l1>len)
{
for(i=len;i<l1;i++)
{
c[i]=(a1[i]+k)%10;
k=(a1[i]+k)/10;
}
if(k!=0)
{
c[l1]=k;
len=l1+1;
}
else len=l1;
}
else
{
for(i=len;i<l2;i++)
{
c[i]=(a2[i]+k)%10;
k=(a2[i]+k)/10;
}
if(k!=0)
{
c[l2]=k;
len=l2+1;
}
else len=l2;
}
c[99]=len;
return;
}
//大数相减函数
void sub(int a1[MAX],int a2[MAX],int *c)
{
int i,l1,l2;
int len,t1[MAX],t2[MAX];
int k=0;
l1=a1[MAX-1];
l2=a2[MAX-1];
if ((a1[MAX-2]=='-') && (a2[MAX-2]=='-'))
{
mov(a1,t1);
mov(a2,t2);
t1[MAX-2]=0;
t2[MAX-2]=0;
sub(t2,t1,c);
return;
}
else if( a2[MAX-2]=='-')
{
mov(a2,t2);
t2[MAX-2]=0;
add(a1,t2,c);
return;
}
else if (a1[MAX-2]=='-')
{
mov(a2,t2);
t2[MAX-2]='-';
add(a1,t2,c);
return;
}
if(cmp(a1,a2)==1)
{
len=l2;
for(i=0;i<len;i++)
{
if ((a1[i]-k-a2[i])<0)
{
c[i]=(a1[i]-a2[i]-k+10)%10;
k=1;
}
else
{
c[i]=(a1[i]-a2[i]-k)%10;
k=0;
}
}
for(i=len;i<l1;i++)
{
if ((a1[i]-k)<0)
{
c[i]=(a1[i]-k+10)%10;
k=1;
}
else
{
c[i]=(a1[i]-k)%10;
k=0;
}
}
if(c[l1-1]==0)/*使得数组C中的前面所以0字符不显示了,如1000-20=0980--->显示为980了*/
{
len=l1-1;
i=2;
while (c[l1-i]==0)/*111456-111450=00006,消除0后变成了6;*/
{
len=l1-i;
i++;
}
}
else
{
len=l1;
}
}
else
if(cmp(a1,a2)==(-1))
{
c[MAX-2]='-';
len=l1;
for(i=0;i<len;i++)
{
if ((a2[i]-k-a1[i])<0)
{
c[i]=(a2[i]-a1[i]-k+10)%10;
k=1;
}
else
{
c[i]=(a2[i]-a1[i]-k)%10;
k=0;
}
}
for(i=len;i<l2;i++)
{
if ((a2[i]-k)<0)
{
c[i]=(a2[i]-k+10)%10;
k=1;
}
else
{
c[i]=(a2[i]-k)%10;
k=0;
}
}
if(c[l2-1]==0)
{
len=l2-1;
i=2;
while (c[l1-i]==0)
{
len=l1-i;
i++;
}
}
else len=l2;
}
else if(cmp(a1,a2)==0)
{
len=1;
c[len-1]=0;
}
c[MAX-1]=len;
return;
}
//大数取模函数 c=a mod b
void mod(int a[MAX],int b[MAX],int *c)/*/c=a mod b//注意:经检验知道此处A和C的数组都改变了。*/
{
int d[MAX];
mov (a,d);
while (cmp(d,b)!=(-1))/*/c=a-b-b-b-b-b.......until(c<b)*/
{
sub(d,b,c);
mov(c,d);/*/c复制给a*/
}
return ;
}
//大数相除函数 试商法c=t/b w为t mod b
void divt(int t[MAX],int b[MAX],int *c ,int *w)/*//试商法//调用以后w为a mod b, C为a div b;*/
{
int a1,b1,i,j,m;/*w用于暂时保存数据*/
int d[MAX],e[MAX],f[MAX],g[MAX],a[MAX];
mov(t,a);
for(i=0;i<MAX;i++)
e[i]=0;
for(i=0;i<MAX;i++)
d[i]=0;
for(i=0;i<MAX;i++) g[i]=0;
a1=a[MAX-1];
b1=b[MAX-1];
if (cmp(a,b)==(-1))
{
c[0]=0;
c[MAX-1]=1;
mov(t,w);
return;
}
else if (cmp(a,b)==0)
{
c[0]=1;
c[MAX-1]=1;
w[0]=0;
w[MAX-1]=1;
return;
}
m=(a1-b1);
for(i=m;i>=0;i--)/*341245/3=341245-300000*1--->41245-30000*1--->11245-3000*3--->2245-300*7--->145-30*4=25--->25-3*8=1*/
{
for(j=0;j<MAX;j++)
d[j]=0;
d[i]=1;
d[MAX-1]=i+1;
mov(b,g);
mul(g,d,e);
while (cmp(a,e)!=(-1))
{
c[i]++;
sub(a,e,f);
mov(f,a
评论2