summary refs log tree commit diff
path: root/crypto/src/math/BigInteger.cs
diff options
context:
space:
mode:
Diffstat (limited to 'crypto/src/math/BigInteger.cs')
-rw-r--r--crypto/src/math/BigInteger.cs3141
1 files changed, 3141 insertions, 0 deletions
diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
new file mode 100644
index 000000000..d52c0f83c
--- /dev/null
+++ b/crypto/src/math/BigInteger.cs
@@ -0,0 +1,3141 @@
+using System;
+using System.Collections;
+using System.Diagnostics;
+using System.Globalization;
+using System.Text;
+
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Math
+{
+#if !(NETCF_1_0 || NETCF_2_0 || SILVERLIGHT || PORTABLE)
+	[Serializable]
+#endif
+    public class BigInteger
+	{
+		// The primes b/w 2 and ~2^10
+		/*
+				3   5   7   11  13  17  19  23  29
+			31  37  41  43  47  53  59  61  67  71
+			73  79  83  89  97  101 103 107 109 113
+			127 131 137 139 149 151 157 163 167 173
+			179 181 191 193 197 199 211 223 227 229
+			233 239 241 251 257 263 269 271 277 281
+			283 293 307 311 313 317 331 337 347 349
+			353 359 367 373 379 383 389 397 401 409
+			419 421 431 433 439 443 449 457 461 463
+			467 479 487 491 499 503 509 521 523 541
+			547 557 563 569 571 577 587 593 599 601
+			607 613 617 619 631 641 643 647 653 659
+			661 673 677 683 691 701 709 719 727 733
+			739 743 751 757 761 769 773 787 797 809
+			811 821 823 827 829 839 853 857 859 863
+			877 881 883 887 907 911 919 929 937 941
+			947 953 967 971 977 983 991 997
+			1009 1013 1019 1021 1031
+		*/
+
+		// Each list has a product < 2^31
+		private static readonly int[][] primeLists = new int[][]
+		{
+			new int[]{ 3, 5, 7, 11, 13, 17, 19, 23 },
+			new int[]{ 29, 31, 37, 41, 43 },
+			new int[]{ 47, 53, 59, 61, 67 },
+			new int[]{ 71, 73, 79, 83 },
+			new int[]{ 89, 97, 101, 103 },
+
+			new int[]{ 107, 109, 113, 127 },
+			new int[]{ 131, 137, 139, 149 },
+			new int[]{ 151, 157, 163, 167 },
+			new int[]{ 173, 179, 181, 191 },
+			new int[]{ 193, 197, 199, 211 },
+
+			new int[]{ 223, 227, 229 },
+			new int[]{ 233, 239, 241 },
+			new int[]{ 251, 257, 263 },
+			new int[]{ 269, 271, 277 },
+			new int[]{ 281, 283, 293 },
+
+			new int[]{ 307, 311, 313 },
+			new int[]{ 317, 331, 337 },
+			new int[]{ 347, 349, 353 },
+			new int[]{ 359, 367, 373 },
+			new int[]{ 379, 383, 389 },
+
+			new int[]{ 397, 401, 409 },
+			new int[]{ 419, 421, 431 },
+			new int[]{ 433, 439, 443 },
+			new int[]{ 449, 457, 461 },
+			new int[]{ 463, 467, 479 },
+
+			new int[]{ 487, 491, 499 },
+			new int[]{ 503, 509, 521 },
+			new int[]{ 523, 541, 547 },
+			new int[]{ 557, 563, 569 },
+			new int[]{ 571, 577, 587 },
+
+			new int[]{ 593, 599, 601 },
+			new int[]{ 607, 613, 617 },
+			new int[]{ 619, 631, 641 },
+			new int[]{ 643, 647, 653 },
+			new int[]{ 659, 661, 673 },
+
+			new int[]{ 677, 683, 691 },
+			new int[]{ 701, 709, 719 },
+			new int[]{ 727, 733, 739 },
+			new int[]{ 743, 751, 757 },
+			new int[]{ 761, 769, 773 },
+
+			new int[]{ 787, 797, 809 },
+			new int[]{ 811, 821, 823 },
+			new int[]{ 827, 829, 839 },
+			new int[]{ 853, 857, 859 },
+			new int[]{ 863, 877, 881 },
+
+			new int[]{ 883, 887, 907 },
+			new int[]{ 911, 919, 929 },
+			new int[]{ 937, 941, 947 },
+			new int[]{ 953, 967, 971 },
+			new int[]{ 977, 983, 991 },
+
+			new int[]{ 997, 1009, 1013 },
+			new int[]{ 1019, 1021, 1031 },
+		};
+
+		private static readonly int[] primeProducts;
+
+		private const long IMASK = 0xffffffffL;
+		private static readonly ulong UIMASK = (ulong)IMASK;
+
+		private static readonly int[] ZeroMagnitude = new int[0];
+		private static readonly byte[] ZeroEncoding = new byte[0];
+
+		public static readonly BigInteger Zero = new BigInteger(0, ZeroMagnitude, false);
+		public static readonly BigInteger One = createUValueOf(1);
+		public static readonly BigInteger Two = createUValueOf(2);
+		public static readonly BigInteger Three = createUValueOf(3);
+		public static readonly BigInteger Ten = createUValueOf(10);
+
+		private static readonly int chunk2 = 1; // TODO Parse 64 bits at a time
+		private static readonly BigInteger radix2 = ValueOf(2);
+		private static readonly BigInteger radix2E = radix2.Pow(chunk2);
+
+		private static readonly int chunk10 = 19;
+		private static readonly BigInteger radix10 = ValueOf(10);
+		private static readonly BigInteger radix10E = radix10.Pow(chunk10);
+
+		private static readonly int chunk16 = 16;
+		private static readonly BigInteger radix16 = ValueOf(16);
+		private static readonly BigInteger radix16E = radix16.Pow(chunk16);
+
+		private static readonly Random RandomSource = new Random();
+
+		private const int BitsPerByte = 8;
+		private const int BitsPerInt = 32;
+		private const int BytesPerInt = 4;
+
+		static BigInteger()
+		{
+			primeProducts = new int[primeLists.Length];
+
+			for (int i = 0; i < primeLists.Length; ++i)
+			{
+				int[] primeList = primeLists[i];
+				int product = primeList[0];
+				for (int j = 1; j < primeList.Length; ++j)
+				{
+					product *= primeList[j];
+				}
+				primeProducts[i] = product;
+			}
+		}
+
+		private int sign; // -1 means -ve; +1 means +ve; 0 means 0;
+		private int[] magnitude; // array of ints with [0] being the most significant
+		private int nBits = -1; // cache BitCount() value
+		private int nBitLength = -1; // cache calcBitLength() value
+		private long mQuote = -1L; // -m^(-1) mod b, b = 2^32 (see Montgomery mult.)
+
+		private static int GetByteLength(
+			int nBits)
+		{
+			return (nBits + BitsPerByte - 1) / BitsPerByte;
+		}
+
+		private BigInteger(
+			int		signum,
+			int[]	mag,
+			bool	checkMag)
+		{
+			if (checkMag)
+			{
+				int i = 0;
+				while (i < mag.Length && mag[i] == 0)
+				{
+					++i;
+				}
+
+				if (i == mag.Length)
+				{
+					this.sign = 0;
+					this.magnitude = ZeroMagnitude;
+				}
+				else
+				{
+					this.sign = signum;
+
+					if (i == 0)
+					{
+						this.magnitude = mag;
+					}
+					else
+					{
+						// strip leading 0 words
+						this.magnitude = new int[mag.Length - i];
+						Array.Copy(mag, i, this.magnitude, 0, this.magnitude.Length);
+					}
+				}
+			}
+			else
+			{
+				this.sign = signum;
+				this.magnitude = mag;
+			}
+		}
+
+		public BigInteger(
+			string value)
+			: this(value, 10)
+		{
+		}
+
+		public BigInteger(
+			string	str,
+			int		radix)
+		{
+			if (str.Length == 0)
+				throw new FormatException("Zero length BigInteger");
+
+			NumberStyles style;
+			int chunk;
+			BigInteger r;
+			BigInteger rE;
+
+			switch (radix)
+			{
+				case 2:
+					// Is there anyway to restrict to binary digits?
+					style = NumberStyles.Integer;
+					chunk = chunk2;
+					r = radix2;
+					rE = radix2E;
+					break;
+				case 10:
+					// This style seems to handle spaces and minus sign already (our processing redundant?)
+					style = NumberStyles.Integer;
+					chunk = chunk10;
+					r = radix10;
+					rE = radix10E;
+					break;
+				case 16:
+					// TODO Should this be HexNumber?
+					style = NumberStyles.AllowHexSpecifier;
+					chunk = chunk16;
+					r = radix16;
+					rE = radix16E;
+					break;
+				default:
+					throw new FormatException("Only bases 2, 10, or 16 allowed");
+			}
+
+
+			int index = 0;
+			sign = 1;
+
+			if (str[0] == '-')
+			{
+				if (str.Length == 1)
+					throw new FormatException("Zero length BigInteger");
+
+				sign = -1;
+				index = 1;
+			}
+
+			// strip leading zeros from the string str
+			while (index < str.Length && Int32.Parse(str[index].ToString(), style) == 0)
+			{
+				index++;
+			}
+
+			if (index >= str.Length)
+			{
+				// zero value - we're done
+				sign = 0;
+				magnitude = ZeroMagnitude;
+				return;
+			}
+
+			//////
+			// could we work out the max number of ints required to store
+			// str.Length digits in the given base, then allocate that
+			// storage in one hit?, then Generate the magnitude in one hit too?
+			//////
+
+			BigInteger b = Zero;
+
+
+			int next = index + chunk;
+
+			if (next <= str.Length)
+			{
+				do
+				{
+					string s = str.Substring(index, chunk);
+					ulong i = ulong.Parse(s, style);
+					BigInteger bi = createUValueOf(i);
+
+					switch (radix)
+					{
+						case 2:
+							// TODO Need this because we are parsing in radix 10 above
+							if (i > 1)
+								throw new FormatException("Bad character in radix 2 string: " + s);
+
+							// TODO Parse 64 bits at a time
+							b = b.ShiftLeft(1);
+							break;
+						case 16:
+							b = b.ShiftLeft(64);
+							break;
+						default:
+							b = b.Multiply(rE);
+							break;
+					}
+
+					b = b.Add(bi);
+
+					index = next;
+					next += chunk;
+				}
+				while (next <= str.Length);
+			}
+
+			if (index < str.Length)
+			{
+				string s = str.Substring(index);
+				ulong i = ulong.Parse(s, style);
+				BigInteger bi = createUValueOf(i);
+
+				if (b.sign > 0)
+				{
+					if (radix == 2)
+					{
+						// NB: Can't reach here since we are parsing one char at a time
+						Debug.Assert(false);
+
+						// TODO Parse all bits at once
+//						b = b.ShiftLeft(s.Length);
+					}
+					else if (radix == 16)
+					{
+						b = b.ShiftLeft(s.Length << 2);
+					}
+					else
+					{
+						b = b.Multiply(r.Pow(s.Length));
+					}
+
+					b = b.Add(bi);
+				}
+				else
+				{
+					b = bi;
+				}
+			}
+
+			// Note: This is the previous (slower) algorithm
+			//			while (index < value.Length)
+			//            {
+			//				char c = value[index];
+			//				string s = c.ToString();
+			//				int i = Int32.Parse(s, style);
+			//
+			//                b = b.Multiply(r).Add(ValueOf(i));
+			//                index++;
+			//            }
+
+			magnitude = b.magnitude;
+		}
+
+		public BigInteger(
+			byte[] bytes)
+			: this(bytes, 0, bytes.Length)
+		{
+		}
+
+		public BigInteger(
+			byte[]	bytes,
+			int		offset,
+			int		length)
+		{
+			if (length == 0)
+				throw new FormatException("Zero length BigInteger");
+
+			// TODO Move this processing into MakeMagnitude (provide sign argument)
+			if ((sbyte)bytes[offset] < 0)
+			{
+				this.sign = -1;
+
+				int end = offset + length;
+
+				int iBval;
+				// strip leading sign bytes
+				for (iBval = offset; iBval < end && ((sbyte)bytes[iBval] == -1); iBval++)
+				{
+				}
+
+				if (iBval >= end)
+				{
+					this.magnitude = One.magnitude;
+				}
+				else
+				{
+					int numBytes = end - iBval;
+					byte[] inverse = new byte[numBytes];
+
+					int index = 0;
+					while (index < numBytes)
+					{
+						inverse[index++] = (byte)~bytes[iBval++];
+					}
+
+					Debug.Assert(iBval == end);
+
+					while (inverse[--index] == byte.MaxValue)
+					{
+						inverse[index] = byte.MinValue;
+					}
+
+					inverse[index]++;
+
+					this.magnitude = MakeMagnitude(inverse, 0, inverse.Length);
+				}
+			}
+			else
+			{
+				// strip leading zero bytes and return magnitude bytes
+				this.magnitude = MakeMagnitude(bytes, offset, length);
+				this.sign = this.magnitude.Length > 0 ? 1 : 0;
+			}
+		}
+
+		private static int[] MakeMagnitude(
+			byte[]	bytes,
+			int		offset,
+			int		length)
+		{
+			int end = offset + length;
+
+			// strip leading zeros
+			int firstSignificant;
+			for (firstSignificant = offset; firstSignificant < end
+				&& bytes[firstSignificant] == 0; firstSignificant++)
+			{
+			}
+
+			if (firstSignificant >= end)
+			{
+				return ZeroMagnitude;
+			}
+
+			int nInts = (end - firstSignificant + 3) / BytesPerInt;
+			int bCount = (end - firstSignificant) % BytesPerInt;
+			if (bCount == 0)
+			{
+				bCount = BytesPerInt;
+			}
+
+			if (nInts < 1)
+			{
+				return ZeroMagnitude;
+			}
+
+			int[] mag = new int[nInts];
+
+			int v = 0;
+			int magnitudeIndex = 0;
+			for (int i = firstSignificant; i < end; ++i)
+			{
+				v <<= 8;
+				v |= bytes[i] & 0xff;
+				bCount--;
+				if (bCount <= 0)
+				{
+					mag[magnitudeIndex] = v;
+					magnitudeIndex++;
+					bCount = BytesPerInt;
+					v = 0;
+				}
+			}
+
+			if (magnitudeIndex < mag.Length)
+			{
+				mag[magnitudeIndex] = v;
+			}
+
+			return mag;
+		}
+
+		public BigInteger(
+			int		sign,
+			byte[]	bytes)
+			: this(sign, bytes, 0, bytes.Length)
+		{
+		}
+
+		public BigInteger(
+			int		sign,
+			byte[]	bytes,
+			int		offset,
+			int		length)
+		{
+			if (sign < -1 || sign > 1)
+				throw new FormatException("Invalid sign value");
+
+			if (sign == 0)
+			{
+				this.sign = 0;
+				this.magnitude = ZeroMagnitude;
+			}
+			else
+			{
+				// copy bytes
+				this.magnitude = MakeMagnitude(bytes, offset, length);
+				this.sign = this.magnitude.Length < 1 ? 0 : sign;
+			}
+		}
+
+		public BigInteger(
+			int		sizeInBits,
+			Random	random)
+		{
+			if (sizeInBits < 0)
+				throw new ArgumentException("sizeInBits must be non-negative");
+
+			this.nBits = -1;
+			this.nBitLength = -1;
+
+			if (sizeInBits == 0)
+			{
+				this.sign = 0;
+				this.magnitude = ZeroMagnitude;
+				return;
+			}
+
+			int nBytes = GetByteLength(sizeInBits);
+			byte[] b = new byte[nBytes];
+			random.NextBytes(b);
+
+			// strip off any excess bits in the MSB
+			b[0] &= rndMask[BitsPerByte * nBytes - sizeInBits];
+
+			this.magnitude = MakeMagnitude(b, 0, b.Length);
+			this.sign = this.magnitude.Length < 1 ? 0 : 1;
+		}
+
+		private static readonly byte[] rndMask = { 255, 127, 63, 31, 15, 7, 3, 1 };
+
+		public BigInteger(
+			int		bitLength,
+			int		certainty,
+			Random	random)
+		{
+			if (bitLength < 2)
+				throw new ArithmeticException("bitLength < 2");
+
+			this.sign = 1;
+			this.nBitLength = bitLength;
+
+			if (bitLength == 2)
+			{
+				this.magnitude = random.Next(2) == 0
+					?	Two.magnitude
+					:	Three.magnitude;
+				return;
+			}
+
+			int nBytes = GetByteLength(bitLength);
+			byte[] b = new byte[nBytes];
+
+			int xBits = BitsPerByte * nBytes - bitLength;
+			byte mask = rndMask[xBits];
+
+			for (;;)
+			{
+				random.NextBytes(b);
+
+				// strip off any excess bits in the MSB
+				b[0] &= mask;
+
+				// ensure the leading bit is 1 (to meet the strength requirement)
+				b[0] |= (byte)(1 << (7 - xBits));
+
+				// ensure the trailing bit is 1 (i.e. must be odd)
+				b[nBytes - 1] |= 1;
+
+				this.magnitude = MakeMagnitude(b, 0, b.Length);
+				this.nBits = -1;
+				this.mQuote = -1L;
+
+				if (certainty < 1)
+					break;
+
+				if (CheckProbablePrime(certainty, random))
+					break;
+
+				if (bitLength > 32)
+				{
+					for (int rep = 0; rep < 10000; ++rep)
+					{
+						int n = 33 + random.Next(bitLength - 2);
+						this.magnitude[this.magnitude.Length - (n >> 5)] ^= (1 << (n & 31));
+						this.magnitude[this.magnitude.Length - 1] ^= ((random.Next() + 1) << 1);
+						this.mQuote = -1L;
+
+						if (CheckProbablePrime(certainty, random))
+							return;
+					}
+				}
+			}
+		}
+
+		public BigInteger Abs()
+		{
+			return sign >= 0 ? this : Negate();
+		}
+
+		/**
+		 * return a = a + b - b preserved.
+		 */
+		private static int[] AddMagnitudes(
+			int[] a,
+			int[] b)
+		{
+			int tI = a.Length - 1;
+			int vI = b.Length - 1;
+			long m = 0;
+
+			while (vI >= 0)
+			{
+				m += ((long)(uint)a[tI] + (long)(uint)b[vI--]);
+				a[tI--] = (int)m;
+				m = (long)((ulong)m >> 32);
+			}
+
+			if (m != 0)
+			{
+				while (tI >= 0 && ++a[tI--] == 0)
+				{
+				}
+			}
+
+			return a;
+		}
+
+		public BigInteger Add(
+			BigInteger value)
+		{
+			if (this.sign == 0)
+				return value;
+
+			if (this.sign != value.sign)
+			{
+				if (value.sign == 0)
+					return this;
+
+				if (value.sign < 0)
+					return Subtract(value.Negate());
+
+				return value.Subtract(Negate());
+			}
+
+			return AddToMagnitude(value.magnitude);
+		}
+
+		private BigInteger AddToMagnitude(
+			int[] magToAdd)
+		{
+			int[] big, small;
+			if (this.magnitude.Length < magToAdd.Length)
+			{
+				big = magToAdd;
+				small = this.magnitude;
+			}
+			else
+			{
+				big = this.magnitude;
+				small = magToAdd;
+			}
+
+			// Conservatively avoid over-allocation when no overflow possible
+			uint limit = uint.MaxValue;
+			if (big.Length == small.Length)
+				limit -= (uint) small[0];
+
+			bool possibleOverflow = (uint) big[0] >= limit;
+
+			int[] bigCopy;
+			if (possibleOverflow)
+			{
+				bigCopy = new int[big.Length + 1];
+				big.CopyTo(bigCopy, 1);
+			}
+			else
+			{
+				bigCopy = (int[]) big.Clone();
+			}
+
+			bigCopy = AddMagnitudes(bigCopy, small);
+
+			return new BigInteger(this.sign, bigCopy, possibleOverflow);
+		}
+
+		public BigInteger And(
+			BigInteger value)
+		{
+			if (this.sign == 0 || value.sign == 0)
+			{
+				return Zero;
+			}
+
+			int[] aMag = this.sign > 0
+				? this.magnitude
+				: Add(One).magnitude;
+
+			int[] bMag = value.sign > 0
+				? value.magnitude
+				: value.Add(One).magnitude;
+
+			bool resultNeg = sign < 0 && value.sign < 0;
+			int resultLength = System.Math.Max(aMag.Length, bMag.Length);
+			int[] resultMag = new int[resultLength];
+
+			int aStart = resultMag.Length - aMag.Length;
+			int bStart = resultMag.Length - bMag.Length;
+
+			for (int i = 0; i < resultMag.Length; ++i)
+			{
+				int aWord = i >= aStart ? aMag[i - aStart] : 0;
+				int bWord = i >= bStart ? bMag[i - bStart] : 0;
+
+				if (this.sign < 0)
+				{
+					aWord = ~aWord;
+				}
+
+				if (value.sign < 0)
+				{
+					bWord = ~bWord;
+				}
+
+				resultMag[i] = aWord & bWord;
+
+				if (resultNeg)
+				{
+					resultMag[i] = ~resultMag[i];
+				}
+			}
+
+			BigInteger result = new BigInteger(1, resultMag, true);
+
+			// TODO Optimise this case
+			if (resultNeg)
+			{
+				result = result.Not();
+			}
+
+			return result;
+		}
+
+		public BigInteger AndNot(
+			BigInteger val)
+		{
+			return And(val.Not());
+		}
+
+		public int BitCount
+		{
+			get
+			{
+				if (nBits == -1)
+				{
+					if (sign < 0)
+					{
+						// TODO Optimise this case
+						nBits = Not().BitCount;
+					}
+					else
+					{
+						int sum = 0;
+						for (int i = 0; i < magnitude.Length; i++)
+						{
+							sum += bitCounts[(byte) magnitude[i]];
+							sum += bitCounts[(byte)(magnitude[i] >> 8)];
+							sum += bitCounts[(byte)(magnitude[i] >> 16)];
+							sum += bitCounts[(byte)(magnitude[i] >> 24)];
+						}
+						nBits = sum;
+					}
+				}
+
+				return nBits;
+			}
+		}
+
+		private readonly static byte[] bitCounts =
+		{
+			0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1,
+			2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4,
+			4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
+			4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
+			3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2,
+			3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3,
+			3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6,
+			7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6,
+			5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5,
+			6, 6, 7, 6, 7, 7, 8
+		};
+
+		private int calcBitLength(
+			int		indx,
+			int[]	mag)
+		{
+			for (;;)
+			{
+				if (indx >= mag.Length)
+					return 0;
+
+				if (mag[indx] != 0)
+					break;
+
+				++indx;
+			}
+
+			// bit length for everything after the first int
+			int bitLength = 32 * ((mag.Length - indx) - 1);
+
+			// and determine bitlength of first int
+			int firstMag = mag[indx];
+			bitLength += BitLen(firstMag);
+
+			// Check for negative powers of two
+			if (sign < 0 && ((firstMag & -firstMag) == firstMag))
+			{
+				do
+				{
+					if (++indx >= mag.Length)
+					{
+						--bitLength;
+						break;
+					}
+				}
+				while (mag[indx] == 0);
+			}
+
+			return bitLength;
+		}
+
+		public int BitLength
+		{
+			get
+			{
+				if (nBitLength == -1)
+				{
+					nBitLength = sign == 0
+						? 0
+						: calcBitLength(0, magnitude);
+				}
+
+				return nBitLength;
+			}
+		}
+
+		//
+		// BitLen(value) is the number of bits in value.
+		//
+		private static int BitLen(
+			int w)
+		{
+			// Binary search - decision tree (5 tests, rarely 6)
+			return (w < 1 << 15 ? (w < 1 << 7
+				? (w < 1 << 3 ? (w < 1 << 1
+				? (w < 1 << 0 ? (w < 0 ? 32 : 0) : 1)
+				: (w < 1 << 2 ? 2 : 3)) : (w < 1 << 5
+				? (w < 1 << 4 ? 4 : 5)
+				: (w < 1 << 6 ? 6 : 7)))
+				: (w < 1 << 11
+				? (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9) : (w < 1 << 10 ? 10 : 11))
+				: (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13) : (w < 1 << 14 ? 14 : 15)))) : (w < 1 << 23 ? (w < 1 << 19
+				? (w < 1 << 17 ? (w < 1 << 16 ? 16 : 17) : (w < 1 << 18 ? 18 : 19))
+				: (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21) : (w < 1 << 22 ? 22 : 23))) : (w < 1 << 27
+				? (w < 1 << 25 ? (w < 1 << 24 ? 24 : 25) : (w < 1 << 26 ? 26 : 27))
+				: (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29) : (w < 1 << 30 ? 30 : 31)))));
+		}
+
+//		private readonly static byte[] bitLengths =
+//		{
+//			0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
+//			5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+//			6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+//			7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+//			7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8,
+//			8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+//			8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+//			8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+//			8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+//			8, 8, 8, 8, 8, 8, 8, 8
+//		};
+
+		private bool QuickPow2Check()
+		{
+			return sign > 0 && nBits == 1;
+		}
+
+		public int CompareTo(
+			object obj)
+		{
+			return CompareTo((BigInteger)obj);
+		}
+
+		/**
+		 * unsigned comparison on two arrays - note the arrays may
+		 * start with leading zeros.
+		 */
+		private static int CompareTo(
+			int		xIndx,
+			int[]	x,
+			int		yIndx,
+			int[]	y)
+		{
+			while (xIndx != x.Length && x[xIndx] == 0)
+			{
+				xIndx++;
+			}
+
+			while (yIndx != y.Length && y[yIndx] == 0)
+			{
+				yIndx++;
+			}
+
+			return CompareNoLeadingZeroes(xIndx, x, yIndx, y);
+		}
+
+		private static int CompareNoLeadingZeroes(
+			int		xIndx,
+			int[]	x,
+			int		yIndx,
+			int[]	y)
+		{
+			int diff = (x.Length - y.Length) - (xIndx - yIndx);
+
+			if (diff != 0)
+			{
+				return diff < 0 ? -1 : 1;
+			}
+
+			// lengths of magnitudes the same, test the magnitude values
+
+			while (xIndx < x.Length)
+			{
+				uint v1 = (uint)x[xIndx++];
+				uint v2 = (uint)y[yIndx++];
+
+				if (v1 != v2)
+					return v1 < v2 ? -1 : 1;
+			}
+
+			return 0;
+		}
+
+		public int CompareTo(
+			BigInteger value)
+		{
+			return sign < value.sign ? -1
+				: sign > value.sign ? 1
+				: sign == 0 ? 0
+				: sign * CompareNoLeadingZeroes(0, magnitude, 0, value.magnitude);
+		}
+
+		/**
+		 * return z = x / y - done in place (z value preserved, x contains the
+		 * remainder)
+		 */
+		private int[] Divide(
+			int[]	x,
+			int[]	y)
+		{
+			int xStart = 0;
+			while (xStart < x.Length && x[xStart] == 0)
+			{
+				++xStart;
+			}
+
+			int yStart = 0;
+			while (yStart < y.Length && y[yStart] == 0)
+			{
+				++yStart;
+			}
+
+			Debug.Assert(yStart < y.Length);
+
+			int xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
+			int[] count;
+
+			if (xyCmp > 0)
+			{
+				int yBitLength = calcBitLength(yStart, y);
+				int xBitLength = calcBitLength(xStart, x);
+				int shift = xBitLength - yBitLength;
+
+				int[] iCount;
+				int iCountStart = 0;
+
+				int[] c;
+				int cStart = 0;
+				int cBitLength = yBitLength;
+				if (shift > 0)
+				{
+//					iCount = ShiftLeft(One.magnitude, shift);
+					iCount = new int[(shift >> 5) + 1];
+					iCount[0] = 1 << (shift % 32);
+
+					c = ShiftLeft(y, shift);
+					cBitLength += shift;
+				}
+				else
+				{
+					iCount = new int[] { 1 };
+
+					int len = y.Length - yStart;
+					c = new int[len];
+					Array.Copy(y, yStart, c, 0, len);
+				}
+
+				count = new int[iCount.Length];
+
+				for (;;)
+				{
+					if (cBitLength < xBitLength
+						|| CompareNoLeadingZeroes(xStart, x, cStart, c) >= 0)
+					{
+						Subtract(xStart, x, cStart, c);
+						AddMagnitudes(count, iCount);
+
+						while (x[xStart] == 0)
+						{
+							if (++xStart == x.Length)
+								return count;
+						}
+
+						//xBitLength = calcBitLength(xStart, x);
+						xBitLength = 32 * (x.Length - xStart - 1) + BitLen(x[xStart]);
+
+						if (xBitLength <= yBitLength)
+						{
+							if (xBitLength < yBitLength)
+								return count;
+
+							xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
+
+							if (xyCmp <= 0)
+								break;
+						}
+					}
+
+					shift = cBitLength - xBitLength;
+
+					// NB: The case where c[cStart] is 1-bit is harmless
+					if (shift == 1)
+					{
+						uint firstC = (uint) c[cStart] >> 1;
+						uint firstX = (uint) x[xStart];
+						if (firstC > firstX)
+							++shift;
+					}
+
+					if (shift < 2)
+					{
+						ShiftRightOneInPlace(cStart, c);
+						--cBitLength;
+						ShiftRightOneInPlace(iCountStart, iCount);
+					}
+					else
+					{
+						ShiftRightInPlace(cStart, c, shift);
+						cBitLength -= shift;
+						ShiftRightInPlace(iCountStart, iCount, shift);
+					}
+
+					//cStart = c.Length - ((cBitLength + 31) / 32);
+					while (c[cStart] == 0)
+					{
+						++cStart;
+					}
+
+					while (iCount[iCountStart] == 0)
+					{
+						++iCountStart;
+					}
+				}
+			}
+			else
+			{
+				count = new int[1];
+			}
+
+			if (xyCmp == 0)
+			{
+				AddMagnitudes(count, One.magnitude);
+				Array.Clear(x, xStart, x.Length - xStart);
+			}
+
+			return count;
+		}
+
+		public BigInteger Divide(
+			BigInteger val)
+		{
+			if (val.sign == 0)
+				throw new ArithmeticException("Division by zero error");
+
+			if (sign == 0)
+				return Zero;
+
+			if (val.QuickPow2Check()) // val is power of two
+			{
+				BigInteger result = this.Abs().ShiftRight(val.Abs().BitLength - 1);
+				return val.sign == this.sign ? result : result.Negate();
+			}
+
+			int[] mag = (int[]) this.magnitude.Clone();
+
+			return new BigInteger(this.sign * val.sign, Divide(mag, val.magnitude), true);
+		}
+
+		public BigInteger[] DivideAndRemainder(
+			BigInteger val)
+		{
+			if (val.sign == 0)
+				throw new ArithmeticException("Division by zero error");
+
+			BigInteger[] biggies = new BigInteger[2];
+
+			if (sign == 0)
+			{
+				biggies[0] = Zero;
+				biggies[1] = Zero;
+			}
+			else if (val.QuickPow2Check()) // val is power of two
+			{
+				int e = val.Abs().BitLength - 1;
+				BigInteger quotient = this.Abs().ShiftRight(e);
+				int[] remainder = this.LastNBits(e);
+
+				biggies[0] = val.sign == this.sign ? quotient : quotient.Negate();
+				biggies[1] = new BigInteger(this.sign, remainder, true);
+			}
+			else
+			{
+				int[] remainder = (int[]) this.magnitude.Clone();
+				int[] quotient = Divide(remainder, val.magnitude);
+
+				biggies[0] = new BigInteger(this.sign * val.sign, quotient, true);
+				biggies[1] = new BigInteger(this.sign, remainder, true);
+			}
+
+			return biggies;
+		}
+
+		public override bool Equals(
+			object obj)
+		{
+			if (obj == this)
+				return true;
+
+			BigInteger biggie = obj as BigInteger;
+			if (biggie == null)
+				return false;
+
+			if (biggie.sign != sign || biggie.magnitude.Length != magnitude.Length)
+				return false;
+
+			for (int i = 0; i < magnitude.Length; i++)
+			{
+				if (biggie.magnitude[i] != magnitude[i])
+				{
+					return false;
+				}
+			}
+
+			return true;
+		}
+
+		public BigInteger Gcd(
+			BigInteger value)
+		{
+			if (value.sign == 0)
+				return Abs();
+
+			if (sign == 0)
+				return value.Abs();
+
+			BigInteger r;
+			BigInteger u = this;
+			BigInteger v = value;
+
+			while (v.sign != 0)
+			{
+				r = u.Mod(v);
+				u = v;
+				v = r;
+			}
+
+			return u;
+		}
+
+		public override int GetHashCode()
+		{
+			int hc = magnitude.Length;
+			if (magnitude.Length > 0)
+			{
+				hc ^= magnitude[0];
+
+				if (magnitude.Length > 1)
+				{
+					hc ^= magnitude[magnitude.Length - 1];
+				}
+			}
+
+			return sign < 0 ? ~hc : hc;
+		}
+
+		// TODO Make public?
+		private BigInteger Inc()
+		{
+			if (this.sign == 0)
+				return One;
+
+			if (this.sign < 0)
+				return new BigInteger(-1, doSubBigLil(this.magnitude, One.magnitude), true);
+
+			return AddToMagnitude(One.magnitude);
+		}
+
+		public int IntValue
+		{
+			get
+			{
+				return sign == 0 ? 0
+					: sign > 0 ? magnitude[magnitude.Length - 1]
+					: -magnitude[magnitude.Length - 1];
+			}
+		}
+
+		/**
+		 * return whether or not a BigInteger is probably prime with a
+		 * probability of 1 - (1/2)**certainty.
+		 * <p>From Knuth Vol 2, pg 395.</p>
+		 */
+		public bool IsProbablePrime(
+			int certainty)
+		{
+			if (certainty <= 0)
+				return true;
+
+			BigInteger n = Abs();
+
+			if (!n.TestBit(0))
+				return n.Equals(Two);
+
+			if (n.Equals(One))
+				return false;
+
+			return n.CheckProbablePrime(certainty, RandomSource);
+		}
+
+		private bool CheckProbablePrime(
+			int		certainty,
+			Random	random)
+		{
+			Debug.Assert(certainty > 0);
+			Debug.Assert(CompareTo(Two) > 0);
+			Debug.Assert(TestBit(0));
+
+
+			// Try to reduce the penalty for really small numbers
+			int numLists = System.Math.Min(BitLength - 1, primeLists.Length);
+
+			for (int i = 0; i < numLists; ++i)
+			{
+				int test = Remainder(primeProducts[i]);
+
+				int[] primeList = primeLists[i];
+				for (int j = 0; j < primeList.Length; ++j)
+				{
+					int prime = primeList[j];
+					int qRem = test % prime;
+					if (qRem == 0)
+					{
+						// We may find small numbers in the list
+						return BitLength < 16 && IntValue == prime;
+					}
+				}
+			}
+
+
+			// TODO Special case for < 10^16 (RabinMiller fixed list)
+//			if (BitLength < 30)
+//			{
+//				RabinMiller against 2, 3, 5, 7, 11, 13, 23 is sufficient
+//			}
+
+
+			// TODO Is it worth trying to create a hybrid of these two?
+			return RabinMillerTest(certainty, random);
+//			return SolovayStrassenTest(certainty, random);
+
+//			bool rbTest = RabinMillerTest(certainty, random);
+//			bool ssTest = SolovayStrassenTest(certainty, random);
+//
+//			Debug.Assert(rbTest == ssTest);
+//
+//			return rbTest;
+		}
+
+		internal bool RabinMillerTest(
+			int		certainty,
+			Random	random)
+		{
+			Debug.Assert(certainty > 0);
+			Debug.Assert(BitLength > 2);
+			Debug.Assert(TestBit(0));
+
+			// let n = 1 + d . 2^s
+			BigInteger n = this;
+			BigInteger nMinusOne = n.Subtract(One);
+			int s = nMinusOne.GetLowestSetBit();
+			BigInteger r = nMinusOne.ShiftRight(s);
+
+			Debug.Assert(s >= 1);
+
+			do
+			{
+				// TODO Make a method for random BigIntegers in range 0 < x < n)
+				// - Method can be optimized by only replacing examined bits at each trial
+				BigInteger a;
+				do
+				{
+					a = new BigInteger(n.BitLength, random);
+				}
+				while (a.CompareTo(One) <= 0 || a.CompareTo(nMinusOne) >= 0);
+
+				BigInteger y = a.ModPow(r, n);
+
+				if (!y.Equals(One))
+				{
+					int j = 0;
+					while (!y.Equals(nMinusOne))
+					{
+						if (++j == s)
+							return false;
+
+						y = y.ModPow(Two, n);
+
+						if (y.Equals(One))
+							return false;
+					}
+				}
+
+				certainty -= 2; // composites pass for only 1/4 possible 'a'
+			}
+			while (certainty > 0);
+
+			return true;
+		}
+
+//		private bool SolovayStrassenTest(
+//			int		certainty,
+//			Random	random)
+//		{
+//			Debug.Assert(certainty > 0);
+//			Debug.Assert(CompareTo(Two) > 0);
+//			Debug.Assert(TestBit(0));
+//
+//			BigInteger n = this;
+//			BigInteger nMinusOne = n.Subtract(One);
+//			BigInteger e = nMinusOne.ShiftRight(1);
+//
+//			do
+//			{
+//				BigInteger a;
+//				do
+//				{
+//					a = new BigInteger(nBitLength, random);
+//				}
+//				// NB: Spec says 0 < x < n, but 1 is trivial
+//				while (a.CompareTo(One) <= 0 || a.CompareTo(n) >= 0);
+//
+//
+//				// TODO Check this is redundant given the way Jacobi() works?
+////				if (!a.Gcd(n).Equals(One))
+////					return false;
+//
+//				int x = Jacobi(a, n);
+//
+//				if (x == 0)
+//					return false;
+//
+//				BigInteger check = a.ModPow(e, n);
+//
+//				if (x == 1 && !check.Equals(One))
+//					return false;
+//
+//				if (x == -1 && !check.Equals(nMinusOne))
+//					return false;
+//
+//				--certainty;
+//			}
+//			while (certainty > 0);
+//
+//			return true;
+//		}
+//
+//		private static int Jacobi(
+//			BigInteger	a,
+//			BigInteger	b)
+//		{
+//			Debug.Assert(a.sign >= 0);
+//			Debug.Assert(b.sign > 0);
+//			Debug.Assert(b.TestBit(0));
+//			Debug.Assert(a.CompareTo(b) < 0);
+//
+//			int totalS = 1;
+//			for (;;)
+//			{
+//				if (a.sign == 0)
+//					return 0;
+//
+//				if (a.Equals(One))
+//					break;
+//
+//				int e = a.GetLowestSetBit();
+//
+//				int bLsw = b.magnitude[b.magnitude.Length - 1];
+//				if ((e & 1) != 0 && ((bLsw & 7) == 3 || (bLsw & 7) == 5))
+//					totalS = -totalS;
+//
+//				// TODO Confirm this is faster than later a1.Equals(One) test
+//				if (a.BitLength == e + 1)
+//					break;
+//				BigInteger a1 = a.ShiftRight(e);
+////				if (a1.Equals(One))
+////					break;
+//
+//				int a1Lsw = a1.magnitude[a1.magnitude.Length - 1];
+//				if ((bLsw & 3) == 3 && (a1Lsw & 3) == 3)
+//					totalS = -totalS;
+//
+////				a = b.Mod(a1);
+//				a = b.Remainder(a1);
+//				b = a1;
+//			}
+//			return totalS;
+//		}
+
+		public long LongValue
+		{
+			get
+			{
+				if (sign == 0)
+					return 0;
+
+				long v;
+				if (magnitude.Length > 1)
+				{
+					v = ((long)magnitude[magnitude.Length - 2] << 32)
+						| (magnitude[magnitude.Length - 1] & IMASK);
+				}
+				else
+				{
+					v = (magnitude[magnitude.Length - 1] & IMASK);
+				}
+
+				return sign < 0 ? -v : v;
+			}
+		}
+
+		public BigInteger Max(
+			BigInteger value)
+		{
+			return CompareTo(value) > 0 ? this : value;
+		}
+
+		public BigInteger Min(
+			BigInteger value)
+		{
+			return CompareTo(value) < 0 ? this : value;
+		}
+
+		public BigInteger Mod(
+			BigInteger m)
+		{
+			if (m.sign < 1)
+				throw new ArithmeticException("Modulus must be positive");
+
+			BigInteger biggie = Remainder(m);
+
+			return (biggie.sign >= 0 ? biggie : biggie.Add(m));
+		}
+
+		public BigInteger ModInverse(
+			BigInteger m)
+		{
+			if (m.sign < 1)
+				throw new ArithmeticException("Modulus must be positive");
+
+			// TODO Too slow at the moment
+//			// "Fast Key Exchange with Elliptic Curve Systems" R.Schoeppel
+//			if (m.TestBit(0))
+//			{
+//				//The Almost Inverse Algorithm
+//				int k = 0;
+//				BigInteger B = One, C = Zero, F = this, G = m, tmp;
+//
+//				for (;;)
+//				{
+//					// While F is even, do F=F/u, C=C*u, k=k+1.
+//					int zeroes = F.GetLowestSetBit();
+//					if (zeroes > 0)
+//					{
+//						F = F.ShiftRight(zeroes);
+//						C = C.ShiftLeft(zeroes);
+//						k += zeroes;
+//					}
+//
+//					// If F = 1, then return B,k.
+//					if (F.Equals(One))
+//					{
+//						BigInteger half = m.Add(One).ShiftRight(1);
+//						BigInteger halfK = half.ModPow(BigInteger.ValueOf(k), m);
+//						return B.Multiply(halfK).Mod(m);
+//					}
+//
+//					if (F.CompareTo(G) < 0)
+//					{
+//						tmp = G; G = F; F = tmp;
+//						tmp = B; B = C; C = tmp;
+//					}
+//
+//					F = F.Add(G);
+//					B = B.Add(C);
+//				}
+//			}
+
+            BigInteger x;
+            BigInteger gcd = ExtEuclid(this.Mod(m), m, out x);
+
+			if (!gcd.Equals(One))
+				throw new ArithmeticException("Numbers not relatively prime.");
+
+			if (x.sign < 0)
+			{
+                x = x.Add(m);
+			}
+
+			return x;
+		}
+
+		/**
+		 * Calculate the numbers u1, u2, and u3 such that:
+		 *
+		 * u1 * a + u2 * b = u3
+		 *
+		 * where u3 is the greatest common divider of a and b.
+		 * a and b using the extended Euclid algorithm (refer p. 323
+		 * of The Art of Computer Programming vol 2, 2nd ed).
+		 * This also seems to have the side effect of calculating
+		 * some form of multiplicative inverse.
+		 *
+		 * @param a    First number to calculate gcd for
+		 * @param b    Second number to calculate gcd for
+		 * @param u1Out      the return object for the u1 value
+		 * @param u2Out      the return object for the u2 value
+		 * @return     The greatest common divisor of a and b
+		 */
+		private static BigInteger ExtEuclid(
+			BigInteger	    a,
+			BigInteger	    b,
+			out BigInteger  u1Out)
+            //BigInteger	    u2Out)
+		{
+			BigInteger u1 = One;
+			BigInteger u3 = a;
+			BigInteger v1 = Zero;
+			BigInteger v3 = b;
+
+			while (v3.sign > 0)
+			{
+				BigInteger[] q = u3.DivideAndRemainder(v3);
+
+				BigInteger tmp = v1.Multiply(q[0]);
+				BigInteger tn = u1.Subtract(tmp);
+				u1 = v1;
+				v1 = tn;
+
+				u3 = v3;
+				v3 = q[1];
+			}
+
+            //if (u1Out != null)
+            //{
+            //    u1Out.sign = u1.sign;
+            //    u1Out.magnitude = u1.magnitude;
+            //}
+            u1Out = u1;
+
+            //if (u2Out != null)
+            //{
+            //    BigInteger tmp = u1.Multiply(a);
+            //    tmp = u3.Subtract(tmp);
+            //    BigInteger res = tmp.Divide(b);
+            //    u2Out.sign = res.sign;
+            //    u2Out.magnitude = res.magnitude;
+            //}
+
+			return u3;
+		}
+
+		private static void ZeroOut(
+			int[] x)
+		{
+			Array.Clear(x, 0, x.Length);
+		}
+
+		public BigInteger ModPow(
+			BigInteger exponent,
+			BigInteger m)
+		{
+			if (m.sign < 1)
+				throw new ArithmeticException("Modulus must be positive");
+
+			if (m.Equals(One))
+				return Zero;
+
+			if (exponent.sign == 0)
+				return One;
+
+			if (sign == 0)
+				return Zero;
+
+			int[] zVal = null;
+			int[] yAccum = null;
+			int[] yVal;
+
+			// Montgomery exponentiation is only possible if the modulus is odd,
+			// but AFAIK, this is always the case for crypto algo's
+			bool useMonty = ((m.magnitude[m.magnitude.Length - 1] & 1) == 1);
+			long mQ = 0;
+			if (useMonty)
+			{
+				mQ = m.GetMQuote();
+
+				// tmp = this * R mod m
+				BigInteger tmp = ShiftLeft(32 * m.magnitude.Length).Mod(m);
+				zVal = tmp.magnitude;
+
+				useMonty = (zVal.Length <= m.magnitude.Length);
+
+				if (useMonty)
+				{
+					yAccum = new int[m.magnitude.Length + 1];
+					if (zVal.Length < m.magnitude.Length)
+					{
+						int[] longZ = new int[m.magnitude.Length];
+						zVal.CopyTo(longZ, longZ.Length - zVal.Length);
+						zVal = longZ;
+					}
+				}
+			}
+
+			if (!useMonty)
+			{
+				if (magnitude.Length <= m.magnitude.Length)
+				{
+					//zAccum = new int[m.magnitude.Length * 2];
+					zVal = new int[m.magnitude.Length];
+					magnitude.CopyTo(zVal, zVal.Length - magnitude.Length);
+				}
+				else
+				{
+					//
+					// in normal practice we'll never see this...
+					//
+					BigInteger tmp = Remainder(m);
+
+					//zAccum = new int[m.magnitude.Length * 2];
+					zVal = new int[m.magnitude.Length];
+					tmp.magnitude.CopyTo(zVal, zVal.Length - tmp.magnitude.Length);
+				}
+
+				yAccum = new int[m.magnitude.Length * 2];
+			}
+
+			yVal = new int[m.magnitude.Length];
+
+			//
+			// from LSW to MSW
+			//
+			for (int i = 0; i < exponent.magnitude.Length; i++)
+			{
+				int v = exponent.magnitude[i];
+				int bits = 0;
+
+				if (i == 0)
+				{
+					while (v > 0)
+					{
+						v <<= 1;
+						bits++;
+					}
+
+					//
+					// first time in initialise y
+					//
+					zVal.CopyTo(yVal, 0);
+
+					v <<= 1;
+					bits++;
+				}
+
+				while (v != 0)
+				{
+					if (useMonty)
+					{
+						// Montgomery square algo doesn't exist, and a normal
+						// square followed by a Montgomery reduction proved to
+						// be almost as heavy as a Montgomery mulitply.
+						MultiplyMonty(yAccum, yVal, yVal, m.magnitude, mQ);
+					}
+					else
+					{
+						Square(yAccum, yVal);
+						Remainder(yAccum, m.magnitude);
+						Array.Copy(yAccum, yAccum.Length - yVal.Length, yVal, 0, yVal.Length);
+						ZeroOut(yAccum);
+					}
+					bits++;
+
+					if (v < 0)
+					{
+						if (useMonty)
+						{
+							MultiplyMonty(yAccum, yVal, zVal, m.magnitude, mQ);
+						}
+						else
+						{
+							Multiply(yAccum, yVal, zVal);
+							Remainder(yAccum, m.magnitude);
+							Array.Copy(yAccum, yAccum.Length - yVal.Length, yVal, 0,
+								yVal.Length);
+							ZeroOut(yAccum);
+						}
+					}
+
+					v <<= 1;
+				}
+
+				while (bits < 32)
+				{
+					if (useMonty)
+					{
+						MultiplyMonty(yAccum, yVal, yVal, m.magnitude, mQ);
+					}
+					else
+					{
+						Square(yAccum, yVal);
+						Remainder(yAccum, m.magnitude);
+						Array.Copy(yAccum, yAccum.Length - yVal.Length, yVal, 0, yVal.Length);
+						ZeroOut(yAccum);
+					}
+					bits++;
+				}
+			}
+
+			if (useMonty)
+			{
+				// Return y * R^(-1) mod m by doing y * 1 * R^(-1) mod m
+				ZeroOut(zVal);
+				zVal[zVal.Length - 1] = 1;
+				MultiplyMonty(yAccum, yVal, zVal, m.magnitude, mQ);
+			}
+
+			BigInteger result = new BigInteger(1, yVal, true);
+
+			return exponent.sign > 0
+				?	result
+				:	result.ModInverse(m);
+		}
+
+		/**
+		 * return w with w = x * x - w is assumed to have enough space.
+		 */
+		private static int[] Square(
+			int[]	w,
+			int[]	x)
+		{
+			// Note: this method allows w to be only (2 * x.Length - 1) words if result will fit
+//			if (w.Length != 2 * x.Length)
+//				throw new ArgumentException("no I don't think so...");
+
+			ulong u1, u2, c;
+
+			int wBase = w.Length - 1;
+
+			for (int i = x.Length - 1; i != 0; i--)
+			{
+				ulong v = (ulong)(uint) x[i];
+
+				u1 = v * v;
+				u2 = u1 >> 32;
+				u1 = (uint) u1;
+
+				u1 += (ulong)(uint) w[wBase];
+
+				w[wBase] = (int)(uint) u1;
+				c = u2 + (u1 >> 32);
+
+				for (int j = i - 1; j >= 0; j--)
+				{
+					--wBase;
+					u1 = v * (ulong)(uint) x[j];
+					u2 = u1 >> 31; // multiply by 2!
+					u1 = (uint)(u1 << 1); // multiply by 2!
+					u1 += c + (ulong)(uint) w[wBase];
+
+					w[wBase] = (int)(uint) u1;
+					c = u2 + (u1 >> 32);
+				}
+
+				c += (ulong)(uint) w[--wBase];
+				w[wBase] = (int)(uint) c;
+
+				if (--wBase >= 0)
+				{
+					w[wBase] = (int)(uint)(c >> 32);
+				}
+				else
+				{
+					Debug.Assert((uint)(c >> 32) == 0);
+				}
+				wBase += i;
+			}
+
+			u1 = (ulong)(uint) x[0];
+			u1 = u1 * u1;
+			u2 = u1 >> 32;
+			u1 = u1 & IMASK;
+
+			u1 += (ulong)(uint) w[wBase];
+
+			w[wBase] = (int)(uint) u1;
+			if (--wBase >= 0)
+			{
+				w[wBase] = (int)(uint)(u2 + (u1 >> 32) + (ulong)(uint) w[wBase]);
+			}
+			else
+			{
+				Debug.Assert((uint)(u2 + (u1 >> 32)) == 0);
+			}
+
+			return w;
+		}
+
+		/**
+		 * return x with x = y * z - x is assumed to have enough space.
+		 */
+		private static int[] Multiply(
+			int[]	x,
+			int[]	y,
+			int[]	z)
+		{
+			int i = z.Length;
+
+			if (i < 1)
+				return x;
+
+			int xBase = x.Length - y.Length;
+
+			do
+			{
+				long a = z[--i] & IMASK;
+				long val = 0;
+
+				if (a != 0)
+				{
+					for (int j = y.Length - 1; j >= 0; j--)
+					{
+						val += a * (y[j] & IMASK) + (x[xBase + j] & IMASK);
+	
+						x[xBase + j] = (int)val;
+	
+						val = (long)((ulong)val >> 32);
+					}
+				}
+
+				--xBase;
+
+				if (xBase >= 0)
+				{
+					x[xBase] = (int)val;
+				}
+				else
+				{
+					Debug.Assert(val == 0);
+				}
+			}
+			while (i > 0);
+
+			return x;
+		}
+
+		private static long FastExtEuclid(
+			long	a,
+			long	b,
+			long[]	uOut)
+		{
+			long u1 = 1;
+			long u3 = a;
+			long v1 = 0;
+			long v3 = b;
+
+			while (v3 > 0)
+			{
+				long q, tn;
+
+				q = u3 / v3;
+
+				tn = u1 - (v1 * q);
+				u1 = v1;
+				v1 = tn;
+
+				tn = u3 - (v3 * q);
+				u3 = v3;
+				v3 = tn;
+			}
+
+			uOut[0] = u1;
+			uOut[1] = (u3 - (u1 * a)) / b;
+
+			return u3;
+		}
+
+		private static long FastModInverse(
+			long	v,
+			long	m)
+		{
+			if (m < 1)
+				throw new ArithmeticException("Modulus must be positive");
+
+			long[] x = new long[2];
+			long gcd = FastExtEuclid(v, m, x);
+
+			if (gcd != 1)
+				throw new ArithmeticException("Numbers not relatively prime.");
+
+			if (x[0] < 0)
+			{
+				x[0] += m;
+			}
+
+			return x[0];
+		}
+
+//		private static BigInteger MQuoteB = One.ShiftLeft(32);
+//		private static BigInteger MQuoteBSub1 = MQuoteB.Subtract(One);
+
+		/**
+		 * Calculate mQuote = -m^(-1) mod b with b = 2^32 (32 = word size)
+		 */
+		private long GetMQuote()
+		{
+			Debug.Assert(this.sign > 0);
+
+			if (mQuote != -1)
+			{
+				return mQuote; // already calculated
+			}
+
+			if (magnitude.Length == 0 || (magnitude[magnitude.Length - 1] & 1) == 0)
+			{
+				return -1; // not for even numbers
+			}
+
+			long v = (((~this.magnitude[this.magnitude.Length - 1]) | 1) & 0xffffffffL);
+			mQuote = FastModInverse(v, 0x100000000L);
+
+			return mQuote;
+		}
+
+		/**
+		 * Montgomery multiplication: a = x * y * R^(-1) mod m
+		 * <br/>
+		 * Based algorithm 14.36 of Handbook of Applied Cryptography.
+		 * <br/>
+		 * <li> m, x, y should have length n </li>
+		 * <li> a should have length (n + 1) </li>
+		 * <li> b = 2^32, R = b^n </li>
+		 * <br/>
+		 * The result is put in x
+		 * <br/>
+		 * NOTE: the indices of x, y, m, a different in HAC and in Java
+		 */
+		private static void MultiplyMonty(
+			int[]	a,
+			int[]	x,
+			int[]	y,
+			int[]	m,
+			long	mQuote)
+			// mQuote = -m^(-1) mod b
+		{
+			if (m.Length == 1)
+			{
+				x[0] = (int)MultiplyMontyNIsOne((uint)x[0], (uint)y[0], (uint)m[0], (ulong)mQuote);
+				return;
+			}
+
+			int n = m.Length;
+			int nMinus1 = n - 1;
+			long y_0 = y[nMinus1] & IMASK;
+
+			// 1. a = 0 (Notation: a = (a_{n} a_{n-1} ... a_{0})_{b} )
+			Array.Clear(a, 0, n + 1);
+
+			// 2. for i from 0 to (n - 1) do the following:
+			for (int i = n; i > 0; i--)
+			{
+				long x_i = x[i - 1] & IMASK;
+
+				// 2.1 u = ((a[0] + (x[i] * y[0]) * mQuote) mod b
+				long u = ((((a[n] & IMASK) + ((x_i * y_0) & IMASK)) & IMASK) * mQuote) & IMASK;
+
+				// 2.2 a = (a + x_i * y + u * m) / b
+				long prod1 = x_i * y_0;
+				long prod2 = u * (m[nMinus1] & IMASK);
+				long tmp = (a[n] & IMASK) + (prod1 & IMASK) + (prod2 & IMASK);
+				long carry = (long)((ulong)prod1 >> 32) + (long)((ulong)prod2 >> 32) + (long)((ulong)tmp >> 32);
+				for (int j = nMinus1; j > 0; j--)
+				{
+					prod1 = x_i * (y[j - 1] & IMASK);
+					prod2 = u * (m[j - 1] & IMASK);
+					tmp = (a[j] & IMASK) + (prod1 & IMASK) + (prod2 & IMASK) + (carry & IMASK);
+					carry = (long)((ulong)carry >> 32) + (long)((ulong)prod1 >> 32) +
+						(long)((ulong)prod2 >> 32) + (long)((ulong)tmp >> 32);
+					a[j + 1] = (int)tmp; // division by b
+				}
+				carry += (a[0] & IMASK);
+				a[1] = (int)carry;
+				a[0] = (int)((ulong)carry >> 32); // OJO!!!!!
+			}
+
+			// 3. if x >= m the x = x - m
+			if (CompareTo(0, a, 0, m) >= 0)
+			{
+				Subtract(0, a, 0, m);
+			}
+
+			// put the result in x
+			Array.Copy(a, 1, x, 0, n);
+		}
+
+		private static uint MultiplyMontyNIsOne(
+			uint	x,
+			uint	y,
+			uint	m,
+			ulong	mQuote)
+		{
+			ulong um = m;
+			ulong prod1 = (ulong)x * (ulong)y;
+			ulong u = (prod1 * mQuote) & UIMASK;
+			ulong prod2 = u * um;
+			ulong tmp = (prod1 & UIMASK) + (prod2 & UIMASK);
+			ulong carry = (prod1 >> 32) + (prod2 >> 32) + (tmp >> 32);
+
+			if (carry > um)
+			{
+				carry -= um;
+			}
+
+			return (uint)(carry & UIMASK);
+		}
+
+		public BigInteger Multiply(
+			BigInteger val)
+		{
+			if (sign == 0 || val.sign == 0)
+				return Zero;
+
+			if (val.QuickPow2Check()) // val is power of two
+			{
+				BigInteger result = this.ShiftLeft(val.Abs().BitLength - 1);
+				return val.sign > 0 ? result : result.Negate();
+			}
+
+			if (this.QuickPow2Check()) // this is power of two
+			{
+				BigInteger result = val.ShiftLeft(this.Abs().BitLength - 1);
+				return this.sign > 0 ? result : result.Negate();
+			}
+
+			int resLength = (this.BitLength + val.BitLength) / BitsPerInt + 1;
+			int[] res = new int[resLength];
+
+			if (val == this)
+			{
+				Square(res, this.magnitude);
+			}
+			else
+			{
+				Multiply(res, this.magnitude, val.magnitude);
+			}
+
+			return new BigInteger(sign * val.sign, res, true);
+		}
+
+		public BigInteger Negate()
+		{
+			if (sign == 0)
+				return this;
+
+			return new BigInteger(-sign, magnitude, false);
+		}
+
+		public BigInteger NextProbablePrime()
+		{
+			if (sign < 0)
+				throw new ArithmeticException("Cannot be called on value < 0");
+
+			if (CompareTo(Two) < 0)
+				return Two;
+
+			BigInteger n = Inc().SetBit(0);
+
+			while (!n.CheckProbablePrime(100, RandomSource))
+			{
+				n = n.Add(Two);
+			}
+
+			return n;
+		}
+
+		public BigInteger Not()
+		{
+			return Inc().Negate();
+		}
+
+		public BigInteger Pow(int exp)
+		{
+			if (exp < 0)
+			{
+				throw new ArithmeticException("Negative exponent");
+			}
+
+			if (exp == 0)
+			{
+				return One;
+			}
+
+			if (sign == 0 || Equals(One))
+			{
+				return this;
+			}
+
+			BigInteger y = One;
+			BigInteger z = this;
+
+			for (;;)
+			{
+				if ((exp & 0x1) == 1)
+				{
+					y = y.Multiply(z);
+				}
+				exp >>= 1;
+				if (exp == 0) break;
+				z = z.Multiply(z);
+			}
+
+			return y;
+		}
+
+		public static BigInteger ProbablePrime(
+			int bitLength,
+			Random random)
+		{
+			return new BigInteger(bitLength, 100, random);
+		}
+
+		private int Remainder(
+			int m)
+		{
+			Debug.Assert(m > 0);
+
+			long acc = 0;
+			for (int pos = 0; pos < magnitude.Length; ++pos)
+			{
+				long posVal = (uint) magnitude[pos];
+				acc = (acc << 32 | posVal) % m;
+			}
+
+			return (int) acc;
+		}
+
+		/**
+		 * return x = x % y - done in place (y value preserved)
+		 */
+		private int[] Remainder(
+			int[] x,
+			int[] y)
+		{
+			int xStart = 0;
+			while (xStart < x.Length && x[xStart] == 0)
+			{
+				++xStart;
+			}
+
+			int yStart = 0;
+			while (yStart < y.Length && y[yStart] == 0)
+			{
+				++yStart;
+			}
+
+			Debug.Assert(yStart < y.Length);
+
+			int xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
+
+			if (xyCmp > 0)
+			{
+				int yBitLength = calcBitLength(yStart, y);
+				int xBitLength = calcBitLength(xStart, x);
+				int shift = xBitLength - yBitLength;
+
+				int[] c;
+				int cStart = 0;
+				int cBitLength = yBitLength;
+				if (shift > 0)
+				{
+					c = ShiftLeft(y, shift);
+					cBitLength += shift;
+					Debug.Assert(c[0] != 0);
+				}
+				else
+				{
+					int len = y.Length - yStart;
+					c = new int[len];
+					Array.Copy(y, yStart, c, 0, len);
+				}
+
+				for (;;)
+				{
+					if (cBitLength < xBitLength
+						|| CompareNoLeadingZeroes(xStart, x, cStart, c) >= 0)
+					{
+						Subtract(xStart, x, cStart, c);
+
+						while (x[xStart] == 0)
+						{
+							if (++xStart == x.Length)
+								return x;
+						}
+
+						//xBitLength = calcBitLength(xStart, x);
+						xBitLength = 32 * (x.Length - xStart - 1) + BitLen(x[xStart]);
+
+						if (xBitLength <= yBitLength)
+						{
+							if (xBitLength < yBitLength)
+								return x;
+
+							xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
+
+							if (xyCmp <= 0)
+								break;
+						}
+					}
+
+					shift = cBitLength - xBitLength;
+
+					// NB: The case where c[cStart] is 1-bit is harmless
+					if (shift == 1)
+					{
+						uint firstC = (uint) c[cStart] >> 1;
+						uint firstX = (uint) x[xStart];
+						if (firstC > firstX)
+							++shift;
+					}
+
+					if (shift < 2)
+					{
+						ShiftRightOneInPlace(cStart, c);
+						--cBitLength;
+					}
+					else
+					{
+						ShiftRightInPlace(cStart, c, shift);
+						cBitLength -= shift;
+					}
+
+					//cStart = c.Length - ((cBitLength + 31) / 32);
+					while (c[cStart] == 0)
+					{
+						++cStart;
+					}
+				}
+			}
+
+			if (xyCmp == 0)
+			{
+				Array.Clear(x, xStart, x.Length - xStart);
+			}
+
+			return x;
+		}
+
+		public BigInteger Remainder(
+			BigInteger n)
+		{
+			if (n.sign == 0)
+				throw new ArithmeticException("Division by zero error");
+
+			if (this.sign == 0)
+				return Zero;
+
+			// For small values, use fast remainder method
+			if (n.magnitude.Length == 1)
+			{
+				int val = n.magnitude[0];
+
+				if (val > 0)
+				{
+					if (val == 1)
+						return Zero;
+
+					// TODO Make this func work on uint, and handle val == 1?
+					int rem = Remainder(val);
+
+					return rem == 0
+						?	Zero
+						:	new BigInteger(sign, new int[]{ rem }, false);
+				}
+			}
+
+			if (CompareNoLeadingZeroes(0, magnitude, 0, n.magnitude) < 0)
+				return this;
+
+			int[] result;
+			if (n.QuickPow2Check())  // n is power of two
+			{
+				// TODO Move before small values branch above?
+				result = LastNBits(n.Abs().BitLength - 1);
+			}
+			else
+			{
+				result = (int[]) this.magnitude.Clone();
+				result = Remainder(result, n.magnitude);
+			}
+
+			return new BigInteger(sign, result, true);
+		}
+
+		private int[] LastNBits(
+			int n)
+		{
+			if (n < 1)
+				return ZeroMagnitude;
+
+			int numWords = (n + BitsPerInt - 1) / BitsPerInt;
+			numWords = System.Math.Min(numWords, this.magnitude.Length);
+			int[] result = new int[numWords];
+
+			Array.Copy(this.magnitude, this.magnitude.Length - numWords, result, 0, numWords);
+
+			int hiBits = n % 32;
+			if (hiBits != 0)
+			{
+				result[0] &= ~(-1 << hiBits);
+			}
+
+			return result;
+		}
+
+		/**
+		 * do a left shift - this returns a new array.
+		 */
+		private static int[] ShiftLeft(
+			int[]	mag,
+			int		n)
+		{
+			int nInts = (int)((uint)n >> 5);
+			int nBits = n & 0x1f;
+			int magLen = mag.Length;
+			int[] newMag;
+
+			if (nBits == 0)
+			{
+				newMag = new int[magLen + nInts];
+				mag.CopyTo(newMag, 0);
+			}
+			else
+			{
+				int i = 0;
+				int nBits2 = 32 - nBits;
+				int highBits = (int)((uint)mag[0] >> nBits2);
+
+				if (highBits != 0)
+				{
+					newMag = new int[magLen + nInts + 1];
+					newMag[i++] = highBits;
+				}
+				else
+				{
+					newMag = new int[magLen + nInts];
+				}
+
+				int m = mag[0];
+				for (int j = 0; j < magLen - 1; j++)
+				{
+					int next = mag[j + 1];
+
+					newMag[i++] = (m << nBits) | (int)((uint)next >> nBits2);
+					m = next;
+				}
+
+				newMag[i] = mag[magLen - 1] << nBits;
+			}
+
+			return newMag;
+		}
+
+		public BigInteger ShiftLeft(
+			int n)
+		{
+			if (sign == 0 || magnitude.Length == 0)
+				return Zero;
+
+			if (n == 0)
+				return this;
+
+			if (n < 0)
+				return ShiftRight(-n);
+
+			BigInteger result = new BigInteger(sign, ShiftLeft(magnitude, n), true);
+
+			if (this.nBits != -1)
+			{
+				result.nBits = sign > 0
+					?	this.nBits
+					:	this.nBits + n;
+			}
+
+			if (this.nBitLength != -1)
+			{
+				result.nBitLength = this.nBitLength + n;
+			}
+
+			return result;
+		}
+
+		/**
+		 * do a right shift - this does it in place.
+		 */
+		private static void ShiftRightInPlace(
+			int		start,
+			int[]	mag,
+			int		n)
+		{
+			int nInts = (int)((uint)n >> 5) + start;
+			int nBits = n & 0x1f;
+			int magEnd = mag.Length - 1;
+
+			if (nInts != start)
+			{
+				int delta = (nInts - start);
+
+				for (int i = magEnd; i >= nInts; i--)
+				{
+					mag[i] = mag[i - delta];
+				}
+				for (int i = nInts - 1; i >= start; i--)
+				{
+					mag[i] = 0;
+				}
+			}
+
+			if (nBits != 0)
+			{
+				int nBits2 = 32 - nBits;
+				int m = mag[magEnd];
+
+				for (int i = magEnd; i > nInts; --i)
+				{
+					int next = mag[i - 1];
+
+					mag[i] = (int)((uint)m >> nBits) | (next << nBits2);
+					m = next;
+				}
+
+				mag[nInts] = (int)((uint)mag[nInts] >> nBits);
+			}
+		}
+
+		/**
+		 * do a right shift by one - this does it in place.
+		 */
+		private static void ShiftRightOneInPlace(
+			int		start,
+			int[]	mag)
+		{
+			int i = mag.Length;
+			int m = mag[i - 1];
+
+			while (--i > start)
+			{
+				int next = mag[i - 1];
+				mag[i] = ((int)((uint)m >> 1)) | (next << 31);
+				m = next;
+			}
+
+			mag[start] = (int)((uint)mag[start] >> 1);
+		}
+
+        public BigInteger ShiftRight(
+			int n)
+		{
+			if (n == 0)
+				return this;
+
+			if (n < 0)
+				return ShiftLeft(-n);
+
+			if (n >= BitLength)
+				return (this.sign < 0 ? One.Negate() : Zero);
+
+//			int[] res = (int[]) this.magnitude.Clone();
+//
+//			ShiftRightInPlace(0, res, n);
+//
+//			return new BigInteger(this.sign, res, true);
+
+			int resultLength = (BitLength - n + 31) >> 5;
+			int[] res = new int[resultLength];
+
+			int numInts = n >> 5;
+			int numBits = n & 31;
+
+			if (numBits == 0)
+			{
+				Array.Copy(this.magnitude, 0, res, 0, res.Length);
+			}
+			else
+			{
+				int numBits2 = 32 - numBits;
+
+				int magPos = this.magnitude.Length - 1 - numInts;
+				for (int i = resultLength - 1; i >= 0; --i)
+				{
+					res[i] = (int)((uint) this.magnitude[magPos--] >> numBits);
+
+					if (magPos >= 0)
+					{
+						res[i] |= this.magnitude[magPos] << numBits2;
+					}
+				}
+			}
+
+			Debug.Assert(res[0] != 0);
+
+			return new BigInteger(this.sign, res, false);
+		}
+
+		public int SignValue
+		{
+			get { return sign; }
+		}
+
+		/**
+		 * returns x = x - y - we assume x is >= y
+		 */
+		private static int[] Subtract(
+			int		xStart,
+			int[]	x,
+			int		yStart,
+			int[]	y)
+		{
+			Debug.Assert(yStart < y.Length);
+			Debug.Assert(x.Length - xStart >= y.Length - yStart);
+
+			int iT = x.Length;
+			int iV = y.Length;
+			long m;
+			int borrow = 0;
+
+			do
+			{
+				m = (x[--iT] & IMASK) - (y[--iV] & IMASK) + borrow;
+				x[iT] = (int) m;
+
+//				borrow = (m < 0) ? -1 : 0;
+				borrow = (int)(m >> 63);
+			}
+			while (iV > yStart);
+
+			if (borrow != 0)
+			{
+				while (--x[--iT] == -1)
+				{
+				}
+			}
+
+			return x;
+		}
+
+		public BigInteger Subtract(
+			BigInteger n)
+		{
+			if (n.sign == 0)
+				return this;
+
+			if (this.sign == 0)
+				return n.Negate();
+
+			if (this.sign != n.sign)
+				return Add(n.Negate());
+
+			int compare = CompareNoLeadingZeroes(0, magnitude, 0, n.magnitude);
+			if (compare == 0)
+				return Zero;
+
+			BigInteger bigun, lilun;
+			if (compare < 0)
+			{
+				bigun = n;
+				lilun = this;
+			}
+			else
+			{
+				bigun = this;
+				lilun = n;
+			}
+
+			return new BigInteger(this.sign * compare, doSubBigLil(bigun.magnitude, lilun.magnitude), true);
+		}
+
+		private static int[] doSubBigLil(
+			int[]	bigMag,
+			int[]	lilMag)
+		{
+			int[] res = (int[]) bigMag.Clone();
+
+			return Subtract(0, res, 0, lilMag);
+		}
+
+		public byte[] ToByteArray()
+		{
+			return ToByteArray(false);
+		}
+
+		public byte[] ToByteArrayUnsigned()
+		{
+			return ToByteArray(true);
+		}
+
+		private byte[] ToByteArray(
+			bool unsigned)
+		{
+			if (sign == 0)
+				return unsigned ? ZeroEncoding : new byte[1];
+
+			int nBits = (unsigned && sign > 0)
+				?	BitLength
+				:	BitLength + 1;
+
+			int nBytes = GetByteLength(nBits);
+			byte[] bytes = new byte[nBytes];
+
+			int magIndex = magnitude.Length;
+			int bytesIndex = bytes.Length;
+
+			if (sign > 0)
+			{
+				while (magIndex > 1)
+				{
+					uint mag = (uint) magnitude[--magIndex];
+					bytes[--bytesIndex] = (byte) mag;
+					bytes[--bytesIndex] = (byte)(mag >> 8);
+					bytes[--bytesIndex] = (byte)(mag >> 16);
+					bytes[--bytesIndex] = (byte)(mag >> 24);
+				}
+
+				uint lastMag = (uint) magnitude[0];
+				while (lastMag > byte.MaxValue)
+				{
+					bytes[--bytesIndex] = (byte) lastMag;
+					lastMag >>= 8;
+				}
+
+				bytes[--bytesIndex] = (byte) lastMag;
+			}
+			else // sign < 0
+			{
+				bool carry = true;
+
+				while (magIndex > 1)
+				{
+					uint mag = ~((uint) magnitude[--magIndex]);
+
+					if (carry)
+					{
+						carry = (++mag == uint.MinValue);
+					}
+
+					bytes[--bytesIndex] = (byte) mag;
+					bytes[--bytesIndex] = (byte)(mag >> 8);
+					bytes[--bytesIndex] = (byte)(mag >> 16);
+					bytes[--bytesIndex] = (byte)(mag >> 24);
+				}
+
+				uint lastMag = (uint) magnitude[0];
+
+				if (carry)
+				{
+					// Never wraps because magnitude[0] != 0
+					--lastMag;
+				}
+
+				while (lastMag > byte.MaxValue)
+				{
+					bytes[--bytesIndex] = (byte) ~lastMag;
+					lastMag >>= 8;
+				}
+
+				bytes[--bytesIndex] = (byte) ~lastMag;
+
+				if (bytesIndex > 0)
+				{
+					bytes[--bytesIndex] = byte.MaxValue;
+				}
+			}
+
+			return bytes;
+		}
+
+		public override string ToString()
+		{
+			return ToString(10);
+		}
+
+		public string ToString(
+			int radix)
+		{
+			// TODO Make this method work for other radices (ideally 2 <= radix <= 16)
+
+			switch (radix)
+			{
+				case 2:
+				case 10:
+				case 16:
+					break;
+				default:
+					throw new FormatException("Only bases 2, 10, 16 are allowed");
+			}
+
+			// NB: Can only happen to internally managed instances
+			if (magnitude == null)
+				return "null";
+
+			if (sign == 0)
+				return "0";
+
+			Debug.Assert(magnitude.Length > 0);
+
+			StringBuilder sb = new StringBuilder();
+
+			if (radix == 16)
+			{
+				sb.Append(magnitude[0].ToString("x"));
+
+				for (int i = 1; i < magnitude.Length; i++)
+				{
+					sb.Append(magnitude[i].ToString("x8"));
+				}
+			}
+			else if (radix == 2)
+			{
+				sb.Append('1');
+
+				for (int i = BitLength - 2; i >= 0; --i)
+				{
+					sb.Append(TestBit(i) ? '1' : '0');
+				}
+			}
+			else
+			{
+				// This is algorithm 1a from chapter 4.4 in Seminumerical Algorithms, slow but it works
+				IList S = Platform.CreateArrayList();
+				BigInteger bs = ValueOf(radix);
+
+				// The sign is handled separatly.
+				// Notice however that for this to work, radix 16 _MUST_ be a special case,
+				// unless we want to enter a recursion well. In their infinite wisdom, why did not
+				// the Sun engineers made a c'tor for BigIntegers taking a BigInteger as parameter?
+				// (Answer: Becuase Sun's BigIntger is clonable, something bouncycastle's isn't.)
+//				BigInteger u = new BigInteger(Abs().ToString(16), 16);
+				BigInteger u = this.Abs();
+				BigInteger b;
+
+				while (u.sign != 0)
+				{
+					b = u.Mod(bs);
+					if (b.sign == 0)
+					{
+						S.Add("0");
+					}
+					else
+					{
+						// see how to interact with different bases
+						S.Add(b.magnitude[0].ToString("d"));
+					}
+					u = u.Divide(bs);
+				}
+
+				// Then pop the stack
+                for (int i = S.Count - 1; i >= 0; --i)
+                {
+                    sb.Append((string)S[i]);
+                }
+			}
+
+			string s = sb.ToString();
+
+			Debug.Assert(s.Length > 0);
+
+			// Strip leading zeros. (We know this number is not all zeroes though)
+			if (s[0] == '0')
+			{
+				int nonZeroPos = 0;
+				while (s[++nonZeroPos] == '0') {}
+
+				s = s.Substring(nonZeroPos);
+			}
+
+			if (sign == -1)
+			{
+				s = "-" + s;
+			}
+
+			return s;
+		}
+
+		private static BigInteger createUValueOf(
+			ulong value)
+		{
+			int msw = (int)(value >> 32);
+			int lsw = (int)value;
+
+			if (msw != 0)
+				return new BigInteger(1, new int[] { msw, lsw }, false);
+
+			if (lsw != 0)
+			{
+				BigInteger n = new BigInteger(1, new int[] { lsw }, false);
+				// Check for a power of two
+				if ((lsw & -lsw) == lsw)
+				{
+					n.nBits = 1;
+				}
+				return n;
+			}
+
+			return Zero;
+		}
+
+		private static BigInteger createValueOf(
+			long value)
+		{
+			if (value < 0)
+			{
+				if (value == long.MinValue)
+					return createValueOf(~value).Not();
+
+				return createValueOf(-value).Negate();
+			}
+
+			return createUValueOf((ulong)value);
+
+//			// store value into a byte array
+//			byte[] b = new byte[8];
+//			for (int i = 0; i < 8; i++)
+//			{
+//				b[7 - i] = (byte)value;
+//				value >>= 8;
+//			}
+//
+//			return new BigInteger(b);
+		}
+
+		public static BigInteger ValueOf(
+			long value)
+		{
+			switch (value)
+			{
+				case 0:
+					return Zero;
+				case 1:
+					return One;
+				case 2:
+					return Two;
+				case 3:
+					return Three;
+				case 10:
+					return Ten;
+			}
+
+			return createValueOf(value);
+		}
+
+		public int GetLowestSetBit()
+		{
+			if (this.sign == 0)
+				return -1;
+
+			int w = magnitude.Length;
+
+			while (--w > 0)
+			{
+				if (magnitude[w] != 0)
+					break;
+			}
+
+			int word = (int) magnitude[w];
+			Debug.Assert(word != 0);
+
+			int b = (word & 0x0000FFFF) == 0
+				?	(word & 0x00FF0000) == 0
+					?	7
+					:	15
+				:	(word & 0x000000FF) == 0
+					?	23
+					:	31;
+
+			while (b > 0)
+			{
+				if ((word << b) == int.MinValue)
+					break;
+
+				b--;
+			}
+
+			return ((magnitude.Length - w) * 32 - (b + 1));
+		}
+
+		public bool TestBit(
+			int n)
+		{
+			if (n < 0)
+				throw new ArithmeticException("Bit position must not be negative");
+
+			if (sign < 0)
+				return !Not().TestBit(n);
+
+			int wordNum = n / 32;
+			if (wordNum >= magnitude.Length)
+				return false;
+
+			int word = magnitude[magnitude.Length - 1 - wordNum];
+			return ((word >> (n % 32)) & 1) > 0;
+		}
+
+		public BigInteger Or(
+			BigInteger value)
+		{
+			if (this.sign == 0)
+				return value;
+
+			if (value.sign == 0)
+				return this;
+
+			int[] aMag = this.sign > 0
+				? this.magnitude
+				: Add(One).magnitude;
+
+			int[] bMag = value.sign > 0
+				? value.magnitude
+				: value.Add(One).magnitude;
+
+			bool resultNeg = sign < 0 || value.sign < 0;
+			int resultLength = System.Math.Max(aMag.Length, bMag.Length);
+			int[] resultMag = new int[resultLength];
+
+			int aStart = resultMag.Length - aMag.Length;
+			int bStart = resultMag.Length - bMag.Length;
+
+			for (int i = 0; i < resultMag.Length; ++i)
+			{
+				int aWord = i >= aStart ? aMag[i - aStart] : 0;
+				int bWord = i >= bStart ? bMag[i - bStart] : 0;
+
+				if (this.sign < 0)
+				{
+					aWord = ~aWord;
+				}
+
+				if (value.sign < 0)
+				{
+					bWord = ~bWord;
+				}
+
+				resultMag[i] = aWord | bWord;
+
+				if (resultNeg)
+				{
+					resultMag[i] = ~resultMag[i];
+				}
+			}
+
+			BigInteger result = new BigInteger(1, resultMag, true);
+
+			// TODO Optimise this case
+			if (resultNeg)
+			{
+				result = result.Not();
+			}
+
+			return result;
+		}
+
+		public BigInteger Xor(
+			BigInteger value)
+		{
+			if (this.sign == 0)
+				return value;
+
+			if (value.sign == 0)
+				return this;
+
+			int[] aMag = this.sign > 0
+				? this.magnitude
+				: Add(One).magnitude;
+
+			int[] bMag = value.sign > 0
+				? value.magnitude
+				: value.Add(One).magnitude;
+
+			// TODO Can just replace with sign != value.sign?
+			bool resultNeg = (sign < 0 && value.sign >= 0) || (sign >= 0 && value.sign < 0);
+			int resultLength = System.Math.Max(aMag.Length, bMag.Length);
+			int[] resultMag = new int[resultLength];
+
+			int aStart = resultMag.Length - aMag.Length;
+			int bStart = resultMag.Length - bMag.Length;
+
+			for (int i = 0; i < resultMag.Length; ++i)
+			{
+				int aWord = i >= aStart ? aMag[i - aStart] : 0;
+				int bWord = i >= bStart ? bMag[i - bStart] : 0;
+
+				if (this.sign < 0)
+				{
+					aWord = ~aWord;
+				}
+
+				if (value.sign < 0)
+				{
+					bWord = ~bWord;
+				}
+
+				resultMag[i] = aWord ^ bWord;
+
+				if (resultNeg)
+				{
+					resultMag[i] = ~resultMag[i];
+				}
+			}
+
+			BigInteger result = new BigInteger(1, resultMag, true);
+
+			// TODO Optimise this case
+			if (resultNeg)
+			{
+				result = result.Not();
+			}
+
+			return result;
+		}
+
+		public BigInteger SetBit(
+			int n)
+		{
+			if (n < 0)
+				throw new ArithmeticException("Bit address less than zero");
+
+			if (TestBit(n))
+				return this;
+
+			// TODO Handle negative values and zero
+			if (sign > 0 && n < (BitLength - 1))
+				return FlipExistingBit(n);
+
+			return Or(One.ShiftLeft(n));
+		}
+
+		public BigInteger ClearBit(
+			int n)
+		{
+			if (n < 0)
+				throw new ArithmeticException("Bit address less than zero");
+
+			if (!TestBit(n))
+				return this;
+
+			// TODO Handle negative values
+			if (sign > 0 && n < (BitLength - 1))
+				return FlipExistingBit(n);
+
+			return AndNot(One.ShiftLeft(n));
+		}
+
+		public BigInteger FlipBit(
+			int n)
+		{
+			if (n < 0)
+				throw new ArithmeticException("Bit address less than zero");
+
+			// TODO Handle negative values and zero
+			if (sign > 0 && n < (BitLength - 1))
+				return FlipExistingBit(n);
+
+			return Xor(One.ShiftLeft(n));
+		}
+
+		private BigInteger FlipExistingBit(
+			int n)
+		{
+			Debug.Assert(sign > 0);
+			Debug.Assert(n >= 0);
+			Debug.Assert(n < BitLength - 1);
+
+			int[] mag = (int[]) this.magnitude.Clone();
+			mag[mag.Length - 1 - (n >> 5)] ^= (1 << (n & 31)); // Flip bit
+			//mag[mag.Length - 1 - (n / 32)] ^= (1 << (n % 32));
+			return new BigInteger(this.sign, mag, false);
+		}
+	}
+}