In This Topic

Liquid XML Runtime for .Net - BigInteger Class

In This Topic

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 +, -, *, /, %, >>, <<, ==, !=, >, <, >=, <=, &, |, ^, ++, --, ~

Method | Description |
---|---|

BigInteger() |
Value of BigInteger is initialized to 0. |

BigInteger(long value) |
Default value provided by a signed long integer.
Throws |

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

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.
To initialize To initialize
To initialize To initialize Note that string values are specified in the sign and magnitude format. Throws |

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

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

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

Return Type | Method | Description |
---|---|---|

BigInteger | abs() |
Returns the absolute value of this.
Throws |

int | bitCount() |
Returns the position of the most significant bit in the BigInteger.
1) Returns 0, if the value of the BigInteger is 0...0000 0000 |

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 Returns Returns |

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 Input parameter Returns |

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, - Trial divisions are carried out using prime numbers below 2000. If any of the primes divides
*this*BigInteger, then it is not prime. - Perform base 2 strong pseudoprime test. If
*this*is a base 2 strong pseudoprime, proceed on to the next step. - Perform strong Lucas pseudoprime test.
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 |

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 To obtain V V To obtain V V and use the identity V Hence, V = (V = (V 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
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 Throws |

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 = 2 1) a Otherwise, p is composite. Input parameter 1) a for any Returns Returns |

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 |

bool | SolovayStrassenTest(int confidence) |
Probabilistic primality test based on Solovay-Strassen.
p is probably prime if for any a < p, where J is the Jacobi symbol. Otherwise, p is composite. Input parameter Returns Returns |

bool | StrongLucasTest() |
Implementation of the Lucas Strong Pseudo Prime test.
Let d odd and s >= 0.If V_{2^r*d} mod n = 0for 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 Returns 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.
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.
Throws |

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 (uint) and ^{32}k = number of digits of n.
The parameter 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.
Throws |

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

- D. E. Knuth, "Seminumerical Algorithms", The Art of Computer Programming Vol. 2, 3rd Edition, Addison-Wesley, 1998.
- K. H. Rosen, "Elementary Number Theory and Its Applications", 3rd Ed, Addison-Wesley, 1993.
- B. Schneier, "Applied Cryptography", 2nd Ed, John Wiley & Sons, 1996.
- A. Menezes, P. van Oorschot, and S. Vanstone, "Handbook of Applied Cryptography", CRC Press, 1996, www.cacr.math.uwaterloo.ca/hac
- A. Bosselaers, R. Govaerts, and J. Vandewalle, "Comparison of Three Modular Reduction Functions," Proc. CRYPTO'93, pp.175-186.
- R. Baillie and S. S. Wagstaff Jr, "Lucas Pseudoprimes", Mathematics of Computation, Vol. 35, No. 152, Oct 1980, pp. 1391-1417.
- 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.
- P. Ribenboim, "The new book of prime number records", 3rd edition, Springer-Verlag, New York, NY, 1995.
- 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.