Chapter 2. Math

Chapter 2. Math
Prev		Next

Table of Contents

2.1.1. Dependencies
2.1.2. The constructor
2.1.3. toString(), toBytes(), toHex() and toBits()
2.1.4. add(), subtract(), multiply() and divide()
2.1.5. powMod() and modInverse()
2.1.6. gcd() and extendedGCD()
2.1.7. abs()
2.1.8. equals() and compare()
2.1.9. setPrecision()
2.1.10. bitwise_and(), bitwise_or(), bitwise_xor() and bitwise_not()
2.1.11. bitwise_rightShift() and bitwise_leftShift()
2.1.12. bitwise_rightRotate() and bitwise_leftRotate()
2.1.13. setRandomGenerator()
2.1.14. isPrime()
2.1.15. random() and randomPrime()

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