📄 biginteger.cs
字号:
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";
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;
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)mcarr⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -