verify.h

RSA算法的VC实现

#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