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;
+ }
+ }
+ }
+}
|
