Class BigInteger

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:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('0x32', 16); // 50 in base-16

   echo $a->toString(); // outputs 50
?>

Parameters

Returns

This function exists to maintain backwards compatibility with older code

Parameters

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:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('65');

   echo $a->toBytes(); // outputs chr(65)
?>

Parameters

Returns

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:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('65');

   echo $a->toHex(); // outputs '41'
?>

Parameters

Returns

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:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('65');

   echo $a->toBits(); // outputs '1000001'
?>

Parameters

Returns

Converts a BigInteger to a base-10 number.

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('50');

   echo $a->toString(); // outputs 50
?>

Returns

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:

http://php.net/language.oop5.basic#51624

Returns

See

__toString() magic method

Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call toString().

__clone() magic method

Although you can call BigInteger::__toString() directly in PHP5, you cannot call 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 BigInteger::copy(), instead.

Returns

See

__sleep() magic method

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

See

__wakeup() magic method

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

See

Adds two BigIntegers.

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('10');
   $b = new BigInteger('20');

   $c = $a->add($b);

   echo $c->toString(); // outputs 30
?>

Parameters

Returns

Performs addition.

Parameters

Returns

Subtracts two BigIntegers.

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('10');
   $b = new BigInteger('20');

   $c = $a->subtract($b);

   echo $c->toString(); // outputs -10
?>

Parameters

Returns

Performs subtraction.

Parameters

Returns

Multiplies two BigIntegers

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('10');
   $b = new BigInteger('20');

   $c = $a->multiply($b);

   echo $c->toString(); // outputs 200
?>

Parameters

Returns

Performs multiplication.

Parameters

Returns

Performs long multiplication on two BigIntegers

Modeled after 'multiply' in MutableBigInteger.java.

Parameters

Returns

Performs Karatsuba multiplication on two BigIntegers

See Karatsuba algorithm and MPM 5.2.3.

Parameters

Returns

Performs squaring

Parameters

Returns

Performs traditional squaring on two BigIntegers

Squaring can be done faster than multiplying a number by itself can be. See HAC 14.2.4 / MPM 5.3 for more information.

Parameters

Returns

Performs Karatsuba "squaring" on two BigIntegers

See Karatsuba algorithm and MPM 5.3.4.

Parameters

Returns

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:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('10');
   $b = new BigInteger('20');

   list($quotient, $remainder) = $a->divide($b);

   echo $quotient->toString(); // outputs 0
   echo "\r\n";
   echo $remainder->toString(); // outputs 10
?>

Parameters

Returns

Divides a BigInteger by a regular integer

abc / x = a00 / x + b0 / x + c / x

Parameters

Returns

Performs Legendre Symbol.

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('2');
   $b = new BigInteger('3');

   $c = $a->legendre($b);

   echo $c->toString(); // outputs -1
?>

Parameters

Returns

Performs modulo.

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('8');
   $b = new BigInteger('3');

   $c = $a->mod($b);

   echo $c->toString(); // outputs 2
?>

Parameters

Returns

Performs modular exponentiation.

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger('10');
   $b = new BigInteger('20');
   $c = new BigInteger('30');

   $c = $a->modPow($b, $c);

   echo $c->toString(); // outputs 10
?>

Parameters

Returns

Performs modular exponentiation.

Alias for BigInteger::modPow()

Parameters

Returns

Sliding Window k-ary Modular Exponentiation

Based on HAC 14.85 / 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.

Parameters

Returns

Modular reduction

For most $modes this will return the remainder.

Parameters

Returns

See

Modular reduction preperation

Parameters

Returns

See

Modular multiply

Parameters

Returns

See

Modular square

Parameters

Returns

See

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.

Parameters

Returns

See

Barrett Modular Reduction

See HAC 14.3.3 / 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 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 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.

Parameters

Returns

See

(Regular) Barrett Modular Reduction

For numbers with more than four digits BigInteger::_barrett() is faster. The difference between that and this is that this function does not fold the denominator into a smaller form.

Parameters

Returns

See

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.

Parameters

Returns

See

Montgomery Modular Reduction

($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n. 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.

Parameters

Returns

See

Montgomery Multiply

Interleaves the montgomery reduction and long multiplication algorithms together as described in HAC 14.36

Parameters

Returns

See

Prepare a number for use in Montgomery Modular Reductions

Parameters

Returns

See

Modular Inverse of a number mod 2**26 (eg. 67108864)

Based off of the bnpInvDigit function implemented and justified in the following URL:

http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js

The following URL provides more info:

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!

Parameters

Returns

See

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:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger(30);
   $b = new BigInteger(17);

   $c = $a->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)
?>

Parameters

Returns

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 dependant upon which mode is in use. See Bezout's identity - Wikipedia for more information.

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger(693);
   $b = new BigInteger(609);

   extract($a->extendedGCD($b));

   echo $gcd->toString() . "\r\n"; // outputs 21
   echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
?>

Parameters

Returns

Calculates the greatest common divisor

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

Here's an example:

<?php
   include('Math/BigInteger.php');

   $a = new BigInteger(693);
   $b = new BigInteger(609);

   $gcd = a->extendedGCD($b);

   echo $gcd->toString() . "\r\n"; // outputs 21
?>

Parameters

Returns

Absolute value.

Returns

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

Parameters

Returns

See

Compares two numbers.

Parameters

Returns

See

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

Parameters

Returns

See

Set Precision

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

Parameters

Logical And

Parameters

Returns

Logical Or

Parameters

Returns

Logical Exclusive-Or

Parameters

Returns

Logical Not

Returns

Logical Right Shift

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

Parameters

Returns

Logical Left Shift

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

Parameters

Returns

Logical Left Rotate

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

Parameters

Returns

Logical Right Rotate

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

Parameters

Returns

Set random number generator function

This function is deprecated.

Parameters

Generates a random BigInteger

Byte length is equal to $length. Uses crypt_random if it's loaded and mt_rand if it's not.

Parameters

Returns

Generate a random number

Parameters

Returns

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.

Parameters

Returns

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.

See

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 accross multiple pageloads on a website instead of just one.

Parameters

Returns

Logical Left Shift

Shifts BigInteger's by $shift bits.

Parameters

Logical Right Shift

Shifts BigInteger's by $shift bits.

Parameters

Normalize

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

Parameters

Returns

See

Trim

Removes leading zeros

Parameters

Returns

Array Repeat

Parameters

Returns

Logical Left Shift

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

Parameters

Returns

Logical Right Shift

Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.

Parameters

Returns

Converts 32-bit integers to bytes.

Parameters

Returns

Converts bytes to 32-bit integers

Parameters

Returns

DER-encode an integer

The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL

Parameters

Returns

See