Math_BigInteger
class Math_BigInteger (View source)
Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256 numbers.
Properties
array | $value | Holds the BigInteger's value. | |
bool | $is_negative | Holds the BigInteger's magnitude. | |
$precision | Precision | ||
$bitmask | Precision Bitmask | ||
string | $hex | Mode independent value used for serialization. |
Methods
Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
PHP4 compatible Default Constructor.
Converts a BigInteger to a byte string (eg. base-256).
Converts a BigInteger to a hex string (eg. base-16)).
Converts a BigInteger to a bit string (eg. base-2).
Converts a BigInteger to a base-10 number.
Copy an object
__toString() magic method
__clone() magic method
__sleep() magic method
__wakeup() magic method
__debugInfo() magic method
Performs addition.
Performs subtraction.
Performs multiplication.
Performs long multiplication on two BigIntegers
Performs Karatsuba multiplication on two BigIntegers
Performs squaring
Performs traditional squaring on two BigIntegers
Performs Karatsuba "squaring" on two BigIntegers
Divides a BigInteger by a regular integer
Sliding Window k-ary Modular Exponentiation
Modular reduction
Modular reduction preperation
Modular multiply
Modular square
Barrett Modular Reduction
(Regular) Barrett Modular Reduction
Performs long multiplication up to $stop digits
Montgomery Modular Reduction
Montgomery Multiply
Prepare a number for use in Montgomery Modular Reductions
Modular Inverse of a number mod 2**26 (eg. 67108864)
Absolute value.
Compares two numbers.
Set Precision
Logical Not
Logical Right Shift
Logical Left Shift
Logical Left Rotate
Logical Right Rotate
Set random number generator function
Generates a random BigInteger
Generate a random prime number.
Make the current number odd
Logical Left Shift
Logical Right Shift
Trim
Array Repeat
Logical Left Shift
Logical Right Shift
Converts 32-bit integers to bytes.
Converts bytes to 32-bit integers
DER-encode an integer
Single digit division
Details
Math_BigInteger
__construct(int|string|resource $x = 0, int $base = 10)
Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using two's compliment. The sole exception to this is -10, which is treated the same as 10 is.
Here's an example:
toString(); // outputs 50
?>
Math_BigInteger($x = 0, int $base = 10)
PHP4 compatible Default Constructor.
string
toBytes(bool $twos_compliment = false)
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.
Here's an example:
toBytes(); // outputs chr(65)
?>
string
toHex(bool $twos_compliment = false)
Converts a BigInteger to a hex string (eg. base-16)).
Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.
Here's an example:
toHex(); // outputs '41'
?>
string
toBits(bool $twos_compliment = false)
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.
Here's an example:
toBits(); // outputs '1000001'
?>
string
toString()
Converts a BigInteger to a base-10 number.
Here's an example:
toString(); // outputs 50
?>
Math_BigInteger
copy()
Copy an object
PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee that all objects are passed by value, when appropriate. More information can be found here:
{@link http://php.net/language.oop5.basic#51624}
__toString()
__toString() magic method
Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call toString().
Math_BigInteger
__clone()
__clone() magic method
Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone() directly in PHP5. You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5 only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and PHP5, call Math_BigInteger::copy(), instead.
__sleep()
__sleep() magic method
Will be called, automatically, when serialize() is called on a Math_BigInteger object.
__wakeup()
__wakeup() magic method
Will be called, automatically, when unserialize() is called on a Math_BigInteger object.
__debugInfo()
__debugInfo() magic method
Will be called, automatically, when print_r() or var_dump() are called
Math_BigInteger
add(Math_BigInteger $y)
Adds two BigIntegers.
Here's an example:
add($b);
echo $c->toString(); // outputs 30
?>
array
_add(array $x_value, bool $x_negative, array $y_value, bool $y_negative)
Performs addition.
Math_BigInteger
subtract(Math_BigInteger $y)
Subtracts two BigIntegers.
Here's an example:
subtract($b);
echo $c->toString(); // outputs -10
?>
array
_subtract(array $x_value, bool $x_negative, array $y_value, bool $y_negative)
Performs subtraction.
Math_BigInteger
multiply(Math_BigInteger $x)
Multiplies two BigIntegers
Here's an example:
multiply($b);
echo $c->toString(); // outputs 200
?>
array
_multiply(array $x_value, bool $x_negative, array $y_value, bool $y_negative)
Performs multiplication.
array
_regularMultiply(array $x_value, array $y_value)
Performs long multiplication on two BigIntegers
Modeled after 'multiply' in MutableBigInteger.java.
array
_karatsuba(array $x_value, array $y_value)
Performs Karatsuba multiplication on two BigIntegers
See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
array
_square(array $x = false)
Performs squaring
array
_baseSquare(array $value)
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.
array
_karatsubaSquare(array $value)
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}.
array
divide(Math_BigInteger $y)
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).
Here's an example:
divide($b);
echo $quotient->toString(); // outputs 0
echo "\r\n";
echo $remainder->toString(); // outputs 10
?>
array
_divide_digit(array $dividend, array $divisor)
Divides a BigInteger by a regular integer
abc / x = a00 / x + b0 / x + c / x
Math_BigInteger
modPow(Math_BigInteger $e, Math_BigInteger $n)
Performs modular exponentiation.
Here's an example:
modPow($b, $c);
echo $c->toString(); // outputs 10
?>
Math_BigInteger
powMod(Math_BigInteger $e, Math_BigInteger $n)
Performs modular exponentiation.
Alias for Math_BigInteger::modPow()
Math_BigInteger
_slidingWindow(Math_BigInteger $e, Math_BigInteger $n, int $mode)
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.
array
_reduce(array $x, array $n, int $mode)
Modular reduction
For most $modes this will return the remainder.
array
_prepareReduce(array $x, array $n, int $mode)
Modular reduction preperation
array
_multiplyReduce(array $x, array $y, array $n, int $mode)
Modular multiply
array
_squareReduce(array $x, array $n, int $mode)
Modular square
Math_BigInteger
_mod2(Math_BigInteger $n)
Modulos for Powers of Two
Calculates $x%$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1), we'll just use this function as a wrapper for doing that.
array
_barrett(array $n, array $m)
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.
array
_regularBarrett(array $x, array $n)
(Regular) Barrett Modular Reduction
For numbers with more than four digits Math_BigInteger::_barrett() is faster. The difference between that and this is that this function does not fold the denominator into a smaller form.
array
_multiplyLower(array $x_value, bool $x_negative, array $y_value, bool $y_negative, int $stop)
Performs long multiplication up to $stop digits
If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
array
_montgomery(array $x, array $n)
Montgomery Modular Reduction
($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n. {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function to work correctly.
array
_montgomeryMultiply(array $x, array $y, array $m)
Montgomery Multiply
Interleaves the montgomery reduction and long multiplication algorithms together as described in {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
array
_prepMontgomery(array $x, array $n)
Prepare a number for use in Montgomery Modular Reductions
int
_modInverse67108864(array $x)
Modular Inverse of a number mod 2**26 (eg. 67108864)
Based off of the bnpInvDigit function implemented and justified in the following URL:
{@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
The following URL provides more info:
{@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to 40 bits, which only 64-bit floating points will support.
Thanks to Pedro Gimeno Fortea for input!
Math_BigInteger|false
modInverse(Math_BigInteger $n)
Calculates modular inverses.
Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.
Here's an example:
modInverse($b);
echo $c->toString(); // outputs 4
echo "\r\n";
$d = $a->multiply($c);
list(, $d) = $d->divide($b);
echo $d; // outputs 1 (as per the definition of modular inverse)
?>
Math_BigInteger
extendedGCD(Math_BigInteger $n)
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.
Here's an example:
extendedGCD($b));
echo $gcd->toString() . "\r\n"; // outputs 21
echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
?>
Math_BigInteger
gcd(Math_BigInteger $n)
Calculates the greatest common divisor
Say you have 693 and 609. The GCD is 21.
Here's an example:
extendedGCD($b);
echo $gcd->toString() . "\r\n"; // outputs 21
?>
Math_BigInteger
abs()
Absolute value.
int
compare(Math_BigInteger $y)
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).
int
_compare(array $x_value, bool $x_negative, array $y_value, bool $y_negative)
Compares two numbers.
bool
equals(Math_BigInteger $x)
Tests the equality of two numbers.
If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare()
setPrecision(int $bits)
Set Precision
Some bitwise operations give different results depending on the precision being used. Examples include left shift, not, and rotates.
Math_BigInteger
bitwise_and(Math_BigInteger $x)
Logical And
Math_BigInteger
bitwise_or(Math_BigInteger $x)
Logical Or
Math_BigInteger
bitwise_xor(Math_BigInteger $x)
Logical Exclusive-Or
Math_BigInteger
bitwise_not()
Logical Not
Math_BigInteger
bitwise_rightShift(int $shift)
Logical Right Shift
Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
Math_BigInteger
bitwise_leftShift(int $shift)
Logical Left Shift
Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
Math_BigInteger
bitwise_leftRotate(int $shift)
Logical Left Rotate
Instead of the top x bits being dropped they're appended to the shifted bit string.
Math_BigInteger
bitwise_rightRotate(int $shift)
Logical Right Rotate
Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
setRandomGenerator(string $generator)
Set random number generator function
This function is deprecated.
Math_BigInteger
_random_number_helper(int $size)
Generates a random BigInteger
Byte length is equal to $length. Uses crypt_random if it's loaded and mt_rand if it's not.
Math_BigInteger
random(Math_BigInteger $arg1, Math_BigInteger $arg2 = false)
Generate a random number
Returns a random number between $min and $max where $min and $max can be defined using one of the two methods:
$min->random($max) $max->random($min)
Math_BigInteger|false
randomPrime(Math_BigInteger $arg1, Math_BigInteger $arg2 = false, int $timeout = false)
Generate a random prime number.
If there's not a prime within the given range, false will be returned. If more than $timeout seconds have elapsed, give up and return false.
_make_odd()
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.
bool
isPrime(Math_BigInteger $t = false)
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. Math_BigInteger::randomPrime() can be distributed across multiple pageloads on a website instead of just one.
_lshift(int $shift)
Logical Left Shift
Shifts BigInteger's by $shift bits.
_rshift(int $shift)
Logical Right Shift
Shifts BigInteger's by $shift bits.
Math_BigInteger
_normalize(Math_BigInteger $result)
Normalize
Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
Math_BigInteger
_trim(array $value)
Trim
Removes leading zeros
array
_array_repeat(array $input, mixed $multiplier)
Array Repeat
string
_base256_lshift(string $x, int $shift)
Logical Left Shift
Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
string
_base256_rshift(string $x, int $shift)
Logical Right Shift
Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
string
_int2bytes(int $x)
Converts 32-bit integers to bytes.
int
_bytes2int(string $x)
Converts bytes to 32-bit integers
string
_encodeASN1Length(int $length)
DER-encode an integer
The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL
int
_safe_divide(int $x, int $y)
Single digit division
Even if int64 is being used the division operator will return a float64 value if the dividend is not evenly divisible by the divisor. Since a float64 doesn't have the precision of int64 this is a problem so, when int64 is being used, we'll guarantee that the dividend is divisible by first subtracting the remainder.