summary refs log tree commit diff
path: root/crypto/src/math
diff options
context:
space:
mode:
Diffstat (limited to 'crypto/src/math')
-rw-r--r--crypto/src/math/ec/ECFieldElement.cs36
-rw-r--r--crypto/src/math/ec/IntArray.cs485
-rw-r--r--crypto/src/math/ec/Mod.cs115
-rw-r--r--crypto/src/math/ec/Nat.cs495
4 files changed, 636 insertions, 495 deletions
diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs
index f31732aaf..93f63a435 100644
--- a/crypto/src/math/ec/ECFieldElement.cs
+++ b/crypto/src/math/ec/ECFieldElement.cs
@@ -138,13 +138,7 @@ namespace Org.BouncyCastle.Math.EC
         public override ECFieldElement Subtract(
             ECFieldElement b)
         {
-            BigInteger x2 = b.ToBigInteger();
-            BigInteger x3 = x.Subtract(x2);
-            if (x3.SignValue < 0)
-            {
-                x3 = x3.Add(q);
-            }
-            return new FpFieldElement(q, r, x3);
+            return new FpFieldElement(q, r, ModSubtract(x, b.ToBigInteger()));
         }
 
         public override ECFieldElement Multiply(
@@ -156,7 +150,7 @@ namespace Org.BouncyCastle.Math.EC
         public override ECFieldElement Divide(
             ECFieldElement b)
         {
-            return new FpFieldElement(q, r, ModMult(x, b.ToBigInteger().ModInverse(q)));
+            return new FpFieldElement(q, r, ModMult(x, ModInverse(b.ToBigInteger())));
         }
 
         public override ECFieldElement Negate()
@@ -172,7 +166,7 @@ namespace Org.BouncyCastle.Math.EC
         public override ECFieldElement Invert()
         {
             // TODO Modular inversion can be faster for a (Generalized) Mersenne Prime.
-            return new FpFieldElement(q, r, x.ModInverse(q));
+            return new FpFieldElement(q, r, ModInverse(x));
         }
 
         // D.1.4 91
@@ -318,6 +312,18 @@ namespace Org.BouncyCastle.Math.EC
             return _2x;
         }
 
+        protected virtual BigInteger ModInverse(BigInteger x)
+        {
+            // Our BigInteger.ModInverse performance is quite poor, so use the new Nat/Mod classes here
+            //return x.ModInverse(q);
+            int len = (FieldSize + 31) >> 5;
+            uint[] p = Nat.FromBigInteger(len, q);
+            uint[] n = Nat.FromBigInteger(len, x);
+            uint[] z = Nat.Create(len);
+            Mod.Invert(p, n, z);
+            return Nat.ToBigInteger(len, z);
+        }
+
         protected virtual BigInteger ModMult(BigInteger x1, BigInteger x2)
         {
             return ModReduce(x1.Multiply(x2));
@@ -359,6 +365,16 @@ namespace Org.BouncyCastle.Math.EC
             return x;
         }
 
