public
Math_BigInteger
|
#
Math_BigInteger( optional $x = 0, optional $base = 10 )
Converts base-2, base-10, base-16, and binary strings (eg. base-256) to
BigIntegers.
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:
<?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('0x32', 16);
echo $a->toString();
?>
Parameters
- $x
optional $x base-10 number or base-$base number if $base set.
- $base
optional integer $base
Returns
|
public
String
|
#
toBytes( Boolean $twos_compliment = false )
Converts a BigInteger to a byte string (eg. base-256).
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 Math_BigInteger('65');
echo $a->toBytes();
?>
Parameters
- $twos_compliment
Boolean $twos_compliment
Returns
String
|
public
String
|
#
toHex( Boolean $twos_compliment = false )
Converts a BigInteger to a hex string (eg. base-16)).
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 Math_BigInteger('65');
echo $a->toHex();
?>
Parameters
- $twos_compliment
Boolean $twos_compliment
Returns
String
|
public
String
|
#
toBits( Boolean $twos_compliment = false )
Converts a BigInteger to a bit string (eg. base-2).
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 Math_BigInteger('65');
echo $a->toBits();
?>
Parameters
- $twos_compliment
Boolean $twos_compliment
Returns
String
|
public
String
|
#
toString( )
Converts a BigInteger to a base-10 number.
Converts a BigInteger to a base-10 number.
Here's an example:
<?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('50');
echo $a->toString();
?>
Returns
String
|
public
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:
http://php.net/language.oop5.basic#51624
Returns
See
|
public
|
#
__toString( )
__toString() magic method
__toString() magic method
Will be called, automatically, if you're supporting just PHP5. If you're
supporting PHP4, you'll need to call toString().
|
public
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.
Returns
See
|
public
|
#
__sleep( )
__sleep() magic method
Will be called, automatically, when serialize() is called on a
Math_BigInteger object.
See
|
public
|
#
__wakeup( )
__wakeup() magic method
Will be called, automatically, when unserialize() is called on a
Math_BigInteger object.
See
|
public
Math_BigInteger
|
#
add( Math_BigInteger $y )
Adds two BigIntegers.
Here's an example:
<?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('10');
$b = new Math_BigInteger('20');
$c = $a->add($b);
echo $c->toString();
?>
Parameters
Returns
|
public
Array
|
#
_add( Array $x_value, Boolean $x_negative, Array $y_value, Boolean $y_negative )
Performs addition.
Parameters
- $x_value
Array $x_value
- $x_negative
Boolean $x_negative
- $y_value
Array $y_value
- $y_negative
Boolean $y_negative
Returns
Array
|
public
Math_BigInteger
|
#
subtract( Math_BigInteger $y )
Subtracts two BigIntegers.
Subtracts two BigIntegers.
Here's an example:
<?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('10');
$b = new Math_BigInteger('20');
$c = $a->subtract($b);
echo $c->toString();
?>
Parameters
Returns
|
public
Array
|
#
_subtract( Array $x_value, Boolean $x_negative, Array $y_value, Boolean $y_negative )
Performs subtraction.
Parameters
- $x_value
Array $x_value
- $x_negative
Boolean $x_negative
- $y_value
Array $y_value
- $y_negative
Boolean $y_negative
Returns
Array
|
public
Math_BigInteger
|
#
multiply( Math_BigInteger $x )
Multiplies two BigIntegers
Multiplies two BigIntegers
Here's an example:
<?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('10');
$b = new Math_BigInteger('20');
$c = $a->multiply($b);
echo $c->toString();
?>
Parameters
Returns
|
public
Array
|
#
_multiply( Array $x_value, Boolean $x_negative, Array $y_value, Boolean $y_negative )
Performs multiplication.
Parameters
- $x_value
Array $x_value
- $x_negative
Boolean $x_negative
- $y_value
Array $y_value
- $y_negative
Boolean $y_negative
Returns
Array
|
public
Array
|
#
_regularMultiply( Array $x_value, Array $y_value )
Performs long multiplication on two BigIntegers
Performs long multiplication on two BigIntegers
Modeled after 'multiply' in MutableBigInteger.java.
Parameters
- $x_value
Array $x_value
- $y_value
Array $y_value
Returns
Array
|
public
Array
|
#
_karatsuba( Array $x_value, Array $y_value )
Performs Karatsuba multiplication on two BigIntegers
Performs Karatsuba multiplication on two BigIntegers
See Karatsuba algorithm and MPM 5.2.3.
Parameters
- $x_value
Array $x_value
- $y_value
Array $y_value
Returns
Array
|
public
Array
|
#
_square( Array $x = false )
Performs squaring
Parameters
Returns
Array
|
public
Array
|
#
_baseSquare( Array $value )
Performs traditional squaring on two BigIntegers
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
Array
|
public
Array
|
#
_karatsubaSquare( Array $value )
Performs Karatsuba "squaring" on two BigIntegers
|
public
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:
<?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('10');
$b = new Math_BigInteger('20');
list($quotient, $remainder) = $a->divide($b);
echo $quotient->toString();
echo "\r\n";
echo $remainder->toString();
?>
Parameters
Returns
Array
|
public
Array
|
#
_divide_digit( Array $dividend, Array $divisor )
Divides a BigInteger by a regular integer
Divides a BigInteger by a regular integer
abc / x = a00 / x + b0 / x + c / x
Parameters
- $dividend
Array $dividend
- $divisor
Array $divisor
Returns
Array
|
public
Math_BigInteger
|
#
modPow( Math_BigInteger $e, Math_BigInteger $n )
Performs modular exponentiation.
Performs modular exponentiation.
Here's an example:
<?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('10');
$b = new Math_BigInteger('20');
$c = new Math_BigInteger('30');
$c = $a->modPow($b, $c);
echo $c->toString();
?>
Parameters
Returns
|
public
Math_BigInteger
|
#
powMod( Math_BigInteger $e, Math_BigInteger $n )
Performs modular exponentiation.
Performs modular exponentiation.
Alias for Math_BigInteger::modPow()
Parameters
Returns
|
public
Math_BigInteger
|
#
_slidingWindow( Math_BigInteger $e, Math_BigInteger $n, Integer $mode )
Sliding Window k-ary Modular Exponentiation
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
|
public
Array
|
#
_reduce( Array $x, Array $n, Integer $mode )
Modular reduction
For most $modes this will return the remainder.
Parameters
- $x
Array $x
- $n
Array $n
- $mode
Integer $mode
Returns
Array
See
|
public
Array
|
#
_prepareReduce( Array $x, Array $n, Integer $mode )
Modular reduction preperation
Modular reduction preperation
Parameters
- $x
Array $x
- $n
Array $n
- $mode
Integer $mode
Returns
Array
See
|
public
Array
|
#
_multiplyReduce( Array $x, Array $y, Array $n, Integer $mode )
Modular multiply
Parameters
- $x
Array $x
- $y
Array $y
- $n
Array $n
- $mode
Integer $mode
Returns
Array
See
|
public
Array
|
#
_squareReduce( Array $x, Array $n, Integer $mode )
Modular square
Parameters
- $x
Array $x
- $n
Array $n
- $mode
Integer $mode
Returns
Array
See
|
public
Math_BigInteger
|
#
_mod2( Math_BigInteger $n )
Modulos for Powers of Two
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
|
public
Array
|
#
_barrett( Array $n, Array $m )
Barrett Modular Reduction
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
Array
See
|
public
Array
|
#
_regularBarrett( Array $x, Array $n )
(Regular) Barrett Modular Reduction
(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.
Parameters
Returns
Array
See
|
public
Array
|
#
_multiplyLower( Array $x_value, Boolean $x_negative, Array $y_value, Boolean $y_negative, mixed $stop )
Performs long multiplication up to $stop digits
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
- $x_value
Array $x_value
- $x_negative
Boolean $x_negative
- $y_value
Array $y_value
- $y_negative
Boolean $y_negative
- $stop
Returns
Array
See
|
public
Array
|
#
_montgomery( Array $x, Array $n )
Montgomery Modular Reduction
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
Array
See
|
public
Array
|
#
_montgomeryMultiply( Array $x, Array $y, Array $m )
Montgomery Multiply
Interleaves the montgomery reduction and long multiplication algorithms
together as described in HAC 14.36
Parameters
- $x
Array $x
- $y
Array $y
- $m
Array $m
Returns
Array
See
|
public
Array
|
#
_prepMontgomery( Array $x, Array $n )
Prepare a number for use in Montgomery Modular Reductions
Prepare a number for use in Montgomery Modular Reductions
Parameters
Returns
Array
See
|
public
Integer
|
#
_modInverse67108864( Array $x )
Modular Inverse of a number mod 2**26 (eg. 67108864)
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
Integer
See
|
public
mixed
|
#
modInverse( Math_BigInteger $n )
Calculates modular inverses.
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 Math_BigInteger(30);
$b = new Math_BigInteger(17);
$c = $a->modInverse($b);
echo $c->toString();
echo "\r\n";
$d = $a->multiply($c);
list(, $d) = $d->divide($b);
echo $d;
?>
Parameters
Returns
mixed false, if no modular inverse exists, Math_BigInteger, otherwise.
|
public
Math_BigInteger
|
#
extendedGCD( Math_BigInteger $n )
Calculates the greatest common divisor and Bézout's identity.
Calculates the greatest common divisor and Bézout's identity.
Say you have 693 and 609. The GCD is 21. Bézout's identity states that there
exist integers x and y such that 693*x + 609*y == 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 Bézout's identity - Wikipedia for more information.
Here's an example:
<?php
include('Math/BigInteger.php');
$a = new Math_BigInteger(693);
$b = new Math_BigInteger(609);
extract($a->extendedGCD($b));
echo $gcd->toString() . "\r\n";
echo $a->toString() * $x->toString() + $b->toString() * $y->toString();
?>
Parameters
Returns
|
public
Math_BigInteger
|
#
gcd( Math_BigInteger $n )
Calculates the greatest common divisor
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 Math_BigInteger(693);
$b = new Math_BigInteger(609);
$gcd = a->extendedGCD($b);
echo $gcd->toString() . "\r\n";
?>
Parameters
Returns
|
public
Math_BigInteger
|
|
public
Integer
|
#
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).
Parameters
Returns
Integer < 0 if $this is less than $x; > 0 if $this is greater than $x, and 0 if
they are equal.
See
|
public
Integer
|
#
_compare( Array $x_value, Boolean $x_negative, Array $y_value, Boolean $y_negative )
Compares two numbers.
Parameters
- $x_value
Array $x_value
- $x_negative
Boolean $x_negative
- $y_value
Array $y_value
- $y_negative
Boolean $y_negative
Returns
Integer
See
|
public
Boolean
|
#
equals( Math_BigInteger $x )
Tests the equality of two numbers.
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()
Parameters
Returns
Boolean
See
|
public
Math_BigInteger
|
#
setPrecision( Math_BigInteger $bits )
Set Precision
Some bitwise operations give different results depending on the precision
being used. Examples include left shift, not, and rotates.
Parameters
Returns
|
public
Math_BigInteger
|
|
public
Math_BigInteger
|
|
public
Math_BigInteger
|
|
public
Math_BigInteger
|
|
public
Math_BigInteger
|
#
bitwise_rightShift( Integer $shift )
Logical Right Shift
Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
Parameters
Returns
|
public
Math_BigInteger
|
#
bitwise_leftShift( Integer $shift )
Logical Left Shift
Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
Parameters
Returns
|
public
Math_BigInteger
|
#
bitwise_leftRotate( Integer $shift )
Logical Left Rotate
Instead of the top x bits being dropped they're appended to the shifted bit
string.
Parameters
Returns
|
public
Math_BigInteger
|
#
bitwise_rightRotate( Integer $shift )
Logical Right Rotate
Instead of the bottom x bits being dropped they're prepended to the shifted
bit string.
Parameters
Returns
|
public
|
#
setRandomGenerator( optional $generator )
Set random number generator function
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().
Parameters
- $generator
optional String $generator
See
|
public
Math_BigInteger
|
#
random( optional $min = false, optional $max = false )
Generate a random number
Parameters
- $min
optional Integer $min
- $max
optional Integer $max
Returns
|
public
Math_BigInteger
|
#
randomPrime( optional $min = false, optional $max = false, optional $timeout = false )
Generate a random prime number.
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
- $min
optional Integer $min
- $max
optional Integer $max
- $timeout
optional Integer $timeout
Returns
|
public
|
#
_make_odd( )
Make the current number 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.
See
|
public
Boolean
|
#
isPrime( optional $t = false )
Checks a numer to see if it's prime
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 accross multiple pageloads on
a website instead of just one.
Parameters
Returns
Boolean
|
public
|
#
_lshift( Integer $shift )
Logical Left Shift
Shifts BigInteger's by $shift bits.
Parameters
|
public
|
#
_rshift( Integer $shift )
Logical Right Shift
Shifts BigInteger's by $shift bits.
Parameters
|
public
Math_BigInteger
|
#
_normalize( Math_BigInteger $result )
Normalize
Removes leading zeros and truncates (if necessary) to maintain the
appropriate precision
Parameters
Returns
See
|
public
Math_BigInteger
|
#
_trim( mixed $value )
Trim
Removes leading zeros
Returns
|
public
Array
|
#
_array_repeat( mixed $input, mixed $multiplier )
Array Repeat
Parameters
- $input
mixed $input Array
- $multiplier
mixed $multiplier mixed
Returns
Array
|
public
String
|
#
_base256_lshift( mixed & $x, mixed $shift )
Logical Left Shift
Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
Parameters
- $x
mixed $x String
- $shift
mixed $shift Integer
Returns
String
|
public
String
|
#
_base256_rshift( mixed & $x, mixed $shift )
Logical Right Shift
Shifts binary strings $shift bits, essentially dividing by 2**$shift and
returning the remainder.
Parameters
- $x
mixed $x String
- $shift
mixed $shift Integer
Returns
String
|
public
String
|
#
_int2bytes( Integer $x )
Converts 32-bit integers to bytes.
Converts 32-bit integers to bytes.
Parameters
Returns
String
|
public
Integer
|
#
_bytes2int( String $x )
Converts bytes to 32-bit integers
Converts bytes to 32-bit integers
Parameters
Returns
Integer
|