Liquid XML Runtime for .Net - BigInteger Class

By Chew Keong TAN

Comments, bugs and suggestions to (www.codeproject.com/csharp/biginteger.asp)

Updated 23 September, 2002
Constructors   Public Methods   Private Methods   References

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 "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.

Liquid Technologies have made use of the BigInteger class provided by Chew Keong TAN. The class is only intended to hold a representation of an arbitrary sized integer number, and as such this area of the functionality has been tested, and is supported by Liquid Technologies.

The additional functionality provided by this class has been left in the class (add, multiply, compare etc) but is considered above and beyond this base requirement, and is unsupported by Liquid Technologies. All steps have been made to ensure its functionality and correctness of this code, and given the testing we have performed there is no reason to believe that there are any issues with it..

Overloaded Operators +, -, *, /, %, >>, <<, ==, !=, >, <, >=, <=, &, |, ^, ++, --, ~

Constructors

Method Description
BigInteger() Value of BigInteger is initialized to 0.
BigInteger(long value) Default value provided by a signed long integer.

Throws ArithmeticException if input value is larger than the maximum size of the BigInteger.

BigInteger(ulong value) Default value provided by an unsigned long integer.

Throws ArithmeticException if input value is larger than the maximum size of the BigInteger.

BigInteger(BigInteger bi) Default value is provided by a BigInteger.
BigInteger(string value, int radix) Default value is 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 and magnitude format.

Throws ArithmeticException if
(1) Invalid characters are found in the string.
(2) Specified value exceeds the maximum representable value of the BigInteger.

BigInteger(byte[] inData) 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.

Example

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.

Throws ArithmeticException if the number of input bytes exceed the maximum representable value of the BigInteger.

BigInteger(byte[] inData, int inLen) Default value provided by an array of bytes of the specified length.

Throws ArithmeticException if
(1) The number of input bytes exceed the maximum representable value of the BigInteger.
(2) The value of inLen exceeds the length of inData.

BigInteger(uint[] inData) Default value provided by an array of unsigned integers.

Throws ArithmeticException if the number of input integers exceed the maximum representable value of the BigInteger.

Public Methods

Return Type Method Description
BigInteger abs() Returns the absolute value of this.

Throws ArithmeticException if the negated value is too large to fit the BigInteger. This happens if the value of this, prior to negation, holds the maximum negative 2's complement value that can be represented by the BigInteger.

int bitCount() Returns the position of the most significant bit in the BigInteger.

Example

1) Returns 0, if the value of the BigInteger is 0...0000 00002.
2) Returns 1, if the value of the BigInteger is 0...0000 00012.
3) Returns 2, if the value of the BigInteger is 0...0000 00102.
4) Returns 2, if the value of the BigInteger is 0...0000 00112.

bool FermatLittleTest(int confidence) Probabilistic primality test based on Fermat's little theorem.

For any a < p if
ap-1 mod p != 1 then p is not prime.

Otherwise, p is probably prime.

Input parameter confidence determines the number of trials. A random value a is generated for each trial and False is returned if ap-1 mod p != 1 for any a.

Returns True if this is probably prime. i.e.
ap-1 mod p = 1 for all a's that were tested.

Returns False if this is definitely composite.

BigInteger gcd(BigInteger bi) Returns the greatest common divisor of this and bi.
BigInteger genCoPrime(int bits, Random rand) Generates a random positive BigInteger with the specified number of bits such that gcd(number, this) = 1
static BigInteger genPseudoPrime(int bits, int confidence, Random rand) Generates a random positive BigInteger with the specified number of bits and is possibly prime.
void genRandomBits(int bits, Random rand) Populates this with the specified amount of random bits.
byte[] getBytes() Returns the value of the BigInteger as a byte array.

The lowest index contains the MSB.

int IntValue() Returns the lowest 4 bytes of the BigInteger as an int.
bool isProbablePrime(int confidence) Determines whether this BigInteger is probably prime using Rabin-Miller's test.

Prior to the test, trial divisions are carried out using prime numbers below 2000. If any of the primes divides this BigInteger, then it is not prime.

Input parameter confidence determines the number of trials for Rabin-Miller's test.

Returns True if this is probably prime.

bool isProbablePrime() 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 is a base 2 strong pseudoprime, proceed on to the next step.
  3. Perform strong Lucas pseudoprime test.
Returns True if this is both a base 2 strong pseudoprime and a strong Lucas pseudoprime.

For a detailed discussion of this primality test, see [6].

static int Jacobi(BigInteger a, BigInteger b) Computes the Jacobi Symbol for a and b.
Algorithm taken from [3] and [4].

Throws ArgumentException if b is not odd.

long LongValue() Returns the lowest 8 bytes of the BigInteger as a long.
static BigInteger[] LucasSequence(BigInteger P, BigInteger Q, BigInteger k, BigInteger n) Returns the kth number in the Lucas Sequence reduced modulo n.

Index doubling is used to speed up the process. For example, to calculate Vk, we maintain two numbers in the sequence Vn and Vn+1.

To obtain V2n, we use the identity

V2n = (Vn * Vn) - (2 * Qn)

To obtain V2n+1, we first write it as

V2n+1 = V(n+1) + n

and use the identity

