Comments, bugs and suggestions to (www.codeproject.com/csharp/biginteger.asp)
Updated 23 September, 2002
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 +, , *, /, %, >>, <<, ==, !=, >, <, >=, <=, &, , ^, ++, , ~
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
To initialize a with the default value of 1234 Example (base 16)
To initialize a with the default value of 0x1D4F in base 16
To initialize a with the default value of 0x1D4F Note that string values are specified in the sign and magnitude format.
Throws ArithmeticException if 
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 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 
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. 
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 0000_{2}. 
bool  FermatLittleTest(int confidence) 
Probabilistic primality test based on Fermat's little theorem.
For any a < p if 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 a^{p1} mod p != 1 for any a.
Returns True if this is probably prime. i.e. 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 RabinMiller'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 RabinMiller'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,
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 k^{th} number in the Lucas Sequence reduced modulo n. Index doubling is used 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^{n} * V_{mn}) 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)}
Returns an array of 3 BigIntegers with,
Where, 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 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 RabinMiller's.
For any p > 0 with p  1 = 2^{s} * t
1) a^{t} mod p = 1 or 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) a^{t} mod p != 1 AND 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 SolovayStrassen.
p is probably prime if for any 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^{(p1)/2} mod p != J(a, p) for any a.
Returns True if this is probably prime. i.e. 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) = 2^{s} * d with d odd and s >= 0.
If U_{d} mod n = 0 OR V_{2^r*d} mod n = 0
Let D be the first element of the sequence
5, 7, 9, 11, 13, ... for which J(D,n) = 1 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 signandmagnitude format
in the specified radix.
Example 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. 
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 < b^{2k}, where b is the base. In this
implementation, b = 2^{32} (uint) and k = number of digits of n. The parameter constant requires the precomputed value of b^{2k} / 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 k^{th} number in the Lucas sequence.
Returns an array of 3 BigIntegers with, 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. 
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. 
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. 
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. 
bool  LucasStrongTestHelper(BigInteger thisVal)  Private method called by the public LucasStrongTest method to perform a Lucas strong pseudoprime test on thisVal. 
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.
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.