/* rep08.c 
gcc rep08.c -o rep08 -lm
*/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include "crypto050609.h"	// crypto050609.h はホームページから download せよ

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;
}

int elementorder(int a, int m)
/* mod m での a の乗法位数を返す */
{
	int x=a,i=1;
	while(x!=1){
		x=modmul(a,x,m);
		i++;
	}
	return i;
}

int primitiveroot(int p)
/* 素数 p を法とする原始根を返す */
{
	int g=1;
	while(elementorder(g,p)!=(p-1)) g++;
	return g;
}

main()
{
	int a,n,p;

	printf("*****  mod n の各剰余類の乗法位数  *****\n");
	for(n=20;n<=30;n++){
		printf("n = %d\n",n);
		printf("Euler(n) = %d\n",eulerfunction(n));
		for(a=1;a<n;a++)
			if(gcd(a,n)==1)
				printf("%2d mod n の乗法位数 = %2d\n",a,elementorder(a,n));
		getchar();
	}

	printf("*****  mod p の原始根  *****\n");
	for(p=3;p<=100;p++)
		if(primeq(p))
			printf("mod %2d の原始根 : %2d\n",p,primitiveroot(p));
}