diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
index 00f8f399d..04c04a55d 100644
--- a/crypto/src/math/BigInteger.cs
+++ b/crypto/src/math/BigInteger.cs
@@ -9,11 +9,11 @@ using Org.BouncyCastle.Utilities;
namespace Org.BouncyCastle.Math
{
#if !(NETCF_1_0 || NETCF_2_0 || SILVERLIGHT)
- [Serializable]
+ [Serializable]
#endif
- public class BigInteger
- {
- // The first few odd primes
+ public class BigInteger
+ {
+ // The first few odd primes
/*
3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
@@ -40,67 +40,67 @@ namespace Org.BouncyCastle.Math
*/
// Each list has a product < 2^31
- internal 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 },
+ internal 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 },
@@ -122,15 +122,15 @@ namespace Org.BouncyCastle.Math
internal static readonly int[] primeProducts;
- private const long IMASK = 0xFFFFFFFFL;
+ private const long IMASK = 0xFFFFFFFFL;
private const ulong UIMASK = 0xFFFFFFFFUL;
private static readonly int[] ZeroMagnitude = new int[0];
- private static readonly byte[] ZeroEncoding = new byte[0];
+ private static readonly byte[] ZeroEncoding = new byte[0];
private static readonly BigInteger[] SMALL_CONSTANTS = new BigInteger[17];
- public static readonly BigInteger Zero;
- public static readonly BigInteger One;
+ public static readonly BigInteger Zero;
+ public static readonly BigInteger One;
public static readonly BigInteger Two;
public static readonly BigInteger Three;
public static readonly BigInteger Ten;
@@ -156,8 +156,8 @@ namespace Org.BouncyCastle.Math
//};
private readonly static byte[] BitLengthTable =
- {
- 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
+ {
+ 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,
@@ -173,11 +173,11 @@ namespace Org.BouncyCastle.Math
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
- };
+ };
// TODO Parse radix-2 64 bits at a time and radix-8 63 bits at a time
private const int chunk2 = 1, chunk8 = 1, chunk10 = 19, chunk16 = 16;
- private static readonly BigInteger radix2, radix2E, radix8, radix8E, radix10, radix10E, radix16, radix16E;
+ private static readonly BigInteger radix2, radix2E, radix8, radix8E, radix10, radix10E, radix16, radix16E;
private static readonly Random RandomSource = new Random();
@@ -189,11 +189,11 @@ namespace Org.BouncyCastle.Math
private static readonly int[] ExpWindowThresholds = { 7, 25, 81, 241, 673, 1793, 4609, Int32.MaxValue };
private const int BitsPerByte = 8;
- private const int BitsPerInt = 32;
- private const int BytesPerInt = 4;
+ private const int BitsPerInt = 32;
+ private const int BytesPerInt = 4;
- static BigInteger()
- {
+ static BigInteger()
+ {
Zero = new BigInteger(0, ZeroMagnitude, false);
Zero.nBits = 0; Zero.nBitLength = 0;
@@ -215,105 +215,105 @@ namespace Org.BouncyCastle.Math
radix8E = radix8.Pow(chunk8);
radix10 = ValueOf(10);
- radix10E = radix10.Pow(chunk10);
+ radix10E = radix10.Pow(chunk10);
radix16 = ValueOf(16);
radix16E = radix16.Pow(chunk16);
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[] magnitude; // array of ints with [0] being the most significant
+ 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[] magnitude; // array of ints with [0] being the most significant
private int sign; // -1 means -ve; +1 means +ve; 0 means 0;
- private int nBits = -1; // cache BitCount() value
- private int nBitLength = -1; // cache BitLength() value
+ private int nBits = -1; // cache BitCount() value
+ private int nBitLength = -1; // cache BitLength() value
private int mQuote = 0; // -m^(-1) mod b, b = 2^32 (see Montgomery mult.), 0 when uninitialised
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;
+ 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 8:
// Is there anyway to restrict to octal digits?
style = NumberStyles.Integer;
@@ -322,79 +322,79 @@ namespace Org.BouncyCastle.Math
rE = radix8E;
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, 8, 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 >= 2)
- throw new FormatException("Bad character in radix 2 string: " + s);
-
- // TODO Parse 64 bits at a time
- b = b.ShiftLeft(1);
- break;
+ // 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, 8, 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 >= 2)
+ throw new FormatException("Bad character in radix 2 string: " + s);
+
+ // TODO Parse 64 bits at a time
+ b = b.ShiftLeft(1);
+ break;
case 8:
// TODO Need this because we are parsing in radix 10 above
if (i >= 8)
@@ -404,37 +404,37 @@ namespace Org.BouncyCastle.Math
b = b.ShiftLeft(3);
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(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 == 8)
{
// NB: Can't reach here since we are parsing one char at a time
@@ -444,21 +444,21 @@ namespace Org.BouncyCastle.Math
// b = b.ShiftLeft(s.Length * 3);
}
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;
- }
- }
+ {
+ 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)
@@ -471,429 +471,429 @@ namespace Org.BouncyCastle.Math
// 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
+ 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
int xBits = BitsPerByte * nBytes - sizeInBits;
b[0] &= (byte)(255U >> xBits);
this.magnitude = MakeMagnitude(b, 0, b.Length);
- this.sign = this.magnitude.Length < 1 ? 0 : 1;
- }
+ this.sign = this.magnitude.Length < 1 ? 0 : 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 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 nBytes = GetByteLength(bitLength);
+ byte[] b = new byte[nBytes];
- int xBits = BitsPerByte * nBytes - bitLength;
+ int xBits = BitsPerByte * nBytes - bitLength;
byte mask = (byte)(255U >> 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 = 0;
-
- 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 = 0;
-
- 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)
- {
+ {
+ 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 = 0;
+
+ 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 = 0;
+
+ 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 += BitCnt(magnitude[i]);
- }
- nBits = sum;
- }
- }
+ }
+ nBits = sum;
+ }
+ }
- return nBits;
- }
- }
+ return nBits;
+ }
+ }
public static int BitCnt(int i)
{
@@ -908,62 +908,62 @@ namespace Org.BouncyCastle.Math
}
private static int CalcBitLength(int sign, int indx, int[] mag)
- {
- for (;;)
- {
- if (indx >= mag.Length)
- return 0;
+ {
+ 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(sign, 0, magnitude);
- }
-
- return nBitLength;
- }
- }
-
- //
- // BitLen(value) is the number of bits in value.
- //
- private static int BitLen(int w)
- {
+ 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(sign, 0, magnitude);
+ }
+
+ return nBitLength;
+ }
+ }
+
+ //
+ // BitLen(value) is the number of bits in value.
+ //
+ private static int BitLen(int w)
+ {
uint v = (uint)w;
uint t = v >> 24;
if (t != 0)
@@ -975,280 +975,280 @@ namespace Org.BouncyCastle.Math
if (t != 0)
return 8 + BitLengthTable[t];
return BitLengthTable[v];
- }
+ }
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(1, yStart, y);
- int xBitLength = CalcBitLength(1, xStart, x);
- int shift = xBitLength - yBitLength;
-
- int[] iCount;
- int iCountStart = 0;
-
- int[] c;
- int cStart = 0;
- int cBitLength = yBitLength;
- if (shift > 0)
- {
+ {
+ 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(1, yStart, y);
+ int xBitLength = CalcBitLength(1, 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;
+ 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;
return sign == biggie.sign && IsEqualMagnitude(biggie);
- }
+ }
private bool IsEqualMagnitude(BigInteger x)
{
@@ -1264,58 +1264,58 @@ namespace Org.BouncyCastle.Math
}
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
- {
+ 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
{
if (sign == 0)
@@ -1327,69 +1327,69 @@ namespace Org.BouncyCastle.Math
return sign < 0 ? -v : v;
}
- }
+ }
/**
- * 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)
+ * 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);
+ // 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);
@@ -1398,15 +1398,15 @@ namespace Org.BouncyCastle.Math
// Debug.Assert(rbTest == ssTest);
//
// return rbTest;
- }
+ }
- public bool RabinMillerTest(int certainty, Random random)
- {
- Debug.Assert(certainty > 0);
- Debug.Assert(BitLength > 2);
- Debug.Assert(TestBit(0));
+ public bool RabinMillerTest(int certainty, Random random)
+ {
+ Debug.Assert(certainty > 0);
+ Debug.Assert(BitLength > 2);
+ Debug.Assert(TestBit(0));
- // let n = 1 + d . 2^s
+ // let n = 1 + d . 2^s
BigInteger n = this;
int s = n.GetLowestSetBitMaskFirst(-1 << 1);
Debug.Assert(s >= 1);
@@ -1418,8 +1418,8 @@ namespace Org.BouncyCastle.Math
BigInteger minusMontRadix = n.Subtract(montRadix);
do
- {
- BigInteger a;
+ {
+ BigInteger a;
do
{
a = new BigInteger(n.BitLength, random);
@@ -1427,29 +1427,29 @@ namespace Org.BouncyCastle.Math
while (a.sign == 0 || a.CompareTo(n) >= 0
|| a.IsEqualMagnitude(montRadix) || a.IsEqualMagnitude(minusMontRadix));
- BigInteger y = ModPowMonty(a, r, n, false);
+ BigInteger y = ModPowMonty(a, r, n, false);
if (!y.Equals(montRadix))
{
int j = 0;
while (!y.Equals(minusMontRadix))
- {
- if (++j == s)
- return false;
+ {
+ if (++j == s)
+ return false;
- y = ModPowMonty(y, Two, n, false);
+ y = ModPowMonty(y, Two, n, false);
if (y.Equals(montRadix))
- return false;
- }
- }
+ return false;
+ }
+ }
- certainty -= 2; // composites pass for only 1/4 possible 'a'
- }
- while (certainty > 0);
+ certainty -= 2; // composites pass for only 1/4 possible 'a'
+ }
+ while (certainty > 0);
- return true;
- }
+ return true;
+ }
// private bool SolovayStrassenTest(
// int certainty,
@@ -1540,8 +1540,8 @@ namespace Org.BouncyCastle.Math
// return totalS;
// }
- public long LongValue
- {
+ public long LongValue
+ {
get
{
if (sign == 0)
@@ -1560,35 +1560,35 @@ namespace Org.BouncyCastle.Math
}
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
+ 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))
// {
@@ -1635,16 +1635,16 @@ namespace Org.BouncyCastle.Math
BigInteger x;
BigInteger gcd = ExtEuclid(d, m, out x);
- if (!gcd.Equals(One))
- throw new ArithmeticException("Numbers not relatively prime.");
+ if (!gcd.Equals(One))
+ throw new ArithmeticException("Numbers not relatively prime.");
- if (x.sign < 0)
- {
+ if (x.sign < 0)
+ {
x = x.Add(m);
- }
+ }
- return x;
- }
+ return x;
+ }
private BigInteger ModInversePow2(BigInteger m)
{
@@ -1678,11 +1678,11 @@ namespace Org.BouncyCastle.Math
bitsCorrect <<= 1;
}
while (bitsCorrect < pow);
+ }
- if (x.sign < 0)
- {
- x = x.Add(m);
- }
+ if (x.sign < 0)
+ {
+ x = x.Add(m);
}
return x;
@@ -1715,46 +1715,46 @@ namespace Org.BouncyCastle.Math
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)
+ /**
+ * 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;
+ {
+ BigInteger u1 = One;
+ BigInteger u3 = a;
+ BigInteger v1 = Zero;
+ BigInteger v3 = b;
- while (v3.sign > 0)
- {
- BigInteger[] q = u3.DivideAndRemainder(v3);
+ while (v3.sign > 0)
+ {
+ BigInteger[] q = u3.DivideAndRemainder(v3);
- BigInteger tmp = v1.Multiply(q[0]);
- BigInteger tn = u1.Subtract(tmp);
- u1 = v1;
- v1 = tn;
+ BigInteger tmp = v1.Multiply(q[0]);
+ BigInteger tn = u1.Subtract(tmp);
+ u1 = v1;
+ v1 = tn;
- u3 = v3;
- v3 = q[1];
- }
+ u3 = v3;
+ v3 = q[1];
+ }
//if (u1Out != null)
//{
@@ -1772,14 +1772,14 @@ namespace Org.BouncyCastle.Math
// u2Out.magnitude = res.magnitude;
//}
- return u3;
- }
+ return u3;
+ }
- private static void ZeroOut(
- int[] x)
- {
- Array.Clear(x, 0, x.Length);
- }
+ private static void ZeroOut(
+ int[] x)
+ {
+ Array.Clear(x, 0, x.Length);
+ }
public BigInteger ModPow(BigInteger e, BigInteger m)
{
@@ -2084,12 +2084,12 @@ namespace Org.BouncyCastle.Math
}
/**
- * return w with w = x * x - w is assumed to have enough space.
- */
- private static int[] Square(
- int[] w,
- int[] x)
- {
+ * 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...");
@@ -2145,62 +2145,62 @@ namespace Org.BouncyCastle.Math
}
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;
- }
+ * 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;
+ }
/**
- * Calculate mQuote = -m^(-1) mod b with b = 2^32 (32 = word size)
- */
+ * Calculate mQuote = -m^(-1) mod b with b = 2^32 (32 = word size)
+ */
private int GetMQuote()
- {
- if (mQuote != 0)
- {
- return mQuote; // already calculated
- }
+ {
+ if (mQuote != 0)
+ {
+ return mQuote; // already calculated
+ }
Debug.Assert(this.sign > 0);
@@ -2209,7 +2209,7 @@ namespace Org.BouncyCastle.Math
Debug.Assert((d & 1) != 0);
return mQuote = ModInverse32(d);
- }
+ }
private static void MontgomeryReduce(int[] x, int[] m, uint mDash) // mDash = -m^(-1) mod b
{
@@ -2245,21 +2245,21 @@ namespace Org.BouncyCastle.Math
}
/**
- * 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, uint mDash, bool smallMontyModulus)
- // mDash = -m^(-1) mod b
- {
+ * 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, uint mDash, bool smallMontyModulus)
+ // mDash = -m^(-1) mod b
+ {
int n = m.Length;
if (n == 1)
@@ -2269,6 +2269,7 @@ namespace Org.BouncyCastle.Math
}
uint y0 = (uint)y[n - 1];
+ int aMax;
{
ulong xi = (uint)x[n - 1];
@@ -2292,7 +2293,7 @@ namespace Org.BouncyCastle.Math
}
a[1] = (int)carry;
- a[0] = (int)(carry >> 32);
+ aMax = (int)(carry >> 32);
}
for (int i = n - 2; i >= 0; --i)
@@ -2319,11 +2320,13 @@ namespace Org.BouncyCastle.Math
carry = (carry >> 32) + (prod1 >> 32) + (prod2 >> 32);
}
- carry += (uint)a[0];
+ carry += (uint)aMax;
a[1] = (int)carry;
- a[0] = (int)(carry >> 32);
+ aMax = (int)(carry >> 32);
}
+ a[0] = aMax;
+
if (!smallMontyModulus && CompareTo(0, a, 0, m) >= 0)
{
Subtract(0, a, 0, m);
@@ -2345,6 +2348,7 @@ namespace Org.BouncyCastle.Math
}
ulong x0 = (uint)x[n - 1];
+ int aMax;
{
ulong carry = x0 * x0;
@@ -2366,7 +2370,7 @@ namespace Org.BouncyCastle.Math
}
a[1] = (int)carry;
- a[0] = (int)(carry >> 32);
+ aMax = (int)(carry >> 32);
}
for (int i = n - 2; i >= 0; --i)
@@ -2406,11 +2410,13 @@ namespace Org.BouncyCastle.Math
carry = (carry >> 32) + (prod1 >> 31) + (prod2 >> 32);
}
- carry += (uint)a[0];
+ carry += (uint)aMax;
a[1] = (int)carry;
- a[0] = (int)(carry >> 32);
+ aMax = (int)(carry >> 32);
}
+ a[0] = aMax;
+
if (!smallMontyModulus && CompareTo(0, a, 0, m) >= 0)
{
Subtract(0, a, 0, m);
@@ -2420,7 +2426,7 @@ namespace Org.BouncyCastle.Math
}
private static uint MultiplyMontyNIsOne(uint x, uint y, uint m, uint mDash)
- {
+ {
ulong carry = (ulong)x * y;
uint t = (uint)carry * mDash;
ulong um = m;
@@ -2434,28 +2440,28 @@ namespace Org.BouncyCastle.Math
}
Debug.Assert(carry < um);
return (uint)carry;
- }
+ }
public BigInteger Multiply(
- BigInteger val)
- {
+ BigInteger val)
+ {
if (val == this)
return Square();
if ((sign & val.sign) == 0)
- return Zero;
+ 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();
- }
+ {
+ 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();
- }
+ 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 = magnitude.Length + val.magnitude.Length;
int[] res = new int[resLength];
@@ -2464,7 +2470,7 @@ namespace Org.BouncyCastle.Math
int resSign = sign ^ val.sign ^ 1;
return new BigInteger(resSign, res, true);
- }
+ }
public BigInteger Square()
{
@@ -2481,50 +2487,50 @@ namespace Org.BouncyCastle.Math
}
public BigInteger Negate()
- {
- if (sign == 0)
- return this;
+ {
+ if (sign == 0)
+ return this;
- return new BigInteger(-sign, magnitude, false);
- }
+ return new BigInteger(-sign, magnitude, false);
+ }
- public BigInteger NextProbablePrime()
- {
- if (sign < 0)
- throw new ArithmeticException("Cannot be called on value < 0");
+ public BigInteger NextProbablePrime()
+ {
+ if (sign < 0)
+ throw new ArithmeticException("Cannot be called on value < 0");
- if (CompareTo(Two) < 0)
- return Two;
+ if (CompareTo(Two) < 0)
+ return Two;
- BigInteger n = Inc().SetBit(0);
+ BigInteger n = Inc().SetBit(0);
- while (!n.CheckProbablePrime(100, RandomSource))
- {
- n = n.Add(Two);
- }
+ while (!n.CheckProbablePrime(100, RandomSource))
+ {
+ n = n.Add(Two);
+ }
- return n;
- }
+ return n;
+ }
- public BigInteger Not()
- {
- return Inc().Negate();
- }
+ public BigInteger Not()
+ {
+ return Inc().Negate();
+ }
- public BigInteger Pow(int exp)
- {
- if (exp <= 0)
- {
+ public BigInteger Pow(int exp)
+ {
+ if (exp <= 0)
+ {
if (exp < 0)
- throw new ArithmeticException("Negative exponent");
+ throw new ArithmeticException("Negative exponent");
return One;
- }
+ }
if (sign == 0)
- {
- return this;
- }
+ {
+ return this;
+ }
if (QuickPow2Check())
{
@@ -2537,212 +2543,212 @@ namespace Org.BouncyCastle.Math
}
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 static 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(1, yStart, y);
- int xBitLength = CalcBitLength(1, 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);
+ 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 static 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(1, yStart, y);
+ int xBitLength = CalcBitLength(1, 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 excessBits = (numWords << 5) - n;
if (excessBits > 0)
@@ -2751,7 +2757,7 @@ namespace Org.BouncyCastle.Math
}
return result;
- }
+ }
private BigInteger DivideWords(int w)
{
@@ -2776,52 +2782,52 @@ namespace Org.BouncyCastle.Math
}
/**
- * 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;
- }
+ * 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;
+ }
private static int ShiftLeftOneInPlace(int[] x, int carry)
{
@@ -2836,109 +2842,109 @@ namespace Org.BouncyCastle.Math
return carry;
}
- 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 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;
+ int n)
+ {
+ if (n == 0)
+ return this;
- if (n < 0)
- return ShiftLeft(-n);
+ if (n < 0)
+ return ShiftLeft(-n);
- if (n >= BitLength)
- return (this.sign < 0 ? One.Negate() : Zero);
+ if (n >= BitLength)
+ return (this.sign < 0 ? One.Negate() : Zero);
// int[] res = (int[]) this.magnitude.Clone();
//
@@ -2946,213 +2952,213 @@ namespace Org.BouncyCastle.Math
//
// return new BigInteger(this.sign, res, true);
- int resultLength = (BitLength - n + 31) >> 5;
- int[] res = new int[resultLength];
+ int resultLength = (BitLength - n + 31) >> 5;
+ int[] res = new int[resultLength];
- int numInts = n >> 5;
- int numBits = n & 31;
+ 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;
+ 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);
+ 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;
- }
- }
- }
+ if (magPos >= 0)
+ {
+ res[i] |= this.magnitude[magPos] << numBits2;
+ }
+ }
+ }
- Debug.Assert(res[0] != 0);
+ Debug.Assert(res[0] != 0);
- return new BigInteger(this.sign, res, false);
- }
+ 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;
+ {
+ 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);
- }
+ 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)
{
@@ -3297,60 +3303,60 @@ namespace Org.BouncyCastle.Math
}
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);
- }
+ 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);
+ }
public static BigInteger ValueOf(
- long value)
- {
+ long value)
+ {
if (value >= 0 && value < SMALL_CONSTANTS.Length)
{
return SMALL_CONSTANTS[value];
}
return CreateValueOf(value);
- }
+ }
public int GetLowestSetBit()
- {
- if (this.sign == 0)
- return -1;
+ {
+ if (this.sign == 0)
+ return -1;
return GetLowestSetBitMaskFirst(-1);
- }
+ }
private int GetLowestSetBitMaskFirst(int firstWordMask)
{
@@ -3381,195 +3387,195 @@ namespace Org.BouncyCastle.Math
}
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);
- }
- }
+ 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);
+ }
+ }
}
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index 396d42f28..ab98af8f1 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -114,12 +114,13 @@ namespace Org.BouncyCastle.Math.EC
*/
public class FpCurve : ECCurve
{
- private readonly BigInteger q;
+ private readonly BigInteger q, r;
private readonly FpPoint infinity;
public FpCurve(BigInteger q, BigInteger a, BigInteger b)
{
this.q = q;
+ this.r = FpFieldElement.CalculateResidue(q);
this.a = FromBigInteger(a);
this.b = FromBigInteger(b);
this.infinity = new FpPoint(this, null, null);
@@ -142,7 +143,7 @@ namespace Org.BouncyCastle.Math.EC
public override ECFieldElement FromBigInteger(BigInteger x)
{
- return new FpFieldElement(this.q, x);
+ return new FpFieldElement(this.q, this.r, x);
}
public override ECPoint CreatePoint(
@@ -179,7 +180,7 @@ namespace Org.BouncyCastle.Math.EC
if (bit0 != yTilde)
{
// Use the other root
- beta = FromBigInteger(q.Subtract(betaValue));
+ beta = beta.Negate();
}
return new FpPoint(this, x, beta, true);
diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs
index 5235c6c0e..cc5050002 100644
--- a/crypto/src/math/ec/ECFieldElement.cs
+++ b/crypto/src/math/ec/ECFieldElement.cs
@@ -5,365 +5,391 @@ using Org.BouncyCastle.Utilities;
namespace Org.BouncyCastle.Math.EC
{
- public abstract class ECFieldElement
- {
- public abstract BigInteger ToBigInteger();
- public abstract string FieldName { get; }
- public abstract int FieldSize { get; }
- public abstract ECFieldElement Add(ECFieldElement b);
- public abstract ECFieldElement Subtract(ECFieldElement b);
- public abstract ECFieldElement Multiply(ECFieldElement b);
- public abstract ECFieldElement Divide(ECFieldElement b);
- public abstract ECFieldElement Negate();
- public abstract ECFieldElement Square();
- public abstract ECFieldElement Invert();
- public abstract ECFieldElement Sqrt();
-
- public override bool Equals(
- object obj)
- {
- if (obj == this)
- return true;
-
- ECFieldElement other = obj as ECFieldElement;
-
- if (other == null)
- return false;
-
- return Equals(other);
- }
-
- protected bool Equals(
- ECFieldElement other)
- {
- return ToBigInteger().Equals(other.ToBigInteger());
- }
-
- public override int GetHashCode()
- {
- return ToBigInteger().GetHashCode();
- }
-
- public override string ToString()
- {
- return this.ToBigInteger().ToString(2);
- }
- }
-
- public class FpFieldElement
- : ECFieldElement
- {
- private readonly BigInteger q, x;
-
- public FpFieldElement(
- BigInteger q,
- BigInteger x)
- {
- if (x.CompareTo(q) >= 0)
- throw new ArgumentException("x value too large in field element");
-
- this.q = q;
- this.x = x;
- }
-
- public override BigInteger ToBigInteger()
- {
- return x;
- }
-
- /**
- * return the field name for this field.
- *
- * @return the string "Fp".
- */
- public override string FieldName
- {
- get { return "Fp"; }
- }
-
- public override int FieldSize
- {
- get { return q.BitLength; }
- }
-
- public BigInteger Q
- {
- get { return q; }
- }
-
- public override ECFieldElement Add(
- ECFieldElement b)
- {
- return new FpFieldElement(q, x.Add(b.ToBigInteger()).Mod(q));
- }
-
- public override ECFieldElement Subtract(
- ECFieldElement b)
- {
- return new FpFieldElement(q, x.Subtract(b.ToBigInteger()).Mod(q));
- }
-
- public override ECFieldElement Multiply(
- ECFieldElement b)
- {
- return new FpFieldElement(q, x.Multiply(b.ToBigInteger()).Mod(q));
- }
-
- public override ECFieldElement Divide(
- ECFieldElement b)
- {
- return new FpFieldElement(q, x.Multiply(b.ToBigInteger().ModInverse(q)).Mod(q));
- }
-
- public override ECFieldElement Negate()
- {
- return new FpFieldElement(q, x.Negate().Mod(q));
- }
-
- public override ECFieldElement Square()
- {
- return new FpFieldElement(q, x.Multiply(x).Mod(q));
- }
-
- public override ECFieldElement Invert()
- {
- return new FpFieldElement(q, x.ModInverse(q));
- }
-
- // D.1.4 91
- /**
- * return a sqrt root - the routine verifies that the calculation
- * returns the right value - if none exists it returns null.
- */
- public override ECFieldElement Sqrt()
- {
- if (!q.TestBit(0))
- throw Platform.CreateNotImplementedException("even value of q");
-
- // p mod 4 == 3
- if (q.TestBit(1))
- {
- // TODO Can this be optimised (inline the Square?)
- // z = g^(u+1) + p, p = 4u + 3
- ECFieldElement z = new FpFieldElement(q, x.ModPow(q.ShiftRight(2).Add(BigInteger.One), q));
-
- return this.Equals(z.Square()) ? z : null;
- }
-
- // p mod 4 == 1
- BigInteger qMinusOne = q.Subtract(BigInteger.One);
-
- BigInteger legendreExponent = qMinusOne.ShiftRight(1);
- if (!(x.ModPow(legendreExponent, q).Equals(BigInteger.One)))
- return null;
-
- BigInteger u = qMinusOne.ShiftRight(2);
- BigInteger k = u.ShiftLeft(1).Add(BigInteger.One);
-
- BigInteger Q = this.x;
- BigInteger fourQ = Q.ShiftLeft(2).Mod(q);
-
- BigInteger U, V;
- do
- {
- Random rand = new Random();
- BigInteger P;
- do
- {
- P = new BigInteger(q.BitLength, rand);
- }
- while (P.CompareTo(q) >= 0
- || !(P.Multiply(P).Subtract(fourQ).ModPow(legendreExponent, q).Equals(qMinusOne)));
-
- BigInteger[] result = fastLucasSequence(q, P, Q, k);
- U = result[0];
- V = result[1];
-
- if (V.Multiply(V).Mod(q).Equals(fourQ))
- {
- // Integer division by 2, mod q
- if (V.TestBit(0))
- {
- V = V.Add(q);
- }
-
- V = V.ShiftRight(1);
-
- Debug.Assert(V.Multiply(V).Mod(q).Equals(x));
-
- return new FpFieldElement(q, V);
- }
- }
- while (U.Equals(BigInteger.One) || U.Equals(qMinusOne));
-
- return null;
-
-
-// BigInteger qMinusOne = q.Subtract(BigInteger.One);
-//
-// BigInteger legendreExponent = qMinusOne.ShiftRight(1);
-// if (!(x.ModPow(legendreExponent, q).Equals(BigInteger.One)))
-// return null;
-//
-// Random rand = new Random();
-// BigInteger fourX = x.ShiftLeft(2);
-//
-// BigInteger r;
-// do
-// {
-// r = new BigInteger(q.BitLength, rand);
-// }
-// while (r.CompareTo(q) >= 0
-// || !(r.Multiply(r).Subtract(fourX).ModPow(legendreExponent, q).Equals(qMinusOne)));
-//
-// BigInteger n1 = qMinusOne.ShiftRight(2);
-// BigInteger n2 = n1.Add(BigInteger.One);
-//
-// BigInteger wOne = WOne(r, x, q);
-// BigInteger wSum = W(n1, wOne, q).Add(W(n2, wOne, q)).Mod(q);
-// BigInteger twoR = r.ShiftLeft(1);
-//
-// BigInteger root = twoR.ModPow(q.Subtract(BigInteger.Two), q)
-// .Multiply(x).Mod(q)
-// .Multiply(wSum).Mod(q);
-//
-// return new FpFieldElement(q, root);
- }
-
-// private static BigInteger W(BigInteger n, BigInteger wOne, BigInteger p)
-// {
-// if (n.Equals(BigInteger.One))
-// return wOne;
-//
-// bool isEven = !n.TestBit(0);
-// n = n.ShiftRight(1);
-// if (isEven)
-// {
-// BigInteger w = W(n, wOne, p);
-// return w.Multiply(w).Subtract(BigInteger.Two).Mod(p);
-// }
-// BigInteger w1 = W(n.Add(BigInteger.One), wOne, p);
-// BigInteger w2 = W(n, wOne, p);
-// return w1.Multiply(w2).Subtract(wOne).Mod(p);
-// }
-//
-// private BigInteger WOne(BigInteger r, BigInteger x, BigInteger p)
-// {
-// return r.Multiply(r).Multiply(x.ModPow(q.Subtract(BigInteger.Two), q)).Subtract(BigInteger.Two).Mod(p);
-// }
-
- private static BigInteger[] fastLucasSequence(
- BigInteger p,
- BigInteger P,
- BigInteger Q,
- BigInteger k)
- {
- // TODO Research and apply "common-multiplicand multiplication here"
-
- int n = k.BitLength;
- int s = k.GetLowestSetBit();
-
- Debug.Assert(k.TestBit(s));
-
- BigInteger Uh = BigInteger.One;
- BigInteger Vl = BigInteger.Two;
- BigInteger Vh = P;
- BigInteger Ql = BigInteger.One;
- BigInteger Qh = BigInteger.One;
-
- for (int j = n - 1; j >= s + 1; --j)
- {
- Ql = Ql.Multiply(Qh).Mod(p);
-
- if (k.TestBit(j))
- {
- Qh = Ql.Multiply(Q).Mod(p);
- Uh = Uh.Multiply(Vh).Mod(p);
- Vl = Vh.Multiply(Vl).Subtract(P.Multiply(Ql)).Mod(p);
- Vh = Vh.Multiply(Vh).Subtract(Qh.ShiftLeft(1)).Mod(p);
- }
- else
- {
- Qh = Ql;
- Uh = Uh.Multiply(Vl).Subtract(Ql).Mod(p);
- Vh = Vh.Multiply(Vl).Subtract(P.Multiply(Ql)).Mod(p);
- Vl = Vl.Multiply(Vl).Subtract(Ql.ShiftLeft(1)).Mod(p);
- }
- }
-
- Ql = Ql.Multiply(Qh).Mod(p);
- Qh = Ql.Multiply(Q).Mod(p);
- Uh = Uh.Multiply(Vl).Subtract(Ql).Mod(p);
- Vl = Vh.Multiply(Vl).Subtract(P.Multiply(Ql)).Mod(p);
- Ql = Ql.Multiply(Qh).Mod(p);
-
- for (int j = 1; j <= s; ++j)
- {
- Uh = Uh.Multiply(Vl).Mod(p);
- Vl = Vl.Multiply(Vl).Subtract(Ql.ShiftLeft(1)).Mod(p);
- Ql = Ql.Multiply(Ql).Mod(p);
- }
-
- return new BigInteger[]{ Uh, Vl };
- }
-
-// private static BigInteger[] verifyLucasSequence(
-// BigInteger p,
-// BigInteger P,
-// BigInteger Q,
-// BigInteger k)
-// {
-// BigInteger[] actual = fastLucasSequence(p, P, Q, k);
-// BigInteger[] plus1 = fastLucasSequence(p, P, Q, k.Add(BigInteger.One));
-// BigInteger[] plus2 = fastLucasSequence(p, P, Q, k.Add(BigInteger.Two));
-//
-// BigInteger[] check = stepLucasSequence(p, P, Q, actual, plus1);
-//
-// Debug.Assert(check[0].Equals(plus2[0]));
-// Debug.Assert(check[1].Equals(plus2[1]));
-//
-// return actual;
-// }
-//
-// private static BigInteger[] stepLucasSequence(
-// BigInteger p,
-// BigInteger P,
-// BigInteger Q,
-// BigInteger[] backTwo,
-// BigInteger[] backOne)
-// {
-// return new BigInteger[]
-// {
-// P.Multiply(backOne[0]).Subtract(Q.Multiply(backTwo[0])).Mod(p),
-// P.Multiply(backOne[1]).Subtract(Q.Multiply(backTwo[1])).Mod(p)
-// };
-// }
-
- public override bool Equals(
- object obj)
- {
- if (obj == this)
- return true;
-
- FpFieldElement other = obj as FpFieldElement;
-
- if (other == null)
- return false;
-
- return Equals(other);
- }
-
- protected bool Equals(
- FpFieldElement other)
- {
- return q.Equals(other.q) && base.Equals(other);
- }
-
- public override int GetHashCode()
- {
- return q.GetHashCode() ^ base.GetHashCode();
- }
- }
+ public abstract class ECFieldElement
+ {
+ public abstract BigInteger ToBigInteger();
+ public abstract string FieldName { get; }
+ public abstract int FieldSize { get; }
+ public abstract ECFieldElement Add(ECFieldElement b);
+ public abstract ECFieldElement Subtract(ECFieldElement b);
+ public abstract ECFieldElement Multiply(ECFieldElement b);
+ public abstract ECFieldElement Divide(ECFieldElement b);
+ public abstract ECFieldElement Negate();
+ public abstract ECFieldElement Square();
+ public abstract ECFieldElement Invert();
+ public abstract ECFieldElement Sqrt();
+
+ public virtual int BitLength
+ {
+ get { return ToBigInteger().BitLength; }
+ }
+
+ public virtual bool IsOne
+ {
+ get { return BitLength == 1; }
+ }
+
+ public virtual bool IsZero
+ {
+ get { return 0 == ToBigInteger().SignValue; }
+ }
+
+ public virtual bool TestBitZero()
+ {
+ return ToBigInteger().TestBit(0);
+ }
+
+ public override bool Equals(
+ object obj)
+ {
+ if (obj == this)
+ return true;
+
+ ECFieldElement other = obj as ECFieldElement;
+
+ if (other == null)
+ return false;
+
+ return Equals(other);
+ }
+
+ public virtual bool Equals(
+ ECFieldElement other)
+ {
+ return ToBigInteger().Equals(other.ToBigInteger());
+ }
+
+ public override int GetHashCode()
+ {
+ return ToBigInteger().GetHashCode();
+ }
+
+ public override string ToString()
+ {
+ return this.ToBigInteger().ToString(16);
+ }
+
+ public virtual byte[] GetEncoded()
+ {
+ return BigIntegers.AsUnsignedByteArray((FieldSize + 7) / 8, ToBigInteger());
+ }
+ }
+
+ public class FpFieldElement
+ : ECFieldElement
+ {
+ private readonly BigInteger q, r, x;
+
+ internal static BigInteger CalculateResidue(BigInteger p)
+ {
+ int bitLength = p.BitLength;
+ if (bitLength > 128)
+ {
+ BigInteger firstWord = p.ShiftRight(bitLength - 64);
+ if (firstWord.LongValue == -1L)
+ {
+ return BigInteger.One.ShiftLeft(bitLength).Subtract(p);
+ }
+ }
+ return null;
+ }
+
+ [Obsolete("Use ECCurve.FromBigInteger to construct field elements")]
+ public FpFieldElement(BigInteger q, BigInteger x)
+ : this(q, CalculateResidue(q), x)
+ {
+ }
+
+ internal FpFieldElement(BigInteger q, BigInteger r, BigInteger x)
+ {
+ if (x == null || x.SignValue < 0 || x.CompareTo(q) >= 0)
+ throw new ArgumentException("value invalid in Fp field element", "x");
+
+ this.q = q;
+ this.r = r;
+ this.x = x;
+ }
+
+ public override BigInteger ToBigInteger()
+ {
+ return x;
+ }
+
+ /**
+ * return the field name for this field.
+ *
+ * @return the string "Fp".
+ */
+ public override string FieldName
+ {
+ get { return "Fp"; }
+ }
+
+ public override int FieldSize
+ {
+ get { return q.BitLength; }
+ }
+
+ public BigInteger Q
+ {
+ get { return q; }
+ }
+
+ public override ECFieldElement Add(
+ ECFieldElement b)
+ {
+ return new FpFieldElement(q, r, ModAdd(x, b.ToBigInteger()));
+ }
+
+ 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);
+ }
+
+ public override ECFieldElement Multiply(
+ ECFieldElement b)
+ {
+ return new FpFieldElement(q, r, ModMult(x, b.ToBigInteger()));
+ }
+
+ public override ECFieldElement Divide(
+ ECFieldElement b)
+ {
+ return new FpFieldElement(q, r, ModMult(x, b.ToBigInteger().ModInverse(q)));
+ }
+
+ public override ECFieldElement Negate()
+ {
+ return x.SignValue == 0 ? this : new FpFieldElement(q, r, q.Subtract(x));
+ }
+
+ public override ECFieldElement Square()
+ {
+ return new FpFieldElement(q, r, ModMult(x, x));
+ }
+
+ public override ECFieldElement Invert()
+ {
+ // TODO Modular inversion can be faster for a (Generalized) Mersenne Prime.
+ return new FpFieldElement(q, r, x.ModInverse(q));
+ }
+
+ // D.1.4 91
+ /**
+ * return a sqrt root - the routine verifies that the calculation
+ * returns the right value - if none exists it returns null.
+ */
+ public override ECFieldElement Sqrt()
+ {
+ if (!q.TestBit(0))
+ throw Platform.CreateNotImplementedException("even value of q");
+
+ // p mod 4 == 3
+ if (q.TestBit(1))
+ {
+ // TODO Can this be optimised (inline the Square?)
+ // z = g^(u+1) + p, p = 4u + 3
+ ECFieldElement z = new FpFieldElement(q, r, x.ModPow(q.ShiftRight(2).Add(BigInteger.One), q));
+
+ return z.Square().Equals(this) ? z : null;
+ }
+
+ // p mod 4 == 1
+ BigInteger qMinusOne = q.Subtract(BigInteger.One);
+
+ BigInteger legendreExponent = qMinusOne.ShiftRight(1);
+ if (!(x.ModPow(legendreExponent, q).Equals(BigInteger.One)))
+ return null;
+
+ BigInteger u = qMinusOne.ShiftRight(2);
+ BigInteger k = u.ShiftLeft(1).Add(BigInteger.One);
+
+ BigInteger X = this.x;
+ BigInteger fourX = ModDouble(ModDouble(X)); ;
+
+ BigInteger U, V;
+ Random rand = new Random();
+ do
+ {
+ BigInteger P;
+ do
+ {
+ P = new BigInteger(q.BitLength, rand);
+ }
+ while (P.CompareTo(q) >= 0
+ || !(ModMult(P, P).Subtract(fourX).ModPow(legendreExponent, q).Equals(qMinusOne)));
+
+ BigInteger[] result = LucasSequence(P, X, k);
+ U = result[0];
+ V = result[1];
+
+ if (ModMult(V, V).Equals(fourX))
+ {
+ // Integer division by 2, mod q
+ if (V.TestBit(0))
+ {
+ V = V.Add(q);
+ }
+
+ V = V.ShiftRight(1);
+
+ Debug.Assert(ModMult(V, V).Equals(X));
+
+ return new FpFieldElement(q, r, V);
+ }
+ }
+ while (U.Equals(BigInteger.One) || U.Equals(qMinusOne));
+
+ return null;
+ }
+
+ private BigInteger[] LucasSequence(
+ BigInteger P,
+ BigInteger Q,
+ BigInteger k)
+ {
+ // TODO Research and apply "common-multiplicand multiplication here"
+
+ int n = k.BitLength;
+ int s = k.GetLowestSetBit();
+
+ Debug.Assert(k.TestBit(s));
+
+ BigInteger Uh = BigInteger.One;
+ BigInteger Vl = BigInteger.Two;
+ BigInteger Vh = P;
+ BigInteger Ql = BigInteger.One;
+ BigInteger Qh = BigInteger.One;
+
+ for (int j = n - 1; j >= s + 1; --j)
+ {
+ Ql = ModMult(Ql, Qh);
+
+ if (k.TestBit(j))
+ {
+ Qh = ModMult(Ql, Q);
+ Uh = ModMult(Uh, Vh);
+ Vl = ModReduce(Vh.Multiply(Vl).Subtract(P.Multiply(Ql)));
+ Vh = ModReduce(Vh.Multiply(Vh).Subtract(Qh.ShiftLeft(1)));
+ }
+ else
+ {
+ Qh = Ql;
+ Uh = ModReduce(Uh.Multiply(Vl).Subtract(Ql));
+ Vh = ModReduce(Vh.Multiply(Vl).Subtract(P.Multiply(Ql)));
+ Vl = ModReduce(Vl.Multiply(Vl).Subtract(Ql.ShiftLeft(1)));
+ }
+ }
+
+ Ql = ModMult(Ql, Qh);
+ Qh = ModMult(Ql, Q);
+ Uh = ModReduce(Uh.Multiply(Vl).Subtract(Ql));
+ Vl = ModReduce(Vh.Multiply(Vl).Subtract(P.Multiply(Ql)));
+ Ql = ModMult(Ql, Qh);
+
+ for (int j = 1; j <= s; ++j)
+ {
+ Uh = ModMult(Uh, Vl);
+ Vl = ModReduce(Vl.Multiply(Vl).Subtract(Ql.ShiftLeft(1)));
+ Ql = ModMult(Ql, Ql);
+ }
+
+ return new BigInteger[] { Uh, Vl };
+ }
+
+ protected virtual BigInteger ModAdd(BigInteger x1, BigInteger x2)
+ {
+ BigInteger x3 = x1.Add(x2);
+ if (x3.CompareTo(q) >= 0)
+ {
+ x3 = x3.Subtract(q);
+ }
+ return x3;
+ }
+
+ protected virtual BigInteger ModDouble(BigInteger x)
+ {
+ BigInteger _2x = x.ShiftLeft(1);
+ if (_2x.CompareTo(q) >= 0)
+ {
+ _2x = _2x.Subtract(q);
+ }
+ return _2x;
+ }
+
+ protected virtual BigInteger ModMult(BigInteger x1, BigInteger x2)
+ {
+ return ModReduce(x1.Multiply(x2));
+ }
+
+ protected virtual BigInteger ModReduce(BigInteger x)
+ {
+ if (r != null)
+ {
+ bool negative = x.SignValue < 0;
+ if (negative)
+ {
+ x = x.Abs();
+ }
+ int qLen = q.BitLength;
+ while (x.BitLength > (qLen + 1))
+ {
+ BigInteger u = x.ShiftRight(qLen);
+ BigInteger v = x.Subtract(u.ShiftLeft(qLen));
+ if (!r.Equals(BigInteger.One))
+ {
+ u = u.Multiply(r);
+ }
+ x = u.Add(v);
+ }
+ while (x.CompareTo(q) >= 0)
+ {
+ x = x.Subtract(q);
+ }
+ if (negative && x.SignValue != 0)
+ {
+ x = q.Subtract(x);
+ }
+ }
+ else
+ {
+ x = x.Mod(q);
+ }
+ return x;
+ }
+
+ public override bool Equals(
+ object obj)
+ {
+ if (obj == this)
+ return true;
+
+ FpFieldElement other = obj as FpFieldElement;
+
+ if (other == null)
+ return false;
+
+ return Equals(other);
+ }
+
+ public virtual bool Equals(
+ FpFieldElement other)
+ {
+ return q.Equals(other.q) && base.Equals(other);
+ }
+
+ public override int GetHashCode()
+ {
+ return q.GetHashCode() ^ base.GetHashCode();
+ }
+ }
// /**
// * Class representing the Elements of the finite field
@@ -815,439 +841,439 @@ namespace Org.BouncyCastle.Math.EC
// }
// }
- /**
- * Class representing the Elements of the finite field
- * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
- * representation. Both trinomial (Tpb) and pentanomial (Ppb) polynomial
- * basis representations are supported. Gaussian normal basis (GNB)
- * representation is not supported.
- */
- public class F2mFieldElement
- : ECFieldElement
- {
- /**
- * Indicates gaussian normal basis representation (GNB). Number chosen
- * according to X9.62. GNB is not implemented at present.
- */
- public const int Gnb = 1;
-
- /**
- * Indicates trinomial basis representation (Tpb). Number chosen
- * according to X9.62.
- */
- public const int Tpb = 2;
-
- /**
- * Indicates pentanomial basis representation (Ppb). Number chosen
- * according to X9.62.
- */
- public const int Ppb = 3;
-
- /**
- * Tpb or Ppb.
- */
- private int representation;
-
- /**
- * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
- */
- private int m;
-
- /**
- * Tpb: The integer <code>k</code> where <code>x<sup>m</sup> +
- * x<sup>k</sup> + 1</code> represents the reduction polynomial
- * <code>f(z)</code>.<br/>
- * Ppb: The integer <code>k1</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.<br/>
- */
- private int k1;
-
- /**
- * Tpb: Always set to <code>0</code><br/>
- * Ppb: The integer <code>k2</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.<br/>
- */
- private int k2;
-
- /**
- * Tpb: Always set to <code>0</code><br/>
- * Ppb: The integer <code>k3</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.<br/>
- */
- private int k3;
-
- /**
- * The <code>IntArray</code> holding the bits.
- */
- private IntArray x;
-
- /**
- * The number of <code>int</code>s required to hold <code>m</code> bits.
- */
- private readonly int t;
-
- /**
- * Constructor for Ppb.
- * @param m The exponent <code>m</code> of
- * <code>F<sub>2<sup>m</sup></sub></code>.
- * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.
- * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.
- * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.
- * @param x The BigInteger representing the value of the field element.
- */
- public F2mFieldElement(
- int m,
- int k1,
- int k2,
- int k3,
- BigInteger x)
- {
- // t = m / 32 rounded up to the next integer
- this.t = (m + 31) >> 5;
- this.x = new IntArray(x, t);
-
- if ((k2 == 0) && (k3 == 0))
- {
- this.representation = Tpb;
- }
- else
- {
- if (k2 >= k3)
- throw new ArgumentException("k2 must be smaller than k3");
- if (k2 <= 0)
- throw new ArgumentException("k2 must be larger than 0");
-
- this.representation = Ppb;
- }
-
- if (x.SignValue < 0)
- throw new ArgumentException("x value cannot be negative");
-
- this.m = m;
- this.k1 = k1;
- this.k2 = k2;
- this.k3 = k3;
- }
-
- /**
- * Constructor for Tpb.
- * @param m The exponent <code>m</code> of
- * <code>F<sub>2<sup>m</sup></sub></code>.
- * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
- * x<sup>k</sup> + 1</code> represents the reduction
- * polynomial <code>f(z)</code>.
- * @param x The BigInteger representing the value of the field element.
- */
- public F2mFieldElement(
- int m,
- int k,
- BigInteger x)
- : this(m, k, 0, 0, x)
- {
- // Set k1 to k, and set k2 and k3 to 0
- }
-
- private F2mFieldElement(int m, int k1, int k2, int k3, IntArray x)
- {
- t = (m + 31) >> 5;
- this.x = x;
- this.m = m;
- this.k1 = k1;
- this.k2 = k2;
- this.k3 = k3;
-
- if ((k2 == 0) && (k3 == 0))
- {
- this.representation = Tpb;
- }
- else
- {
- this.representation = Ppb;
- }
- }
-
- public override BigInteger ToBigInteger()
- {
- return x.ToBigInteger();
- }
-
- public override string FieldName
- {
- get { return "F2m"; }
- }
-
- public override int FieldSize
- {
- get { return m; }
- }
-
- /**
- * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
- * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
- * (having the same representation).
- * @param a field element.
- * @param b field element to be compared.
- * @throws ArgumentException if <code>a</code> and <code>b</code>
- * are not elements of the same field
- * <code>F<sub>2<sup>m</sup></sub></code> (having the same
- * representation).
- */
- public static void CheckFieldElements(
- ECFieldElement a,
- ECFieldElement b)
- {
- if (!(a is F2mFieldElement) || !(b is F2mFieldElement))
- {
- throw new ArgumentException("Field elements are not "
- + "both instances of F2mFieldElement");
- }
-
- F2mFieldElement aF2m = (F2mFieldElement)a;
- F2mFieldElement bF2m = (F2mFieldElement)b;
-
- if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
- || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3))
- {
- throw new ArgumentException("Field elements are not "
- + "elements of the same field F2m");
- }
-
- if (aF2m.representation != bF2m.representation)
- {
- // Should never occur
- throw new ArgumentException(
- "One of the field "
- + "elements are not elements has incorrect representation");
- }
- }
-
- public override ECFieldElement Add(
- ECFieldElement b)
- {
- // No check performed here for performance reasons. Instead the
- // elements involved are checked in ECPoint.F2m
- // checkFieldElements(this, b);
- IntArray iarrClone = (IntArray) this.x.Copy();
- F2mFieldElement bF2m = (F2mFieldElement) b;
- iarrClone.AddShifted(bF2m.x, 0);
- return new F2mFieldElement(m, k1, k2, k3, iarrClone);
- }
-
- public override ECFieldElement Subtract(
- ECFieldElement b)
- {
- // Addition and subtraction are the same in F2m
- return Add(b);
- }
-
- public override ECFieldElement Multiply(
- ECFieldElement b)
- {
- // Right-to-left comb multiplication in the IntArray
- // Input: Binary polynomials a(z) and b(z) of degree at most m-1
- // Output: c(z) = a(z) * b(z) mod f(z)
-
- // No check performed here for performance reasons. Instead the
- // elements involved are checked in ECPoint.F2m
- // checkFieldElements(this, b);
- F2mFieldElement bF2m = (F2mFieldElement) b;
- IntArray mult = x.Multiply(bF2m.x, m);
- mult.Reduce(m, new int[]{k1, k2, k3});
- return new F2mFieldElement(m, k1, k2, k3, mult);
- }
-
- public override ECFieldElement Divide(
- ECFieldElement b)
- {
- // There may be more efficient implementations
- ECFieldElement bInv = b.Invert();
- return Multiply(bInv);
- }
-
- public override ECFieldElement Negate()
- {
- // -x == x holds for all x in F2m
- return this;
- }
-
- public override ECFieldElement Square()
- {
- IntArray squared = x.Square(m);
- squared.Reduce(m, new int[]{k1, k2, k3});
- return new F2mFieldElement(m, k1, k2, k3, squared);
- }
-
- public override ECFieldElement Invert()
- {
- // Inversion in F2m using the extended Euclidean algorithm
- // Input: A nonzero polynomial a(z) of degree at most m-1
- // Output: a(z)^(-1) mod f(z)
-
- // u(z) := a(z)
+ /**
+ * Class representing the Elements of the finite field
+ * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB)
+ * representation. Both trinomial (Tpb) and pentanomial (Ppb) polynomial
+ * basis representations are supported. Gaussian normal basis (GNB)
+ * representation is not supported.
+ */
+ public class F2mFieldElement
+ : ECFieldElement
+ {
+ /**
+ * Indicates gaussian normal basis representation (GNB). Number chosen
+ * according to X9.62. GNB is not implemented at present.
+ */
+ public const int Gnb = 1;
+
+ /**
+ * Indicates trinomial basis representation (Tpb). Number chosen
+ * according to X9.62.
+ */
+ public const int Tpb = 2;
+
+ /**
+ * Indicates pentanomial basis representation (Ppb). Number chosen
+ * according to X9.62.
+ */
+ public const int Ppb = 3;
+
+ /**
+ * Tpb or Ppb.
+ */
+ private int representation;
+
+ /**
+ * The exponent <code>m</code> of <code>F<sub>2<sup>m</sup></sub></code>.
+ */
+ private int m;
+
+ /**
+ * Tpb: The integer <code>k</code> where <code>x<sup>m</sup> +
+ * x<sup>k</sup> + 1</code> represents the reduction polynomial
+ * <code>f(z)</code>.<br/>
+ * Ppb: The integer <code>k1</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.<br/>
+ */
+ private int k1;
+
+ /**
+ * Tpb: Always set to <code>0</code><br/>
+ * Ppb: The integer <code>k2</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.<br/>
+ */
+ private int k2;
+
+ /**
+ * Tpb: Always set to <code>0</code><br/>
+ * Ppb: The integer <code>k3</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.<br/>
+ */
+ private int k3;
+
+ /**
+ * The <code>IntArray</code> holding the bits.
+ */
+ private IntArray x;
+
+ /**
+ * The number of <code>int</code>s required to hold <code>m</code> bits.
+ */
+ private readonly int t;
+
+ /**
+ * Constructor for Ppb.
+ * @param m The exponent <code>m</code> of
+ * <code>F<sub>2<sup>m</sup></sub></code>.
+ * @param k1 The integer <code>k1</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.
+ * @param k2 The integer <code>k2</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.
+ * @param k3 The integer <code>k3</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.
+ * @param x The BigInteger representing the value of the field element.
+ */
+ public F2mFieldElement(
+ int m,
+ int k1,
+ int k2,
+ int k3,
+ BigInteger x)
+ {
+ // t = m / 32 rounded up to the next integer
+ this.t = (m + 31) >> 5;
+ this.x = new IntArray(x, t);
+
+ if ((k2 == 0) && (k3 == 0))
+ {
+ this.representation = Tpb;
+ }
+ else
+ {
+ if (k2 >= k3)
+ throw new ArgumentException("k2 must be smaller than k3");
+ if (k2 <= 0)
+ throw new ArgumentException("k2 must be larger than 0");
+
+ this.representation = Ppb;
+ }
+
+ if (x.SignValue < 0)
+ throw new ArgumentException("x value cannot be negative");
+
+ this.m = m;
+ this.k1 = k1;
+ this.k2 = k2;
+ this.k3 = k3;
+ }
+
+ /**
+ * Constructor for Tpb.
+ * @param m The exponent <code>m</code> of
+ * <code>F<sub>2<sup>m</sup></sub></code>.
+ * @param k The integer <code>k</code> where <code>x<sup>m</sup> +
+ * x<sup>k</sup> + 1</code> represents the reduction
+ * polynomial <code>f(z)</code>.
+ * @param x The BigInteger representing the value of the field element.
+ */
+ public F2mFieldElement(
+ int m,
+ int k,
+ BigInteger x)
+ : this(m, k, 0, 0, x)
+ {
+ // Set k1 to k, and set k2 and k3 to 0
+ }
+
+ private F2mFieldElement(int m, int k1, int k2, int k3, IntArray x)
+ {
+ t = (m + 31) >> 5;
+ this.x = x;
+ this.m = m;
+ this.k1 = k1;
+ this.k2 = k2;
+ this.k3 = k3;
+
+ if ((k2 == 0) && (k3 == 0))
+ {
+ this.representation = Tpb;
+ }
+ else
+ {
+ this.representation = Ppb;
+ }
+ }
+
+ public override BigInteger ToBigInteger()
+ {
+ return x.ToBigInteger();
+ }
+
+ public override string FieldName
+ {
+ get { return "F2m"; }
+ }
+
+ public override int FieldSize
+ {
+ get { return m; }
+ }
+
+ /**
+ * Checks, if the ECFieldElements <code>a</code> and <code>b</code>
+ * are elements of the same field <code>F<sub>2<sup>m</sup></sub></code>
+ * (having the same representation).
+ * @param a field element.
+ * @param b field element to be compared.
+ * @throws ArgumentException if <code>a</code> and <code>b</code>
+ * are not elements of the same field
+ * <code>F<sub>2<sup>m</sup></sub></code> (having the same
+ * representation).
+ */
+ public static void CheckFieldElements(
+ ECFieldElement a,
+ ECFieldElement b)
+ {
+ if (!(a is F2mFieldElement) || !(b is F2mFieldElement))
+ {
+ throw new ArgumentException("Field elements are not "
+ + "both instances of F2mFieldElement");
+ }
+
+ F2mFieldElement aF2m = (F2mFieldElement)a;
+ F2mFieldElement bF2m = (F2mFieldElement)b;
+
+ if ((aF2m.m != bF2m.m) || (aF2m.k1 != bF2m.k1)
+ || (aF2m.k2 != bF2m.k2) || (aF2m.k3 != bF2m.k3))
+ {
+ throw new ArgumentException("Field elements are not "
+ + "elements of the same field F2m");
+ }
+
+ if (aF2m.representation != bF2m.representation)
+ {
+ // Should never occur
+ throw new ArgumentException(
+ "One of the field "
+ + "elements are not elements has incorrect representation");
+ }
+ }
+
+ public override ECFieldElement Add(
+ ECFieldElement b)
+ {
+ // No check performed here for performance reasons. Instead the
+ // elements involved are checked in ECPoint.F2m
+ // checkFieldElements(this, b);
+ IntArray iarrClone = (IntArray) this.x.Copy();
+ F2mFieldElement bF2m = (F2mFieldElement) b;
+ iarrClone.AddShifted(bF2m.x, 0);
+ return new F2mFieldElement(m, k1, k2, k3, iarrClone);
+ }
+
+ public override ECFieldElement Subtract(
+ ECFieldElement b)
+ {
+ // Addition and subtraction are the same in F2m
+ return Add(b);
+ }
+
+ public override ECFieldElement Multiply(
+ ECFieldElement b)
+ {
+ // Right-to-left comb multiplication in the IntArray
+ // Input: Binary polynomials a(z) and b(z) of degree at most m-1
+ // Output: c(z) = a(z) * b(z) mod f(z)
+
+ // No check performed here for performance reasons. Instead the
+ // elements involved are checked in ECPoint.F2m
+ // checkFieldElements(this, b);
+ F2mFieldElement bF2m = (F2mFieldElement) b;
+ IntArray mult = x.Multiply(bF2m.x, m);
+ mult.Reduce(m, new int[]{k1, k2, k3});
+ return new F2mFieldElement(m, k1, k2, k3, mult);
+ }
+
+ public override ECFieldElement Divide(
+ ECFieldElement b)
+ {
+ // There may be more efficient implementations
+ ECFieldElement bInv = b.Invert();
+ return Multiply(bInv);
+ }
+
+ public override ECFieldElement Negate()
+ {
+ // -x == x holds for all x in F2m
+ return this;
+ }
+
+ public override ECFieldElement Square()
+ {
+ IntArray squared = x.Square(m);
+ squared.Reduce(m, new int[]{k1, k2, k3});
+ return new F2mFieldElement(m, k1, k2, k3, squared);
+ }
+
+ public override ECFieldElement Invert()
+ {
+ // Inversion in F2m using the extended Euclidean algorithm
+ // Input: A nonzero polynomial a(z) of degree at most m-1
+ // Output: a(z)^(-1) mod f(z)
+
+ // u(z) := a(z)
IntArray uz = (IntArray)this.x.Copy();
- // v(z) := f(z)
- IntArray vz = new IntArray(t);
- vz.SetBit(m);
- vz.SetBit(0);
- vz.SetBit(this.k1);
- if (this.representation == Ppb)
- {
- vz.SetBit(this.k2);
- vz.SetBit(this.k3);
- }
-
- // g1(z) := 1, g2(z) := 0
- IntArray g1z = new IntArray(t);
- g1z.SetBit(0);
- IntArray g2z = new IntArray(t);
-
- // while u != 0
- while (uz.GetUsedLength() > 0)
+ // v(z) := f(z)
+ IntArray vz = new IntArray(t);
+ vz.SetBit(m);
+ vz.SetBit(0);
+ vz.SetBit(this.k1);
+ if (this.representation == Ppb)
+ {
+ vz.SetBit(this.k2);
+ vz.SetBit(this.k3);
+ }
+
+ // g1(z) := 1, g2(z) := 0
+ IntArray g1z = new IntArray(t);
+ g1z.SetBit(0);
+ IntArray g2z = new IntArray(t);
+
+ // while u != 0
+ while (uz.GetUsedLength() > 0)
// while (uz.bitLength() > 1)
- {
- // j := deg(u(z)) - deg(v(z))
- int j = uz.BitLength - vz.BitLength;
+ {
+ // j := deg(u(z)) - deg(v(z))
+ int j = uz.BitLength - vz.BitLength;
- // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
- if (j < 0)
- {
+ // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j
+ if (j < 0)
+ {
IntArray uzCopy = uz;
- uz = vz;
- vz = uzCopy;
+ uz = vz;
+ vz = uzCopy;
IntArray g1zCopy = g1z;
- g1z = g2z;
- g2z = g1zCopy;
-
- j = -j;
- }
-
- // u(z) := u(z) + z^j * v(z)
- // Note, that no reduction modulo f(z) is required, because
- // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
- // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
- // = deg(u(z))
- // uz = uz.xor(vz.ShiftLeft(j));
- // jInt = n / 32
- int jInt = j >> 5;
- // jInt = n % 32
- int jBit = j & 0x1F;
- IntArray vzShift = vz.ShiftLeft(jBit);
- uz.AddShifted(vzShift, jInt);
-
- // g1(z) := g1(z) + z^j * g2(z)
+ g1z = g2z;
+ g2z = g1zCopy;
+
+ j = -j;
+ }
+
+ // u(z) := u(z) + z^j * v(z)
+ // Note, that no reduction modulo f(z) is required, because
+ // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z)))
+ // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z))
+ // = deg(u(z))
+ // uz = uz.xor(vz.ShiftLeft(j));
+ // jInt = n / 32
+ int jInt = j >> 5;
+ // jInt = n % 32
+ int jBit = j & 0x1F;
+ IntArray vzShift = vz.ShiftLeft(jBit);
+ uz.AddShifted(vzShift, jInt);
+
+ // g1(z) := g1(z) + z^j * g2(z)
// g1z = g1z.xor(g2z.ShiftLeft(j));
- IntArray g2zShift = g2z.ShiftLeft(jBit);
- g1z.AddShifted(g2zShift, jInt);
- }
- return new F2mFieldElement(this.m, this.k1, this.k2, this.k3, g2z);
- }
-
- public override ECFieldElement Sqrt()
- {
- throw new ArithmeticException("Not implemented");
- }
-
- /**
- * @return the representation of the field
- * <code>F<sub>2<sup>m</sup></sub></code>, either of
- * {@link F2mFieldElement.Tpb} (trinomial
- * basis representation) or
- * {@link F2mFieldElement.Ppb} (pentanomial
- * basis representation).
- */
- public int Representation
- {
- get { return this.representation; }
- }
-
- /**
- * @return the degree <code>m</code> of the reduction polynomial
- * <code>f(z)</code>.
- */
- public int M
- {
- get { return this.m; }
- }
-
- /**
- * @return Tpb: The integer <code>k</code> where <code>x<sup>m</sup> +
- * x<sup>k</sup> + 1</code> represents the reduction polynomial
- * <code>f(z)</code>.<br/>
- * Ppb: The integer <code>k1</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.<br/>
- */
- public int K1
- {
- get { return this.k1; }
- }
-
- /**
- * @return Tpb: Always returns <code>0</code><br/>
- * Ppb: The integer <code>k2</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.<br/>
- */
- public int K2
- {
- get { return this.k2; }
- }
-
- /**
- * @return Tpb: Always set to <code>0</code><br/>
- * Ppb: The integer <code>k3</code> where <code>x<sup>m</sup> +
- * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
- * represents the reduction polynomial <code>f(z)</code>.<br/>
- */
- public int K3
- {
- get { return this.k3; }
- }
-
- public override bool Equals(
- object obj)
- {
- if (obj == this)
- return true;
-
- F2mFieldElement other = obj as F2mFieldElement;
-
- if (other == null)
- return false;
-
- return Equals(other);
- }
-
- protected bool Equals(
- F2mFieldElement other)
- {
- return m == other.m
- && k1 == other.k1
- && k2 == other.k2
- && k3 == other.k3
- && representation == other.representation
- && base.Equals(other);
- }
-
- public override int GetHashCode()
- {
- return m.GetHashCode()
- ^ k1.GetHashCode()
- ^ k2.GetHashCode()
- ^ k3.GetHashCode()
- ^ representation.GetHashCode()
- ^ base.GetHashCode();
- }
- }
+ IntArray g2zShift = g2z.ShiftLeft(jBit);
+ g1z.AddShifted(g2zShift, jInt);
+ }
+ return new F2mFieldElement(this.m, this.k1, this.k2, this.k3, g2z);
+ }
+
+ public override ECFieldElement Sqrt()
+ {
+ throw new ArithmeticException("Not implemented");
+ }
+
+ /**
+ * @return the representation of the field
+ * <code>F<sub>2<sup>m</sup></sub></code>, either of
+ * {@link F2mFieldElement.Tpb} (trinomial
+ * basis representation) or
+ * {@link F2mFieldElement.Ppb} (pentanomial
+ * basis representation).
+ */
+ public int Representation
+ {
+ get { return this.representation; }
+ }
+
+ /**
+ * @return the degree <code>m</code> of the reduction polynomial
+ * <code>f(z)</code>.
+ */
+ public int M
+ {
+ get { return this.m; }
+ }
+
+ /**
+ * @return Tpb: The integer <code>k</code> where <code>x<sup>m</sup> +
+ * x<sup>k</sup> + 1</code> represents the reduction polynomial
+ * <code>f(z)</code>.<br/>
+ * Ppb: The integer <code>k1</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.<br/>
+ */
+ public int K1
+ {
+ get { return this.k1; }
+ }
+
+ /**
+ * @return Tpb: Always returns <code>0</code><br/>
+ * Ppb: The integer <code>k2</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.<br/>
+ */
+ public int K2
+ {
+ get { return this.k2; }
+ }
+
+ /**
+ * @return Tpb: Always set to <code>0</code><br/>
+ * Ppb: The integer <code>k3</code> where <code>x<sup>m</sup> +
+ * x<sup>k3</sup> + x<sup>k2</sup> + x<sup>k1</sup> + 1</code>
+ * represents the reduction polynomial <code>f(z)</code>.<br/>
+ */
+ public int K3
+ {
+ get { return this.k3; }
+ }
+
+ public override bool Equals(
+ object obj)
+ {
+ if (obj == this)
+ return true;
+
+ F2mFieldElement other = obj as F2mFieldElement;
+
+ if (other == null)
+ return false;
+
+ return Equals(other);
+ }
+
+ public virtual bool Equals(
+ F2mFieldElement other)
+ {
+ return m == other.m
+ && k1 == other.k1
+ && k2 == other.k2
+ && k3 == other.k3
+ && representation == other.representation
+ && base.Equals(other);
+ }
+
+ public override int GetHashCode()
+ {
+ return m.GetHashCode()
+ ^ k1.GetHashCode()
+ ^ k2.GetHashCode()
+ ^ k3.GetHashCode()
+ ^ representation.GetHashCode()
+ ^ base.GetHashCode();
+ }
+ }
}
diff --git a/crypto/src/math/field/FiniteFields.cs b/crypto/src/math/field/FiniteFields.cs
new file mode 100644
index 000000000..7b84569fe
--- /dev/null
+++ b/crypto/src/math/field/FiniteFields.cs
@@ -0,0 +1,54 @@
+using System;
+
+namespace Org.BouncyCastle.Math.Field
+{
+ public abstract class FiniteFields
+ {
+ internal static readonly IFiniteField GF_2 = new PrimeField(BigInteger.ValueOf(2));
+ internal static readonly IFiniteField GF_3 = new PrimeField(BigInteger.ValueOf(3));
+
+ public static IPolynomialExtensionField GetBinaryExtensionField(int[] exponents)
+ {
+ if (exponents[0] != 0)
+ {
+ throw new ArgumentException("Irreducible polynomials in GF(2) must have constant term", "exponents");
+ }
+ for (int i = 1; i < exponents.Length; ++i)
+ {
+ if (exponents[i] <= exponents[i - 1])
+ {
+ throw new ArgumentException("Polynomial exponents must be montonically increasing", "exponents");
+ }
+ }
+
+ return new GenericPolynomialExtensionField(GF_2, new GF2Polynomial(exponents));
+ }
+
+ // public static IPolynomialExtensionField GetTernaryExtensionField(Term[] terms)
+ // {
+ // return new GenericPolynomialExtensionField(GF_3, new GF3Polynomial(terms));
+ // }
+
+ public static IFiniteField GetPrimeField(BigInteger characteristic)
+ {
+ int bitLength = characteristic.BitLength;
+ if (characteristic.SignValue <= 0 || bitLength < 2)
+ {
+ throw new ArgumentException("Must be >= 2", "characteristic");
+ }
+
+ if (bitLength < 3)
+ {
+ switch (characteristic.IntValue)
+ {
+ case 2:
+ return GF_2;
+ case 3:
+ return GF_3;
+ }
+ }
+
+ return new PrimeField(characteristic);
+ }
+ }
+}
diff --git a/crypto/src/math/field/GF2Polynomial.cs b/crypto/src/math/field/GF2Polynomial.cs
new file mode 100644
index 000000000..c062d508a
--- /dev/null
+++ b/crypto/src/math/field/GF2Polynomial.cs
@@ -0,0 +1,46 @@
+using System;
+
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Math.Field
+{
+ internal class GF2Polynomial
+ : IPolynomial
+ {
+ protected readonly int[] exponents;
+
+ internal GF2Polynomial(int[] exponents)
+ {
+ this.exponents = Arrays.Clone(exponents);
+ }
+
+ public virtual int Degree
+ {
+ get { return exponents[exponents.Length - 1]; }
+ }
+
+ public virtual int[] GetExponentsPresent()
+ {
+ return Arrays.Clone(exponents);
+ }
+
+ public override bool Equals(object obj)
+ {
+ if (this == obj)
+ {
+ return true;
+ }
+ GF2Polynomial other = obj as GF2Polynomial;
+ if (null == other)
+ {
+ return false;
+ }
+ return Arrays.AreEqual(exponents, other.exponents);
+ }
+
+ public override int GetHashCode()
+ {
+ return Arrays.GetHashCode(exponents);
+ }
+ }
+}
diff --git a/crypto/src/math/field/GenericPolynomialExtensionField.cs b/crypto/src/math/field/GenericPolynomialExtensionField.cs
new file mode 100644
index 000000000..13ef57165
--- /dev/null
+++ b/crypto/src/math/field/GenericPolynomialExtensionField.cs
@@ -0,0 +1,63 @@
+using System;
+
+using Org.BouncyCastle.Utilities;
+
+namespace Org.BouncyCastle.Math.Field
+{
+ internal class GenericPolynomialExtensionField
+ : IPolynomialExtensionField
+ {
+ protected readonly IFiniteField subfield;
+ protected readonly IPolynomial minimalPolynomial;
+
+ internal GenericPolynomialExtensionField(IFiniteField subfield, IPolynomial polynomial)
+ {
+ this.subfield = subfield;
+ this.minimalPolynomial = polynomial;
+ }
+
+ public virtual BigInteger Characteristic
+ {
+ get { return subfield.Characteristic; }
+ }
+
+ public virtual int Dimension
+ {
+ get { return subfield.Dimension * minimalPolynomial.Degree; }
+ }
+
+ public virtual IFiniteField Subfield
+ {
+ get { return subfield; }
+ }
+
+ public virtual int Degree
+ {
+ get { return minimalPolynomial.Degree; }
+ }
+
+ public virtual IPolynomial MinimalPolynomial
+ {
+ get { return minimalPolynomial; }
+ }
+
+ public override bool Equals(object obj)
+ {
+ if (this == obj)
+ {
+ return true;
+ }
+ GenericPolynomialExtensionField other = obj as GenericPolynomialExtensionField;
+ if (null == other)
+ {
+ return false;
+ }
+ return subfield.Equals(other.subfield) && minimalPolynomial.Equals(other.minimalPolynomial);
+ }
+
+ public override int GetHashCode()
+ {
+ return subfield.GetHashCode() ^ Integers.RotateLeft(minimalPolynomial.GetHashCode(), 16);
+ }
+ }
+}
diff --git a/crypto/src/math/field/IExtensionField.cs b/crypto/src/math/field/IExtensionField.cs
new file mode 100644
index 000000000..17f45c153
--- /dev/null
+++ b/crypto/src/math/field/IExtensionField.cs
@@ -0,0 +1,12 @@
+using System;
+
+namespace Org.BouncyCastle.Math.Field
+{
+ public interface IExtensionField
+ : IFiniteField
+ {
+ IFiniteField Subfield { get; }
+
+ int Degree { get; }
+ }
+}
diff --git a/crypto/src/math/field/IFiniteField.cs b/crypto/src/math/field/IFiniteField.cs
new file mode 100644
index 000000000..b618be74b
--- /dev/null
+++ b/crypto/src/math/field/IFiniteField.cs
@@ -0,0 +1,11 @@
+using System;
+
+namespace Org.BouncyCastle.Math.Field
+{
+ public interface IFiniteField
+ {
+ BigInteger Characteristic { get; }
+
+ int Dimension { get; }
+ }
+}
diff --git a/crypto/src/math/field/IPolynomial.cs b/crypto/src/math/field/IPolynomial.cs
new file mode 100644
index 000000000..ad6dfb662
--- /dev/null
+++ b/crypto/src/math/field/IPolynomial.cs
@@ -0,0 +1,15 @@
+using System;
+
+namespace Org.BouncyCastle.Math.Field
+{
+ public interface IPolynomial
+ {
+ int Degree { get; }
+
+ //BigInteger[] GetCoefficients();
+
+ int[] GetExponentsPresent();
+
+ //Term[] GetNonZeroTerms();
+ }
+}
diff --git a/crypto/src/math/field/IPolynomialExtensionField.cs b/crypto/src/math/field/IPolynomialExtensionField.cs
new file mode 100644
index 000000000..3818c1855
--- /dev/null
+++ b/crypto/src/math/field/IPolynomialExtensionField.cs
@@ -0,0 +1,10 @@
+using System;
+
+namespace Org.BouncyCastle.Math.Field
+{
+ public interface IPolynomialExtensionField
+ : IExtensionField
+ {
+ IPolynomial MinimalPolynomial { get; }
+ }
+}
diff --git a/crypto/src/math/field/PrimeField.cs b/crypto/src/math/field/PrimeField.cs
new file mode 100644
index 000000000..f6ba629d5
--- /dev/null
+++ b/crypto/src/math/field/PrimeField.cs
@@ -0,0 +1,44 @@
+using System;
+
+namespace Org.BouncyCastle.Math.Field
+{
+ internal class PrimeField
+ : IFiniteField
+ {
+ protected readonly BigInteger characteristic;
+
+ internal PrimeField(BigInteger characteristic)
+ {
+ this.characteristic = characteristic;
+ }
+
+ public virtual BigInteger Characteristic
+ {
+ get { return characteristic; }
+ }
+
+ public virtual int Dimension
+ {
+ get { return 1; }
+ }
+
+ public override bool Equals(object obj)
+ {
+ if (this == obj)
+ {
+ return true;
+ }
+ PrimeField other = obj as PrimeField;
+ if (null == other)
+ {
+ return false;
+ }
+ return characteristic.Equals(other.characteristic);
+ }
+
+ public override int GetHashCode()
+ {
+ return characteristic.GetHashCode();
+ }
+ }
+}
|
