C++ 实现Biginteger
2024-08-25 20:37:16
网上C++版Biginteger参差不齐，一下子没有找到一个令人满意Biginteger，最近用c++改写了一下C#版 BigInteger，可以用于RSA大素数的生成，分享给大家。也请大家批评指正改的不好的地方。
其中有几个类型未在CPP中：
typedef unsigned char Byte;
#define null 0
typedef unsigned int Uint;
typedef unsigned __int64 Uint64;
//最大长度200 ： 200 Uint=200*32=6400位
const int MaxLength=200;
//已知素数长度
const int NumberPrimes=2048;
//素数数组
const int Primes[]={ 2, 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,...17789,17791,17807,17827,17837,17839,17851,17863};
// BigInteger.h: interface for the BigInteger class.
//
////////////////////////////////////////////////////////////////////// #if !defined(AFX_BIGINTER_H__2870290C_E65B_46BB_85C1_D05AAA9EDE64__INCLUDED_)
#define AFX_BIGINTER_H__2870290C_E65B_46BB_85C1_D05AAA9EDE64__INCLUDED_ #if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000 #include "Random.h"
#include "ConstAndTypeDef.h"
class BigInteger
{
public:
BigInteger(void); BigInteger(Uint64 value); BigInteger(const BigInteger &bi); BigInteger(const Uint inData[],int length); BigInteger(const Uint inData[],int length,bool direct); BigInteger(const Byte inData[],int length); ~BigInteger(); BigInteger Max(const BigInteger &bi); BigInteger Min(const BigInteger &bi); BigInteger Abs();
BigInteger ModPow( BigInteger exp, BigInteger n); BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant); BigInteger Gcd(const BigInteger &bi);
void GenRandomBits(int bits, Random &random);
int BitCount();
bool FermatLittleTest(int confidence,Random &random);
bool RabinMillerTest(int confidence,Random &random);
bool SolovayStrassenTest(int confidence,Random &random);
bool LucasStrongTest();
bool IsProbablePrime(int confidence,Random &random);
bool IsProbablePrime();
int IntValue();
Uint64 LongValue();
BigInteger GenCoPrime(int bits, Random &random);
BigInteger ModInverse(BigInteger modulus);
Byte* GetBytes();
void SetBit(Uint bitNum);
void UnsetBit(Uint bitNum);
BigInteger Sqrt(); int GetBytes(Byte result[],int orgLength); int GetBytesRemovedZero(Byte result[],int orgLength); friend BigInteger operator +(const BigInteger &bi1,const BigInteger &bi2); friend BigInteger operator ++(BigInteger &bi);
friend BigInteger operator -(const BigInteger &bi1,const BigInteger &bi2);
friend BigInteger operator --(BigInteger &bi);
friend BigInteger operator -=(BigInteger &bi1,const BigInteger &bi2);
friend BigInteger operator *(BigInteger bi1,BigInteger bi2);
friend BigInteger operator -(const BigInteger& bi1); friend BigInteger operator <<(const BigInteger &bi,int offset);
friend BigInteger operator >>(const BigInteger &bi,int offset);
friend BigInteger operator ~(const BigInteger &bi1); friend bool operator ==(const BigInteger &bi1,const BigInteger &bi2);
friend bool operator !=(const BigInteger &bi1,const BigInteger &bi2);
friend bool operator >(const BigInteger &bi1,const BigInteger &bi2);
friend bool operator <(const BigInteger &bi1, const BigInteger &bi2);
friend bool operator >=(const BigInteger &bi1,const BigInteger &bi2);
friend bool operator <=(const BigInteger &bi1, const BigInteger &bi2);
static void MultiByteDivide(BigInteger bi1, BigInteger bi2,
BigInteger& outQuotient, BigInteger& outRemainder); static void SingleByteDivide(BigInteger bi1, BigInteger bi2,
BigInteger& outQuotient, BigInteger& outRemainder); friend BigInteger operator /(BigInteger bi1, BigInteger bi2);
friend BigInteger operator %(BigInteger bi1, BigInteger bi2);
friend BigInteger operator &(const BigInteger& bi1,const BigInteger& bi2);
friend BigInteger operator |(const BigInteger& bi1,const BigInteger& bi2);
friend BigInteger operator ^(const BigInteger& bi1,const BigInteger& bi2);
static int Jacobi(BigInteger a, BigInteger b);
static BigInteger GenPseudoPrime(int bits, int confidence, Random &rand);
static BigInteger* LucasSequence(BigInteger P, BigInteger Q,
BigInteger k, BigInteger n);
static BigInteger* LucasSequenceHelper(BigInteger P, BigInteger Q,
BigInteger k, BigInteger n,
BigInteger constant, int s); static __int64 Abs(__int64 value); private: Uint data[MaxLength];
int dataLength;
void Init(void);
static int ShiftLeft( Uint buffer[],int bufLen, int shiftVal);
static int ShiftRight( Uint buffer[],int bufLen, int shiftVal);
bool LucasStrongTestHelper(BigInteger thisVal);
}; #endif // !defined(AFX_BIGINTER_H__2870290C_E65B_46BB_85C1_D05AAA9EDE64__INCLUDED_)
// BigInteger.cpp: implementation of the BigInteger class.
//
////////////////////////////////////////////////////////////////////// #include "stdafx.h"
#include "BigInter.h"
#include <math.h>
#include "iostream.h" //////////////////////////////////////////////////////////////////////
// Construction/Destruction
////////////////////////////////////////////////////////////////////// BigInteger::BigInteger(void)
{
Init();
dataLength = ;
} BigInteger::BigInteger(Uint64 value)
{
Init(); dataLength = ;
while (value != && dataLength < MaxLength)
{
data[dataLength] = (Uint)(value & 0xFFFFFFFF);
value =value>> ;
dataLength++;
} if (dataLength == )
{
dataLength = ;
}
} BigInteger::BigInteger(const BigInteger &bi)
{
Init(); dataLength = bi.dataLength; for (int i = ; i < dataLength; i++)
{
data[i] = bi.data[i];
}
} BigInteger::BigInteger(const Uint inData[],int length)
{
Init(); dataLength = length; if (dataLength > MaxLength)
{
dataLength=MaxLength;
} for (int i = dataLength - , j = ; i >= ; i--, j++)
{
data[j] = inData[i];
} while (dataLength > && data[dataLength - ] == )
{
dataLength--;
} } BigInteger::BigInteger(const Uint inData[],int length,bool direct)
{
Init(); dataLength = length; if (dataLength > MaxLength)
{
dataLength=MaxLength;
} if(direct)
{
for(int i=;i<dataLength;i++)
{
data[i] = inData[i];
}
}else
{
for (int i = dataLength - , j = ; i >= ; i--, j++)
{
data[j] = inData[i];
}
}
while (dataLength > && data[dataLength - ] == )
{
dataLength--;
}
} BigInteger::BigInteger(const Byte inData[],int length)
{
Init();
dataLength = length >> ; int leftOver =length & 0x3;
if (leftOver != ) // length not multiples of 4
{
dataLength++;
} if (dataLength > MaxLength)
{
dataLength=MaxLength;
length=dataLength<<;
} for (int i = length - , j = ; i >= ; i -= , j++)
{
data[j] = (Uint)(((Uint)inData[i - ] << ) + ((Uint)inData[i - ] << ) +
((Uint)inData[i - ] << ) + inData[i]);
} if (leftOver == )
{
data[dataLength - ] = (Uint)inData[];
}
else if (leftOver == )
{
data[dataLength - ] = (Uint)(((Uint)inData[] << ) + inData[]);
}
else if (leftOver == )
{
data[dataLength - ] = (Uint)(((Uint)inData[] << ) + ((Uint)inData[] << ) + inData[]);
} while (dataLength > && data[dataLength - ] == )
{
dataLength--;
}
} BigInteger::~BigInteger(void)
{
} void BigInteger::Init()
{ dataLength=;
for(int i=;i<MaxLength;i++)
{
data[i]=0u;
}
} BigInteger operator +(const BigInteger &bi1,const BigInteger &bi2)
{
BigInteger result;
result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength; __int64 carry = ;
for (int i = ; i < result.dataLength; i++)
{
__int64 sum = (__int64)bi1.data[i] + (__int64)bi2.data[i] + carry;
carry = sum >> ;
result.data[i] = (Uint)(sum & 0xFFFFFFFF);
} if (carry != && result.dataLength < MaxLength)
{
result.data[result.dataLength] = (Uint)(carry);
result.dataLength++;
} while (result.dataLength > && result.data[result.dataLength - ] == )
result.dataLength--; // overflow
/*int lastPos = MaxLength - 1;
if ((bi1.data[lastPos] & 0x80000000) == (bi2.data[lastPos] & 0x80000000) &&
(result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
{ }*/ return result;
} BigInteger operator ++(BigInteger& bi)
{ __int64 val, carry = ;
int index = ; while (carry != && index < MaxLength)
{
val = (__int64)(bi.data[index]);
val++; bi.data[index] = (Uint)(val & 0xFFFFFFFF);
carry = val >> ; index++;
} if (index > bi.dataLength)
bi.dataLength = index;
else
{
while (bi.dataLength > && bi.data[bi.dataLength - ] == )
bi.dataLength--;
} int lastPos = MaxLength - ; return bi;
} BigInteger operator -(const BigInteger& bi1,const BigInteger& bi2)
{
BigInteger result; result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength; __int64 carryIn = ;
for (int i = ; i < result.dataLength; i++)
{
__int64 diff; diff = (__int64)bi1.data[i] - (__int64)bi2.data[i] - carryIn;
result.data[i] = (Uint)(diff & 0xFFFFFFFF); if (diff < )
carryIn = ;
else
carryIn = ;
} // roll over to negative
if (carryIn != )
{
for (int i = result.dataLength; i < MaxLength; i++)
result.data[i] = 0xFFFFFFFF;
result.dataLength = MaxLength;
} // fixed in v1.03 to give correct datalength for a - (-b)
while (result.dataLength > && result.data[result.dataLength - ] == )
result.dataLength--; // overflow check
/*int lastPos = MaxLength - 1; if ((bi1.data[lastPos] & 0x80000000) != (bi2.data[lastPos] & 0x80000000) &&
(result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
{
//throw (new ArithmeticException());
}
*/ return result;
} BigInteger operator --(BigInteger &bi)
{
__int64 val;
bool carryIn = true;
int index = ; while (carryIn && index < MaxLength)
{
val = (__int64)(bi.data[index]);
val--; bi.data[index] = (Uint)(val & 0xFFFFFFFF); if (val >= )
carryIn = false; index++;
} if (index > bi.dataLength)
bi.dataLength = index; while (bi.dataLength > && bi.data[bi.dataLength - ] == )
bi.dataLength--; int lastPos = MaxLength - ; return bi;
} BigInteger operator -=(BigInteger &bi1,const BigInteger &bi2)
{
bi1=bi1-bi2;
return bi1;
} BigInteger operator -(const BigInteger& bi1)
{
if (bi1.dataLength == && bi1.data[] == )
{
BigInteger result;
return result;
} BigInteger result(bi1); // 1's complement
for (int i = ; i < MaxLength; i++)
{
result.data[i] = (Uint)(~(bi1.data[i]));
}
// add one to result of 1's complement
__int64 val, carry = ;
int index = ; while (carry != && index < MaxLength)
{
val = (__int64)(result.data[index]);
val++; result.data[index] = (Uint)(val & 0xFFFFFFFF);
carry = val >> ; index++;
} //Overflow in negation
/*if ((bi1.data[MaxLength - 1] & 0x80000000) == (result.data[MaxLength - 1] & 0x80000000))
{ }*/ result.dataLength = MaxLength; while (result.dataLength > && result.data[result.dataLength - ] == )
{
result.dataLength--;
}
return result;
} BigInteger operator *(BigInteger bi1,BigInteger bi2)
{
int lastPos = MaxLength - ;
bool bi1Neg = false, bi2Neg = false; if ((bi1.data[lastPos] & 0x80000000) != ) // bi1 negative
{
bi1Neg = true; bi1 = -bi1;
}
if ((bi2.data[lastPos] & 0x80000000) != ) // bi2 negative
{
bi2Neg = true; bi2 = -bi2;
} BigInteger result; for (int i = ; i < bi1.dataLength; i++)
{
if (bi1.data[i] == ) continue; Uint64 mcarry = ;
for (int j = , k = i; j < bi2.dataLength; j++, k++)
{
// k = i + j
Uint64 val = ((Uint64)bi1.data[i] * (Uint64)bi2.data[j]) +
(Uint64)result.data[k] + mcarry; result.data[k] = (Uint)(val & 0xFFFFFFFF);
mcarry = (val >> );
} if (mcarry != )
{
result.data[i + bi2.dataLength] = (Uint)mcarry;
}
} result.dataLength = bi1.dataLength + bi2.dataLength;
if (result.dataLength > MaxLength)
result.dataLength = MaxLength; while (result.dataLength > && result.data[result.dataLength - ] == )
result.dataLength--; // overflow check (result is -ve)
if ((result.data[lastPos] & 0x80000000) != )
{
if (bi1Neg != bi2Neg && result.data[lastPos] == 0x80000000) // different sign
{
// handle the special case where multiplication produces
// a max negative number in 2's complement. if (result.dataLength == )
return result;
else
{
bool isMaxNeg = true;
for (int i = ; i < result.dataLength - && isMaxNeg; i++)
{
if (result.data[i] != )
isMaxNeg = false;
} if (isMaxNeg)
return result;
}
}else
{
//Multiplication overflow
} } // if input has different signs, then result is -ve
if (bi1Neg != bi2Neg)
return -result; return result;
} BigInteger operator <<(const BigInteger &bi1, int offset)
{
BigInteger result=BigInteger(bi1);
if(offset==)
{
return result;
}
result.dataLength = BigInteger::ShiftLeft(result.data,result.dataLength, offset);
return result;
} BigInteger operator >>(const BigInteger &bi1, int shiftVal)
{
BigInteger result(bi1);
if(shiftVal==)
{
return result;
}
result.dataLength = BigInteger::ShiftRight(result.data,result.dataLength, shiftVal); int i=;
if ((bi1.data[MaxLength - ] & 0x80000000) != ) // negative
{
for ( i = MaxLength - ; i >= result.dataLength; i--)
result.data[i] = 0xFFFFFFFF; Uint mask = 0x80000000;
for (i = ; i < ; i++)
{
if ((result.data[result.dataLength - ] & mask) != )
break; result.data[result.dataLength - ] |= mask;
mask >>= ;
}
result.dataLength = MaxLength;
} return result;
} int BigInteger::ShiftLeft(Uint buffer[],int bufLen, int shiftVal)
{
int shiftAmount = ; int index=bufLen; while (index > && buffer[index - ] == )
{
index--;
} for (int count = shiftVal; count > ; )
{
if (count < shiftAmount)
{
shiftAmount = count;
} Uint64 carry = ;
for (int i = ; i < index; i++)
{
Uint64 val = ((Uint64)buffer[i]) << shiftAmount;
val |= carry; buffer[i] = (Uint)(val & 0xFFFFFFFF);
carry = val >> ;
} if (carry != )
{
if (index + <=bufLen)
{
buffer[index] = (Uint)carry;
index++;
}
}
count -= shiftAmount;
}
return index;
} int BigInteger::ShiftRight( Uint buffer[],int bufLen, int shiftVal)
{
int shiftAmount = ;
int invShift = ; while (bufLen > && buffer[bufLen - ] == )
bufLen--; for (int count = shiftVal; count > ; )
{
if (count < shiftAmount)
{
shiftAmount = count;
invShift = - shiftAmount;
} Uint64 carry = ;
for (int i = bufLen - ; i >= ; i--)
{
Uint64 val = ((Uint64)buffer[i]) >> shiftAmount;
val |= carry; carry = ((Uint64)buffer[i]) << invShift;
buffer[i] = (Uint)(val);
} count -= shiftAmount;
} while (bufLen > && buffer[bufLen - ] == )
bufLen--; return bufLen;
} BigInteger operator ~(const BigInteger &bi)
{
BigInteger result(bi); for (int i = ; i < MaxLength; i++)
{
result.data[i] = (Uint)(~(bi.data[i]));
} result.dataLength = MaxLength; while (result.dataLength > && result.data[result.dataLength - ] == )
{
result.dataLength--;
}
return result;
} bool operator ==(const BigInteger &bi1,const BigInteger &bi2)
{
if(bi1.dataLength!=bi2.dataLength)
{
return false;
}
for(int i=;i<bi1.dataLength;i++)
{
if(bi1.data[i]!=bi2.data[i])
{
return false;
}
}
return true;
} bool operator !=(const BigInteger &bi1,const BigInteger &bi2)
{
if(bi1.dataLength!=bi2.dataLength)
{
return true;
}
for(int i=;i<bi1.dataLength;i++)
{
if(bi1.data[i]!=bi2.data[i])
{
return true;
}
}
return false;
} bool operator >(const BigInteger &bi1,const BigInteger &bi2)
{
int pos = MaxLength - ; // bi1 is negative, bi2 is positive
if ((bi1.data[pos] & 0x80000000) != && (bi2.data[pos] & 0x80000000) == )
return false; // bi1 is positive, bi2 is negative
else if ((bi1.data[pos] & 0x80000000) == && (bi2.data[pos] & 0x80000000) != )
return true; // same sign
int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength; for (pos = len - ; pos >= && bi1.data[pos] == bi2.data[pos]; pos--) ; if (pos >= )
{
if (bi1.data[pos] > bi2.data[pos])
{
return true;
}else
{
return false;
}
}
return false;
} bool operator <(const BigInteger &bi1, const BigInteger &bi2)
{
int pos = MaxLength - ; // bi1 is negative, bi2 is positive
if ((bi1.data[pos] & 0x80000000) != && (bi2.data[pos] & 0x80000000) == )
return true; // bi1 is positive, bi2 is negative
else if ((bi1.data[pos] & 0x80000000) == && (bi2.data[pos] & 0x80000000) != )
return false; // same sign
int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength; for (pos = len - ; pos >= && bi1.data[pos] == bi2.data[pos]; pos--) ; if (pos >= )
{
if (bi1.data[pos] < bi2.data[pos])
{
return true;
}else
{
return false;
}
}
return false;
} bool operator >=(const BigInteger &bi1,const BigInteger &bi2)
{
return (bi1 == bi2 || bi1 > bi2);
} bool operator <=(const BigInteger &bi1, const BigInteger &bi2)
{
return (bi1 == bi2 || bi1 < bi2);
} void BigInteger::MultiByteDivide(BigInteger bi1, BigInteger bi2,
BigInteger &outQuotient, BigInteger& outRemainder)
{
int i=;
Uint result[MaxLength]; for( i=;i<MaxLength;i++)
{
result[i]=;
} int remainderLen = bi1.dataLength + ; Uint* remainder=new Uint[remainderLen]; for( i=;i<remainderLen;i++)
{
remainder[i]=;
} Uint mask = 0x80000000;
Uint val = bi2.data[bi2.dataLength - ]; int shift = , resultPos = ; while (mask != && (val & mask) == )
{
shift++;
mask >>= ;
} for ( i = ; i < bi1.dataLength; i++)
{
remainder[i] = bi1.data[i];
} BigInteger::ShiftLeft(remainder,remainderLen, shift); bi2 = bi2 << shift; int j = remainderLen - bi2.dataLength;
int pos = remainderLen - ; Uint64 firstDivisorByte = bi2.data[bi2.dataLength - ];
Uint64 secondDivisorByte = bi2.data[bi2.dataLength - ]; int divisorLen = bi2.dataLength + ;
Uint* dividendPart=new Uint[divisorLen]; for(i=;i<divisorLen;i++)
{
dividendPart[i]=;
} while (j > )
{
Uint64 dividend = ((Uint64)remainder[pos] << ) + (Uint64)remainder[pos - ]; Uint64 q_hat = dividend / firstDivisorByte;
Uint64 r_hat = dividend % firstDivisorByte; bool done = false;
while (!done)
{
done = true; if (q_hat == 0x100000000 ||
(q_hat * secondDivisorByte) > ((r_hat << ) + remainder[pos - ]))
{
q_hat--;
r_hat += firstDivisorByte; if (r_hat < 0x100000000)
done = false;
}
} int h =;
for ( h = ; h < divisorLen; h++)
dividendPart[h] = remainder[pos - h]; BigInteger kk(dividendPart,divisorLen);
BigInteger ss = bi2 * (__int64)q_hat; while (ss > kk)
{
q_hat--;
ss -= bi2;
}
BigInteger yy = kk - ss; for ( h = ; h < divisorLen; h++)
remainder[pos - h] = yy.data[bi2.dataLength - h]; result[resultPos++] = (Uint)q_hat; pos--;
j--;
} outQuotient.dataLength = resultPos;
int y = ;
for (int x = outQuotient.dataLength - ; x >= ; x--, y++)
outQuotient.data[y] = result[x];
for (; y < MaxLength; y++)
outQuotient.data[y] = ; while (outQuotient.dataLength > && outQuotient.data[outQuotient.dataLength - ] == )
outQuotient.dataLength--; if (outQuotient.dataLength == )
outQuotient.dataLength = ; outRemainder.dataLength = BigInteger::ShiftRight(remainder,remainderLen, shift); for (y = ; y < outRemainder.dataLength; y++)
outRemainder.data[y] = remainder[y];
for (; y < MaxLength; y++)
outRemainder.data[y] = ;
if(remainder!=)
{
delete remainder;
}
if(dividendPart!=)
{
delete dividendPart;
}
} void BigInteger::SingleByteDivide(BigInteger bi1, BigInteger bi2,
BigInteger& outQuotient, BigInteger& outRemainder)
{
Uint result[MaxLength];
int resultPos = ;
int i = ;
int j = ; // copy dividend to reminder
for ( i = ; i < MaxLength; i++)
outRemainder.data[i] = bi1.data[i];
outRemainder.dataLength = bi1.dataLength; while (outRemainder.dataLength > && outRemainder.data[outRemainder.dataLength - ] == )
outRemainder.dataLength--; Uint64 divisor = (Uint64)bi2.data[];
int pos = outRemainder.dataLength - ;
Uint64 dividend = (Uint64)outRemainder.data[pos]; if (dividend >= divisor)
{
Uint64 quotient = dividend / divisor;
result[resultPos++] = (Uint)quotient; outRemainder.data[pos] = (Uint)(dividend % divisor);
}
pos--; while (pos >= )
{ dividend = ((Uint64)outRemainder.data[pos + ] << ) + (Uint64)outRemainder.data[pos];
Uint64 quotient = dividend / divisor;
result[resultPos++] = (Uint)quotient; outRemainder.data[pos + ] = ;
outRemainder.data[pos--] = (Uint)(dividend % divisor);
} outQuotient.dataLength = resultPos; for ( i = outQuotient.dataLength - ; i >= ; i--, j++)
outQuotient.data[j] = result[i];
for (; j < MaxLength; j++)
outQuotient.data[j] = ; while (outQuotient.dataLength > && outQuotient.data[outQuotient.dataLength - ] == )
outQuotient.dataLength--; if (outQuotient.dataLength == )
outQuotient.dataLength = ; while (outRemainder.dataLength > && outRemainder.data[outRemainder.dataLength - ] == )
outRemainder.dataLength--; } BigInteger operator /(BigInteger bi1,BigInteger bi2)
{
BigInteger quotient;
BigInteger remainder; int lastPos = MaxLength - ;
bool divisorNeg = false, dividendNeg = false; if ((bi1.data[lastPos] & 0x80000000) != ) // bi1 negative
{
bi1 = -bi1;
dividendNeg = true;
}
if ((bi2.data[lastPos] & 0x80000000) != ) // bi2 negative
{
bi2 = -bi2;
divisorNeg = true;
} if (bi1 < bi2)
{
return quotient;
} else
{
if (bi2.dataLength == )
BigInteger::SingleByteDivide(bi1, bi2, quotient, remainder);
else
BigInteger::MultiByteDivide(bi1, bi2, quotient, remainder); if (dividendNeg != divisorNeg)
return -quotient; return quotient;
}
} BigInteger operator %(BigInteger bi1, BigInteger bi2)
{
BigInteger quotient;
BigInteger remainder(bi1); int lastPos = MaxLength - ;
bool dividendNeg = false; if ((bi1.data[lastPos] & 0x80000000) != ) // bi1 negative
{
bi1 = -bi1;
dividendNeg = true;
}
if ((bi2.data[lastPos] & 0x80000000) != ) // bi2 negative
bi2 = -bi2; if (bi1 < bi2)
{
return remainder;
} else
{
if (bi2.dataLength == )
BigInteger::SingleByteDivide(bi1, bi2, quotient, remainder);
else
BigInteger::MultiByteDivide(bi1, bi2, quotient, remainder); if (dividendNeg)
return -remainder; return remainder;
}
} BigInteger operator &(const BigInteger &bi1,const BigInteger &bi2)
{
BigInteger result; int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength; for (int i = ; i < len; i++)
{
Uint sum = (Uint)(bi1.data[i] & bi2.data[i]);
result.data[i] = sum;
} result.dataLength = MaxLength; while (result.dataLength > && result.data[result.dataLength - ] == )
result.dataLength--; return result;
} BigInteger operator |(const BigInteger& bi1,const BigInteger& bi2)
{
BigInteger result; int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength; for (int i = ; i < len; i++)
{
Uint sum = (Uint)(bi1.data[i] | bi2.data[i]);
result.data[i] = sum;
} result.dataLength = MaxLength; while (result.dataLength > && result.data[result.dataLength - ] == )
result.dataLength--; return result;
} BigInteger operator ^(const BigInteger& bi1,const BigInteger& bi2)
{
BigInteger result; int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength; for (int i = ; i < len; i++)
{
Uint sum = (Uint)(bi1.data[i] ^ bi2.data[i]);
result.data[i] = sum;
} result.dataLength = MaxLength; while (result.dataLength > && result.data[result.dataLength - ] == )
result.dataLength--; return result;
} int BigInteger::Jacobi(BigInteger a, BigInteger b)
{
if ((b.data[] & 0x1) == )
{
//Exception::Jacobi defined only for odd integers
} if (a >= b) a=a % b;
if (a.dataLength == && a.data[] == ) return ; // a == 0
if (a.dataLength == && a.data[] == ) return ; // a == 1 if (a < BigInteger())
{
if ((((b - ).data[]) & 0x2) == ) //if( (((b-1) >> 1).data[0] & 0x1) == 0)
return Jacobi(-a, b);
else
return -Jacobi(-a, b);
} int e = ;
for (int index = ; index < a.dataLength; index++)
{
Uint mask = 0x01; for (int i = ; i < ; i++)
{
if ((a.data[index] & mask) != )
{
index = a.dataLength; // to break the outer loop
break;
}
mask <<= ;
e++;
}
} BigInteger a1 = a >> e; int s = ;
if ((e & 0x1) != && ((b.data[] & 0x7) == || (b.data[] & 0x7) == ))
s = -; if ((b.data[] & 0x3) == && (a1.data[] & 0x3) == )
s = -s; if (a1.dataLength == && a1.data[] == )
return s;
else
return (s * Jacobi(b % a1, a1));
} BigInteger BigInteger::GenPseudoPrime(int bits, int confidence,Random &random)
{
BigInteger result;
bool done = false; while (!done)
{
result.GenRandomBits(bits,random); result.data[] |= 0x01; // make it odd // prime test
done = result.IsProbablePrime(confidence,random);
}
return result;
} BigInteger* BigInteger::LucasSequence(BigInteger P, BigInteger Q,
BigInteger k, BigInteger n)
{
if (k.dataLength == && k.data[] == )
{
BigInteger* result = new BigInteger[]; result[] =BigInteger();
result[] = BigInteger() % n;
result[] = BigInteger() % n;
return result;
} // calculate constant = b^(2k) / m
// for Barrett Reduction
BigInteger constant; int nLen = n.dataLength << ;
constant.data[nLen] = 0x00000001;
constant.dataLength = nLen + ; constant = constant / n; // calculate values of s and t
int s = ; for (int index = ; index < k.dataLength; index++)
{
Uint mask = 0x01; for (int i = ; i < ; i++)
{
if ((k.data[index] & mask) != )
{
index = k.dataLength; // to break the outer loop
break;
}
mask <<= ;
s++;
}
} BigInteger t = k >> s; return LucasSequenceHelper(P, Q, t, n, constant, s);
} BigInteger* BigInteger::LucasSequenceHelper(BigInteger P, BigInteger Q,
BigInteger k, BigInteger n,
BigInteger constant, int s)
{
int i=; BigInteger* result = new BigInteger[]; for(i=;i<;i++)
{
result[i]=;
} if ((k.data[] & 0x00000001) == )
{
//Exception::"Argument k must be odd."
}
int numbits = k.BitCount(); Uint mask = (Uint)0x1 << ((numbits & 0x1F) - ); // v = v0, v1 = v1, u1 = u1, Q_k = Q^0 BigInteger v = % n, Q_k = % n,
v1 = P % n, u1 = Q_k;
bool flag = true; for ( i = k.dataLength - ; i >= ; i--) // iterate on the binary expansion of k
{
while (mask != )
{
if (i == && mask == 0x00000001) // last bit
break; if ((k.data[i] & mask) != ) // bit is set
{
// index doubling with addition u1 = (u1 * v1) % n; v = ((v * v1) - (P * Q_k)) % n;
v1 = n.BarrettReduction(v1 * v1, n, constant);
v1 = (v1 - ((Q_k * Q) << )) % n; if (flag)
flag = false;
else
Q_k = n.BarrettReduction(Q_k * Q_k, n, constant); Q_k = (Q_k * Q) % n;
}
else
{
// index doubling
u1 = ((u1 * v) - Q_k) % n; v1 = ((v * v1) - (P * Q_k)) % n;
v = n.BarrettReduction(v * v, n, constant);
v = (v - (Q_k << )) % n; if (flag)
{
Q_k = Q % n;
flag = false;
}
else
Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
} mask >>= ;
}
mask = 0x80000000;
} // at this point u1 = u(n+1) and v = v(n)
// since the last bit always 1, we need to transform u1 to u(2n+1) and v to v(2n+1) u1 = ((u1 * v) - Q_k) % n;
v = ((v * v1) - (P * Q_k)) % n;
if (flag)
flag = false;
else
Q_k = n.BarrettReduction(Q_k * Q_k, n, constant); Q_k = (Q_k * Q) % n; for ( i = ; i < s; i++)
{
// index doubling
u1 = (u1 * v) % n;
v = ((v * v) - (Q_k << )) % n; if (flag)
{
Q_k = Q % n;
flag = false;
}
else
Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
} result[] = u1;
result[] = v;
result[] = Q_k; return result;
} bool BigInteger::LucasStrongTestHelper(BigInteger thisVal)
{
__int64 D = , sign = -, dCount = ;
bool done = false; while (!done)
{
int Jresult = BigInteger::Jacobi(D, thisVal); if (Jresult == -)
done = true; // J(D, this) = 1
else
{
if ((Jresult == ) && (BigInteger::Abs(D) < thisVal)) // divisor found
return false; if (dCount == )
{
// check for square
BigInteger root = thisVal.Sqrt();
if (root * root == thisVal)
return false;
} D = (BigInteger::Abs(D) + ) * sign;
sign = -sign;
}
dCount++;
} __int64 Q = ( - D) >> ; BigInteger p_add1 = thisVal + ;
int s = ; for (int index = ; index < p_add1.dataLength; index++)
{
Uint mask = 0x01; for (int i = ; i < ; i++)
{
if ((p_add1.data[index] & mask) != )
{
index = p_add1.dataLength; // to break the outer loop
break;
}
mask <<= ;
s++;
}
} BigInteger t = p_add1 >> s; // calculate constant = b^(2k) / m
// for Barrett Reduction
BigInteger constant; int nLen = thisVal.dataLength << ;
constant.data[nLen] = 0x00000001;
constant.dataLength = nLen + ; constant = constant / thisVal; BigInteger* lucas = LucasSequenceHelper(, Q, t, thisVal, constant, );
bool isPrime = false; if ((lucas[].dataLength == && lucas[].data[] == ) ||
(lucas[].dataLength == && lucas[].data[] == ))
{
// u(t) = 0 or V(t) = 0
isPrime = true;
} for (int i = ; i < s; i++)
{
if (!isPrime)
{
// doubling of index
lucas[] = thisVal.BarrettReduction(lucas[] * lucas[], thisVal, constant);
lucas[] = (lucas[] - (lucas[] << )) % thisVal; //lucas[1] = ((lucas[1] * lucas[1]) - (lucas[2] << 1)) % thisVal; if ((lucas[].dataLength == && lucas[].data[] == ))
isPrime = true;
} lucas[] = thisVal.BarrettReduction(lucas[] * lucas[], thisVal, constant); //Q^k
} if (isPrime) // additional checks for composite numbers
{
// If n is prime and gcd(n, Q) == 1, then
// Q^((n+1)/2) = Q * Q^((n-1)/2) is congruent to (Q * J(Q, n)) mod n BigInteger g = thisVal.Gcd(Q);
if (g.dataLength == && g.data[] == ) // gcd(this, Q) == 1
{
if ((lucas[].data[MaxLength - ] & 0x80000000) != )
lucas[] =lucas[] + thisVal; BigInteger temp = (Q * BigInteger::Jacobi(Q, thisVal)) % thisVal;
if ((temp.data[MaxLength - ] & 0x80000000) != )
temp = temp+thisVal; if (lucas[] != temp)
isPrime = false;
}
} if(lucas!=)
{
delete lucas;
} return isPrime; } BigInteger BigInteger::Max(const BigInteger &bi)
{
if (*this > bi)
return BigInteger(*this);
else
return BigInteger(bi);
} BigInteger BigInteger::Min(const BigInteger &bi)
{
if (*this < bi)
return BigInteger(*this);
else
return BigInteger(bi);
} BigInteger BigInteger::Abs()
{
if ((this->data[MaxLength - ] & 0x80000000) != )
return -(*this);
else
return BigInteger(*this);
} BigInteger BigInteger::ModPow(BigInteger exp, BigInteger n)
{
if ((exp.data[MaxLength - ] & 0x80000000) != )
{
//Exception::"Positive exponents only."
} BigInteger resultNum = ;
BigInteger tempNum;
bool thisNegative = false; if ((this->data[MaxLength - ] & 0x80000000) != ) // negative this
{
tempNum = (-(*this)) % n;
thisNegative = true;
}
else
tempNum = (*this) % n; // ensures (tempNum * tempNum) < b^(2k) if ((n.data[MaxLength - ] & 0x80000000) != ) // negative n
n = -n; // calculate constant = b^(2k) / m
BigInteger constant; int i = n.dataLength << ;
constant.data[i] = 0x00000001;
constant.dataLength = i + ; constant = constant / n;
int totalBits = exp.BitCount();
int count = ; // perform squaring and multiply exponentiation
for (int pos = ; pos < exp.dataLength; pos++)
{
Uint mask = 0x01; for (int index = ; index < ; index++)
{
if ((exp.data[pos] & mask) != )
resultNum = BarrettReduction(resultNum * tempNum, n, constant); mask <<= ; tempNum = BarrettReduction(tempNum * tempNum, n, constant); if (tempNum.dataLength == && tempNum.data[] == )
{
if (thisNegative && (exp.data[] & 0x1) != ) //odd exp
return -resultNum;
return resultNum;
}
count++;
if (count == totalBits)
break;
}
} if (thisNegative && (exp.data[] & 0x1) != ) //odd exp
return -resultNum; return resultNum;
} BigInteger BigInteger::BarrettReduction(BigInteger x, BigInteger n, BigInteger constant)
{
int k = n.dataLength,
kPlusOne = k + ,
kMinusOne = k - ;
int i =,j=;
BigInteger q1; // q1 = x / b^(k-1)
for ( i = kMinusOne, j = ; i < x.dataLength; i++, j++)
q1.data[j] = x.data[i];
q1.dataLength = x.dataLength - kMinusOne;
if (q1.dataLength <= )
q1.dataLength = ; BigInteger q2 = q1 * constant;
BigInteger q3; // q3 = q2 / b^(k+1)
for (i = kPlusOne, j = ; i < q2.dataLength; i++, j++)
q3.data[j] = q2.data[i];
q3.dataLength = q2.dataLength - kPlusOne;
if (q3.dataLength <= )
q3.dataLength = ; // r1 = x mod b^(k+1)
// i.e. keep the lowest (k+1) words
BigInteger r1 ;
int lengthToCopy = (x.dataLength > kPlusOne) ? kPlusOne : x.dataLength;
for ( i = ; i < lengthToCopy; i++)
r1.data[i] = x.data[i];
r1.dataLength = lengthToCopy; // r2 = (q3 * n) mod b^(k+1)
// partial multiplication of q3 and n BigInteger r2;
for ( i = ; i < q3.dataLength; i++)
{
if (q3.data[i] == ) continue; Uint64 mcarry = ;
int t = i;
for (int j = ; j < n.dataLength && t < kPlusOne; j++, t++)
{
// t = i + j
Uint64 val = ((Uint64)q3.data[i] * (Uint64)n.data[j]) +
(Uint64)r2.data[t] + mcarry; r2.data[t] = (Uint)(val & 0xFFFFFFFF);
mcarry = (val >> );
} if (t < kPlusOne)
r2.data[t] = (Uint)mcarry;
}
r2.dataLength = kPlusOne;
while (r2.dataLength > && r2.data[r2.dataLength - ] == )
r2.dataLength--; r1 -= r2;
if ((r1.data[MaxLength - ] & 0x80000000) != ) // negative
{
BigInteger val;
val.data[kPlusOne] = 0x00000001;
val.dataLength = kPlusOne + ;
r1 =r1+ val;
} while (r1 >= n)
r1 -= n; return r1;
} BigInteger BigInteger::Gcd(const BigInteger &bi)
{
BigInteger x;
BigInteger y; if ((data[MaxLength - ] & 0x80000000) != ) // negative
x = -(*this);
else
x = *this; if ((bi.data[MaxLength - ] & 0x80000000) != ) // negative
y = -bi;
else
y = bi; BigInteger g = y; while (x.dataLength > || (x.dataLength == && x.data[] != ))
{
g = x;
x = y % x;
y = g;
} return g;
} void BigInteger::GenRandomBits(int bits,Random &random)
{
int dwords = bits >> ;
int remBits = bits & 0x1F;
int i = ;
if (remBits != )
dwords++; if (dwords > MaxLength)
{
//Exception::"Number of required bits > maxLength."
} for (i = ; i < dwords; i++)
{
data[i]=random.NextUint();
} for (i = dwords; i < MaxLength; i++)
data[i] = ; if (remBits != )
{
Uint mask = (Uint)(0x01 << (remBits - ));
data[dwords - ] |= mask; mask = (Uint)(0xFFFFFFFF >> ( - remBits));
data[dwords - ] &= mask;
}
else
data[dwords - ] |= 0x80000000; dataLength = dwords; if (dataLength == )
dataLength = ;
} int BigInteger::BitCount()
{
while (dataLength > && data[dataLength - ] == )
{
dataLength--;
} Uint value = data[dataLength - ]; Uint mask = 0x80000000; int bits = ; while (bits > && (value & mask) == )
{
bits--;
mask >>= ;
} bits += ((dataLength - ) << ); return bits;
} bool BigInteger::FermatLittleTest(int confidence,Random &random)
{
BigInteger thisVal;
if ((this->data[MaxLength - ] & 0x80000000) != ) // negative
thisVal = -(*this);
else
thisVal = *this; if (thisVal.dataLength == )
{
// test small numbers
if (thisVal.data[] == || thisVal.data[] == )
return false;
else if (thisVal.data[] == || thisVal.data[] == )
return true;
} if ((thisVal.data[] & 0x1) == ) // even numbers
return false; int bits = thisVal.BitCount();
BigInteger a;
BigInteger p_sub1 = thisVal - BigInteger(); for (int round = ; round < confidence; round++)
{
bool done = false; while (!done) // generate a < n
{
int testBits = ; // make sure "a" has at least 2 bits
testBits=random.NextValue(,bits-); a.GenRandomBits(testBits,random); int byteLen = a.dataLength; // make sure "a" is not 0
if (byteLen > || (byteLen == && a.data[] != ))
done = true;
} // check whether a factor exists (fix for version 1.03)
BigInteger gcdTest = a.Gcd(thisVal);
if (gcdTest.dataLength == && gcdTest.data[] != )
return false; // calculate a^(p-1) mod p
BigInteger expResult = a.ModPow(p_sub1, thisVal); int resultLen = expResult.dataLength; // is NOT prime is a^(p-1) mod p != 1 if (resultLen > || (resultLen == && expResult.data[] != ))
{
return false;
}
} return true;
} bool BigInteger::RabinMillerTest(int confidence,Random &random)
{
BigInteger thisVal;
if ((this->data[MaxLength - ] & 0x80000000) != ) // negative
thisVal = -(*this);
else
thisVal = *this; if (thisVal.dataLength == )
{
// test small numbers
if (thisVal.data[] == || thisVal.data[] == )
return false;
else if (thisVal.data[] == || thisVal.data[] == )
return true;
} if ((thisVal.data[] & 0x1) == ) // even numbers
return false; // calculate values of s and t
BigInteger p_sub1 = thisVal - BigInteger();
int s = ; for (int index = ; index < p_sub1.dataLength; index++)
{
Uint mask = 0x01; for (int i = ; i < ; i++)
{
if ((p_sub1.data[index] & mask) != )
{
index = p_sub1.dataLength; // to break the outer loop
break;
}
mask <<= ;
s++;
}
} BigInteger t = p_sub1 >> s; int bits = thisVal.BitCount();
BigInteger a; for (int round = ; round < confidence; round++)
{
bool done = false; while (!done) // generate a < n
{
int testBits = ; //make sure "a" has at least 2 bits testBits = random.NextValue(,bits-); a.GenRandomBits(testBits,random); int byteLen = a.dataLength; // make sure "a" is not 0
if (byteLen > || (byteLen == && a.data[] != ))
done = true;
} // check whether a factor exists (fix for version 1.03)
BigInteger gcdTest = a.Gcd(thisVal);
if (gcdTest.dataLength == && gcdTest.data[] != )
return false; BigInteger b = a.ModPow(t, thisVal); bool result = false; if (b.dataLength == && b.data[] == ) // a^t mod p = 1
result = true; for (int j = ; result == false && j < s; j++)
{
if (b == p_sub1) // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
{
result = true;
break;
} b = (b * b) % thisVal;
} if (result == false)
return false;
}
return true;
} bool BigInteger::SolovayStrassenTest(int confidence,Random &random)
{
BigInteger thisVal;
if ((this->data[MaxLength - ] & 0x80000000) != ) // negative
thisVal = -(*this);
else
thisVal = (*this); if (thisVal.dataLength == )
{
// test small numbers
if (thisVal.data[] == || thisVal.data[] == )
return false;
else if (thisVal.data[] == || thisVal.data[] == )
return true;
} if ((thisVal.data[] & 0x1) == ) // even numbers
return false; int bits = thisVal.BitCount();
BigInteger a ;
BigInteger p_sub1 = thisVal - ;
BigInteger p_sub1_shift = p_sub1 >> ; //Random rand; for (int round = ; round < confidence; round++)
{
bool done = false; while (!done) // generate a < n
{
int testBits = ; // make sure "a" has at least 2 bits testBits=random.NextValue(,bits-); a.GenRandomBits(testBits,random); int byteLen = a.dataLength; // make sure "a" is not 0
if (byteLen > || (byteLen == && a.data[] != ))
done = true;
} // check whether a factor exists (fix for version 1.03)
BigInteger gcdTest = a.Gcd(thisVal);
if (gcdTest.dataLength == && gcdTest.data[] != )
return false; // calculate a^((p-1)/2) mod p BigInteger expResult = a.ModPow(p_sub1_shift, thisVal);
if (expResult == p_sub1)
expResult = -; // calculate Jacobi symbol
BigInteger jacob = Jacobi(a, thisVal); // if they are different then it is not prime
if (expResult != jacob)
return false;
} return true;
} bool BigInteger::LucasStrongTest()
{
BigInteger thisVal;
if ((this->data[MaxLength - ] & 0x80000000) != ) // negative
thisVal = -(*this);
else
thisVal = *this; if (thisVal.dataLength == )
{
// test small numbers
if (thisVal.data[] == || thisVal.data[] == )
return false;
else if (thisVal.data[] == || thisVal.data[] == )
return true;
} if ((thisVal.data[] & 0x1) == ) // even numbers
return false; return LucasStrongTestHelper(thisVal);
} bool BigInteger::IsProbablePrime(int confidence,Random &random)
{
BigInteger thisVal;
if ((this->data[MaxLength - ] & 0x80000000) != ) // negative
thisVal = -(*this);
else
thisVal = *this; // test for divisibility by primes
for (int p = ; p < NumberPrimes; p++)
{
BigInteger divisor = Primes[p]; if (divisor >= thisVal)
break; BigInteger resultNum = thisVal % divisor;
if (resultNum.IntValue() == )
{
return false;
}
} if (thisVal.RabinMillerTest(confidence,random))
{
return true;
}
else
{
return false;
}
} bool BigInteger::IsProbablePrime()
{
BigInteger thisVal;
if ((this->data[MaxLength - ] & 0x80000000) != ) // negative
thisVal = -(*this);
else
thisVal = (*this); if (thisVal.dataLength == )
{
// test small numbers
if (thisVal.data[] == || thisVal.data[] == )
return false;
else if (thisVal.data[] == || thisVal.data[] == )
return true;
} if ((thisVal.data[] & 0x1) == ) // even numbers
return false; // test for divisibility by primes < 2000
for (int p = ; p <NumberPrimes; p++)
{
BigInteger divisor = Primes[p]; if (divisor >= thisVal)
break; BigInteger resultNum = thisVal % divisor;
if (resultNum.IntValue() == )
{
return false;
}
} // Perform BASE 2 Rabin-Miller Test // calculate values of s and t
BigInteger p_sub1 = thisVal - BigInteger();
int s = ; for (int index = ; index < p_sub1.dataLength; index++)
{
Uint mask = 0x01; for (int i = ; i < ; i++)
{
if ((p_sub1.data[index] & mask) != )
{
index = p_sub1.dataLength; // to break the outer loop
break;
}
mask <<= ;
s++;
}
} BigInteger t = p_sub1 >> s; int bits = thisVal.BitCount();
BigInteger a = ; // b = a^t mod p
BigInteger b = a.ModPow(t, thisVal);
bool result = false; if (b.dataLength == && b.data[] == ) // a^t mod p = 1
result = true; for (int j = ; result == false && j < s; j++)
{
if (b == p_sub1) // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
{
result = true;
break;
} b = (b * b) % thisVal;
} // if number is strong pseudoprime to base 2, then do a strong lucas test
if (result)
result = LucasStrongTestHelper(thisVal); return result;
} int BigInteger::IntValue()
{
return (int)data[];
} Uint64 BigInteger::LongValue()
{
Uint64 val = ; val = (Uint64)data[]; val |= (Uint64)data[] << ; return val;
} BigInteger BigInteger::GenCoPrime(int bits, Random &rand)
{
bool done = false;
BigInteger result; while (!done)
{
result.GenRandomBits(bits, rand); // gcd test
BigInteger g = result.Gcd(*this);
if (g.dataLength == && g.data[] == )
done = true;
} return result;
} BigInteger BigInteger::ModInverse(BigInteger modulus)
{
BigInteger p[] = { BigInteger(), BigInteger() };
BigInteger q[]={,}; // quotients
BigInteger r[] = {BigInteger(),BigInteger() }; // remainders int step = ; BigInteger a = modulus;
BigInteger b = *this; while (b.dataLength > || (b.dataLength == && b.data[] != ))
{
BigInteger quotient;
BigInteger remainder; if (step > )
{
BigInteger pval = (p[] - (p[] * q[])) % modulus;
p[] = p[];
p[] = pval;
} if (b.dataLength == )
SingleByteDivide(a, b, quotient, remainder);
else
MultiByteDivide(a, b, quotient, remainder); q[] = q[];
r[] = r[];
q[] = quotient; r[] = remainder; a = b;
b = remainder; step++;
} if (r[].dataLength > || (r[].dataLength == && r[].data[] != ))
{
//Exception::"No inverse!"
} BigInteger result = ((p[] - (p[] * q[])) % modulus); if ((result.data[MaxLength - ] & 0x80000000) != )
result =result+ modulus; // get the least positive modulus return result;
} Byte* BigInteger::GetBytes()
{
int numBytes = dataLength << ;
int i=; Byte* result = new Byte[numBytes];
for(i=;i<numBytes;i++)
{
result[i]=;
} int pos = ;
Uint val = ; for ( i = dataLength -; i >= ; i--, pos += )
{
val = data[i];
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos] = (Byte)(val & 0xFF);
} return result;
} int BigInteger::GetBytes(Byte result[],int orgLength)
{
int numBytes = dataLength << ;
int i=; if(orgLength<numBytes)
{
return -;
} for(i=;i<orgLength;i++)
{
result[i]=;
} int pos = ;
Uint val = ; for ( i = dataLength -; i >= ; i--, pos += )
{
val = data[i];
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos] = (Byte)(val & 0xFF);
} return numBytes;
} int BigInteger::GetBytesRemovedZero(Byte result[],int orgLength)
{
int numBits = BitCount();
int i=;
int numBytes = numBits >> ; if ((numBits & 0x7) != )
numBytes++; for(i=;i<orgLength;i++)
{
result[i]=;
} int pos = ; Uint val = data[dataLength - ];
bool isHaveData = false; Uint tempVal = (val >> & 0xFF);
if (tempVal != )
{
result[pos++] = (Byte)tempVal;
isHaveData = true;
}
tempVal = (val >> & 0xFF);
if (isHaveData || tempVal != )
{
result[pos++] = (Byte)tempVal;
isHaveData = true;
}
tempVal = (val >> & 0xFF);
if (isHaveData || tempVal != )
{
result[pos++] = (Byte)tempVal;
isHaveData = true;
}
tempVal = (val & 0xFF);
if (isHaveData || tempVal != )
{
result[pos++] = (Byte)tempVal;
} for ( i = dataLength - ; i >= ; i--, pos += )
{
val = data[i];
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos + ] = (Byte)(val & 0xFF);
val >>= ;
result[pos] = (Byte)(val & 0xFF);
} return numBytes;
} void BigInteger::SetBit(Uint bitNum)
{
Uint bytePos = bitNum >> ; // divide by 32
char bitPos = (char)(bitNum & 0x1F); // get the lowest 5 bits Uint mask = (Uint) << bitPos;
this->data[bytePos] |= mask; if (bytePos >= (Uint)this->dataLength)
{
this->dataLength = (int)bytePos + ;
}
} void BigInteger::UnsetBit(Uint bitNum)
{
Uint bytePos = bitNum >> ; if (bytePos < (Uint)this->dataLength)
{
char bitPos = (char)(bitNum & 0x1F); Uint mask = ( Uint) << bitPos;
Uint mask2 = 0xFFFFFFFF ^ mask; this->data[bytePos] &= mask2; if (this->dataLength > && this->data[this->dataLength - ] == )
this->dataLength--;
}
} BigInteger BigInteger::Sqrt()
{
Uint numBits = (Uint)BitCount(); if ((numBits & 0x1) != ) // odd number of bits
numBits = (numBits >> ) + ;
else
numBits = (numBits >> ); Uint bytePos = numBits >> ;
char bitPos = (char)(numBits & 0x1F); Uint mask; BigInteger result;
if (bitPos == )
mask = 0x80000000;
else
{
mask = (Uint) << bitPos;
bytePos++;
}
result.dataLength = (int)bytePos; for (int i = (int)bytePos - ; i >= ; i--)
{
while (mask != )
{
// guess
result.data[i] ^= mask; // undo the guess if its square is larger than this
if ((result * result) > *this)
result.data[i] ^= mask; mask >>= ;
}
mask = 0x80000000;
}
return result;
} __int64 BigInteger::Abs(__int64 value)
{
if(value<)
{
return -value;
}else
{
return value;
}
}
最新文章
- a href=#与 a href=javascript:void(0) 的区别
- 如何用分析函数找出EMP表中每个部门工资最高的员工
- 几篇关于VisualStudio的调试工具文章
- WCF中使用控件的委托，线程中的UI委托
- SQL Server 监控 使用sp_trace_create
- Day4 内置函数补充、装饰器
- centos搭建zabbix
- 22、手把手教你Extjs5（二十二）模块Form的自定义的设计[1]
- Javascript实现简单跨域调用
- shell常用监控脚本
- php向mariaDB插入数据时乱码问题解决 --- mysqli_set_charset（设置默认字符编码）
- WCF发布到IIS 7.0，并以https访问
- centos7将可执行程序做成服务
- ida pro65
- sudo command
- List元素为泛型时的注意事项
- [BZOJ4000][TJOI2015]棋盘(状压DP+矩阵快速幂)
- Fragment切换页面
- 异常：idea一直刷新索引：updating index
- USACO Section1.3 Mixing Milk 解题报告