#ifndef Verify_h
#define Verify_h
#include "Numbertheory.h"
#include <fstream.h>
#include <stdlib.h>
#include <time.h>
template<class Type>
int Solovay_Strassen(Type a,Type n){//素性檢驗：返回1為素數，0為合數；
	Type x;//x=
	x=Jacobi(a,n);
	if(x==0)return 0;
	Type b=(n-1)/2;
	Type y=Square_and_Multiply(a,b,n);
	if(MOD(x,n)==y)
		return 1;
	else return 0;////我的直覺是對的；
}

template< class Type>
int Verify(Type n,	Type& bogusprime,Type& T){//檢驗是素數則返回1；
    bogusprime=0;
    T=0;
	Type temp;
	Type a;
	for(a=1;a<n;a++)//這里應該從2開始好一點
	{

		temp=Inverse(a,n);
		if(temp!=0){//判斷求逆是否存在，即a是否屬于Zn_star
			T++;
		//cout<<Solovay_Strassen(a,n)<<endl;
		if(Solovay_Strassen(a,n)==1)bogusprime++;
		}

	}
	//if(bogusprime>T/2)
	if (bogusprime==T)
		return 1;
	else 
	{
		return 0;
	}
}
template< class Type>
int Answer(Type m,Type n){//事件b
	//連續回答m次n是一個素數，成功返回1，失敗返回0；
	Type i=0;
	Type r=1;
	int flg=1;
	srand((unsigned)time(NULL));
	for(;i<m;i++)//i=0
	{
		r=rand()%n;//這里有大大的問題啊；需要嗎？有可能模成0；
		while(r==0)
			r=rand()%n;
        if(Solovay_Strassen(r,n)==0){
			flg=0;
			break;
		}
	}
	return flg;
}
template< class Type>
int Verifyfile(char* primefile,Type m){
	int flg=1;
	//long bogusprime,T;這里就將就著了
	ifstream fin(primefile);
	if(!fin){
		cout<<primefile<<" cannot be opened!"; exit(1);
	}
	Type p;
	int r;
	while(fin){
		fin>>p;
		r=Answer(m,p);
			//Verify(p,bogusprime,T);
		if(r==0)
		{
			cout<<p<<" is  not a prime!"<<endl;//not
			flg=0;
		}

		//else cout<<p<<" is a prime!"<<endl;
	}
	return flg;
	fin.close();
}
template< class Type>
void Pr_ab(Type m,Type N){//檢驗pr[a|b];
	Type i;
	Type T=0;
	Type E=0;
	Type num=N;
	if(!Odd(N))//!=1
		N=N+1;
	for(i=num;i<2*num;i++)//檢驗范圍為N－2N的奇整數；//這里也有錯；
	{
		N=N+2;
		if(Answer(m,N)==1){
			T++;
		if(FactoringAlgorithm(N)!=1)
			E++;
		}
	}
	cout<<m<<";"<<E<<"/"<<T<<";";//"m="Pr[a|b]=<<"(ln(n)-2)/(ln(n)-2+pow(2,m+1))="
	cout<<(log(N)-2)/(log(N)-2+pow(2,m+1))<<endl;
}
template< class Type>
void Pr_ba(Type m,Type N){//檢驗pr[b|a];
	Type i;
	Type T=0;
	Type E=0;
	Type num=N;
	if(!Odd(N))//!=1
		N=N+1;
	for(i=num;i<2*num;i++)//檢驗范圍為N－2N內的奇合數；
	{
		N=N+2;
		if(FactoringAlgorithm(N)!=1){//這里與上面Pr_ab順序剛好相反；
			T++;
		if(Answer(m,N)==1)
			E++;
		}
	}
	cout<<m<<";"<<E<<"/"<<T<<";";
	cout<<1/pow(2,m)<<endl;
}
template< class Type>
void Prime_Generator(Type low,Type h,Type m){//low－h為范圍，m為詢問Solovay_Strassen次數；
	Type max;
	Type i=low;
	if(i<3)i=3;
	if(Odd(i)!=1)
		i++;
	Type T=0;
	for(;i<=h;i+=2)
		if(Answer(m,i)==1)
		{
			T++;
			max=i;
			cout<<i<<" ";//這個弄到文件里面比較好；
			if(T%10==0)
				cout<<endl;
		}
	return ;//返回最大素數；
}
template< class Type>
Type Prime_Single(Type low,Type h,Type m){//low－h為范圍，m為詢問Solovay_Strassen次數；
	//產生單個素數
	Type i=low;
	if(i<3)i=3;
	if(Odd(i)!=1)
		i++;
	for(;i<=h;i+=2)
		if(Answer(m,i)==1)
    return i;//返回這個范圍內找到的第一個素數；
		return 3;
}
template< class Type>
void Prime_Double(Type low,Type h,Type m,Type& p,Type& q){//low－h為范圍，m為詢問Solovay_Strassen次數；
	//產生兩個素數給RSA用
	Type i=low;
	if(i<3)i=3;
	if(Odd(i)!=1)
		i++;
	p=1511;//默認；
	q=2003;//默認；
	for(;i<=h;i+=2)
		if(Answer(m,i)==1)
		{
			p=i;//返回這個范圍內找到的第一個素數；
			break;
		}
	for(i+=2;i<=h;i+=2)
		if(Answer(m,i)==1)
		{
			q=i;//返回這個范圍內找到的第二個素數；
			break;
		}
}
#endif