MONTGOMERY
MONTGOMERY
Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256 numbers.
$hex : string
Mode independent 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.
__construct( $x, integer $base = 10) : \phpseclib\Math\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
$a = new \phpseclib\Math\BigInteger('0x32', 16); // 50 in base-16
echo $a->toString(); // outputs 50 ?>
| $x | base-10 number or base-$base number if $base set. |
|
| integer | $base |
copy() : \phpseclib\Math\BigInteger
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
__clone() : \phpseclib\Math\BigInteger
__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.
multiply(\phpseclib\Math\BigInteger $x) : \phpseclib\Math\BigInteger
Multiplies two BigIntegers
Here's an example:
<?php
$a = new \phpseclib\Math\BigInteger('10');
$b = new \phpseclib\Math\BigInteger('20');
$c = $a->multiply($b);
echo $c->toString(); // outputs 200 ?>
| \phpseclib\Math\BigInteger | $x |
_karatsuba(array $x_value, array $y_value) : array
Performs Karatsuba multiplication on two BigIntegers
See Karatsuba algorithm and MPM 5.2.3.
| array | $x_value | |
| array | $y_value |
_baseSquare(array $value) : array
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.
| array | $value |
_karatsubaSquare(array $value) : array
Performs Karatsuba "squaring" on two BigIntegers
See Karatsuba algorithm and MPM 5.3.4.
| array | $value |
powMod(\phpseclib\Math\BigInteger $e, \phpseclib\Math\BigInteger $n) : \phpseclib\Math\BigInteger
Performs modular exponentiation.
Alias for modPow().
| \phpseclib\Math\BigInteger | $e | |
| \phpseclib\Math\BigInteger | $n |
_slidingWindow(\phpseclib\Math\BigInteger $e, \phpseclib\Math\BigInteger $n, integer $mode) : \phpseclib\Math\BigInteger
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.
| \phpseclib\Math\BigInteger | $e | |
| \phpseclib\Math\BigInteger | $n | |
| integer | $mode |
_mod2( $n) : \phpseclib\Math\BigInteger
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.
| $n |
_barrett(array $n, array $m) : array
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.
| array | $n | |
| array | $m |
_regularBarrett(array $x, array $n) : array
(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.
| array | $x | |
| array | $n |
_multiplyLower(array $x_value, boolean $x_negative, array $y_value, boolean $y_negative, integer $stop) : array
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.
| array | $x_value | |
| boolean | $x_negative | |
| array | $y_value | |
| boolean | $y_negative | |
| integer | $stop |
_montgomery(array $x, array $n) : array
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.
| array | $x | |
| array | $n |
_montgomeryMultiply(array $x, array $y, array $m) : array
Montgomery Multiply
Interleaves the montgomery reduction and long multiplication algorithms together as described in HAC 14.36
| array | $x | |
| array | $y | |
| array | $m |
_modInverse67108864(array $x) : integer
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!
| array | $x |
gcd(\phpseclib\Math\BigInteger $n) : \phpseclib\Math\BigInteger
Calculates the greatest common divisor
Say you have 693 and 609. The GCD is 21.
Here's an example:
<?php
$a = new \phpseclib\Math\BigInteger(693);
$b = new \phpseclib\Math\BigInteger(609);
$gcd = a->extendedGCD($b);
echo $gcd->toString() . "\r\n"; // outputs 21 ?>
| \phpseclib\Math\BigInteger | $n |
abs() : \phpseclib\Math\BigInteger
Absolute value.
equals(\phpseclib\Math\BigInteger $x) : boolean
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()
| \phpseclib\Math\BigInteger | $x |
bitwise_leftRotate(integer $shift) : \phpseclib\Math\BigInteger
Logical Left Rotate
Instead of the top x bits being dropped they're appended to the shifted bit string.
| integer | $shift |
bitwise_rightRotate(integer $shift) : \phpseclib\Math\BigInteger
Logical Right Rotate
Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
| integer | $shift |
_random_number_helper( $size) : \phpseclib\Math\BigInteger
Generates a random BigInteger
Byte length is equal to $length. Uses \phpseclib\Crypt\Random if it's loaded and mt_rand if it's not.
| $size |
_normalize( $result) : \phpseclib\Math\BigInteger
Normalize
Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
| $result |
_trim(array $value) : \phpseclib\Math\BigInteger
Trim
Removes leading zeros
| array | $value |
_safe_divide(integer $x, integer $y) : integer
Single digit division
Even if int64 is being used the division operator will return a float64 value if the dividend is not evenly divisible by the divisor. Since a float64 doesn't have the precision of int64 this is a problem so, when int64 is being used, we'll guarantee that the dividend is divisible by first subtracting the remainder.
| integer | $x | |
| integer | $y |