/* rep12.c
平方剰余記号を３通りの計算法で計算する
　・定義通り
　・Euler の規準
　・Jacobi 記号

gcc rep12.c -lm
*/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include"crypto050706.h"  // crypto050706.h をインクルードして用いよ

// Euler の規準
int eulercriterion(int i, int p)
{
	int e=powermod(i,(p-1)/2,p);	// 平方剰余記号 = i^((p-1)/2) mod p
	return e>1 ? e-p : e;		// p-1 は -1 に読み替える
}

main()
{
	int p;		// 素数の法
	int r[65536];	// mod p での平方根を格納する配列
	int q,e,j,i,h,x;

	p=3;
	while(1){
		if(primeq(p)){

			// 定義通りの計算  
			// r[i] には初期値として -1 を登録しておき、
			// x = 1,...,(p-1)/2 について
			// i = x^2 mod p  となるとき r[i] = x に書き換える

   			h=(p-1)/2;
			for(i=1;i<p;i++) r[i]=-1;
			for(x=1;x<=h;x++) r[modmul(x,x,p)]=x;
  
			// 出力
			printf("法 p = %d\n",p);
			for(i=1;i<p;i++){
				e=eulercriterion(i,p);	// Euler の規準
				j=jacobi(i,p);		// Jacobi 記号
				if(r[i]!=-1){		// 平方根を持てば平方剰余
					q=1;
					printf("%3d  %2d  %2d  %2d  ( sqrt(%3d) = %3d )\n",i,q,e,j,i,r[i]);
				}
				else{			// 平方根を持たなければ平方非剰余
					q=-1;
					printf("%3d  %2d  %2d  %2d\n",i,q,e,j);
				}
				if(q!=e || e!=j || j!=q){
					printf("ERROR\n");
					exit(0);
				}
			}
			getchar();
		}
		p+=2;
	} 
}