Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available,
and an internal implementation, otherwise.
PHP versions 4 and 5
{@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
{@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible
value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
which only supports integers. Although this fact will slow this library down, the fact that such a high
base is being used should more than compensate.
When PHP version 6 is officially released, we'll be able to use 64-bit integers. This should, once again,
allow bitwise operators, and will increase the maximum possible base to 2**31 (or 2**62 for addition /
subtraction).
Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie.
(new Math_BigInteger(pow(2, 26)))->value = array(0, 1)
Useful resources are as follows:
- {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
- {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
- Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
Here's an example of how to use this library:
add($b);
echo $c->toString(); // outputs 5
?>
LICENSE: 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, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
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. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
Constants
MATH_BIGINTEGER_MONTGOMERY
= 0
MATH_BIGINTEGER_BARRETT
= 1
MATH_BIGINTEGER_POWEROF2
= 2
MATH_BIGINTEGER_CLASSIC
= 3
MATH_BIGINTEGER_NONE
= 4
MATH_BIGINTEGER_VALUE
= 0
$result[MATH_BIGINTEGER_VALUE] contains the value.
MATH_BIGINTEGER_SIGN
= 1
$result[MATH_BIGINTEGER_SIGN] contains the sign.
MATH_BIGINTEGER_VARIABLE
= 0
Cache constants $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
MATH_BIGINTEGER_DATA
= 1
$cache[MATH_BIGINTEGER_DATA] contains the cached data.
MATH_BIGINTEGER_MODE_INTERNAL
= 1
To use the pure-PHP implementation
MATH_BIGINTEGER_MODE_BCMATH
= 2
To use the BCMath library (if enabled; otherwise, the internal implementation will be used)
MATH_BIGINTEGER_MODE_GMP
= 3
To use the GMP library (if present; otherwise, either the BCMath or the internal implementation will be used)
MATH_BIGINTEGER_MAX_DIGIT52
= pow(2, 52)
The largest digit that may be used in addition / subtraction (we do pow(2, 52) instead of using 4503599627370496, directly, because some PHP installations
will truncate 4503599627370496)
MATH_BIGINTEGER_KARATSUBA_CUTOFF
= 25
Karatsuba Cutoff At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
Converts base-2, base-10, base-16, and binary strings (eg. 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
?>
__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.
Return value
Type
Description
\Math_BigInteger
Tags
Name
Description
access
public
see
__sleep(
)
:
n/a
Description
__sleep() magic method Will be called, automatically, when serialize() is called on a Math_BigInteger object.
Return value
Type
Description
n/a
n/a
Tags
Name
Description
see
access
public
__wakeup(
)
:
n/a
Description
__wakeup() magic method Will be called, automatically, when unserialize() is called on a Math_BigInteger object.
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.
Arguments
Name
Type
Description
Default
$n
Array
$m
Array
Return value
Type
Description
Array
Tags
Name
Description
see
access
private
_base256_lshift(
$x,
$shift,
)
:
String
Description
Logical Left Shift Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
Arguments
Name
Type
Description
Default
$x
n/a
String
$shift
n/a
Integer
Return value
Type
Description
String
Tags
Name
Description
access
private
_base256_rshift(
$x,
$shift,
)
:
String
Description
Logical Right Shift Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
Arguments
Name
Type
Description
Default
$x
n/a
String
$shift
n/a
Integer
Return value
Type
Description
String
Tags
Name
Description
access
private
_baseSquare(
Array
$value,
)
:
Array
Description
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 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}.
Arguments
Name
Type
Description
Default
$x_value
Array
$y_value
Array
Return value
Type
Description
Array
Tags
Name
Description
access
private
_karatsubaSquare(
Array
$value,
)
:
Array
Description
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}.
Arguments
Name
Type
Description
Default
$value
Array
Return value
Type
Description
Array
Tags
Name
Description
access
private
_lshift(
Integer
$shift,
)
:
n/a
Description
Logical Left Shift Shifts BigInteger's by $shift bits.
Arguments
Name
Type
Description
Default
$shift
Integer
Return value
Type
Description
n/a
n/a
Tags
Name
Description
access
private
_make_odd(
)
:
n/a
Description
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.
Return value
Type
Description
n/a
n/a
Tags
Name
Description
see
access
private
_mod2(
$n,
)
:
\Math_BigInteger
Description
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.
Arguments
Name
Type
Description
Default
$n
n/a
Return value
Type
Description
\Math_BigInteger
Tags
Name
Description
see
access
private
_modInverse67108864(
Array
$x,
)
:
Integer
Description
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!
Arguments
Name
Type
Description
Default
$x
Array
Return value
Type
Description
Integer
Tags
Name
Description
see
access
private
_montgomery(
Array
$x,
Array
$n,
)
:
Array
Description
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.
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}
Modular reduction For most $modes this will return the remainder.
Arguments
Name
Type
Description
Default
$x
Array
$n
Array
$mode
Integer
Return value
Type
Description
Array
Tags
Name
Description
see
access
private
_regularBarrett(
Array
$x,
Array
$n,
)
:
Array
Description
(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.
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.
Logical Right Rotate Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
Arguments
Name
Type
Description
Default
$shift
Integer
Return value
Type
Description
\Math_BigInteger
Tags
Name
Description
access
public
copy(
)
:
\Math_BigInteger
Description
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}
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
?>
Set Precision Some bitwise operations give different results depending on the precision being used. Examples include left
shift, not, and rotates.
Arguments
Name
Type
Description
Default
$bits
n/a
Return value
Type
Description
\Math_BigInteger
Tags
Name
Description
access
public
setRandomGenerator(
$generator,
)
:
n/a
Description
Set random number generator function $generator should be the name of a random generating function whose first parameter is the minimum
value and whose second parameter is the maximum value. If this function needs to be seeded, it should
be seeded prior to calling Math_BigInteger::random() or Math_BigInteger::randomPrime()
If the random generating function is not explicitly set, it'll be assumed to be mt_rand().
Mode independant value used for serialization. If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value,
however, $this->hex is only calculated when $this->__sleep() is called.