BigInteger
public struct BigInteger : IComparable, IFormattable, IComparable<BigInteger>, IEquatable<BigInteger>
Represents an arbitrarily large signed integer.
using Renci.SshNet.Abstractions;
using System;
using System.Collections.Generic;
using System.Globalization;
namespace Renci.SshNet.Common
{
public struct BigInteger : IComparable, IFormattable, IComparable<BigInteger>, IEquatable<BigInteger>
{
private static readonly BigInteger ZeroSingleton = new BigInteger(0);
private static readonly BigInteger OneSingleton = new BigInteger(1);
private static readonly BigInteger MinusOneSingleton = new BigInteger(-1);
private const ulong Base = 4294967296;
private const int Bias = 1075;
private const int DecimalSignMask = int.MinValue;
private readonly uint[] _data;
private readonly short _sign;
public int BitLength {
get {
if (_sign == 0)
return 0;
int num = _data.Length - 1;
while (_data[num] == 0) {
num--;
}
int num2 = BitScanBackward(_data[num]) + 1;
return num * 4 * 8 + num2 + ((_sign <= 0) ? 1 : 0);
}
}
public bool IsEven {
get {
if (_sign != 0)
return (_data[0] & 1) == 0;
return true;
}
}
public bool IsOne {
get {
if (_sign == 1 && _data.Length == 1)
return _data[0] == 1;
return false;
}
}
public bool IsPowerOfTwo {
get {
bool flag = false;
if (_sign != 1)
return false;
uint[] data = _data;
for (int i = 0; i < data.Length; i++) {
int num = PopulationCount(data[i]);
if (num > 0) {
if ((num > 1) | flag)
return false;
flag = true;
}
}
return flag;
}
}
public bool IsZero => _sign == 0;
public int Sign => _sign;
public static BigInteger MinusOne => MinusOneSingleton;
public static BigInteger One => OneSingleton;
public static BigInteger Zero => ZeroSingleton;
public static BigInteger ModInverse(BigInteger bi, BigInteger modulus)
{
BigInteger bigInteger = modulus;
BigInteger bigInteger2 = bi % modulus;
BigInteger bigInteger3 = 0;
BigInteger bigInteger4 = 1;
while (!bigInteger2.IsZero) {
if (bigInteger2.IsOne)
return bigInteger4;
bigInteger3 += bigInteger / bigInteger2 * bigInteger4;
bigInteger %= bigInteger2;
if (bigInteger.IsZero)
break;
if (bigInteger.IsOne)
return modulus - bigInteger3;
bigInteger4 += bigInteger2 / bigInteger * bigInteger3;
bigInteger2 %= bigInteger;
}
return 0;
}
public static BigInteger PositiveMod(BigInteger dividend, BigInteger divisor)
{
BigInteger bigInteger = dividend % divisor;
if (bigInteger < 0)
bigInteger += divisor;
return bigInteger;
}
public static BigInteger Random(int bitLength)
{
byte[] array = new byte[bitLength / 8 + ((bitLength % 8 > 0) ? 1 : 0)];
CryptoAbstraction.GenerateRandom(array);
array[array.Length - 1] = (byte)(array[array.Length - 1] & 127);
return new BigInteger(array);
}
private BigInteger(short sign, uint[] data)
{
_sign = sign;
_data = data;
}
public BigInteger(int value)
{
if (value == 0) {
_sign = 0;
_data = null;
} else if (value > 0) {
_sign = 1;
_data = new uint[1] {
(uint)value
};
} else {
_sign = -1;
_data = new uint[1] {
(uint)(-value)
};
}
}
[CLSCompliant(false)]
public BigInteger(uint value)
{
if (value == 0) {
_sign = 0;
_data = null;
} else {
_sign = 1;
_data = new uint[1] {
value
};
}
}
public BigInteger(long value)
{
if (value == 0) {
_sign = 0;
_data = null;
} else if (value > 0) {
_sign = 1;
uint num = (uint)value;
uint num2 = (uint)(value >> 32);
_data = new uint[(num2 == 0) ? 1 : 2];
_data[0] = num;
if (num2 != 0)
_data[1] = num2;
} else {
_sign = -1;
value = -value;
uint num3 = (uint)value;
uint num4 = (uint)((ulong)value >> 32);
_data = new uint[(num4 == 0) ? 1 : 2];
_data[0] = num3;
if (num4 != 0)
_data[1] = num4;
}
}
[CLSCompliant(false)]
public BigInteger(ulong value)
{
if (value == 0) {
_sign = 0;
_data = null;
} else {
_sign = 1;
uint num = (uint)value;
uint num2 = (uint)(value >> 32);
_data = new uint[(num2 == 0) ? 1 : 2];
_data[0] = num;
if (num2 != 0)
_data[1] = num2;
}
}
private static bool Negative(byte[] v)
{
return (v[7] & 128) != 0;
}
private static ushort Exponent(byte[] v)
{
return (ushort)(((ushort)(v[7] & 127) << 4) | ((ushort)(v[6] & 240) >> 4));
}
private static ulong Mantissa(byte[] v)
{
int num = v[0] | (v[1] << 8) | (v[2] << 16) | (v[3] << 24);
uint num2 = (uint)(v[4] | (v[5] << 8) | ((v[6] & 15) << 16));
return (uint)num | ((ulong)num2 << 32);
}
public BigInteger(double value)
{
if (double.IsNaN(value) || double.IsInfinity(value))
throw new OverflowException();
byte[] bytes = BitConverter.GetBytes(value);
ulong num = Mantissa(bytes);
if (num == 0) {
int num2 = Exponent(bytes);
if (num2 == 0) {
_sign = 0;
_data = null;
} else {
BigInteger value2 = Negative(bytes) ? MinusOne : One;
value2 <<= num2 - 1023;
_sign = value2._sign;
_data = value2._data;
}
} else {
int num3 = Exponent(bytes);
num |= 4503599627370496;
BigInteger value3 = num;
value3 = ((num3 > 1075) ? (value3 << num3 - 1075) : (value3 >> 1075 - num3));
_sign = (short)((!Negative(bytes)) ? 1 : (-1));
_data = value3._data;
}
}
public BigInteger(float value)
{
this = new BigInteger((double)value);
}
public BigInteger(decimal value)
{
int[] bits = decimal.GetBits(decimal.Truncate(value));
int num = 3;
while (num > 0 && bits[num - 1] == 0) {
num--;
}
if (num == 0) {
_sign = 0;
_data = null;
} else {
_sign = (short)(((bits[3] & -2147483648) == 0) ? 1 : (-1));
_data = new uint[num];
_data[0] = (uint)bits[0];
if (num > 1)
_data[1] = (uint)bits[1];
if (num > 2)
_data[2] = (uint)bits[2];
}
}
[CLSCompliant(false)]
public BigInteger(byte[] value)
{
if (value == null)
throw new ArgumentNullException("value");
int num = value.Length;
switch (num) {
case 1:
if (value[0] != 0)
break;
goto case 0;
case 0:
_sign = 0;
_data = null;
return;
}
if ((value[num - 1] & 128) != 0)
_sign = -1;
else
_sign = 1;
if (_sign == 1) {
while (value[num - 1] == 0) {
if (--num == 0) {
_sign = 0;
_data = null;
return;
}
}
int num2;
int num3 = num2 = num / 4;
if ((num & 3) != 0)
num2++;
_data = new uint[num2];
int num4 = 0;
for (int i = 0; i < num3; i++) {
_data[i] = (uint)(value[num4++] | (value[num4++] << 8) | (value[num4++] << 16) | (value[num4++] << 24));
}
num2 = (num & 3);
if (num2 > 0) {
int num9 = _data.Length - 1;
for (int j = 0; j < num2; j++) {
_data[num9] |= (uint)(value[num4++] << j * 8);
}
}
} else {
int num11;
int num12 = num11 = num / 4;
if ((num & 3) != 0)
num11++;
_data = new uint[num11];
uint num13 = 1;
int num14 = 0;
for (int k = 0; k < num12; k++) {
uint num19 = (uint)(value[num14++] | (value[num14++] << 8) | (value[num14++] << 16) | (value[num14++] << 24));
long num20 = (long)num19 - (long)num13;
num19 = (uint)num20;
num13 = (uint)((int)((ulong)num20 >> 32) & 1);
_data[k] = ~num19;
}
num11 = (num & 3);
if (num11 > 0) {
uint num19 = 0;
uint num21 = 0;
for (int l = 0; l < num11; l++) {
num19 = (uint)((int)num19 | (value[num14++] << l * 8));
num21 = ((num21 << 8) | 255);
}
long num23 = num19 - num13;
num19 = (uint)num23;
num13 = (uint)((int)((ulong)num23 >> 32) & 1);
if ((~num19 & num21) == 0)
Array.Resize(ref _data, _data.Length - 1);
else
_data[_data.Length - 1] = (~num19 & num21);
}
if (num13 != 0)
throw new Exception("non zero final carry");
}
}
private static int PopulationCount(uint x)
{
x -= ((x >> 1) & 1431655765);
x = (x & 858993459) + ((x >> 2) & 858993459);
x = ((x + (x >> 4)) & 252645135);
x += x >> 8;
x += x >> 16;
return (int)(x & 63);
}
private static int PopulationCount(ulong x)
{
x -= ((x >> 1) & 6148914691236517205);
x = (x & 3689348814741910323) + ((x >> 2) & 3689348814741910323);
x = ((x + (x >> 4)) & 1085102592571150095);
return (int)(x * 72340172838076673 >> 56);
}
private static int LeadingZeroCount(uint value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return 32 - PopulationCount(value);
}
private static int LeadingZeroCount(ulong value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
return 64 - PopulationCount(value);
}
private static double BuildDouble(int sign, ulong mantissa, int exponent)
{
if (sign == 0 || mantissa == 0)
return 0;
exponent += 1075;
int num = LeadingZeroCount(mantissa) - 11;
if (exponent - num > 2046) {
if (sign <= 0)
return -Infinity;
return Infinity;
}
if (num < 0) {
mantissa >>= -num;
exponent += -num;
} else if (num >= exponent) {
mantissa <<= exponent - 1;
exponent = 0;
} else {
mantissa <<= num;
exponent -= num;
}
mantissa &= 4503599627370495;
if (((long)exponent & 2047) == exponent) {
ulong num2 = (ulong)((long)mantissa | ((long)exponent << 52));
if (sign < 0)
num2 = (ulong)((long)num2 | -9223372036854775808);
return BitConverter.Int64BitsToDouble((long)num2);
}
if (sign <= 0)
return -Infinity;
return Infinity;
}
public static explicit operator int(BigInteger value)
{
if (value._data == null)
return 0;
if (value._data.Length > 1)
throw new OverflowException();
uint num = value._data[0];
if (value._sign == 1) {
if (num > 2147483647)
throw new OverflowException();
return (int)num;
}
if (value._sign == -1) {
if (num > 2147483648)
throw new OverflowException();
return (int)(0 - num);
}
return 0;
}
public static explicit operator uint(BigInteger value)
{
if (value._data == null)
return 0;
if (value._data.Length > 1 || value._sign == -1)
throw new OverflowException();
return value._data[0];
}
public static explicit operator short(BigInteger value)
{
int num = (int)value;
if (num < -32768 || num > 32767)
throw new OverflowException();
return (short)num;
}
public static explicit operator ushort(BigInteger value)
{
uint num = (uint)value;
if (num > 65535)
throw new OverflowException();
return (ushort)num;
}
public static explicit operator byte(BigInteger value)
{
uint num = (uint)value;
if (num > 255)
throw new OverflowException();
return (byte)num;
}
public static explicit operator sbyte(BigInteger value)
{
int num = (int)value;
if (num < -128 || num > 127)
throw new OverflowException();
return (sbyte)num;
}
public static explicit operator long(BigInteger value)
{
if (value._data == null)
return 0;
if (value._data.Length > 2)
throw new OverflowException();
uint num = value._data[0];
if (value._data.Length == 1) {
if (value._sign == 1)
return num;
return 0 - num;
}
uint num2 = value._data[1];
if (value._sign == 1) {
if (num2 >= 2147483648)
throw new OverflowException();
return (long)(((ulong)num2 << 32) | num);
}
ulong num3 = 0 - (((ulong)num2 << 32) | num);
if ((long)num3 > 0)
throw new OverflowException();
return (long)num3;
}
public static explicit operator ulong(BigInteger value)
{
if (value._data == null)
return 0;
if (value._data.Length > 2 || value._sign == -1)
throw new OverflowException();
uint num = value._data[0];
if (value._data.Length == 1)
return num;
return ((ulong)value._data[1] << 32) | num;
}
public static explicit operator double(BigInteger value)
{
if (value._data != null) {
switch (value._data.LongLength) {
case 1:
return BuildDouble(value._sign, value._data[0], 0);
case 2:
return BuildDouble(value._sign, ((ulong)value._data[1] << 32) | value._data[0], 0);
default: {
int num = value._data.Length - 1;
uint num2 = value._data[num];
ulong num3 = ((ulong)num2 << 32) | value._data[num - 1];
int num4 = LeadingZeroCount(num2) - 11;
return BuildDouble(mantissa: (num4 <= 0) ? (num3 >> -num4) : ((num3 << num4) | (value._data[num - 2] >> 32 - num4)), sign: value._sign, exponent: (value._data.Length - 2) * 32 - num4);
}
}
}
return 0;
}
public static explicit operator float(BigInteger value)
{
return (float)(double)value;
}
public static explicit operator decimal(BigInteger value)
{
if (value._data == null)
return decimal.Zero;
uint[] data = value._data;
if (data.Length > 3)
throw new OverflowException();
int lo = 0;
int mid = 0;
int hi = 0;
if (data.Length > 2)
hi = (int)data[2];
if (data.Length > 1)
mid = (int)data[1];
if (data.Length != 0)
lo = (int)data[0];
return new decimal(lo, mid, hi, value._sign < 0, 0);
}
public static implicit operator BigInteger(int value)
{
return new BigInteger(value);
}
public static implicit operator BigInteger(uint value)
{
return new BigInteger(value);
}
public static implicit operator BigInteger(short value)
{
return new BigInteger(value);
}
public static implicit operator BigInteger(ushort value)
{
return new BigInteger(value);
}
public static implicit operator BigInteger(byte value)
{
return new BigInteger(value);
}
public static implicit operator BigInteger(sbyte value)
{
return new BigInteger(value);
}
public static implicit operator BigInteger(long value)
{
return new BigInteger(value);
}
public static implicit operator BigInteger(ulong value)
{
return new BigInteger(value);
}
public static explicit operator BigInteger(double value)
{
return new BigInteger(value);
}
public static explicit operator BigInteger(float value)
{
return new BigInteger(value);
}
public static explicit operator BigInteger(decimal value)
{
return new BigInteger(value);
}
public static BigInteger operator +(BigInteger left, BigInteger right)
{
if (left._sign == 0)
return right;
if (right._sign == 0)
return left;
if (left._sign == right._sign)
return new BigInteger(left._sign, CoreAdd(left._data, right._data));
int num = CoreCompare(left._data, right._data);
if (num == 0)
return Zero;
if (num > 0)
return new BigInteger(left._sign, CoreSub(left._data, right._data));
return new BigInteger(right._sign, CoreSub(right._data, left._data));
}
public static BigInteger operator -(BigInteger left, BigInteger right)
{
if (right._sign == 0)
return left;
if (left._sign == 0)
return new BigInteger((short)(-right._sign), right._data);
if (left._sign == right._sign) {
int num = CoreCompare(left._data, right._data);
if (num == 0)
return Zero;
if (num > 0)
return new BigInteger(left._sign, CoreSub(left._data, right._data));
return new BigInteger((short)(-right._sign), CoreSub(right._data, left._data));
}
return new BigInteger(left._sign, CoreAdd(left._data, right._data));
}
public static BigInteger operator *(BigInteger left, BigInteger right)
{
if (left._sign == 0 || right._sign == 0)
return Zero;
if (left._data[0] == 1 && left._data.Length == 1) {
if (left._sign == 1)
return right;
return new BigInteger((short)(-right._sign), right._data);
}
if (right._data[0] == 1 && right._data.Length == 1) {
if (right._sign == 1)
return left;
return new BigInteger((short)(-left._sign), left._data);
}
uint[] data = left._data;
uint[] data2 = right._data;
uint[] array = new uint[data.Length + data2.Length];
for (int i = 0; i < data.Length; i++) {
uint num = data[i];
int num2 = i;
ulong num3 = 0;
for (int j = 0; j < data2.Length; j++) {
num3 = (ulong)((long)num3 + (long)num * (long)data2[j] + array[num2]);
array[num2++] = (uint)num3;
num3 >>= 32;
}
while (num3 != 0) {
num3 += array[num2];
array[num2++] = (uint)num3;
num3 >>= 32;
}
}
int num6 = array.Length - 1;
while (num6 >= 0 && array[num6] == 0) {
num6--;
}
if (num6 < array.Length - 1)
Array.Resize(ref array, num6 + 1);
return new BigInteger((short)(left._sign * right._sign), array);
}
public static BigInteger operator /(BigInteger dividend, BigInteger divisor)
{
if (divisor._sign == 0)
throw new DivideByZeroException();
if (dividend._sign == 0)
return dividend;
DivModUnsigned(dividend._data, divisor._data, out uint[] q, out uint[] _);
int num = q.Length - 1;
while (num >= 0 && q[num] == 0) {
num--;
}
if (num == -1)
return Zero;
if (num < q.Length - 1)
Array.Resize(ref q, num + 1);
return new BigInteger((short)(dividend._sign * divisor._sign), q);
}
public static BigInteger operator %(BigInteger dividend, BigInteger divisor)
{
if (divisor._sign == 0)
throw new DivideByZeroException();
if (dividend._sign == 0)
return dividend;
DivModUnsigned(dividend._data, divisor._data, out uint[] _, out uint[] r);
int num = r.Length - 1;
while (num >= 0 && r[num] == 0) {
num--;
}
if (num == -1)
return Zero;
if (num < r.Length - 1)
Array.Resize(ref r, num + 1);
return new BigInteger(dividend._sign, r);
}
public static BigInteger operator -(BigInteger value)
{
if (value._data == null)
return value;
return new BigInteger((short)(-value._sign), value._data);
}
public static BigInteger operator +(BigInteger value)
{
return value;
}
public static BigInteger operator ++(BigInteger value)
{
if (value._data == null)
return One;
short sign = value._sign;
uint[] data = value._data;
if (data.Length == 1) {
if (sign == -1 && data[0] == 1)
return Zero;
if (sign == 0)
return One;
}
data = ((sign == -1) ? CoreSub(data, 1) : CoreAdd(data, 1));
return new BigInteger(sign, data);
}
public static BigInteger operator --(BigInteger value)
{
if (value._data == null)
return MinusOne;
short sign = value._sign;
uint[] data = value._data;
if (data.Length == 1) {
if (sign == 1 && data[0] == 1)
return Zero;
if (sign == 0)
return MinusOne;
}
data = ((sign == -1) ? CoreAdd(data, 1) : CoreSub(data, 1));
return new BigInteger(sign, data);
}
public static BigInteger operator &(BigInteger left, BigInteger right)
{
if (left._sign == 0)
return left;
if (right._sign == 0)
return right;
uint[] data = left._data;
uint[] data2 = right._data;
int sign = left._sign;
int sign2 = right._sign;
bool flag = sign == sign2 && sign == -1;
uint[] array = new uint[Math.Max(data.Length, data2.Length)];
ulong num = 1;
ulong num2 = 1;
ulong num3 = 1;
int i;
for (i = 0; i < array.Length; i++) {
uint num4 = 0;
if (i < data.Length)
num4 = data[i];
if (sign == -1) {
num = ~num4 + num;
num4 = (uint)num;
num = (uint)(num >> 32);
}
uint num5 = 0;
if (i < data2.Length)
num5 = data2[i];
if (sign2 == -1) {
num2 = ~num5 + num2;
num5 = (uint)num2;
num2 = (uint)(num2 >> 32);
}
uint num6 = num4 & num5;
if (flag) {
num3 = num6 - num3;
num6 = (uint)(~num3);
num3 = (uint)((int)(num3 >> 32) & 1);
}
array[i] = num6;
}
i = array.Length - 1;
while (i >= 0 && array[i] == 0) {
i--;
}
if (i == -1)
return Zero;
if (i < array.Length - 1)
Array.Resize(ref array, i + 1);
return new BigInteger((short)((!flag) ? 1 : (-1)), array);
}
public static BigInteger operator |(BigInteger left, BigInteger right)
{
if (left._sign == 0)
return right;
if (right._sign == 0)
return left;
uint[] data = left._data;
uint[] data2 = right._data;
int sign = left._sign;
int sign2 = right._sign;
bool flag = sign == -1 || sign2 == -1;
uint[] array = new uint[Math.Max(data.Length, data2.Length)];
ulong num = 1;
ulong num2 = 1;
ulong num3 = 1;
int i;
for (i = 0; i < array.Length; i++) {
uint num4 = 0;
if (i < data.Length)
num4 = data[i];
if (sign == -1) {
num = ~num4 + num;
num4 = (uint)num;
num = (uint)(num >> 32);
}
uint num5 = 0;
if (i < data2.Length)
num5 = data2[i];
if (sign2 == -1) {
num2 = ~num5 + num2;
num5 = (uint)num2;
num2 = (uint)(num2 >> 32);
}
uint num6 = num4 | num5;
if (flag) {
num3 = num6 - num3;
num6 = (uint)(~num3);
num3 = (uint)((int)(num3 >> 32) & 1);
}
array[i] = num6;
}
i = array.Length - 1;
while (i >= 0 && array[i] == 0) {
i--;
}
if (i == -1)
return Zero;
if (i < array.Length - 1)
Array.Resize(ref array, i + 1);
return new BigInteger((short)((!flag) ? 1 : (-1)), array);
}
public static BigInteger operator ^(BigInteger left, BigInteger right)
{
if (left._sign == 0)
return right;
if (right._sign == 0)
return left;
uint[] data = left._data;
uint[] data2 = right._data;
int sign = left._sign;
int sign2 = right._sign;
bool flag = (sign == -1) ^ (sign2 == -1);
uint[] array = new uint[Math.Max(data.Length, data2.Length)];
ulong num = 1;
ulong num2 = 1;
ulong num3 = 1;
int i;
for (i = 0; i < array.Length; i++) {
uint num4 = 0;
if (i < data.Length)
num4 = data[i];
if (sign == -1) {
num = ~num4 + num;
num4 = (uint)num;
num = (uint)(num >> 32);
}
uint num5 = 0;
if (i < data2.Length)
num5 = data2[i];
if (sign2 == -1) {
num2 = ~num5 + num2;
num5 = (uint)num2;
num2 = (uint)(num2 >> 32);
}
uint num6 = num4 ^ num5;
if (flag) {
num3 = num6 - num3;
num6 = (uint)(~num3);
num3 = (uint)((int)(num3 >> 32) & 1);
}
array[i] = num6;
}
i = array.Length - 1;
while (i >= 0 && array[i] == 0) {
i--;
}
if (i == -1)
return Zero;
if (i < array.Length - 1)
Array.Resize(ref array, i + 1);
return new BigInteger((short)((!flag) ? 1 : (-1)), array);
}
public static BigInteger operator ~(BigInteger value)
{
if (value._data == null)
return MinusOne;
uint[] data = value._data;
int sign = value._sign;
bool flag = sign == 1;
uint[] array = new uint[data.Length];
ulong num = 1;
ulong num2 = 1;
int i;
for (i = 0; i < array.Length; i++) {
uint num3 = data[i];
if (sign == -1) {
num = ~num3 + num;
num3 = (uint)num;
num = (uint)(num >> 32);
}
num3 = ~num3;
if (flag) {
num2 = num3 - num2;
num3 = (uint)(~num2);
num2 = (uint)((int)(num2 >> 32) & 1);
}
array[i] = num3;
}
i = array.Length - 1;
while (i >= 0 && array[i] == 0) {
i--;
}
if (i == -1)
return Zero;
if (i < array.Length - 1)
Array.Resize(ref array, i + 1);
return new BigInteger((short)((!flag) ? 1 : (-1)), array);
}
private static int BitScanBackward(uint word)
{
for (int num = 31; num >= 0; num--) {
uint num2 = (uint)(1 << num);
if ((word & num2) == num2)
return num;
}
return 0;
}
public static BigInteger operator <<(BigInteger value, int shift)
{
if (shift == 0 || value._data == null)
return value;
if (shift < 0)
return value >> -shift;
uint[] data = value._data;
int sign = value._sign;
int num = BitScanBackward(data[data.Length - 1]);
int num2 = shift - (31 - num);
int num3 = (num2 >> 5) + (((num2 & 31) != 0) ? 1 : 0);
uint[] array = new uint[data.Length + num3];
int num4 = shift >> 5;
int num5 = shift & 31;
int num6 = 32 - num5;
if (num6 == 32) {
for (int i = 0; i < data.Length; i++) {
uint num7 = data[i];
array[i + num4] |= num7 << num5;
}
} else {
for (int j = 0; j < data.Length; j++) {
uint num8 = data[j];
array[j + num4] |= num8 << num5;
if (j + num4 + 1 < array.Length)
array[j + num4 + 1] = num8 >> num6;
}
}
return new BigInteger((short)sign, array);
}
public static BigInteger operator >>(BigInteger value, int shift)
{
if (shift == 0 || value._sign == 0)
return value;
if (shift < 0)
return value << -shift;
uint[] data = value._data;
int sign = value._sign;
int num = BitScanBackward(data[data.Length - 1]);
int num2 = shift >> 5;
int num3 = shift & 31;
int num4 = num2;
if (num3 > num)
num4++;
int num5 = data.Length - num4;
if (num5 <= 0) {
if (sign == 1)
return Zero;
return MinusOne;
}
uint[] array = new uint[num5];
int num6 = 32 - num3;
if (num6 == 32) {
for (int num7 = data.Length - 1; num7 >= num2; num7--) {
uint num8 = data[num7];
if (num7 - num2 < array.Length)
array[num7 - num2] |= num8 >> num3;
}
} else {
for (int num9 = data.Length - 1; num9 >= num2; num9--) {
uint num10 = data[num9];
if (num9 - num2 < array.Length)
array[num9 - num2] |= num10 >> num3;
if (num9 - num2 - 1 >= 0)
array[num9 - num2 - 1] = num10 << num6;
}
}
if (sign == -1) {
for (int i = 0; i < num2; i++) {
if (data[i] != 0)
return --new BigInteger((short)sign, array);
}
if (num3 > 0 && data[num2] << num6 != 0)
return --new BigInteger((short)sign, array);
}
return new BigInteger((short)sign, array);
}
public static bool operator <(BigInteger left, BigInteger right)
{
return Compare(left, right) < 0;
}
public static bool operator <(BigInteger left, long right)
{
return left.CompareTo(right) < 0;
}
public static bool operator <(long left, BigInteger right)
{
return right.CompareTo(left) > 0;
}
public static bool operator <(BigInteger left, ulong right)
{
return left.CompareTo(right) < 0;
}
public static bool operator <(ulong left, BigInteger right)
{
return right.CompareTo(left) > 0;
}
public static bool operator <=(BigInteger left, BigInteger right)
{
return Compare(left, right) <= 0;
}
public static bool operator <=(BigInteger left, long right)
{
return left.CompareTo(right) <= 0;
}
public static bool operator <=(long left, BigInteger right)
{
return right.CompareTo(left) >= 0;
}
public static bool operator <=(BigInteger left, ulong right)
{
return left.CompareTo(right) <= 0;
}
public static bool operator <=(ulong left, BigInteger right)
{
return right.CompareTo(left) >= 0;
}
public static bool operator >(BigInteger left, BigInteger right)
{
return Compare(left, right) > 0;
}
public static bool operator >(BigInteger left, long right)
{
return left.CompareTo(right) > 0;
}
public static bool operator >(long left, BigInteger right)
{
return right.CompareTo(left) < 0;
}
public static bool operator >(BigInteger left, ulong right)
{
return left.CompareTo(right) > 0;
}
public static bool operator >(ulong left, BigInteger right)
{
return right.CompareTo(left) < 0;
}
public static bool operator >=(BigInteger left, BigInteger right)
{
return Compare(left, right) >= 0;
}
public static bool operator >=(BigInteger left, long right)
{
return left.CompareTo(right) >= 0;
}
public static bool operator >=(long left, BigInteger right)
{
return right.CompareTo(left) <= 0;
}
public static bool operator >=(BigInteger left, ulong right)
{
return left.CompareTo(right) >= 0;
}
public static bool operator >=(ulong left, BigInteger right)
{
return right.CompareTo(left) <= 0;
}
public static bool operator ==(BigInteger left, BigInteger right)
{
return Compare(left, right) == 0;
}
public static bool operator ==(BigInteger left, long right)
{
return left.CompareTo(right) == 0;
}
public static bool operator ==(long left, BigInteger right)
{
return right.CompareTo(left) == 0;
}
public static bool operator ==(BigInteger left, ulong right)
{
return left.CompareTo(right) == 0;
}
public static bool operator ==(ulong left, BigInteger right)
{
return right.CompareTo(left) == 0;
}
public static bool operator !=(BigInteger left, BigInteger right)
{
return Compare(left, right) != 0;
}
public static bool operator !=(BigInteger left, long right)
{
return left.CompareTo(right) != 0;
}
public static bool operator !=(long left, BigInteger right)
{
return right.CompareTo(left) != 0;
}
public static bool operator !=(BigInteger left, ulong right)
{
return left.CompareTo(right) != 0;
}
public static bool operator !=(ulong left, BigInteger right)
{
return right.CompareTo(left) != 0;
}
public override bool Equals(object obj)
{
if (!(obj is BigInteger))
return false;
return Equals((BigInteger)obj);
}
public bool Equals(BigInteger other)
{
if (_sign != other._sign)
return false;
int num = (_data != null) ? _data.Length : 0;
int num2 = (other._data != null) ? other._data.Length : 0;
if (num != num2)
return false;
for (int i = 0; i < num; i++) {
if (_data[i] != other._data[i])
return false;
}
return true;
}
public bool Equals(long other)
{
return CompareTo(other) == 0;
}
public override string ToString()
{
return ToString(10, null);
}
private string ToStringWithPadding(string format, uint radix, IFormatProvider provider)
{
if (format.Length > 1) {
int num = Convert.ToInt32(format.Substring(1), CultureInfo.InvariantCulture.NumberFormat);
string text = ToString(radix, provider);
if (text.Length < num) {
string text2 = new string('0', num - text.Length);
if (text[0] != '-')
return text2 + text;
return "-" + text2 + text.Substring(1);
}
return text;
}
return ToString(radix, provider);
}
public string ToString(string format)
{
return ToString(format, null);
}
public string ToString(IFormatProvider provider)
{
return ToString(null, provider);
}
public string ToString(string format, IFormatProvider provider)
{
if (!string.IsNullOrEmpty(format)) {
switch (format[0]) {
case 'D':
case 'G':
case 'R':
case 'd':
case 'g':
case 'r':
return ToStringWithPadding(format, 10, provider);
case 'X':
case 'x':
return ToStringWithPadding(format, 16, null);
default:
throw new FormatException($"""{format}""");
}
}
return ToString(10, provider);
}
private static uint[] MakeTwoComplement(uint[] v)
{
uint[] array = new uint[v.Length];
ulong num = 1;
for (int i = 0; i < v.Length; i++) {
uint num2 = v[i];
num = ~num2 + num;
num2 = (uint)num;
num = (uint)(num >> 32);
array[i] = num2;
}
uint num3 = array[array.Length - 1];
int num4 = FirstNonFfByte(num3);
uint num5 = 255;
for (int j = 1; j < num4; j++) {
num5 = ((num5 << 8) | 255);
}
array[array.Length - 1] = (num3 & num5);
return array;
}
private string ToString(uint radix, IFormatProvider provider)
{
if ("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".Length < radix)
throw new ArgumentException("charSet length less than radix", "characterSet");
if (radix == 1)
throw new ArgumentException("There is no such thing as radix one notation", "radix");
if (_sign == 0)
return "0";
if (_data.Length == 1 && _data[0] == 1) {
if (_sign != 1)
return "-1";
return "1";
}
List<char> list = new List<char>(1 + _data.Length * 3 / 10);
BigInteger bigInteger;
if (_sign == 1)
bigInteger = this;
else {
uint[] array = _data;
if (radix > 10)
array = MakeTwoComplement(array);
bigInteger = new BigInteger(1, array);
}
while (bigInteger != 0) {
bigInteger = DivRem(bigInteger, radix, out BigInteger remainder);
list.Add("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[(int)remainder]);
}
if (_sign == -1 && radix == 10) {
NumberFormatInfo numberFormatInfo = null;
if (provider != null)
numberFormatInfo = (provider.GetFormat(typeof(NumberFormatInfo)) as NumberFormatInfo);
if (numberFormatInfo != null) {
string negativeSign = numberFormatInfo.NegativeSign;
for (int num = negativeSign.Length - 1; num >= 0; num--) {
list.Add(negativeSign[num]);
}
} else
list.Add('-');
}
char c = list[list.Count - 1];
if (_sign == 1 && radix > 10 && (c < '0' || c > '9'))
list.Add('0');
list.Reverse();
return new string(list.ToArray());
}
public static BigInteger Parse(string value)
{
if (!Parse(value, false, out BigInteger result, out Exception exc))
throw exc;
return result;
}
public static BigInteger Parse(string value, NumberStyles style)
{
return Parse(value, style, null);
}
public static BigInteger Parse(string value, IFormatProvider provider)
{
return Parse(value, NumberStyles.Integer, provider);
}
public static BigInteger Parse(string value, NumberStyles style, IFormatProvider provider)
{
if (!Parse(value, style, provider, false, out BigInteger result, out Exception exc))
throw exc;
return result;
}
public static bool TryParse(string value, out BigInteger result)
{
Exception exc;
return Parse(value, true, out result, out exc);
}
public static bool TryParse(string value, NumberStyles style, IFormatProvider provider, out BigInteger result)
{
if (!Parse(value, style, provider, true, out result, out Exception _)) {
result = Zero;
return false;
}
return true;
}
private static bool Parse(string value, NumberStyles style, IFormatProvider fp, bool tryParse, out BigInteger result, out Exception exc)
{
result = Zero;
exc = null;
if (value == null) {
if (!tryParse)
exc = new ArgumentNullException("value");
return false;
}
if (value.Length == 0) {
if (!tryParse)
exc = GetFormatException();
return false;
}
NumberFormatInfo numberFormatInfo = null;
if (fp != null) {
Type typeFromHandle = typeof(NumberFormatInfo);
numberFormatInfo = (NumberFormatInfo)fp.GetFormat(typeFromHandle);
}
if (numberFormatInfo == null)
numberFormatInfo = NumberFormatInfo.CurrentInfo;
if (!CheckStyle(style, tryParse, ref exc))
return false;
bool flag = (style & NumberStyles.AllowCurrencySymbol) != NumberStyles.None;
bool flag2 = (style & NumberStyles.AllowHexSpecifier) != NumberStyles.None;
bool flag3 = (style & NumberStyles.AllowThousands) != NumberStyles.None;
bool flag4 = (style & NumberStyles.AllowDecimalPoint) != NumberStyles.None;
bool flag5 = (style & NumberStyles.AllowParentheses) != NumberStyles.None;
bool flag6 = (style & NumberStyles.AllowTrailingSign) != NumberStyles.None;
bool flag7 = (style & NumberStyles.AllowLeadingSign) != NumberStyles.None;
bool flag8 = (style & NumberStyles.AllowTrailingWhite) != NumberStyles.None;
bool flag9 = (style & NumberStyles.AllowLeadingWhite) != NumberStyles.None;
bool flag10 = (style & NumberStyles.AllowExponent) != NumberStyles.None;
int pos = 0;
if (flag9 && !JumpOverWhitespace(ref pos, value, true, tryParse, ref exc))
return false;
bool flag11 = false;
bool negative = false;
bool foundSign = false;
bool foundCurrency = false;
if (flag5 && value[pos] == '(') {
flag11 = true;
foundSign = true;
negative = true;
pos++;
if (flag9 && !JumpOverWhitespace(ref pos, value, true, tryParse, ref exc))
return false;
if (value.Substring(pos, numberFormatInfo.NegativeSign.Length) == numberFormatInfo.NegativeSign) {
if (!tryParse)
exc = GetFormatException();
return false;
}
if (value.Substring(pos, numberFormatInfo.PositiveSign.Length) == numberFormatInfo.PositiveSign) {
if (!tryParse)
exc = GetFormatException();
return false;
}
}
if (flag7 && !foundSign) {
FindSign(ref pos, value, numberFormatInfo, ref foundSign, ref negative);
if (foundSign) {
if (flag9 && !JumpOverWhitespace(ref pos, value, true, tryParse, ref exc))
return false;
if (flag) {
FindCurrency(ref pos, value, numberFormatInfo, ref foundCurrency);
if ((foundCurrency & flag9) && !JumpOverWhitespace(ref pos, value, true, tryParse, ref exc))
return false;
}
}
}
if (flag && !foundCurrency) {
FindCurrency(ref pos, value, numberFormatInfo, ref foundCurrency);
if (foundCurrency) {
if (flag9 && !JumpOverWhitespace(ref pos, value, true, tryParse, ref exc))
return false;
if (foundCurrency && (!foundSign & flag7)) {
FindSign(ref pos, value, numberFormatInfo, ref foundSign, ref negative);
if ((foundSign & flag9) && !JumpOverWhitespace(ref pos, value, true, tryParse, ref exc))
return false;
}
}
}
BigInteger bigInteger = Zero;
int num = 0;
int num2 = -1;
bool flag12 = true;
while (pos < value.Length) {
if (!ValidDigit(value[pos], flag2)) {
if (!flag3 || (!FindOther(ref pos, value, numberFormatInfo.NumberGroupSeparator) && !FindOther(ref pos, value, numberFormatInfo.CurrencyGroupSeparator))) {
if (!flag4 || num2 >= 0 || (!FindOther(ref pos, value, numberFormatInfo.NumberDecimalSeparator) && !FindOther(ref pos, value, numberFormatInfo.CurrencyDecimalSeparator)))
break;
num2 = num;
}
} else {
num++;
if (flag2) {
char c = value[pos++];
byte b = char.IsDigit(c) ? ((byte)(c - 48)) : ((!char.IsLower(c)) ? ((byte)(c - 65 + 10)) : ((byte)(c - 97 + 10)));
if (flag12 && b >= 8)
negative = true;
bigInteger = bigInteger * (BigInteger)16 + (BigInteger)b;
flag12 = false;
} else
bigInteger = bigInteger * (BigInteger)10 + (BigInteger)(byte)(value[pos++] - 48);
}
}
if (num == 0) {
if (!tryParse)
exc = GetFormatException();
return false;
}
if (flag2 & negative) {
BigInteger right = Pow(16, num) - (BigInteger)1;
bigInteger = (bigInteger ^ right) + (BigInteger)1;
}
int exponent = 0;
if (flag10 && FindExponent(ref pos, value, ref exponent, tryParse, ref exc) && exc != null)
return false;
if (flag6 && !foundSign) {
FindSign(ref pos, value, numberFormatInfo, ref foundSign, ref negative);
if (foundSign && pos < value.Length && flag8 && !JumpOverWhitespace(ref pos, value, true, tryParse, ref exc))
return false;
}
if (flag && !foundCurrency) {
if (flag8 && pos < value.Length && !JumpOverWhitespace(ref pos, value, false, tryParse, ref exc))
return false;
FindCurrency(ref pos, value, numberFormatInfo, ref foundCurrency);
if (foundCurrency && pos < value.Length) {
if (flag8 && !JumpOverWhitespace(ref pos, value, true, tryParse, ref exc))
return false;
if (!foundSign & flag6)
FindSign(ref pos, value, numberFormatInfo, ref foundSign, ref negative);
}
}
if (flag8 && pos < value.Length && !JumpOverWhitespace(ref pos, value, false, tryParse, ref exc))
return false;
if (flag11) {
if (pos >= value.Length || value[pos++] != ')') {
if (!tryParse)
exc = GetFormatException();
return false;
}
if (flag8 && pos < value.Length && !JumpOverWhitespace(ref pos, value, false, tryParse, ref exc))
return false;
}
if (pos < value.Length && value[pos] != 0) {
if (!tryParse)
exc = GetFormatException();
return false;
}
if (num2 >= 0)
exponent = exponent - num + num2;
if (exponent < 0) {
bigInteger = DivRem(bigInteger, Pow(10, -exponent), out BigInteger remainder);
if (!remainder.IsZero) {
if (!tryParse) {
string[] obj = new string[6] {
"Value too large or too small. exp=",
exponent.ToString(),
" rem = ",
null,
null,
null
};
BigInteger bigInteger2 = remainder;
obj[3] = bigInteger2.ToString();
obj[4] = " pow = ";
bigInteger2 = Pow(10, -exponent);
obj[5] = bigInteger2.ToString();
exc = new OverflowException(string.Concat(obj));
}
return false;
}
} else if (exponent > 0) {
bigInteger = Pow(10, exponent) * bigInteger;
}
if (bigInteger._sign == 0)
result = bigInteger;
else if (negative) {
result = new BigInteger(-1, bigInteger._data);
} else {
result = new BigInteger(1, bigInteger._data);
}
return true;
}
private static bool CheckStyle(NumberStyles style, bool tryParse, ref Exception exc)
{
if ((style & NumberStyles.AllowHexSpecifier) != 0) {
NumberStyles numberStyles = style ^ NumberStyles.AllowHexSpecifier;
if ((numberStyles & NumberStyles.AllowLeadingWhite) != 0)
numberStyles ^= NumberStyles.AllowLeadingWhite;
if ((numberStyles & NumberStyles.AllowTrailingWhite) != 0)
numberStyles ^= NumberStyles.AllowTrailingWhite;
if (numberStyles != 0) {
if (!tryParse)
exc = new ArgumentException("With AllowHexSpecifier only AllowLeadingWhite and AllowTrailingWhite are permitted.");
return false;
}
} else if ((uint)style > 511) {
if (!tryParse)
exc = new ArgumentException("Not a valid number style");
return false;
}
return true;
}
private static bool JumpOverWhitespace(ref int pos, string s, bool reportError, bool tryParse, ref Exception exc)
{
while (pos < s.Length && char.IsWhiteSpace(s[pos])) {
pos++;
}
if (reportError && pos >= s.Length) {
if (!tryParse)
exc = GetFormatException();
return false;
}
return true;
}
private static void FindSign(ref int pos, string s, NumberFormatInfo nfi, ref bool foundSign, ref bool negative)
{
if (pos + nfi.NegativeSign.Length <= s.Length && string.CompareOrdinal(s, pos, nfi.NegativeSign, 0, nfi.NegativeSign.Length) == 0) {
negative = true;
foundSign = true;
pos += nfi.NegativeSign.Length;
} else if (pos + nfi.PositiveSign.Length <= s.Length && string.CompareOrdinal(s, pos, nfi.PositiveSign, 0, nfi.PositiveSign.Length) == 0) {
negative = false;
pos += nfi.PositiveSign.Length;
foundSign = true;
}
}
private static void FindCurrency(ref int pos, string s, NumberFormatInfo nfi, ref bool foundCurrency)
{
if (pos + nfi.CurrencySymbol.Length <= s.Length && s.Substring(pos, nfi.CurrencySymbol.Length) == nfi.CurrencySymbol) {
foundCurrency = true;
pos += nfi.CurrencySymbol.Length;
}
}
private static bool FindExponent(ref int pos, string s, ref int exponent, bool tryParse, ref Exception exc)
{
exponent = 0;
if (pos >= s.Length || (s[pos] != 'e' && s[pos] != 'E')) {
exc = null;
return false;
}
int i = pos + 1;
if (i == s.Length) {
exc = (tryParse ? null : GetFormatException());
return true;
}
bool flag = false;
if (s[i] == '-') {
flag = true;
if (++i == s.Length) {
exc = (tryParse ? null : GetFormatException());
return true;
}
}
if (s[i] == '+' && ++i == s.Length) {
exc = (tryParse ? null : GetFormatException());
return true;
}
long num = 0;
for (; i < s.Length; i++) {
if (!char.IsDigit(s[i])) {
exc = (tryParse ? null : GetFormatException());
return true;
}
checked {
num = num * 10 - (unchecked((int)s[i]) - 48);
if (num < -2147483648 || num > 2147483647) {
exc = (tryParse ? null : new OverflowException("Value too large or too small."));
return true;
}
}
}
if (!flag)
num = -num;
exc = null;
exponent = (int)num;
pos = i;
return true;
}
private static bool FindOther(ref int pos, string s, string other)
{
if (pos + other.Length <= s.Length && s.Substring(pos, other.Length) == other) {
pos += other.Length;
return true;
}
return false;
}
private static bool ValidDigit(char e, bool allowHex)
{
if (allowHex) {
if (!char.IsDigit(e) && (e < 'A' || e > 'F')) {
if (e >= 'a')
return e <= 'f';
return false;
}
return true;
}
return char.IsDigit(e);
}
private static Exception GetFormatException()
{
return new FormatException("Input string was not in the correct format");
}
private static bool ProcessTrailingWhitespace(bool tryParse, string s, int position, ref Exception exc)
{
int length = s.Length;
for (int i = position; i < length; i++) {
char c = s[i];
if (c != 0 && !char.IsWhiteSpace(c)) {
if (!tryParse)
exc = GetFormatException();
return false;
}
}
return true;
}
private static bool Parse(string value, bool tryParse, out BigInteger result, out Exception exc)
{
int num = 1;
bool flag = false;
result = Zero;
exc = null;
if (value == null) {
if (!tryParse)
exc = new ArgumentNullException("value");
return false;
}
int length = value.Length;
int i;
for (i = 0; i < length; i++) {
char c = value[i];
if (!char.IsWhiteSpace(c))
break;
}
if (i == length) {
if (!tryParse)
exc = GetFormatException();
return false;
}
NumberFormatInfo currentInfo = NumberFormatInfo.CurrentInfo;
string negativeSign = currentInfo.NegativeSign;
string positiveSign = currentInfo.PositiveSign;
if (string.CompareOrdinal(value, i, positiveSign, 0, positiveSign.Length) == 0)
i += positiveSign.Length;
else if (string.CompareOrdinal(value, i, negativeSign, 0, negativeSign.Length) == 0) {
num = -1;
i += negativeSign.Length;
}
BigInteger bigInteger = Zero;
for (; i < length; i++) {
char c = value[i];
if (c == ' ')
i = length;
else if (c >= '0' && c <= '9') {
byte value2 = (byte)(c - 48);
bigInteger = bigInteger * (BigInteger)10 + (BigInteger)value2;
flag = true;
} else if (!ProcessTrailingWhitespace(tryParse, value, i, ref exc)) {
return false;
}
}
if (!flag) {
if (!tryParse)
exc = GetFormatException();
return false;
}
if (bigInteger._sign == 0)
result = bigInteger;
else if (num == -1) {
result = new BigInteger(-1, bigInteger._data);
} else {
result = new BigInteger(1, bigInteger._data);
}
return true;
}
public static BigInteger Min(BigInteger left, BigInteger right)
{
int sign = left._sign;
int sign2 = right._sign;
if (sign < sign2)
return left;
if (sign2 < sign)
return right;
int num = CoreCompare(left._data, right._data);
if (sign == -1)
num = -num;
if (num <= 0)
return left;
return right;
}
public static BigInteger Max(BigInteger left, BigInteger right)
{
int sign = left._sign;
int sign2 = right._sign;
if (sign > sign2)
return left;
if (sign2 > sign)
return right;
int num = CoreCompare(left._data, right._data);
if (sign == -1)
num = -num;
if (num >= 0)
return left;
return right;
}
public static BigInteger Abs(BigInteger value)
{
return new BigInteger(Math.Abs(value._sign), value._data);
}
public static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder)
{
if (divisor._sign == 0)
throw new DivideByZeroException();
if (dividend._sign == 0) {
remainder = dividend;
return dividend;
}
DivModUnsigned(dividend._data, divisor._data, out uint[] q, out uint[] r);
int num = r.Length - 1;
while (num >= 0 && r[num] == 0) {
num--;
}
if (num == -1)
remainder = Zero;
else {
if (num < r.Length - 1)
Array.Resize(ref r, num + 1);
remainder = new BigInteger(dividend._sign, r);
}
num = q.Length - 1;
while (num >= 0 && q[num] == 0) {
num--;
}
if (num == -1)
return Zero;
if (num < q.Length - 1)
Array.Resize(ref q, num + 1);
return new BigInteger((short)(dividend._sign * divisor._sign), q);
}
public static BigInteger Pow(BigInteger value, int exponent)
{
if (exponent >= 0) {
switch (exponent) {
case 0:
return One;
case 1:
return value;
default: {
BigInteger bigInteger = One;
while (exponent != 0) {
if ((exponent & 1) != 0)
bigInteger *= value;
if (exponent == 1)
break;
value *= value;
exponent >>= 1;
}
return bigInteger;
}
}
}
throw new ArgumentOutOfRangeException("exponent", "exp must be >= 0");
}
public static BigInteger ModPow(BigInteger value, BigInteger exponent, BigInteger modulus)
{
if (exponent._sign == -1)
throw new ArgumentOutOfRangeException("exponent", "power must be >= 0");
if (modulus._sign == 0)
throw new DivideByZeroException();
BigInteger bigInteger = One % modulus;
while (exponent._sign != 0) {
if (!exponent.IsEven) {
bigInteger *= value;
bigInteger %= modulus;
}
if (exponent.IsOne)
break;
value *= value;
value %= modulus;
exponent >>= 1;
}
return bigInteger;
}
public static BigInteger GreatestCommonDivisor(BigInteger left, BigInteger right)
{
if (left._sign != 0 && left._data.Length == 1 && left._data[0] == 1)
return One;
if (right._sign != 0 && right._data.Length == 1 && right._data[0] == 1)
return One;
if (left.IsZero)
return Abs(right);
if (right.IsZero)
return Abs(left);
BigInteger bigInteger = new BigInteger(1, left._data);
BigInteger bigInteger2 = new BigInteger(1, right._data);
BigInteger bigInteger3 = bigInteger2;
while (bigInteger._data.Length > 1) {
bigInteger3 = bigInteger;
bigInteger = bigInteger2 % bigInteger;
bigInteger2 = bigInteger3;
}
if (bigInteger.IsZero)
return bigInteger3;
uint num = bigInteger._data[0];
uint num2 = (uint)(bigInteger2 % (BigInteger)num);
int num3 = 0;
while (((num2 | num) & 1) == 0) {
num2 >>= 1;
num >>= 1;
num3++;
}
while (num2 != 0) {
while ((num2 & 1) == 0) {
num2 >>= 1;
}
while ((num & 1) == 0) {
num >>= 1;
}
if (num2 >= num)
num2 = num2 - num >> 1;
else
num = num - num2 >> 1;
}
return num << num3;
}
public static double Log(BigInteger value, double baseValue)
{
if (value._sign == -1 || baseValue == 1 || baseValue == -1 || baseValue == -Infinity || double.IsNaN(baseValue))
return NaN;
if (baseValue == 0 || baseValue == Infinity) {
if (!value.IsOne)
return NaN;
return 0;
}
if (value._data == null)
return -Infinity;
int num = value._data.Length - 1;
int num2 = -1;
for (int num3 = 31; num3 >= 0; num3--) {
if ((value._data[num] & (1 << num3)) != 0) {
num2 = num3 + num * 32;
break;
}
}
long num4 = num2;
double num5 = 0;
double num6 = 1;
BigInteger value2 = One;
long num7;
for (num7 = num4; num7 > 2147483647; num7 -= 2147483647) {
value2 <<= 2147483647;
}
value2 <<= (int)num7;
for (long num8 = num4; num8 >= 0; num8--) {
if ((value & value2)._sign != 0)
num5 += num6;
num6 *= 0.5;
value2 >>= 1;
}
return (Math.Log(num5) + Math.Log(2) * (double)num4) / Math.Log(baseValue);
}
public static double Log(BigInteger value)
{
return Log(value, 2.718281828459045);
}
public static double Log10(BigInteger value)
{
return Log(value, 10);
}
[CLSCompliant(false)]
public bool Equals(ulong other)
{
return CompareTo(other) == 0;
}
public override int GetHashCode()
{
uint num = (uint)((long)_sign * 16843009);
if (_data != null) {
uint[] data = _data;
foreach (uint num2 in data) {
num ^= num2;
}
}
return (int)num;
}
public static BigInteger Add(BigInteger left, BigInteger right)
{
return left + right;
}
public static BigInteger Subtract(BigInteger left, BigInteger right)
{
return left - right;
}
public static BigInteger Multiply(BigInteger left, BigInteger right)
{
return left * right;
}
public static BigInteger Divide(BigInteger dividend, BigInteger divisor)
{
return dividend / divisor;
}
public static BigInteger Remainder(BigInteger dividend, BigInteger divisor)
{
return dividend % divisor;
}
public static BigInteger Negate(BigInteger value)
{
return -value;
}
public int CompareTo(object obj)
{
if (obj == null)
return 1;
if (!(obj is BigInteger))
return -1;
return Compare(this, (BigInteger)obj);
}
public int CompareTo(BigInteger other)
{
return Compare(this, other);
}
[CLSCompliant(false)]
public int CompareTo(ulong other)
{
if (_sign < 0)
return -1;
if (_sign == 0) {
if (other != 0)
return -1;
return 0;
}
if (_data.Length > 2)
return 1;
uint high = (uint)(other >> 32);
uint low = (uint)other;
return LongCompare(low, high);
}
private int LongCompare(uint low, uint high)
{
uint num = 0;
if (_data.Length > 1)
num = _data[1];
if (num > high)
return 1;
if (num < high)
return -1;
uint num2 = _data[0];
if (num2 > low)
return 1;
if (num2 < low)
return -1;
return 0;
}
public int CompareTo(long other)
{
int sign = _sign;
int num = Math.Sign(other);
if (sign != num) {
if (sign <= num)
return -1;
return 1;
}
if (sign == 0)
return 0;
if (_data.Length > 2)
return _sign;
if (other < 0)
other = -other;
uint low = (uint)other;
uint high = (uint)((ulong)other >> 32);
int num2 = LongCompare(low, high);
if (sign == -1)
num2 = -num2;
return num2;
}
public static int Compare(BigInteger left, BigInteger right)
{
int sign = left._sign;
int sign2 = right._sign;
if (sign != sign2) {
if (sign <= sign2)
return -1;
return 1;
}
int num = CoreCompare(left._data, right._data);
if (sign < 0)
num = -num;
return num;
}
private static int TopByte(uint x)
{
if (((int)x & -65536) != 0) {
if (((int)x & -16777216) != 0)
return 4;
return 3;
}
if ((x & 65280) != 0)
return 2;
return 1;
}
private static int FirstNonFfByte(uint word)
{
if (((int)word & -16777216) != -16777216)
return 4;
if ((word & 16711680) != 16711680)
return 3;
if ((word & 65280) != 65280)
return 2;
return 1;
}
public byte[] ToByteArray()
{
if (_sign == 0)
return new byte[1];
int num = (_data.Length - 1) * 4;
bool flag = false;
uint num2 = _data[_data.Length - 1];
int num3;
if (_sign == 1) {
num3 = TopByte(num2);
uint num4 = (uint)(128 << (num3 - 1) * 8);
if ((num2 & num4) != 0)
flag = true;
} else
num3 = TopByte(num2);
byte[] array = new byte[num + num3 + (flag ? 1 : 0)];
if (_sign == 1) {
int num5 = 0;
int num6 = _data.Length - 1;
for (int i = 0; i < num6; i++) {
uint num7 = _data[i];
array[num5++] = (byte)num7;
array[num5++] = (byte)(num7 >> 8);
array[num5++] = (byte)(num7 >> 16);
array[num5++] = (byte)(num7 >> 24);
}
while (num3-- > 0) {
array[num5++] = (byte)num2;
num2 >>= 8;
}
} else {
int num14 = 0;
int num15 = _data.Length - 1;
uint num16 = 1;
uint num17;
for (int j = 0; j < num15; j++) {
num17 = _data[j];
long num18 = (long)(~num17) + (long)num16;
num17 = (uint)num18;
num16 = (uint)((ulong)num18 >> 32);
array[num14++] = (byte)num17;
array[num14++] = (byte)(num17 >> 8);
array[num14++] = (byte)(num17 >> 16);
array[num14++] = (byte)(num17 >> 24);
}
long num23 = (long)(~num2) + (long)num16;
num17 = (uint)num23;
if ((int)((ulong)num23 >> 32) == 0) {
int num24 = FirstNonFfByte(num17);
bool flag2 = (num17 & (1 << num24 * 8 - 1)) == 0;
int num25 = num24 + (flag2 ? 1 : 0);
if (num25 != num3)
Array.Resize(ref array, num + num25);
while (num24-- > 0) {
array[num14++] = (byte)num17;
num17 >>= 8;
}
if (flag2)
array[num14++] = byte.MaxValue;
} else {
Array.Resize(ref array, num + 5);
array[num14++] = (byte)num17;
array[num14++] = (byte)(num17 >> 8);
array[num14++] = (byte)(num17 >> 16);
array[num14++] = (byte)(num17 >> 24);
array[num14++] = byte.MaxValue;
}
}
return array;
}
private static uint[] CoreAdd(uint[] a, uint[] b)
{
if (a.Length < b.Length) {
uint[] array = a;
a = b;
b = array;
}
int num = a.Length;
int num2 = b.Length;
uint[] array2 = new uint[num];
ulong num3 = 0;
int i;
for (i = 0; i < num2; i++) {
num3 = num3 + a[i] + b[i];
array2[i] = (uint)num3;
num3 >>= 32;
}
for (; i < num; i++) {
num3 += a[i];
array2[i] = (uint)num3;
num3 >>= 32;
}
if (num3 != 0) {
Array.Resize(ref array2, num + 1);
array2[i] = (uint)num3;
}
return array2;
}
private static uint[] CoreSub(uint[] a, uint[] b)
{
int num = a.Length;
int num2 = b.Length;
uint[] array = new uint[num];
ulong num3 = 0;
int i;
for (i = 0; i < num2; i++) {
num3 = (ulong)((long)a[i] - (long)b[i] - (long)num3);
array[i] = (uint)num3;
num3 = ((num3 >> 32) & 1);
}
for (; i < num; i++) {
num3 = a[i] - num3;
array[i] = (uint)num3;
num3 = ((num3 >> 32) & 1);
}
i = num - 1;
while (i >= 0 && array[i] == 0) {
i--;
}
if (i < num - 1)
Array.Resize(ref array, i + 1);
return array;
}
private static uint[] CoreAdd(uint[] a, uint b)
{
int num = a.Length;
uint[] array = new uint[num];
ulong num2 = b;
int i;
for (i = 0; i < num; i++) {
num2 += a[i];
array[i] = (uint)num2;
num2 >>= 32;
}
if (num2 != 0) {
Array.Resize(ref array, num + 1);
array[i] = (uint)num2;
}
return array;
}
private static uint[] CoreSub(uint[] a, uint b)
{
int num = a.Length;
uint[] array = new uint[num];
ulong num2 = b;
int i;
for (i = 0; i < num; i++) {
num2 = a[i] - num2;
array[i] = (uint)num2;
num2 = ((num2 >> 32) & 1);
}
i = num - 1;
while (i >= 0 && array[i] == 0) {
i--;
}
if (i < num - 1)
Array.Resize(ref array, i + 1);
return array;
}
private static int CoreCompare(uint[] a, uint[] b)
{
int num = (a != null) ? a.Length : 0;
int num2 = (b != null) ? b.Length : 0;
if (num > num2)
return 1;
if (num2 > num)
return -1;
for (int num3 = num - 1; num3 >= 0; num3--) {
uint num4 = a[num3];
uint num5 = b[num3];
if (num4 > num5)
return 1;
if (num4 < num5)
return -1;
}
return 0;
}
private static int GetNormalizeShift(uint value)
{
int num = 0;
if (((int)value & -65536) == 0) {
value <<= 16;
num += 16;
}
if (((int)value & -16777216) == 0) {
value <<= 8;
num += 8;
}
if (((int)value & -268435456) == 0) {
value <<= 4;
num += 4;
}
if (((int)value & -1073741824) == 0) {
value <<= 2;
num += 2;
}
if (((int)value & -2147483648) == 0) {
value <<= 1;
num++;
}
return num;
}
private static void Normalize(uint[] u, int l, uint[] un, int shift)
{
uint num = 0;
int i;
if (shift > 0) {
int num2 = 32 - shift;
for (i = 0; i < l; i++) {
uint num3 = u[i];
un[i] = ((num3 << shift) | num);
num = num3 >> num2;
}
} else {
for (i = 0; i < l; i++) {
un[i] = u[i];
}
}
while (i < un.Length) {
un[i++] = 0;
}
if (num != 0)
un[l] = num;
}
private static void Unnormalize(uint[] un, out uint[] r, int shift)
{
int num = un.Length;
r = new uint[num];
if (shift > 0) {
int num2 = 32 - shift;
uint num3 = 0;
for (int num4 = num - 1; num4 >= 0; num4--) {
uint num5 = un[num4];
r[num4] = ((num5 >> shift) | num3);
num3 = num5 << num2;
}
} else {
for (int i = 0; i < num; i++) {
r[i] = un[i];
}
}
}
private static void DivModUnsigned(uint[] u, uint[] v, out uint[] q, out uint[] r)
{
int num = u.Length;
int num2 = v.Length;
if (num2 <= 1) {
ulong num3 = 0;
uint num4 = v[0];
q = new uint[num];
r = new uint[1];
for (int num5 = num - 1; num5 >= 0; num5--) {
num3 *= 4294967296;
num3 += u[num5];
ulong num6 = num3 / num4;
num3 -= num6 * num4;
q[num5] = (uint)num6;
}
r[0] = (uint)num3;
} else if (num >= num2) {
int normalizeShift = GetNormalizeShift(v[num2 - 1]);
uint[] array = new uint[num + 1];
uint[] array2 = new uint[num2];
Normalize(u, num, array, normalizeShift);
Normalize(v, num2, array2, normalizeShift);
q = new uint[num - num2 + 1];
r = null;
for (int num7 = num - num2; num7 >= 0; num7--) {
ulong num8 = (ulong)(4294967296 * array[num7 + num2] + array[num7 + num2 - 1]);
ulong num9 = num8 / array2[num2 - 1];
num8 -= num9 * array2[num2 - 1];
while (num9 >= 4294967296 || num9 * array2[num2 - 2] > num8 * 4294967296 + array[num7 + num2 - 2]) {
num9--;
num8 += array2[num2 - 1];
if (num8 >= 4294967296)
break;
}
long num10 = 0;
long num11 = 0;
for (int i = 0; i < num2; i++) {
ulong num12 = array2[i] * num9;
num11 = (long)array[i + num7] - (long)(uint)num12 - num10;
array[i + num7] = (uint)num11;
num12 >>= 32;
num11 >>= 32;
num10 = (long)num12 - num11;
}
num11 = array[num7 + num2] - num10;
array[num7 + num2] = (uint)num11;
q[num7] = (uint)num9;
if (num11 < 0) {
q[num7]--;
ulong num13 = 0;
for (int i = 0; i < num2; i++) {
num13 = (ulong)((long)array2[i] + (long)array[num7 + i] + (long)num13);
array[num7 + i] = (uint)num13;
num13 >>= 32;
}
num13 += array[num7 + num2];
array[num7 + num2] = (uint)num13;
}
}
Unnormalize(array, out r, normalizeShift);
} else {
q = new uint[1];
r = u;
}
}
}
}