Chapter 2. Math
Prev |  | Next

## Chapter 2. Math

## 2.1. Math_BigInteger

Implements an arbitrary precision integer arithmetic library. Uses gmp or bcmath, if available, and an internal implementation, otherwise. Here's an example:

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

        $a = new Math_BigInteger(2);
        $b = new Math_BigInteger(3);

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

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

### 2.1.1. Dependencies

If you're running PHP 5, Math_BigInteger's only dependancy is the PCRE extension (which is enabled by default). Math_BigInteger also works on PHP 4 if PHP/Compat/Function/array_fill.php and PHP/Compat/Function/bcpowmod.php are included.

### 2.1.2. The constructor

The constructor takes two parameters. The first is the number and the second represents the base. Both are optional (if they're not provided, the Math_BigInteger object will assume a value of 0).

The supported bases are base-2, base-10 (default), base-16, and base-256. To set $a, in the above example, to 2, using base-2, we'd do `new Math_BigInteger('10', 2)`. To do it using base-16, you could do `new Math_BigInteger('2', 16)` or `new Math_BigInteger('0x2', 16)`. To set it to 2 using base-256, you'd do `new Math_BigInteger(chr(2), 256)`.

If the base is negative (eg. -256), two's compliment will be used. Thus, `new Math_BigInteger(chr(0xFF), -256)` is equal to -1, as is `new Math_BigInteger('0xFFFFFFFF', -16)` and `new Math_BigInteger('11', -2)`. Basically, if the leading bit is 1, the number is assumed to be negative.

### 2.1.3. toString(), toBytes(), toHex() and toBits()

`toString()` returns the base-10 form of a number. `toBytes()` returns the base-256 form of a number, `toHex()` returns the base-16 form, and `toBits()` the base-2 form. `toBytes()`, `toHex()`, and `toBits()` also take an optional parameter which, if set, will return the two's compliment of a number. So if, for example, $a is equal to -1, `toBytes(true)` will return `chr(0xFF)`.

On PHP 5, `toString()` is called automatically when used in a string context via the __toString() magic method.

### 2.1.4. add(), subtract(), multiply() and divide()

`subtract()` and `multiply()` operate similarly to `add()`. `divide()`, however, does not. Namely, it 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 Math_BigInteger('10');
        $b = new Math_BigInteger('20');

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

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

### 2.1.5. powMod() and modInverse()

Examples of each follow:

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

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

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

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

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

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

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

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

### 2.1.6. gcd() and extendedGCD()

`extendedGCD()` returns an array containing three Math_BigInteger values indexed with x, y, and gcd. x and y represent Bézout's identity. `gcd()` returns a Math_BigInteger value equal to the gcd. An example of each follows:

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

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

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

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

### 2.1.7. abs()

`$x->abs()` returns the absolute value of `$x`.

### 2.1.8. equals() and compare()

`$x->equals($y)` returns true or false depending on whether or not `$x` and `$y` are equal.

`$x->compare($y)` returns 1 if $x > $y, 0 if $x == $y, and -1 if $x < $y. 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
    $x >= $y: $x->compare($y) >= 0
    $x <= $y: $x->compare($y) <= 0

As a consequence of this, `!$x->compare($y)` does not mean `$x != $y` but rather `$x == $y`.

### 2.1.9. setPrecision()

Some bitwise operations give different results depending on the precision being used. Examples include left shift, not, and rotates, as discussed for bitwise_not(). This function lets you control the precision.

Whenever a new Math_BigInteger object is created it's precision is set to the same precision as the calling object. In other words, if you do `$b = $a->bitwise_not()` then `$b` will have the same precision as `$a`.

### 2.1.10. bitwise_and(), bitwise_or(), bitwise_xor() and bitwise_not()

`bitwise_and()`, `bitwise_or()` and `bitwise_xor()` operate similar to `add()`. `bitwise_not()` is a bit more complicated. To elaborate, if the precision (see setPrecision) is arbitrary, `$x->bitwise_not()` will always yield a smaller value since the most significant bit is assumed to have a value of one. With fixed precision, however, the leading bit can be anything.

### 2.1.11. bitwise_rightShift() and bitwise_leftShift()

`$a->bitwise_rightShift($shift)` shifts $a by $shift bits, effectively dividing by 2**$shift. `$a->bitwise_leftShift($shift)` shifts $a by $shift bits, effectively multiplying by 2**$shift.

### 2.1.12. bitwise_rightRotate() and bitwise_leftRotate()

`$a->bitwise_rightRotate($shift)` and `$a->bitwise_leftRotate($shift)` are demonstrated thusly:

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

    $a = new Math_BigInteger('00111000', 2);
    $a->setPrecision(8);
    $b = $a->bitwise_leftRotate(2);
    echo $b->toBits(); // returns 11100000

    echo "\r\n";

    $a = new Math_BigInteger('00111000', 2);
    $b = $a->bitwise_leftRotate(2);
    echo $b->toBits(); // returns 100011
    ?>

Just as with bitwise_not(), these operations are precision dependant.

### 2.1.13. setRandomGenerator()

Sets the random generator. To set it to `mt_rand()` (which is what it is by default), call `$x->setRandomGenerator('mt_rand')`.

### 2.1.14. isPrime()

Returns true if a number is prime and false if it isn't.

### 2.1.15. random() and randomPrime()

`random($min, $max)` generates a random number between `$min` and `$max`. `randomPrime($min, $max)` generates a random prime number between `$min` and `$max`. If no prime number exists between `$min` and `$max` false is returned.

`randomPrime()` has an optional third parameter, as well - $timeout. Generating prime numbers is a particurarly expensive operation and although in certain environments even 512-bit primes can be generated in a less than a second it can take other environments upwards of around a minute if not more.

Prev |  | Next
Chapter 1. Introduction | Home | Chapter 3. Symmetric-key Cryptography