// BigInteger.cs - Big Integer implementation
//
// Authors:
+// Ben Maurer
// Chew Keong TAN
-// Sebastien Pouliot (spouliot@motus.com)
+// Sebastien Pouliot <sebastien@ximian.com>
+// Pieter Philippaerts <Pieter@mentalis.org>
//
-// Copyright (c) 2002 Chew Keong TAN
-// All rights reserved.
-//
-// Modifications from original
-// - Removed all reference to Random class (not secure enough)
-// - Moved all static Test function into BigIntegerTest.cs (for NUnit)
-//
-
-//************************************************************************************
-// BigInteger Class Version 1.03
+// Copyright (c) 2003 Ben Maurer
+// All rights reserved
//
// Copyright (c) 2002 Chew Keong TAN
// All rights reserved.
//
-// Permission is hereby granted, free of charge, to any person obtaining a
-// copy of this software and associated documentation files (the
+// Copyright (C) 2004 Novell, Inc (http://www.novell.com)
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
// "Software"), to deal in the Software without restriction, including
// without limitation the rights to use, copy, modify, merge, publish,
-// distribute, and/or sell copies of the Software, and to permit persons
-// to whom the Software is furnished to do so, provided that the above
-// copyright notice(s) and this permission notice appear in all copies of
-// the Software and that both the above copyright notice(s) and this
-// permission notice appear in supporting documentation.
-//
-// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
-// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
-// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
-// OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
-// HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
-// INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
-// FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
-// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
-// WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
-//
-//
-// Disclaimer
-// ----------
-// Although reasonable care has been taken to ensure the correctness of this
-// implementation, this code should never be used in any application without
-// proper verification and testing. I disclaim all liability and responsibility
-// to any person or entity with respect to any loss or damage caused, or alleged
-// to be caused, directly or indirectly, by the use of this BigInteger class.
-//
-// Comments, bugs and suggestions to
-// (http://www.codeproject.com/csharp/biginteger.asp)
-//
-//
-// Overloaded Operators +, -, *, /, %, >>, <<, ==, !=, >, <, >=, <=, &, |, ^, ++, --, ~
-//
-// Features
-// --------
-// 1) Arithmetic operations involving large signed integers (2's complement).
-// 2) Primality test using Fermat little theorm, Rabin Miller's method,
-// Solovay Strassen's method and Lucas strong pseudoprime.
-// 3) Modulo exponential with Barrett's reduction.
-// 4) Inverse modulo.
-// 5) Pseudo prime generation.
-// 6) Co-prime generation.
-//
-//
-// Known Problem
-// -------------
-// This pseudoprime passes my implementation of
-// primality test but failed in JDK's isProbablePrime test.
-//
-// byte[] pseudoPrime1 = { (byte)0x00,
-// (byte)0x85, (byte)0x84, (byte)0x64, (byte)0xFD, (byte)0x70, (byte)0x6A,
-// (byte)0x9F, (byte)0xF0, (byte)0x94, (byte)0x0C, (byte)0x3E, (byte)0x2C,
-// (byte)0x74, (byte)0x34, (byte)0x05, (byte)0xC9, (byte)0x55, (byte)0xB3,
-// (byte)0x85, (byte)0x32, (byte)0x98, (byte)0x71, (byte)0xF9, (byte)0x41,
-// (byte)0x21, (byte)0x5F, (byte)0x02, (byte)0x9E, (byte)0xEA, (byte)0x56,
-// (byte)0x8D, (byte)0x8C, (byte)0x44, (byte)0xCC, (byte)0xEE, (byte)0xEE,
-// (byte)0x3D, (byte)0x2C, (byte)0x9D, (byte)0x2C, (byte)0x12, (byte)0x41,
-// (byte)0x1E, (byte)0xF1, (byte)0xC5, (byte)0x32, (byte)0xC3, (byte)0xAA,
-// (byte)0x31, (byte)0x4A, (byte)0x52, (byte)0xD8, (byte)0xE8, (byte)0xAF,
-// (byte)0x42, (byte)0xF4, (byte)0x72, (byte)0xA1, (byte)0x2A, (byte)0x0D,
-// (byte)0x97, (byte)0xB1, (byte)0x31, (byte)0xB3,
-// };
-//
-//
-// Change Log
-// ----------
-// 1) September 23, 2002 (Version 1.03)
-// - Fixed operator- to give correct data length.
-// - Added Lucas sequence generation.
-// - Added Strong Lucas Primality test.
-// - Added integer square root method.
-// - Added setBit/unsetBit methods.
-// - New isProbablePrime() method which do not require the
-// confident parameter.
-//
-// 2) August 29, 2002 (Version 1.02)
-// - Fixed bug in the exponentiation of negative numbers.
-// - Faster modular exponentiation using Barrett reduction.
-// - Added getBytes() method.
-// - Fixed bug in ToHexString method.
-// - Added overloading of ^ operator.
-// - Faster computation of Jacobi symbol.
-//
-// 3) August 19, 2002 (Version 1.01)
-// - Big integer is stored and manipulated as unsigned integers (4 bytes) instead of
-// individual bytes this gives significant performance improvement.
-// - Updated Fermat's Little Theorem test to use a^(p-1) mod p = 1
-// - Added isProbablePrime method.
-// - Updated documentation.
-//
-// 4) August 9, 2002 (Version 1.0)
-// - Initial Release.
-//
-//
-// References
-// [1] D. E. Knuth, "Seminumerical Algorithms", The Art of Computer Programming Vol. 2,
-// 3rd Edition, Addison-Wesley, 1998.
-//
-// [2] K. H. Rosen, "Elementary Number Theory and Its Applications", 3rd Ed,
-// Addison-Wesley, 1993.
-//
-// [3] B. Schneier, "Applied Cryptography", 2nd Ed, John Wiley & Sons, 1996.
-//
-// [4] A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography",
-// CRC Press, 1996, www.cacr.math.uwaterloo.ca/hac
-//
-// [5] A. Bosselaers, R. Govaerts, and J. Vandewalle, "Comparison of Three Modular
-// Reduction Functions," Proc. CRYPTO'93, pp.175-186.
-//
-// [6] R. Baillie and S. S. Wagstaff Jr, "Lucas Pseudoprimes", Mathematics of Computation,
-// Vol. 35, No. 152, Oct 1980, pp. 1391-1417.
-//
-// [7] H. C. Williams, "Édouard Lucas and Primality Testing", Canadian Mathematical
-// Society Series of Monographs and Advance Texts, vol. 22, John Wiley & Sons, New York,
-// NY, 1998.
-//
-// [8] P. Ribenboim, "The new book of prime number records", 3rd edition, Springer-Verlag,
-// New York, NY, 1995.
-//
-// [9] M. Joye and J.-J. Quisquater, "Efficient computation of full Lucas sequences",
-// Electronics Letters, 32(6), 1996, pp 537-538.
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
-//************************************************************************************
using System;
+using System.Security.Cryptography;
+using Mono.Math.Prime.Generator;
+using Mono.Math.Prime;
+
+namespace Mono.Math {
+
+#if INSIDE_CORLIB
+ internal
+#else
+ public
+#endif
+ class BigInteger {
+
+ #region Data Storage
+
+ /// <summary>
+ /// The Length of this BigInteger
+ /// </summary>
+ uint length = 1;
+
+ /// <summary>
+ /// The data for this BigInteger
+ /// </summary>
+ uint [] data;
+
+ #endregion
+
+ #region Constants
+
+ /// <summary>
+ /// Default length of a BigInteger in bytes
+ /// </summary>
+ const uint DEFAULT_LEN = 20;
+
+ /// <summary>
+ /// Table of primes below 2000.
+ /// </summary>
+ /// <remarks>
+ /// <para>
+ /// This table was generated using Mathematica 4.1 using the following function:
+ /// </para>
+ /// <para>
+ /// <code>
+ /// PrimeTable [x_] := Prime [Range [1, PrimePi [x]]]
+ /// PrimeTable [6000]
+ /// </code>
+ /// </para>
+ /// </remarks>
+ internal static readonly uint [] smallPrimes = {
+ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
+ 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
+ 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
+ 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
+ 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
+ 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
+ 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
+ 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
+ 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
+ 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
+ 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
+
+ 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087,
+ 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181,
+ 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279,
+ 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,
+ 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471,
+ 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
+ 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637,
+ 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
+ 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867,
+ 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973,
+ 1979, 1987, 1993, 1997, 1999,
+
+ 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089,
+ 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207,
+ 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
+ 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389,
+ 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503,
+ 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621,
+ 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707,
+ 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797,
+ 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,
+ 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
+
+ 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109,
+ 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
+ 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329,
+ 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449,
+ 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539,
+ 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631,
+ 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733,
+ 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
+ 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943,
+ 3947, 3967, 3989,
+
+ 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091,
+ 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
+ 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289,
+ 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423,
+ 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523,
+ 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649,
+ 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759,
+ 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
+ 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987,
+ 4993, 4999,
+
+ 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101,
+ 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231,
+ 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351,
+ 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449,
+ 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563,
+ 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669,
+ 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
+ 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869,
+ 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987
+ };
+
+ public enum Sign : int {
+ Negative = -1,
+ Zero = 0,
+ Positive = 1
+ };
+
+ #region Exception Messages
+ const string WouldReturnNegVal = "Operation would return a negative value";
+ #endregion
+
+ #endregion
+
+ #region Constructors
+
+ public BigInteger ()
+ {
+ data = new uint [DEFAULT_LEN];
+ this.length = DEFAULT_LEN;
+ }
+
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public BigInteger (Sign sign, uint len)
+ {
+ this.data = new uint [len];
+ this.length = len;
+ }
+
+ public BigInteger (BigInteger bi)
+ {
+ this.data = (uint [])bi.data.Clone ();
+ this.length = bi.length;
+ }
+
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public BigInteger (BigInteger bi, uint len)
+ {
+
+ this.data = new uint [len];
+
+ for (uint i = 0; i < bi.length; i++)
+ this.data [i] = bi.data [i];
+
+ this.length = bi.length;
+ }
+
+ #endregion
+
+ #region Conversions
+
+ public BigInteger (byte [] inData)
+ {
+ length = (uint)inData.Length >> 2;
+ int leftOver = inData.Length & 0x3;
+
+ // length not multiples of 4
+ if (leftOver != 0) length++;
+
+ data = new uint [length];
+
+ for (int i = inData.Length - 1, j = 0; i >= 3; i -= 4, j++) {
+ data [j] = (uint)(
+ (inData [i-3] << (3*8)) |
+ (inData [i-2] << (2*8)) |
+ (inData [i-1] << (1*8)) |
+ (inData [i])
+ );
+ }
-namespace System.Security.Cryptography {
-
-internal class BigRandom {
- RandomNumberGenerator rng;
-
- public BigRandom ()
- {
- rng = RandomNumberGenerator.Create ();
- }
+ switch (leftOver) {
+ case 1: data [length-1] = (uint)inData [0]; break;
+ case 2: data [length-1] = (uint)((inData [0] << 8) | inData [1]); break;
+ case 3: data [length-1] = (uint)((inData [0] << 16) | (inData [1] << 8) | inData [2]); break;
+ }
- public void Get (uint[] data)
- {
- byte[] random = new byte [4 * data.Length];
- rng.GetBytes (random);
- int n = 0;
- for (int i=0; i < data.Length; i++) {
- data[i] = BitConverter.ToUInt32 (random, n);
- n+=4;
+ this.Normalize ();
}
- }
- public int GetInt (int maxValue)
- {
- // calculate mask
- int mask = Int32.MaxValue;
- while ((mask & maxValue) == maxValue)
- mask >>= 1;
- // undo last iteration
- mask <<= 1;
- mask |= 0x01;
- byte[] data = new byte [4];
- int result = -1;
- while ((result < 0) || (result > maxValue)) {
- rng.GetBytes (data);
- result = (BitConverter.ToInt32 (data, 0) & mask);
- }
- return result;
- }
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public BigInteger (uint [] inData)
+ {
+ length = (uint)inData.Length;
- public byte GetByte()
- {
- byte[] data = new byte [1];
- rng.GetBytes (data);
- return data [0];
- }
-}
+ data = new uint [length];
-internal class BigInteger {
- // maximum length of the BigInteger in uint (4 bytes)
- // change this to suit the required level of precision.
-
- //private const int maxLength = 70;
- // FIXME: actually this limit us to approx. 2048 bits keypair for RSA
- private const int maxLength = 140;
-
- private BigRandom random;
-
- // primes smaller than 2000 to test the generated prime number
-
- public static readonly int[] primesBelow2000 = {
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
- 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
- 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
- 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
- 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
- 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
- 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
- 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
- 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
- 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
- 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
- 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193,
- 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297,
- 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
- 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499,
- 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
- 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699,
- 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
- 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
- 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999 };
-
- private uint[] data = null; // stores bytes from the Big Integer
- public int dataLength; // number of actual chars used
-
- // Constructor (Default value for BigInteger is 0
- public BigInteger()
- {
- data = new uint[maxLength];
- dataLength = 1;
- }
+ for (int i = (int)length - 1, j = 0; i >= 0; i--, j++)
+ data [j] = inData [i];
- // Constructor (Default value provided by long)
- public BigInteger(long value)
- {
- data = new uint[maxLength];
- long tempVal = value;
- // copy bytes from long to BigInteger without any assumption of
- // the length of the long datatype
- dataLength = 0;
- while(value != 0 && dataLength < maxLength) {
- data[dataLength] = (uint)(value & 0xFFFFFFFF);
- value >>= 32;
- dataLength++;
+ this.Normalize ();
}
- if(tempVal > 0) { // overflow check for +ve value
- if(value != 0 || (data[maxLength-1] & 0x80000000) != 0)
- throw(new ArithmeticException("Positive overflow in constructor."));
- }
- else if(tempVal < 0) { // underflow check for -ve value
- if(value != -1 || (data[dataLength-1] & 0x80000000) == 0)
- throw(new ArithmeticException("Negative underflow in constructor."));
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public BigInteger (uint ui)
+ {
+ data = new uint [] {ui};
}
- if(dataLength == 0)
- dataLength = 1;
- }
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public BigInteger (ulong ul)
+ {
+ data = new uint [2] { (uint)ul, (uint)(ul >> 32)};
+ length = 2;
- // Constructor (Default value provided by ulong)
- public BigInteger(ulong value)
- {
- data = new uint[maxLength];
- // copy bytes from ulong to BigInteger without any assumption of
- // the length of the ulong datatype
-
- dataLength = 0;
- while(value != 0 && dataLength < maxLength) {
- data[dataLength] = (uint)(value & 0xFFFFFFFF);
- value >>= 32;
- dataLength++;
+ this.Normalize ();
}
- if(value != 0 || (data[maxLength-1] & 0x80000000) != 0)
- throw(new ArithmeticException("Positive overflow in constructor."));
-
- if(dataLength == 0)
- dataLength = 1;
- }
-
- // Constructor (Default value provided by BigInteger)
- public BigInteger(BigInteger bi)
- {
- data = new uint[maxLength];
- dataLength = bi.dataLength;
- for(int i = 0; i < dataLength; i++)
- data[i] = bi.data[i];
- }
-
- // Constructor (Default value provided by a string of digits of the
- // specified base)
- // Example (base 10)
- // -----------------
- // To initialize "a" with the default value of 1234 in base 10
- // BigInteger a = new BigInteger("1234", 10)
- //
- // To initialize "a" with the default value of -1234
- // BigInteger a = new BigInteger("-1234", 10)
- //
- // Example (base 16)
- // -----------------
- // To initialize "a" with the default value of 0x1D4F in base 16
- // BigInteger a = new BigInteger("1D4F", 16)
- //
- // To initialize "a" with the default value of -0x1D4F
- // BigInteger a = new BigInteger("-1D4F", 16)
- //
- // Note that string values are specified in the <sign><magnitude>
- // format.
- public BigInteger(string value, int radix)
- {
- BigInteger multiplier = new BigInteger(1);
- BigInteger result = new BigInteger();
- value = (value.ToUpper()).Trim();
- int limit = 0;
-
- if(value[0] == '-')
- limit = 1;
-
- for(int i = value.Length - 1; i >= limit ; i--) {
- int posVal = (int)value[i];
-
- if(posVal >= '0' && posVal <= '9')
- posVal -= '0';
- else if(posVal >= 'A' && posVal <= 'Z')
- posVal = (posVal - 'A') + 10;
- else
- posVal = 9999999; // arbitrary large
-
-
- if(posVal >= radix)
- throw(new ArithmeticException("Invalid string in constructor."));
- else {
- if(value[0] == '-')
- posVal = -posVal;
-
- result = result + (multiplier * posVal);
-
- if((i - 1) >= limit)
- multiplier = multiplier * radix;
- }
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public static implicit operator BigInteger (uint value)
+ {
+ return (new BigInteger (value));
}
- if(value[0] == '-') { // negative values
- if((result.data[maxLength-1] & 0x80000000) == 0)
- throw(new ArithmeticException("Negative underflow in constructor."));
+ public static implicit operator BigInteger (int value)
+ {
+ if (value < 0) throw new ArgumentOutOfRangeException ("value");
+ return (new BigInteger ((uint)value));
}
- else { // positive values
- if((result.data[maxLength-1] & 0x80000000) != 0)
- throw(new ArithmeticException("Positive overflow in constructor."));
- }
-
- data = new uint[maxLength];
- for(int i = 0; i < result.dataLength; i++)
- data[i] = result.data[i];
-
- dataLength = result.dataLength;
- }
-
- // Constructor (Default value provided by an array of bytes)
- //
- // The lowest index of the input byte array (i.e [0]) should contain the
- // most significant byte of the number, and the highest index should
- // contain the least significant byte.
- //
- // E.g.
- // To initialize "a" with the default value of 0x1D4F in base 16
- // byte[] temp = { 0x1D, 0x4F };
- // BigInteger a = new BigInteger(temp)
- //
- // Note that this method of initialization does not allow the
- // sign to be specified.
- public BigInteger(byte[] inData)
- {
- dataLength = inData.Length >> 2;
-
- int leftOver = inData.Length & 0x3;
- if(leftOver != 0) // length not multiples of 4
- dataLength++;
-
-
- if(dataLength > maxLength)
- throw(new ArithmeticException("Byte overflow in constructor."));
-
- data = new uint[maxLength];
-
- for(int i = inData.Length - 1, j = 0; i >= 3; i -= 4, j++) {
- data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
- (inData[i-1] << 8) + inData[i]);
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public static implicit operator BigInteger (ulong value)
+ {
+ return (new BigInteger (value));
}
- if(leftOver == 1)
- data[dataLength-1] = (uint)inData[0];
- else if(leftOver == 2)
- data[dataLength-1] = (uint)((inData[0] << 8) + inData[1]);
- else if(leftOver == 3)
- data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2]);
-
+ /* This is the BigInteger.Parse method I use. This method works
+ because BigInteger.ToString returns the input I gave to Parse. */
+ public static BigInteger Parse (string number)
+ {
+ if (number == null)
+ throw new ArgumentNullException ("number");
- while(dataLength > 1 && data[dataLength-1] == 0)
- dataLength--;
-
- //Console.WriteLine("Len = " + dataLength);
- }
-
- // Constructor (Default value provided by an array of bytes of the
- // specified length.)
- public BigInteger(byte[] inData, int inLen)
- {
- dataLength = inLen >> 2;
-
- int leftOver = inLen & 0x3;
- if(leftOver != 0) // length not multiples of 4
- dataLength++;
+ int i = 0, len = number.Length;
+ char c;
+ bool digits_seen = false;
+ BigInteger val = new BigInteger (0);
+ if (number [i] == '+') {
+ i++;
+ }
+ else if (number [i] == '-') {
+ throw new FormatException (WouldReturnNegVal);
+ }
- if(dataLength > maxLength || inLen > inData.Length)
- throw(new ArithmeticException("Byte overflow in constructor."));
+ for (; i < len; i++) {
+ c = number [i];
+ if (c == '\0') {
+ i = len;
+ continue;
+ }
+ if (c >= '0' && c <= '9') {
+ val = val * 10 + (c - '0');
+ digits_seen = true;
+ }
+ else {
+ if (Char.IsWhiteSpace (c)) {
+ for (i++; i < len; i++) {
+ if (!Char.IsWhiteSpace (number [i]))
+ throw new FormatException ();
+ }
+ break;
+ }
+ else
+ throw new FormatException ();
+ }
+ }
+ if (!digits_seen)
+ throw new FormatException ();
+ return val;
+ }
+ #endregion
- data = new uint[maxLength];
+ #region Operators
- for(int i = inLen - 1, j = 0; i >= 3; i -= 4, j++) {
- data[j] = (uint)((inData[i-3] << 24) + (inData[i-2] << 16) +
- (inData[i-1] << 8) + inData[i]);
+ public static BigInteger operator + (BigInteger bi1, BigInteger bi2)
+ {
+ if (bi1 == 0)
+ return new BigInteger (bi2);
+ else if (bi2 == 0)
+ return new BigInteger (bi1);
+ else
+ return Kernel.AddSameSign (bi1, bi2);
}
- if(leftOver == 1)
- data[dataLength-1] = (uint)inData[0];
- else if(leftOver == 2)
- data[dataLength-1] = (uint)((inData[0] << 8) + inData[1]);
- else if(leftOver == 3)
- data[dataLength-1] = (uint)((inData[0] << 16) + (inData[1] << 8) + inData[2]);
-
+ public static BigInteger operator - (BigInteger bi1, BigInteger bi2)
+ {
+ if (bi2 == 0)
+ return new BigInteger (bi1);
- if(dataLength == 0)
- dataLength = 1;
+ if (bi1 == 0)
+ throw new ArithmeticException (WouldReturnNegVal);
- while(dataLength > 1 && data[dataLength-1] == 0)
- dataLength--;
+ switch (Kernel.Compare (bi1, bi2)) {
- //Console.WriteLine("Len = " + dataLength);
- }
+ case Sign.Zero:
+ return 0;
+ case Sign.Positive:
+ return Kernel.Subtract (bi1, bi2);
- // Constructor (Default value provided by an array of unsigned integers)
- public BigInteger(uint[] inData)
- {
- dataLength = inData.Length;
+ case Sign.Negative:
+ throw new ArithmeticException (WouldReturnNegVal);
+ default:
+ throw new Exception ();
+ }
+ }
- if(dataLength > maxLength)
- throw(new ArithmeticException("Byte overflow in constructor."));
+ public static int operator % (BigInteger bi, int i)
+ {
+ if (i > 0)
+ return (int)Kernel.DwordMod (bi, (uint)i);
+ else
+ return -(int)Kernel.DwordMod (bi, (uint)-i);
+ }
- data = new uint[maxLength];
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public static uint operator % (BigInteger bi, uint ui)
+ {
+ return Kernel.DwordMod (bi, (uint)ui);
+ }
- for(int i = dataLength - 1, j = 0; i >= 0; i--, j++)
- data[j] = inData[i];
+ public static BigInteger operator % (BigInteger bi1, BigInteger bi2)
+ {
+ return Kernel.multiByteDivide (bi1, bi2)[1];
+ }
- while(dataLength > 1 && data[dataLength-1] == 0)
- dataLength--;
+ public static BigInteger operator / (BigInteger bi, int i)
+ {
+ if (i > 0)
+ return Kernel.DwordDiv (bi, (uint)i);
- //Console.WriteLine("Len = " + dataLength);
- }
+ throw new ArithmeticException (WouldReturnNegVal);
+ }
- private BigRandom rng {
- get {
- if (random == null)
- random = new BigRandom ();
- return random;
+ public static BigInteger operator / (BigInteger bi1, BigInteger bi2)
+ {
+ return Kernel.multiByteDivide (bi1, bi2)[0];
}
- }
- // Overloading of the typecast operator.
- // For BigInteger bi = 10;
- public static implicit operator BigInteger (long value)
- {
- return (new BigInteger (value));
- }
+ public static BigInteger operator * (BigInteger bi1, BigInteger bi2)
+ {
+ if (bi1 == 0 || bi2 == 0) return 0;
- public static implicit operator BigInteger (ulong value)
- {
- return (new BigInteger (value));
- }
+ //
+ // Validate pointers
+ //
+ if (bi1.data.Length < bi1.length) throw new IndexOutOfRangeException ("bi1 out of range");
+ if (bi2.data.Length < bi2.length) throw new IndexOutOfRangeException ("bi2 out of range");
- public static implicit operator BigInteger (int value)
- {
- return (new BigInteger ( (long)value));
- }
+ BigInteger ret = new BigInteger (Sign.Positive, bi1.length + bi2.length);
- public static implicit operator BigInteger (uint value)
- {
- return (new BigInteger ( (ulong)value));
- }
+ Kernel.Multiply (bi1.data, 0, bi1.length, bi2.data, 0, bi2.length, ret.data, 0);
- // Overloading of addition operator
- public static BigInteger operator + (BigInteger bi1, BigInteger bi2)
- {
- BigInteger result = new BigInteger ();
+ ret.Normalize ();
+ return ret;
+ }
- result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
+ public static BigInteger operator * (BigInteger bi, int i)
+ {
+ if (i < 0) throw new ArithmeticException (WouldReturnNegVal);
+ if (i == 0) return 0;
+ if (i == 1) return new BigInteger (bi);
- long carry = 0;
- for(int i = 0; i < result.dataLength; i++) {
- long sum = (long)bi1.data[i] + (long)bi2.data[i] + carry;
- carry = sum >> 32;
- result.data[i] = (uint)(sum & 0xFFFFFFFF);
+ return Kernel.MultiplyByDword (bi, (uint)i);
}
- if(carry != 0 && result.dataLength < maxLength) {
- result.data[result.dataLength] = (uint)(carry);
- result.dataLength++;
+ public static BigInteger operator << (BigInteger bi1, int shiftVal)
+ {
+ return Kernel.LeftShift (bi1, shiftVal);
}
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
-
-
- // overflow check
- int lastPos = maxLength - 1;
- if((bi1.data[lastPos] & 0x80000000) == (bi2.data[lastPos] & 0x80000000) &&
- (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000)) {
- throw (new ArithmeticException());
+ public static BigInteger operator >> (BigInteger bi1, int shiftVal)
+ {
+ return Kernel.RightShift (bi1, shiftVal);
}
- return result;
- }
-
- // Overloading of the unary ++ operator
- public static BigInteger operator ++ (BigInteger bi1)
- {
- BigInteger result = new BigInteger (bi1);
+ #endregion
- long val, carry = 1;
- int index = 0;
+ #region Friendly names for operators
- while(carry != 0 && index < maxLength) {
- val = (long)(result.data[index]);
- val++;
+ // with names suggested by FxCop 1.30
- result.data[index] = (uint)(val & 0xFFFFFFFF);
- carry = val >> 32;
-
- index++;
+ public static BigInteger Add (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 + bi2);
}
- if(index > result.dataLength)
- result.dataLength = index;
- else {
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
+ public static BigInteger Subtract (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 - bi2);
}
- // overflow check
- int lastPos = maxLength - 1;
-
- // overflow if initial value was +ve but ++ caused a sign
- // change to negative.
-
- if((bi1.data[lastPos] & 0x80000000) == 0 &&
- (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000)) {
- throw (new ArithmeticException("Overflow in ++."));
+ public static int Modulus (BigInteger bi, int i)
+ {
+ return (bi % i);
}
- return result;
- }
-
- // Overloading of subtraction operator
- public static BigInteger operator - (BigInteger bi1, BigInteger bi2)
- {
- BigInteger result = new BigInteger ();
-
- result.dataLength = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
-
- long carryIn = 0;
- for(int i = 0; i < result.dataLength; i++) {
- long diff;
- diff = (long)bi1.data[i] - (long)bi2.data[i] - carryIn;
- result.data[i] = (uint)(diff & 0xFFFFFFFF);
-
- if(diff < 0)
- carryIn = 1;
- else
- carryIn = 0;
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public static uint Modulus (BigInteger bi, uint ui)
+ {
+ return (bi % ui);
}
- // roll over to negative
- if(carryIn != 0) {
- for(int i = result.dataLength; i < maxLength; i++)
- result.data[i] = 0xFFFFFFFF;
- result.dataLength = maxLength;
+ public static BigInteger Modulus (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 % bi2);
}
- // fixed in v1.03 to give correct datalength for a - (-b)
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
-
- // overflow check
-
- int lastPos = maxLength - 1;
- if((bi1.data[lastPos] & 0x80000000) != (bi2.data[lastPos] & 0x80000000) &&
- (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000)) {
- throw (new ArithmeticException());
+ public static BigInteger Divid (BigInteger bi, int i)
+ {
+ return (bi / i);
}
- return result;
- }
-
-
- // Overloading of the unary -- operator
- public static BigInteger operator -- (BigInteger bi1)
- {
- BigInteger result = new BigInteger (bi1);
-
- long val;
- bool carryIn = true;
- int index = 0;
-
- while(carryIn && index < maxLength) {
- val = (long)(result.data[index]);
- val--;
-
- result.data[index] = (uint)(val & 0xFFFFFFFF);
-
- if(val >= 0)
- carryIn = false;
-
- index++;
+ public static BigInteger Divid (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 / bi2);
}
- if(index > result.dataLength)
- result.dataLength = index;
-
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
-
- // overflow check
- int lastPos = maxLength - 1;
-
- // overflow if initial value was -ve but -- caused a sign
- // change to positive.
-
- if((bi1.data[lastPos] & 0x80000000) != 0 &&
- (result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000)) {
- throw (new ArithmeticException("Underflow in --."));
+ public static BigInteger Multiply (BigInteger bi1, BigInteger bi2)
+ {
+ return (bi1 * bi2);
}
- return result;
- }
-
- // Overloading of multiplication operator
- public static BigInteger operator * (BigInteger bi1, BigInteger bi2)
- {
- int lastPos = maxLength-1;
- bool bi1Neg = false, bi2Neg = false;
-
- // take the absolute value of the inputs
- try {
- if((bi1.data[lastPos] & 0x80000000) != 0) { // bi1 negative
- bi1Neg = true; bi1 = -bi1;
- }
- if((bi2.data[lastPos] & 0x80000000) != 0) { // bi2 negative
- bi2Neg = true; bi2 = -bi2;
- }
+ public static BigInteger Multiply (BigInteger bi, int i)
+ {
+ return (bi * i);
}
- catch(Exception) {}
-
- BigInteger result = new BigInteger();
-
- // multiply the absolute values
- try {
- for(int i = 0; i < bi1.dataLength; i++) {
- if(bi1.data[i] == 0) continue;
- ulong mcarry = 0;
- for(int j = 0, k = i; j < bi2.dataLength; j++, k++) {
- // k = i + j
- ulong val = ((ulong)bi1.data[i] * (ulong)bi2.data[j]) +
- (ulong)result.data[k] + mcarry;
+ #endregion
- result.data[k] = (uint)(val & 0xFFFFFFFF);
- mcarry = (val >> 32);
- }
-
- if(mcarry != 0)
- result.data[i+bi2.dataLength] = (uint)mcarry;
+ #region Random
+ private static RandomNumberGenerator rng;
+ private static RandomNumberGenerator Rng {
+ get {
+ if (rng == null)
+ rng = RandomNumberGenerator.Create ();
+ return rng;
}
}
- catch(Exception) {
- throw(new ArithmeticException("Multiplication overflow."));
- }
+ /// <summary>
+ /// Generates a new, random BigInteger of the specified length.
+ /// </summary>
+ /// <param name="bits">The number of bits for the new number.</param>
+ /// <param name="rng">A random number generator to use to obtain the bits.</param>
+ /// <returns>A random number of the specified length.</returns>
+ public static BigInteger GenerateRandom (int bits, RandomNumberGenerator rng)
+ {
+ int dwords = bits >> 5;
+ int remBits = bits & 0x1F;
- result.dataLength = bi1.dataLength + bi2.dataLength;
- if(result.dataLength > maxLength)
- result.dataLength = maxLength;
+ if (remBits != 0)
+ dwords++;
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
+ BigInteger ret = new BigInteger (Sign.Positive, (uint)dwords + 1);
+ byte [] random = new byte [dwords << 2];
- // overflow check (result is -ve)
- if((result.data[lastPos] & 0x80000000) != 0) {
- if(bi1Neg != bi2Neg && result.data[lastPos] == 0x80000000) { // different sign
- // handle the special case where multiplication produces
- // a max negative number in 2's complement.
+ rng.GetBytes (random);
+ Buffer.BlockCopy (random, 0, ret.data, 0, (int)dwords << 2);
- if(result.dataLength == 1)
- return result;
- else {
- bool isMaxNeg = true;
- for(int i = 0; i < result.dataLength - 1 && isMaxNeg; i++) {
- if(result.data[i] != 0)
- isMaxNeg = false;
- }
+ if (remBits != 0) {
+ uint mask = (uint)(0x01 << (remBits-1));
+ ret.data [dwords-1] |= mask;
- if(isMaxNeg)
- return result;
- }
+ mask = (uint)(0xFFFFFFFF >> (32 - remBits));
+ ret.data [dwords-1] &= mask;
}
+ else
+ ret.data [dwords-1] |= 0x80000000;
- throw(new ArithmeticException("Multiplication overflow."));
+ ret.Normalize ();
+ return ret;
}
- // if input has different signs, then result is -ve
- if(bi1Neg != bi2Neg)
- return -result;
-
- return result;
- }
-
- // Overloading of unary << operators
- public static BigInteger operator << (BigInteger bi1, int shiftVal)
- {
- BigInteger result = new BigInteger (bi1);
- result.dataLength = shiftLeft(result.data, shiftVal);
+ /// <summary>
+ /// Generates a new, random BigInteger of the specified length using the default RNG crypto service provider.
+ /// </summary>
+ /// <param name="bits">The number of bits for the new number.</param>
+ /// <returns>A random number of the specified length.</returns>
+ public static BigInteger GenerateRandom (int bits)
+ {
+ return GenerateRandom (bits, Rng);
+ }
- return result;
- }
+ /// <summary>
+ /// Randomizes the bits in "this" from the specified RNG.
+ /// </summary>
+ /// <param name="rng">A RNG.</param>
+ public void Randomize (RandomNumberGenerator rng)
+ {
+ if (this == 0)
+ return;
- // least significant bits at lower part of buffer
- private static int shiftLeft (uint[] buffer, int shiftVal)
- {
- int shiftAmount = 32;
- int bufLen = buffer.Length;
+ int bits = this.BitCount ();
+ int dwords = bits >> 5;
+ int remBits = bits & 0x1F;
- while(bufLen > 1 && buffer[bufLen-1] == 0)
- bufLen--;
+ if (remBits != 0)
+ dwords++;
- for(int count = shiftVal; count > 0;) {
- if(count < shiftAmount)
- shiftAmount = count;
+ byte [] random = new byte [dwords << 2];
- //Console.WriteLine("shiftAmount = {0}", shiftAmount);
+ rng.GetBytes (random);
+ Buffer.BlockCopy (random, 0, data, 0, (int)dwords << 2);
- ulong carry = 0;
- for(int i = 0; i < bufLen; i++) {
- ulong val = ((ulong)buffer[i]) << shiftAmount;
- val |= carry;
+ if (remBits != 0) {
+ uint mask = (uint)(0x01 << (remBits-1));
+ data [dwords-1] |= mask;
- buffer[i] = (uint)(val & 0xFFFFFFFF);
- carry = val >> 32;
+ mask = (uint)(0xFFFFFFFF >> (32 - remBits));
+ data [dwords-1] &= mask;
}
- if(carry != 0) {
- if(bufLen + 1 <= buffer.Length) {
- buffer[bufLen] = (uint)carry;
- bufLen++;
- }
- }
- count -= shiftAmount;
- }
- return bufLen;
- }
-
- // Overloading of unary >> operators
- public static BigInteger operator >> (BigInteger bi1, int shiftVal)
- {
- BigInteger result = new BigInteger(bi1);
- result.dataLength = shiftRight(result.data, shiftVal);
-
- if((bi1.data[maxLength-1] & 0x80000000) != 0) { // negative
- for(int i = maxLength - 1; i >= result.dataLength; i--)
- result.data[i] = 0xFFFFFFFF;
-
- uint mask = 0x80000000;
- for(int i = 0; i < 32; i++) {
- if((result.data[result.dataLength-1] & mask) != 0)
- break;
+ else
+ data [dwords-1] |= 0x80000000;
- result.data[result.dataLength-1] |= mask;
- mask >>= 1;
- }
- result.dataLength = maxLength;
+ Normalize ();
}
- return result;
- }
-
- private static int shiftRight (uint[] buffer, int shiftVal)
- {
- int shiftAmount = 32;
- int invShift = 0;
- int bufLen = buffer.Length;
-
- while(bufLen > 1 && buffer[bufLen-1] == 0)
- bufLen--;
+ /// <summary>
+ /// Randomizes the bits in "this" from the default RNG.
+ /// </summary>
+ public void Randomize ()
+ {
+ Randomize (Rng);
+ }
- //Console.WriteLine("bufLen = " + bufLen + " buffer.Length = " + buffer.Length);
+ #endregion
- for(int count = shiftVal; count > 0;) {
- if(count < shiftAmount) {
- shiftAmount = count;
- invShift = 32 - shiftAmount;
- }
+ #region Bitwise
- //Console.WriteLine("shiftAmount = {0}", shiftAmount);
+ public int BitCount ()
+ {
+ this.Normalize ();
- ulong carry = 0;
- for(int i = bufLen - 1; i >= 0; i--) {
- ulong val = ((ulong)buffer[i]) >> shiftAmount;
- val |= carry;
+ uint value = data [length - 1];
+ uint mask = 0x80000000;
+ uint bits = 32;
- carry = ((ulong)buffer[i]) << invShift;
- buffer[i] = (uint)(val);
+ while (bits > 0 && (value & mask) == 0) {
+ bits--;
+ mask >>= 1;
}
+ bits += ((length - 1) << 5);
- count -= shiftAmount;
+ return (int)bits;
}
- while(bufLen > 1 && buffer[bufLen-1] == 0)
- bufLen--;
-
- return bufLen;
- }
-
-
- // Overloading of the NOT operator (1's complement)
- public static BigInteger operator ~ (BigInteger bi1)
- {
- BigInteger result = new BigInteger (bi1);
-
- for(int i = 0; i < maxLength; i++)
- result.data[i] = (uint)(~(bi1.data[i]));
-
- result.dataLength = maxLength;
+ /// <summary>
+ /// Tests if the specified bit is 1.
+ /// </summary>
+ /// <param name="bitNum">The bit to test. The least significant bit is 0.</param>
+ /// <returns>True if bitNum is set to 1, else false.</returns>
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public bool TestBit (uint bitNum)
+ {
+ uint bytePos = bitNum >> 5; // divide by 32
+ byte bitPos = (byte)(bitNum & 0x1F); // get the lowest 5 bits
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
-
- return result;
- }
-
- // Overloading of the NEGATE operator (2's complement)
- public static BigInteger operator - (BigInteger bi1)
- {
- // handle neg of zero separately since it'll cause an overflow
- // if we proceed.
- if(bi1.dataLength == 1 && bi1.data[0] == 0)
- return (new BigInteger ());
-
- BigInteger result = new BigInteger (bi1);
-
- // 1's complement
- for(int i = 0; i < maxLength; i++)
- result.data[i] = (uint)(~(bi1.data[i]));
+ uint mask = (uint)1 << bitPos;
+ return ((this.data [bytePos] & mask) != 0);
+ }
- // add one to result of 1's complement
- long val, carry = 1;
- int index = 0;
+ public bool TestBit (int bitNum)
+ {
+ if (bitNum < 0) throw new IndexOutOfRangeException ("bitNum out of range");
- while(carry != 0 && index < maxLength) {
- val = (long)(result.data[index]);
- val++;
+ uint bytePos = (uint)bitNum >> 5; // divide by 32
+ byte bitPos = (byte)(bitNum & 0x1F); // get the lowest 5 bits
- result.data[index] = (uint)(val & 0xFFFFFFFF);
- carry = val >> 32;
+ uint mask = (uint)1 << bitPos;
+ return ((this.data [bytePos] | mask) == this.data [bytePos]);
+ }
- index++;
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public void SetBit (uint bitNum)
+ {
+ SetBit (bitNum, true);
}
- if((bi1.data[maxLength-1] & 0x80000000) == (result.data[maxLength-1] & 0x80000000))
- throw (new ArithmeticException("Overflow in negation.\n"));
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public void ClearBit (uint bitNum)
+ {
+ SetBit (bitNum, false);
+ }
- result.dataLength = maxLength;
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public void SetBit (uint bitNum, bool value)
+ {
+ uint bytePos = bitNum >> 5; // divide by 32
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
- return result;
- }
+ if (bytePos < this.length) {
+ uint mask = (uint)1 << (int)(bitNum & 0x1F);
+ if (value)
+ this.data [bytePos] |= mask;
+ else
+ this.data [bytePos] &= ~mask;
+ }
+ }
+ public int LowestSetBit ()
+ {
+ if (this == 0) return -1;
+ int i = 0;
+ while (!TestBit (i)) i++;
+ return i;
+ }
- // Overloading of equality operator
- public static bool operator == (BigInteger bi1, BigInteger bi2)
- {
- return bi1.Equals (bi2);
- }
+ public byte[] GetBytes ()
+ {
+ if (this == 0) return new byte [1];
- public static bool operator !=( BigInteger bi1, BigInteger bi2)
- {
- return !(bi1.Equals (bi2));
- }
+ int numBits = BitCount ();
+ int numBytes = numBits >> 3;
+ if ((numBits & 0x7) != 0)
+ numBytes++;
- public override bool Equals (object o)
- {
- BigInteger bi = (BigInteger) o;
+ byte [] result = new byte [numBytes];
- if(this.dataLength != bi.dataLength)
- return false;
+ int numBytesInWord = numBytes & 0x3;
+ if (numBytesInWord == 0) numBytesInWord = 4;
- for(int i = 0; i < this.dataLength; i++) {
- if(this.data [i] != bi.data [i])
- return false;
+ int pos = 0;
+ for (int i = (int)length - 1; i >= 0; i--) {
+ uint val = data [i];
+ for (int j = numBytesInWord - 1; j >= 0; j--) {
+ result [pos+j] = (byte)(val & 0xFF);
+ val >>= 8;
+ }
+ pos += numBytesInWord;
+ numBytesInWord = 4;
+ }
+ return result;
}
- return true;
- }
- public override int GetHashCode ()
- {
- return this.ToString ().GetHashCode ();
- }
+ #endregion
- // Overloading of inequality operator
- public static bool operator > (BigInteger bi1, BigInteger bi2)
- {
- int pos = maxLength - 1;
+ #region Compare
- // bi1 is negative, bi2 is positive
- if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
- return false;
-
- // bi1 is positive, bi2 is negative
- else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
- return true;
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public static bool operator == (BigInteger bi1, uint ui)
+ {
+ if (bi1.length != 1) bi1.Normalize ();
+ return bi1.length == 1 && bi1.data [0] == ui;
+ }
- // same sign
- int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
- for(pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--);
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public static bool operator != (BigInteger bi1, uint ui)
+ {
+ if (bi1.length != 1) bi1.Normalize ();
+ return !(bi1.length == 1 && bi1.data [0] == ui);
+ }
- if(pos >= 0) {
- if(bi1.data[pos] > bi2.data[pos])
+ public static bool operator == (BigInteger bi1, BigInteger bi2)
+ {
+ // we need to compare with null
+ if ((bi1 as object) == (bi2 as object))
return true;
- return false;
+ if (null == bi1 || null == bi2)
+ return false;
+ return Kernel.Compare (bi1, bi2) == 0;
}
- return false;
- }
-
- public static bool operator < (BigInteger bi1, BigInteger bi2)
- {
- int pos = maxLength - 1;
-
- // bi1 is negative, bi2 is positive
- if((bi1.data[pos] & 0x80000000) != 0 && (bi2.data[pos] & 0x80000000) == 0)
- return true;
- // bi1 is positive, bi2 is negative
- else if((bi1.data[pos] & 0x80000000) == 0 && (bi2.data[pos] & 0x80000000) != 0)
- return false;
-
- // same sign
- int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
- for(pos = len - 1; pos >= 0 && bi1.data[pos] == bi2.data[pos]; pos--);
-
- if(pos >= 0) {
- if(bi1.data[pos] < bi2.data[pos])
+ public static bool operator != (BigInteger bi1, BigInteger bi2)
+ {
+ // we need to compare with null
+ if ((bi1 as object) == (bi2 as object))
+ return false;
+ if (null == bi1 || null == bi2)
return true;
- return false;
+ return Kernel.Compare (bi1, bi2) != 0;
}
- return false;
- }
-
- public static bool operator >= (BigInteger bi1, BigInteger bi2)
- {
- return (bi1 == bi2 || bi1 > bi2);
- }
-
- public static bool operator <= (BigInteger bi1, BigInteger bi2)
- {
- return (bi1 == bi2 || bi1 < bi2);
- }
- // Private function that supports the division of two numbers with
- // a divisor that has more than 1 digit.
- // Algorithm taken from [1]
- private static void multiByteDivide (BigInteger bi1, BigInteger bi2,
- BigInteger outQuotient, BigInteger outRemainder)
- {
- uint[] result = new uint[maxLength];
-
- int remainderLen = bi1.dataLength + 1;
- uint[] remainder = new uint[remainderLen];
-
- uint mask = 0x80000000;
- uint val = bi2.data[bi2.dataLength - 1];
- int shift = 0, resultPos = 0;
-
- while(mask != 0 && (val & mask) == 0) {
- shift++; mask >>= 1;
+ public static bool operator > (BigInteger bi1, BigInteger bi2)
+ {
+ return Kernel.Compare (bi1, bi2) > 0;
}
- //Console.WriteLine("shift = {0}", shift);
- //Console.WriteLine("Before bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength);
-
- for (int i = 0; i < bi1.dataLength; i++)
- remainder[i] = bi1.data[i];
- shiftLeft (remainder, shift);
- bi2 = bi2 << shift;
-
- /*
- Console.WriteLine("bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength, bi2.dataLength);
- Console.WriteLine("dividend = " + bi1 + "\ndivisor = " + bi2);
- for(int q = remainderLen - 1; q >= 0; q--)
- Console.Write("{0:x2}", remainder[q]);
- Console.WriteLine();
- */
-
- int j = remainderLen - bi2.dataLength;
- int pos = remainderLen - 1;
+ public static bool operator < (BigInteger bi1, BigInteger bi2)
+ {
+ return Kernel.Compare (bi1, bi2) < 0;
+ }
- ulong firstDivisorByte = bi2.data[bi2.dataLength-1];
- ulong secondDivisorByte = bi2.data[bi2.dataLength-2];
+ public static bool operator >= (BigInteger bi1, BigInteger bi2)
+ {
+ return Kernel.Compare (bi1, bi2) >= 0;
+ }
- int divisorLen = bi2.dataLength + 1;
- uint[] dividendPart = new uint[divisorLen];
+ public static bool operator <= (BigInteger bi1, BigInteger bi2)
+ {
+ return Kernel.Compare (bi1, bi2) <= 0;
+ }
- while(j > 0) {
- ulong dividend = ((ulong)remainder[pos] << 32) + (ulong)remainder[pos-1];
- //Console.WriteLine("dividend = {0}", dividend);
+ public Sign Compare (BigInteger bi)
+ {
+ return Kernel.Compare (this, bi);
+ }
- ulong q_hat = dividend / firstDivisorByte;
- ulong r_hat = dividend % firstDivisorByte;
+ #endregion
- //Console.WriteLine("q_hat = {0:X}, r_hat = {1:X}", q_hat, r_hat);
+ #region Formatting
- bool done = false;
- while(!done) {
- done = true;
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public string ToString (uint radix)
+ {
+ return ToString (radix, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ");
+ }
- if(q_hat == 0x100000000 ||
- (q_hat * secondDivisorByte) > ((r_hat << 32) + remainder[pos-2])) {
- q_hat--;
- r_hat += firstDivisorByte;
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public string ToString (uint radix, string characterSet)
+ {
+ if (characterSet.Length < radix)
+ throw new ArgumentException ("charSet length less than radix", "characterSet");
+ if (radix == 1)
+ throw new ArgumentException ("There is no such thing as radix one notation", "radix");
- if(r_hat < 0x100000000)
- done = false;
- }
- }
+ if (this == 0) return "0";
+ if (this == 1) return "1";
- for (int h = 0; h < divisorLen; h++)
- dividendPart[h] = remainder[pos-h];
+ string result = "";
- BigInteger kk = new BigInteger (dividendPart);
- BigInteger ss = bi2 * (long)q_hat;
+ BigInteger a = new BigInteger (this);
- //Console.WriteLine("ss before = " + ss);
- while(ss > kk) {
- q_hat--;
- ss -= bi2;
- //Console.WriteLine(ss);
+ while (a != 0) {
+ uint rem = Kernel.SingleByteDivideInPlace (a, radix);
+ result = characterSet [(int) rem] + result;
}
- BigInteger yy = kk - ss;
-
- //Console.WriteLine("ss = " + ss);
- //Console.WriteLine("kk = " + kk);
- //Console.WriteLine("yy = " + yy);
-
- for(int h = 0; h < divisorLen; h++)
- remainder[pos-h] = yy.data[bi2.dataLength-h];
- /*
- Console.WriteLine("dividend = ");
- for(int q = remainderLen - 1; q >= 0; q--)
- Console.Write("{0:x2}", remainder[q]);
- Console.WriteLine("\n************ q_hat = {0:X}\n", q_hat);
- */
-
- result[resultPos++] = (uint)q_hat;
-
- pos--;
- j--;
+ return result;
}
- outQuotient.dataLength = resultPos;
- int y = 0;
- for(int x = outQuotient.dataLength - 1; x >= 0; x--, y++)
- outQuotient.data[y] = result[x];
- for(; y < maxLength; y++)
- outQuotient.data[y] = 0;
-
- while(outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength-1] == 0)
- outQuotient.dataLength--;
-
- if(outQuotient.dataLength == 0)
- outQuotient.dataLength = 1;
-
- outRemainder.dataLength = shiftRight(remainder, shift);
-
- for(y = 0; y < outRemainder.dataLength; y++)
- outRemainder.data[y] = remainder[y];
- for(; y < maxLength; y++)
- outRemainder.data[y] = 0;
- }
-
- // Private function that supports the division of two numbers with
- // a divisor that has only 1 digit.
- private static void singleByteDivide (BigInteger bi1, BigInteger bi2,
- BigInteger outQuotient, BigInteger outRemainder)
- {
- uint[] result = new uint[maxLength];
- int resultPos = 0;
-
- // copy dividend to reminder
- for(int i = 0; i < maxLength; i++)
- outRemainder.data[i] = bi1.data[i];
- outRemainder.dataLength = bi1.dataLength;
-
- while(outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength-1] == 0)
- outRemainder.dataLength--;
+ #endregion
- ulong divisor = (ulong)bi2.data[0];
- int pos = outRemainder.dataLength - 1;
- ulong dividend = (ulong)outRemainder.data[pos];
+ #region Misc
- //Console.WriteLine("divisor = " + divisor + " dividend = " + dividend);
- //Console.WriteLine("divisor = " + bi2 + "\ndividend = " + bi1);
+ /// <summary>
+ /// Normalizes this by setting the length to the actual number of
+ /// uints used in data and by setting the sign to Sign.Zero if the
+ /// value of this is 0.
+ /// </summary>
+ private void Normalize ()
+ {
+ // Normalize length
+ while (length > 0 && data [length-1] == 0) length--;
- if(dividend >= divisor) {
- ulong quotient = dividend / divisor;
- result[resultPos++] = (uint)quotient;
-
- outRemainder.data[pos] = (uint)(dividend % divisor);
+ // Check for zero
+ if (length == 0)
+ length++;
}
- pos--;
-
- while(pos >= 0) {
- //Console.WriteLine(pos);
- dividend = ((ulong)outRemainder.data[pos+1] << 32) + (ulong)outRemainder.data[pos];
- ulong quotient = dividend / divisor;
- result[resultPos++] = (uint)quotient;
-
- outRemainder.data[pos+1] = 0;
- outRemainder.data[pos--] = (uint)(dividend % divisor);
- //Console.WriteLine(">>>> " + bi1);
+ public void Clear ()
+ {
+ for (int i=0; i < length; i++)
+ data [i] = 0x00;
}
- outQuotient.dataLength = resultPos;
- int j = 0;
- for(int i = outQuotient.dataLength - 1; i >= 0; i--, j++)
- outQuotient.data[j] = result[i];
- for(; j < maxLength; j++)
- outQuotient.data[j] = 0;
+ #endregion
- while(outQuotient.dataLength > 1 && outQuotient.data[outQuotient.dataLength-1] == 0)
- outQuotient.dataLength--;
+ #region Object Impl
- if(outQuotient.dataLength == 0)
- outQuotient.dataLength = 1;
+ public override int GetHashCode ()
+ {
+ uint val = 0;
- while(outRemainder.dataLength > 1 && outRemainder.data[outRemainder.dataLength-1] == 0)
- outRemainder.dataLength--;
- }
+ for (uint i = 0; i < this.length; i++)
+ val ^= this.data [i];
- // Overloading of division operator
- public static BigInteger operator / (BigInteger bi1, BigInteger bi2)
- {
- BigInteger quotient = new BigInteger();
- BigInteger remainder = new BigInteger();
-
- int lastPos = maxLength-1;
- bool divisorNeg = false, dividendNeg = false;
-
- if((bi1.data[lastPos] & 0x80000000) != 0) { // bi1 negative
- bi1 = -bi1;
- dividendNeg = true;
- }
- if((bi2.data[lastPos] & 0x80000000) != 0) { // bi2 negative
- bi2 = -bi2;
- divisorNeg = true;
+ return (int)val;
}
- if(bi1 < bi2) {
- return quotient;
+ public override string ToString ()
+ {
+ return ToString (10);
}
- else {
- if(bi2.dataLength == 1)
- singleByteDivide(bi1, bi2, quotient, remainder);
- else
- multiByteDivide(bi1, bi2, quotient, remainder);
+ public override bool Equals (object o)
+ {
+ if (o == null) return false;
+ if (o is int) return (int)o >= 0 && this == (uint)o;
- if(dividendNeg != divisorNeg)
- return -quotient;
-
- return quotient;
+ return Kernel.Compare (this, (BigInteger)o) == 0;
}
- }
- // Overloading of modulus operator
- public static BigInteger operator % (BigInteger bi1, BigInteger bi2)
- {
- BigInteger quotient = new BigInteger();
- BigInteger remainder = new BigInteger(bi1);
+ #endregion
- int lastPos = maxLength-1;
- bool dividendNeg = false;
+ #region Number Theory
- if((bi1.data[lastPos] & 0x80000000) != 0) { // bi1 negative
- bi1 = -bi1;
- dividendNeg = true;
+ public BigInteger GCD (BigInteger bi)
+ {
+ return Kernel.gcd (this, bi);
}
- if((bi2.data[lastPos] & 0x80000000) != 0) // bi2 negative
- bi2 = -bi2;
- if(bi1 < bi2) {
- return remainder;
+ public BigInteger ModInverse (BigInteger modulus)
+ {
+ return Kernel.modInverse (this, modulus);
}
- else {
- if(bi2.dataLength == 1)
- singleByteDivide(bi1, bi2, quotient, remainder);
- else
- multiByteDivide(bi1, bi2, quotient, remainder);
-
- if(dividendNeg)
- return -remainder;
-
- return remainder;
+ public BigInteger ModPow (BigInteger exp, BigInteger n)
+ {
+ ModulusRing mr = new ModulusRing (n);
+ return mr.Pow (this, exp);
}
- }
-
- // Overloading of bitwise AND operator
- public static BigInteger operator & (BigInteger bi1, BigInteger bi2)
- {
- BigInteger result = new BigInteger();
+
+ #endregion
- int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
+ #region Prime Testing
- for(int i = 0; i < len; i++) {
- uint sum = (uint)(bi1.data[i] & bi2.data[i]);
- result.data[i] = sum;
+ public bool IsProbablePrime ()
+ {
+ if (this < smallPrimes [smallPrimes.Length - 1]) {
+ for (int p = 0; p < smallPrimes.Length; p++) {
+ if (this == smallPrimes [p])
+ return true;
+ }
+ }
+ else {
+ for (int p = 0; p < smallPrimes.Length; p++) {
+ if (this % smallPrimes [p] == 0)
+ return false;
+ }
+ }
+ return PrimalityTests.RabinMillerTest (this, Prime.ConfidenceFactor.Medium);
}
- result.dataLength = maxLength;
+ #endregion
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
-
- return result;
- }
+ #region Prime Number Generation
- // Overloading of bitwise OR operator
- public static BigInteger operator | (BigInteger bi1, BigInteger bi2)
- {
- BigInteger result = new BigInteger();
-
- int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
-
- for(int i = 0; i < len; i++) {
- uint sum = (uint)(bi1.data[i] | bi2.data[i]);
- result.data[i] = sum;
+ /// <summary>
+ /// Generates the smallest prime >= bi
+ /// </summary>
+ /// <param name="bi">A BigInteger</param>
+ /// <returns>The smallest prime >= bi. More mathematically, if bi is prime: bi, else Prime [PrimePi [bi] + 1].</returns>
+ public static BigInteger NextHighestPrime (BigInteger bi)
+ {
+ NextPrimeFinder npf = new NextPrimeFinder ();
+ return npf.GenerateNewPrime (0, bi);
}
- result.dataLength = maxLength;
-
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
-
- return result;
- }
-
- // Overloading of bitwise XOR operator
- public static BigInteger operator ^ (BigInteger bi1, BigInteger bi2)
- {
- BigInteger result = new BigInteger();
-
- int len = (bi1.dataLength > bi2.dataLength) ? bi1.dataLength : bi2.dataLength;
-
- for(int i = 0; i < len; i++) {
- uint sum = (uint)(bi1.data[i] ^ bi2.data[i]);
- result.data[i] = sum;
+ public static BigInteger GeneratePseudoPrime (int bits)
+ {
+ SequentialSearchPrimeGeneratorBase sspg = new SequentialSearchPrimeGeneratorBase ();
+ return sspg.GenerateNewPrime (bits);
}
- result.dataLength = maxLength;
+ /// <summary>
+ /// Increments this by two
+ /// </summary>
+ public void Incr2 ()
+ {
+ int i = 0;
- while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
- result.dataLength--;
+ data [0] += 2;
- return result;
- }
+ // If there was no carry, nothing to do
+ if (data [0] < 2) {
- // Returns max(this, bi)
- public BigInteger max (BigInteger bi)
- {
- if(this > bi)
- return (new BigInteger(this));
- else
- return (new BigInteger(bi));
- }
+ // Account for the first carry
+ data [++i]++;
- // Returns min(this, bi)
- public BigInteger min (BigInteger bi)
- {
- if (this < bi)
- return (new BigInteger (this));
- else
- return (new BigInteger (bi));
- }
+ // Keep adding until no carry
+ while (data [i++] == 0x0)
+ data [i]++;
- // Returns the absolute value
- public BigInteger abs ()
- {
- if((this.data[maxLength - 1] & 0x80000000) != 0)
- return (-this);
- else
- return (new BigInteger (this));
- }
-
- // Returns a string representing the BigInteger in base 10.
- public override string ToString ()
- {
- return ToString (10);
- }
-
- // Returns a string representing the BigInteger in sign-and-magnitude
- // format in the specified radix.
- //
- // Example
- // -------
- // If the value of BigInteger is -255 in base 10, then
- // ToString(16) returns "-FF"
- public string ToString (int radix)
- {
- if(radix < 2 || radix > 36)
- throw (new ArgumentException("Radix must be >= 2 and <= 36"));
-
- string charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
- string result = "";
-
- BigInteger a = this;
-
- bool negative = false;
- if((a.data[maxLength-1] & 0x80000000) != 0) {
- negative = true;
- try {
- a = -a;
+ // See if we increased the data length
+ if (length == (uint)i)
+ length++;
}
- catch(Exception) {}
}
- BigInteger quotient = new BigInteger();
- BigInteger remainder = new BigInteger();
- BigInteger biRadix = new BigInteger(radix);
+ #endregion
- if(a.dataLength == 1 && a.data[0] == 0)
- result = "0";
- else {
- while(a.dataLength > 1 || (a.dataLength == 1 && a.data[0] != 0)) {
- singleByteDivide(a, biRadix, quotient, remainder);
+#if INSIDE_CORLIB
+ internal
+#else
+ public
+#endif
+ sealed class ModulusRing {
- if(remainder.data[0] < 10)
- result = remainder.data[0] + result;
- else
- result = charSet[(int)remainder.data[0] - 10] + result;
-
- a = quotient;
- }
- if(negative)
- result = "-" + result;
- }
+ BigInteger mod, constant;
- return result;
- }
+ public ModulusRing (BigInteger modulus)
+ {
+ this.mod = modulus;
+ // calculate constant = b^ (2k) / m
+ uint i = mod.length << 1;
- // Returns a hex string showing the contains of the BigInteger
- //
- // Examples
- // -------
- // 1) If the value of BigInteger is 255 in base 10, then
- // ToHexString() returns "FF"
- //
- // 2) If the value of BigInteger is -255 in base 10, then
- // ToHexString() returns ".....FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF01",
- // which is the 2's complement representation of -255.
- public string ToHexString ()
- {
- string result = data[dataLength - 1].ToString("X");
+ constant = new BigInteger (Sign.Positive, i + 1);
+ constant.data [i] = 0x00000001;
- for(int i = dataLength - 2; i >= 0; i--) {
- result += data[i].ToString("X8");
- }
+ constant = constant / mod;
+ }
- return result;
- }
+ public void BarrettReduction (BigInteger x)
+ {
+ BigInteger n = mod;
+ uint k = n.length,
+ kPlusOne = k+1,
+ kMinusOne = k-1;
- // Modulo Exponentiation
- public BigInteger modPow(BigInteger exp, BigInteger n)
- {
- if((exp.data[maxLength-1] & 0x80000000) != 0)
- throw (new ArithmeticException("Positive exponents only."));
+ // x < mod, so nothing to do.
+ if (x.length < k) return;
- BigInteger resultNum = 1;
- BigInteger tempNum;
- bool thisNegative = false;
+ BigInteger q3;
- if((this.data[maxLength-1] & 0x80000000) != 0) { // negative this
- tempNum = -this % n;
- thisNegative = true;
- }
- else
- tempNum = this % n; // ensures (tempNum * tempNum) < b^(2k)
+ //
+ // Validate pointers
+ //
+ if (x.data.Length < x.length) throw new IndexOutOfRangeException ("x out of range");
- if((n.data[maxLength-1] & 0x80000000) != 0) // negative n
- n = -n;
+ // q1 = x / b^ (k-1)
+ // q2 = q1 * constant
+ // q3 = q2 / b^ (k+1), Needs to be accessed with an offset of kPlusOne
- // calculate constant = b^(2k) / m
- BigInteger constant = new BigInteger ();
+ // TODO: We should the method in HAC p 604 to do this (14.45)
+ q3 = new BigInteger (Sign.Positive, x.length - kMinusOne + constant.length);
+ Kernel.Multiply (x.data, kMinusOne, x.length - kMinusOne, constant.data, 0, constant.length, q3.data, 0);
- int i = n.dataLength << 1;
- constant.data[i] = 0x00000001;
- constant.dataLength = i + 1;
+ // r1 = x mod b^ (k+1)
+ // i.e. keep the lowest (k+1) words
- constant = constant / n;
- int totalBits = exp.bitCount ();
- int count = 0;
+ uint lengthToCopy = (x.length > kPlusOne) ? kPlusOne : x.length;
- // perform squaring and multiply exponentiation
- for(int pos = 0; pos < exp.dataLength; pos++) {
- uint mask = 0x01;
- //Console.WriteLine("pos = " + pos);
+ x.length = lengthToCopy;
+ x.Normalize ();
- for(int index = 0; index < 32; index++) {
- if((exp.data[pos] & mask) != 0)
- resultNum = BarrettReduction(resultNum * tempNum, n, constant);
+ // r2 = (q3 * n) mod b^ (k+1)
+ // partial multiplication of q3 and n
- mask <<= 1;
+ BigInteger r2 = new BigInteger (Sign.Positive, kPlusOne);
+ Kernel.MultiplyMod2p32pmod (q3.data, (int)kPlusOne, (int)q3.length - (int)kPlusOne, n.data, 0, (int)n.length, r2.data, 0, (int)kPlusOne);
- tempNum = BarrettReduction(tempNum * tempNum, n, constant);
+ r2.Normalize ();
+ if (r2 <= x) {
+ Kernel.MinusEq (x, r2);
+ } else {
+ BigInteger val = new BigInteger (Sign.Positive, kPlusOne + 1);
+ val.data [kPlusOne] = 0x00000001;
- if(tempNum.dataLength == 1 && tempNum.data[0] == 1) {
- if(thisNegative && (exp.data[0] & 0x1) != 0) //odd exp
- return -resultNum;
- return resultNum;
+ Kernel.MinusEq (val, r2);
+ Kernel.PlusEq (x, val);
}
- count++;
- if(count == totalBits)
- break;
- }
- }
- if(thisNegative && (exp.data[0] & 0x1) != 0) //odd exp
- return -resultNum;
-
- return resultNum;
- }
-
- // Fast calculation of modular reduction using Barrett's reduction.
- // Requires x < b^(2k), where b is the base. In this case, base is
- // 2^32 (uint).
- // Reference [4]
- private BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant)
- {
- int k = n.dataLength,
- kPlusOne = k+1,
- kMinusOne = k-1;
-
- BigInteger q1 = new BigInteger ();
-
- // q1 = x / b^(k-1)
- for(int i = kMinusOne, j = 0; i < x.dataLength; i++, j++)
- q1.data[j] = x.data[i];
- q1.dataLength = x.dataLength - kMinusOne;
- if(q1.dataLength <= 0)
- q1.dataLength = 1;
-
-
- BigInteger q2 = q1 * constant;
- BigInteger q3 = new BigInteger();
-
- // q3 = q2 / b^(k+1)
- for(int i = kPlusOne, j = 0; i < q2.dataLength; i++, j++)
- q3.data[j] = q2.data[i];
- q3.dataLength = q2.dataLength - kPlusOne;
- if(q3.dataLength <= 0)
- q3.dataLength = 1;
-
- // r1 = x mod b^(k+1)
- // i.e. keep the lowest (k+1) words
- BigInteger r1 = new BigInteger();
- int lengthToCopy = (x.dataLength > kPlusOne) ? kPlusOne : x.dataLength;
- for(int i = 0; i < lengthToCopy; i++)
- r1.data[i] = x.data[i];
- r1.dataLength = lengthToCopy;
-
- // r2 = (q3 * n) mod b^(k+1)
- // partial multiplication of q3 and n
-
- BigInteger r2 = new BigInteger();
- for(int i = 0; i < q3.dataLength; i++) {
- if(q3.data[i] == 0) continue;
-
- ulong mcarry = 0;
- int t = i;
- for(int j = 0; j < n.dataLength && t < kPlusOne; j++, t++) {
- // t = i + j
- ulong val = ((ulong)q3.data[i] * (ulong)n.data[j]) +
- (ulong)r2.data[t] + mcarry;
-
- r2.data[t] = (uint)(val & 0xFFFFFFFF);
- mcarry = (val >> 32);
+ while (x >= n)
+ Kernel.MinusEq (x, n);
}
- if(t < kPlusOne)
- r2.data[t] = (uint)mcarry;
- }
- r2.dataLength = kPlusOne;
- while(r2.dataLength > 1 && r2.data[r2.dataLength-1] == 0)
- r2.dataLength--;
-
- r1 -= r2;
- if((r1.data[maxLength-1] & 0x80000000) != 0) { // negative
- BigInteger val = new BigInteger();
- val.data[kPlusOne] = 0x00000001;
- val.dataLength = kPlusOne + 1;
- r1 += val;
- }
-
- while(r1 >= n)
- r1 -= n;
+ public BigInteger Multiply (BigInteger a, BigInteger b)
+ {
+ if (a == 0 || b == 0) return 0;
- return r1;
- }
-
- // Returns gcd(this, bi)
- public BigInteger gcd(BigInteger bi)
- {
- BigInteger x;
- BigInteger y;
-
- if((data[maxLength-1] & 0x80000000) != 0) // negative
- x = -this;
- else
- x = this;
-
- if((bi.data[maxLength-1] & 0x80000000) != 0) // negative
- y = -bi;
- else
- y = bi;
+ if (a.length >= mod.length << 1)
+ a %= mod;
- BigInteger g = y;
+ if (b.length >= mod.length << 1)
+ b %= mod;
- while(x.dataLength > 1 || (x.dataLength == 1 && x.data[0] != 0)) {
- g = x;
- x = y % x;
- y = g;
- }
-
- return g;
- }
+ if (a.length >= mod.length)
+ BarrettReduction (a);
- // Populates "this" with the specified amount of random bits
- public void genRandomBits (int bits)
- {
- genRandomBits (bits, new BigRandom ());
- }
+ if (b.length >= mod.length)
+ BarrettReduction (b);
- public void genRandomBits (int bits, BigRandom rng)
- {
- int dwords = bits >> 5;
- int remBits = bits & 0x1F;
+ BigInteger ret = new BigInteger (a * b);
+ BarrettReduction (ret);
- if (remBits != 0)
- dwords++;
-
- if (dwords > maxLength)
- throw (new ArithmeticException("Number of required bits > maxLength."));
+ return ret;
+ }
- rng.Get (data);
- for (int i = dwords; i < maxLength; i++)
- data[i] = 0;
+ public BigInteger Difference (BigInteger a, BigInteger b)
+ {
+ Sign cmp = Kernel.Compare (a, b);
+ BigInteger diff;
+
+ switch (cmp) {
+ case Sign.Zero:
+ return 0;
+ case Sign.Positive:
+ diff = a - b; break;
+ case Sign.Negative:
+ diff = b - a; break;
+ default:
+ throw new Exception ();
+ }
- if (remBits != 0) {
- uint mask = (uint)(0x01 << (remBits-1));
- data[dwords-1] |= mask;
+ if (diff >= mod) {
+ if (diff.length >= mod.length << 1)
+ diff %= mod;
+ else
+ BarrettReduction (diff);
+ }
+ if (cmp == Sign.Negative)
+ diff = mod - diff;
+ return diff;
+ }
- mask = (uint)(0xFFFFFFFF >> (32 - remBits));
- data[dwords-1] &= mask;
- }
- else
- data[dwords-1] |= 0x80000000;
+ public BigInteger Pow (BigInteger b, BigInteger exp)
+ {
+ if ((mod.data [0] & 1) == 1) return OddPow (b, exp);
+ else return EvenPow (b, exp);
+ }
+
+ public BigInteger EvenPow (BigInteger b, BigInteger exp)
+ {
+ BigInteger resultNum = new BigInteger ((BigInteger)1, mod.length << 1);
+ BigInteger tempNum = new BigInteger (b % mod, mod.length << 1); // ensures (tempNum * tempNum) < b^ (2k)
- dataLength = dwords;
+ uint totalBits = (uint)exp.BitCount ();
- if (dataLength == 0)
- dataLength = 1;
- }
+ uint [] wkspace = new uint [mod.length << 1];
- // Returns the position of the most significant bit in the BigInteger.
- // Eg. The result is 0, if the value of BigInteger is 0...0000 0000
- // The result is 1, if the value of BigInteger is 0...0000 0001
- // The result is 2, if the value of BigInteger is 0...0000 0010
- // The result is 2, if the value of BigInteger is 0...0000 0011
- public int bitCount ()
- {
- while(dataLength > 1 && data[dataLength-1] == 0)
- dataLength--;
+ // perform squaring and multiply exponentiation
+ for (uint pos = 0; pos < totalBits; pos++) {
+ if (exp.TestBit (pos)) {
- uint value = data[dataLength - 1];
- uint mask = 0x80000000;
- int bits = 32;
+ Array.Clear (wkspace, 0, wkspace.Length);
+ Kernel.Multiply (resultNum.data, 0, resultNum.length, tempNum.data, 0, tempNum.length, wkspace, 0);
+ resultNum.length += tempNum.length;
+ uint [] t = wkspace;
+ wkspace = resultNum.data;
+ resultNum.data = t;
- while(bits > 0 && (value & mask) == 0) {
- bits--;
- mask >>= 1;
- }
- bits += ((dataLength - 1) << 5);
+ BarrettReduction (resultNum);
+ }
- return bits;
- }
+ Kernel.SquarePositive (tempNum, ref wkspace);
+ BarrettReduction (tempNum);
- // Probabilistic prime test based on Fermat's little theorem
- //
- // for any a < p (p does not divide a) if
- // a^(p-1) mod p != 1 then p is not prime.
- //
- // Otherwise, p is probably prime (pseudoprime to the chosen base).
- //
- // Returns
- // -------
- // True if "this" is a pseudoprime to randomly chosen
- // bases. The number of chosen bases is given by the "confidence"
- // parameter.
- //
- // False if "this" is definitely NOT prime.
- //
- // Note - this method is fast but fails for Carmichael numbers except
- // when the randomly chosen base is a factor of the number.
- public bool FermatLittleTest (int confidence)
- {
- BigInteger thisVal;
- if((this.data[maxLength-1] & 0x80000000) != 0) // negative
- thisVal = -this;
- else
- thisVal = this;
-
- if(thisVal.dataLength == 1) {
- // test small numbers
- if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
- return false;
- else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
- return true;
- }
+ if (tempNum == 1) {
+ return resultNum;
+ }
+ }
- if((thisVal.data[0] & 0x1) == 0) // even numbers
- return false;
+ return resultNum;
+ }
- int bits = thisVal.bitCount();
- BigInteger a = new BigInteger();
- BigInteger p_sub1 = thisVal - (new BigInteger(1));
+ private BigInteger OddPow (BigInteger b, BigInteger exp)
+ {
+ BigInteger resultNum = new BigInteger (Montgomery.ToMont (1, mod), mod.length << 1);
+ BigInteger tempNum = new BigInteger (Montgomery.ToMont (b, mod), mod.length << 1); // ensures (tempNum * tempNum) < b^ (2k)
+ uint mPrime = Montgomery.Inverse (mod.data [0]);
+ uint totalBits = (uint)exp.BitCount ();
- for(int round = 0; round < confidence; round++) {
- bool done = false;
+ uint [] wkspace = new uint [mod.length << 1];
- while(!done) { // generate a < n
- int testBits = 0;
+ // perform squaring and multiply exponentiation
+ for (uint pos = 0; pos < totalBits; pos++) {
+ if (exp.TestBit (pos)) {
- // make sure "a" has at least 2 bits
- while(testBits < 2)
- testBits = rng.GetInt (bits);
+ Array.Clear (wkspace, 0, wkspace.Length);
+ Kernel.Multiply (resultNum.data, 0, resultNum.length, tempNum.data, 0, tempNum.length, wkspace, 0);
+ resultNum.length += tempNum.length;
+ uint [] t = wkspace;
+ wkspace = resultNum.data;
+ resultNum.data = t;
- a.genRandomBits (testBits);
+ Montgomery.Reduce (resultNum, mod, mPrime);
+ }
- int byteLen = a.dataLength;
+ Kernel.SquarePositive (tempNum, ref wkspace);
+ Montgomery.Reduce (tempNum, mod, mPrime);
+ }
- // make sure "a" is not 0
- if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
- done = true;
+ Montgomery.Reduce (resultNum, mod, mPrime);
+ return resultNum;
}
- // check whether a factor exists (fix for version 1.03)
- BigInteger gcdTest = a.gcd(thisVal);
- if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
- return false;
+ #region Pow Small Base
+
+ // TODO: Make tests for this, not really needed b/c prime stuff
+ // checks it, but still would be nice
+#if !INSIDE_CORLIB
+ [CLSCompliant (false)]
+#endif
+ public BigInteger Pow (uint b, BigInteger exp)
+ {
+// if (b != 2) {
+ if ((mod.data [0] & 1) == 1)
+ return OddPow (b, exp);
+ else
+ return EvenPow (b, exp);
+/* buggy in some cases (like the well tested primes)
+ } else {
+ if ((mod.data [0] & 1) == 1)
+ return OddModTwoPow (exp);
+ else
+ return EvenModTwoPow (exp);
+ }*/
+ }
- // calculate a^(p-1) mod p
- BigInteger expResult = a.modPow(p_sub1, thisVal);
+ private unsafe BigInteger OddPow (uint b, BigInteger exp)
+ {
+ exp.Normalize ();
+ uint [] wkspace = new uint [mod.length << 1 + 1];
+
+ BigInteger resultNum = Montgomery.ToMont ((BigInteger)b, this.mod);
+ resultNum = new BigInteger (resultNum, mod.length << 1 +1);
+
+ uint mPrime = Montgomery.Inverse (mod.data [0]);
+
+ uint pos = (uint)exp.BitCount () - 2;
+
+ //
+ // We know that the first itr will make the val b
+ //
+
+ do {
+ //
+ // r = r ^ 2 % m
+ //
+ Kernel.SquarePositive (resultNum, ref wkspace);
+ resultNum = Montgomery.Reduce (resultNum, mod, mPrime);
+
+ if (exp.TestBit (pos)) {
+
+ //
+ // r = r * b % m
+ //
+
+ // TODO: Is Unsafe really speeding things up?
+ fixed (uint* u = resultNum.data) {
+
+ uint i = 0;
+ ulong mc = 0;
+
+ do {
+ mc += (ulong)u [i] * (ulong)b;
+ u [i] = (uint)mc;
+ mc >>= 32;
+ } while (++i < resultNum.length);
+
+ if (resultNum.length < mod.length) {
+ if (mc != 0) {
+ u [i] = (uint)mc;
+ resultNum.length++;
+ while (resultNum >= mod)
+ Kernel.MinusEq (resultNum, mod);
+ }
+ } else if (mc != 0) {
+
+ //
+ // First, we estimate the quotient by dividing
+ // the first part of each of the numbers. Then
+ // we correct this, if necessary, with a subtraction.
+ //
+
+ uint cc = (uint)mc;
+
+ // We would rather have this estimate overshoot,
+ // so we add one to the divisor
+ uint divEstimate;
+ if (mod.data [mod.length - 1] < UInt32.MaxValue) {
+ divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) /
+ (mod.data [mod.length-1] + 1));
+ }
+ else {
+ // guess but don't divide by 0
+ divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) /
+ (mod.data [mod.length-1]));
+ }
+
+ uint t;
+
+ i = 0;
+ mc = 0;
+ do {
+ mc += (ulong)mod.data [i] * (ulong)divEstimate;
+ t = u [i];
+ u [i] -= (uint)mc;
+ mc >>= 32;
+ if (u [i] > t) mc++;
+ i++;
+ } while (i < resultNum.length);
+ cc -= (uint)mc;
+
+ if (cc != 0) {
+
+ uint sc = 0, j = 0;
+ uint [] s = mod.data;
+ do {
+ uint a = s [j];
+ if (((a += sc) < sc) | ((u [j] -= a) > ~a)) sc = 1;
+ else sc = 0;
+ j++;
+ } while (j < resultNum.length);
+ cc -= sc;
+ }
+ while (resultNum >= mod)
+ Kernel.MinusEq (resultNum, mod);
+ } else {
+ while (resultNum >= mod)
+ Kernel.MinusEq (resultNum, mod);
+ }
+ }
+ }
+ } while (pos-- > 0);
- int resultLen = expResult.dataLength;
+ resultNum = Montgomery.Reduce (resultNum, mod, mPrime);
+ return resultNum;
- // is NOT prime is a^(p-1) mod p != 1
+ }
+
+ private unsafe BigInteger EvenPow (uint b, BigInteger exp)
+ {
+ exp.Normalize ();
+ uint [] wkspace = new uint [mod.length << 1 + 1];
+ BigInteger resultNum = new BigInteger ((BigInteger)b, mod.length << 1 + 1);
+
+ uint pos = (uint)exp.BitCount () - 2;
+
+ //
+ // We know that the first itr will make the val b
+ //
+
+ do {
+ //
+ // r = r ^ 2 % m
+ //
+ Kernel.SquarePositive (resultNum, ref wkspace);
+ if (!(resultNum.length < mod.length))
+ BarrettReduction (resultNum);
+
+ if (exp.TestBit (pos)) {
+
+ //
+ // r = r * b % m
+ //
+
+ // TODO: Is Unsafe really speeding things up?
+ fixed (uint* u = resultNum.data) {
+
+ uint i = 0;
+ ulong mc = 0;
+
+ do {
+ mc += (ulong)u [i] * (ulong)b;
+ u [i] = (uint)mc;
+ mc >>= 32;
+ } while (++i < resultNum.length);
+
+ if (resultNum.length < mod.length) {
+ if (mc != 0) {
+ u [i] = (uint)mc;
+ resultNum.length++;
+ while (resultNum >= mod)
+ Kernel.MinusEq (resultNum, mod);
+ }
+ } else if (mc != 0) {
+
+ //
+ // First, we estimate the quotient by dividing
+ // the first part of each of the numbers. Then
+ // we correct this, if necessary, with a subtraction.
+ //
+
+ uint cc = (uint)mc;
+
+ // We would rather have this estimate overshoot,
+ // so we add one to the divisor
+ uint divEstimate = (uint) ((((ulong)cc << 32) | (ulong) u [i -1]) /
+ (mod.data [mod.length-1] + 1));
+
+ uint t;
+
+ i = 0;
+ mc = 0;
+ do {
+ mc += (ulong)mod.data [i] * (ulong)divEstimate;
+ t = u [i];
+ u [i] -= (uint)mc;
+ mc >>= 32;
+ if (u [i] > t) mc++;
+ i++;
+ } while (i < resultNum.length);
+ cc -= (uint)mc;
+
+ if (cc != 0) {
+
+ uint sc = 0, j = 0;
+ uint [] s = mod.data;
+ do {
+ uint a = s [j];
+ if (((a += sc) < sc) | ((u [j] -= a) > ~a)) sc = 1;
+ else sc = 0;
+ j++;
+ } while (j < resultNum.length);
+ cc -= sc;
+ }
+ while (resultNum >= mod)
+ Kernel.MinusEq (resultNum, mod);
+ } else {
+ while (resultNum >= mod)
+ Kernel.MinusEq (resultNum, mod);
+ }
+ }
+ }
+ } while (pos-- > 0);
- if(resultLen > 1 || (resultLen == 1 && expResult.data[0] != 1)) {
- //Console.WriteLine("a = " + a.ToString());
- return false;
+ return resultNum;
}
- }
- return true;
- }
+/* known to be buggy in some cases
+ private unsafe BigInteger EvenModTwoPow (BigInteger exp)
+ {
+ exp.Normalize ();
+ uint [] wkspace = new uint [mod.length << 1 + 1];
- // Probabilistic prime test based on Rabin-Miller's
- //
- // for any p > 0 with p - 1 = 2^s * t
- //
- // p is probably prime (strong pseudoprime) if for any a < p,
- // 1) a^t mod p = 1 or
- // 2) a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
- //
- // Otherwise, p is composite.
- //
- // Returns
- // -------
- // True if "this" is a strong pseudoprime to randomly chosen
- // bases. The number of chosen bases is given by the "confidence"
- // parameter.
- //
- // False if "this" is definitely NOT prime.
- public bool RabinMillerTest(int confidence)
- {
- BigInteger thisVal;
- if((this.data[maxLength-1] & 0x80000000) != 0) // negative
- thisVal = -this;
- else
- thisVal = this;
-
- if(thisVal.dataLength == 1) {
- // test small numbers
- if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
- return false;
- else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
- return true;
- }
+ BigInteger resultNum = new BigInteger (2, mod.length << 1 +1);
- if((thisVal.data[0] & 0x1) == 0) // even numbers
- return false;
+ uint value = exp.data [exp.length - 1];
+ uint mask = 0x80000000;
- // calculate values of s and t
- BigInteger p_sub1 = thisVal - (new BigInteger(1));
- int s = 0;
+ // Find the first bit of the exponent
+ while ((value & mask) == 0)
+ mask >>= 1;
- for(int index = 0; index < p_sub1.dataLength; index++) {
- uint mask = 0x01;
+ //
+ // We know that the first itr will make the val 2,
+ // so eat one bit of the exponent
+ //
+ mask >>= 1;
- for(int i = 0; i < 32; i++) {
- if((p_sub1.data[index] & mask) != 0) {
- index = p_sub1.dataLength; // to break the outer loop
- break;
- }
- mask <<= 1;
- s++;
+ uint wPos = exp.length - 1;
+
+ do {
+ value = exp.data [wPos];
+ do {
+ Kernel.SquarePositive (resultNum, ref wkspace);
+ if (resultNum.length >= mod.length)
+ BarrettReduction (resultNum);
+
+ if ((value & mask) != 0) {
+ //
+ // resultNum = (resultNum * 2) % mod
+ //
+
+ fixed (uint* u = resultNum.data) {
+ //
+ // Double
+ //
+ uint* uu = u;
+ uint* uuE = u + resultNum.length;
+ uint x, carry = 0;
+ while (uu < uuE) {
+ x = *uu;
+ *uu = (x << 1) | carry;
+ carry = x >> (32 - 1);
+ uu++;
+ }
+
+ // subtraction inlined because we know it is square
+ if (carry != 0 || resultNum >= mod) {
+ uu = u;
+ uint c = 0;
+ uint [] s = mod.data;
+ uint i = 0;
+ do {
+ uint a = s [i];
+ if (((a += c) < c) | ((* (uu++) -= a) > ~a))
+ c = 1;
+ else
+ c = 0;
+ i++;
+ } while (uu < uuE);
+ }
+ }
+ }
+ } while ((mask >>= 1) > 0);
+ mask = 0x80000000;
+ } while (wPos-- > 0);
+
+ return resultNum;
}
- }
-
- BigInteger t = p_sub1 >> s;
- int bits = thisVal.bitCount();
- BigInteger a = new BigInteger();
+ private unsafe BigInteger OddModTwoPow (BigInteger exp)
+ {
+
+ uint [] wkspace = new uint [mod.length << 1 + 1];
+
+ BigInteger resultNum = Montgomery.ToMont ((BigInteger)2, this.mod);
+ resultNum = new BigInteger (resultNum, mod.length << 1 +1);
+
+ uint mPrime = Montgomery.Inverse (mod.data [0]);
+
+ //
+ // TODO: eat small bits, the ones we can do with no modular reduction
+ //
+ uint pos = (uint)exp.BitCount () - 2;
+
+ do {
+ Kernel.SquarePositive (resultNum, ref wkspace);
+ resultNum = Montgomery.Reduce (resultNum, mod, mPrime);
+
+ if (exp.TestBit (pos)) {
+ //
+ // resultNum = (resultNum * 2) % mod
+ //
+
+ fixed (uint* u = resultNum.data) {
+ //
+ // Double
+ //
+ uint* uu = u;
+ uint* uuE = u + resultNum.length;
+ uint x, carry = 0;
+ while (uu < uuE) {
+ x = *uu;
+ *uu = (x << 1) | carry;
+ carry = x >> (32 - 1);
+ uu++;
+ }
+
+ // subtraction inlined because we know it is square
+ if (carry != 0 || resultNum >= mod) {
+ fixed (uint* s = mod.data) {
+ uu = u;
+ uint c = 0;
+ uint* ss = s;
+ do {
+ uint a = *ss++;
+ if (((a += c) < c) | ((* (uu++) -= a) > ~a))
+ c = 1;
+ else
+ c = 0;
+ } while (uu < uuE);
+ }
+ }
+ }
+ }
+ } while (pos-- > 0);
- for(int round = 0; round < confidence; round++) {
- bool done = false;
+ resultNum = Montgomery.Reduce (resultNum, mod, mPrime);
+ return resultNum;
+ }
+*/
+ #endregion
+ }
- while(!done) { // generate a < n
- int testBits = 0;
+ internal sealed class Montgomery {
- // make sure "a" has at least 2 bits
- while(testBits < 2)
- testBits = rng.GetInt (bits);
+ private Montgomery ()
+ {
+ }
- a.genRandomBits (testBits);
+ public static uint Inverse (uint n)
+ {
+ uint y = n, z;
- int byteLen = a.dataLength;
+ while ((z = n * y) != 1)
+ y *= 2 - z;
- // make sure "a" is not 0
- if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
- done = true;
+ return (uint)-y;
}
- // check whether a factor exists (fix for version 1.03)
- BigInteger gcdTest = a.gcd(thisVal);
- if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
- return false;
-
- BigInteger b = a.modPow(t, thisVal);
+ public static BigInteger ToMont (BigInteger n, BigInteger m)
+ {
+ n.Normalize (); m.Normalize ();
- /*
- Console.WriteLine("a = " + a.ToString(10));
- Console.WriteLine("b = " + b.ToString(10));
- Console.WriteLine("t = " + t.ToString(10));
- Console.WriteLine("s = " + s);
- */
+ n <<= (int)m.length * 32;
+ n %= m;
+ return n;
+ }
- bool result = false;
+ public static unsafe BigInteger Reduce (BigInteger n, BigInteger m, uint mPrime)
+ {
+ BigInteger A = n;
+ fixed (uint* a = A.data, mm = m.data) {
+ for (uint i = 0; i < m.length; i++) {
+ // The mod here is taken care of by the CPU,
+ // since the multiply will overflow.
+ uint u_i = a [0] * mPrime /* % 2^32 */;
+
+ //
+ // A += u_i * m;
+ // A >>= 32
+ //
+
+ // mP = Position in mod
+ // aSP = the source of bits from a
+ // aDP = destination for bits
+ uint* mP = mm, aSP = a, aDP = a;
+
+ ulong c = (ulong)u_i * ((ulong)*(mP++)) + *(aSP++);
+ c >>= 32;
+ uint j = 1;
+
+ // Multiply and add
+ for (; j < m.length; j++) {
+ c += (ulong)u_i * (ulong)*(mP++) + *(aSP++);
+ *(aDP++) = (uint)c;
+ c >>= 32;
+ }
+
+ // Account for carry
+ // TODO: use a better loop here, we dont need the ulong stuff
+ for (; j < A.length; j++) {
+ c += *(aSP++);
+ *(aDP++) = (uint)c;
+ c >>= 32;
+ if (c == 0) {j++; break;}
+ }
+ // Copy the rest
+ for (; j < A.length; j++) {
+ *(aDP++) = *(aSP++);
+ }
+
+ *(aDP++) = (uint)c;
+ }
- if(b.dataLength == 1 && b.data[0] == 1) // a^t mod p = 1
- result = true;
+ while (A.length > 1 && a [A.length-1] == 0) A.length--;
- for(int j = 0; result == false && j < s; j++) {
- if(b == p_sub1) { // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
- result = true;
- break;
}
+ if (A >= m) Kernel.MinusEq (A, m);
- b = (b * b) % thisVal;
+ return A;
}
+#if _NOT_USED_
+ public static BigInteger Reduce (BigInteger n, BigInteger m)
+ {
+ return Reduce (n, m, Inverse (m.data [0]));
+ }
+#endif
+ }
+
+ /// <summary>
+ /// Low level functions for the BigInteger
+ /// </summary>
+ private sealed class Kernel {
+
+ #region Addition/Subtraction
+
+ /// <summary>
+ /// Adds two numbers with the same sign.
+ /// </summary>
+ /// <param name="bi1">A BigInteger</param>
+ /// <param name="bi2">A BigInteger</param>
+ /// <returns>bi1 + bi2</returns>
+ public static BigInteger AddSameSign (BigInteger bi1, BigInteger bi2)
+ {
+ uint [] x, y;
+ uint yMax, xMax, i = 0;
+
+ // x should be bigger
+ if (bi1.length < bi2.length) {
+ x = bi2.data;
+ xMax = bi2.length;
+ y = bi1.data;
+ yMax = bi1.length;
+ } else {
+ x = bi1.data;
+ xMax = bi1.length;
+ y = bi2.data;
+ yMax = bi2.length;
+ }
+
+ BigInteger result = new BigInteger (Sign.Positive, xMax + 1);
- if(result == false)
- return false;
- }
- return true;
- }
-
- // Probabilistic prime test based on Solovay-Strassen (Euler Criterion)
- //
- // p is probably prime if for any a < p (a is not multiple of p),
- // a^((p-1)/2) mod p = J(a, p)
- //
- // where J is the Jacobi symbol.
- //
- // Otherwise, p is composite.
- //
- // Returns
- // -------
- // True if "this" is a Euler pseudoprime to randomly chosen
- // bases. The number of chosen bases is given by the "confidence"
- // parameter.
- //
- // False if "this" is definitely NOT prime.
- public bool SolovayStrassenTest(int confidence)
- {
- BigInteger thisVal;
- if((this.data[maxLength-1] & 0x80000000) != 0) // negative
- thisVal = -this;
- else
- thisVal = this;
-
- if(thisVal.dataLength == 1) {
- // test small numbers
- if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
- return false;
- else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
- return true;
- }
+ uint [] r = result.data;
- if((thisVal.data[0] & 0x1) == 0) // even numbers
- return false;
+ ulong sum = 0;
- int bits = thisVal.bitCount();
- BigInteger a = new BigInteger();
- BigInteger p_sub1 = thisVal - 1;
- BigInteger p_sub1_shift = p_sub1 >> 1;
+ // Add common parts of both numbers
+ do {
+ sum = ((ulong)x [i]) + ((ulong)y [i]) + sum;
+ r [i] = (uint)sum;
+ sum >>= 32;
+ } while (++i < yMax);
- for(int round = 0; round < confidence; round++) {
- bool done = false;
+ // Copy remainder of longer number while carry propagation is required
+ bool carry = (sum != 0);
- while(!done) { // generate a < n
- int testBits = 0;
+ if (carry) {
- // make sure "a" has at least 2 bits
- while(testBits < 2)
- testBits = rng.GetInt (bits);
+ if (i < xMax) {
+ do
+ carry = ((r [i] = x [i] + 1) == 0);
+ while (++i < xMax && carry);
+ }
- a.genRandomBits (testBits);
+ if (carry) {
+ r [i] = 1;
+ result.length = ++i;
+ return result;
+ }
+ }
- int byteLen = a.dataLength;
+ // Copy the rest
+ if (i < xMax) {
+ do
+ r [i] = x [i];
+ while (++i < xMax);
+ }
- // make sure "a" is not 0
- if(byteLen > 1 || (byteLen == 1 && a.data[0] != 1))
- done = true;
+ result.Normalize ();
+ return result;
}
- // check whether a factor exists (fix for version 1.03)
- BigInteger gcdTest = a.gcd(thisVal);
- if(gcdTest.dataLength == 1 && gcdTest.data[0] != 1)
- return false;
+ public static BigInteger Subtract (BigInteger big, BigInteger small)
+ {
+ BigInteger result = new BigInteger (Sign.Positive, big.length);
- // calculate a^((p-1)/2) mod p
+ uint [] r = result.data, b = big.data, s = small.data;
+ uint i = 0, c = 0;
- BigInteger expResult = a.modPow(p_sub1_shift, thisVal);
- if(expResult == p_sub1)
- expResult = -1;
+ do {
- // calculate Jacobi symbol
- BigInteger jacob = Jacobi(a, thisVal);
+ uint x = s [i];
+ if (((x += c) < c) | ((r [i] = b [i] - x) > ~x))
+ c = 1;
+ else
+ c = 0;
- //Console.WriteLine("a = " + a.ToString(10) + " b = " + thisVal.ToString(10));
- //Console.WriteLine("expResult = " + expResult.ToString(10) + " Jacob = " + jacob.ToString(10));
+ } while (++i < small.length);
- // if they are different then it is not prime
- if(expResult != jacob)
- return false;
- }
+ if (i == big.length) goto fixup;
- return true;
- }
+ if (c == 1) {
+ do
+ r [i] = b [i] - 1;
+ while (b [i++] == 0 && i < big.length);
- // Implementation of the Lucas Strong Pseudo Prime test.
- //
- // Let n be an odd number with gcd(n,D) = 1, and n - J(D, n) = 2^s * d
- // with d odd and s >= 0.
- //
- // If Ud mod n = 0 or V2^r*d mod n = 0 for some 0 <= r < s, then n
- // is a strong Lucas pseudoprime with parameters (P, Q). We select
- // P and Q based on Selfridge.
- //
- // Returns True if number is a strong Lucus pseudo prime.
- // Otherwise, returns False indicating that number is composite.
- public bool LucasStrongTest()
- {
- BigInteger thisVal;
- if((this.data[maxLength-1] & 0x80000000) != 0) // negative
- thisVal = -this;
- else
- thisVal = this;
-
- if(thisVal.dataLength == 1) {
- // test small numbers
- if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
- return false;
- else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
- return true;
- }
+ if (i == big.length) goto fixup;
+ }
- if((thisVal.data[0] & 0x1) == 0) // even numbers
- return false;
+ do
+ r [i] = b [i];
+ while (++i < big.length);
- return LucasStrongTestHelper(thisVal);
- }
+ fixup:
- private bool LucasStrongTestHelper(BigInteger thisVal)
- {
- // Do the test (selects D based on Selfridge)
- // Let D be the first element of the sequence
- // 5, -7, 9, -11, 13, ... for which J(D,n) = -1
- // Let P = 1, Q = (1-D) / 4
+ result.Normalize ();
+ return result;
+ }
- long D = 5, sign = -1, dCount = 0;
- bool done = false;
+ public static void MinusEq (BigInteger big, BigInteger small)
+ {
+ uint [] b = big.data, s = small.data;
+ uint i = 0, c = 0;
- while(!done) {
- int Jresult = BigInteger.Jacobi(D, thisVal);
+ do {
+ uint x = s [i];
+ if (((x += c) < c) | ((b [i] -= x) > ~x))
+ c = 1;
+ else
+ c = 0;
+ } while (++i < small.length);
- if(Jresult == -1)
- done = true; // J(D, this) = 1
- else {
- if(Jresult == 0 && System.Math.Abs(D) < thisVal) // divisor found
- return false;
+ if (i == big.length) goto fixup;
- if(dCount == 20) {
- // check for square
- BigInteger root = thisVal.sqrt();
- if(root * root == thisVal)
- return false;
+ if (c == 1) {
+ do
+ b [i]--;
+ while (b [i++] == 0 && i < big.length);
}
- //Console.WriteLine(D);
- D = (System.Math.Abs(D) + 2) * sign;
- sign = -sign;
- }
- dCount++;
- }
-
- long Q = (1 - D) >> 2;
+ fixup:
- /*
- Console.WriteLine("D = " + D);
- Console.WriteLine("Q = " + Q);
- Console.WriteLine("(n,D) = " + thisVal.gcd(D));
- Console.WriteLine("(n,Q) = " + thisVal.gcd(Q));
- Console.WriteLine("J(D|n) = " + BigInteger.Jacobi(D, thisVal));
- */
+ // Normalize length
+ while (big.length > 0 && big.data [big.length-1] == 0) big.length--;
- BigInteger p_add1 = thisVal + 1;
- int s = 0;
+ // Check for zero
+ if (big.length == 0)
+ big.length++;
- for(int index = 0; index < p_add1.dataLength; index++) {
- uint mask = 0x01;
+ }
- for(int i = 0; i < 32; i++) {
- if((p_add1.data[index] & mask) != 0) {
- index = p_add1.dataLength; // to break the outer loop
- break;
+ public static void PlusEq (BigInteger bi1, BigInteger bi2)
+ {
+ uint [] x, y;
+ uint yMax, xMax, i = 0;
+ bool flag = false;
+
+ // x should be bigger
+ if (bi1.length < bi2.length){
+ flag = true;
+ x = bi2.data;
+ xMax = bi2.length;
+ y = bi1.data;
+ yMax = bi1.length;
+ } else {
+ x = bi1.data;
+ xMax = bi1.length;
+ y = bi2.data;
+ yMax = bi2.length;
}
- mask <<= 1;
- s++;
- }
- }
- BigInteger t = p_add1 >> s;
+ uint [] r = bi1.data;
- // calculate constant = b^(2k) / m
- // for Barrett Reduction
- BigInteger constant = new BigInteger();
+ ulong sum = 0;
- int nLen = thisVal.dataLength << 1;
- constant.data[nLen] = 0x00000001;
- constant.dataLength = nLen + 1;
+ // Add common parts of both numbers
+ do {
+ sum += ((ulong)x [i]) + ((ulong)y [i]);
+ r [i] = (uint)sum;
+ sum >>= 32;
+ } while (++i < yMax);
- constant = constant / thisVal;
+ // Copy remainder of longer number while carry propagation is required
+ bool carry = (sum != 0);
- BigInteger[] lucas = LucasSequenceHelper(1, Q, t, thisVal, constant, 0);
- bool isPrime = false;
+ if (carry){
- if((lucas[0].dataLength == 1 && lucas[0].data[0] == 0) ||
- (lucas[1].dataLength == 1 && lucas[1].data[0] == 0)) {
- // u(t) = 0 or V(t) = 0
- isPrime = true;
- }
+ if (i < xMax) {
+ do
+ carry = ((r [i] = x [i] + 1) == 0);
+ while (++i < xMax && carry);
+ }
- for(int i = 1; i < s; i++) {
- if(!isPrime) {
- // doubling of index
- lucas[1] = thisVal.BarrettReduction(lucas[1] * lucas[1], thisVal, constant);
- lucas[1] = (lucas[1] - (lucas[2] << 1)) % thisVal;
+ if (carry) {
+ r [i] = 1;
+ bi1.length = ++i;
+ return;
+ }
+ }
- //lucas[1] = ((lucas[1] * lucas[1]) - (lucas[2] << 1)) % thisVal;
+ // Copy the rest
+ if (flag && i < xMax - 1) {
+ do
+ r [i] = x [i];
+ while (++i < xMax);
+ }
- if((lucas[1].dataLength == 1 && lucas[1].data[0] == 0))
- isPrime = true;
+ bi1.length = xMax + 1;
+ bi1.Normalize ();
}
- lucas[2] = thisVal.BarrettReduction(lucas[2] * lucas[2], thisVal, constant); //Q^k
- }
-
+ #endregion
+
+ #region Compare
+
+ /// <summary>
+ /// Compares two BigInteger
+ /// </summary>
+ /// <param name="bi1">A BigInteger</param>
+ /// <param name="bi2">A BigInteger</param>
+ /// <returns>The sign of bi1 - bi2</returns>
+ public static Sign Compare (BigInteger bi1, BigInteger bi2)
+ {
+ //
+ // Step 1. Compare the lengths
+ //
+ uint l1 = bi1.length, l2 = bi2.length;
+
+ while (l1 > 0 && bi1.data [l1-1] == 0) l1--;
+ while (l2 > 0 && bi2.data [l2-1] == 0) l2--;
+
+ if (l1 == 0 && l2 == 0) return Sign.Zero;
+
+ // bi1 len < bi2 len
+ if (l1 < l2) return Sign.Negative;
+ // bi1 len > bi2 len
+ else if (l1 > l2) return Sign.Positive;
+
+ //
+ // Step 2. Compare the bits
+ //
+
+ uint pos = l1 - 1;
+
+ while (pos != 0 && bi1.data [pos] == bi2.data [pos]) pos--;
+
+ if (bi1.data [pos] < bi2.data [pos])
+ return Sign.Negative;
+ else if (bi1.data [pos] > bi2.data [pos])
+ return Sign.Positive;
+ else
+ return Sign.Zero;
+ }
- if(isPrime) { // additional checks for composite numbers
- // If n is prime and gcd(n, Q) == 1, then
- // Q^((n+1)/2) = Q * Q^((n-1)/2) is congruent to (Q * J(Q, n)) mod n
+ #endregion
- BigInteger g = thisVal.gcd(Q);
- if(g.dataLength == 1 && g.data[0] == 1) { // gcd(this, Q) == 1
- if((lucas[2].data[maxLength-1] & 0x80000000) != 0)
- lucas[2] += thisVal;
+ #region Division
- BigInteger temp = (Q * BigInteger.Jacobi(Q, thisVal)) % thisVal;
- if((temp.data[maxLength-1] & 0x80000000) != 0)
- temp += thisVal;
+ #region Dword
- if(lucas[2] != temp)
- isPrime = false;
- }
- }
+ /// <summary>
+ /// Performs n / d and n % d in one operation.
+ /// </summary>
+ /// <param name="n">A BigInteger, upon exit this will hold n / d</param>
+ /// <param name="d">The divisor</param>
+ /// <returns>n % d</returns>
+ public static uint SingleByteDivideInPlace (BigInteger n, uint d)
+ {
+ ulong r = 0;
+ uint i = n.length;
- return isPrime;
- }
+ while (i-- > 0) {
+ r <<= 32;
+ r |= n.data [i];
+ n.data [i] = (uint)(r / d);
+ r %= d;
+ }
+ n.Normalize ();
- // Determines whether a number is probably prime, using the Rabin-Miller's
- // test. Before applying the test, the number is tested for divisibility
- // by primes < 2000
- //
- // Returns true if number is probably prime.
- public bool isProbablePrime(int confidence)
- {
- BigInteger thisVal;
- if((this.data[maxLength-1] & 0x80000000) != 0) // negative
- thisVal = -this;
- else
- thisVal = this;
-
-
- // test for divisibility by primes < 2000
- for(int p = 0; p < primesBelow2000.Length; p++) {
- BigInteger divisor = primesBelow2000[p];
-
- if(divisor >= thisVal)
- break;
-
- BigInteger resultNum = thisVal % divisor;
- if(resultNum.IntValue() == 0) {
- /*
- Console.WriteLine("Not prime! Divisible by {0}\n",
- primesBelow2000[p]);
- */
- return false;
+ return (uint)r;
}
- }
- if(thisVal.RabinMillerTest(confidence))
- return true;
- else {
- //Console.WriteLine("Not prime! Failed primality test\n");
- return false;
- }
- }
+ public static uint DwordMod (BigInteger n, uint d)
+ {
+ ulong r = 0;
+ uint i = n.length;
- // Determines whether this BigInteger is probably prime using a
- // combination of base 2 strong pseudoprime test and Lucas strong
- // pseudoprime test.
- //
- // The sequence of the primality test is as follows,
- //
- // 1) Trial divisions are carried out using prime numbers below 2000.
- // if any of the primes divides this BigInteger, then it is not prime.
- //
- // 2) Perform base 2 strong pseudoprime test. If this BigInteger is a
- // base 2 strong pseudoprime, proceed on to the next step.
- //
- // 3) Perform strong Lucas pseudoprime test.
- //
- // Returns True if this BigInteger is both a base 2 strong pseudoprime
- // and a strong Lucas pseudoprime.
- //
- // For a detailed discussion of this primality test, see [6].
- public bool isProbablePrime()
- {
- BigInteger thisVal;
- if((this.data[maxLength-1] & 0x80000000) != 0) // negative
- thisVal = -this;
- else
- thisVal = this;
-
- if(thisVal.dataLength == 1) {
- // test small numbers
- if(thisVal.data[0] == 0 || thisVal.data[0] == 1)
- return false;
- else if(thisVal.data[0] == 2 || thisVal.data[0] == 3)
- return true;
- }
+ while (i-- > 0) {
+ r <<= 32;
+ r |= n.data [i];
+ r %= d;
+ }
- if((thisVal.data[0] & 0x1) == 0) // even numbers
- return false;
+ return (uint)r;
+ }
- // test for divisibility by primes < 2000
- for(int p = 0; p < primesBelow2000.Length; p++) {
- BigInteger divisor = primesBelow2000[p];
+ public static BigInteger DwordDiv (BigInteger n, uint d)
+ {
+ BigInteger ret = new BigInteger (Sign.Positive, n.length);
- if(divisor >= thisVal)
- break;
+ ulong r = 0;
+ uint i = n.length;
- BigInteger resultNum = thisVal % divisor;
- if(resultNum.IntValue() == 0) {
- //Console.WriteLine("Not prime! Divisible by {0}\n",
- // primesBelow2000[p]);
+ while (i-- > 0) {
+ r <<= 32;
+ r |= n.data [i];
+ ret.data [i] = (uint)(r / d);
+ r %= d;
+ }
+ ret.Normalize ();
- return false;
+ return ret;
}
- }
- // Perform BASE 2 Rabin-Miller Test
+ public static BigInteger [] DwordDivMod (BigInteger n, uint d)
+ {
+ BigInteger ret = new BigInteger (Sign.Positive , n.length);
- // calculate values of s and t
- BigInteger p_sub1 = thisVal - (new BigInteger(1));
- int s = 0;
+ ulong r = 0;
+ uint i = n.length;
- for(int index = 0; index < p_sub1.dataLength; index++) {
- uint mask = 0x01;
-
- for(int i = 0; i < 32; i++) {
- if((p_sub1.data[index] & mask) != 0) {
- index = p_sub1.dataLength; // to break the outer loop
- break;
+ while (i-- > 0) {
+ r <<= 32;
+ r |= n.data [i];
+ ret.data [i] = (uint)(r / d);
+ r %= d;
}
- mask <<= 1;
- s++;
+ ret.Normalize ();
+
+ BigInteger rem = (uint)r;
+
+ return new BigInteger [] {ret, rem};
}
- }
- BigInteger t = p_sub1 >> s;
+ #endregion
- int bits = thisVal.bitCount();
- BigInteger a = 2;
+ #region BigNum
- // b = a^t mod p
- BigInteger b = a.modPow(t, thisVal);
- bool result = false;
+ public static BigInteger [] multiByteDivide (BigInteger bi1, BigInteger bi2)
+ {
+ if (Kernel.Compare (bi1, bi2) == Sign.Negative)
+ return new BigInteger [2] { 0, new BigInteger (bi1) };
- if(b.dataLength == 1 && b.data[0] == 1) // a^t mod p = 1
- result = true;
+ bi1.Normalize (); bi2.Normalize ();
- for(int j = 0; result == false && j < s; j++) {
- if(b == p_sub1) { // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
- result = true;
- break;
- }
+ if (bi2.length == 1)
+ return DwordDivMod (bi1, bi2.data [0]);
- b = (b * b) % thisVal;
- }
+ uint remainderLen = bi1.length + 1;
+ int divisorLen = (int)bi2.length + 1;
- // if number is strong pseudoprime to base 2, then do a strong lucas test
- if(result)
- result = LucasStrongTestHelper(thisVal);
+ uint mask = 0x80000000;
+ uint val = bi2.data [bi2.length - 1];
+ int shift = 0;
+ int resultPos = (int)bi1.length - (int)bi2.length;
- return result;
- }
+ while (mask != 0 && (val & mask) == 0) {
+ shift++; mask >>= 1;
+ }
- // Returns the lowest 4 bytes of the BigInteger as an int.
- public int IntValue ()
- {
- return (int)data[0];
- }
+ BigInteger quot = new BigInteger (Sign.Positive, bi1.length - bi2.length + 1);
+ BigInteger rem = (bi1 << shift);
+
+ uint [] remainder = rem.data;
+
+ bi2 = bi2 << shift;
+
+ int j = (int)(remainderLen - bi2.length);
+ int pos = (int)remainderLen - 1;
+
+ uint firstDivisorByte = bi2.data [bi2.length-1];
+ ulong secondDivisorByte = bi2.data [bi2.length-2];
+
+ while (j > 0) {
+ ulong dividend = ((ulong)remainder [pos] << 32) + (ulong)remainder [pos-1];
+
+ ulong q_hat = dividend / (ulong)firstDivisorByte;
+ ulong r_hat = dividend % (ulong)firstDivisorByte;
+
+ do {
+
+ if (q_hat == 0x100000000 ||
+ (q_hat * secondDivisorByte) > ((r_hat << 32) + remainder [pos-2])) {
+ q_hat--;
+ r_hat += (ulong)firstDivisorByte;
+
+ if (r_hat < 0x100000000)
+ continue;
+ }
+ break;
+ } while (true);
+
+ //
+ // At this point, q_hat is either exact, or one too large
+ // (more likely to be exact) so, we attempt to multiply the
+ // divisor by q_hat, if we get a borrow, we just subtract
+ // one from q_hat and add the divisor back.
+ //
+
+ uint t;
+ uint dPos = 0;
+ int nPos = pos - divisorLen + 1;
+ ulong mc = 0;
+ uint uint_q_hat = (uint)q_hat;
+ do {
+ mc += (ulong)bi2.data [dPos] * (ulong)uint_q_hat;
+ t = remainder [nPos];
+ remainder [nPos] -= (uint)mc;
+ mc >>= 32;
+ if (remainder [nPos] > t) mc++;
+ dPos++; nPos++;
+ } while (dPos < divisorLen);
+
+ nPos = pos - divisorLen + 1;
+ dPos = 0;
+
+ // Overestimate
+ if (mc != 0) {
+ uint_q_hat--;
+ ulong sum = 0;
+
+ do {
+ sum = ((ulong)remainder [nPos]) + ((ulong)bi2.data [dPos]) + sum;
+ remainder [nPos] = (uint)sum;
+ sum >>= 32;
+ dPos++; nPos++;
+ } while (dPos < divisorLen);
- // Returns the lowest 8 bytes of the BigInteger as a long.
- public long LongValue ()
- {
- long val = 0;
+ }
- val = (long)data[0];
- try {
- // exception if maxLength = 1
- val |= (long)data[1] << 32;
- }
- catch(Exception) {
- if((data[0] & 0x80000000) != 0) // negative
- val = (int)data[0];
- }
+ quot.data [resultPos--] = (uint)uint_q_hat;
- return val;
- }
+ pos--;
+ j--;
+ }
- // Computes the Jacobi Symbol for a and b.
- // Algorithm adapted from [3] and [4] with some optimizations
- public static int Jacobi (BigInteger a, BigInteger b)
- {
- // Jacobi defined only for odd integers
- if((b.data[0] & 0x1) == 0)
- throw (new ArgumentException("Jacobi defined only for odd integers."));
-
- if(a >= b) a %= b;
- if(a.dataLength == 1 && a.data[0] == 0) return 0; // a == 0
- if(a.dataLength == 1 && a.data[0] == 1) return 1; // a == 1
-
- if(a < 0) {
- if( (((b-1).data[0]) & 0x2) == 0) //if( (((b-1) >> 1).data[0] & 0x1) == 0)
- return Jacobi(-a, b);
- else
- return -Jacobi(-a, b);
- }
+ quot.Normalize ();
+ rem.Normalize ();
+ BigInteger [] ret = new BigInteger [2] { quot, rem };
- int e = 0;
- for(int index = 0; index < a.dataLength; index++) {
- uint mask = 0x01;
+ if (shift != 0)
+ ret [1] >>= shift;
- for(int i = 0; i < 32; i++) {
- if((a.data[index] & mask) != 0) {
- index = a.dataLength; // to break the outer loop
- break;
- }
- mask <<= 1;
- e++;
+ return ret;
}
- }
- BigInteger a1 = a >> e;
+ #endregion
- int s = 1;
- if((e & 0x1) != 0 && ((b.data[0] & 0x7) == 3 || (b.data[0] & 0x7) == 5))
- s = -1;
+ #endregion
- if((b.data[0] & 0x3) == 3 && (a1.data[0] & 0x3) == 3)
- s = -s;
+ #region Shift
+ public static BigInteger LeftShift (BigInteger bi, int n)
+ {
+ if (n == 0) return new BigInteger (bi, bi.length + 1);
- if(a1.dataLength == 1 && a1.data[0] == 1)
- return s;
- else
- return (s * Jacobi(b % a1, a1));
- }
+ int w = n >> 5;
+ n &= ((1 << 5) - 1);
- // Generates a positive BigInteger that is probably prime.
- public static BigInteger genPseudoPrime (int bits, int confidence)
- {
- BigInteger result = new BigInteger ();
- bool done = false;
+ BigInteger ret = new BigInteger (Sign.Positive, bi.length + 1 + (uint)w);
- while (!done) {
- result.genRandomBits (bits);
- result.data[0] |= 0x01; // make it odd
- // prime test
- done = result.isProbablePrime(confidence);
- }
- return result;
- }
-
- // Generates a random number with the specified number of bits such
- // that gcd(number, this) = 1
- public BigInteger genCoPrime (int bits)
- {
- bool done = false;
- BigInteger result = new BigInteger ();
+ uint i = 0, l = bi.length;
+ if (n != 0) {
+ uint x, carry = 0;
+ while (i < l) {
+ x = bi.data [i];
+ ret.data [i + w] = (x << n) | carry;
+ carry = x >> (32 - n);
+ i++;
+ }
+ ret.data [i + w] = carry;
+ } else {
+ while (i < l) {
+ ret.data [i + w] = bi.data [i];
+ i++;
+ }
+ }
- while(!done) {
- result.genRandomBits (bits);
- //Console.WriteLine(result.ToString(16));
+ ret.Normalize ();
+ return ret;
+ }
- // gcd test
- BigInteger g = result.gcd(this);
- if (g.dataLength == 1 && g.data[0] == 1)
- done = true;
- }
+ public static BigInteger RightShift (BigInteger bi, int n)
+ {
+ if (n == 0) return new BigInteger (bi);
- return result;
- }
+ int w = n >> 5;
+ int s = n & ((1 << 5) - 1);
- // Returns the modulo inverse of this. Throws ArithmeticException if
- // the inverse does not exist. (i.e. gcd(this, modulus) != 1)
- public BigInteger modInverse (BigInteger modulus)
- {
- BigInteger[] p = { 0, 1 };
- BigInteger[] q = new BigInteger[2]; // quotients
- BigInteger[] r = { 0, 0 }; // remainders
+ BigInteger ret = new BigInteger (Sign.Positive, bi.length - (uint)w + 1);
+ uint l = (uint)ret.data.Length - 1;
- int step = 0;
+ if (s != 0) {
- BigInteger a = modulus;
- BigInteger b = this;
+ uint x, carry = 0;
- while(b.dataLength > 1 || (b.dataLength == 1 && b.data[0] != 0)) {
- BigInteger quotient = new BigInteger();
- BigInteger remainder = new BigInteger();
+ while (l-- > 0) {
+ x = bi.data [l + w];
+ ret.data [l] = (x >> n) | carry;
+ carry = x << (32 - n);
+ }
+ } else {
+ while (l-- > 0)
+ ret.data [l] = bi.data [l + w];
- if(step > 1) {
- BigInteger pval = (p[0] - (p[1] * q[0])) % modulus;
- p[0] = p[1];
- p[1] = pval;
+ }
+ ret.Normalize ();
+ return ret;
}
- if(b.dataLength == 1)
- singleByteDivide(a, b, quotient, remainder);
- else
- multiByteDivide(a, b, quotient, remainder);
+ #endregion
- /*
- Console.WriteLine(quotient.dataLength);
- Console.WriteLine("{0} = {1}({2}) + {3} p = {4}", a.ToString(10),
- b.ToString(10), quotient.ToString(10), remainder.ToString(10),
- p[1].ToString(10));
- */
+ #region Multiply
- q[0] = q[1];
- r[0] = r[1];
- q[1] = quotient; r[1] = remainder;
+ public static BigInteger MultiplyByDword (BigInteger n, uint f)
+ {
+ BigInteger ret = new BigInteger (Sign.Positive, n.length + 1);
- a = b;
- b = remainder;
+ uint i = 0;
+ ulong c = 0;
- step++;
- }
+ do {
+ c += (ulong)n.data [i] * (ulong)f;
+ ret.data [i] = (uint)c;
+ c >>= 32;
+ } while (++i < n.length);
+ ret.data [i] = (uint)c;
+ ret.Normalize ();
+ return ret;
- if(r[0].dataLength > 1 || (r[0].dataLength == 1 && r[0].data[0] != 1))
- throw (new ArithmeticException("No inverse!"));
+ }
- BigInteger result = ((p[0] - (p[1] * q[0])) % modulus);
+ /// <summary>
+ /// Multiplies the data in x [xOffset:xOffset+xLen] by
+ /// y [yOffset:yOffset+yLen] and puts it into
+ /// d [dOffset:dOffset+xLen+yLen].
+ /// </summary>
+ /// <remarks>
+ /// This code is unsafe! It is the caller's responsibility to make
+ /// sure that it is safe to access x [xOffset:xOffset+xLen],
+ /// y [yOffset:yOffset+yLen], and d [dOffset:dOffset+xLen+yLen].
+ /// </remarks>
+ public static unsafe void Multiply (uint [] x, uint xOffset, uint xLen, uint [] y, uint yOffset, uint yLen, uint [] d, uint dOffset)
+ {
+ fixed (uint* xx = x, yy = y, dd = d) {
+ uint* xP = xx + xOffset,
+ xE = xP + xLen,
+ yB = yy + yOffset,
+ yE = yB + yLen,
+ dB = dd + dOffset;
+
+ for (; xP < xE; xP++, dB++) {
+
+ if (*xP == 0) continue;
+
+ ulong mcarry = 0;
+
+ uint* dP = dB;
+ for (uint* yP = yB; yP < yE; yP++, dP++) {
+ mcarry += ((ulong)*xP * (ulong)*yP) + (ulong)*dP;
+
+ *dP = (uint)mcarry;
+ mcarry >>= 32;
+ }
+
+ if (mcarry != 0)
+ *dP = (uint)mcarry;
+ }
+ }
+ }
- if((result.data[maxLength - 1] & 0x80000000) != 0)
- result += modulus; // get the least positive modulus
+ /// <summary>
+ /// Multiplies the data in x [xOffset:xOffset+xLen] by
+ /// y [yOffset:yOffset+yLen] and puts the low mod words into
+ /// d [dOffset:dOffset+mod].
+ /// </summary>
+ /// <remarks>
+ /// This code is unsafe! It is the caller's responsibility to make
+ /// sure that it is safe to access x [xOffset:xOffset+xLen],
+ /// y [yOffset:yOffset+yLen], and d [dOffset:dOffset+mod].
+ /// </remarks>
+ public static unsafe void MultiplyMod2p32pmod (uint [] x, int xOffset, int xLen, uint [] y, int yOffest, int yLen, uint [] d, int dOffset, int mod)
+ {
+ fixed (uint* xx = x, yy = y, dd = d) {
+ uint* xP = xx + xOffset,
+ xE = xP + xLen,
+ yB = yy + yOffest,
+ yE = yB + yLen,
+ dB = dd + dOffset,
+ dE = dB + mod;
+
+ for (; xP < xE; xP++, dB++) {
+
+ if (*xP == 0) continue;
+
+ ulong mcarry = 0;
+ uint* dP = dB;
+ for (uint* yP = yB; yP < yE && dP < dE; yP++, dP++) {
+ mcarry += ((ulong)*xP * (ulong)*yP) + (ulong)*dP;
+
+ *dP = (uint)mcarry;
+ mcarry >>= 32;
+ }
+
+ if (mcarry != 0 && dP < dE)
+ *dP = (uint)mcarry;
+ }
+ }
+ }
- return result;
- }
+ public static unsafe void SquarePositive (BigInteger bi, ref uint [] wkSpace)
+ {
+ uint [] t = wkSpace;
+ wkSpace = bi.data;
+ uint [] d = bi.data;
+ uint dl = bi.length;
+ bi.data = t;
- // Returns the value of the BigInteger as a byte array. The lowest
- // index contains the MSB.
- public byte[] getBytes()
- {
- int numBits = bitCount();
- byte[] result = null;
- if(numBits == 0) {
- result = new byte[1];
- result[0] = 0;
- }
- else {
- int numBytes = numBits >> 3;
- if((numBits & 0x7) != 0)
- numBytes++;
- result = new byte[numBytes];
- //Console.WriteLine(result.Length);
- int numBytesInWord = numBytes & 0x3;
- if(numBytesInWord == 0)
- numBytesInWord = 4;
- int pos = 0;
- for(int i = dataLength - 1; i >= 0; i--) {
- uint val = data[i];
- for(int j = numBytesInWord - 1; j >= 0; j--) {
- result[pos+j] = (byte)(val & 0xFF);
- val >>= 8;
- }
- pos += numBytesInWord;
- numBytesInWord = 4;
- }
- }
- return result;
- }
+ fixed (uint* dd = d, tt = t) {
- // Return true if the value of the specified bit is 1, false otherwise
- public bool testBit (uint bitNum)
- {
- uint bytePos = bitNum >> 5; // divide by 32
- byte bitPos = (byte)(bitNum & 0x1F); // get the lowest 5 bits
+ uint* ttE = tt + t.Length;
+ // Clear the dest
+ for (uint* ttt = tt; ttt < ttE; ttt++)
+ *ttt = 0;
- uint mask = (uint)1 << bitPos;
- return ((this.data[bytePos] | mask) == this.data[bytePos]);
- }
+ uint* dP = dd, tP = tt;
- // Sets the value of the specified bit to 1
- // The Least Significant Bit position is 0.
- public void setBit(uint bitNum)
- {
- uint bytePos = bitNum >> 5; // divide by 32
- byte bitPos = (byte)(bitNum & 0x1F); // get the lowest 5 bits
+ for (uint i = 0; i < dl; i++, dP++) {
+ if (*dP == 0)
+ continue;
- uint mask = (uint)1 << bitPos;
- this.data[bytePos] |= mask;
+ ulong mcarry = 0;
+ uint bi1val = *dP;
- if(bytePos >= this.dataLength)
- this.dataLength = (int)bytePos + 1;
- }
+ uint* dP2 = dP + 1, tP2 = tP + 2*i + 1;
- // Sets the value of the specified bit to 0
- // The Least Significant Bit position is 0.
- public void unsetBit(uint bitNum)
- {
- uint bytePos = bitNum >> 5;
+ for (uint j = i + 1; j < dl; j++, tP2++, dP2++) {
+ // k = i + j
+ mcarry += ((ulong)bi1val * (ulong)*dP2) + *tP2;
- if(bytePos < this.dataLength) {
- byte bitPos = (byte)(bitNum & 0x1F);
+ *tP2 = (uint)mcarry;
+ mcarry >>= 32;
+ }
- uint mask = (uint)1 << bitPos;
- uint mask2 = 0xFFFFFFFF ^ mask;
+ if (mcarry != 0)
+ *tP2 = (uint)mcarry;
+ }
- this.data[bytePos] &= mask2;
+ // Double t. Inlined for speed.
- if(this.dataLength > 1 && this.data[this.dataLength - 1] == 0)
- this.dataLength--;
- }
- }
+ tP = tt;
- // Returns a value that is equivalent to the integer square root
- // of the BigInteger.
- // The integer square root of "this" is defined as the largest integer n
- // such that (n * n) <= this
- public BigInteger sqrt ()
- {
- uint numBits = (uint)this.bitCount();
+ uint x, carry = 0;
+ while (tP < ttE) {
+ x = *tP;
+ *tP = (x << 1) | carry;
+ carry = x >> (32 - 1);
+ tP++;
+ }
+ if (carry != 0) *tP = carry;
+
+ // Add in the diagnals
+
+ dP = dd;
+ tP = tt;
+ for (uint* dE = dP + dl; (dP < dE); dP++, tP++) {
+ ulong val = (ulong)*dP * (ulong)*dP + *tP;
+ *tP = (uint)val;
+ val >>= 32;
+ *(++tP) += (uint)val;
+ if (*tP < (uint)val) {
+ uint* tP3 = tP;
+ // Account for the first carry
+ (*++tP3)++;
+
+ // Keep adding until no carry
+ while ((*tP3++) == 0)
+ (*tP3)++;
+ }
- if((numBits & 0x1) != 0) // odd number of bits
- numBits = (numBits >> 1) + 1;
- else
- numBits = (numBits >> 1);
+ }
- uint bytePos = numBits >> 5;
- byte bitPos = (byte)(numBits & 0x1F);
+ bi.length <<= 1;
- uint mask;
+ // Normalize length
+ while (tt [bi.length-1] == 0 && bi.length > 1) bi.length--;
- BigInteger result = new BigInteger();
- if(bitPos == 0)
- mask = 0x80000000;
- else {
- mask = (uint)1 << bitPos;
- bytePos++;
- }
- result.dataLength = (int)bytePos;
+ }
+ }
- for(int i = (int)bytePos - 1; i >= 0; i--) {
- while(mask != 0) {
- // guess
- result.data[i] ^= mask;
+/*
+ * Never called in BigInteger (and part of a private class)
+ * public static bool Double (uint [] u, int l)
+ {
+ uint x, carry = 0;
+ uint i = 0;
+ while (i < l) {
+ x = u [i];
+ u [i] = (x << 1) | carry;
+ carry = x >> (32 - 1);
+ i++;
+ }
+ if (carry != 0) u [l] = carry;
+ return carry != 0;
+ }*/
- // undo the guess if its square is larger than this
- if((result * result) > this)
- result.data[i] ^= mask;
+ #endregion
- mask >>= 1;
- }
- mask = 0x80000000;
- }
- return result;
- }
+ #region Number Theory
- // Returns the k_th number in the Lucas Sequence reduced modulo n.
- //
- // Uses index doubling to speed up the process. For example, to calculate V(k),
- // we maintain two numbers in the sequence V(n) and V(n+1).
- //
- // To obtain V(2n), we use the identity
- // V(2n) = (V(n) * V(n)) - (2 * Q^n)
- // To obtain V(2n+1), we first write it as
- // V(2n+1) = V((n+1) + n)
- // and use the identity
- // V(m+n) = V(m) * V(n) - Q * V(m-n)
- // Hence,
- // V((n+1) + n) = V(n+1) * V(n) - Q^n * V((n+1) - n)
- // = V(n+1) * V(n) - Q^n * V(1)
- // = V(n+1) * V(n) - Q^n * P
- //
- // We use k in its binary expansion and perform index doubling for each
- // bit position. For each bit position that is set, we perform an
- // index doubling followed by an index addition. This means that for V(n),
- // we need to update it to V(2n+1). For V(n+1), we need to update it to
- // V((2n+1)+1) = V(2*(n+1))
- //
- // This function returns
- // [0] = U(k)
- // [1] = V(k)
- // [2] = Q^n
- //
- // Where U(0) = 0 % n, U(1) = 1 % n
- // V(0) = 2 % n, V(1) = P % n
- public static BigInteger[] LucasSequence (BigInteger P, BigInteger Q,
- BigInteger k, BigInteger n)
- {
- if(k.dataLength == 1 && k.data[0] == 0) {
- BigInteger[] result = new BigInteger[3];
-
- result[0] = 0; result[1] = 2 % n; result[2] = 1 % n;
- return result;
- }
+ public static BigInteger gcd (BigInteger a, BigInteger b)
+ {
+ BigInteger x = a;
+ BigInteger y = b;
- // calculate constant = b^(2k) / m
- // for Barrett Reduction
- BigInteger constant = new BigInteger();
+ BigInteger g = y;
- int nLen = n.dataLength << 1;
- constant.data[nLen] = 0x00000001;
- constant.dataLength = nLen + 1;
+ while (x.length > 1) {
+ g = x;
+ x = y % x;
+ y = g;
- constant = constant / n;
+ }
+ if (x == 0) return g;
- // calculate values of s and t
- int s = 0;
+ // TODO: should we have something here if we can convert to long?
- for(int index = 0; index < k.dataLength; index++) {
- uint mask = 0x01;
+ //
+ // Now we can just do it with single precision. I am using the binary gcd method,
+ // as it should be faster.
+ //
- for(int i = 0; i < 32; i++) {
- if((k.data[index] & mask) != 0) {
- index = k.dataLength; // to break the outer loop
- break;
- }
- mask <<= 1;
- s++;
- }
- }
+ uint yy = x.data [0];
+ uint xx = y % yy;
- BigInteger t = k >> s;
+ int t = 0;
- //Console.WriteLine("s = " + s + " t = " + t);
- return LucasSequenceHelper(P, Q, t, n, constant, s);
- }
+ while (((xx | yy) & 1) == 0) {
+ xx >>= 1; yy >>= 1; t++;
+ }
+ while (xx != 0) {
+ while ((xx & 1) == 0) xx >>= 1;
+ while ((yy & 1) == 0) yy >>= 1;
+ if (xx >= yy)
+ xx = (xx - yy) >> 1;
+ else
+ yy = (yy - xx) >> 1;
+ }
- // Performs the calculation of the kth term in the Lucas Sequence.
- // For details of the algorithm, see reference [9].
- // k must be odd. i.e LSB == 1
- private static BigInteger[] LucasSequenceHelper(BigInteger P, BigInteger Q,
- BigInteger k, BigInteger n, BigInteger constant, int s)
- {
- BigInteger[] result = new BigInteger[3];
+ return yy << t;
+ }
- if((k.data[0] & 0x00000001) == 0)
- throw (new ArgumentException("Argument k must be odd."));
+ public static uint modInverse (BigInteger bi, uint modulus)
+ {
+ uint a = modulus, b = bi % modulus;
+ uint p0 = 0, p1 = 1;
- int numbits = k.bitCount();
- uint mask = (uint)0x1 << ((numbits & 0x1F) - 1);
+ while (b != 0) {
+ if (b == 1)
+ return p1;
+ p0 += (a / b) * p1;
+ a %= b;
- // v = v0, v1 = v1, u1 = u1, Q_k = Q^0
+ if (a == 0)
+ break;
+ if (a == 1)
+ return modulus-p0;
- BigInteger v = 2 % n, Q_k = 1 % n,
- v1 = P % n, u1 = Q_k;
- bool flag = true;
+ p1 += (b / a) * p0;
+ b %= a;
- for(int i = k.dataLength - 1; i >= 0 ; i--) { // iterate on the binary expansion of k
- //Console.WriteLine("round");
- while(mask != 0) {
- if(i == 0 && mask == 0x00000001) // last bit
- break;
+ }
+ return 0;
+ }
+
+ public static BigInteger modInverse (BigInteger bi, BigInteger modulus)
+ {
+ if (modulus.length == 1) return modInverse (bi, modulus.data [0]);
- if((k.data[i] & mask) != 0) { // bit is set
- // index doubling with addition
+ BigInteger [] p = { 0, 1 };
+ BigInteger [] q = new BigInteger [2]; // quotients
+ BigInteger [] r = { 0, 0 }; // remainders
- u1 = (u1 * v1) % n;
+ int step = 0;
- v = ((v * v1) - (P * Q_k)) % n;
- v1 = n.BarrettReduction(v1 * v1, n, constant);
- v1 = (v1 - ((Q_k * Q) << 1)) % n;
+ BigInteger a = modulus;
+ BigInteger b = bi;
- if(flag)
- flag = false;
- else
- Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
+ ModulusRing mr = new ModulusRing (modulus);
- Q_k = (Q_k * Q) % n;
- }
- else {
- // index doubling
- u1 = ((u1 * v) - Q_k) % n;
+ while (b != 0) {
- v1 = ((v * v1) - (P * Q_k)) % n;
- v = n.BarrettReduction(v * v, n, constant);
- v = (v - (Q_k << 1)) % n;
+ if (step > 1) {
- if(flag) {
- Q_k = Q % n;
- flag = false;
+ BigInteger pval = mr.Difference (p [0], p [1] * q [0]);
+ p [0] = p [1]; p [1] = pval;
}
- else
- Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
- }
- mask >>= 1;
- }
- mask = 0x80000000;
- }
-
- // at this point u1 = u(n+1) and v = v(n)
- // since the last bit always 1, we need to transform u1 to u(2n+1) and v to v(2n+1)
+ BigInteger [] divret = multiByteDivide (a, b);
- u1 = ((u1 * v) - Q_k) % n;
- v = ((v * v1) - (P * Q_k)) % n;
- if(flag)
- flag = false;
- else
- Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
+ q [0] = q [1]; q [1] = divret [0];
+ r [0] = r [1]; r [1] = divret [1];
+ a = b;
+ b = divret [1];
- Q_k = (Q_k * Q) % n;
+ step++;
+ }
+ if (r [0] != 1)
+ throw (new ArithmeticException ("No inverse!"));
- for (int i = 0; i < s; i++) {
- // index doubling
- u1 = (u1 * v) % n;
- v = ((v * v) - (Q_k << 1)) % n;
+ return mr.Difference (p [0], p [1] * q [0]);
- if(flag) {
- Q_k = Q % n;
- flag = false;
}
- else
- Q_k = n.BarrettReduction(Q_k * Q_k, n, constant);
+ #endregion
}
-
- result[0] = u1;
- result[1] = v;
- result[2] = Q_k;
-
- return result;
}
}
-
-}
\ No newline at end of file
projects / mono.git / blobdiff