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

Test for engine validity

Initialize a BCMath BigInteger Engine instance

Converts a BigInteger to a base-10 number.

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

Adds two BigIntegers.

Subtracts two BigIntegers.

Multiplies two BigIntegers.

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

Calculates modular inverses.

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

Calculates the greatest common divisor and Bezout's identity.

Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that 693x + 609y == 21. In point of fact, there are actually an infinite number of x and y combinations and which combination is returned is dependent upon which mode is in use. See {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.

Calculates the greatest common divisor

Say you have 693 and 609. The GCD is 21.

Absolute value.

Logical And

Logical Or

Logical Exclusive Or

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.

Compares two numbers.

Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is demonstrated thusly:

$x > $y: $x->compare($y) > 0 $x < $y: $x->compare($y) < 0 $x == $y: $x->compare($y) == 0

Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).

{@internal Could return $this->subtract($x), but that's not as fast as what we do do.}

Tests the equality of two numbers.

If you need to see if one number is greater than or less than another number, use BigInteger::compare()

Performs modular exponentiation.

Performs modular exponentiation.

Alias for modPow().

Performs modular exponentiation.

Normalize

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

Generate a random prime number between a range

If there's not a prime within the given range, false will be returned.

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)

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.

Return the minimum BigInteger between an arbitrary number of BigIntegers.

Return the maximum BigInteger between an arbitrary number of BigIntegers.

Tests BigInteger to see if it is between two integers, inclusive

Is Odd?

Tests if a bit is set

Is Negative?

Negate

Given $k, returns -$k

Performs modular exponentiation.

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.