Barrett

Default constructor

Sets engine type.

Throws an exception if the type is invalid

Converts a BigInteger to a byte string (eg. base-256).

Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.

Converts a BigInteger to a hex string (eg. base-16).

Converts a BigInteger to a bit string (eg. base-2).

Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.

Calculates modular inverses.

Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.

{@internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.}

Serialize

Will be called, automatically, when serialize() is called on a BigInteger object.

Serialize

Will be called, automatically, when unserialize() is called on a BigInteger object.

Converts a BigInteger to a base-10 number.

__debugInfo() magic method

Will be called, automatically, when print_r() or var_dump() are called

Set Precision

Some bitwise operations give different results depending on the precision being used. Examples include left shift, not, and rotates.

Get Precision

Returns the precision if it exists, -1 if it doesn't

Set Bitmask

Logical Not

Logical Left Shift

Shifts binary strings $shift bits, essentially multiplying by 2**$shift.

Logical Left Rotate

Instead of the top x bits being dropped they're appended to the shifted bit string.

Logical Right Rotate

Instead of the bottom x bits being dropped they're prepended to the shifted bit string.

Returns the smallest and largest n-bit number

Return the size of a BigInteger in bits

Return the size of a BigInteger in bytes

Performs some pre-processing for powMod

Sliding Window k-ary Modular Exponentiation

Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} / {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims, however, this function performs a modular reduction after every multiplication and squaring operation. As such, this function has the same preconditions that the reductions being used do.

Generates a random number of a certain size

Bit length is equal to $size

Generates a random prime number of a certain size

Bit length is equal to $size

Performs some pre-processing for randomRangePrime

Generate a random number between a range

Returns a random number between $min and $max where $min and $max can be defined using one of the two methods:

BigInteger::randomRange($min, $max) BigInteger::randomRange($max, $min)

Performs some post-processing for randomRangePrime

Sets the $t parameter for primality testing

Tests Primality

Uses the {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24} for more info.

Checks a numer to see if it's prime

Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the $t parameter is distributability. BigInteger::randomPrime() can be distributed across multiple pageloads on a website instead of just one.

Performs a few preliminary checks on root

Calculates the nth root of a biginteger.

Returns the nth root of a positive biginteger, where n defaults to 2

{@internal This function is based off of {@link http://mathforum.org/library/drmath/view/52605.html this page} and {@link http://stackoverflow.com/questions/11242920/calculating-nth-root-with-bcmath-in-php this stackoverflow question}.}

Calculates the nth root of a biginteger.

Return the minimum BigInteger between an arbitrary number of BigIntegers.

Return the minimum BigInteger between an arbitrary number of BigIntegers.

Create Recurring Modulo Function

Sometimes it may be desirable to do repeated modulos with the same number outside of modular exponentiation

Calculates the greatest common divisor and Bezout's identity.

Bitwise Split

Splits BigInteger's into chunks of $split bits

Logical And

Logical Or

Logical Exclusive Or

Initialize a PHP BigInteger Engine instance

Pads strings so that unpack may be used on them

Converts a BigInteger to a base-10 number.

Converts a BigInteger to a byte string (eg. base-256).

Performs addition.

Performs subtraction.

Performs multiplication.

Performs long multiplication on two BigIntegers

Modeled after 'multiply' in MutableBigInteger.java.

Divides two BigIntegers.

Returns an array whose first element contains the quotient and whose second element contains the "common residue". If the remainder would be positive, the "common residue" and the remainder are the same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder and the divisor (basically, the "common residue" is the first positive modulo).

Normalize

Removes leading zeros and truncates (if necessary) to maintain the appropriate precision

Absolute value.

Trim

Removes leading zeros

Logical Right Shift

Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.

Logical Left Shift

Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.

Array Repeat

Logical Left Shift

Shifts BigInteger's by $shift bits.

Logical Right Shift

Shifts BigInteger's by $shift bits.

Performs modular exponentiation.

Performs squaring

Performs traditional squaring on two BigIntegers

Squaring can be done faster than multiplying a number by itself can be. See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.

Performs Karatsuba "squaring" on two BigIntegers

See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.

Make the current number odd

If the current number is odd it'll be unchanged. If it's even, one will be added to it.

Test the number against small primes.

Scan for 1 and right shift by that amount

ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));

Performs exponentiation.

Is Odd?

Tests if a bit is set

Is Negative?

Negate

Given $k, returns -$k

Test for engine validity

Performs modular exponentiation.

The most naive approach to modular exponentiation has very unreasonable requirements, and and although the approach involving repeated squaring does vastly better, it, too, is impractical for our purposes. The reason being that division - by far the most complicated and time-consuming of the basic operations (eg. +,-,*,/) - occurs multiple times within it.

Modular reductions resolve this issue. Although an individual modular reduction takes more time then an individual division, when performed in succession (with the same modulo), they're a lot faster.

The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction, although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because the product of two odd numbers is odd), but what about when RSA isn't used?

In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however, uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and the other, a power of two - and recombine them, later. This is the method that this modPow function uses. {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.

Modular reduction preparation

Modular multiply

Modular square

Barrett Modular Reduction

See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} / {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly, so as not to require negative numbers (initially, this script didn't support negative numbers).

Employs "folding", as described at {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."

Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that usable on account of (1) its not using reasonable radix points as discussed in {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that (x >> 1) + (x >> 1) != x / 2 + x / 2. If x is even, they're the same, but if x is odd, they're not. See the in-line comments for details.