解释一下这个程序的算法

来源：百度知道 编辑：UC知道 时间：2024/09/28 08:21:44
/****************************************************************************************
测试素数
调用方式：N.TestPrime()
返回值：若N为素数，返回0，否则返回最小质因数，若质因数不可知，返回1
****************************************************************************************/
int CBigInt::TestPrime()
{
unsigned i,pass;
if((m_ulValue[0]&1)==0)return 2;
for(i=0;i<1230;i++){if(Mod(PrimeTable[i])==0)return PrimeTable[i];}
if((m_nLength==1)&&(m_ulValue[0]<100180081))return 0;
CBigInt S,A,I,K;
K.Mov(*this);
K.m_ulValue[0]--;
for(i=0;i<5;i++)
{
pass=0;
A.Mov(rand());
S.Mov(K);
while((S.m_ulValue[0]&1)==0)
{
S.Mov(S.Div(2));
I.Mov(A.ModExp(S,*this));
if(I.Cmp(K)==0){pass=1;break;}
}
if((I.m_nLength==1)&&(I.m_ulValue[0]==1))pass=1;
if(pass==0)return 1;

//判断素数的程序——自己写的，测试范围为__int64
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define False 0
#define True 1
#define Unknow 2
#define CircleTime 6

bool prime[1000001] ; //1百万之内的素数
__int64 sushu[10000] ; //前一万个素数

//( a + b ) mod n
inline __int64 plus( __int64 a, __int64 b, __int64 n )
{
__int64 m_plus = ( a - n ) + b ;
if( m_plus < 0 ) m_plus += n ;
return m_plus ;
}

//( a * q ) mod n
__int64 Cheng( __int64 a, __int64 q, __int64 n )
{
__int64 m_cheng, m_x, m_y, m_z ;
a = a % n ;
q = q % n ;
if( q == 1 || q == 0 ) return a * q ;
if( a < 2147483648 && q < 2147483648 ) //若a,q都在int范围内，直接乘
return ( a * q ) % n ;
//递归(a*b)%n = 2*( a*(b/2) ) + (b%2)*a,并随时mod n
m_x = Cheng( a, q>>1, n ) ;
m_y = a * ( q&1 ) ;
m_z = plus( m_x, m_x, n ) ;
m_cheng = plus( m_y, m_z, n )