Add Nat/Mod classes and use instead of (slow) BigInteger.ModInverse implementation for FpFieldElement

1 files changed, 0 insertions, 485 deletions

diff --git a/crypto/src/math/ec/IntArray.cs b/crypto/src/math/ec/IntArray.cs
deleted file mode 100644
index 1089966a8..000000000
--- a/crypto/src/math/ec/IntArray.cs
+++ /dev/null
@@ -1,485 +0,0 @@
-using System;
-using System.Text;
-
-namespace Org.BouncyCastle.Math.EC
-{
-	internal class IntArray
-    {
-        // TODO make m fixed for the IntArray, and hence compute T once and for all
-
-		// TODO Use uint's internally?
-		private int[] m_ints;
-
-		public IntArray(int intLen)
-		{
-			m_ints = new int[intLen];
-		}
-
-		private IntArray(int[] ints)
-		{
-			m_ints = ints;
-		}
-
-		public IntArray(BigInteger bigInt)
-			: this(bigInt, 0)
-		{
-		}
-
-		public IntArray(BigInteger bigInt, int minIntLen)
-		{
-			if (bigInt.SignValue == -1)
-				throw new ArgumentException("Only positive Integers allowed", "bigint");
-
-			if (bigInt.SignValue == 0)
-			{
-				m_ints = new int[] { 0 };
-				return;
-			}
-
-			byte[] barr = bigInt.ToByteArrayUnsigned();
-			int barrLen = barr.Length;
-
-			int intLen = (barrLen + 3) / 4;
-			m_ints = new int[System.Math.Max(intLen, minIntLen)];
-
-			int rem = barrLen % 4;
-			int barrI = 0;
-
-			if (0 < rem)
-			{
-				int temp = (int) barr[barrI++];
-				while (barrI < rem)
-				{
-					temp = temp << 8 | (int) barr[barrI++];
-				}
-				m_ints[--intLen] = temp;
-			}
-
-			while (intLen > 0)
-			{
-				int temp = (int) barr[barrI++];
-				for (int i = 1; i < 4; i++)
-				{
-					temp = temp << 8 | (int) barr[barrI++];
-				}
-				m_ints[--intLen] = temp;
-			}
-		}
-
-		public int GetUsedLength()
-		{
-			int highestIntPos = m_ints.Length;
-
-			if (highestIntPos < 1)
-				return 0;
-
-			// Check if first element will act as sentinel
-			if (m_ints[0] != 0)
-			{
-				while (m_ints[--highestIntPos] == 0)
-				{
-				}
-				return highestIntPos + 1;
-			}
-
-			do
-			{
-				if (m_ints[--highestIntPos] != 0)
-				{
-					return highestIntPos + 1;
-				}
-			}
-			while (highestIntPos > 0);
-
-			return 0;
-		}
-
-		public int BitLength
-		{
-			get
-			{
-				// JDK 1.5: see Integer.numberOfLeadingZeros()
-				int intLen = GetUsedLength();
-				if (intLen == 0)
-					return 0;
-
-				int last = intLen - 1;
-				uint highest = (uint) m_ints[last];
-				int bits = (last << 5) + 1;
-
-				// A couple of binary search steps
-				if (highest > 0x0000ffff)
-				{
-					if (highest > 0x00ffffff)
-					{
-						bits += 24;
-						highest >>= 24;
-					}
-					else
-					{
-						bits += 16;
-						highest >>= 16;
-					}
-				}
-				else if (highest > 0x000000ff)
-				{
-					bits += 8;
-					highest >>= 8;
-				}
-
-				while (highest > 1)
-				{
-					++bits;
-					highest >>= 1;
-				}
-
-				return bits;
-			}
-		}
-
-		private int[] resizedInts(int newLen)
-		{
-			int[] newInts = new int[newLen];
-			int oldLen = m_ints.Length;
-			int copyLen = oldLen < newLen ? oldLen : newLen;
-			Array.Copy(m_ints, 0, newInts, 0, copyLen);
-			return newInts;
-		}
-
-		public BigInteger ToBigInteger()
-		{
-			int usedLen = GetUsedLength();
-			if (usedLen == 0)
-			{
-				return BigInteger.Zero;
-			}
-
-			int highestInt = m_ints[usedLen - 1];
-			byte[] temp = new byte[4];
-			int barrI = 0;
-			bool trailingZeroBytesDone = false;
-			for (int j = 3; j >= 0; j--)
-			{
-				byte thisByte = (byte)((int)((uint) highestInt >> (8 * j)));
-				if (trailingZeroBytesDone || (thisByte != 0))
-				{
-					trailingZeroBytesDone = true;
-					temp[barrI++] = thisByte;
-				}
-			}
-
-			int barrLen = 4 * (usedLen - 1) + barrI;
-			byte[] barr = new byte[barrLen];
-			for (int j = 0; j < barrI; j++)
-			{
-				barr[j] = temp[j];
-			}
-			// Highest value int is done now
-
-			for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--)
-			{
-				for (int j = 3; j >= 0; j--)
-				{
-					barr[barrI++] = (byte)((int)((uint)m_ints[iarrJ] >> (8 * j)));
-				}
-			}
-			return new BigInteger(1, barr);
-		}
-
-		public void ShiftLeft()
-		{
-			int usedLen = GetUsedLength();
-			if (usedLen == 0)
-			{
-				return;
-			}
-			if (m_ints[usedLen - 1] < 0)
-			{
-				// highest bit of highest used byte is set, so shifting left will
-				// make the IntArray one byte longer
-				usedLen++;
-				if (usedLen > m_ints.Length)
-				{
-					// make the m_ints one byte longer, because we need one more
-					// byte which is not available in m_ints
-					m_ints = resizedInts(m_ints.Length + 1);
-				}
-			}
-
-			bool carry = false;
-			for (int i = 0; i < usedLen; i++)
-			{
-				// nextCarry is true if highest bit is set
-				bool nextCarry = m_ints[i] < 0;
-				m_ints[i] <<= 1;
-				if (carry)
-				{
-					// set lowest bit
-					m_ints[i] |= 1;
-				}
-				carry = nextCarry;
-			}
-		}
-
-		public IntArray ShiftLeft(int n)
-		{
-			int usedLen = GetUsedLength();
-			if (usedLen == 0)
-			{
-				return this;
-			}
-
-			if (n == 0)
-			{
-				return this;
-			}
-
-			if (n > 31)
-			{
-				throw new ArgumentException("shiftLeft() for max 31 bits "
-					+ ", " + n + "bit shift is not possible", "n");
-			}
-
-			int[] newInts = new int[usedLen + 1];
-
-			int nm32 = 32 - n;
-			newInts[0] = m_ints[0] << n;
-			for (int i = 1; i < usedLen; i++)
-			{
-				newInts[i] = (m_ints[i] << n) | (int)((uint)m_ints[i - 1] >> nm32);
-			}
-			newInts[usedLen] = (int)((uint)m_ints[usedLen - 1] >> nm32);
-
-			return new IntArray(newInts);
-		}
-
-		public void AddShifted(IntArray other, int shift)
-		{
-			int usedLenOther = other.GetUsedLength();
-			int newMinUsedLen = usedLenOther + shift;
-			if (newMinUsedLen > m_ints.Length)
-			{
-				m_ints = resizedInts(newMinUsedLen);
-				//Console.WriteLine("Resize required");
-			}
-
-			for (int i = 0; i < usedLenOther; i++)
-			{
-				m_ints[i + shift] ^= other.m_ints[i];
-			}
-		}
-
-		public int Length
-		{
-			get { return m_ints.Length; }
-		}
-
-		public bool TestBit(int n)
-		{
-			// theInt = n / 32
-			int theInt = n >> 5;
-			// theBit = n % 32
-			int theBit = n & 0x1F;
-			int tester = 1 << theBit;
-			return ((m_ints[theInt] & tester) != 0);
-		}
-
-		public void FlipBit(int n)
-		{
-			// theInt = n / 32
-			int theInt = n >> 5;
-			// theBit = n % 32
-			int theBit = n & 0x1F;
-			int flipper = 1 << theBit;
-			m_ints[theInt] ^= flipper;
-		}
-
-		public void SetBit(int n)
-		{
-			// theInt = n / 32
-			int theInt = n >> 5;
-			// theBit = n % 32
-			int theBit = n & 0x1F;
-			int setter = 1 << theBit;
-			m_ints[theInt] |= setter;
-		}
-
-		public IntArray Multiply(IntArray other, int m)
-		{
-			// Lenght of c is 2m bits rounded up to the next int (32 bit)
-			int t = (m + 31) >> 5;
-			if (m_ints.Length < t)
-			{
-				m_ints = resizedInts(t);
-			}
-
-			IntArray b = new IntArray(other.resizedInts(other.Length + 1));
-			IntArray c = new IntArray((m + m + 31) >> 5);
-			// IntArray c = new IntArray(t + t);
-			int testBit = 1;
-			for (int k = 0; k < 32; k++)
-			{
-				for (int j = 0; j < t; j++)
-				{
-					if ((m_ints[j] & testBit) != 0)
-					{
-						// The kth bit of m_ints[j] is set
-						c.AddShifted(b, j);
-					}
-				}
-				testBit <<= 1;
-				b.ShiftLeft();
-			}
-			return c;
-		}
-
-		// public IntArray multiplyLeftToRight(IntArray other, int m) {
-		// // Lenght of c is 2m bits rounded up to the next int (32 bit)
-		// int t = (m + 31) / 32;
-		// if (m_ints.Length < t) {
-		// m_ints = resizedInts(t);
-		// }
-		//
-		// IntArray b = new IntArray(other.resizedInts(other.getLength() + 1));
-		// IntArray c = new IntArray((m + m + 31) / 32);
-		// // IntArray c = new IntArray(t + t);
-		// int testBit = 1 << 31;
-		// for (int k = 31; k >= 0; k--) {
-		// for (int j = 0; j < t; j++) {
-		// if ((m_ints[j] & testBit) != 0) {
-		// // The kth bit of m_ints[j] is set
-		// c.addShifted(b, j);
-		// }
-		// }
-		// testBit >>>= 1;
-		// if (k > 0) {
-		// c.shiftLeft();
-		// }
-		// }
-		// return c;
-		// }
-
-		// TODO note, redPol.Length must be 3 for TPB and 5 for PPB
-		public void Reduce(int m, int[] redPol)
-		{
-			for (int i = m + m - 2; i >= m; i--)
-			{
-				if (TestBit(i))
-				{
-					int bit = i - m;
-					FlipBit(bit);
-					FlipBit(i);
-					int l = redPol.Length;
-					while (--l >= 0)
-					{
-						FlipBit(redPol[l] + bit);
-					}
-				}
-			}
-			m_ints = resizedInts((m + 31) >> 5);
-		}
-
-		public IntArray Square(int m)
-		{
-			// TODO make the table static readonly
-			int[] table = { 0x0, 0x1, 0x4, 0x5, 0x10, 0x11, 0x14, 0x15, 0x40,
-									0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55 };
-
-			int t = (m + 31) >> 5;
-			if (m_ints.Length < t)
-			{
-				m_ints = resizedInts(t);
-			}
-
-			IntArray c = new IntArray(t + t);
-
-			// TODO twice the same code, put in separate private method
-			for (int i = 0; i < t; i++)
-			{
-				int v0 = 0;
-				for (int j = 0; j < 4; j++)
-				{
-					v0 = (int)((uint) v0 >> 8);
-					int u = (int)((uint)m_ints[i] >> (j * 4)) & 0xF;
-					int w = table[u] << 24;
-					v0 |= w;
-				}
-				c.m_ints[i + i] = v0;
-
-				v0 = 0;
-				int upper = (int)((uint) m_ints[i] >> 16);
-				for (int j = 0; j < 4; j++)
-				{
-					v0 = (int)((uint) v0 >> 8);
-					int u = (int)((uint)upper >> (j * 4)) & 0xF;
-					int w = table[u] << 24;
-					v0 |= w;
-				}
-				c.m_ints[i + i + 1] = v0;
-			}
-			return c;
-		}
-
-		public override bool Equals(object o)
-		{
-			if (!(o is IntArray))
-			{
-				return false;
-			}
-			IntArray other = (IntArray) o;
-			int usedLen = GetUsedLength();
-			if (other.GetUsedLength() != usedLen)
-			{
-				return false;
-			}
-			for (int i = 0; i < usedLen; i++)
-			{
-				if (m_ints[i] != other.m_ints[i])
-				{
-					return false;
-				}
-			}
-			return true;
-		}
-
-		public override int GetHashCode()
-		{
-			int i = GetUsedLength();
-			int hc = i;
-			while (--i >= 0)
-			{
-				hc *= 17;
-				hc ^= m_ints[i];
-			}
-			return hc;
-		}
-
-		internal IntArray Copy()
-		{
-			return new IntArray((int[]) m_ints.Clone());
-		}
-
-		public override string ToString()
-		{
-			int usedLen = GetUsedLength();
-			if (usedLen == 0)
-			{
-				return "0";
-			}
-
-			StringBuilder sb = new StringBuilder(Convert.ToString(m_ints[usedLen - 1], 2));
-			for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--)
-			{
-				string hexString = Convert.ToString(m_ints[iarrJ], 2);
-
-				// Add leading zeroes, except for highest significant int
-				for (int i = hexString.Length; i < 8; i++)
-				{
-					hexString = "0" + hexString;
-				}
-				sb.Append(hexString);
-			}
-			return sb.ToString();
-		}
-	}
-}