GMP大数库实现大整数模以及Miller Rabin素数测试算法

GMP大数库的中文使用手册，以及已经编译好的GMP大数库，仅适用于VC6.0，并有自己写的生成随机大素数，大整数模运算，以及Miller Rabin素数测试算法。

#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 < a <= n-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