#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>

//////////////////////////測試素數(shù) 

int TestPrime(int p)
{
	int k=sqrt(p);
	int i;
	for (i=2;i<=k;i++) 
	{
		if (p%i==0) {return 0;break;}
	}
	if(i>k) return 1;
}

//////////////////////////g(x)方程 HOHO 

int function(int x,int a2,int a1,int a0)
{
    int y;
    y=(a2*x*x+a1*x+a0);
    return y;
}

//////////////////////////隨機獲取一個不大于n的數(shù) 

int gec(int n)
{
	int e;
	
		e=rand()%n;
		
	return e;
}

///////////////////////////隨機獲取不大于m的素數(shù) 

int gecp(int m)
{
    int p;
    do
    {
    p=rand()%m;
    if(TestPrime(p)==1) break;
	}
    while(1);
    return p;
}

///////////////////////////求逆函數(shù)   

int Athwart(int e,int n)
{
	int n1=n;
	int n2=e;
	int b1=0;
	int b2=1;
	int t;
	int q;
	int r;
	do
	{
		q=n1/n2;
		r=n1-q*n2;
		if (r==0) break;
		n1=n2;
		n2=r;
		t=b2;
		b2=b1-q*b2;
		b1=t;
	}
	while (1);
	if (n2!=1)
		return (0);   
	if (b2<0)
		return (b2+n);
	else
		return (b2);

}


///////////////////////////求分母，并取正 


int intgere(int x,int y,int p)
{
  int z;
  if(x>y) z=x-y;
  else z=x-y+p;
  return z;
}


////////////////////////// 求b函數(shù)（還原K函數(shù)里面有用）


int calcuB(int x1,int x2,int x3,int p)
{
    int a,b,c;
    b=Athwart(intgere(x1,x3,p),p)%p;
    c=Athwart(intgere(x2,x3,p),p)%p;
    a=(b*c*x1*x2)%p;
    return a;

}
//////////////////////////還原K的函數(shù) 

int calcuK(int x1,int x2,int x3,int y1,int y2,int y3,int p)
{
    int b1,b2,b3,k;
    b1=calcuB(x2,x3,x1,p);
    b2=calcuB(x1,x3,x2,p);
    b3=calcuB(x2,x1,x3,p);
    k=((b1*y1)%p+(b2*y2)%p+(b3*y3)%p)%p;
    return k;
}

int main()
{
    //srand(time(NULL));
    int a0,a1,a2;
    int k;
    int n,m;
    int p;      
    int x[5];   //////存放x的值 
    int xx[3];  //////存放x的隨機下標(biāo) 
    int y[5];   //////存放y的值 
    int i,j;
    
    ///////////////素數(shù)p的大小范圍 
    m=300;
    
    
    ////////////////獲取素數(shù)p 
    p=gecp(m);
    printf("Output p: %d\n",p);
    
    /////////////////n的取值范圍不大于p 
    n=p;
    
    
    //////////////////隨機獲取一個g(x)函數(shù)的系數(shù) 
    a1=gec(n);
    a2=gec(n);
    a0=gec(n);
    
    
    
    ///////////////////隨機選取5個子密鑰對 
    x[0]=gec(n);
    for(i=1;i<5;i++)
    {
     x[i]=gec(n);
     for(j=0;j<i;j++)
     if(x[i]==x[j]) {i--;break;}
    }
    for(i=0;i<5;i++)
    {
     y[i]=function(x[i],a2,a1,a0);
    }
    
    
    ////////////////輸出密鑰對 HOHO 
    printf("\nGenerate Keys: \n");
    for(i=0;i<5;i++)
    printf("(%d,%d) \n",x[i],y[i]);
    
    ///////////////輸出g(x)函數(shù)的系數(shù) 
    printf("\nOutput g(x): a0=%d,a1=%d,a2=%d\n",a0,a1,a2);
    
    
    //////////////隨機選取3對密鑰對并輸出，（XX數(shù)組存放x數(shù)組的下標(biāo) ） 
    printf("\nChoose s keys:\n");
    xx[0]=gec(n)%5;
    for(i=1;i<3;i++)
    {
     xx[i]=gec(n)%5;
     for(j=0;j<i;j++)
     if(xx[i]==xx[j]) i--;
    }
    for(i=0;i<3;i++)
    printf("(%d,%d) \n",x[xx[i]],y[xx[i]]);
    
    //////////////計算k并且輸出  
    printf("\nOutput k:");
    k = calcuK(x[xx[0]],x[xx[1]],x[xx[2]],y[xx[0]],y[xx[1]],y[xx[2]],p);
    printf("%d\n",k);
    
    ///////////////結(jié)束! 
    system("pause");
    return 0;
}