/*
實驗八  計算模逆與模冪
(一)實驗內容
1．	對于兩個不超過216的正整數d與n，編寫計算d-1 (mod n) 的程序；
2．	對于三個不超過216的正整數a、e與n，編寫計算ae (mod n) 的程序。
在上述程序基礎上寫出下列程序：
（1）	對給定的10000以內數判定其是否為素數；
（2）	進行ElGamal體制的加密與簽名。
(二)實驗要求
1.	判定n=2579是否為素數；
2.	選擇p=2579，a=2，a=765，算出b=aa (mod p)=         。
設消息m=1299，若秘密選定隨機整數x=853，按ElGamal體制：
i）試求出加密m的密文，并正確還原明文；ii）試對m作出簽名，并進行驗證。

*/

#include<stdio.h>	//頭文件
#include<stdlib.h>
#include<math.h>
#include<time.h>

int  moni(int d,int n){	//求模逆
	int i,a[100][2],temp=0,vk,u=0,t;	//數組a用來存各個狀態
	a[0][0]=n;	//初始阿a0=n,a1=d
	a[1][0]=d;
	for(i=2;a[i-1][0]!=0;i++){	//計算
		a[i][0]=a[i-2][0]%a[i-1][0];
		a[i-1][1]=(int)a[i-2][0]/a[i-1][0];
	}
	temp=i-3;	//長度
	if(a[temp+1][0]!=1)	//若最后一項不為1則不互素，無模逆
		printf("%d和%d不互素\n",a[1][0],a[0][0]);
	else{	//計算模逆
		for(i=1;i<=temp+1;i++)//a[i-1][0]!=0;i++)
			printf("%d=%d*%d+%d\n",a[i-1][0],a[i][1],a[i][0],a[i+1][0]);
		for(i=1,vk=-a[1][1],u=1;i<temp;i++){	//計算！
			t=vk;
			vk=u-vk*a[i+1][1];
			u=t;
		}
		a[0][1]=vk;
		printf("Vk=%d",vk);
		if(vk<0){vk=n+vk;printf("=%d\n",vk);}
		else putchar('\n');
	}
	return vk;
}

int momi(int a,int e,int n){	//求模冪，從左向右
	int i,ab[100],temp=0,tempn;	//數組ab用來存儲2進制
	for(i=0,temp=e;temp!=0;i++){	//求2進制
		ab[i]=(int)temp%2;
		temp=(int)temp/2;
	}
	tempn=i-1;
	printf("%d的2進制為：",e);
	for(i=tempn;i>=0;i--)
		printf("%d",ab[i]);
	putchar('\n');
	for(i=tempn-1,temp=a;i>=0;i--){	//計算模冪
		temp=temp*temp%n;
		if(ab[i]==1)
			temp=temp*a%n;
	}	printf("\n結果為:%d\n",temp);
	return temp;
}

int jianyan(int n){	//檢驗素數
	int i,temp,s=0,t,a,b;
	temp=n-1;	//求2的最大次項
	while(temp%2!=1){
		temp=temp/2;
		s++;
	}
	printf("%d-1=2(%d)*%d\n",n,s,temp);
	t=temp;
	srand(time(NULL));
	a=rand()%n;	//隨即生成a
	printf("a=%d\n",a);
	b=momi(a,temp,n);	//開始計算
	if(b==1){
		printf("====%d可能是素數\n",n);
		return 1;
	}
	for(i=0;i<s;i++){	//如滿足條件則為素數
		if(b==-1||b==n-1){
			printf("====%d可能是素數\n",n);
			return 1;
		}
		if(b!=-1)b=momi(b,2,n);
	}
	printf("====%d是復合數\n",n);
	return 0;	
}

int ElGamal(int m,int x){	//ElGamal體制的加密與簽名
	int p=2579,a=2,e=765,c,b,c1,c2,k;
	char s;
	srand(time(NULL));
	printf("1.加密 2.解密:");
	scanf("%d",&c);
	getchar();
	if(c==1){	//加密
		printf("手動輸入？Y/N:");	//輸入初態
		scanf("%c",&s);
		if(s=='Y'||s=='y'){
			printf("請輸入 p a e:");
			scanf("%d %d %d",&p,&a,&e);
		}
		else{
			while(jianyan(p)==0||p<1000)
				p=rand()%10000;
			printf("隨機整數為:");
			scanf("%d",&e);
			if(m<=0||m>p-1){
				printf("錯誤:m范圍錯誤");
				return 0;
			}
		}
		b=momi(a,e,p);	//開始計算
		printf("公開密鑰:(%d,%d,%d)\n",p,a,b);
		c1=momi(a,x,p);
		c2=m*momi(b,x,p)%p;
		printf("加密!!結果為:(%d,%d)",c1,c2);
	}
	if(c==2){	//解密
		printf("請輸入公鑰(p,a,b):");
		scanf("%d %d %d",&p,&a,&b);
		printf("密鑰為:");
		scanf("%d",&e);
		k=x*moni(momi(m,e,p),p)%p;
		printf("解密!!結果為:%d\n",k);
	}
	return 0;
}

void main(){
	int c,a,d,e,m,n,x,temp;
	printf("1.求模逆\n2.求模冪\n3.檢驗素數\n4.ElGamal\n");
	scanf("%d",&c);

	switch(c){
		case 1 :printf("求模逆：請輸入 d & n :");
				scanf("%d %d",&d,&n);
				temp=moni(d,n);
				break;
		case 2 :printf("求模冪：請輸入 a & e & n :");
				scanf("%d %d %d",&a,&e,&n);
				temp=momi(a,e,n);
				printf("\n結果為:%d\n",temp);
				break;
		case 3 :printf("檢驗素數：請輸入需要檢驗的數:");
				scanf("%d",&d);
				temp=jianyan(d);
				break;
		case 4 :printf("ElGamal：請輸入 m & x:");
				scanf("%d %d",&m,&x);
				temp=ElGamal(m,x);
				break;
		default :printf("輸入錯誤\n");
	}

}

/*
1.求模逆
2.求模冪
3.檢驗素數
4.ElGamal
3
檢驗素數：請輸入需要檢驗的數:2579
2579-1=2(1)*1289
a=2428
1289的2進制為：10100001001
結果為:2578
====2579可能是素數

1.求模逆
2.求模冪
3.檢驗素數
4.ElGamal
4
ElGamal：請輸入 m & x:1299 853
1.加密 2.解密:1
手動輸入？Y/N:y
請輸入 p a e:2579 2 765
765的2進制為：1011111101
結果為:949
公開密鑰:(2579,2,949)
853的2進制為：1101010101
結果為:435
853的2進制為：1101010101
結果為:2424
加密!!結果為:(435,2396)

1.求模逆
2.求模冪
3.檢驗素數
4.ElGamal
4
ElGamal：請輸入 m & x:435 2396
1.加密 2.解密:2
請輸入公鑰(p,a,b):2579 2 949
密鑰為:765
765的2進制為：1011111101
結果為:2424
2579=1*2424+155
2424=15*155+99
155=1*99+56
99=1*56+43
56=1*43+13
43=3*13+4
13=3*4+1
4=4*1+0
Vk=-599=1980
解密!!結果為:1299
*/