2039 lines
64 KiB
C#
2039 lines
64 KiB
C#
using System;
|
|
using System.IO;
|
|
using System.Reflection;
|
|
using System.Runtime.InteropServices;
|
|
using System.Runtime.Serialization;
|
|
using System.Text;
|
|
|
|
namespace ln.biginteger
|
|
{
|
|
public class BigInteger : IDisposable, IComparable<BigInteger>
|
|
{
|
|
public static readonly BigInteger One = new BigInteger(); //1);
|
|
public static readonly BigInteger Zero = new BigInteger();
|
|
public static readonly BigInteger MinusOne = new BigInteger();// -1);
|
|
|
|
|
|
private IntPtr _mpz;
|
|
|
|
|
|
public BigInteger()
|
|
{
|
|
|
|
_mpz = BigIntegerAllocator.Pop();
|
|
mpz_init(_mpz);
|
|
}
|
|
public BigInteger(Int64 i64) :this() => mpz_set_si(_mpz, i64);
|
|
public BigInteger(UInt64 ui64) :this() => mpz_set_ui(_mpz, ui64);
|
|
public BigInteger(Int32 i32) :this() => mpz_set_si(_mpz, i32);
|
|
public BigInteger(UInt32 ui32) :this() => mpz_set_ui(_mpz, ui32);
|
|
private BigInteger(BigInteger src) :this() => mpz_set(_mpz, src._mpz);
|
|
|
|
|
|
private BigInteger(string source, int b) :this()
|
|
{
|
|
if (mpz_set_str( _mpz, source, b) != 0)
|
|
throw new ArgumentOutOfRangeException(nameof(source));
|
|
}
|
|
|
|
public static BigInteger Parse(string src) => new BigInteger(src, 0);
|
|
public static BigInteger Parse(string src, int b) => new BigInteger(src, b);
|
|
|
|
public static BigInteger FromByteArray(byte[] bytes)
|
|
{
|
|
BigInteger bi = new BigInteger();
|
|
mpz_import(bi._mpz, bytes.Length, -1, 1, -1, 0, bytes);
|
|
return bi;
|
|
}
|
|
public byte[] ToByteArray()
|
|
{
|
|
int countp = 0;
|
|
IntPtr bptr = mpz_export(null, ref countp, -1, 1, -1, 0, _mpz);
|
|
byte[] bytes = new byte[countp];
|
|
Marshal.Copy(bptr, bytes, 0, countp);
|
|
return bytes;
|
|
}
|
|
public void TryWriteBytes(Span<byte> s,out int bytesWritten)
|
|
{
|
|
byte[] sb = ToByteArray();
|
|
for (bytesWritten = 0; bytesWritten < sb.Length; bytesWritten++)
|
|
s[bytesWritten] = sb[bytesWritten];
|
|
}
|
|
|
|
public static BigInteger operator+(BigInteger op1, BigInteger op2)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_add(result._mpz, op1._mpz, op2._mpz);
|
|
return result;
|
|
}
|
|
public static BigInteger operator+(BigInteger op1, ulong ul)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_add_ui(result._mpz, op1._mpz, ul);
|
|
return result;
|
|
}
|
|
public static BigInteger operator-(BigInteger op1, BigInteger op2)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_sub(result._mpz, op1._mpz, op2._mpz);
|
|
return result;
|
|
}
|
|
public static BigInteger operator-(BigInteger op1, ulong ul)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_sub_ui(result._mpz, op1._mpz, ul);
|
|
return result;
|
|
}
|
|
|
|
public static BigInteger operator-(BigInteger op1)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_neg(result._mpz, op1._mpz);
|
|
return result;
|
|
}
|
|
|
|
public static BigInteger operator*(BigInteger op1, BigInteger op2)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_mul(result._mpz, op1._mpz, op2._mpz);
|
|
return result;
|
|
}
|
|
public static BigInteger operator*(BigInteger op1, long si)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_mul_si(result._mpz, op1._mpz, si);
|
|
return result;
|
|
}
|
|
public static BigInteger operator*(BigInteger op1, ulong ui)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_mul_ui(result._mpz, op1._mpz, ui);
|
|
return result;
|
|
}
|
|
|
|
public static BigInteger operator/(BigInteger n, BigInteger d)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_tdiv_q(result._mpz, n._mpz, d._mpz);
|
|
return result;
|
|
}
|
|
public static BigInteger operator%(BigInteger n, BigInteger d)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_tdiv_r(result._mpz, n._mpz, d._mpz);
|
|
return result;
|
|
}
|
|
|
|
public static bool operator==(BigInteger a, BigInteger b) => mpz_cmp(a._mpz, b._mpz) == 0;
|
|
public static bool operator!=(BigInteger a, BigInteger b) => mpz_cmp(a._mpz, b._mpz) != 0;
|
|
public static bool operator<(BigInteger a, BigInteger b) => mpz_cmp(a._mpz, b._mpz) < 0;
|
|
public static bool operator>(BigInteger a, BigInteger b) => mpz_cmp(a._mpz, b._mpz) > 0;
|
|
public static bool operator<(BigInteger a, long b) => mpz_cmp_si(a._mpz, b) < 0;
|
|
public static bool operator>(BigInteger a, long b) => mpz_cmp_si(a._mpz, b) > 0;
|
|
public static bool operator<(BigInteger a, int b) => mpz_cmp_si(a._mpz, b) < 0;
|
|
public static bool operator>(BigInteger a, int b) => mpz_cmp_si(a._mpz, b) > 0;
|
|
|
|
public static BigInteger operator<<(BigInteger n, int b)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_mul_2exp(result._mpz, n._mpz, (ulong)b );
|
|
return result;
|
|
}
|
|
public static BigInteger operator>>(BigInteger n, int b)
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_tdiv_q_2exp(result._mpz, n._mpz, (ulong)b );
|
|
return result;
|
|
}
|
|
|
|
public static implicit operator BigInteger(int i) => new BigInteger(i);
|
|
public static implicit operator BigInteger(uint i) => new BigInteger(i);
|
|
public static implicit operator BigInteger(long i) => new BigInteger(i);
|
|
public static implicit operator BigInteger(ulong i) => new BigInteger(i);
|
|
|
|
|
|
|
|
|
|
public BigInteger Abs()
|
|
{
|
|
BigInteger result = new BigInteger();
|
|
mpz_neg(result._mpz, _mpz);
|
|
return result;
|
|
}
|
|
public BigInteger DivMod(BigInteger d, out BigInteger r)
|
|
{
|
|
BigInteger q = new BigInteger();
|
|
r = new BigInteger();
|
|
mpz_tdiv_qr(q._mpz, d._mpz, _mpz, d._mpz);
|
|
return q;
|
|
}
|
|
public static BigInteger ModPow(BigInteger n, BigInteger e, BigInteger m) => n.ModPow(e,m);
|
|
public BigInteger ModPow(BigInteger e, BigInteger m)
|
|
{
|
|
BigInteger r = new BigInteger();
|
|
mpz_powm(r._mpz, _mpz, e._mpz, m._mpz);
|
|
return r;
|
|
}
|
|
public static BigInteger ModPow(BigInteger n, ulong e, BigInteger m) => n.ModPow(e,m);
|
|
public BigInteger ModPow(ulong e, BigInteger m)
|
|
{
|
|
BigInteger r = new BigInteger();
|
|
mpz_powm_ui(r._mpz, _mpz, e, m._mpz);
|
|
return r;
|
|
}
|
|
public static BigInteger Pow(BigInteger n, ulong e) => n.Pow(e);
|
|
public BigInteger Pow(ulong e)
|
|
{
|
|
BigInteger r = new BigInteger();
|
|
mpz_pow_ui(r._mpz, _mpz, e);
|
|
return r;
|
|
}
|
|
|
|
public int CompareTo(BigInteger other) => mpz_cmp(_mpz, other._mpz);
|
|
public int CompareTo(long other) => mpz_cmp_si(_mpz, other);
|
|
public int CompareTo(int other) => mpz_cmp_si(_mpz, other);
|
|
|
|
|
|
public override string ToString() => ToString(16);
|
|
|
|
public string ToString(int b)
|
|
{
|
|
StringBuilder sb = new StringBuilder(4096);
|
|
mpz_get_str(sb, b, _mpz);
|
|
return sb.ToString();
|
|
}
|
|
|
|
public string ToString(int b, int length)
|
|
{
|
|
StringBuilder sb = new StringBuilder(4096);
|
|
mpz_get_str(sb, b, _mpz);
|
|
|
|
StringBuilder sb2 = new StringBuilder();
|
|
for (int n=0;n<length-sb.Length;n++)
|
|
sb2.Append('0');
|
|
sb2.Append(sb.ToString());
|
|
return sb2.ToString();
|
|
}
|
|
|
|
|
|
public void Dispose()
|
|
{
|
|
if (_mpz != IntPtr.Zero)
|
|
{
|
|
mpz_clear(_mpz);
|
|
//Marshal.FreeHGlobal(_mpz);
|
|
BigIntegerAllocator.Push(_mpz);
|
|
_mpz = IntPtr.Zero;
|
|
}
|
|
}
|
|
|
|
public override bool Equals(object obj) => (obj is BigInteger other) && (mpz_cmp(_mpz, other._mpz) == 0);
|
|
public override int GetHashCode() => base.GetHashCode();
|
|
|
|
public bool IsZero => (this == 0);
|
|
public int Sign {
|
|
get {
|
|
int c = mpz_cmp_si(_mpz, 0);
|
|
return (c < 0) ? -1 : (c > 0) ? 1 : 0;
|
|
}
|
|
}
|
|
|
|
public int GetByteLength() => mpz_sizeinbase(_mpz, 2) >> 3;
|
|
public int GetBitLength() => mpz_sizeinbase(_mpz, 2);
|
|
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_init")]
|
|
static extern void mpz_init(IntPtr mpz);
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_clear")]
|
|
static extern void mpz_clear(IntPtr mpz);
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_set")]
|
|
static extern void mpz_set(IntPtr mpz_dst, IntPtr mpz_src);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_set_ui")]
|
|
static extern void mpz_set_ui(IntPtr mpz_dst, UInt64 src);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_set_si")]
|
|
static extern void mpz_set_si(IntPtr mpz_dst, Int64 src);
|
|
|
|
[DllImport("gmp", CharSet = CharSet.Auto, EntryPoint = "__gmpz_set_str")]
|
|
static extern int mpz_set_str(IntPtr mpz_dst, string src, int b);
|
|
[DllImport("gmp", CharSet = CharSet.Auto, EntryPoint = "__gmpz_get_str")]
|
|
static extern IntPtr mpz_get_str (StringBuilder stringBuilder, int b, IntPtr mpz);
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_add")]
|
|
static extern void mpz_add(IntPtr dst, IntPtr op1, IntPtr op2);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_add_ui")]
|
|
static extern void mpz_add_ui(IntPtr dst, IntPtr op1, ulong op2);
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_sub")]
|
|
static extern void mpz_sub(IntPtr dst, IntPtr op1, IntPtr op2);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_sub_ui")]
|
|
static extern void mpz_sub_ui(IntPtr dst, IntPtr op1, ulong op2);
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_neg")]
|
|
static extern void mpz_neg(IntPtr dst, IntPtr op1);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_abs")]
|
|
static extern void mpz_abs(IntPtr dst, IntPtr op1);
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_mul")]
|
|
static extern void mpz_mul(IntPtr dst, IntPtr op1, IntPtr op2);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_mul_2exp")]
|
|
static extern void mpz_mul_2exp(IntPtr dst, IntPtr op1, ulong op2);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_mul_si")]
|
|
static extern void mpz_mul_si(IntPtr dst, IntPtr op1, long sl);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_mul_ui")]
|
|
static extern void mpz_mul_ui(IntPtr dst, IntPtr op1, ulong ul);
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_mod")]
|
|
static extern void mpz_mod(IntPtr dst, IntPtr op1, IntPtr op2 );
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_tdiv_q")]
|
|
static extern void mpz_tdiv_q(IntPtr q, IntPtr n, IntPtr d );
|
|
[DllImport("gmp", EntryPoint = "__gmpz_tdiv_r")]
|
|
static extern void mpz_tdiv_r(IntPtr r, IntPtr n, IntPtr d );
|
|
[DllImport("gmp", EntryPoint = "__gmpz_tdiv_qr")]
|
|
static extern void mpz_tdiv_qr(IntPtr q, IntPtr r, IntPtr n, IntPtr d );
|
|
[DllImport("gmp", EntryPoint = "__gmpz_tdiv_q_2exp")]
|
|
static extern void mpz_tdiv_q_2exp(IntPtr q, IntPtr n, ulong b );
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_powm")]
|
|
static extern void mpz_powm(IntPtr dst, IntPtr b, IntPtr exp, IntPtr mod );
|
|
[DllImport("gmp", EntryPoint = "__gmpz_powm_ui")]
|
|
static extern void mpz_powm_ui(IntPtr dst, IntPtr b, ulong exp, IntPtr mod );
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_pow_ui")]
|
|
static extern void mpz_pow_ui(IntPtr dst, IntPtr b, ulong ui );
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_cmp")]
|
|
static extern Int32 mpz_cmp(IntPtr a, IntPtr b );
|
|
[DllImport("gmp", EntryPoint = "__gmpz_cmp_ui")]
|
|
static extern Int32 mpz_cmp_ui(IntPtr a, ulong b );
|
|
[DllImport("gmp", EntryPoint = "__gmpz_cmp_si")]
|
|
static extern Int32 mpz_cmp_si(IntPtr a, long b );
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_import")]
|
|
static extern void mpz_import(IntPtr dst, int count, int order, int size, int endian, int nails, byte[] buffer);
|
|
[DllImport("gmp", EntryPoint = "__gmpz_export")]
|
|
static extern IntPtr mpz_export(byte[] buffer, ref int countp, int order, int size, int endian, int nails, IntPtr src);
|
|
|
|
[DllImport("gmp", EntryPoint = "__gmpz_sizeinbase")]
|
|
static extern Int32 mpz_sizeinbase(IntPtr a, int b);
|
|
|
|
static BigInteger()
|
|
{
|
|
NativeLibrary.SetDllImportResolver(typeof(BigInteger).Assembly, ResolveLibrary);
|
|
}
|
|
|
|
static IntPtr ResolveLibrary(string libraryName, Assembly assembly, DllImportSearchPath? searchPath)
|
|
{
|
|
IntPtr libHandle = IntPtr.Zero;
|
|
foreach (string pat in libraryPatterns)
|
|
{
|
|
if (NativeLibrary.TryLoad(String.Format(pat, libraryName), out libHandle))
|
|
return libHandle;
|
|
}
|
|
throw new FileNotFoundException(libraryName);
|
|
}
|
|
|
|
static string[] libraryPatterns = new string[]{
|
|
"x32/lib{0}.so",
|
|
"x32/lib{0}.dll",
|
|
"x32/{0}.dll",
|
|
"x32/lib{0}.dylib",
|
|
"x64/lib{0}.so",
|
|
"x64/lib{0}.dll",
|
|
"x64/{0}.dll",
|
|
"x64/lib{0}.dylib",
|
|
};
|
|
|
|
}
|
|
|
|
|
|
|
|
// public class BigInteger : IComparable<BigInteger>
|
|
// {
|
|
// public static readonly BigInteger Zero = 0;
|
|
// public static readonly BigInteger One = 1;
|
|
// public static readonly BigInteger MinusOne = -1;
|
|
|
|
// private UInt32[] bits;
|
|
// private Int32 _length;
|
|
// private Int32 _sign;
|
|
|
|
|
|
// public Int32 Sign => _sign;
|
|
// public bool IsZero => (bits == null);
|
|
|
|
|
|
// private BigInteger(int sign, UInt32[] bits)
|
|
// {
|
|
// if (sign < 0)
|
|
// this._sign = -1;
|
|
// else if (sign > 0)
|
|
// this._sign = 1;
|
|
|
|
// this.bits = bits;
|
|
// }
|
|
|
|
// private void Reduce() { bits = Reduce(bits); _length = bits.Length; }
|
|
// public static UInt32[] Reduce(UInt32[] bits)
|
|
// {
|
|
// Int32 rl = managed_get_length(bits);
|
|
// if (bits.Length > rl)
|
|
// {
|
|
// UInt32[] newbits = new uint[rl];
|
|
// Array.Copy(bits, newbits, rl);
|
|
// bits = newbits;
|
|
// } else {
|
|
// bits = (UInt32[])bits.Clone();
|
|
// }
|
|
// return bits;
|
|
// }
|
|
|
|
// public static UInt32[] Extend(UInt32[] bits, int length)
|
|
// {
|
|
// UInt32[] extendedbits = new UInt32[length];
|
|
// Array.Copy(bits, extendedbits, bits.Length);
|
|
// if ((bits[bits.Length-1] & 0x80000000)==0x80000000)
|
|
// for (int n=bits.Length; n<extendedbits.Length; n++)
|
|
// extendedbits[n] = 0xFFFFFFFF;
|
|
// return extendedbits;
|
|
// }
|
|
|
|
// public Int32 GetByteCount() => big_get_length(bits) << 2;
|
|
// public Int32 GetBitLength() => big_get_bitlength(bits) << 5;
|
|
// public Int32 GetLength() => big_get_length(bits);
|
|
|
|
// public int CompareTo(BigInteger other)
|
|
// {
|
|
// if (_sign == other._sign)
|
|
// {
|
|
|
|
// } else {
|
|
// return _sign - other._sign;
|
|
// }
|
|
// }
|
|
|
|
// private bool TestZero(UInt32[] bits)
|
|
// {
|
|
// if (bits == null)
|
|
// return true;
|
|
|
|
// foreach (uint ui in bits)
|
|
// if (ui > 0)
|
|
// return false;
|
|
// return true;
|
|
// }
|
|
|
|
|
|
// public BigInteger Add(BigInteger bi2)
|
|
// {
|
|
// // if ((bits.Length == 1) && (bi2.bits.Length == 1))
|
|
// // return new BigInteger(bits[0]+bi2.bits[0]);
|
|
|
|
// int tlength = max(_length, bi2._length) + 1;
|
|
// UInt32[] r = new uint[tlength];
|
|
// Array.Copy(bits,r,bits.Length);
|
|
// big_add(r, bi2.bits);
|
|
// return new BigInteger(r);
|
|
// }
|
|
// public BigInteger MAdd(BigInteger bi2)
|
|
// {
|
|
// int tlength = max(_length, bi2._length) + 1;
|
|
// UInt32[] r = new uint[tlength];
|
|
// Array.Copy(bits,r,bits.Length);
|
|
// managed_add(r, bi2.bits);
|
|
// return new BigInteger(r);
|
|
// }
|
|
|
|
|
|
// public BigInteger Sub(BigInteger bi2)
|
|
// {
|
|
// int tlength = max(big_get_bitlength(bits), big_get_bitlength(bi2.bits))+1;
|
|
// UInt32[] r = new uint[(tlength + 31)>>5];
|
|
// Array.Copy(bits,r,bits.Length);
|
|
// big_sub(r, r.Length, bi2.bits, bi2.bits.Length);
|
|
// return new BigInteger(r);
|
|
// }
|
|
|
|
// // public BigInteger Sub(BigInteger bi2)
|
|
// // {
|
|
// // UInt32[] r = new uint[max(bits.Length, bi2.bits.Length)+1];
|
|
// // Array.Copy(bits,r,bits.Length);
|
|
|
|
// // UInt32[] r2 = (uint[])bi2.bits.Clone();
|
|
// // big_twos(r2, r2.Length);
|
|
|
|
// // big_add(r, r.Length, r2, r2.Length);
|
|
// // return new BigInteger(r);
|
|
// // }
|
|
|
|
// public BigInteger Mul(BigInteger bi2)
|
|
// {
|
|
// int l = (big_get_bitlength(bits) + big_get_bitlength(bi2.bits) + 31) >> 5;
|
|
// UInt32[] r = new UInt32[l];
|
|
// Array.Copy(bits, r, bits.Length);
|
|
// big_smul(r, bi2.bits);
|
|
// return new BigInteger(r);
|
|
// }
|
|
// public BigInteger MMul(BigInteger bi2)
|
|
// {
|
|
// int l = (big_get_bitlength(bits) + big_get_bitlength(bi2.bits) + 31) >> 5;
|
|
// UInt32[] r = new UInt32[l];
|
|
// Array.Copy(bits, r, bits.Length);
|
|
// managed_smul(r, bi2.bits);
|
|
// return new BigInteger(r);
|
|
// }
|
|
|
|
// public BigInteger DivMod(BigInteger divisor,out BigInteger remainder)
|
|
// {
|
|
// UInt32[] quotient = (uint[])bits.Clone();
|
|
// UInt32[] d = (uint[])divisor.bits.Clone();
|
|
|
|
// big_divmod( quotient, quotient.Length, d, d.Length);
|
|
|
|
// remainder = new BigInteger(d);
|
|
// return new BigInteger(quotient);
|
|
// }
|
|
// public BigInteger Div(BigInteger divisor)
|
|
// {
|
|
// UInt32[] quotient = (uint[])bits.Clone();
|
|
// UInt32[] d = (uint[])divisor.bits.Clone();
|
|
|
|
// big_divmod( quotient, quotient.Length, d, d.Length);
|
|
|
|
// return new BigInteger(quotient);
|
|
// }
|
|
// public BigInteger Mod(BigInteger divisor)
|
|
// {
|
|
// UInt32[] quotient = (uint[])bits.Clone();
|
|
// UInt32[] d = (uint[])divisor.bits.Clone();
|
|
|
|
// big_divmod( quotient, quotient.Length, d, d.Length);
|
|
|
|
// return new BigInteger(d);
|
|
// }
|
|
|
|
|
|
|
|
// public BigInteger Ones()
|
|
// {
|
|
// UInt32[] r = (UInt32[])bits.Clone();
|
|
// for (int n=0;n<r.Length;n++)
|
|
// r[n] = ~r[n];
|
|
// return new BigInteger(r);
|
|
// }
|
|
|
|
// public BigInteger Twos()
|
|
// {
|
|
// UInt32[] r = (UInt32[])bits.Clone();
|
|
// big_twos(r, r.Length);
|
|
// return new BigInteger(r);
|
|
// }
|
|
|
|
// public BigInteger ShiftLeft(int n)
|
|
// {
|
|
// UInt32[] r = (UInt32[])bits.Clone();
|
|
// big_shl(r, r.Length, n);
|
|
// return new BigInteger(r);
|
|
// }
|
|
// public BigInteger ShiftRight(int n)
|
|
// {
|
|
// UInt32[] r = (UInt32[])bits.Clone();
|
|
// big_shr(r, r.Length, n);
|
|
// return new BigInteger(r);
|
|
// }
|
|
// public BigInteger Pow(int n)
|
|
// {
|
|
// if (n == 0)
|
|
// return One;
|
|
// else if (n == 1)
|
|
// return this;
|
|
// else if (n == 2)
|
|
// return this * this;
|
|
// else if (n > 2)
|
|
// {
|
|
// BigInteger result = One;
|
|
// for (int i=31; i>=0; i--)
|
|
// {
|
|
// result *= result;
|
|
// if ((n & (1<<i))!=0)
|
|
// result *= this;
|
|
// }
|
|
// return result;
|
|
// }
|
|
// throw new ArgumentException("Integer.Pow(n): not implemented for negative exponent");
|
|
// }
|
|
|
|
|
|
// public override bool Equals(object obj)
|
|
// {
|
|
// if (obj is BigInteger bi2)
|
|
// {
|
|
// if (bits.Length == bi2.bits.Length)
|
|
// {
|
|
// for (int n=0;n<bits.Length;n++)
|
|
// {
|
|
// if (bits[n] != bi2.bits[n])
|
|
// return false;
|
|
// }
|
|
// return true;
|
|
// }
|
|
|
|
// }
|
|
// return false;
|
|
// }
|
|
|
|
|
|
// public byte[] ToByteArray()
|
|
// {
|
|
// bool nonzero = false;
|
|
// MemoryStream ms = new MemoryStream();
|
|
|
|
// // if (Sign < 0)
|
|
// // ms.WriteByte(0);
|
|
|
|
// for (int n=bits.Length-1; n >= 0; n--)
|
|
// {
|
|
// for (int m=3; m>=0; m--)
|
|
// {
|
|
// byte tb = (byte)((bits[n] >> (m*8)) & 0xff);
|
|
// if (nonzero || (tb!=0))
|
|
// {
|
|
// nonzero = true;
|
|
// ms.WriteByte(tb);
|
|
// }
|
|
// }
|
|
// }
|
|
|
|
// return ms.ToArray();
|
|
// }
|
|
|
|
|
|
// public static implicit operator BigInteger(int i)
|
|
// {
|
|
// if (i > 0)
|
|
// return new BigInteger(1, new UInt32[]{ (uint)i} );
|
|
// if (i < 0)
|
|
// return new BigInteger(-1, new uint[]{ (uint)-i});
|
|
|
|
// return new BigInteger(0, null);
|
|
// }
|
|
// public static implicit operator BigInteger(uint i)
|
|
// {
|
|
// if (i > 0)
|
|
// return new BigInteger(1, new UInt32[]{ (uint)i} );
|
|
// return new BigInteger(0, null);
|
|
// }
|
|
|
|
// public static BigInteger operator+(BigInteger bi1,BigInteger bi2) => bi1.Add(bi2);
|
|
// public static BigInteger operator-(BigInteger bi1,BigInteger bi2) => bi1.Sub(bi2);
|
|
|
|
// public static BigInteger operator<<(BigInteger bi, int n) => bi.ShiftLeft(n);
|
|
// public static BigInteger operator>>(BigInteger bi, int n) => bi.ShiftRight(n);
|
|
|
|
// public static BigInteger operator*(BigInteger bi1,BigInteger bi2) => bi1.Mul(bi2);
|
|
// public static BigInteger operator/(BigInteger bi1,BigInteger bi2) => bi1.Div(bi2);
|
|
// public static BigInteger operator%(BigInteger bi1,BigInteger bi2) => bi1.Mod(bi2);
|
|
// //public static BigInteger operator^(BigInteger bi1,int exp) => bi1.Pow(exp);
|
|
|
|
|
|
|
|
// public static BigInteger Parse(string source) => Parse( source, 10 );
|
|
// public static BigInteger Parse(string source,int radix)
|
|
// {
|
|
// UInt32[] bits = new UInt32[ ((source.Length * 6) + 31) >> 5];
|
|
// big_parse(bits, bits.Length, source, 16);
|
|
// return new BigInteger(bits);
|
|
// }
|
|
|
|
// public static BigInteger FromHexString(string hex)
|
|
// {
|
|
// // hex = hex.ToUpper();
|
|
// // int length = (hex.Length+7) >> 3;
|
|
// // UInt32[] bits = new uint[length];
|
|
// // int n;
|
|
|
|
// // for (n=hex.Length-8; n>=0; n -= 8)
|
|
// // bits[length - 1 - (n >> 3)] = uint.Parse(hex.Substring(n,8), NumberStyles.HexNumber);
|
|
// // if (n > -8)
|
|
// // bits[length - 1] = uint.Parse(hex.Substring(0, 8 + n), NumberStyles.HexNumber);
|
|
|
|
// UInt32[] bits = new UInt32[ ((hex.Length * 6) + 31) >> 5];
|
|
// big_parse(bits, bits.Length, hex, 16);
|
|
// return new BigInteger(bits);
|
|
// }
|
|
|
|
// public string ToHexString()
|
|
// {
|
|
// byte[] bytes = ToByteArray();
|
|
// StringBuilder sb = new StringBuilder();
|
|
// foreach (byte by in bytes)
|
|
// sb.AppendFormat("{0:X2}", by);
|
|
// return sb.ToString();
|
|
// }
|
|
|
|
// public override string ToString() => ToHexString();
|
|
// public string ToString(int radix)
|
|
// {
|
|
// if (IsZero)
|
|
// return "0";
|
|
|
|
// UInt32[] r;
|
|
// UInt32[] v = (UInt32[])bits.Clone();
|
|
|
|
// StringBuilder sb = new StringBuilder();
|
|
|
|
// if (Sign < 0)
|
|
// big_twos(v, v.Length);
|
|
|
|
// while (big_cmp(v, v.Length, Zero.bits, Zero.bits.Length)!=0)
|
|
// {
|
|
// r = new UInt32[]{ (UInt32)radix };
|
|
// big_divmod(v, v.Length, r, r.Length);
|
|
// if (r[0] < 10)
|
|
// sb.Append((char)('0' + r[0]));
|
|
// else
|
|
// sb.Append((char)(55 + r[0]) );
|
|
// }
|
|
|
|
// if (Sign < 0)
|
|
// sb.Append('-');
|
|
|
|
// char[] chs = new char[sb.Length];
|
|
// sb.CopyTo(0,chs,0,sb.Length);
|
|
// Array.Reverse(chs);
|
|
// return new string(chs);
|
|
// }
|
|
|
|
|
|
// // public BigInteger(UInt32[] value)
|
|
// // {
|
|
// // this.bits = value;
|
|
// // }
|
|
|
|
|
|
|
|
|
|
// // public BigInteger(byte[] ivalue)
|
|
// // {
|
|
// // UInt32[] v = new UInt32[(ivalue.Length + 3) >> 2];
|
|
// // ivalue = ivalue.Segment(0, v.Length << 2);
|
|
|
|
// // for (int n = 0; n < v.Length; n++)
|
|
// // {
|
|
// // v[n] = BitConverter.ToUInt32(ivalue, n << 2);
|
|
// // }
|
|
// // this.bits = BigIntMath.reduceSigned(v);
|
|
// // }
|
|
// // public BigInteger(BigInteger src)
|
|
// // {
|
|
// // this.bits = src.bits;
|
|
// // }
|
|
|
|
// // public bool IsZero => BigIntMath.isZero(bits);
|
|
// // public int Sign => BigIntMath.isZero(bits) ? 0 : BigIntMath.sign(bits) ? -1 : 1;
|
|
|
|
// // public int GetByteCount() => bits.Length * 4;
|
|
// // public int GetBitLength() => BigIntMath.log2(bits);
|
|
|
|
// // public byte[] ToByteArray() => bits.GetBytes();
|
|
|
|
// // public void TryWriteBytes(Span<byte> s,out int bytesWritten)
|
|
// // {
|
|
// // byte[] sb = ToByteArray();
|
|
// // for (bytesWritten = 0; bytesWritten < sb.Length; bytesWritten++)
|
|
// // s[bytesWritten] = sb[bytesWritten];
|
|
// // }
|
|
|
|
// // public int Log2(){
|
|
// // return BigIntMath.log2(bits);
|
|
// // }
|
|
|
|
// // public static BigInteger ModPow(BigInteger i,int n,BigInteger modulus)
|
|
// // {
|
|
// // BigInteger r = BigInteger.One;
|
|
// // while (n-- > 0)
|
|
// // {
|
|
// // r *= i;
|
|
// // r %= modulus;
|
|
// // }
|
|
// // return r;
|
|
// // }
|
|
|
|
// // public BigInteger Pow(int n)
|
|
// // {
|
|
// // if (n == 0)
|
|
// // {
|
|
// // return One;
|
|
// // }
|
|
// // else if (n == 1)
|
|
// // {
|
|
// // return this;
|
|
// // }
|
|
// // else if (n > 1)
|
|
// // {
|
|
// // BigInteger result = this;
|
|
// // n--;
|
|
// // while ((n--) > 0)
|
|
// // {
|
|
// // result = (result * this);
|
|
// // }
|
|
// // return result;
|
|
// // }
|
|
// // throw new ArgumentException("Integer.Pow(n): not implemented for negative exponent");
|
|
// // }
|
|
|
|
// // public BigInteger Ones()
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.ones(bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // public BigInteger Twos()
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.twos(bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
|
|
// // public static BigInteger fromHexString(string hex) => Parse(hex, 16);
|
|
|
|
// // public override string ToString()
|
|
// // {
|
|
// // return String.Format("[{0}: Sign: {2,5} / {1}]", this.GetType().Name, ToString(16), Sign );
|
|
// // }
|
|
|
|
// // public string ToString(string format)
|
|
// // {
|
|
// // if (format.Equals("X"))
|
|
// // return ToString(16);
|
|
// // return ToString(10);
|
|
// // }
|
|
|
|
// // public string ToString(int radix) => ToString(radix, -1);
|
|
// // public string ToString(int radix, int length)
|
|
// // {
|
|
// // if ((radix < 2) || (radix > 36))
|
|
// // throw new ArgumentOutOfRangeException(nameof(radix));
|
|
|
|
// // uint[] v = bits.Segment(0);
|
|
// // uint[] r = new uint[]{ (uint)radix };
|
|
|
|
// // StringBuilder sb = new StringBuilder();
|
|
|
|
// // while ((!BigIntMath.isZero(v)) && ((length-- )!=0))
|
|
// // {
|
|
// // uint[] x = BigIntMath.sdivmod(ref v, r);
|
|
// // if (v[0] < 10)
|
|
// // sb.Append((char)('0' + v[0]));
|
|
// // else
|
|
// // sb.Append((char)(55 + v[0]));
|
|
// // v = x;
|
|
// // }
|
|
|
|
// // char[] result = new char[sb.Length];
|
|
// // sb.CopyTo(0, result, 0, sb.Length);
|
|
// // Array.Reverse(result);
|
|
// // return new string(result);
|
|
// // }
|
|
|
|
// // public static BigInteger Parse(string input) => Parse(input, 10);
|
|
|
|
// // public static BigInteger Parse(string input, NumberStyles numberStyles)
|
|
// // {
|
|
// // if ((numberStyles & (NumberStyles.HexNumber | NumberStyles.AllowHexSpecifier)) != 0)
|
|
// // return Parse(input, 16);
|
|
// // return Parse(input, 10);
|
|
// // }
|
|
|
|
// // public static BigInteger Parse(string input, int radix)
|
|
// // {
|
|
// // BigInteger v = 0;
|
|
// // bool sign = false;
|
|
|
|
// // if (input[0] == '-')
|
|
// // {
|
|
// // sign = true;
|
|
// // input = input.Substring(1);
|
|
// // }
|
|
|
|
// // foreach (char d in input)
|
|
// // {
|
|
// // int n = d - '0';
|
|
// // if (n > 9)
|
|
// // n = d - 55;
|
|
|
|
// // v *= radix;
|
|
// // v += n;
|
|
// // }
|
|
|
|
// // if (sign)
|
|
// // v = v.Twos();
|
|
|
|
// // return v;
|
|
// // }
|
|
|
|
|
|
|
|
// // private BigInteger __op_add(BigInteger b)
|
|
// // {
|
|
// // int width = (bits.Length > b.bits.Length ? bits.Length : b.bits.Length) + 1;
|
|
// // UInt32[] v = BigIntMath.extendSigned(bits, width);
|
|
// // UInt32[] vb = BigIntMath.extendSigned(b.bits, width);
|
|
// // return new BigInteger(BigIntMath.reduceSigned(BigIntMath.add(v,vb)));
|
|
// // }
|
|
// // private BigInteger __op_sub(BigInteger b)
|
|
// // {
|
|
// // int width = (bits.Length > b.bits.Length ? bits.Length : b.bits.Length) + 1;
|
|
// // UInt32[] v = BigIntMath.extendSigned(bits, width);
|
|
// // UInt32[] vb = BigIntMath.extendSigned(b.bits, width);
|
|
// // return new BigInteger(BigIntMath.reduceSigned(BigIntMath.sub(v,vb)));
|
|
// // }
|
|
|
|
// // private int __op_cmp(BigInteger b)
|
|
// // {
|
|
// // return BigIntMath.cmp(bits, b.bits);
|
|
// // }
|
|
|
|
// // private BigInteger __op_div(BigInteger b)
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.sdiv(bits, b.bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // private BigInteger __op_mod(BigInteger b)
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.smod(bits, b.bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // private BigInteger __op_mul(BigInteger b)
|
|
// // {
|
|
// // UInt32[] value = BigIntMath.smul(bits, b.bits);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_new(uint[] value)
|
|
// // {
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_shl(int b)
|
|
// // {
|
|
// // UInt32[] value = BigIntMath.extendSigned(bits, bits.Length + ((b + 31) >> 5));
|
|
// // BigIntMath.shl(value,b);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_shr(int b)
|
|
// // {
|
|
// // UInt32[] value = bits.Segment(0);
|
|
// // BigIntMath.shr(value, b);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // public static implicit operator BigInteger(int i)
|
|
// // {
|
|
// // return new BigInteger(new UInt32[]{(UInt32)i});
|
|
// // }
|
|
|
|
|
|
|
|
// // public static BigInteger operator +(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_add(b);
|
|
// // }
|
|
// // public static BigInteger operator -(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_sub(b);
|
|
// // }
|
|
// // public static BigInteger operator *(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_mul(b);
|
|
// // }
|
|
|
|
// // public static BigInteger operator /(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_div(b);
|
|
// // }
|
|
// // public static BigInteger operator %(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_mod(b);
|
|
// // }
|
|
|
|
// // public static bool operator <(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) < 0;
|
|
// // }
|
|
// // public static bool operator >(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) > 0;
|
|
// // }
|
|
// // public static bool operator ==(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // if ((object)a == (object)b)
|
|
// // {
|
|
// // return true;
|
|
// // }
|
|
// // if (((object)a == null) || ((object)b == null))
|
|
// // {
|
|
// // return false;
|
|
// // }
|
|
// // return a.__op_cmp(b) == 0;
|
|
// // }
|
|
// // public static bool operator !=(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) != 0;
|
|
// // }
|
|
|
|
// // public static BigInteger operator <<(BigInteger a, int b)
|
|
// // {
|
|
// // return a.__op_shl(b);
|
|
// // }
|
|
// // public static BigInteger operator >>(BigInteger a, int b)
|
|
// // {
|
|
// // return a.__op_shr(b);
|
|
// // }
|
|
|
|
// // public override bool Equals(object obj) => (obj is BigInteger other) && (this == other);
|
|
// // public override int GetHashCode() => ToByteArray().CreateHashCode();
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// /*** Native Implementations ***/
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// // public BigInteger(UInt32[] value)
|
|
// // {
|
|
// // this.bits = value;
|
|
// // }
|
|
|
|
|
|
|
|
|
|
// // public BigInteger(byte[] ivalue)
|
|
// // {
|
|
// // UInt32[] v = new UInt32[(ivalue.Length + 3) >> 2];
|
|
// // ivalue = ivalue.Segment(0, v.Length << 2);
|
|
|
|
// // for (int n = 0; n < v.Length; n++)
|
|
// // {
|
|
// // v[n] = BitConverter.ToUInt32(ivalue, n << 2);
|
|
// // }
|
|
// // this.bits = BigIntMath.reduceSigned(v);
|
|
// // }
|
|
// // public BigInteger(BigInteger src)
|
|
// // {
|
|
// // this.bits = src.bits;
|
|
// // }
|
|
|
|
// // public bool IsZero => BigIntMath.isZero(bits);
|
|
// // public int Sign => BigIntMath.isZero(bits) ? 0 : BigIntMath.sign(bits) ? -1 : 1;
|
|
|
|
// // public int GetByteCount() => bits.Length * 4;
|
|
// // public int GetBitLength() => BigIntMath.log2(bits);
|
|
|
|
// // public byte[] ToByteArray() => bits.GetBytes();
|
|
|
|
// // public void TryWriteBytes(Span<byte> s,out int bytesWritten)
|
|
// // {
|
|
// // byte[] sb = ToByteArray();
|
|
// // for (bytesWritten = 0; bytesWritten < sb.Length; bytesWritten++)
|
|
// // s[bytesWritten] = sb[bytesWritten];
|
|
// // }
|
|
|
|
// // public int Log2(){
|
|
// // return BigIntMath.log2(bits);
|
|
// // }
|
|
|
|
// // public static BigInteger ModPow(BigInteger i,int n,BigInteger modulus)
|
|
// // {
|
|
// // BigInteger r = BigInteger.One;
|
|
// // while (n-- > 0)
|
|
// // {
|
|
// // r *= i;
|
|
// // r %= modulus;
|
|
// // }
|
|
// // return r;
|
|
// // }
|
|
|
|
// // public BigInteger Pow(int n)
|
|
// // {
|
|
// // if (n == 0)
|
|
// // {
|
|
// // return One;
|
|
// // }
|
|
// // else if (n == 1)
|
|
// // {
|
|
// // return this;
|
|
// // }
|
|
// // else if (n > 1)
|
|
// // {
|
|
// // BigInteger result = this;
|
|
// // n--;
|
|
// // while ((n--) > 0)
|
|
// // {
|
|
// // result = (result * this);
|
|
// // }
|
|
// // return result;
|
|
// // }
|
|
// // throw new ArgumentException("Integer.Pow(n): not implemented for negative exponent");
|
|
// // }
|
|
|
|
// // public BigInteger Ones()
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.ones(bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // public BigInteger Twos()
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.twos(bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
|
|
// // public static BigInteger fromHexString(string hex) => Parse(hex, 16);
|
|
|
|
// // public override string ToString()
|
|
// // {
|
|
// // return String.Format("[{0}: Sign: {2,5} / {1}]", this.GetType().Name, ToString(16), Sign );
|
|
// // }
|
|
|
|
// // public string ToString(string format)
|
|
// // {
|
|
// // if (format.Equals("X"))
|
|
// // return ToString(16);
|
|
// // return ToString(10);
|
|
// // }
|
|
|
|
// // public string ToString(int radix) => ToString(radix, -1);
|
|
// // public string ToString(int radix, int length)
|
|
// // {
|
|
// // if ((radix < 2) || (radix > 36))
|
|
// // throw new ArgumentOutOfRangeException(nameof(radix));
|
|
|
|
// // uint[] v = bits.Segment(0);
|
|
// // uint[] r = new uint[]{ (uint)radix };
|
|
|
|
// // StringBuilder sb = new StringBuilder();
|
|
|
|
// // while ((!BigIntMath.isZero(v)) && ((length-- )!=0))
|
|
// // {
|
|
// // uint[] x = BigIntMath.sdivmod(ref v, r);
|
|
// // if (v[0] < 10)
|
|
// // sb.Append((char)('0' + v[0]));
|
|
// // else
|
|
// // sb.Append((char)(55 + v[0]));
|
|
// // v = x;
|
|
// // }
|
|
|
|
// // char[] result = new char[sb.Length];
|
|
// // sb.CopyTo(0, result, 0, sb.Length);
|
|
// // Array.Reverse(result);
|
|
// // return new string(result);
|
|
// // }
|
|
|
|
// // public static BigInteger Parse(string input) => Parse(input, 10);
|
|
|
|
// // public static BigInteger Parse(string input, NumberStyles numberStyles)
|
|
// // {
|
|
// // if ((numberStyles & (NumberStyles.HexNumber | NumberStyles.AllowHexSpecifier)) != 0)
|
|
// // return Parse(input, 16);
|
|
// // return Parse(input, 10);
|
|
// // }
|
|
|
|
// // public static BigInteger Parse(string input, int radix)
|
|
// // {
|
|
// // BigInteger v = 0;
|
|
// // bool sign = false;
|
|
|
|
// // if (input[0] == '-')
|
|
// // {
|
|
// // sign = true;
|
|
// // input = input.Substring(1);
|
|
// // }
|
|
|
|
// // foreach (char d in input)
|
|
// // {
|
|
// // int n = d - '0';
|
|
// // if (n > 9)
|
|
// // n = d - 55;
|
|
|
|
// // v *= radix;
|
|
// // v += n;
|
|
// // }
|
|
|
|
// // if (sign)
|
|
// // v = v.Twos();
|
|
|
|
// // return v;
|
|
// // }
|
|
|
|
|
|
|
|
// // private BigInteger __op_add(BigInteger b)
|
|
// // {
|
|
// // int width = (bits.Length > b.bits.Length ? bits.Length : b.bits.Length) + 1;
|
|
// // UInt32[] v = BigIntMath.extendSigned(bits, width);
|
|
// // UInt32[] vb = BigIntMath.extendSigned(b.bits, width);
|
|
// // return new BigInteger(BigIntMath.reduceSigned(BigIntMath.add(v,vb)));
|
|
// // }
|
|
// // private BigInteger __op_sub(BigInteger b)
|
|
// // {
|
|
// // int width = (bits.Length > b.bits.Length ? bits.Length : b.bits.Length) + 1;
|
|
// // UInt32[] v = BigIntMath.extendSigned(bits, width);
|
|
// // UInt32[] vb = BigIntMath.extendSigned(b.bits, width);
|
|
// // return new BigInteger(BigIntMath.reduceSigned(BigIntMath.sub(v,vb)));
|
|
// // }
|
|
|
|
// // private int __op_cmp(BigInteger b)
|
|
// // {
|
|
// // return BigIntMath.cmp(bits, b.bits);
|
|
// // }
|
|
|
|
// // private BigInteger __op_div(BigInteger b)
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.sdiv(bits, b.bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // private BigInteger __op_mod(BigInteger b)
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.smod(bits, b.bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // private BigInteger __op_mul(BigInteger b)
|
|
// // {
|
|
// // UInt32[] value = BigIntMath.smul(bits, b.bits);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_new(uint[] value)
|
|
// // {
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_shl(int b)
|
|
// // {
|
|
// // UInt32[] value = BigIntMath.extendSigned(bits, bits.Length + ((b + 31) >> 5));
|
|
// // BigIntMath.shl(value,b);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_shr(int b)
|
|
// // {
|
|
// // UInt32[] value = bits.Segment(0);
|
|
// // BigIntMath.shr(value, b);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // public static implicit operator BigInteger(int i)
|
|
// // {
|
|
// // return new BigInteger(new UInt32[]{(UInt32)i});
|
|
// // }
|
|
|
|
|
|
|
|
// // public static BigInteger operator +(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_add(b);
|
|
// // }
|
|
// // public static BigInteger operator -(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_sub(b);
|
|
// // }
|
|
// // public static BigInteger operator *(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_mul(b);
|
|
// // }
|
|
|
|
// // public static BigInteger operator /(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_div(b);
|
|
// // }
|
|
// // public static BigInteger operator %(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_mod(b);
|
|
// // }
|
|
|
|
// // public static bool operator <(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) < 0;
|
|
// // }
|
|
// // public static bool operator >(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) > 0;
|
|
// // }
|
|
// // public static bool operator ==(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // if ((object)a == (object)b)
|
|
// // {
|
|
// // return true;
|
|
// // }
|
|
// // if (((object)a == null) || ((object)b == null))
|
|
// // {
|
|
// // return false;
|
|
// // }
|
|
// // return a.__op_cmp(b) == 0;
|
|
// // }
|
|
// // public static bool operator !=(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) != 0;
|
|
// // }
|
|
|
|
// // public static BigInteger operator <<(BigInteger a, int b)
|
|
// // {
|
|
// // return a.__op_shl(b);
|
|
// // }
|
|
// // public static BigInteger operator >>(BigInteger a, int b)
|
|
// // {
|
|
// // return a.__op_shr(b);
|
|
// // }
|
|
|
|
// // public override bool Equals(object obj) => (obj is BigInteger other) && (this == other);
|
|
// // public override int GetHashCode() => ToByteArray().CreateHashCode();
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// /*** Native Implementations ***/
|
|
|
|
|
|
|
|
// // public BigInteger(UInt32[] value)
|
|
// // {
|
|
// // this.bits = value;
|
|
// // }
|
|
|
|
|
|
|
|
|
|
// // public BigInteger(byte[] ivalue)
|
|
// // {
|
|
// // UInt32[] v = new UInt32[(ivalue.Length + 3) >> 2];
|
|
// // ivalue = ivalue.Segment(0, v.Length << 2);
|
|
|
|
// // for (int n = 0; n < v.Length; n++)
|
|
// // {
|
|
// // v[n] = BitConverter.ToUInt32(ivalue, n << 2);
|
|
// // }
|
|
// // this.bits = BigIntMath.reduceSigned(v);
|
|
// // }
|
|
// // public BigInteger(BigInteger src)
|
|
// // {
|
|
// // this.bits = src.bits;
|
|
// // }
|
|
|
|
// // public bool IsZero => BigIntMath.isZero(bits);
|
|
// // public int Sign => BigIntMath.isZero(bits) ? 0 : BigIntMath.sign(bits) ? -1 : 1;
|
|
|
|
// // public int GetByteCount() => bits.Length * 4;
|
|
// // public int GetBitLength() => BigIntMath.log2(bits);
|
|
|
|
// // public byte[] ToByteArray() => bits.GetBytes();
|
|
|
|
// // public void TryWriteBytes(Span<byte> s,out int bytesWritten)
|
|
// // {
|
|
// // byte[] sb = ToByteArray();
|
|
// // for (bytesWritten = 0; bytesWritten < sb.Length; bytesWritten++)
|
|
// // s[bytesWritten] = sb[bytesWritten];
|
|
// // }
|
|
|
|
// // public int Log2(){
|
|
// // return BigIntMath.log2(bits);
|
|
// // }
|
|
|
|
// // public static BigInteger ModPow(BigInteger i,int n,BigInteger modulus)
|
|
// // {
|
|
// // BigInteger r = BigInteger.One;
|
|
// // while (n-- > 0)
|
|
// // {
|
|
// // r *= i;
|
|
// // r %= modulus;
|
|
// // }
|
|
// // return r;
|
|
// // }
|
|
|
|
// // public BigInteger Pow(int n)
|
|
// // {
|
|
// // if (n == 0)
|
|
// // {
|
|
// // return One;
|
|
// // }
|
|
// // else if (n == 1)
|
|
// // {
|
|
// // return this;
|
|
// // }
|
|
// // else if (n > 1)
|
|
// // {
|
|
// // BigInteger result = this;
|
|
// // n--;
|
|
// // while ((n--) > 0)
|
|
// // {
|
|
// // result = (result * this);
|
|
// // }
|
|
// // return result;
|
|
// // }
|
|
// // throw new ArgumentException("Integer.Pow(n): not implemented for negative exponent");
|
|
// // }
|
|
|
|
// // public BigInteger Ones()
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.ones(bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // public BigInteger Twos()
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.twos(bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
|
|
// // public static BigInteger fromHexString(string hex) => Parse(hex, 16);
|
|
|
|
// // public override string ToString()
|
|
// // {
|
|
// // return String.Format("[{0}: Sign: {2,5} / {1}]", this.GetType().Name, ToString(16), Sign );
|
|
// // }
|
|
|
|
// // public string ToString(string format)
|
|
// // {
|
|
// // if (format.Equals("X"))
|
|
// // return ToString(16);
|
|
// // return ToString(10);
|
|
// // }
|
|
|
|
// // public string ToString(int radix) => ToString(radix, -1);
|
|
// // public string ToString(int radix, int length)
|
|
// // {
|
|
// // if ((radix < 2) || (radix > 36))
|
|
// // throw new ArgumentOutOfRangeException(nameof(radix));
|
|
|
|
// // uint[] v = bits.Segment(0);
|
|
// // uint[] r = new uint[]{ (uint)radix };
|
|
|
|
// // StringBuilder sb = new StringBuilder();
|
|
|
|
// // while ((!BigIntMath.isZero(v)) && ((length-- )!=0))
|
|
// // {
|
|
// // uint[] x = BigIntMath.sdivmod(ref v, r);
|
|
// // if (v[0] < 10)
|
|
// // sb.Append((char)('0' + v[0]));
|
|
// // else
|
|
// // sb.Append((char)(55 + v[0]));
|
|
// // v = x;
|
|
// // }
|
|
|
|
// // char[] result = new char[sb.Length];
|
|
// // sb.CopyTo(0, result, 0, sb.Length);
|
|
// // Array.Reverse(result);
|
|
// // return new string(result);
|
|
// // }
|
|
|
|
// // public static BigInteger Parse(string input) => Parse(input, 10);
|
|
|
|
// // public static BigInteger Parse(string input, NumberStyles numberStyles)
|
|
// // {
|
|
// // if ((numberStyles & (NumberStyles.HexNumber | NumberStyles.AllowHexSpecifier)) != 0)
|
|
// // return Parse(input, 16);
|
|
// // return Parse(input, 10);
|
|
// // }
|
|
|
|
// // public static BigInteger Parse(string input, int radix)
|
|
// // {
|
|
// // BigInteger v = 0;
|
|
// // bool sign = false;
|
|
|
|
// // if (input[0] == '-')
|
|
// // {
|
|
// // sign = true;
|
|
// // input = input.Substring(1);
|
|
// // }
|
|
|
|
// // foreach (char d in input)
|
|
// // {
|
|
// // int n = d - '0';
|
|
// // if (n > 9)
|
|
// // n = d - 55;
|
|
|
|
// // v *= radix;
|
|
// // v += n;
|
|
// // }
|
|
|
|
// // if (sign)
|
|
// // v = v.Twos();
|
|
|
|
// // return v;
|
|
// // }
|
|
|
|
|
|
|
|
// // private BigInteger __op_add(BigInteger b)
|
|
// // {
|
|
// // int width = (bits.Length > b.bits.Length ? bits.Length : b.bits.Length) + 1;
|
|
// // UInt32[] v = BigIntMath.extendSigned(bits, width);
|
|
// // UInt32[] vb = BigIntMath.extendSigned(b.bits, width);
|
|
// // return new BigInteger(BigIntMath.reduceSigned(BigIntMath.add(v,vb)));
|
|
// // }
|
|
// // private BigInteger __op_sub(BigInteger b)
|
|
// // {
|
|
// // int width = (bits.Length > b.bits.Length ? bits.Length : b.bits.Length) + 1;
|
|
// // UInt32[] v = BigIntMath.extendSigned(bits, width);
|
|
// // UInt32[] vb = BigIntMath.extendSigned(b.bits, width);
|
|
// // return new BigInteger(BigIntMath.reduceSigned(BigIntMath.sub(v,vb)));
|
|
// // }
|
|
|
|
// // private int __op_cmp(BigInteger b)
|
|
// // {
|
|
// // return BigIntMath.cmp(bits, b.bits);
|
|
// // }
|
|
|
|
// // private BigInteger __op_div(BigInteger b)
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.sdiv(bits, b.bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // private BigInteger __op_mod(BigInteger b)
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.smod(bits, b.bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // private BigInteger __op_mul(BigInteger b)
|
|
// // {
|
|
// // UInt32[] value = BigIntMath.smul(bits, b.bits);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_new(uint[] value)
|
|
// // {
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_shl(int b)
|
|
// // {
|
|
// // UInt32[] value = BigIntMath.extendSigned(bits, bits.Length + ((b + 31) >> 5));
|
|
// // BigIntMath.shl(value,b);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_shr(int b)
|
|
// // {
|
|
// // UInt32[] value = bits.Segment(0);
|
|
// // BigIntMath.shr(value, b);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // public static implicit operator BigInteger(int i)
|
|
// // {
|
|
// // return new BigInteger(new UInt32[]{(UInt32)i});
|
|
// // }
|
|
|
|
|
|
|
|
// // public static BigInteger operator +(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_add(b);
|
|
// // }
|
|
// // public static BigInteger operator -(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_sub(b);
|
|
// // }
|
|
// // public static BigInteger operator *(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_mul(b);
|
|
// // }
|
|
|
|
// // public static BigInteger operator /(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_div(b);
|
|
// // }
|
|
// // public static BigInteger operator %(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_mod(b);
|
|
// // }
|
|
|
|
// // public static bool operator <(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) < 0;
|
|
// // }
|
|
// // public static bool operator >(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) > 0;
|
|
// // }
|
|
// // public static bool operator ==(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // if ((object)a == (object)b)
|
|
// // {
|
|
// // return true;
|
|
// // }
|
|
// // if (((object)a == null) || ((object)b == null))
|
|
// // {
|
|
// // return false;
|
|
// // }
|
|
// // return a.__op_cmp(b) == 0;
|
|
// // }
|
|
// // public static bool operator !=(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) != 0;
|
|
// // }
|
|
|
|
// // public static BigInteger operator <<(BigInteger a, int b)
|
|
// // {
|
|
// // return a.__op_shl(b);
|
|
// // }
|
|
// // public static BigInteger operator >>(BigInteger a, int b)
|
|
// // {
|
|
// // return a.__op_shr(b);
|
|
// // }
|
|
|
|
// // public override bool Equals(object obj) => (obj is BigInteger other) && (this == other);
|
|
// // public override int GetHashCode() => ToByteArray().CreateHashCode();
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// /*** Native Implementations ***/
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// // public BigInteger(UInt32[] value)
|
|
// // {
|
|
// // this.bits = value;
|
|
// // }
|
|
|
|
|
|
|
|
|
|
// // public BigInteger(byte[] ivalue)
|
|
// // {
|
|
// // UInt32[] v = new UInt32[(ivalue.Length + 3) >> 2];
|
|
// // ivalue = ivalue.Segment(0, v.Length << 2);
|
|
|
|
// // for (int n = 0; n < v.Length; n++)
|
|
// // {
|
|
// // v[n] = BitConverter.ToUInt32(ivalue, n << 2);
|
|
// // }
|
|
// // this.bits = BigIntMath.reduceSigned(v);
|
|
// // }
|
|
// // public BigInteger(BigInteger src)
|
|
// // {
|
|
// // this.bits = src.bits;
|
|
// // }
|
|
|
|
// // public bool IsZero => BigIntMath.isZero(bits);
|
|
// // public int Sign => BigIntMath.isZero(bits) ? 0 : BigIntMath.sign(bits) ? -1 : 1;
|
|
|
|
// // public int GetByteCount() => bits.Length * 4;
|
|
// // public int GetBitLength() => BigIntMath.log2(bits);
|
|
|
|
// // public byte[] ToByteArray() => bits.GetBytes();
|
|
|
|
// // public void TryWriteBytes(Span<byte> s,out int bytesWritten)
|
|
// // {
|
|
// // byte[] sb = ToByteArray();
|
|
// // for (bytesWritten = 0; bytesWritten < sb.Length; bytesWritten++)
|
|
// // s[bytesWritten] = sb[bytesWritten];
|
|
// // }
|
|
|
|
// // public int Log2(){
|
|
// // return BigIntMath.log2(bits);
|
|
// // }
|
|
|
|
// // public static BigInteger ModPow(BigInteger i,int n,BigInteger modulus)
|
|
// // {
|
|
// // BigInteger r = BigInteger.One;
|
|
// // while (n-- > 0)
|
|
// // {
|
|
// // r *= i;
|
|
// // r %= modulus;
|
|
// // }
|
|
// // return r;
|
|
// // }
|
|
|
|
// // public BigInteger Pow(int n)
|
|
// // {
|
|
// // if (n == 0)
|
|
// // {
|
|
// // return One;
|
|
// // }
|
|
// // else if (n == 1)
|
|
// // {
|
|
// // return this;
|
|
// // }
|
|
// // else if (n > 1)
|
|
// // {
|
|
// // BigInteger result = this;
|
|
// // n--;
|
|
// // while ((n--) > 0)
|
|
// // {
|
|
// // result = (result * this);
|
|
// // }
|
|
// // return result;
|
|
// // }
|
|
// // throw new ArgumentException("Integer.Pow(n): not implemented for negative exponent");
|
|
// // }
|
|
|
|
// // public BigInteger Ones()
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.ones(bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // public BigInteger Twos()
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.twos(bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
|
|
// // public static BigInteger fromHexString(string hex) => Parse(hex, 16);
|
|
|
|
// // public override string ToString()
|
|
// // {
|
|
// // return String.Format("[{0}: Sign: {2,5} / {1}]", this.GetType().Name, ToString(16), Sign );
|
|
// // }
|
|
|
|
// // public string ToString(string format)
|
|
// // {
|
|
// // if (format.Equals("X"))
|
|
// // return ToString(16);
|
|
// // return ToString(10);
|
|
// // }
|
|
|
|
// // public string ToString(int radix) => ToString(radix, -1);
|
|
// // public string ToString(int radix, int length)
|
|
// // {
|
|
// // if ((radix < 2) || (radix > 36))
|
|
// // throw new ArgumentOutOfRangeException(nameof(radix));
|
|
|
|
// // uint[] v = bits.Segment(0);
|
|
// // uint[] r = new uint[]{ (uint)radix };
|
|
|
|
// // StringBuilder sb = new StringBuilder();
|
|
|
|
// // while ((!BigIntMath.isZero(v)) && ((length-- )!=0))
|
|
// // {
|
|
// // uint[] x = BigIntMath.sdivmod(ref v, r);
|
|
// // if (v[0] < 10)
|
|
// // sb.Append((char)('0' + v[0]));
|
|
// // else
|
|
// // sb.Append((char)(55 + v[0]));
|
|
// // v = x;
|
|
// // }
|
|
|
|
// // char[] result = new char[sb.Length];
|
|
// // sb.CopyTo(0, result, 0, sb.Length);
|
|
// // Array.Reverse(result);
|
|
// // return new string(result);
|
|
// // }
|
|
|
|
// // public static BigInteger Parse(string input) => Parse(input, 10);
|
|
|
|
// // public static BigInteger Parse(string input, NumberStyles numberStyles)
|
|
// // {
|
|
// // if ((numberStyles & (NumberStyles.HexNumber | NumberStyles.AllowHexSpecifier)) != 0)
|
|
// // return Parse(input, 16);
|
|
// // return Parse(input, 10);
|
|
// // }
|
|
|
|
// // public static BigInteger Parse(string input, int radix)
|
|
// // {
|
|
// // BigInteger v = 0;
|
|
// // bool sign = false;
|
|
|
|
// // if (input[0] == '-')
|
|
// // {
|
|
// // sign = true;
|
|
// // input = input.Substring(1);
|
|
// // }
|
|
|
|
// // foreach (char d in input)
|
|
// // {
|
|
// // int n = d - '0';
|
|
// // if (n > 9)
|
|
// // n = d - 55;
|
|
|
|
// // v *= radix;
|
|
// // v += n;
|
|
// // }
|
|
|
|
// // if (sign)
|
|
// // v = v.Twos();
|
|
|
|
// // return v;
|
|
// // }
|
|
|
|
|
|
|
|
// // private BigInteger __op_add(BigInteger b)
|
|
// // {
|
|
// // int width = (bits.Length > b.bits.Length ? bits.Length : b.bits.Length) + 1;
|
|
// // UInt32[] v = BigIntMath.extendSigned(bits, width);
|
|
// // UInt32[] vb = BigIntMath.extendSigned(b.bits, width);
|
|
// // return new BigInteger(BigIntMath.reduceSigned(BigIntMath.add(v,vb)));
|
|
// // }
|
|
// // private BigInteger __op_sub(BigInteger b)
|
|
// // {
|
|
// // int width = (bits.Length > b.bits.Length ? bits.Length : b.bits.Length) + 1;
|
|
// // UInt32[] v = BigIntMath.extendSigned(bits, width);
|
|
// // UInt32[] vb = BigIntMath.extendSigned(b.bits, width);
|
|
// // return new BigInteger(BigIntMath.reduceSigned(BigIntMath.sub(v,vb)));
|
|
// // }
|
|
|
|
// // private int __op_cmp(BigInteger b)
|
|
// // {
|
|
// // return BigIntMath.cmp(bits, b.bits);
|
|
// // }
|
|
|
|
// // private BigInteger __op_div(BigInteger b)
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.sdiv(bits, b.bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // private BigInteger __op_mod(BigInteger b)
|
|
// // {
|
|
// // UInt32[] result = BigIntMath.smod(bits, b.bits);
|
|
// // return new BigInteger(result);
|
|
// // }
|
|
|
|
// // private BigInteger __op_mul(BigInteger b)
|
|
// // {
|
|
// // UInt32[] value = BigIntMath.smul(bits, b.bits);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_new(uint[] value)
|
|
// // {
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_shl(int b)
|
|
// // {
|
|
// // UInt32[] value = BigIntMath.extendSigned(bits, bits.Length + ((b + 31) >> 5));
|
|
// // BigIntMath.shl(value,b);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // private BigInteger __op_shr(int b)
|
|
// // {
|
|
// // UInt32[] value = bits.Segment(0);
|
|
// // BigIntMath.shr(value, b);
|
|
// // return new BigInteger(value);
|
|
// // }
|
|
|
|
// // public static implicit operator BigInteger(int i)
|
|
// // {
|
|
// // return new BigInteger(new UInt32[]{(UInt32)i});
|
|
// // }
|
|
|
|
|
|
|
|
// // public static BigInteger operator +(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_add(b);
|
|
// // }
|
|
// // public static BigInteger operator -(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_sub(b);
|
|
// // }
|
|
// // public static BigInteger operator *(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_mul(b);
|
|
// // }
|
|
|
|
// // public static BigInteger operator /(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_div(b);
|
|
// // }
|
|
// // public static BigInteger operator %(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_mod(b);
|
|
// // }
|
|
|
|
// // public static bool operator <(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) < 0;
|
|
// // }
|
|
// // public static bool operator >(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) > 0;
|
|
// // }
|
|
// // public static bool operator ==(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // if ((object)a == (object)b)
|
|
// // {
|
|
// // return true;
|
|
// // }
|
|
// // if (((object)a == null) || ((object)b == null))
|
|
// // {
|
|
// // return false;
|
|
// // }
|
|
// // return a.__op_cmp(b) == 0;
|
|
// // }
|
|
// // public static bool operator !=(BigInteger a, BigInteger b)
|
|
// // {
|
|
// // return a.__op_cmp(b) != 0;
|
|
// // }
|
|
|
|
// // public static BigInteger operator <<(BigInteger a, int b)
|
|
// // {
|
|
// // return a.__op_shl(b);
|
|
// // }
|
|
// // public static BigInteger operator >>(BigInteger a, int b)
|
|
// // {
|
|
// // return a.__op_shr(b);
|
|
// // }
|
|
|
|
// // public override bool Equals(object obj) => (obj is BigInteger other) && (this == other);
|
|
// // public override int GetHashCode() => ToByteArray().CreateHashCode();
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
// /*** Native Implementations ***/
|
|
// [DllImport("bigint")]
|
|
// public static extern Int32 big_get_length(UInt32[] bits, Int32 length);
|
|
// public static Int32 big_get_length(UInt32[] bits) => big_get_length(bits, bits.Length);
|
|
|
|
// /***
|
|
// big_get_bitlength() returns the number of bits needed to represent this value including the sign bit
|
|
// ***/
|
|
// [DllImport("bigint")]
|
|
// public static extern Int32 big_get_bitlength(UInt32[] bits, Int32 length);
|
|
// public static Int32 big_get_bitlength(UInt32[] bits) => big_get_bitlength( bits, bits.Length );
|
|
|
|
// [DllImport("bigint")]
|
|
// public static extern Int32 big_parse(UInt32[] op, Int32 length, String source, Int32 radix);
|
|
// // [DllImport("bigint")]
|
|
// // public static extern Int32 big_log2(UInt32[] bits, Int32 length);
|
|
|
|
// [DllImport("bigint")]
|
|
// public static extern void big_add(UInt32[] op_a, Int32 length_a, UInt32[] op_b, Int32 length_b);
|
|
// public static void big_add(UInt32[] op_a, UInt32[] op_b) => big_add( op_a, op_a.Length, op_b, op_b.Length);
|
|
// //public static unsafe extern void big_add(UInt32* op_a, Int32 length_a, UInt32* op_b, Int32 length_b);
|
|
// // public unsafe static void big_add(UInt32[] op_a, UInt32[] op_b){
|
|
// // fixed (UInt32* a = op_a)
|
|
// // fixed (UInt32* b = op_b)
|
|
// // big_add( a, op_a.Length, b, op_b.Length );
|
|
// // }
|
|
|
|
// [DllImport("bigint")]
|
|
// public static extern void big_sub(UInt32[] op_a, Int32 length_a, UInt32[] op_b, Int32 length_b);
|
|
// public static void big_sub(UInt32[] op_a, UInt32[] op_b) => big_sub( op_a, op_a.Length, op_b, op_b.Length );
|
|
|
|
// [DllImport("bigint")]
|
|
// public static extern void big_twos(UInt32[] bits, Int32 length);
|
|
// [DllImport("bigint")]
|
|
// public static extern void big_shl(UInt32[] bits, Int32 length, Int32 n);
|
|
// [DllImport("bigint")]
|
|
// public static extern void big_shr(UInt32[] bits, Int32 length, Int32 n);
|
|
|
|
|
|
// [DllImport("bigint")]
|
|
// public static extern Int32 big_cmp(UInt32[] op_a, Int32 length_a, UInt32[] op_b, Int32 length_b);
|
|
// public static Int32 big_cmp(UInt32[] op_a, UInt32[] op_b) => big_cmp(op_a, op_a.Length, op_b, op_b.Length);
|
|
|
|
|
|
// [DllImport("bigint")]
|
|
// public static unsafe extern void big_smul(UInt32* op_a, Int32 length_a, UInt32* op_b, Int32 length_b);
|
|
// public static unsafe void big_smul(UInt32[] op_a, UInt32[] op_b)
|
|
// {
|
|
// fixed (UInt32* a = op_a)
|
|
// fixed (UInt32* b = op_b)
|
|
// big_smul( a, op_a.Length, b, op_b.Length);
|
|
// }
|
|
// [DllImport("bigint")]
|
|
// public static extern void big_divmod(UInt32[] op_a, Int32 length_a, UInt32[] op_b, Int32 length_b);
|
|
// public static void big_divmod(UInt32[] op_a, UInt32[] op_b) => big_divmod( op_a, op_a.Length, op_b, op_b.Length);
|
|
|
|
|
|
// private int max(int a,int b) => a > b ? a : b;
|
|
|
|
|
|
// public static int managed_get_length(UInt32[] op)
|
|
// {
|
|
// for (int n=op.Length-1;n>0;n--)
|
|
// {
|
|
// if ((op[n] != 0xFFFFFFFF) && ((op[n]==0) || ((op[n-1] & 0x80000000)!=0) ) )
|
|
// return n;
|
|
// }
|
|
// return 1;
|
|
// }
|
|
|
|
// public void managed_smul(UInt32[] op_a, UInt32[] op_b)
|
|
// {
|
|
// Int32 length_a = op_a.Length;
|
|
// Int32 length_b = op_b.Length;
|
|
// UInt32[] op_a_bak = new uint[length_a];
|
|
// Array.Copy(op_a, op_a_bak, length_a);
|
|
|
|
// for (int l1 = 0; l1 < length_a; l1++)
|
|
// {
|
|
// UInt64 ui64 = 0;
|
|
// int l2;
|
|
// for (l2 = 0; (l2 < length_b) && (l1 + l2 < length_a); l2++)
|
|
// {
|
|
// int target = l1 + l2;
|
|
// ui64 += op_a[target];
|
|
// ui64 += ((UInt64)op_a_bak[l1] * op_b[l2]);
|
|
// op_a[target] = (UInt32)ui64;
|
|
// ui64 >>= 32;
|
|
// }
|
|
// for (;(l2 < length_a) && (ui64 != 0);l2++)
|
|
// {
|
|
// int target = l1 + l2;
|
|
// ui64 += op_a[target];
|
|
// op_a[target] = (UInt32)ui64;
|
|
// ui64 >>= 32;
|
|
// }
|
|
// }
|
|
// }
|
|
|
|
// public void managed_add(UInt32[] op_a, UInt32[] op_b)
|
|
// {
|
|
// Int64 c = 0;
|
|
// Int32 length_a = op_a.Length;
|
|
// Int32 length_b = op_b.Length;
|
|
|
|
|
|
// for (int n=0;n<length_a;n++)
|
|
// {
|
|
// c += (Int64)op_a[n] + ((n < length_b) ? op_b[n] : 0);
|
|
// op_a[n] = (UInt32)c;
|
|
// c >>= 32;
|
|
|
|
// if ((c == 0) && (n > length_b))
|
|
// break;
|
|
// }
|
|
// }
|
|
|
|
// }
|
|
}
|