/* L05.c 
ユークリッドのアルゴリズム拡張版を用いた
法演算での逆数計算
*/

#include<stdio.h>
#include<stdlib.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 r0=a,r1=b,r2,x0=1,x1=0,x2,y0=0,y1=1,y2,q;
	while(r1!=0){
		q=r0/r1;
		r2=r0-q*r1;
		x2=x0-q*x1;
		y2=y0-q*y1;
		// 番号を振り替える
		r0=r1;
		r1=r2;
		x0=x1;
		x1=x2;
		y0=y1;
		y1=y2;
	}
	if(r0<0){
		r0=-r0;
		x0=-x0;
		y0=-y0;
	}
	*x=x0;
	*y=y0;
	return(r0);
}

/* a を法 n の数に取り直す */
int mod(int a, int n)
{
	int b=a%n;
	return b<0 ? b+n : b;
	// C言語では a<0, n>0 のときの符号は処理系に依存
}

/* 法 n での a+b */
int modadd(int a, int b, int n)
{
	return mod(a+b,n);
}

/* 法 n での a-b */
int modsub(int a, int b, int n)
{
	return mod(a-b,n);
}

/* 法 n での a*b */
int modmul(int a, int b, int n)
{
	return mod(a*b,n);
}

/* k ビットの乱数 */
int randbit(int k)
{
	int x=1;
	while(k>1){
		x=2*x+rand()%2;
		k--;
	}
	return x;
}

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


main()
{
	int a,n,x,k;
	srand(time(NULL));  /* 乱数の初期化 */

	printf("----------------------------------------\n");
	printf("法 n での a の逆数 x を求めます。\n");
	printf("----------------------------------------\n");
	printf("ビット数を入力してください（ 0 で終了 ）: \n");
	scanf("%d",&k);
	if(k<=0) exit(1);
	n=randbit(k);
	a=rand()%n;
	while(gcd(a,n) != 1) a=mod(a+1,n);
	printf("n = %d\n",n);
	printf("a = %d\n",a);
	x=modinv(a,n);
	printf("x = %d\n",x);
	printf("検算 : a x ≡ %d\n",modmul(a,x,n));
}

/* 実行例

----------------------------------------
法 n での a の逆数 x を求めます。
----------------------------------------
ビット数を入力してください（ 0 で終了 ）:
14
n = 9099
a = 1306
x = 1693
検算 : a x ≡ 1

*/