+        protected virtual BigInteger ModSubtract(BigInteger x1, BigInteger x2)
+        {
+            BigInteger x3 = x1.Subtract(x2);
+            if (x3.SignValue < 0)
+            {
+                x3 = x3.Add(q);
+            }
+            return x3;
+        }
+
         public override bool Equals(
             object obj)
         {
@@ -1067,7 +1083,7 @@ namespace Org.BouncyCastle.Math.EC
         public override ECFieldElement Multiply(
             ECFieldElement b)
         {
-            // Right-to-left comb multiplication in the IntArray
+            // Right-to-left comb multiplication in the LongArray
             // Input: Binary polynomials a(z) and b(z) of degree at most m-1
             // Output: c(z) = a(z) * b(z) mod f(z)
 
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();
-		}
-	}
-}
diff --git a/crypto/src/math/ec/Mod.cs b/crypto/src/math/ec/Mod.cs
new file mode 100644
index 000000000..57f75ed12
--- /dev/null
+++ b/crypto/src/math/ec/Mod.cs
@@ -0,0 +1,115 @@
+using System;
+
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Math.EC
+{
+    internal abstract class Mod
+    {
+        public static void Invert(uint[] p, uint[] x, uint[] z)
+        {
+            int len = p.Length;
+            if (Nat.IsOne(len, x))
+            {
+                Array.Copy(x, 0, z, 0, len);
+                return;
+            }
+
+            uint[] u = Nat.Copy(len, x);
+            uint[] a = Nat.Create(len);
+            a[0] = 1;
+
+            if ((u[0] & 1) == 0)
+            {
+                InversionStep(p, u, a);
+            }
+            if (Nat.IsOne(len, u))
+            {
+                Array.Copy(a, 0, z, 0, len);
+                return;
+            }
+
+            uint[] v = Nat.Copy(len, p);
+            uint[] b = Nat.Create(len);
+
+            for (;;)
+            {
+                if (Nat.Gte(len, u, v))
+                {
+                    Subtract(p, a, b, a);
+                    Nat.Sub(len, u, v, u);
+                    if ((u[0] & 1) == 0)
+                    {
+                        InversionStep(p, u, a);
+                    }
+                    if (Nat.IsOne(len, u))
+                    {
+                        Array.Copy(a, 0, z, 0, len);
+                        return;
+                    }
+                }
+                else
+                {
+                    Subtract(p, b, a, b);
+                    Nat.Sub(len, v, u, v);
+                    if ((v[0] & 1) == 0)
+                    {
+                        InversionStep(p, v, b);
+                    }
+                    if (Nat.IsOne(len, v))
+                    {
+                        Array.Copy(b, 0, z, 0, len);
+                        return;
+                    }
+                }
+            }
+        }
+
+        public static void Subtract(uint[] p, uint[] x, uint[] y, uint[] z)
+        {
+            int len = p.Length;
+            int c = Nat.Sub(len, x, y, z);
+            if (c != 0)
+            {
+                Nat.Add(len, z, p, z);
+            }
+        }
+
+        private static void InversionStep(uint[] p, uint[] u, uint[] x)
+        {
+            int len = p.Length;
+            int count = 0;
+            while (u[0] == 0)
+            {
+                Nat.ShiftDownWord(u, len, 0);
+                count += 32;
+            }
+
+            int zeroes = GetTrailingZeroes(u[0]);
+            if (zeroes > 0)
+            {
+                Nat.ShiftDownBits(u, len, zeroes, 0);
+                count += zeroes;
+            }
+
+            for (int i = 0; i < count; ++i)
+            {
+                uint c = (x[0] & 1) == 0 ? 0 : Nat.Add(len, x, p, x);
+                Nat.ShiftDownBit(x, len, c);
+            }
+        }
+
+        private static int GetTrailingZeroes(uint x)
+        {
+    //        assert x != 0;
+
+            int count = 0;
+            while ((x & 1) == 0)
+            {
+                x >>= 1;
+                ++count;
+            }
+            return count;
+        }
+    }
+}
diff --git a/crypto/src/math/ec/Nat.cs b/crypto/src/math/ec/Nat.cs
new file mode 100644
index 000000000..cc8996dfc
--- /dev/null
+++ b/crypto/src/math/ec/Nat.cs
@@ -0,0 +1,495 @@
+using System;
+
+using Org.BouncyCastle.Crypto.Utilities;
+using Org.BouncyCastle.Math;
+
+namespace Org.BouncyCastle.Math.EC
+{
+    internal abstract class Nat
+    {
+        public static uint Add(int len, uint[] x, uint[] y, uint[] z)
+        {
+            ulong c = 0;
+            for (int i = 0; i < len; ++i)
+            {
+                c += (ulong)x[i] + y[i];
+                z[i] = (uint)c;
+                c >>= 32;
+            }
+            return (uint)c;
+        }
+
+        public static uint AddBothTo(int len, uint[] x, uint[] y, uint[] z)
+        {
+            ulong c = 0;
+            for (int i = 0; i < len; ++i)
+            {
+                c += (ulong)x[i] + y[i] + z[i];
+                z[i] = (uint)c;
+                c >>= 32;
+            }
+            return (uint)c;
+        }
+
+        public static uint AddDWord(int len, ulong x, uint[] z, int zOff)
+        {
+            // assert zOff < (len - 2);
+            ulong c = x;
+            c += (ulong)z[zOff + 0];
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            c += (ulong)z[zOff + 1];
+            z[zOff + 1] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(len, z, zOff + 2);
+        }
+
+        public static uint AddExt(int len, uint[] xx, uint[] yy, uint[] zz)
+        {
+            int extLen = len << 1;
+            ulong c = 0;
+            for (int i = 0; i < extLen; ++i)
+            {
+                c += (ulong)xx[i] + yy[i];
+                zz[i] = (uint)c;
+                c >>= 32;
+            }
+            return (uint)c;
+        }
+
+        public static uint AddToExt(int len, uint[] x, int xOff, uint[] zz, int zzOff)
+        {
+            // assert zzOff <= len;
+            ulong c = 0;
+            for (int i = 0; i < len; ++i)
+            {
+                c += (ulong)x[xOff + i] + zz[zzOff + i];
+                zz[zzOff + i] = (uint)c;
+                c >>= 32;
+            }
+            return (uint)c;
+        }
+
+        public static uint AddWordExt(int len, uint x, uint[] zz, int zzOff)
+        {
+            // assert zzOff < ((len << 1) - 1);
+            ulong c = (ulong)x + zz[zzOff];
+            zz[zzOff] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : IncExt(len, zz, zzOff + 1);
+        }
+
+        public static uint[] Copy(int len, uint[] x)
+        {
+            uint[] z = new uint[len];
+            Array.Copy(x, 0, z, 0, len);
+            return z;
+        }
+
+        public static uint[] Create(int len)
+        {
+            return new uint[len];
+        }
+
+        public static uint[] CreateExt(int len)
+        {
+            int extLen = len << 1;
+            return new uint[extLen];
+        }
+
+        public static int Dec(int len, uint[] z, int zOff)
+        {
+            // assert zOff < len;
+            int i = zOff;
+            do
+            {
+                if (--z[i] != uint.MaxValue)
+                {
+                    return 0;
+                }
+            }
+            while (++i < len);
+            return -1;
+        }
+
+        public static uint[] FromBigInteger(int len, BigInteger x)
+        {
+            if (x.SignValue < 0 || x.BitLength > (len << 5))
+                throw new ArgumentException();
+
+            uint[] z = Create(len);
+            int i = 0;
+            while (x.SignValue != 0)
+            {
+                z[i++] = (uint)x.IntValue;
+                x = x.ShiftRight(32);
+            }
+            return z;
+        }
+
+        public static uint GetBit(uint[] x, int bit)
+        {
+            if (bit == 0)
+            {
+                return x[0] & 1;
+            }
+            uint w = (uint)bit >> 5;
+            int b = bit & 31;
+            return (x[w] >> b) & 1;
+        }
+
+        public static bool Gte(int len, uint[] x, uint[] y)
+        {
+            for (int i = len - 1; i >= 0; --i)
+            {
+                uint x_i = x[i], y_i = y[i];
+                if (x_i < y_i)
+                    return false;
+                if (x_i > y_i)
+                    return true;
+            }
+            return false;
+        }
+
+        public static bool GteExt(int len, uint[] xx, uint[] yy)
+        {
+            int extLen = len << 1;
+            for (int i = extLen - 1; i >= 0; --i)
+            {
+                uint xx_i = xx[i], yy_i = yy[i];
+                if (xx_i < yy_i)
+                    return false;
+                if (xx_i > yy_i)
+                    return true;
+            }
+            return false;
+        }
+
+        public static uint Inc(int len, uint[] z, int zOff)
+        {
+            // assert zOff < len;
+            for (int i = zOff; i < len; ++i)
+            {
+                if (++z[i] != 0)
+                {
+                    return 0;
+                }
+            }
+            return 1;
+        }
+
+        public static uint IncExt(int len, uint[] zz, int zzOff)
+        {
+            int extLen = len;
+            // assert zzOff < extLen;
+            for (int i = zzOff; i < extLen; ++i)
+            {
+                if (++zz[i] != 0)
+                {
+                    return 0;
+                }
+            }
+            return 1;
+        }
+
+        public static bool IsOne(int len, uint[] x)
+        {
+            if (x[0] != 1)
+            {
+                return false;
+            }
+            for (int i = 1; i < len; ++i)
+            {
+                if (x[i] != 0)
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        public static bool IsZero(int len, uint[] x)
+        {
+            if (x[0] != 0)
+            {
+                return false;
+            }
+            for (int i = 1; i < len; ++i)
+            {
+                if (x[i] != 0)
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        public static bool isZeroExt(int len, uint[] xx)
+        {
+            if (xx[0] != 0)
+            {
+                return false;
+            }
+            int extLen = len << 1;
+            for (int i = 1; i < extLen; ++i)
+            {
+                if (xx[i] != 0)
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        public static void Mul(int len, uint[] x, uint[] y, uint[] zz)
+        {
+            zz[len] = (uint)MulWordExt(len, x[0], y, zz, 0);
+
+            for (int i = 1; i < len; ++i)
+            {
+                zz[i + len] = (uint)MulWordAddExt(len, x[i], y, 0, zz, i);
+            }
+        }
+
+        public static uint MulWordAddExt(int len, uint x, uint[] yy, int yyOff, uint[] zz, int zzOff)
+        {
+            // assert yyOff <= len;
+            // assert zzOff <= len;
+            ulong c = 0, xVal = (ulong)x;
+            int i = 0;
+            do
+            {
+                c += xVal * yy[yyOff + i] + zz[zzOff + i];
+                zz[zzOff + i] = (uint)c;
+                c >>= 32;
+            }
+            while (++i < len);
+            return (uint)c;
+        }
+
+        public static uint SquareWordAddExt(int len, uint[] x, int xPos, uint[] zz)
+        {
+            // assert xPos > 0 && xPos < len;
+            ulong c = 0, xVal = (ulong)x[xPos];
+            int i = 0;
+            do
+            {
+                c += xVal * x[i] + zz[xPos + i];
+                zz[xPos + i] = (uint)c;
+                c >>= 32;
+            }
+            while (++i < xPos);
+            return (uint)c;
+        }
+
+        public static uint MulWordDwordAdd(int len, uint x, ulong y, uint[] z, int zOff)
+        {
+            // assert zOff < (len - 3);
+            ulong c = 0, xVal = (ulong)x;
+            c += xVal * (uint)y + z[zOff + 0];
+            z[zOff + 0] = (uint)c;
+            c >>= 32;
+            c += xVal * (y >> 32) + z[zOff + 1];
+            z[zOff + 1] = (uint)c;
+            c >>= 32;
+            c += (ulong)z[zOff + 2];
+            z[zOff + 2] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Inc(len, z, zOff + 3);
+        }
+
+        public static uint MulWordExt(int len, uint x, uint[] y, uint[] zz, int zzOff)
+        {
+            // assert zzOff <= len;
+            ulong c = 0, xVal = (ulong)x;
+            int i = 0;
+            do
+            {
+                c += xVal * y[i];
+                zz[zzOff + i] = (uint)c;
+                c >>= 32;
+            }
+            while (++i < len);
+            return (uint)c;
+        }
+
+        public static uint ShiftDownBit(uint[] x, int xLen, uint c)
+        {
+            int i = xLen;
+            while (--i >= 0)
+            {
+                uint next = x[i];
+                x[i] = (next >> 1) | (c << 31);
+                c = next;
+            }
+            return c << 31;
+        }
+
+        public static uint ShiftDownBit(int len, uint[] x, uint c, uint[] z)
+        {
+            int i = len;
+            while (--i >= 0)
+            {
+                uint next = x[i];
+                z[i] = (next >> 1) | (c << 31);
+                c = next;
+            }
+            return c << 31;
+        }
+
+        public static uint ShiftDownBits(uint[] x, int xLen, int bits, uint c)
+        {
+            //assert bits > 0 && bits < 32;
+            int i = xLen;
+            while (--i >= 0)
+            {
+                uint next = x[i];
+                x[i] = (next >> bits) | (c << -bits);
+                c = next;
+            }
+            return c << 32 - bits;
+        }
+
+        public static uint ShiftDownWord(uint[] x, int xLen, uint c)
+        {
+            int i = xLen;
+            while (--i >= 0)
+            {
+                uint next = x[i];
+                x[i] = c;
+                c = next;
+            }
+            return c;
+        }
+
+        public static uint ShiftUpBit(uint[] x, int xLen, uint c)
+        {
+            for (int i = 0; i < xLen; ++i)
+            {
+                uint next = x[i];
+                x[i] = (next << 1) | (c >> 31);
+                c = next;
+            }
+            return c >> 31;
+        }
+
+        public static uint ShiftUpBit(int len, uint[] x, uint c, uint[] z)
+        {
+            for (int i = 0; i < len; ++i)
+            {
+                uint next = x[i];
+                z[i] = (next << 1) | (c >> 31);
+                c = next;
+            }
+            return c >> 31;
+        }
+
+        public static void Square(int len, uint[] x, uint[] zz)
+        {
+            int extLen = len << 1;
+            uint c = 0;
+            int j = len, k = extLen;
+            do
+            {
+                ulong xVal = (ulong)x[--j];
+                ulong p = xVal * xVal;
+                zz[--k] = (c << 31) | (uint)(p >> 33);
+                zz[--k] = (uint)(p >> 1);
+                c = (uint)p;
+            }
+            while (j > 0);
+
+            for (int i = 1; i < len; ++i)
+            {
+                c = SquareWordAddExt(len, x, i, zz);
+                AddWordExt(len, c, zz, i << 1);
+            }
+
+            ShiftUpBit(zz, extLen, x[0] << 31);
+        }
+
+        public static int Sub(int len, uint[] x, uint[] y, uint[] z)
+        {
+            long c = 0;
+            for (int i = 0; i < len; ++i)
+            {
+                c += (long)x[i] - y[i];
+                z[i] = (uint)c;
+                c >>= 32;
+            }
+            return (int)c;
+        }
+
+        public static int SubBothFrom(int len, uint[] x, uint[] y, uint[] z)
+        {
+            long c = 0;
+            for (int i = 0; i < len; ++i)
+            {
+                c += (long)z[i] - x[i] - y[i];
+                z[i] = (uint)c;
+                c >>= 32;
+            }
+            return (int)c;
+        }
+
+        public static int SubDWord(int len, ulong x, uint[] z)
+        {
+            long c = -(long)x;
+            c += (long)z[0];
+            z[0] = (uint)c;
+            c >>= 32;
+            c += (long)z[1];
+            z[1] = (uint)c;
+            c >>= 32;
+            return c == 0 ? 0 : Dec(len, z, 2);
+        }
+
+        public static int SubExt(int len, uint[] xx, uint[] yy, uint[] zz)
+        {
+            int extLen = len << 1;
+            long c = 0;
+            for (int i = 0; i < extLen; ++i)
+            {
+                c += (long)xx[i] - yy[i];
+                zz[i] = (uint)c;
+                c >>= 32;
+            }
+            return (int)c;
+        }
+
+        public static uint SubFromExt(int len, uint[] x, int xOff, uint[] zz, int zzOff)
+        {
+            // assert zzOff <= len;
+            ulong c = 0;
+            for (int i = 0; i < len; ++i)
+            {
+                c += (ulong)zz[zzOff + i] - x[xOff + i];
+                zz[zzOff + i] = (uint)c;
+                c >>= 32;
+            }
+            return (uint)c;
+        }
+
+        public static BigInteger ToBigInteger(int len, uint[] x)
+        {
+            byte[] bs = new byte[len << 2];
+            for (int i = 0; i < len; ++i)
+            {
+                uint x_i = x[i];
+                if (x_i != 0)
+                {
+                    Pack.UInt32_To_BE(x_i, bs, (len - 1 - i) << 2);
+                }
+            }
+            return new BigInteger(1, bs);
+        }
+
+        public static void Zero(int len, uint[] z)
+        {
+            for (int i = 0; i < len; ++i)
+            {
+                z[i] = 0;
+            }
+        }
+    }
+}
generated by cgit-pink 1.4.1 (git 2.36.1) at 2024-09-20 11:46:58 +0000