Vm+n = (Vm * Vn) - (Qn * Vm-n)

Hence,

V(n+1) + n = (Vn+1 * Vn) - (Qn * V(n+1) - n)

= (Vn+1 * Vn) - (Qn * V1)

= (Vn+1 * Vn) - (Qn * 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 Vn, we need to update it to V2n+1. For Vn+1, we need to update it to V(2n+1)+1 = V2*(n+1)

Returns an array of 3 BigIntegers with,
[0] = Uk
[1] = Vk
[2] = Qn

Where,
U0 = 0 % n, U1 = 1 % n
V0 = 2 % n, V1 = P % n

For a detailed discussion of the algorithm and identities, refer to [6],[7],[8] and [9].

BigInteger max(BigInteger bi) Returns max(this, bi)
BigInteger min(BigInteger bi) Returns min(this, bi)
BigInteger modInverse(BigInteger modulus) Returns the modulo inverse of this.

The modulus inverse is defined as the unique number x such that
(this * x) mod modulus = 1

Throws ArithmeticException if the inverse does not exist. (i.e. gcd(this, modulus) != 1)

BigInteger modPow(BigInteger exp, BigInteger n) Returns the value of this raised to the power of exp, modulo n.
bool RabinMillerTest(int confidence) Probabilistic primality test based on Rabin-Miller's.

For any p > 0 with p - 1 = 2s * t
p is probably prime if for any a < p,

1) at mod p = 1 or
2) a(2^j)*t mod p = p-1 for some 0 <= j <= s-1

Otherwise, p is composite.

Input parameter confidence determines the number of trials. A random value a is generated for each trial and False is returned if

1) at mod p != 1 AND
2) a(2^j)*t mod p != p-1 for all 0 <= j <= s-1.

for any a.

Returns True if this is probably prime.

Returns False if this is definitely composite.

void setBit() Sets the value of the specified bit to 1.

The Least Significant Bit position is 0.

BigInteger sqrt() Returns a value that is equivalent to the integer square root of the BigInteger.

The integer square root of an integer n is defined as the largest integer a such that (a * a) <= n

bool SolovayStrassenTest(int confidence) Probabilistic primality test based on Solovay-Strassen.

p is probably prime if for any a < p,
a(p-1)/2 mod p = J(a, p)

where J is the Jacobi symbol.

Otherwise, p is composite.

Input parameter confidence determines the number of trials. A random value a is generated for each trial and False is returned if a(p-1)/2 mod p != J(a, p) for any a.

Returns True if this is probably prime. i.e.
a(p-1)/2 mod p = J(a, p) for all a's that were tested.

Returns False if this is definitely composite.

bool StrongLucasTest() Implementation of the Lucas Strong Pseudo Prime test.

Let n be an odd number with gcd(n,D) = 1, and n - J(D, n) = 2s * 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.

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

Returns True if number is a strong Lucus pseudo prime. Otherwise, returns False indicating that number is composite.

For a detailed discussion of the algorithm and identities, refer to [6],[7],[8] and [9].

string ToHexString() 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.

override string ToString() Returns a string representing the BigInteger in base 10.
string ToString(int radix) 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"

Throws ArgumentException if radix is not between 2 and 36, inclusive.

void unsetBit() Sets the value of the specified bit to 0.

The Least Significant Bit position is 0.

Private Methods

Return Type Method Description
BigInteger BarrettReduction(BigInteger x, BigInteger n, BigInteger constant) Fast computation of x mod n using Barrett Reduction. Value of x must be < b2k, where b is the base. In this implementation, b = 232 (uint) and k = number of digits of n.

The parameter constant requires the precomputed value of b2k / n

For details of this algorithm, refer to [4].

static BigInteger[] LucasSequenceHelper(BigInteger P, BigInteger Q, BigInteger k, BigInteger n, BigInteger constant, int s) Private method that is called by the public LucasSequence method to generate the kth number in the Lucas sequence.

Returns an array of 3 BigIntegers with,
[0] = Uk
[1] = Vk
[2] = Qn

Throws ArgumentException if k is not odd.

static void multiByteDivide(BigInteger bi1, BigInteger bi2, BigInteger outQuotient, BigInteger outRemainder) Supports the division of two numbers with a divisor that has more than 1 digit.

Used by the overloaded / and % operators.
Parameters bi1 and bi2 are the dividend and the divisor respectively.

static void singleByteDivide(BigInteger bi1, BigInteger bi2, BigInteger outQuotient, BigInteger outRemainder) Supports the division of two numbers with a divisor that has only 1 digit.

Used by the overloaded / and % operators.
Parameters bi1 and bi2 are the dividend and the divisor respectively.

static int shiftLeft(uint[] buffer, int shiftVal) Shifts the BigInteger stored in the buffer by the specified number of bits to the left.

Used by the overloaded << operator.
Returns the position of the most significant integer that is not 0.

static int shiftRight(uint[] buffer, int shiftVal) Shifts the BigInteger stored in the buffer by the specified number of bits to the right.

Used by the overloaded >> operator.
Returns the position of the most significant integer that is not 0.

bool LucasStrongTestHelper(BigInteger thisVal) Private method called by the public LucasStrongTest method to perform a Lucas strong pseudoprime test on thisVal.

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.

    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.