Liquid XML Runtime for .Net - BigInteger Class

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

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

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.

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.

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.

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

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.

Example

1) Returns 0, if the value of the BigInteger is 0...0000 0000₂.
2) Returns 1, if the value of the BigInteger is 0...0000 0001₂.
3) Returns 2, if the value of the BigInteger is 0...0000 0010₂.
4) Returns 2, if the value of the BigInteger is 0...0000 0011₂.

For any a < p if
a^p-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 a^p-1 mod p != 1 for any a.

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

Returns False if this is definitely composite.

The lowest index contains the MSB.

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.

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.

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

Throws ArgumentException if b is not odd.

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ⁿ)

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ⁿ * V_{(n+1) - n})

= (V_n+1 * V_n) - (Qⁿ * V₁)

= (V_n+1 * V_n) - (Qⁿ * 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,
[0] = U_k
[1] = V_k
[2] = Qⁿ

Where,
U₀ = 0 % n, U₁ = 1 % n
V₀ = 2 % n, V₁ = P % n

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

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)

For any p > 0 with p - 1 = 2^s * t
p is probably prime 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.

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

The Least Significant Bit position is 0.

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

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.

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

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.

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.

The Least Significant Bit position is 0.

The parameter constant requires the precomputed value of b^2k / n

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

Returns an array of 3 BigIntegers with,
[0] = U_k
[1] = V_k
[2] = Qⁿ

Throws ArgumentException if k is not odd.

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

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

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

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