/* L06.c 
p を素数とするとき mod p の原始根を求める

1, a, a^2, ... が mod p の 0 以外の全ての数を作り出すとき
a を mod p の原始根（生成元）と呼ぶ。

精度上 15 ビットくらいが限界
*/

#include<stdio.h>
#include<stdlib.h>

/* 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 primetest(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;
}

main()
{
	int k,a,p,n,x,c;
	char w[32];
	srand(time(NULL));  /* 乱数の初期化 */

	printf("---------------------------------------------\n");
	printf("p を素数とするとき mod p の原始根を求めます。\n");
	printf("---------------------------------------------\n");
	printf("ビット数を入力してください（ 0 で終了 ）: \n");
	scanf("%d",&k);
	if(k <= 0) exit(1);
	gets(w);	// 入力のゴミ取り

	// k ビットの素数 p を生成
	p = randbit(k);
	while(!primetest(p)) p++;

	c = 0;
	printf("\n");
	printf("mod %d の原始根 :\n",p);
	for(a = 1; a < p; a++){
		n = 1;
		x = a;
		// x = a^n mod p を順々に計算してゆく
		while(x != 1){
			x = modmul(x, a, p);
			n++;
		}
		// 初めて a^n ≡ 1 mod p となる n が p - 1 ならば原始根
		if(n == (p - 1)){
			printf("  %d\n",a);
			c++;
			if(c % 10 == 0){
				printf("[ 続行 : Enter / 終了 : 0 ]\n");
				gets(w);
				if(strlen(w) > 0) exit(1);
			}
		}
	}
}

/* 実行例

---------------------------------------------
p を素数とするとき mod p の原始根を求めます。
---------------------------------------------
ビット数を入力してください（ 0 で終了 ）:
11

mod 1597 の原始根 :
  11
  13
  29
  33
  34
  37
  38
  39
  42
  44
[ 続行 : Enter / 終了 : 0 ]

*/