📄 bigint.cpp
字号:
// BigInt.cpp: implementation of the CBigInt class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "MixedCS.h"
#include "BigInt.h"
#include "Window.h"
#include "GfL.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
///////////////////////////////////////////////////////////////////////////////
// Little Primes
///////////////////////////////////////////////////////////////////////////////
#define PTL 550
const static int PrimeTable[PTL] =
{ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331, 337, 347, 349, 353,
359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
479, 487, 491, 499, 503, 509, 521, 523, 541, 547,
557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
673, 677, 683, 691, 701, 709, 719, 727, 733, 739,
743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
821, 823, 827, 829, 839, 853, 857, 859, 863, 877,
881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019,
1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153,
1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229,
1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297,
1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381,
1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,
1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663,
1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741,
1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823,
1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901,
1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993,
1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063,
2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131,
2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221,
2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293,
2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371,
2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539,
2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621,
2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689,
2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749,
2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833,
2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909,
2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001,
3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083,
3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187,
3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259,
3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343,
3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433,
3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517,
3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581,
3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659,
3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733,
3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823,
3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911,
3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001
};
////////////////////////////////////////////////////////////////////////////////
// Construction
////////////////////////////////////////////////////////////////////////////////
CBigInt::CBigInt()
{
Zero= New(0);
One = New(1);
Two = New(2);
MulCache[0] = Zero;
}
////////////////////////////////////////////////////////////////////////////////
// CBigInt Functions
////////////////////////////////////////////////////////////////////////////////
#define CHECK(x) {if( !(x) ) return false;}
#define CHECK_MSG(x,msg) {if( !(x) ){CWindow::ShowMessage(msg);return false;}}
#define EQUAL(BI,y) ( BI.len==1 && BI.bit[0]==y )
/******************************************************************************/
// 名称：GetPrime
// 功能：获取随机大素数
// 参数：len—大素数长度>4,<=BI_MAXLEN/4
// 返回：获取成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::GetPrime(BigInt &P,UINT len)
{
CHECK_MSG( len>4 && len<=BI_MAXLEN/4, "素数长度不在合法范围之内!" )
BigInt P_1,P_1Div2,LtP,A,Tmp;
int k=0;
CWindow wnd;
// 显示等待光标
wnd.ShowWaitCursor();
Next: ++k;
// 产生一个随机大数(奇数) P
RandVal(P,len);
P.bit[len-1] |= BI_BASE>>1;
// 先用小素数测试
for(int i=0; i<PTL; ++i)
{
SetVal(LtP,PrimeTable[i]);
CHECK( Div(Tmp,A,P,LtP) )
if( !A.len )
goto Next;
}
// 再用 Lehmann 方法测试
P_1=P; P_1.bit[0] -= 1;
CHECK( Div(P_1Div2,Tmp,P_1,Two) )
for(i=0; i<5; ++i)
{ // 产生一个小随机大数 A
SetVal(A,rand()+2);
CHECK( PowMod(Tmp,A,P_1Div2,P) )
if( ! ( EQUAL(Tmp,1)||!Cmp(Tmp,P_1) ) )
{
wnd.SetWindowCaption("正在测试第%d个随机大数......",k);
goto Next;
}
}
// 结束等待光标
wnd.EndWaitCursor();
return true;
}
/******************************************************************************/
// 名称：IsPrime
// 功能：检查P是否为大素数
// 参数：
// 返回：是返回true，否则返回false
/******************************************************************************/
bool CBigInt::IsPrime(BigInt &P)
{
// 如为素数，最后一位必为奇数
CHECK( P.bit[0]%2 )
CWindow wnd;
// 显示等待光标
wnd.ShowWaitCursor();
wnd.SetWindowCaption("正在测试该数是否是素数......");
BigInt P_1,P_1Div2,A,Tmp;
// 用 Lehmann 方法测试
P_1=P; P_1.bit[0] -= 1;
CHECK( Div(P_1Div2,Tmp,P_1,Two) )
for(int i=0; i<3; ++i)
{ // 产生一个小随机大数 a
SetVal(A,rand()+2);
CHECK( PowMod(Tmp,A,P_1Div2,P) )
CHECK( EQUAL(Tmp,1) || !Cmp(Tmp,P_1) )
}
// 结束等待光标
wnd.EndWaitCursor();
return true;
}
/******************************************************************************/
// 名称：PowMod
// 功能：大数乘方取模 ( C = Power(A,B) (Mod N) )
// 参数：
// 返回：成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::PowMod(BigInt &C,BigInt &A,BigInt &B,BigInt &N)
{
// N != 0
CHECK( N.len )
static bool bits[ BI_MAXLEN*4 ];
static BigInt Out,Tmp,M,ModCache[ BI_MAXLEN*4 ];
// ModCache[i] = Power(A, Power(2,i) ) (Mod N)
CHECK( Div(M,ModCache[0],A,N) )
for(int i=1,j=B.len<<2; i<j ; ++i)
{
CHECK( Mul(Tmp,ModCache[i-1],ModCache[i-1]) )
CHECK( Div(M,ModCache[i],Tmp,N) )
}
Out = One;
// 将B分解成位组
CGfL::ByteToBit(bits,B.bit,B.len,4);
for(i=0; i<j; ++i)
{
if(bits[i])
{
CHECK( Mul(Tmp,Out,ModCache[i]) )
CHECK( Div(M,Out,Tmp,N) )
}
}
C = Out;
return true;
}
/******************************************************************************/
// 名称：Inverse
// 功能：求乘法逆元 ( 即求X使 AX = 1 (mod N) )
// 参数：X—乘法逆元
// 返回：成功(A,N互素)返回 true; 否则返回 false
// 备注：虽然该算法使用递归，但它的时间效率和空间效率都非常高(我曾将书上的算法改成大数版，
// 但它连10位(16进制)都跑不起来，而我的算法跑500位(16进制)不超过2秒钟，简直没法比)
// 该算法使用动态内存分配存储中间大数，所以根本不会产生栈溢出错误，因为递归时压入
// 栈中的只是几个指针。
/******************************************************************************/
#define IV_CHECK(x) {if( !(x) ){ if(Spls)delete(Spls); if(M)delete(M);return false; }}
bool CBigInt::Inverse(BigInt &A,BigInt &X,BigInt &N,BigInt &Y)
{
BigInt *Spls=new(BigInt),*M=new(BigInt);
// 检查申请内存是否成功
IV_CHECK( Spls && M )
IV_CHECK( Div(*M,*Spls,N,A) )
// 检查余数是否为0
IV_CHECK( Spls->len )
if( EQUAL((*Spls),1) )
{
Sub(X,N,*M);
Sub(Y,A,One);
}
else
{
// 递归调用
CHECK( Inverse(*Spls,X,A,Y) )
static BigInt Tmp;
IV_CHECK( Mul(Tmp,X,*M) )
IV_CHECK( Add(Tmp,Tmp,Y) )
IV_CHECK( Sub(Y,A,X) )
IV_CHECK( Sub(X,N,Tmp) )
}
delete(Spls);
delete(M);
return true;
}
/******************************************************************************/
// 名称：Mul
// 功能：大数乘法 ( C = A * B )
// 参数：
// 返回：成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::Mul(BigInt &C,BigInt &A,BigInt &B)
{
static BigInt Out,Tmp,*pa,*pb;
if( A.len > B.len )
pa=&A,pb=&B;
else
pa=&B,pb=&A;
Out = Zero;
CHECK( InitMulCache(*pa) )
for(int i=0,j=B.len; i<j; ++i)
{
if( pb->bit[i] )
{
CHECK( ShR(Tmp,MulCache[ pb->bit[i] ],i) )
CHECK( Add(Out,Out,Tmp) )
}
}
C = Out;
return true;
}
/******************************************************************************/
// 名称：GetDivNext
// 用途：从A中(高位(由i确定)到低位)移入一些位到Spls中，使Spls>=B
// 参数：i—指向A的"当前最高位"
// 返回：成功返回true,否则返回false
/******************************************************************************/
bool CBigInt::GetDivNext(BigInt &Spls,const BigInt &A,const BigInt &B,int &i)
{
do{
int k = B.len - Spls.len;
if( k>0 )
{
if( i >= k-1 )
{
i -= k;
ShR(Spls,Spls,k);
memcpy(Spls.bit,A.bit+i+1,k);
// 如果Spls为0,则必须重设长度，因为移入的高位可能是0
if( !Spls.len )
SetLen(Spls,B.len-1);
}
else
{
ShR(Spls,Spls,i+1);
memcpy(Spls.bit,A.bit ,i+1);
if( !Spls.len )
SetLen(Spls,i);
return false;
}
}
if( Cmp(Spls,B)<0 )
{
if( i>=0 )
{
ShR(Spls,Spls,1);
Spls.bit[0] = A.bit[i--];
if( !Spls.len && Spls.bit[0] )
Spls.len = 1;
}
else
{
return false;
}
}
}while( Spls.len < B.len );
return true;
}
/******************************************************************************/
// 名称：BI_Div
// 功能：大数除法 ( M = A/B; Spls = A (Mod B) )
// 参数：
// 返回：成功返回true，否则返回false
/******************************************************************************/
bool CBigInt::Div(BigInt &M,BigInt &Spls,BigInt &A,BigInt &B)
{
// B != 0
CHECK( B.len )
if( Cmp(A,B)<0 )
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -