#?include
//求最大公約數(shù)
int?Gcd（int?aint?b）
{
	int?s[50]q[50];
	if（a>b）
	{
		s[0]=a;
		s[1]=b;
	}
	else
	{
		s[0]=a;
		s[1]=b;
	}
	for（int?i=1;i<100;i++）
	{
		s[i+1]=s[i-1]%s[i];
		q[i]=s[i-1]/s[i];
		if（s[i+1]==0）?break;
	}
	return?s[i];
}

void?main（）
{
/***************Key?generation***************/
	int?pgkb=1;
	//Choose?a?prime?p
	printf（“Choose?a?prime?p:“）;
	scanf（“%d“&p）;
	printf（“Choose?a?generator?g:“）;
	scanf（“%d“&g）;
	//Select?a?random?int?k?as?the?private?key
	printf（“請輸入私鑰k:“）;
	scanf（“%d“&k）;
	for（int?i=0;i	{
		b*=g;
		b%=p;
	}
	printf（“Pubilc?key?is?（%d%d%d）\n“bgp）;
	printf（“Private?key?is?（%d）\n“k）;
/*********