#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 2050
#define L 6
#define LM 2
int compare(int a[],int b[]){
int i;
if(a[0]>b[0])
return 1;
else if(a[0]<b[0])
return -1;
else{
for(i=a[0];i>0;i--){
if(a[i]>b[i])
return 1;
else if(a[i]<b[i])
return -1;
}
return 0;
}
}
void copy(int a[],int b[]){
int i;
for(i=0;i<N;i++)
a[i]=b[i];
}
void fix(int a[]){
int i;
for(i=1;i<a[0]+1;i++){
if(a[i]<0){
a[i]+=2;
a[i+1]--;
}
if(a[i]>1){
a[i]-=2;
a[i+1]++;
}
}
}
void len(int a[]){
int i;
for(i=a[0]+1;i>0;i--)
if(a[i]!=0){
a[0]=i;
return;
}
a[0]=0;
}
int maxlen(int a[],int b[]){
if(a[0]>=b[0])
return a[0];
else return b[0];
}
void plus(int a[],int b[]){
int i;
for(i=1;i<=a[0]||i<=b[0];i++)
a[i]+=b[i];
a[0]=maxlen(a,b);
fix(a);
len(a);
}
void minus(int a[],int b[]){
int i;
if(compare(a,b)==1||compare(a,b)==0){
for(i=1;i<=a[0]||i<=b[0];i++)
a[i]-=b[i];
a[0]=maxlen(a,b);
fix(a);
len(a);
}
}
void mod(int a[],int b[]){
int i;
while(a[0]>b[0]){
for(i=0;i<b[0];i++)
a[a[0]-b[0]+i]-=b[i+1];
fix(a);
len(a);
}
if(compare(a,b)==1||compare(a,b)==0)
minus(a,b);
len(a);
}
void mul(int a[],int b[],int n[]){
int i,j,k,*c;
c=new int[N];
for(i=0;i<N;i++)
c[i]=0;
c[0]=N-2;
mod(a,n);
mod(b,n);
for(i=1;i<=b[0];i++){
if(b[i]==1){
for(j=i,k=1;k<=a[0];j++,k++){
c[j]+=a[k];
c[0]=maxlen(c,a);
fix(c);
len(c);
mod(c,n);
c[0]=N-2;
}
}
}
for(i=0;i<N;i++)
a[i]=c[i];
len(a);
delete []c;
}
void div(int a[],int b[],int c[]){
int i;
for(i=0;i<N;i++)
c[i]=0;
c[0]=N-2;
while(a[0]>b[0]){
for(i=0;i<b[0];i++)
a[a[0]-b[0]+i]-=b[i+1];
c[a[0]-b[0]]++;
fix(a);
fix(c);
len(a);
}
if(compare(a,b)==1||!compare(a,b)){
c[1]++;
minus(a,b);
fix(c);
}
len(a);
len(c);
}
void quick(int a[],int q[],int c[],int n[]){
int i,*a1,*q1;
a1=new int[N];
q1=new int[N];
for(i=0;i<N;i++){
a1[i]=a[i];
q1[i]=q[i];
}
mod(a1,n);
mod(q1,n);
for(i=2;i<N;i++)
c[i]=0;
c[0]=1;
c[1]=1;
for(i=q1[0];i>0;i--){
mul(c,c,n);
if(q1[i]==1)
mul(c,a1,n);
}
delete[]a1;
delete[]q1;
}
void randomarray(int a[],int n){//产生随机数,位数为n。
int i;
for(i=1;i<n;i++){
a[i]=(rand()/(RAND_MAX/2));
}
a[0]=n;
a[n]=1;
}
int get_kandq(int q[])
{
int i,k=0;
for(i=1;i<=q[0];i++){
if(q[i]==0)
k++;
else break;
}
q[0]-=k;
for(i=1;i<=q[0];i++){
q[i]=q[i+k];
q[i+k]=0;
}
return k;
}
int text(int n[],int q[],int k){
int *a,*c,b[N]={2,0,1},a1[N]={1,1},*n1,i,j;
a=new int[N];
n1=new int[N];
c=new int[N];
for(i=0;i<N;i++)
a[i]=c[i]=n1[i]=0;
for(i=0;i<=n[0];i++)
n1[i]=n[i];
minus(n1,a1);
do{
randomarray(a,n[0]);
}while(!compare(a,n));
mod(a,n);
quick(a,q,c,n);
if(compare(c,a1)==0){
delete[]a;
delete[]c;
delete[]n1;
return 1;
}
for(j=0;j<k;j++){
if(compare(c,n1)==0){
delete[]a;
delete[]c;
delete[]n1;
return 1;
}
mul(c,c,n);
}
delete[]a;
delete[]c;
delete[]n1;
return 0;
}
void get_prime(int n[],int m){
int i,*n1;
int k,j,b[N]={2,0,1};
n1=new int[N];
for(i=0;i<N;i++)
n1[i]=0;
randomarray(n,m);
n[1]=1;
for(i=0;i<N;i++)
n1[i]=n[i];
n1[1]=0;
k=get_kandq(n1);
for(j=0;j<10;j++){
if(text(n,n1,k)==1)
continue;
else{
plus(n,b);
for(i=0;i<N;i++)
n1[i]=n[i];
n1[1]=0;
k=get_kandq(n1);
j=-1;
}
}
delete[]n1;
for(i=0;i<n[0]+1;i++)
printf("%d ",n[i]);
printf("\n");
}
void Euclid(int a[],int b[]){
int *n,*n1,*n2,*n3,*n4,*n5,i,z1[N]={1,1},z0[N]={0};
n=new int[N];
n1=new int[N];
n2=new int[N];
n3=new int[N];
n4=new int[N];
n5=new int[N];
for(i=0;i<N;i++){
n[i]=a[i];
n1[i]=b[i];
n2[i]=n3[i]=n4[i]=n5[i]=0;
}
n3[0]=n3[1]=1;
n5[0]=n5[1]=1;
for(i=0;;i++){
if(!(i%2)){
div(n,n1,n4);
mul(n5,n4,a);
plus(n2,n5);
copy(n5,n2);
}
else{
div(n1,n,n4);
mul(n5,n4,a);
plus(n3,n5);
copy(n5,n3);
}
if(!compare(z1,n1)){
copy(a,n5);
break;
}
else if(!compare(z1,n)){
minus(a,n5);
break;
}
else if(!compare(z0,n)||!compare(z0,n1)){
delete[]n;
delete[]n1;
delete[]n2;
delete[]n3;
delete[]n4;
delete[]n5;
printf("没有逆元\n");
exit(0);
}
}
delete[]n;
delete[]n1;
delete[]n2;
delete[]n3;
delete[]n4;
delete[]n5;
}
void RSA(int p[],int q[],int n[]){
int i,*MAX;
MAX=new int[N];
for(i=0;i<N;i++)
MAX[i]=1;
MAX[0]=2048;
printf("P: \n");
get_prime(p,L);
printf("Q: \n");
get_prime(q,L);
copy(n,p);
mul(n,q,MAX);
printf("N: \n");
for(i=0;i<n[0]+1;i++)
printf("%d ",n[i]);
printf("\n");
delete[]MAX;
}
void Enc(int n[],int C[]){
int *M,*MAX,i;
int e[N];
e[0]=17;
e[17]=e[1]=1;
M=new int[N];
MAX=new int[N];
for(i=0;i<N;i++)
MAX[i]=0;
randomarray(M,LM);
for(i=0;i<M[0]+1;i++)
printf("%d ",M[i]);
printf("\n");
quick(M,e,C,n);
for(i=0;i<C[0]+1;i++)
printf("%d ",C[i]);
printf("\n");
delete[]M;
delete[]MAX;
}
void Dec(int p[],int q[],int n[],int C[]){
int e[N]={0},*d,a1[N]={1,1},M[N]={0},i;
int *MAX,*p1,*q1;
MAX=new int[N];
p1=new int[N];
q1=new int[N];
d=new int[N];
for(i=0;i<N;i++)
MAX[i]=1;
copy(p1,p);
copy(q1,q);
minus(p1,a1);
minus(q1,a1);
MAX[0]=2048;
e[0]=17;
e[17]=e[1]=1;
copy(d,p1);
mul(d,q1,MAX);
Euclid(d,e);
quick(C,d,M,n);
for(i=0;i<M[0]+1;i++)
printf("%d ",M[i]);
printf("\n");
delete[]MAX;
delete[]d;
delete[]p1;
delete[]q1;
}
void main(){
int n[N]={0},p[N]={0},q[N]={0},C[N]={0};
srand((int)time(0));
RSA(p,q,n);
Enc(n,C);
Dec(p,q,n,C);
}