primetest.h

一个很好用的大整数的类, 最大可支持9999990位的十进制整数

// PrimeTest.h: interface for the CPrimeTest class.
// 素性测试的类
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_PRIMETEST_H__C3253C5F_BC84_43AE_B1DB_CE6D40EE5FD4__INCLUDED_)
#define AFX_PRIMETEST_H__C3253C5F_BC84_43AE_B1DB_CE6D40EE5FD4__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "ZBIntArray.h"
#include "Rand.h"

class __declspec(dllexport) CPrimeTest  
{
public:
	CPrimeTest();
	virtual ~CPrimeTest();

public://求幂的模
	static BOOL PowerMode(CZBInt &cA, CZBInt &cK, CZBInt &cN, CZBInt &cRe);
					//求幂的模(用平方-乘积法),型如 A^K mod N
					//cRe是结果, 如果cN==0, 返回false

public://产生随机数
	static void RandInt(UINT uNums, CZBInt &cBI);//随机产生一个正整数, uNums:位数
	static void RandOdd(UINT uNums, CZBInt &cBI);//随机产生一个正奇数, uNums:位数
	static void RandEven(UINT uNums, CZBInt &cBI);//随机产生一个正偶数, uNums:位数

	static void RandInt(CRand &cRand, UINT uNums, CZBInt &cBI);//随机产生一个正整数, uNums:位数
	static void RandOdd(CRand &cRand, UINT uNums, CZBInt &cBI);//随机产生一个正奇数, uNums:位数
	static void RandEven(CRand &cRand, UINT uNums, CZBInt &cBI);//随机产生一个正偶数, uNums:位数

	static void RandMedium(CRand &cRand, CZBInt &cBI1, CZBInt &cBI2, 
							CZBInt &cRe);//
					//随机产生一个介于cBI1, cBI2之间的正整数(包含cBI1, cBI2)
	static void RandMediumOdd(CRand &cRand, CZBInt &cBI1, CZBInt &cBI2, 
							CZBInt &cRe);//
					//随机产生一个介于cBI1, cBI2之间的正奇数(包含cBI1, cBI2)
	static void RandMediumEven(CRand &cRand, CZBInt &cBI1, CZBInt &cBI2, 
							CZBInt &cRe);//
					//随机产生一个介于cBI1, cBI2之间的正偶数(包含cBI1, cBI2)

public://分解偶数
	static void DecompEven(CZBInt &cBI,
						unsigned __int64 &uPower2, CZBInt &cOdd);
					//分解偶数形如:  n=2^s * r, r为奇数
					//cBI:待分解的数, uPower2:分解得到2的幂, cOdd:剩余的奇数

public://Miller-Rabin测试
	static int MRTest(CZBInt &cBI, UINT uT);//对大奇数进行Miller-Rabin测试
				//cBI:待测试的奇数, uT:安全参数, 概率=4^-uT
				//返回: 0:合数, 1:素数
				//      -1:cBI为偶数或<3  -2:uT==0(应该>=1)
				//      -3:uT太大( >=100000 )
};

#endif // !defined(AFX_PRIMETEST_H__C3253C5F_BC84_43AE_B1DB_CE6D40EE5FD4__INCLUDED_)