?? biginteger.cs
字號:
if(dividendNeg)
return -remainder;
return remainder;
}
}
//***********************************************************************
// Overloading of bitwise AND operator
//***********************************************************************
public static BigInteger operator &(BigInteger bi1, BigInteger bi2)
{
BigInteger result = new BigInteger();
int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
for(int i = 0; i < len; i++)
{
uint sum = (uint)(bi1.data[i] & bi2.data[i]);
result.data[i] = sum;
}
result.dataLength = maxLength;
while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
result.dataLength--;
return result;
}
//***********************************************************************
// Overloading of bitwise OR operator
//***********************************************************************
public static BigInteger operator |(BigInteger bi1, BigInteger bi2)
{
BigInteger result = new BigInteger();
int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
for(int i = 0; i < len; i++)
{
uint sum = (uint)(bi1.data[i] | bi2.data[i]);
result.data[i] = sum;
}
result.dataLength = maxLength;
while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
result.dataLength--;
return result;
}
//***********************************************************************
// Overloading of bitwise XOR operator
//***********************************************************************
public static BigInteger operator ^(BigInteger bi1, BigInteger bi2)
{
BigInteger result = new BigInteger();
int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
for(int i = 0; i < len; i++)
{
uint sum = (uint)(bi1.data[i] ^ bi2.data[i]);
result.data[i] = sum;
}
result.dataLength = maxLength;
while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
result.dataLength--;
return result;
}
//***********************************************************************
// Returns max(this, bi)
//***********************************************************************
public BigInteger max(BigInteger bi)
{
if(this > bi)
return (new BigInteger(this));
else
return (new BigInteger(bi));
}
//***********************************************************************
// Returns min(this, bi)
//***********************************************************************
public BigInteger min(BigInteger bi)
{
if(this < bi)
return (new BigInteger(this));
else
return (new BigInteger(bi));
}
//***********************************************************************
// Returns the absolute value
//***********************************************************************
public BigInteger abs()
{
if((this.data[maxLength - 1] & 0x80000000) != 0)
return (-this);
else
return (new BigInteger(this));
}
//***********************************************************************
// Returns a string representing the BigInteger in base 10.
//***********************************************************************
public override string ToString()
{
return ToString(10);
}
//***********************************************************************
// Returns a string representing the BigInteger in sign-and-magnitude
// format in the specified radix.
//
// Example
// -------
// If the value of BigInteger is -255 in base 10, then
// ToString(16) returns "-FF"
//
//***********************************************************************
public string ToString(int radix)
{
// if(radix < 2 || radix > 36)
// throw (new ArgumentException("Radix must be >= 2 and <= 36"));
//
// string charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
if(radix < 2 || radix > 95)
throw (new ArgumentException("Radix must be >= 2 and <= 95"));
string charSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_=!@#$%^&*()[]{}|;:,.<>/?`~ \\\'\"+-";
string result = "";
BigInteger a = this;
bool negative = false;
if((a.data[maxLength-1] & 0x80000000) != 0)
{
negative = true;
try
{
a = -a;
}
catch(Exception) {}
}
BigInteger quotient = new BigInteger();
BigInteger remainder = new BigInteger();
BigInteger biRadix = new BigInteger(radix);
if(a.dataLength == 1 && a.data[0] == 0)
result = "0";
else
{
while(a.dataLength > 1 || (a.dataLength == 1 && a.data[0] != 0))
{
singleByteDivide(a, biRadix, quotient, remainder);
// if(remainder.data[0] < 10)
// result = remainder.data[0] + result;
// else
// result = charSet[(int)remainder.data[0] - 10] + result;
result = charSet[(int)remainder.data[0]] + result;
a = quotient;
}
if(negative)
result = "-" + result;
}
return result;
}
//***********************************************************************
// Returns a hex string showing the contains of the BigInteger
//
// Examples
// -------
// 1) If the value of BigInteger is 255 in base 10, then
// ToHexString() returns "FF"
//
// 2) If the value of BigInteger is -255 in base 10, then
// ToHexString() returns ".....FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01",
// which is the 2's complement representation of -255.
//
//***********************************************************************
public string ToHexString()
{
string result = data[dataLength - 1].ToString("X");
for(int i = dataLength - 2; i >= 0; i--)
{
result += data[i].ToString("X8");
}
return result;
}
//***********************************************************************
// Modulo Exponentiation
//***********************************************************************
public BigInteger modPow(BigInteger exp, BigInteger n)
{
if((exp.data[maxLength-1] & 0x80000000) != 0)
throw (new ArithmeticException("Positive exponents only."));
BigInteger resultNum = 1;
BigInteger tempNum;
bool thisNegative = false;
if((this.data[maxLength-1] & 0x80000000) != 0) // negative this
{
tempNum = -this % n;
thisNegative = true;
}
else
tempNum = this % n; // ensures (tempNum * tempNum) < b^(2k)
if((n.data[maxLength-1] & 0x80000000) != 0) // negative n
n = -n;
// calculate constant = b^(2k) / m
BigInteger constant = new BigInteger();
int i = n.dataLength << 1;
constant.data[i] = 0x00000001;
constant.dataLength = i + 1;
constant = constant / n;
int totalBits = exp.bitCount();
int count = 0;
// perform squaring and multiply exponentiation
for(int pos = 0; pos < exp.dataLength; pos++)
{
uint mask = 0x01;
//Console.WriteLine("pos = " + pos);
for(int index = 0; index < 32; index++)
{
if((exp.data[pos] & mask) != 0)
resultNum = BarrettReduction(resultNum * tempNum, n, constant);
mask <<= 1;
tempNum = BarrettReduction(tempNum * tempNum, n, constant);
if(tempNum.dataLength == 1 && tempNum.data[0] == 1)
{
if(thisNegative && (exp.data[0] & 0x1) != 0) //odd exp
return -resultNum;
return resultNum;
}
count++;
if(count == totalBits)
break;
}
}
if(thisNegative && (exp.data[0] & 0x1) != 0) //odd exp
return -resultNum;
return resultNum;
}
//***********************************************************************
// Fast calculation of modular reduction using Barrett's reduction.
// Requires x < b^(2k), where b is the base. In this case, base is
// 2^32 (uint).
//
// Reference [4]
//***********************************************************************
private BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant)
{
int k = n.dataLength,
kPlusOne = k+1,
kMinusOne = k-1;
BigInteger q1 = new BigInteger();
// q1 = x / b^(k-1)
for(int i = kMinusOne, j = 0; i < x.dataLength; i++, j++)
q1.data[j] = x.data[i];
q1.dataLength = x.dataLength - kMinusOne;
if(q1.dataLength <= 0)
q1.dataLength = 1;
BigInteger q2 = q1 * constant;
BigInteger q3 = new BigInteger();
// q3 = q2 / b^(k+1)
for(int i = kPlusOne, j = 0; i < q2.dataLength; i++, j++)
q3.data[j] = q2.data[i];
q3.dataLength = q2.dataLength - kPlusOne;
if(q3.dataLength <= 0)
q3.dataLength = 1;
// r1 = x mod b^(k+1)
// i.e. keep the lowest (k+1) words
BigInteger r1 = new BigInteger();
int lengthToCopy = (x.dataLength > kPlusOne) ? kPlusOne : x.dataLength;
for(int i = 0; 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 = new BigInteger();
for(int i = 0; i < q3.dataLength; i++)
{
if(q3.data[i] == 0) continue;
ulong mcarry = 0;
int t = i;
for(int j = 0; j < n.dataLength && t < kPlusOne; j++, t++)
{
// t = i + j
ulong val = ((ulong)q3.data[i] * (ulong)n.data[j]) +
(ulong)r2.data[t] + mcarry;
r2.data[t] = (uint)(val & 0xFFFFFFFF);
mcarry = (val >> 32);
}
if(t < kPlusOne)
r2.data[t] = (uint)mcarry;
}
r2.dataLength = kPlusOne;
while(r2.dataLength > 1 && r2.data[r2.dataLength-1] == 0)
r2.dataLength--;
r1 -= r2;
if((r1.data[maxLength-1] & 0x80000000) != 0) // negative
{
BigInteger val = new BigInteger();
val.data[kPlusOne] = 0x00000001;
val.dataLength = kPlusOne + 1;
r1 += val;
}
while(r1 >= n)
r1 -= n;
return r1;
}
//***********************************************************************
// Returns gcd(this, bi)
//***********************************************************************
public BigInteger gcd(BigInteger bi)
{
BigInteger x;
BigInteger y;
if((data[maxLength-1] & 0x80000000) != 0) // negative
x = -this;
else
x = this;
if((bi.data[maxLength-1] & 0x80000000) != 0) // negative
y = -bi;
else
y = bi;
BigInteger g = y;
while(x.dataLength > 1 || (x.dataLength == 1 && x.data[0] != 0))
{
g = x;
x = y % x;
y = g;
}
return g;
}
//***********************************************************************
// Populates "this" with the specified amount of random bits
//***********************************************************************
public void genRandomBits(int bits, Random rand)
{
int dwords = bits >> 5;
int remBits = bits & 0x1F;
if(remBits != 0)
dwords++;
if(dwords > maxLength)
throw (new ArithmeticException("Number of required bits > maxLength."));
for(int i = 0; i < dwords; i++)
data[i] = (uint)(rand.NextDouble() * 0x100000000);
for(int i = dwords; i < maxLength; i++)
data[i] = 0;
if(remBits != 0)
{
uint mask = (uint)(0x01 << (remBits-1));
data[dwords-1] |= mask;
mask = (uint)(0xFFFFFFFF >> (32 - remBits));
data[dwords-1] &= mask;
}
else
data[dwords-1] |= 0x80000000;
dataLength = dwords;
if(dataLength == 0)
dataLength = 1;
}
//***********************************************************************
// Returns the position of the most significant bit in the BigInteger.
//
// Eg. The result is 0, if the value of BigInteger is 0...0000 0000
// The result is 1, if the value of BigInteger is 0...0000 0001
// The result is 2, if the value of BigInteger is 0...0000 0010
// The result is 2, if the value of BigInteger is 0...0000 0011
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -