#include?
#include?“iostream“
#include?“gmp.h“
#include?“ctime“
#pragma?comment（linker?“/NODEFAULTLIB:MSVCRTD.LIB“）
#pragma?comment（lib?“gmp.lib“）
#pragma?comment（lib?“gmpDebug.lib“）
using?namespace?std;

const?int?TestCase?=?5;
#define?PRIME_PROBABILITY?20
#define?PRIME_BITLENGTH?1024

void?CreateBigPrime（mpz_t?mpzPrimeint?bits）//int?Probability）
{
	int?ilast_rand=0;
	char?*char_rand?=?new?char?[bits+1];
	char_rand[0]?=?‘1‘;
	char_rand[bits]?=?‘\0‘;
	mpz_init（mpzPrime）;

	do
	{
		for（i=1;i		{
			if（rand（）==last_rand）
				cout<<“SRAND?ERROR!?--short?time!?same?rand?number!“<			last_rand?=?rand（）;
			char_rand[i]?=?‘0‘+（0x01&last_rand）;
		}
			
		mpz_set_str（mpzPrimechar_rand2）;
		mpz_nextprime（mpzPrimempzPrime）;
	}while（0==mpz_probab_prime_p（mpzPrimePRIME_PROBABILITY））;
	
	return;
}


//a?^?b?%?n
void?BigIntergerMod（mpz_t?a?mpz_t?b?mpz_t?n?mpz_t?&res）
{
	mpz_t?temp;
	mpz_t?k;
	mpz_t?bb;
	mpz_init（temp）;
	mpz_init（k）;
	mpz_init（bb）;
	mpz_set（bbb）;//bb?=?b;
	//res?=?1;
	mpz_set_ui（res1）;
	mpz_mod（tempan）;//temp?=?a?%?n;
	while?（mpz_cmp_ui（bb0））//bb?>?0??
	{
		mpz_mod_ui（k?bb?2）;//?k?=?bb?%?2;
		if?（mpz_cmp_ui（k?0））//k?==?1?
		{
		//	res?=?res?*?temp?%?n;
			mpz_mul（res?res?temp）;
			mpz_mod（res?res?n）;
		}
		//bb?=?bb?>>?1;
		mpz_fdiv_q_ui（bb?bb?2）;
		//temp?=?temp?*?temp?%?n;
		mpz_mul（temp?temp?temp）;
		mpz_mod（temptemp?n）;
		
	}
	mpz_clear（temp）;
	mpz_clear（k）;
	mpz_clear（bb）;
}


//判斷n是否為素數，若為合數返回true，若可能為素數返回false
bool?TestPrime（mpz_t?n）
{
	mpz_t?a?k?q?j?judge?n_sub?res;
	mpz_init（a）;
	mpz_init（k）;
	mpz_init（q）;
	mpz_init（j）;
	mpz_init（judge）;
	mpz_init（n_sub）;
	mpz_init（res）;
	gmp_randstate_t?state;
	gmp_randinit_default（state）;
	mpz_sub_ui（n_sub?n?1）;//n_sub?=?n?-?1;
	mpz_set（q?n_sub）;//q?=?n?-?1;
	mpz_mod_ui（judge?q?2）;//?judge?=?q?%?2;
	//?n-1?=?2^k*q
	while?（!mpz_cmp_ui（judge0））//judge?=?0
	{
		mpz_fdiv_q_ui（q?q?2）;//q?=?q?/?2;
		mpz_add_ui（k?k?1）;//?k++;
		mpz_mod_ui（judge?q?2）;//?judge?=?q?%?2;
	}
//	gmp_printf（“k=%Zd\n“k）;
//	gmp_printf（“q=%Zd\n“q）;
	mpz_urandomm（astaten）;//產生隨機數1?	mpz_sub_ui（a?a?1）;//a?=?a?-?1;
	BigIntergerMod（a?q?n?res）;//res?=?a?^?q?%?n
	if?（!mpz_cmp_ui（res?1）||!mpz_cmp（res?n_sub））//res?==?1||res?==?n?-?1
		return??false;
	else
	{
		mpz_add_ui（jj1）;//j++;
		for?（?;mpz_cmp（j?k）;?mpz_add_ui（j?j?1））//j?=?1..k-1
		{
			mpz_mul（res?res?res）;//res?=?res?^?2;
			mpz_mod（res?res?n）;//res?=?res?%?n;
			if?（?!mpz_cmp_ui（res?1））//res?==?1
				return?true;
			if?（?!mpz_cmp（res?n_sub）?）//?res?==?n-1
				return?false;
		}
	}
	mpz_clear（a）;
	mpz_clear（k）;
	mpz_clear（q）;
	mpz_clear（j）;
	mpz_clear（judge）;
	mpz_clear（n_sub）;
	mpz_clear（res）;
	return?true;
}

