2 /* vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4: */
5 * Pure-PHP arbitrary precision integer arithmetic library.
7 * Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available,
8 * and an internal implementation, otherwise.
10 * PHP versions 4 and 5
12 * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
13 * {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
15 * Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
16 * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible
17 * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
18 * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
19 * used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
20 * which only supports integers. Although this fact will slow this library down, the fact that such a high
21 * base is being used should more than compensate.
23 * When PHP version 6 is officially released, we'll be able to use 64-bit integers. This should, once again,
24 * allow bitwise operators, and will increase the maximum possible base to 2**31 (or 2**62 for addition /
27 * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie.
28 * (new Math_BigInteger(pow(2, 26)))->value = array(0, 1)
30 * Useful resources are as follows:
32 * - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
33 * - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
34 * - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
36 * Here's an example of how to use this library:
39 * include('Math/BigInteger.php');
41 * $a = new Math_BigInteger(2);
42 * $b = new Math_BigInteger(3);
46 * echo $c->toString(); // outputs 5
50 * LICENSE: Permission is hereby granted, free of charge, to any person obtaining a copy
51 * of this software and associated documentation files (the "Software"), to deal
52 * in the Software without restriction, including without limitation the rights
53 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
54 * copies of the Software, and to permit persons to whom the Software is
55 * furnished to do so, subject to the following conditions:
57 * The above copyright notice and this permission notice shall be included in
58 * all copies or substantial portions of the Software.
60 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
61 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
62 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
63 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
64 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
65 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
69 * @package Math_BigInteger
70 * @author Jim Wigginton <terrafrost@php.net>
71 * @copyright MMVI Jim Wigginton
72 * @license http://www.opensource.org/licenses/mit-license.html MIT License
73 * @version $Id: BigInteger.php,v 1.33 2010/03/22 22:32:03 terrafrost Exp $
74 * @link http://pear.php.net/package/Math_BigInteger
81 * @see Math_BigInteger::_reduce()
84 * @see Math_BigInteger::_montgomery()
85 * @see Math_BigInteger::_prepMontgomery()
87 define('MATH_BIGINTEGER_MONTGOMERY', 0);
89 * @see Math_BigInteger::_barrett()
91 define('MATH_BIGINTEGER_BARRETT', 1);
93 * @see Math_BigInteger::_mod2()
95 define('MATH_BIGINTEGER_POWEROF2', 2);
97 * @see Math_BigInteger::_remainder()
99 define('MATH_BIGINTEGER_CLASSIC', 3);
101 * @see Math_BigInteger::__clone()
103 define('MATH_BIGINTEGER_NONE', 4);
109 * Rather than create a thousands and thousands of new Math_BigInteger objects in repeated function calls to add() and
110 * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
115 * $result[MATH_BIGINTEGER_VALUE] contains the value.
117 define('MATH_BIGINTEGER_VALUE', 0);
119 * $result[MATH_BIGINTEGER_SIGN] contains the sign.
121 define('MATH_BIGINTEGER_SIGN', 1);
126 * @see Math_BigInteger::_montgomery()
127 * @see Math_BigInteger::_barrett()
132 * $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
134 define('MATH_BIGINTEGER_VARIABLE', 0);
136 * $cache[MATH_BIGINTEGER_DATA] contains the cached data.
138 define('MATH_BIGINTEGER_DATA', 1);
145 * @see Math_BigInteger::Math_BigInteger()
148 * To use the pure-PHP implementation
150 define('MATH_BIGINTEGER_MODE_INTERNAL', 1);
152 * To use the BCMath library
154 * (if enabled; otherwise, the internal implementation will be used)
156 define('MATH_BIGINTEGER_MODE_BCMATH', 2);
158 * To use the GMP library
160 * (if present; otherwise, either the BCMath or the internal implementation will be used)
162 define('MATH_BIGINTEGER_MODE_GMP', 3);
166 * The largest digit that may be used in addition / subtraction
168 * (we do pow(2, 52) instead of using 4503599627370496, directly, because some PHP installations
169 * will truncate 4503599627370496)
173 define('MATH_BIGINTEGER_MAX_DIGIT52', pow(2, 52));
178 * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
182 define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 25);
185 * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
188 * @author Jim Wigginton <terrafrost@php.net>
191 * @package Math_BigInteger
193 class Math_BigInteger
{
195 * Holds the BigInteger's value.
203 * Holds the BigInteger's magnitude.
208 var $is_negative = false;
211 * Random number generator function
213 * @see setRandomGenerator()
216 var $generator = 'mt_rand';
221 * @see setPrecision()
229 * @see setPrecision()
232 var $bitmask = false;
235 * Mode independant value used for serialization.
237 * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
238 * a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value,
239 * however, $this->hex is only calculated when $this->__sleep() is called.
249 * Converts base-2, base-10, base-16, and binary strings (eg. base-256) to BigIntegers.
251 * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
252 * two's compliment. The sole exception to this is -10, which is treated the same as 10 is.
257 * include('Math/BigInteger.php');
259 * $a = new Math_BigInteger('0x32', 16); // 50 in base-16
261 * echo $a->toString(); // outputs 50
265 * @param optional $x base-10 number or base-$base number if $base set.
266 * @param optional integer $base
267 * @return Math_BigInteger
270 function Math_BigInteger($x = 0, $base = 10)
272 if ( !defined('MATH_BIGINTEGER_MODE') ) {
274 case extension_loaded('gmp'):
275 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP
);
277 case extension_loaded('bcmath'):
278 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH
);
281 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL
);
285 if (function_exists('openssl_public_encrypt') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
286 define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
289 switch ( MATH_BIGINTEGER_MODE
) {
290 case MATH_BIGINTEGER_MODE_GMP
:
291 if (is_resource($x) && get_resource_type($x) == 'GMP integer') {
295 $this->value
= gmp_init(0);
297 case MATH_BIGINTEGER_MODE_BCMATH
:
301 $this->value
= array();
304 // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
305 // '0' is the only value like this per http://php.net/empty
306 if (empty($x) && (abs($base) != 256 ||
$x !== '0')) {
312 if (ord($x[0]) & 0x80) {
314 $this->is_negative
= true;
317 switch ( MATH_BIGINTEGER_MODE
) {
318 case MATH_BIGINTEGER_MODE_GMP
:
319 $sign = $this->is_negative ?
'-' : '';
320 $this->value
= gmp_init($sign . '0x' . bin2hex($x));
322 case MATH_BIGINTEGER_MODE_BCMATH
:
323 // round $len to the nearest 4 (thanks, DavidMJ!)
324 $len = (strlen($x) +
3) & 0xFFFFFFFC;
326 $x = str_pad($x, $len, chr(0), STR_PAD_LEFT
);
328 for ($i = 0; $i < $len; $i+
= 4) {
329 $this->value
= bcmul($this->value
, '4294967296', 0); // 4294967296 == 2**32
330 $this->value
= bcadd($this->value
, 0x1000000 * ord($x[$i]) +
((ord($x[$i +
1]) << 16) |
(ord($x[$i +
2]) << 8) |
ord($x[$i +
3])), 0);
333 if ($this->is_negative
) {
334 $this->value
= '-' . $this->value
;
338 // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
341 $this->value
[] = $this->_bytes2int($this->_base256_rshift($x, 26));
345 if ($this->is_negative
) {
346 if (MATH_BIGINTEGER_MODE
!= MATH_BIGINTEGER_MODE_INTERNAL
) {
347 $this->is_negative
= false;
349 $temp = $this->add(new Math_BigInteger('-1'));
350 $this->value
= $temp->value
;
355 if ($base > 0 && $x[0] == '-') {
356 $this->is_negative
= true;
360 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
362 $is_negative = false;
363 if ($base < 0 && hexdec($x[0]) >= 8) {
364 $this->is_negative
= $is_negative = true;
365 $x = bin2hex(~
pack('H*', $x));
368 switch ( MATH_BIGINTEGER_MODE
) {
369 case MATH_BIGINTEGER_MODE_GMP
:
370 $temp = $this->is_negative ?
'-0x' . $x : '0x' . $x;
371 $this->value
= gmp_init($temp);
372 $this->is_negative
= false;
374 case MATH_BIGINTEGER_MODE_BCMATH
:
375 $x = ( strlen($x) & 1 ) ?
'0' . $x : $x;
376 $temp = new Math_BigInteger(pack('H*', $x), 256);
377 $this->value
= $this->is_negative ?
'-' . $temp->value
: $temp->value
;
378 $this->is_negative
= false;
381 $x = ( strlen($x) & 1 ) ?
'0' . $x : $x;
382 $temp = new Math_BigInteger(pack('H*', $x), 256);
383 $this->value
= $temp->value
;
387 $temp = $this->add(new Math_BigInteger('-1'));
388 $this->value
= $temp->value
;
393 $x = preg_replace('#^(-?[0-9]*).*#', '$1', $x);
395 switch ( MATH_BIGINTEGER_MODE
) {
396 case MATH_BIGINTEGER_MODE_GMP
:
397 $this->value
= gmp_init($x);
399 case MATH_BIGINTEGER_MODE_BCMATH
:
400 // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
401 // results then doing it on '-1' does (modInverse does $x[0])
402 $this->value
= (string) $x;
405 $temp = new Math_BigInteger();
407 // array(10000000) is 10**7 in base-2**26. 10**7 is the closest to 2**26 we can get without passing it.
408 $multiplier = new Math_BigInteger();
409 $multiplier->value
= array(10000000);
412 $this->is_negative
= true;
416 $x = str_pad($x, strlen($x) +
(6 * strlen($x)) %
7, 0, STR_PAD_LEFT
);
419 $temp = $temp->multiply($multiplier);
420 $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr($x, 0, 7)), 256));
424 $this->value
= $temp->value
;
427 case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
429 if ($base > 0 && $x[0] == '-') {
430 $this->is_negative
= true;
434 $x = preg_replace('#^([01]*).*#', '$1', $x);
435 $x = str_pad($x, strlen($x) +
(3 * strlen($x)) %
4, 0, STR_PAD_LEFT
);
439 $part = substr($x, 0, 4);
440 $str.= dechex(bindec($part));
444 if ($this->is_negative
) {
448 $temp = new Math_BigInteger($str, 8 * $base); // ie. either -16 or +16
449 $this->value
= $temp->value
;
450 $this->is_negative
= $temp->is_negative
;
454 // base not supported, so we'll let $this == 0
459 * Converts a BigInteger to a byte string (eg. base-256).
461 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
462 * saved as two's compliment.
467 * include('Math/BigInteger.php');
469 * $a = new Math_BigInteger('65');
471 * echo $a->toBytes(); // outputs chr(65)
475 * @param Boolean $twos_compliment
478 * @internal Converts a base-2**26 number to base-2**8
480 function toBytes($twos_compliment = false)
482 if ($twos_compliment) {
483 $comparison = $this->compare(new Math_BigInteger());
484 if ($comparison == 0) {
485 return $this->precision
> 0 ?
str_repeat(chr(0), ($this->precision +
1) >> 3) : '';
488 $temp = $comparison < 0 ?
$this->add(new Math_BigInteger(1)) : $this->copy();
489 $bytes = $temp->toBytes();
491 if (empty($bytes)) { // eg. if the number we're trying to convert is -1
495 if (ord($bytes[0]) & 0x80) {
496 $bytes = chr(0) . $bytes;
499 return $comparison < 0 ? ~
$bytes : $bytes;
502 switch ( MATH_BIGINTEGER_MODE
) {
503 case MATH_BIGINTEGER_MODE_GMP
:
504 if (gmp_cmp($this->value
, gmp_init(0)) == 0) {
505 return $this->precision
> 0 ?
str_repeat(chr(0), ($this->precision +
1) >> 3) : '';
508 $temp = gmp_strval(gmp_abs($this->value
), 16);
509 $temp = ( strlen($temp) & 1 ) ?
'0' . $temp : $temp;
510 $temp = pack('H*', $temp);
512 return $this->precision
> 0 ?
513 substr(str_pad($temp, $this->precision
>> 3, chr(0), STR_PAD_LEFT
), -($this->precision
>> 3)) :
514 ltrim($temp, chr(0));
515 case MATH_BIGINTEGER_MODE_BCMATH
:
516 if ($this->value
=== '0') {
517 return $this->precision
> 0 ?
str_repeat(chr(0), ($this->precision +
1) >> 3) : '';
521 $current = $this->value
;
523 if ($current[0] == '-') {
524 $current = substr($current, 1);
527 while (bccomp($current, '0', 0) > 0) {
528 $temp = bcmod($current, '16777216');
529 $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
530 $current = bcdiv($current, '16777216', 0);
533 return $this->precision
> 0 ?
534 substr(str_pad($value, $this->precision
>> 3, chr(0), STR_PAD_LEFT
), -($this->precision
>> 3)) :
535 ltrim($value, chr(0));
538 if (!count($this->value
)) {
539 return $this->precision
> 0 ?
str_repeat(chr(0), ($this->precision +
1) >> 3) : '';
541 $result = $this->_int2bytes($this->value
[count($this->value
) - 1]);
543 $temp = $this->copy();
545 for ($i = count($temp->value
) - 2; $i >= 0; --$i) {
546 $temp->_base256_lshift($result, 26);
547 $result = $result |
str_pad($temp->_int2bytes($temp->value
[$i]), strlen($result), chr(0), STR_PAD_LEFT
);
550 return $this->precision
> 0 ?
551 str_pad(substr($result, -(($this->precision +
7) >> 3)), ($this->precision +
7) >> 3, chr(0), STR_PAD_LEFT
) :
556 * Converts a BigInteger to a hex string (eg. base-16)).
558 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
559 * saved as two's compliment.
564 * include('Math/BigInteger.php');
566 * $a = new Math_BigInteger('65');
568 * echo $a->toHex(); // outputs '41'
572 * @param Boolean $twos_compliment
575 * @internal Converts a base-2**26 number to base-2**8
577 function toHex($twos_compliment = false)
579 return bin2hex($this->toBytes($twos_compliment));
583 * Converts a BigInteger to a bit string (eg. base-2).
585 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
586 * saved as two's compliment.
591 * include('Math/BigInteger.php');
593 * $a = new Math_BigInteger('65');
595 * echo $a->toBits(); // outputs '1000001'
599 * @param Boolean $twos_compliment
602 * @internal Converts a base-2**26 number to base-2**2
604 function toBits($twos_compliment = false)
606 $hex = $this->toHex($twos_compliment);
608 for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
609 $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT
) . $bits;
611 if ($start) { // hexdec('') == 0
612 $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT
) . $bits;
614 $result = $this->precision
> 0 ?
substr($bits, -$this->precision
) : ltrim($bits, '0');
616 if ($twos_compliment && $this->compare(new Math_BigInteger()) > 0 && $this->precision
<= 0) {
617 return '0' . $result;
624 * Converts a BigInteger to a base-10 number.
629 * include('Math/BigInteger.php');
631 * $a = new Math_BigInteger('50');
633 * echo $a->toString(); // outputs 50
639 * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
643 switch ( MATH_BIGINTEGER_MODE
) {
644 case MATH_BIGINTEGER_MODE_GMP
:
645 return gmp_strval($this->value
);
646 case MATH_BIGINTEGER_MODE_BCMATH
:
647 if ($this->value
=== '0') {
651 return ltrim($this->value
, '0');
654 if (!count($this->value
)) {
658 $temp = $this->copy();
659 $temp->is_negative
= false;
661 $divisor = new Math_BigInteger();
662 $divisor->value
= array(10000000); // eg. 10**7
664 while (count($temp->value
)) {
665 list($temp, $mod) = $temp->divide($divisor);
666 $result = str_pad(isset($mod->value
[0]) ?
$mod->value
[0] : '', 7, '0', STR_PAD_LEFT
) . $result;
668 $result = ltrim($result, '0');
669 if (empty($result)) {
673 if ($this->is_negative
) {
674 $result = '-' . $result;
683 * PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee
684 * that all objects are passed by value, when appropriate. More information can be found here:
686 * {@link http://php.net/language.oop5.basic#51624}
690 * @return Math_BigInteger
694 $temp = new Math_BigInteger();
695 $temp->value
= $this->value
;
696 $temp->is_negative
= $this->is_negative
;
697 $temp->generator
= $this->generator
;
698 $temp->precision
= $this->precision
;
699 $temp->bitmask
= $this->bitmask
;
704 * __toString() magic method
706 * Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call
710 * @internal Implemented per a suggestion by Techie-Michael - thanks!
712 function __toString()
714 return $this->toString();
718 * __clone() magic method
720 * Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone()
721 * 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
722 * only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and PHP5,
723 * call Math_BigInteger::copy(), instead.
727 * @return Math_BigInteger
731 return $this->copy();
735 * __sleep() magic method
737 * Will be called, automatically, when serialize() is called on a Math_BigInteger object.
744 $this->hex
= $this->toHex(true);
745 $vars = array('hex');
746 if ($this->generator
!= 'mt_rand') {
747 $vars[] = 'generator';
749 if ($this->precision
> 0) {
750 $vars[] = 'precision';
757 * __wakeup() magic method
759 * Will be called, automatically, when unserialize() is called on a Math_BigInteger object.
766 $temp = new Math_BigInteger($this->hex
, -16);
767 $this->value
= $temp->value
;
768 $this->is_negative
= $temp->is_negative
;
769 $this->setRandomGenerator($this->generator
);
770 if ($this->precision
> 0) {
771 // recalculate $this->bitmask
772 $this->setPrecision($this->precision
);
777 * Adds two BigIntegers.
782 * include('Math/BigInteger.php');
784 * $a = new Math_BigInteger('10');
785 * $b = new Math_BigInteger('20');
789 * echo $c->toString(); // outputs 30
793 * @param Math_BigInteger $y
794 * @return Math_BigInteger
796 * @internal Performs base-2**52 addition
800 switch ( MATH_BIGINTEGER_MODE
) {
801 case MATH_BIGINTEGER_MODE_GMP
:
802 $temp = new Math_BigInteger();
803 $temp->value
= gmp_add($this->value
, $y->value
);
805 return $this->_normalize($temp);
806 case MATH_BIGINTEGER_MODE_BCMATH
:
807 $temp = new Math_BigInteger();
808 $temp->value
= bcadd($this->value
, $y->value
, 0);
810 return $this->_normalize($temp);
813 $temp = $this->_add($this->value
, $this->is_negative
, $y->value
, $y->is_negative
);
815 $result = new Math_BigInteger();
816 $result->value
= $temp[MATH_BIGINTEGER_VALUE
];
817 $result->is_negative
= $temp[MATH_BIGINTEGER_SIGN
];
819 return $this->_normalize($result);
825 * @param Array $x_value
826 * @param Boolean $x_negative
827 * @param Array $y_value
828 * @param Boolean $y_negative
832 function _add($x_value, $x_negative, $y_value, $y_negative)
834 $x_size = count($x_value);
835 $y_size = count($y_value);
839 MATH_BIGINTEGER_VALUE
=> $y_value,
840 MATH_BIGINTEGER_SIGN
=> $y_negative
842 } else if ($y_size == 0) {
844 MATH_BIGINTEGER_VALUE
=> $x_value,
845 MATH_BIGINTEGER_SIGN
=> $x_negative
849 // subtract, if appropriate
850 if ( $x_negative != $y_negative ) {
851 if ( $x_value == $y_value ) {
853 MATH_BIGINTEGER_VALUE
=> array(),
854 MATH_BIGINTEGER_SIGN
=> false
858 $temp = $this->_subtract($x_value, false, $y_value, false);
859 $temp[MATH_BIGINTEGER_SIGN
] = $this->_compare($x_value, false, $y_value, false) > 0 ?
860 $x_negative : $y_negative;
865 if ($x_size < $y_size) {
873 $value[] = 0; // just in case the carry adds an extra digit
876 for ($i = 0, $j = 1; $j < $size; $i+
=2, $j+
=2) {
877 $sum = $x_value[$j] * 0x4000000 +
$x_value[$i] +
$y_value[$j] * 0x4000000 +
$y_value[$i] +
$carry;
878 $carry = $sum >= MATH_BIGINTEGER_MAX_DIGIT52
; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
879 $sum = $carry ?
$sum - MATH_BIGINTEGER_MAX_DIGIT52
: $sum;
881 $temp = (int) ($sum / 0x4000000);
883 $value[$i] = (int) ($sum - 0x4000000 * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
887 if ($j == $size) { // ie. if $y_size is odd
888 $sum = $x_value[$i] +
$y_value[$i] +
$carry;
889 $carry = $sum >= 0x4000000;
890 $value[$i] = $carry ?
$sum - 0x4000000 : $sum;
891 ++
$i; // ie. let $i = $j since we've just done $value[$i]
895 for (; $value[$i] == 0x3FFFFFF; ++
$i) {
902 MATH_BIGINTEGER_VALUE
=> $this->_trim($value),
903 MATH_BIGINTEGER_SIGN
=> $x_negative
908 * Subtracts two BigIntegers.
913 * include('Math/BigInteger.php');
915 * $a = new Math_BigInteger('10');
916 * $b = new Math_BigInteger('20');
918 * $c = $a->subtract($b);
920 * echo $c->toString(); // outputs -10
924 * @param Math_BigInteger $y
925 * @return Math_BigInteger
927 * @internal Performs base-2**52 subtraction
929 function subtract($y)
931 switch ( MATH_BIGINTEGER_MODE
) {
932 case MATH_BIGINTEGER_MODE_GMP
:
933 $temp = new Math_BigInteger();
934 $temp->value
= gmp_sub($this->value
, $y->value
);
936 return $this->_normalize($temp);
937 case MATH_BIGINTEGER_MODE_BCMATH
:
938 $temp = new Math_BigInteger();
939 $temp->value
= bcsub($this->value
, $y->value
, 0);
941 return $this->_normalize($temp);
944 $temp = $this->_subtract($this->value
, $this->is_negative
, $y->value
, $y->is_negative
);
946 $result = new Math_BigInteger();
947 $result->value
= $temp[MATH_BIGINTEGER_VALUE
];
948 $result->is_negative
= $temp[MATH_BIGINTEGER_SIGN
];
950 return $this->_normalize($result);
954 * Performs subtraction.
956 * @param Array $x_value
957 * @param Boolean $x_negative
958 * @param Array $y_value
959 * @param Boolean $y_negative
963 function _subtract($x_value, $x_negative, $y_value, $y_negative)
965 $x_size = count($x_value);
966 $y_size = count($y_value);
970 MATH_BIGINTEGER_VALUE
=> $y_value,
971 MATH_BIGINTEGER_SIGN
=> !$y_negative
973 } else if ($y_size == 0) {
975 MATH_BIGINTEGER_VALUE
=> $x_value,
976 MATH_BIGINTEGER_SIGN
=> $x_negative
980 // add, if appropriate (ie. -$x - +$y or +$x - -$y)
981 if ( $x_negative != $y_negative ) {
982 $temp = $this->_add($x_value, false, $y_value, false);
983 $temp[MATH_BIGINTEGER_SIGN
] = $x_negative;
988 $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
992 MATH_BIGINTEGER_VALUE
=> array(),
993 MATH_BIGINTEGER_SIGN
=> false
997 // switch $x and $y around, if appropriate.
998 if ( (!$x_negative && $diff < 0) ||
($x_negative && $diff > 0) ) {
1000 $x_value = $y_value;
1003 $x_negative = !$x_negative;
1005 $x_size = count($x_value);
1006 $y_size = count($y_value);
1009 // at this point, $x_value should be at least as big as - if not bigger than - $y_value
1012 for ($i = 0, $j = 1; $j < $y_size; $i+
=2, $j+
=2) {
1013 $sum = $x_value[$j] * 0x4000000 +
$x_value[$i] - $y_value[$j] * 0x4000000 - $y_value[$i] - $carry;
1014 $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
1015 $sum = $carry ?
$sum + MATH_BIGINTEGER_MAX_DIGIT52
: $sum;
1017 $temp = (int) ($sum / 0x4000000);
1019 $x_value[$i] = (int) ($sum - 0x4000000 * $temp);
1020 $x_value[$j] = $temp;
1023 if ($j == $y_size) { // ie. if $y_size is odd
1024 $sum = $x_value[$i] - $y_value[$i] - $carry;
1026 $x_value[$i] = $carry ?
$sum +
0x4000000 : $sum;
1031 for (; !$x_value[$i]; ++
$i) {
1032 $x_value[$i] = 0x3FFFFFF;
1038 MATH_BIGINTEGER_VALUE
=> $this->_trim($x_value),
1039 MATH_BIGINTEGER_SIGN
=> $x_negative
1044 * Multiplies two BigIntegers
1046 * Here's an example:
1049 * include('Math/BigInteger.php');
1051 * $a = new Math_BigInteger('10');
1052 * $b = new Math_BigInteger('20');
1054 * $c = $a->multiply($b);
1056 * echo $c->toString(); // outputs 200
1060 * @param Math_BigInteger $x
1061 * @return Math_BigInteger
1064 function multiply($x)
1066 switch ( MATH_BIGINTEGER_MODE
) {
1067 case MATH_BIGINTEGER_MODE_GMP
:
1068 $temp = new Math_BigInteger();
1069 $temp->value
= gmp_mul($this->value
, $x->value
);
1071 return $this->_normalize($temp);
1072 case MATH_BIGINTEGER_MODE_BCMATH
:
1073 $temp = new Math_BigInteger();
1074 $temp->value
= bcmul($this->value
, $x->value
, 0);
1076 return $this->_normalize($temp);
1079 $temp = $this->_multiply($this->value
, $this->is_negative
, $x->value
, $x->is_negative
);
1081 $product = new Math_BigInteger();
1082 $product->value
= $temp[MATH_BIGINTEGER_VALUE
];
1083 $product->is_negative
= $temp[MATH_BIGINTEGER_SIGN
];
1085 return $this->_normalize($product);
1089 * Performs multiplication.
1091 * @param Array $x_value
1092 * @param Boolean $x_negative
1093 * @param Array $y_value
1094 * @param Boolean $y_negative
1098 function _multiply($x_value, $x_negative, $y_value, $y_negative)
1100 //if ( $x_value == $y_value ) {
1102 // MATH_BIGINTEGER_VALUE => $this->_square($x_value),
1103 // MATH_BIGINTEGER_SIGN => $x_sign != $y_value
1107 $x_length = count($x_value);
1108 $y_length = count($y_value);
1110 if ( !$x_length ||
!$y_length ) { // a 0 is being multiplied
1112 MATH_BIGINTEGER_VALUE
=> array(),
1113 MATH_BIGINTEGER_SIGN
=> false
1118 MATH_BIGINTEGER_VALUE
=> min($x_length, $y_length) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
1119 $this->_trim($this->_regularMultiply($x_value, $y_value)) :
1120 $this->_trim($this->_karatsuba($x_value, $y_value)),
1121 MATH_BIGINTEGER_SIGN
=> $x_negative != $y_negative
1126 * Performs long multiplication on two BigIntegers
1128 * Modeled after 'multiply' in MutableBigInteger.java.
1130 * @param Array $x_value
1131 * @param Array $y_value
1135 function _regularMultiply($x_value, $y_value)
1137 $x_length = count($x_value);
1138 $y_length = count($y_value);
1140 if ( !$x_length ||
!$y_length ) { // a 0 is being multiplied
1144 if ( $x_length < $y_length ) {
1146 $x_value = $y_value;
1149 $x_length = count($x_value);
1150 $y_length = count($y_value);
1153 $product_value = $this->_array_repeat(0, $x_length +
$y_length);
1155 // the following for loop could be removed if the for loop following it
1156 // (the one with nested for loops) initially set $i to 0, but
1157 // doing so would also make the result in one set of unnecessary adds,
1158 // since on the outermost loops first pass, $product->value[$k] is going
1163 for ($j = 0; $j < $x_length; ++
$j) { // ie. $i = 0
1164 $temp = $x_value[$j] * $y_value[0] +
$carry; // $product_value[$k] == 0
1165 $carry = (int) ($temp / 0x4000000);
1166 $product_value[$j] = (int) ($temp - 0x4000000 * $carry);
1169 $product_value[$j] = $carry;
1171 // the above for loop is what the previous comment was talking about. the
1172 // following for loop is the "one with nested for loops"
1173 for ($i = 1; $i < $y_length; ++
$i) {
1176 for ($j = 0, $k = $i; $j < $x_length; ++
$j, ++
$k) {
1177 $temp = $product_value[$k] +
$x_value[$j] * $y_value[$i] +
$carry;
1178 $carry = (int) ($temp / 0x4000000);
1179 $product_value[$k] = (int) ($temp - 0x4000000 * $carry);
1182 $product_value[$k] = $carry;
1185 return $product_value;
1189 * Performs Karatsuba multiplication on two BigIntegers
1191 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1192 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
1194 * @param Array $x_value
1195 * @param Array $y_value
1199 function _karatsuba($x_value, $y_value)
1201 $m = min(count($x_value) >> 1, count($y_value) >> 1);
1203 if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF
) {
1204 return $this->_regularMultiply($x_value, $y_value);
1207 $x1 = array_slice($x_value, $m);
1208 $x0 = array_slice($x_value, 0, $m);
1209 $y1 = array_slice($y_value, $m);
1210 $y0 = array_slice($y_value, 0, $m);
1212 $z2 = $this->_karatsuba($x1, $y1);
1213 $z0 = $this->_karatsuba($x0, $y0);
1215 $z1 = $this->_add($x1, false, $x0, false);
1216 $temp = $this->_add($y1, false, $y0, false);
1217 $z1 = $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE
], $temp[MATH_BIGINTEGER_VALUE
]);
1218 $temp = $this->_add($z2, false, $z0, false);
1219 $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE
], false);
1221 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1222 $z1[MATH_BIGINTEGER_VALUE
] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE
]);
1224 $xy = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE
], $z1[MATH_BIGINTEGER_SIGN
]);
1225 $xy = $this->_add($xy[MATH_BIGINTEGER_VALUE
], $xy[MATH_BIGINTEGER_SIGN
], $z0, false);
1227 return $xy[MATH_BIGINTEGER_VALUE
];
1237 function _square($x = false)
1239 return count($x) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
1240 $this->_trim($this->_baseSquare($x)) :
1241 $this->_trim($this->_karatsubaSquare($x));
1245 * Performs traditional squaring on two BigIntegers
1247 * Squaring can be done faster than multiplying a number by itself can be. See
1248 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
1249 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
1251 * @param Array $value
1255 function _baseSquare($value)
1257 if ( empty($value) ) {
1260 $square_value = $this->_array_repeat(0, 2 * count($value));
1262 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++
$i) {
1265 $temp = $square_value[$i2] +
$value[$i] * $value[$i];
1266 $carry = (int) ($temp / 0x4000000);
1267 $square_value[$i2] = (int) ($temp - 0x4000000 * $carry);
1269 // note how we start from $i+1 instead of 0 as we do in multiplication.
1270 for ($j = $i +
1, $k = $i2 +
1; $j <= $max_index; ++
$j, ++
$k) {
1271 $temp = $square_value[$k] +
2 * $value[$j] * $value[$i] +
$carry;
1272 $carry = (int) ($temp / 0x4000000);
1273 $square_value[$k] = (int) ($temp - 0x4000000 * $carry);
1276 // the following line can yield values larger 2**15. at this point, PHP should switch
1278 $square_value[$i +
$max_index +
1] = $carry;
1281 return $square_value;
1285 * Performs Karatsuba "squaring" on two BigIntegers
1287 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1288 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
1290 * @param Array $value
1294 function _karatsubaSquare($value)
1296 $m = count($value) >> 1;
1298 if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF
) {
1299 return $this->_baseSquare($value);
1302 $x1 = array_slice($value, $m);
1303 $x0 = array_slice($value, 0, $m);
1305 $z2 = $this->_karatsubaSquare($x1);
1306 $z0 = $this->_karatsubaSquare($x0);
1308 $z1 = $this->_add($x1, false, $x0, false);
1309 $z1 = $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE
]);
1310 $temp = $this->_add($z2, false, $z0, false);
1311 $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE
], false);
1313 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1314 $z1[MATH_BIGINTEGER_VALUE
] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE
]);
1316 $xx = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE
], $z1[MATH_BIGINTEGER_SIGN
]);
1317 $xx = $this->_add($xx[MATH_BIGINTEGER_VALUE
], $xx[MATH_BIGINTEGER_SIGN
], $z0, false);
1319 return $xx[MATH_BIGINTEGER_VALUE
];
1323 * Divides two BigIntegers.
1325 * Returns an array whose first element contains the quotient and whose second element contains the
1326 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the
1327 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder
1328 * and the divisor (basically, the "common residue" is the first positive modulo).
1330 * Here's an example:
1333 * include('Math/BigInteger.php');
1335 * $a = new Math_BigInteger('10');
1336 * $b = new Math_BigInteger('20');
1338 * list($quotient, $remainder) = $a->divide($b);
1340 * echo $quotient->toString(); // outputs 0
1342 * echo $remainder->toString(); // outputs 10
1346 * @param Math_BigInteger $y
1349 * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
1353 switch ( MATH_BIGINTEGER_MODE
) {
1354 case MATH_BIGINTEGER_MODE_GMP
:
1355 $quotient = new Math_BigInteger();
1356 $remainder = new Math_BigInteger();
1358 list($quotient->value
, $remainder->value
) = gmp_div_qr($this->value
, $y->value
);
1360 if (gmp_sign($remainder->value
) < 0) {
1361 $remainder->value
= gmp_add($remainder->value
, gmp_abs($y->value
));
1364 return array($this->_normalize($quotient), $this->_normalize($remainder));
1365 case MATH_BIGINTEGER_MODE_BCMATH
:
1366 $quotient = new Math_BigInteger();
1367 $remainder = new Math_BigInteger();
1369 $quotient->value
= bcdiv($this->value
, $y->value
, 0);
1370 $remainder->value
= bcmod($this->value
, $y->value
);
1372 if ($remainder->value
[0] == '-') {
1373 $remainder->value
= bcadd($remainder->value
, $y->value
[0] == '-' ?
substr($y->value
, 1) : $y->value
, 0);
1376 return array($this->_normalize($quotient), $this->_normalize($remainder));
1379 if (count($y->value
) == 1) {
1380 list($q, $r) = $this->_divide_digit($this->value
, $y->value
[0]);
1381 $quotient = new Math_BigInteger();
1382 $remainder = new Math_BigInteger();
1383 $quotient->value
= $q;
1384 $remainder->value
= array($r);
1385 $quotient->is_negative
= $this->is_negative
!= $y->is_negative
;
1386 return array($this->_normalize($quotient), $this->_normalize($remainder));
1390 if ( !isset($zero) ) {
1391 $zero = new Math_BigInteger();
1397 $x_sign = $x->is_negative
;
1398 $y_sign = $y->is_negative
;
1400 $x->is_negative
= $y->is_negative
= false;
1402 $diff = $x->compare($y);
1405 $temp = new Math_BigInteger();
1406 $temp->value
= array(1);
1407 $temp->is_negative
= $x_sign != $y_sign;
1408 return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger()));
1412 // if $x is negative, "add" $y.
1414 $x = $y->subtract($x);
1416 return array($this->_normalize(new Math_BigInteger()), $this->_normalize($x));
1419 // normalize $x and $y as described in HAC 14.23 / 14.24
1420 $msb = $y->value
[count($y->value
) - 1];
1421 for ($shift = 0; !($msb & 0x2000000); ++
$shift) {
1424 $x->_lshift($shift);
1425 $y->_lshift($shift);
1426 $y_value = &$y->value
;
1428 $x_max = count($x->value
) - 1;
1429 $y_max = count($y->value
) - 1;
1431 $quotient = new Math_BigInteger();
1432 $quotient_value = &$quotient->value
;
1433 $quotient_value = $this->_array_repeat(0, $x_max - $y_max +
1);
1435 static $temp, $lhs, $rhs;
1436 if (!isset($temp)) {
1437 $temp = new Math_BigInteger();
1438 $lhs = new Math_BigInteger();
1439 $rhs = new Math_BigInteger();
1441 $temp_value = &$temp->value
;
1442 $rhs_value = &$rhs->value
;
1444 // $temp = $y << ($x_max - $y_max-1) in base 2**26
1445 $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
1447 while ( $x->compare($temp) >= 0 ) {
1448 // calculate the "common residue"
1449 ++
$quotient_value[$x_max - $y_max];
1450 $x = $x->subtract($temp);
1451 $x_max = count($x->value
) - 1;
1454 for ($i = $x_max; $i >= $y_max +
1; --$i) {
1455 $x_value = &$x->value
;
1457 isset($x_value[$i]) ?
$x_value[$i] : 0,
1458 isset($x_value[$i - 1]) ?
$x_value[$i - 1] : 0,
1459 isset($x_value[$i - 2]) ?
$x_value[$i - 2] : 0
1463 ( $y_max > 0 ) ?
$y_value[$y_max - 1] : 0
1466 $q_index = $i - $y_max - 1;
1467 if ($x_window[0] == $y_window[0]) {
1468 $quotient_value[$q_index] = 0x3FFFFFF;
1470 $quotient_value[$q_index] = (int) (
1471 ($x_window[0] * 0x4000000 +
$x_window[1])
1477 $temp_value = array($y_window[1], $y_window[0]);
1479 $lhs->value
= array($quotient_value[$q_index]);
1480 $lhs = $lhs->multiply($temp);
1482 $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
1484 while ( $lhs->compare($rhs) > 0 ) {
1485 --$quotient_value[$q_index];
1487 $lhs->value
= array($quotient_value[$q_index]);
1488 $lhs = $lhs->multiply($temp);
1491 $adjust = $this->_array_repeat(0, $q_index);
1492 $temp_value = array($quotient_value[$q_index]);
1493 $temp = $temp->multiply($y);
1494 $temp_value = &$temp->value
;
1495 $temp_value = array_merge($adjust, $temp_value);
1497 $x = $x->subtract($temp);
1499 if ($x->compare($zero) < 0) {
1500 $temp_value = array_merge($adjust, $y_value);
1501 $x = $x->add($temp);
1503 --$quotient_value[$q_index];
1506 $x_max = count($x_value) - 1;
1509 // unnormalize the remainder
1510 $x->_rshift($shift);
1512 $quotient->is_negative
= $x_sign != $y_sign;
1514 // calculate the "common residue", if appropriate
1516 $y->_rshift($shift);
1517 $x = $y->subtract($x);
1520 return array($this->_normalize($quotient), $this->_normalize($x));
1524 * Divides a BigInteger by a regular integer
1526 * abc / x = a00 / x + b0 / x + c / x
1528 * @param Array $dividend
1529 * @param Array $divisor
1533 function _divide_digit($dividend, $divisor)
1538 for ($i = count($dividend) - 1; $i >= 0; --$i) {
1539 $temp = 0x4000000 * $carry +
$dividend[$i];
1540 $result[$i] = (int) ($temp / $divisor);
1541 $carry = (int) ($temp - $divisor * $result[$i]);
1544 return array($result, $carry);
1548 * Performs modular exponentiation.
1550 * Here's an example:
1553 * include('Math/BigInteger.php');
1555 * $a = new Math_BigInteger('10');
1556 * $b = new Math_BigInteger('20');
1557 * $c = new Math_BigInteger('30');
1559 * $c = $a->modPow($b, $c);
1561 * echo $c->toString(); // outputs 10
1565 * @param Math_BigInteger $e
1566 * @param Math_BigInteger $n
1567 * @return Math_BigInteger
1569 * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
1570 * and although the approach involving repeated squaring does vastly better, it, too, is impractical
1571 * for our purposes. The reason being that division - by far the most complicated and time-consuming
1572 * of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
1574 * Modular reductions resolve this issue. Although an individual modular reduction takes more time
1575 * then an individual division, when performed in succession (with the same modulo), they're a lot faster.
1577 * The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction,
1578 * although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the
1579 * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
1580 * the product of two odd numbers is odd), but what about when RSA isn't used?
1582 * In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a
1583 * Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the
1584 * modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however,
1585 * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
1586 * the other, a power of two - and recombine them, later. This is the method that this modPow function uses.
1587 * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
1589 function modPow($e, $n)
1591 $n = $this->bitmask
!== false && $this->bitmask
->compare($n) < 0 ?
$this->bitmask
: $n->abs();
1593 if ($e->compare(new Math_BigInteger()) < 0) {
1596 $temp = $this->modInverse($n);
1597 if ($temp === false) {
1601 return $this->_normalize($temp->modPow($e, $n));
1604 if (MATH_BIGINTEGER_MODE
== MATH_BIGINTEGER_MODE_GMP
) {
1605 $temp = new Math_BigInteger();
1606 $temp->value
= gmp_powm($this->value
, $e->value
, $n->value
);
1608 return $this->_normalize($temp);
1611 if ($this->compare(new Math_BigInteger()) < 0 ||
$this->compare($n) > 0) {
1612 list(, $temp) = $this->divide($n);
1613 return $temp->modPow($e, $n);
1616 if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
1617 $components = array(
1618 'modulus' => $n->toBytes(true),
1619 'publicExponent' => $e->toBytes(true)
1622 $components = array(
1623 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
1624 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
1627 $RSAPublicKey = pack('Ca*a*a*',
1628 48, $this->_encodeASN1Length(strlen($components['modulus']) +
strlen($components['publicExponent'])),
1629 $components['modulus'], $components['publicExponent']
1632 $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
1633 $RSAPublicKey = chr(0) . $RSAPublicKey;
1634 $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
1636 $encapsulated = pack('Ca*a*',
1637 48, $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)), $rsaOID . $RSAPublicKey
1640 $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
1641 chunk_split(base64_encode($encapsulated)) .
1642 '-----END PUBLIC KEY-----';
1644 $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT
);
1646 if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING
)) {
1647 return new Math_BigInteger($result, 256);
1651 switch ( MATH_BIGINTEGER_MODE
) {
1652 case MATH_BIGINTEGER_MODE_GMP
:
1653 $temp = new Math_BigInteger();
1654 $temp->value
= gmp_powm($this->value
, $e->value
, $n->value
);
1656 return $this->_normalize($temp);
1657 case MATH_BIGINTEGER_MODE_BCMATH
:
1658 $temp = new Math_BigInteger();
1659 $temp->value
= bcpowmod($this->value
, $e->value
, $n->value
, 0);
1661 return $this->_normalize($temp);
1664 if ( empty($e->value
) ) {
1665 $temp = new Math_BigInteger();
1666 $temp->value
= array(1);
1667 return $this->_normalize($temp);
1670 if ( $e->value
== array(1) ) {
1671 list(, $temp) = $this->divide($n);
1672 return $this->_normalize($temp);
1675 if ( $e->value
== array(2) ) {
1676 $temp = new Math_BigInteger();
1677 $temp->value
= $this->_square($this->value
);
1678 list(, $temp) = $temp->divide($n);
1679 return $this->_normalize($temp);
1682 return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT
));
1684 // is the modulo odd?
1685 if ( $n->value
[0] & 1 ) {
1686 return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY
));
1688 // if it's not, it's even
1690 // find the lowest set bit (eg. the max pow of 2 that divides $n)
1691 for ($i = 0; $i < count($n->value
); ++
$i) {
1692 if ( $n->value
[$i] ) {
1693 $temp = decbin($n->value
[$i]);
1694 $j = strlen($temp) - strrpos($temp, '1') - 1;
1699 // at this point, 2^$j * $n/(2^$j) == $n
1703 $mod2 = new Math_BigInteger();
1704 $mod2->value
= array(1);
1707 $part1 = ( $mod1->value
!= array(1) ) ?
$this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY
) : new Math_BigInteger();
1708 $part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2
);
1710 $y1 = $mod2->modInverse($mod1);
1711 $y2 = $mod1->modInverse($mod2);
1713 $result = $part1->multiply($mod2);
1714 $result = $result->multiply($y1);
1716 $temp = $part2->multiply($mod1);
1717 $temp = $temp->multiply($y2);
1719 $result = $result->add($temp);
1720 list(, $result) = $result->divide($n);
1722 return $this->_normalize($result);
1726 * Performs modular exponentiation.
1728 * Alias for Math_BigInteger::modPow()
1730 * @param Math_BigInteger $e
1731 * @param Math_BigInteger $n
1732 * @return Math_BigInteger
1735 function powMod($e, $n)
1737 return $this->modPow($e, $n);
1741 * Sliding Window k-ary Modular Exponentiation
1743 * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
1744 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims,
1745 * however, this function performs a modular reduction after every multiplication and squaring operation.
1746 * As such, this function has the same preconditions that the reductions being used do.
1748 * @param Math_BigInteger $e
1749 * @param Math_BigInteger $n
1750 * @param Integer $mode
1751 * @return Math_BigInteger
1754 function _slidingWindow($e, $n, $mode)
1756 static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
1757 //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
1759 $e_value = $e->value
;
1760 $e_length = count($e_value) - 1;
1761 $e_bits = decbin($e_value[$e_length]);
1762 for ($i = $e_length - 1; $i >= 0; --$i) {
1763 $e_bits.= str_pad(decbin($e_value[$i]), 26, '0', STR_PAD_LEFT
);
1766 $e_length = strlen($e_bits);
1768 // calculate the appropriate window size.
1769 // $window_size == 3 if $window_ranges is between 25 and 81, for example.
1770 for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); ++
$window_size, ++
$i);
1772 $n_value = $n->value
;
1774 // precompute $this^0 through $this^$window_size
1776 $powers[1] = $this->_prepareReduce($this->value
, $n_value, $mode);
1777 $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
1779 // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
1780 // in a 1. ie. it's supposed to be odd.
1781 $temp = 1 << ($window_size - 1);
1782 for ($i = 1; $i < $temp; ++
$i) {
1784 $powers[$i2 +
1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
1788 $result = $this->_prepareReduce($result, $n_value, $mode);
1790 for ($i = 0; $i < $e_length; ) {
1791 if ( !$e_bits[$i] ) {
1792 $result = $this->_squareReduce($result, $n_value, $mode);
1795 for ($j = $window_size - 1; $j > 0; --$j) {
1796 if ( !empty($e_bits[$i +
$j]) ) {
1801 for ($k = 0; $k <= $j; ++
$k) {// eg. the length of substr($e_bits, $i, $j+1)
1802 $result = $this->_squareReduce($result, $n_value, $mode);
1805 $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j +
1))], $n_value, $mode);
1811 $temp = new Math_BigInteger();
1812 $temp->value
= $this->_reduce($result, $n_value, $mode);
1820 * For most $modes this will return the remainder.
1822 * @see _slidingWindow()
1826 * @param Integer $mode
1829 function _reduce($x, $n, $mode)
1832 case MATH_BIGINTEGER_MONTGOMERY
:
1833 return $this->_montgomery($x, $n);
1834 case MATH_BIGINTEGER_BARRETT
:
1835 return $this->_barrett($x, $n);
1836 case MATH_BIGINTEGER_POWEROF2
:
1837 $lhs = new Math_BigInteger();
1839 $rhs = new Math_BigInteger();
1841 return $x->_mod2($n);
1842 case MATH_BIGINTEGER_CLASSIC
:
1843 $lhs = new Math_BigInteger();
1845 $rhs = new Math_BigInteger();
1847 list(, $temp) = $lhs->divide($rhs);
1848 return $temp->value
;
1849 case MATH_BIGINTEGER_NONE
:
1852 // an invalid $mode was provided
1857 * Modular reduction preperation
1859 * @see _slidingWindow()
1863 * @param Integer $mode
1866 function _prepareReduce($x, $n, $mode)
1868 if ($mode == MATH_BIGINTEGER_MONTGOMERY
) {
1869 return $this->_prepMontgomery($x, $n);
1871 return $this->_reduce($x, $n, $mode);
1877 * @see _slidingWindow()
1882 * @param Integer $mode
1885 function _multiplyReduce($x, $y, $n, $mode)
1887 if ($mode == MATH_BIGINTEGER_MONTGOMERY
) {
1888 return $this->_montgomeryMultiply($x, $y, $n);
1890 $temp = $this->_multiply($x, false, $y, false);
1891 return $this->_reduce($temp[MATH_BIGINTEGER_VALUE
], $n, $mode);
1897 * @see _slidingWindow()
1901 * @param Integer $mode
1904 function _squareReduce($x, $n, $mode)
1906 if ($mode == MATH_BIGINTEGER_MONTGOMERY
) {
1907 return $this->_montgomeryMultiply($x, $x, $n);
1909 return $this->_reduce($this->_square($x), $n, $mode);
1913 * Modulos for Powers of Two
1915 * Calculates $x%$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1),
1916 * we'll just use this function as a wrapper for doing that.
1918 * @see _slidingWindow()
1920 * @param Math_BigInteger
1921 * @return Math_BigInteger
1925 $temp = new Math_BigInteger();
1926 $temp->value
= array(1);
1927 return $this->bitwise_and($n->subtract($temp));
1931 * Barrett Modular Reduction
1933 * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
1934 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly,
1935 * so as not to require negative numbers (initially, this script didn't support negative numbers).
1937 * Employs "folding", as described at
1938 * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from
1939 * 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."
1941 * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
1942 * usable on account of (1) its not using reasonable radix points as discussed in
1943 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
1944 * radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that
1945 * (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
1946 * comments for details.
1948 * @see _slidingWindow()
1954 function _barrett($n, $m)
1956 static $cache = array(
1957 MATH_BIGINTEGER_VARIABLE
=> array(),
1958 MATH_BIGINTEGER_DATA
=> array()
1961 $m_length = count($m);
1963 // if ($this->_compare($n, $this->_square($m)) >= 0) {
1964 if (count($n) > 2 * $m_length) {
1965 $lhs = new Math_BigInteger();
1966 $rhs = new Math_BigInteger();
1969 list(, $temp) = $lhs->divide($rhs);
1970 return $temp->value
;
1973 // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
1974 if ($m_length < 5) {
1975 return $this->_regularBarrett($n, $m);
1980 if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE
])) === false ) {
1981 $key = count($cache[MATH_BIGINTEGER_VARIABLE
]);
1982 $cache[MATH_BIGINTEGER_VARIABLE
][] = $m;
1984 $lhs = new Math_BigInteger();
1985 $lhs_value = &$lhs->value
;
1986 $lhs_value = $this->_array_repeat(0, $m_length +
($m_length >> 1));
1988 $rhs = new Math_BigInteger();
1991 list($u, $m1) = $lhs->divide($rhs);
1995 $cache[MATH_BIGINTEGER_DATA
][] = array(
1996 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
1997 'm1'=> $m1 // m.length
2000 extract($cache[MATH_BIGINTEGER_DATA
][$key]);
2003 $cutoff = $m_length +
($m_length >> 1);
2004 $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
2005 $msd = array_slice($n, $cutoff); // m.length >> 1
2006 $lsd = $this->_trim($lsd);
2007 $temp = $this->_multiply($msd, false, $m1, false);
2008 $n = $this->_add($lsd, false, $temp[MATH_BIGINTEGER_VALUE
], false); // m.length + (m.length >> 1) + 1
2010 if ($m_length & 1) {
2011 return $this->_regularBarrett($n[MATH_BIGINTEGER_VALUE
], $m);
2014 // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
2015 $temp = array_slice($n[MATH_BIGINTEGER_VALUE
], $m_length - 1);
2016 // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
2017 // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
2018 $temp = $this->_multiply($temp, false, $u, false);
2019 // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
2020 // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
2021 $temp = array_slice($temp[MATH_BIGINTEGER_VALUE
], ($m_length >> 1) +
1);
2022 // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
2023 // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1)
2024 $temp = $this->_multiply($temp, false, $m, false);
2026 // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
2027 // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop
2028 // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
2030 $result = $this->_subtract($n[MATH_BIGINTEGER_VALUE
], false, $temp[MATH_BIGINTEGER_VALUE
], false);
2032 while ($this->_compare($result[MATH_BIGINTEGER_VALUE
], $result[MATH_BIGINTEGER_SIGN
], $m, false) >= 0) {
2033 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE
], $result[MATH_BIGINTEGER_SIGN
], $m, false);
2036 return $result[MATH_BIGINTEGER_VALUE
];
2040 * (Regular) Barrett Modular Reduction
2042 * For numbers with more than four digits Math_BigInteger::_barrett() is faster. The difference between that and this
2043 * is that this function does not fold the denominator into a smaller form.
2045 * @see _slidingWindow()
2051 function _regularBarrett($x, $n)
2053 static $cache = array(
2054 MATH_BIGINTEGER_VARIABLE
=> array(),
2055 MATH_BIGINTEGER_DATA
=> array()
2058 $n_length = count($n);
2060 if (count($x) > 2 * $n_length) {
2061 $lhs = new Math_BigInteger();
2062 $rhs = new Math_BigInteger();
2065 list(, $temp) = $lhs->divide($rhs);
2066 return $temp->value
;
2069 if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE
])) === false ) {
2070 $key = count($cache[MATH_BIGINTEGER_VARIABLE
]);
2071 $cache[MATH_BIGINTEGER_VARIABLE
][] = $n;
2072 $lhs = new Math_BigInteger();
2073 $lhs_value = &$lhs->value
;
2074 $lhs_value = $this->_array_repeat(0, 2 * $n_length);
2076 $rhs = new Math_BigInteger();
2078 list($temp, ) = $lhs->divide($rhs); // m.length
2079 $cache[MATH_BIGINTEGER_DATA
][] = $temp->value
;
2082 // 2 * m.length - (m.length - 1) = m.length + 1
2083 $temp = array_slice($x, $n_length - 1);
2084 // (m.length + 1) + m.length = 2 * m.length + 1
2085 $temp = $this->_multiply($temp, false, $cache[MATH_BIGINTEGER_DATA
][$key], false);
2086 // (2 * m.length + 1) - (m.length - 1) = m.length + 2
2087 $temp = array_slice($temp[MATH_BIGINTEGER_VALUE
], $n_length +
1);
2090 $result = array_slice($x, 0, $n_length +
1);
2092 $temp = $this->_multiplyLower($temp, false, $n, false, $n_length +
1);
2093 // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
2095 if ($this->_compare($result, false, $temp[MATH_BIGINTEGER_VALUE
], $temp[MATH_BIGINTEGER_SIGN
]) < 0) {
2096 $corrector_value = $this->_array_repeat(0, $n_length +
1);
2097 $corrector_value[] = 1;
2098 $result = $this->_add($result, false, $corrector, false);
2099 $result = $result[MATH_BIGINTEGER_VALUE
];
2102 // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
2103 $result = $this->_subtract($result, false, $temp[MATH_BIGINTEGER_VALUE
], $temp[MATH_BIGINTEGER_SIGN
]);
2104 while ($this->_compare($result[MATH_BIGINTEGER_VALUE
], $result[MATH_BIGINTEGER_SIGN
], $n, false) > 0) {
2105 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE
], $result[MATH_BIGINTEGER_SIGN
], $n, false);
2108 return $result[MATH_BIGINTEGER_VALUE
];
2112 * Performs long multiplication up to $stop digits
2114 * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
2116 * @see _regularBarrett()
2117 * @param Array $x_value
2118 * @param Boolean $x_negative
2119 * @param Array $y_value
2120 * @param Boolean $y_negative
2124 function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
2126 $x_length = count($x_value);
2127 $y_length = count($y_value);
2129 if ( !$x_length ||
!$y_length ) { // a 0 is being multiplied
2131 MATH_BIGINTEGER_VALUE
=> array(),
2132 MATH_BIGINTEGER_SIGN
=> false
2136 if ( $x_length < $y_length ) {
2138 $x_value = $y_value;
2141 $x_length = count($x_value);
2142 $y_length = count($y_value);
2145 $product_value = $this->_array_repeat(0, $x_length +
$y_length);
2147 // the following for loop could be removed if the for loop following it
2148 // (the one with nested for loops) initially set $i to 0, but
2149 // doing so would also make the result in one set of unnecessary adds,
2150 // since on the outermost loops first pass, $product->value[$k] is going
2155 for ($j = 0; $j < $x_length; ++
$j) { // ie. $i = 0, $k = $i
2156 $temp = $x_value[$j] * $y_value[0] +
$carry; // $product_value[$k] == 0
2157 $carry = (int) ($temp / 0x4000000);
2158 $product_value[$j] = (int) ($temp - 0x4000000 * $carry);
2162 $product_value[$j] = $carry;
2165 // the above for loop is what the previous comment was talking about. the
2166 // following for loop is the "one with nested for loops"
2168 for ($i = 1; $i < $y_length; ++
$i) {
2171 for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++
$j, ++
$k) {
2172 $temp = $product_value[$k] +
$x_value[$j] * $y_value[$i] +
$carry;
2173 $carry = (int) ($temp / 0x4000000);
2174 $product_value[$k] = (int) ($temp - 0x4000000 * $carry);
2178 $product_value[$k] = $carry;
2183 MATH_BIGINTEGER_VALUE
=> $this->_trim($product_value),
2184 MATH_BIGINTEGER_SIGN
=> $x_negative != $y_negative
2189 * Montgomery Modular Reduction
2191 * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n.
2192 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be
2193 * improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function
2194 * to work correctly.
2196 * @see _prepMontgomery()
2197 * @see _slidingWindow()
2203 function _montgomery($x, $n)
2205 static $cache = array(
2206 MATH_BIGINTEGER_VARIABLE
=> array(),
2207 MATH_BIGINTEGER_DATA
=> array()
2210 if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE
])) === false ) {
2211 $key = count($cache[MATH_BIGINTEGER_VARIABLE
]);
2212 $cache[MATH_BIGINTEGER_VARIABLE
][] = $x;
2213 $cache[MATH_BIGINTEGER_DATA
][] = $this->_modInverse67108864($n);
2218 $result = array(MATH_BIGINTEGER_VALUE
=> $x);
2220 for ($i = 0; $i < $k; ++
$i) {
2221 $temp = $result[MATH_BIGINTEGER_VALUE
][$i] * $cache[MATH_BIGINTEGER_DATA
][$key];
2222 $temp = (int) ($temp - 0x4000000 * ((int) ($temp / 0x4000000)));
2223 $temp = $this->_regularMultiply(array($temp), $n);
2224 $temp = array_merge($this->_array_repeat(0, $i), $temp);
2225 $result = $this->_add($result[MATH_BIGINTEGER_VALUE
], false, $temp, false);
2228 $result[MATH_BIGINTEGER_VALUE
] = array_slice($result[MATH_BIGINTEGER_VALUE
], $k);
2230 if ($this->_compare($result, false, $n, false) >= 0) {
2231 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE
], false, $n, false);
2234 return $result[MATH_BIGINTEGER_VALUE
];
2238 * Montgomery Multiply
2240 * Interleaves the montgomery reduction and long multiplication algorithms together as described in
2241 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
2243 * @see _prepMontgomery()
2244 * @see _montgomery()
2251 function _montgomeryMultiply($x, $y, $m)
2253 $temp = $this->_multiply($x, false, $y, false);
2254 return $this->_montgomery($temp[MATH_BIGINTEGER_VALUE
], $m);
2256 static $cache = array(
2257 MATH_BIGINTEGER_VARIABLE
=> array(),
2258 MATH_BIGINTEGER_DATA
=> array()
2261 if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE
])) === false ) {
2262 $key = count($cache[MATH_BIGINTEGER_VARIABLE
]);
2263 $cache[MATH_BIGINTEGER_VARIABLE
][] = $m;
2264 $cache[MATH_BIGINTEGER_DATA
][] = $this->_modInverse67108864($m);
2267 $n = max(count($x), count($y), count($m));
2268 $x = array_pad($x, $n, 0);
2269 $y = array_pad($y, $n, 0);
2270 $m = array_pad($m, $n, 0);
2271 $a = array(MATH_BIGINTEGER_VALUE
=> $this->_array_repeat(0, $n +
1));
2272 for ($i = 0; $i < $n; ++
$i) {
2273 $temp = $a[MATH_BIGINTEGER_VALUE
][0] +
$x[$i] * $y[0];
2274 $temp = (int) ($temp - 0x4000000 * ((int) ($temp / 0x4000000)));
2275 $temp = $temp * $cache[MATH_BIGINTEGER_DATA
][$key];
2276 $temp = (int) ($temp - 0x4000000 * ((int) ($temp / 0x4000000)));
2277 $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
2278 $a = $this->_add($a[MATH_BIGINTEGER_VALUE
], false, $temp[MATH_BIGINTEGER_VALUE
], false);
2279 $a[MATH_BIGINTEGER_VALUE
] = array_slice($a[MATH_BIGINTEGER_VALUE
], 1);
2281 if ($this->_compare($a[MATH_BIGINTEGER_VALUE
], false, $m, false) >= 0) {
2282 $a = $this->_subtract($a[MATH_BIGINTEGER_VALUE
], false, $m, false);
2284 return $a[MATH_BIGINTEGER_VALUE
];
2288 * Prepare a number for use in Montgomery Modular Reductions
2290 * @see _montgomery()
2291 * @see _slidingWindow()
2297 function _prepMontgomery($x, $n)
2299 $lhs = new Math_BigInteger();
2300 $lhs->value
= array_merge($this->_array_repeat(0, count($n)), $x);
2301 $rhs = new Math_BigInteger();
2304 list(, $temp) = $lhs->divide($rhs);
2305 return $temp->value
;
2309 * Modular Inverse of a number mod 2**26 (eg. 67108864)
2311 * Based off of the bnpInvDigit function implemented and justified in the following URL:
2313 * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
2315 * The following URL provides more info:
2317 * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
2319 * As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For
2320 * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
2321 * int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
2322 * auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that
2323 * the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the
2324 * maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to
2325 * 40 bits, which only 64-bit floating points will support.
2327 * Thanks to Pedro Gimeno Fortea for input!
2329 * @see _montgomery()
2334 function _modInverse67108864($x) // 2**26 == 67108864
2337 $result = $x & 0x3; // x**-1 mod 2**2
2338 $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
2339 $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8
2340 $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
2341 $result = fmod($result * (2 - fmod($x * $result, 0x4000000)), 0x4000000); // x**-1 mod 2**26
2342 return $result & 0x3FFFFFF;
2346 * Calculates modular inverses.
2348 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.
2350 * Here's an example:
2353 * include('Math/BigInteger.php');
2355 * $a = new Math_BigInteger(30);
2356 * $b = new Math_BigInteger(17);
2358 * $c = $a->modInverse($b);
2359 * echo $c->toString(); // outputs 4
2363 * $d = $a->multiply($c);
2364 * list(, $d) = $d->divide($b);
2365 * echo $d; // outputs 1 (as per the definition of modular inverse)
2369 * @param Math_BigInteger $n
2370 * @return mixed false, if no modular inverse exists, Math_BigInteger, otherwise.
2372 * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.
2374 function modInverse($n)
2376 switch ( MATH_BIGINTEGER_MODE
) {
2377 case MATH_BIGINTEGER_MODE_GMP
:
2378 $temp = new Math_BigInteger();
2379 $temp->value
= gmp_invert($this->value
, $n->value
);
2381 return ( $temp->value
=== false ) ?
false : $this->_normalize($temp);
2385 if (!isset($zero)) {
2386 $zero = new Math_BigInteger();
2387 $one = new Math_BigInteger(1);
2390 // $x mod -$n == $x mod $n.
2393 if ($this->compare($zero) < 0) {
2394 $temp = $this->abs();
2395 $temp = $temp->modInverse($n);
2396 return $this->_normalize($n->subtract($temp));
2399 extract($this->extendedGCD($n));
2401 if (!$gcd->equals($one)) {
2405 $x = $x->compare($zero) < 0 ?
$x->add($n) : $x;
2407 return $this->compare($zero) < 0 ?
$this->_normalize($n->subtract($x)) : $this->_normalize($x);
2411 * Calculates the greatest common divisor and Bézout's identity.
2413 * Say you have 693 and 609. The GCD is 21. Bézout's identity states that there exist integers x and y such that
2414 * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which
2415 * combination is returned is dependant upon which mode is in use. See
2416 * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bézout's identity - Wikipedia} for more information.
2418 * Here's an example:
2421 * include('Math/BigInteger.php');
2423 * $a = new Math_BigInteger(693);
2424 * $b = new Math_BigInteger(609);
2426 * extract($a->extendedGCD($b));
2428 * echo $gcd->toString() . "\r\n"; // outputs 21
2429 * echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
2433 * @param Math_BigInteger $n
2434 * @return Math_BigInteger
2436 * @internal Calculates the GCD using the binary xGCD algorithim described in
2437 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}. As the text above 14.61 notes,
2438 * the more traditional algorithim requires "relatively costly multiple-precision divisions".
2440 function extendedGCD($n)
2442 switch ( MATH_BIGINTEGER_MODE
) {
2443 case MATH_BIGINTEGER_MODE_GMP
:
2444 extract(gmp_gcdext($this->value
, $n->value
));
2447 'gcd' => $this->_normalize(new Math_BigInteger($g)),
2448 'x' => $this->_normalize(new Math_BigInteger($s)),
2449 'y' => $this->_normalize(new Math_BigInteger($t))
2451 case MATH_BIGINTEGER_MODE_BCMATH
:
2452 // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
2453 // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is,
2454 // the basic extended euclidean algorithim is what we're using.
2464 while (bccomp($v, '0', 0) != 0) {
2465 $q = bcdiv($u, $v, 0);
2469 $v = bcsub($temp, bcmul($v, $q, 0), 0);
2473 $c = bcsub($temp, bcmul($a, $q, 0), 0);
2477 $d = bcsub($temp, bcmul($b, $q, 0), 0);
2481 'gcd' => $this->_normalize(new Math_BigInteger($u)),
2482 'x' => $this->_normalize(new Math_BigInteger($a)),
2483 'y' => $this->_normalize(new Math_BigInteger($b))
2489 $g = new Math_BigInteger();
2490 $g->value
= array(1);
2492 while ( !(($x->value
[0] & 1)||
($y->value
[0] & 1)) ) {
2501 $a = new Math_BigInteger();
2502 $b = new Math_BigInteger();
2503 $c = new Math_BigInteger();
2504 $d = new Math_BigInteger();
2506 $a->value
= $d->value
= $g->value
= array(1);
2507 $b->value
= $c->value
= array();
2509 while ( !empty($u->value
) ) {
2510 while ( !($u->value
[0] & 1) ) {
2512 if ( (!empty($a->value
) && ($a->value
[0] & 1)) ||
(!empty($b->value
) && ($b->value
[0] & 1)) ) {
2514 $b = $b->subtract($x);
2520 while ( !($v->value
[0] & 1) ) {
2522 if ( (!empty($d->value
) && ($d->value
[0] & 1)) ||
(!empty($c->value
) && ($c->value
[0] & 1)) ) {
2524 $d = $d->subtract($x);
2530 if ($u->compare($v) >= 0) {
2531 $u = $u->subtract($v);
2532 $a = $a->subtract($c);
2533 $b = $b->subtract($d);
2535 $v = $v->subtract($u);
2536 $c = $c->subtract($a);
2537 $d = $d->subtract($b);
2542 'gcd' => $this->_normalize($g->multiply($v)),
2543 'x' => $this->_normalize($c),
2544 'y' => $this->_normalize($d)
2549 * Calculates the greatest common divisor
2551 * Say you have 693 and 609. The GCD is 21.
2553 * Here's an example:
2556 * include('Math/BigInteger.php');
2558 * $a = new Math_BigInteger(693);
2559 * $b = new Math_BigInteger(609);
2561 * $gcd = a->extendedGCD($b);
2563 * echo $gcd->toString() . "\r\n"; // outputs 21
2567 * @param Math_BigInteger $n
2568 * @return Math_BigInteger
2573 extract($this->extendedGCD($n));
2580 * @return Math_BigInteger
2585 $temp = new Math_BigInteger();
2587 switch ( MATH_BIGINTEGER_MODE
) {
2588 case MATH_BIGINTEGER_MODE_GMP
:
2589 $temp->value
= gmp_abs($this->value
);
2591 case MATH_BIGINTEGER_MODE_BCMATH
:
2592 $temp->value
= (bccomp($this->value
, '0', 0) < 0) ?
substr($this->value
, 1) : $this->value
;
2595 $temp->value
= $this->value
;
2602 * Compares two numbers.
2604 * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is
2605 * demonstrated thusly:
2607 * $x > $y: $x->compare($y) > 0
2608 * $x < $y: $x->compare($y) < 0
2609 * $x == $y: $x->compare($y) == 0
2611 * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).
2613 * @param Math_BigInteger $x
2614 * @return Integer < 0 if $this is less than $x; > 0 if $this is greater than $x, and 0 if they are equal.
2617 * @internal Could return $this->subtract($x), but that's not as fast as what we do do.
2619 function compare($y)
2621 switch ( MATH_BIGINTEGER_MODE
) {
2622 case MATH_BIGINTEGER_MODE_GMP
:
2623 return gmp_cmp($this->value
, $y->value
);
2624 case MATH_BIGINTEGER_MODE_BCMATH
:
2625 return bccomp($this->value
, $y->value
, 0);
2628 return $this->_compare($this->value
, $this->is_negative
, $y->value
, $y->is_negative
);
2632 * Compares two numbers.
2634 * @param Array $x_value
2635 * @param Boolean $x_negative
2636 * @param Array $y_value
2637 * @param Boolean $y_negative
2642 function _compare($x_value, $x_negative, $y_value, $y_negative)
2644 if ( $x_negative != $y_negative ) {
2645 return ( !$x_negative && $y_negative ) ?
1 : -1;
2648 $result = $x_negative ?
-1 : 1;
2650 if ( count($x_value) != count($y_value) ) {
2651 return ( count($x_value) > count($y_value) ) ?
$result : -$result;
2653 $size = max(count($x_value), count($y_value));
2655 $x_value = array_pad($x_value, $size, 0);
2656 $y_value = array_pad($y_value, $size, 0);
2658 for ($i = count($x_value) - 1; $i >= 0; --$i) {
2659 if ($x_value[$i] != $y_value[$i]) {
2660 return ( $x_value[$i] > $y_value[$i] ) ?
$result : -$result;
2668 * Tests the equality of two numbers.
2670 * If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare()
2672 * @param Math_BigInteger $x
2679 switch ( MATH_BIGINTEGER_MODE
) {
2680 case MATH_BIGINTEGER_MODE_GMP
:
2681 return gmp_cmp($this->value
, $x->value
) == 0;
2683 return $this->value
=== $x->value
&& $this->is_negative
== $x->is_negative
;
2690 * Some bitwise operations give different results depending on the precision being used. Examples include left
2691 * shift, not, and rotates.
2693 * @param Math_BigInteger $x
2695 * @return Math_BigInteger
2697 function setPrecision($bits)
2699 $this->precision
= $bits;
2700 if ( MATH_BIGINTEGER_MODE
!= MATH_BIGINTEGER_MODE_BCMATH
) {
2701 $this->bitmask
= new Math_BigInteger(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
2703 $this->bitmask
= new Math_BigInteger(bcpow('2', $bits, 0));
2706 $temp = $this->_normalize($this);
2707 $this->value
= $temp->value
;
2713 * @param Math_BigInteger $x
2715 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2716 * @return Math_BigInteger
2718 function bitwise_and($x)
2720 switch ( MATH_BIGINTEGER_MODE
) {
2721 case MATH_BIGINTEGER_MODE_GMP
:
2722 $temp = new Math_BigInteger();
2723 $temp->value
= gmp_and($this->value
, $x->value
);
2725 return $this->_normalize($temp);
2726 case MATH_BIGINTEGER_MODE_BCMATH
:
2727 $left = $this->toBytes();
2728 $right = $x->toBytes();
2730 $length = max(strlen($left), strlen($right));
2732 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT
);
2733 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT
);
2735 return $this->_normalize(new Math_BigInteger($left & $right, 256));
2738 $result = $this->copy();
2740 $length = min(count($x->value
), count($this->value
));
2742 $result->value
= array_slice($result->value
, 0, $length);
2744 for ($i = 0; $i < $length; ++
$i) {
2745 $result->value
[$i] = $result->value
[$i] & $x->value
[$i];
2748 return $this->_normalize($result);
2754 * @param Math_BigInteger $x
2756 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2757 * @return Math_BigInteger
2759 function bitwise_or($x)
2761 switch ( MATH_BIGINTEGER_MODE
) {
2762 case MATH_BIGINTEGER_MODE_GMP
:
2763 $temp = new Math_BigInteger();
2764 $temp->value
= gmp_or($this->value
, $x->value
);
2766 return $this->_normalize($temp);
2767 case MATH_BIGINTEGER_MODE_BCMATH
:
2768 $left = $this->toBytes();
2769 $right = $x->toBytes();
2771 $length = max(strlen($left), strlen($right));
2773 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT
);
2774 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT
);
2776 return $this->_normalize(new Math_BigInteger($left |
$right, 256));
2779 $length = max(count($this->value
), count($x->value
));
2780 $result = $this->copy();
2781 $result->value
= array_pad($result->value
, 0, $length);
2782 $x->value
= array_pad($x->value
, 0, $length);
2784 for ($i = 0; $i < $length; ++
$i) {
2785 $result->value
[$i] = $this->value
[$i] |
$x->value
[$i];
2788 return $this->_normalize($result);
2792 * Logical Exclusive-Or
2794 * @param Math_BigInteger $x
2796 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2797 * @return Math_BigInteger
2799 function bitwise_xor($x)
2801 switch ( MATH_BIGINTEGER_MODE
) {
2802 case MATH_BIGINTEGER_MODE_GMP
:
2803 $temp = new Math_BigInteger();
2804 $temp->value
= gmp_xor($this->value
, $x->value
);
2806 return $this->_normalize($temp);
2807 case MATH_BIGINTEGER_MODE_BCMATH
:
2808 $left = $this->toBytes();
2809 $right = $x->toBytes();
2811 $length = max(strlen($left), strlen($right));
2813 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT
);
2814 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT
);
2816 return $this->_normalize(new Math_BigInteger($left ^
$right, 256));
2819 $length = max(count($this->value
), count($x->value
));
2820 $result = $this->copy();
2821 $result->value
= array_pad($result->value
, 0, $length);
2822 $x->value
= array_pad($x->value
, 0, $length);
2824 for ($i = 0; $i < $length; ++
$i) {
2825 $result->value
[$i] = $this->value
[$i] ^
$x->value
[$i];
2828 return $this->_normalize($result);
2835 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2836 * @return Math_BigInteger
2838 function bitwise_not()
2840 // calculuate "not" without regard to $this->precision
2841 // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0)
2842 $temp = $this->toBytes();
2843 $pre_msb = decbin(ord($temp[0]));
2845 $msb = decbin(ord($temp[0]));
2846 if (strlen($msb) == 8) {
2847 $msb = substr($msb, strpos($msb, '0'));
2849 $temp[0] = chr(bindec($msb));
2851 // see if we need to add extra leading 1's
2852 $current_bits = strlen($pre_msb) +
8 * strlen($temp) - 8;
2853 $new_bits = $this->precision
- $current_bits;
2854 if ($new_bits <= 0) {
2855 return $this->_normalize(new Math_BigInteger($temp, 256));
2858 // generate as many leading 1's as we need to.
2859 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
2860 $this->_base256_lshift($leading_ones, $current_bits);
2862 $temp = str_pad($temp, ceil($this->bits
/ 8), chr(0), STR_PAD_LEFT
);
2864 return $this->_normalize(new Math_BigInteger($leading_ones |
$temp, 256));
2868 * Logical Right Shift
2870 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
2872 * @param Integer $shift
2873 * @return Math_BigInteger
2875 * @internal The only version that yields any speed increases is the internal version.
2877 function bitwise_rightShift($shift)
2879 $temp = new Math_BigInteger();
2881 switch ( MATH_BIGINTEGER_MODE
) {
2882 case MATH_BIGINTEGER_MODE_GMP
:
2886 $two = gmp_init('2');
2889 $temp->value
= gmp_div_q($this->value
, gmp_pow($two, $shift));
2892 case MATH_BIGINTEGER_MODE_BCMATH
:
2893 $temp->value
= bcdiv($this->value
, bcpow('2', $shift, 0), 0);
2896 default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
2897 // and I don't want to do that...
2898 $temp->value
= $this->value
;
2899 $temp->_rshift($shift);
2902 return $this->_normalize($temp);
2906 * Logical Left Shift
2908 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
2910 * @param Integer $shift
2911 * @return Math_BigInteger
2913 * @internal The only version that yields any speed increases is the internal version.
2915 function bitwise_leftShift($shift)
2917 $temp = new Math_BigInteger();
2919 switch ( MATH_BIGINTEGER_MODE
) {
2920 case MATH_BIGINTEGER_MODE_GMP
:
2924 $two = gmp_init('2');
2927 $temp->value
= gmp_mul($this->value
, gmp_pow($two, $shift));
2930 case MATH_BIGINTEGER_MODE_BCMATH
:
2931 $temp->value
= bcmul($this->value
, bcpow('2', $shift, 0), 0);
2934 default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
2935 // and I don't want to do that...
2936 $temp->value
= $this->value
;
2937 $temp->_lshift($shift);
2940 return $this->_normalize($temp);
2944 * Logical Left Rotate
2946 * Instead of the top x bits being dropped they're appended to the shifted bit string.
2948 * @param Integer $shift
2949 * @return Math_BigInteger
2952 function bitwise_leftRotate($shift)
2954 $bits = $this->toBytes();
2956 if ($this->precision
> 0) {
2957 $precision = $this->precision
;
2958 if ( MATH_BIGINTEGER_MODE
== MATH_BIGINTEGER_MODE_BCMATH
) {
2959 $mask = $this->bitmask
->subtract(new Math_BigInteger(1));
2960 $mask = $mask->toBytes();
2962 $mask = $this->bitmask
->toBytes();
2965 $temp = ord($bits[0]);
2966 for ($i = 0; $temp >> $i; ++
$i);
2967 $precision = 8 * strlen($bits) - 8 +
$i;
2968 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
2972 $shift+
= $precision;
2974 $shift%
= $precision;
2977 return $this->copy();
2980 $left = $this->bitwise_leftShift($shift);
2981 $left = $left->bitwise_and(new Math_BigInteger($mask, 256));
2982 $right = $this->bitwise_rightShift($precision - $shift);
2983 $result = MATH_BIGINTEGER_MODE
!= MATH_BIGINTEGER_MODE_BCMATH ?
$left->bitwise_or($right) : $left->add($right);
2984 return $this->_normalize($result);
2988 * Logical Right Rotate
2990 * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
2992 * @param Integer $shift
2993 * @return Math_BigInteger
2996 function bitwise_rightRotate($shift)
2998 return $this->bitwise_leftRotate(-$shift);
3002 * Set random number generator function
3004 * $generator should be the name of a random generating function whose first parameter is the minimum
3005 * value and whose second parameter is the maximum value. If this function needs to be seeded, it should
3006 * be seeded prior to calling Math_BigInteger::random() or Math_BigInteger::randomPrime()
3008 * If the random generating function is not explicitly set, it'll be assumed to be mt_rand().
3011 * @see randomPrime()
3012 * @param optional String $generator
3015 function setRandomGenerator($generator)
3017 $this->generator
= $generator;
3021 * Generate a random number
3023 * @param optional Integer $min
3024 * @param optional Integer $max
3025 * @return Math_BigInteger
3028 function random($min = false, $max = false)
3030 if ($min === false) {
3031 $min = new Math_BigInteger(0);
3034 if ($max === false) {
3035 $max = new Math_BigInteger(0x7FFFFFFF);
3038 $compare = $max->compare($min);
3041 return $this->_normalize($min);
3042 } else if ($compare < 0) {
3043 // if $min is bigger then $max, swap $min and $max
3049 $generator = $this->generator
;
3051 $max = $max->subtract($min);
3052 $max = ltrim($max->toBytes(), chr(0));
3053 $size = strlen($max) - 1;
3057 for ($i = 0; $i < $bytes; ++
$i) {
3058 $random.= chr($generator(0, 255));
3061 $blocks = $size >> 1;
3062 for ($i = 0; $i < $blocks; ++
$i) {
3063 // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
3064 $random.= pack('n', $generator(0, 0xFFFF));
3067 $temp = new Math_BigInteger($random, 256);
3068 if ($temp->compare(new Math_BigInteger(substr($max, 1), 256)) > 0) {
3069 $random = chr($generator(0, ord($max[0]) - 1)) . $random;
3071 $random = chr($generator(0, ord($max[0]) )) . $random;
3074 $random = new Math_BigInteger($random, 256);
3076 return $this->_normalize($random->add($min));
3080 * Generate a random prime number.
3082 * If there's not a prime within the given range, false will be returned. If more than $timeout seconds have elapsed,
3083 * give up and return false.
3085 * @param optional Integer $min
3086 * @param optional Integer $max
3087 * @param optional Integer $timeout
3088 * @return Math_BigInteger
3090 * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}.
3092 function randomPrime($min = false, $max = false, $timeout = false)
3094 $compare = $max->compare($min);
3098 } else if ($compare < 0) {
3099 // if $min is bigger then $max, swap $min and $max
3105 // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
3106 if ( MATH_BIGINTEGER_MODE
== MATH_BIGINTEGER_MODE_GMP
&& function_exists('gmp_nextprime') ) {
3107 // we don't rely on Math_BigInteger::random()'s min / max when gmp_nextprime() is being used since this function
3108 // does its own checks on $max / $min when gmp_nextprime() is used. When gmp_nextprime() is not used, however,
3109 // the same $max / $min checks are not performed.
3110 if ($min === false) {
3111 $min = new Math_BigInteger(0);
3114 if ($max === false) {
3115 $max = new Math_BigInteger(0x7FFFFFFF);
3118 $x = $this->random($min, $max);
3120 $x->value
= gmp_nextprime($x->value
);
3122 if ($x->compare($max) <= 0) {
3126 $x->value
= gmp_nextprime($min->value
);
3128 if ($x->compare($max) <= 0) {
3137 $one = new Math_BigInteger(1);
3138 $two = new Math_BigInteger(2);
3143 $x = $this->random($min, $max);
3144 if ($x->equals($two)) {
3149 if ($x->compare($max) > 0) {
3150 // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
3151 if ($min->equals($max)) {
3158 $initial_x = $x->copy();
3161 if ($timeout !== false && time() - $start > $timeout) {
3165 if ($x->isPrime()) {
3171 if ($x->compare($max) > 0) {
3173 if ($x->equals($two)) {
3179 if ($x->equals($initial_x)) {
3186 * Make the current number odd
3188 * If the current number is odd it'll be unchanged. If it's even, one will be added to it.
3190 * @see randomPrime()
3193 function _make_odd()
3195 switch ( MATH_BIGINTEGER_MODE
) {
3196 case MATH_BIGINTEGER_MODE_GMP
:
3197 gmp_setbit($this->value
, 0);
3199 case MATH_BIGINTEGER_MODE_BCMATH
:
3200 if ($this->value
[strlen($this->value
) - 1] %
2 == 0) {
3201 $this->value
= bcadd($this->value
, '1');
3205 $this->value
[0] |
= 1;
3210 * Checks a numer to see if it's prime
3212 * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the
3213 * $t parameter is distributability. Math_BigInteger::randomPrime() can be distributed accross multiple pageloads
3214 * on a website instead of just one.
3216 * @param optional Integer $t
3219 * @internal Uses the
3220 * {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. See
3221 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}.
3223 function isPrime($t = false)
3225 $length = strlen($this->toBytes());
3228 // see HAC 4.49 "Note (controlling the error probability)"
3229 if ($length >= 163) { $t = 2; } // floor(1300 / 8)
3230 else if ($length >= 106) { $t = 3; } // floor( 850 / 8)
3231 else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8)
3232 else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8)
3233 else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8)
3234 else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8)
3235 else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8)
3236 else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8)
3237 else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
3238 else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
3239 else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
3243 // ie. gmp_testbit($this, 0)
3244 // ie. isEven() or !isOdd()
3245 switch ( MATH_BIGINTEGER_MODE
) {
3246 case MATH_BIGINTEGER_MODE_GMP
:
3247 return gmp_prob_prime($this->value
, $t) != 0;
3248 case MATH_BIGINTEGER_MODE_BCMATH
:
3249 if ($this->value
=== '2') {
3252 if ($this->value
[strlen($this->value
) - 1] %
2 == 0) {
3257 if ($this->value
== array(2)) {
3260 if (~
$this->value
[0] & 1) {
3265 static $primes, $zero, $one, $two;
3267 if (!isset($primes)) {
3269 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
3270 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
3271 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
3272 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
3273 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
3274 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
3275 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
3276 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
3277 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
3278 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
3279 953, 967, 971, 977, 983, 991, 997
3282 if ( MATH_BIGINTEGER_MODE
!= MATH_BIGINTEGER_MODE_INTERNAL
) {
3283 for ($i = 0; $i < count($primes); ++
$i) {
3284 $primes[$i] = new Math_BigInteger($primes[$i]);
3288 $zero = new Math_BigInteger();
3289 $one = new Math_BigInteger(1);
3290 $two = new Math_BigInteger(2);
3293 if ($this->equals($one)) {
3297 // see HAC 4.4.1 "Random search for probable primes"
3298 if ( MATH_BIGINTEGER_MODE
!= MATH_BIGINTEGER_MODE_INTERNAL
) {
3299 foreach ($primes as $prime) {
3300 list(, $r) = $this->divide($prime);
3301 if ($r->equals($zero)) {
3302 return $this->equals($prime);
3306 $value = $this->value
;
3307 foreach ($primes as $prime) {
3308 list(, $r) = $this->_divide_digit($value, $prime);
3310 return count($value) == 1 && $value[0] == $prime;
3316 $n_1 = $n->subtract($one);
3317 $n_2 = $n->subtract($two);
3320 $r_value = $r->value
;
3321 // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
3322 if ( MATH_BIGINTEGER_MODE
== MATH_BIGINTEGER_MODE_BCMATH
) {
3324 // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
3325 while ($r->value
[strlen($r->value
) - 1] %
2 == 0) {
3326 $r->value
= bcdiv($r->value
, '2', 0);
3330 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++
$i) {
3331 $temp = ~
$r_value[$i] & 0xFFFFFF;
3332 for ($j = 1; ($temp >> $j) & 1; ++
$j);
3337 $s = 26 * $i +
$j - 1;
3341 for ($i = 0; $i < $t; ++
$i) {
3342 $a = $this->random($two, $n_2);
3343 $y = $a->modPow($r, $n);
3345 if (!$y->equals($one) && !$y->equals($n_1)) {
3346 for ($j = 1; $j < $s && !$y->equals($n_1); ++
$j) {
3347 $y = $y->modPow($two, $n);
3348 if ($y->equals($one)) {
3353 if (!$y->equals($n_1)) {
3362 * Logical Left Shift
3364 * Shifts BigInteger's by $shift bits.
3366 * @param Integer $shift
3369 function _lshift($shift)
3371 if ( $shift == 0 ) {
3375 $num_digits = (int) ($shift / 26);
3377 $shift = 1 << $shift;
3381 for ($i = 0; $i < count($this->value
); ++
$i) {
3382 $temp = $this->value
[$i] * $shift +
$carry;
3383 $carry = (int) ($temp / 0x4000000);
3384 $this->value
[$i] = (int) ($temp - $carry * 0x4000000);
3388 $this->value
[] = $carry;
3391 while ($num_digits--) {
3392 array_unshift($this->value
, 0);
3397 * Logical Right Shift
3399 * Shifts BigInteger's by $shift bits.
3401 * @param Integer $shift
3404 function _rshift($shift)
3410 $num_digits = (int) ($shift / 26);
3412 $carry_shift = 26 - $shift;
3413 $carry_mask = (1 << $shift) - 1;
3415 if ( $num_digits ) {
3416 $this->value
= array_slice($this->value
, $num_digits);
3421 for ($i = count($this->value
) - 1; $i >= 0; --$i) {
3422 $temp = $this->value
[$i] >> $shift |
$carry;
3423 $carry = ($this->value
[$i] & $carry_mask) << $carry_shift;
3424 $this->value
[$i] = $temp;
3427 $this->value
= $this->_trim($this->value
);
3433 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
3435 * @param Math_BigInteger
3436 * @return Math_BigInteger
3440 function _normalize($result)
3442 $result->precision
= $this->precision
;
3443 $result->bitmask
= $this->bitmask
;
3445 switch ( MATH_BIGINTEGER_MODE
) {
3446 case MATH_BIGINTEGER_MODE_GMP
:
3447 if (!empty($result->bitmask
->value
)) {
3448 $result->value
= gmp_and($result->value
, $result->bitmask
->value
);
3452 case MATH_BIGINTEGER_MODE_BCMATH
:
3453 if (!empty($result->bitmask
->value
)) {
3454 $result->value
= bcmod($result->value
, $result->bitmask
->value
);
3460 $value = &$result->value
;
3462 if ( !count($value) ) {
3466 $value = $this->_trim($value);
3468 if (!empty($result->bitmask
->value
)) {
3469 $length = min(count($value), count($this->bitmask
->value
));
3470 $value = array_slice($value, 0, $length);
3472 for ($i = 0; $i < $length; ++
$i) {
3473 $value[$i] = $value[$i] & $this->bitmask
->value
[$i];
3483 * Removes leading zeros
3485 * @return Math_BigInteger
3488 function _trim($value)
3490 for ($i = count($value) - 1; $i >= 0; --$i) {
3503 * @param $input Array
3504 * @param $multiplier mixed
3508 function _array_repeat($input, $multiplier)
3510 return ($multiplier) ?
array_fill(0, $multiplier, $input) : array();
3514 * Logical Left Shift
3516 * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
3519 * @param $shift Integer
3523 function _base256_lshift(&$x, $shift)
3529 $num_bytes = $shift >> 3; // eg. floor($shift/8)
3530 $shift &= 7; // eg. $shift % 8
3533 for ($i = strlen($x) - 1; $i >= 0; --$i) {
3534 $temp = ord($x[$i]) << $shift |
$carry;
3535 $x[$i] = chr($temp);
3536 $carry = $temp >> 8;
3538 $carry = ($carry != 0) ?
chr($carry) : '';
3539 $x = $carry . $x . str_repeat(chr(0), $num_bytes);
3543 * Logical Right Shift
3545 * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
3548 * @param $shift Integer
3552 function _base256_rshift(&$x, $shift)
3555 $x = ltrim($x, chr(0));
3559 $num_bytes = $shift >> 3; // eg. floor($shift/8)
3560 $shift &= 7; // eg. $shift % 8
3564 $start = $num_bytes > strlen($x) ?
-strlen($x) : -$num_bytes;
3565 $remainder = substr($x, $start);
3566 $x = substr($x, 0, -$num_bytes);
3570 $carry_shift = 8 - $shift;
3571 for ($i = 0; $i < strlen($x); ++
$i) {
3572 $temp = (ord($x[$i]) >> $shift) |
$carry;
3573 $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
3574 $x[$i] = chr($temp);
3576 $x = ltrim($x, chr(0));
3578 $remainder = chr($carry >> $carry_shift) . $remainder;
3580 return ltrim($remainder, chr(0));
3583 // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
3584 // at 32-bits, while java's longs are 64-bits.
3587 * Converts 32-bit integers to bytes.
3593 function _int2bytes($x)
3595 return ltrim(pack('N', $x), chr(0));
3599 * Converts bytes to 32-bit integers
3605 function _bytes2int($x)
3607 $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT
));
3608 return $temp['int'];
3612 * DER-encode an integer
3614 * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL
3618 * @param Integer $length
3621 function _encodeASN1Length($length)
3623 if ($length <= 0x7F) {
3624 return chr($length);
3627 $temp = ltrim(pack('N', $length), chr(0));
3628 return pack('Ca*', 0x80 |
strlen($temp), $temp);