/* crypto060608.h */

int gcd(int a, int b)
{
  return b==0 ? abs(a): gcd(b,a%b);
}

int euclid(int a, int b, int *x, int *y)
{
	int q,r,d0,x0,y0;
	if(b==0){
		if(a>=0){
			*x=1;
			*y=0;
			return(a);
		}
		else{
			*x=-1;
			*y=0;
			return(-a);
		}
	}
	else{
		q=a/b;
		r=a-q*b;
		d0=euclid(b,r,&x0,&y0);
		*x=y0;
		*y=x0-q*y0;
		return(d0);
	}
}

int mod(int a, int m)
{
	int b=a%m;
	return b<0 ?  b+m: b;
}

int modadd(int a, int b, int m)
{
	return mod(a+b,m);
}

int modsub(int a, int b, int m)
{
	return mod(a-b,m);
}

int modmul(int a, int b, int m)
{
	return mod(a*b,m);
}

int modinv(int a, int m)
{
	int d,x,y;
	d=euclid(a,m,&x,&y);
	if(d!=1){
		printf("法と互いに素ではありません\n");
		exit(1);
	}
	else return mod(x,m);
}

int moddiv(int a, int b, int m)
{
	return modmul(a,modinv(b,m),m);
}

int primeq(int n)
/* n が素数のとき 1、そうでないとき 0 を返す */
{
	int i,m;
	if(n<2) return 0;
	if(n<=3) return 1;
	if(n%2==0) return 0;
	m=(int)sqrt(n);
	for(i=3;i<=m;i+=2) if(n%i==0) return 0;
	return 1;
}

int powermod(int a0, int e0, int m)
{
	int e=e0,a=a0,b,x;
	if(e<0){
		a=modinv(a,m);
		e=-e;
	}
	x=1;
	b=a;
	while(e>0){
		if(e%2) x=modmul(x,b,m);
		b=modmul(b,b,m);
		e/=2;
	}
	return x;
}

int encrypt(int x, int e, int n)
/* RSA暗号の公開鍵 e,n を用いて平文 x を暗号文に変換する */
{
	return powermod(x,e,n);
}

int decrypt(int y, int d, int n)
/* RSA暗号の公開鍵 n と秘密鍵 d を用いて暗号文 y を復号する */
{
	return powermod(y,d,n);
}

int eulerfunction(int m)
/* Euler 関数の値を返す */
{
	int a,c=0;
	if(m<=0){
		printf("法が自然数ではありません。\n");
		exit(1);
	}
	for(a=0;a<m;a++) if(gcd(a,m)==1) c++;
	return c;
}