//Miller?Rabin素數測試，是素數返回true，否則返回false
bool?MRTest（mpz_t?n）
{
	mpz_t?temp;
	mpz_init（temp）;
	mpz_mod_ui（temp?n?2）;
	if?（!mpz_cmp_ui（temp

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2014-12-15?10:53??Gmp_test\
?????目錄???????????0??2014-12-15?10:52??Gmp_test\BigIntergerMod\
?????文件????????4428??2014-12-10?00:51??Gmp_test\BigIntergerMod\BigIntergerMod.dsp
?????文件?????????534??2014-12-09?22:50??Gmp_test\BigIntergerMod\BigIntergerMod.dsw
?????文件???????50176??2014-12-15?10:52??Gmp_test\BigIntergerMod\BigIntergerMod.ncb
?????文件???????48640??2014-12-15?10:52??Gmp_test\BigIntergerMod\BigIntergerMod.opt
?????文件????????1417??2014-12-15?10:52??Gmp_test\BigIntergerMod\BigIntergerMod.plg
?????目錄???????????0??2014-12-15?10:52??Gmp_test\BigIntergerMod\Debug\
?????文件??????385089??2014-12-15?10:52??Gmp_test\BigIntergerMod\Debug\BigIntergerMod.exe
?????文件??????455440??2014-12-15?10:52??Gmp_test\BigIntergerMod\Debug\BigIntergerMod.ilk
?????文件?????2073320??2014-12-09?22:53??Gmp_test\BigIntergerMod\Debug\BigIntergerMod.pch
?????文件?????1106944??2014-12-15?10:52??Gmp_test\BigIntergerMod\Debug\BigIntergerMod.pdb
?????文件???????44442??2014-12-15?10:52??Gmp_test\BigIntergerMod\Debug\main.obj
?????文件???????74752??2014-12-15?10:52??Gmp_test\BigIntergerMod\Debug\vc60.idb
?????文件??????110592??2014-12-15?10:52??Gmp_test\BigIntergerMod\Debug\vc60.pdb
?????文件???????78931??2002-07-26?16:45??Gmp_test\BigIntergerMod\gmp.h
?????文件??????419934??2004-02-27?12:02??Gmp_test\BigIntergerMod\gmp.lib
?????文件?????1478434??2004-02-27?12:05??Gmp_test\BigIntergerMod\gmpDebug.lib
?????文件????????3656??2014-12-15?10:51??Gmp_test\BigIntergerMod\main.cpp
?????目錄???????????0??2014-12-15?10:53??Gmp_test\gmp-static\
?????文件??????425865??2014-11-15?10:05??Gmp_test\gmp-static\GMP中文簡介.pdf
?????目錄???????????0??2014-12-15?10:53??Gmp_test\gmp-static\gmp-static\
?????文件??????996792??2007-03-25?22:26??Gmp_test\gmp-static\gmp-static\gmp-man-4.2.1.pdf
?????文件???????78931??2002-07-26?16:45??Gmp_test\gmp-static\gmp-static\gmp.h
?????文件??????419934??2004-02-27?12:02??Gmp_test\gmp-static\gmp-static\gmp.lib
?????文件?????1478434??2004-02-27?12:05??Gmp_test\gmp-static\gmp-static\gmpDebug.lib