1<?php
2
3/**
4 * Pure-PHP arbitrary precision integer arithmetic library.
5 *
6 * Supports base-2, base-10, base-16, and base-256 numbers.  Uses the GMP or BCMath extensions, if available,
7 * and an internal implementation, otherwise.
8 *
9 * PHP version 5
10 *
11 * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
12 * {@link self::MODE_INTERNAL self::MODE_INTERNAL} mode)
13 *
14 * BigInteger uses base-2**26 to perform operations such as multiplication and division and
15 * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction.  Because the largest possible
16 * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
17 * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
18 * used.  As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
19 * which only supports integers.  Although this fact will slow this library down, the fact that such a high
20 * base is being used should more than compensate.
21 *
22 * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format.  ie.
23 * (new \phpseclib\Math\BigInteger(pow(2, 26)))->value = array(0, 1)
24 *
25 * Useful resources are as follows:
26 *
27 *  - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
28 *  - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
29 *  - Java's BigInteger classes.  See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
30 *
31 * Here's an example of how to use this library:
32 * <code>
33 * <?php
34 *    $a = new \phpseclib\Math\BigInteger(2);
35 *    $b = new \phpseclib\Math\BigInteger(3);
36 *
37 *    $c = $a->add($b);
38 *
39 *    echo $c->toString(); // outputs 5
40 * ?>
41 * </code>
42 *
43 * @category  Math
44 * @package   BigInteger
45 * @author    Jim Wigginton <terrafrost@php.net>
46 * @copyright 2006 Jim Wigginton
47 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
48 */
49
50namespace phpseclib\Math;
51
52use phpseclib\Crypt\Random;
53
54/**
55 * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
56 * numbers.
57 *
58 * @package BigInteger
59 * @author  Jim Wigginton <terrafrost@php.net>
60 * @access  public
61 */
62class BigInteger
63{
64    /**#@+
65     * Reduction constants
66     *
67     * @access private
68     * @see BigInteger::_reduce()
69     */
70    /**
71     * @see BigInteger::_montgomery()
72     * @see BigInteger::_prepMontgomery()
73     */
74    const MONTGOMERY = 0;
75    /**
76     * @see BigInteger::_barrett()
77     */
78    const BARRETT = 1;
79    /**
80     * @see BigInteger::_mod2()
81     */
82    const POWEROF2 = 2;
83    /**
84     * @see BigInteger::_remainder()
85     */
86    const CLASSIC = 3;
87    /**
88     * @see BigInteger::__clone()
89     */
90    const NONE = 4;
91    /**#@-*/
92
93    /**#@+
94     * Array constants
95     *
96     * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and
97     * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
98     *
99     * @access private
100    */
101    /**
102     * $result[self::VALUE] contains the value.
103     */
104    const VALUE = 0;
105    /**
106     * $result[self::SIGN] contains the sign.
107     */
108    const SIGN = 1;
109    /**#@-*/
110
111    /**#@+
112     * @access private
113     * @see BigInteger::_montgomery()
114     * @see BigInteger::_barrett()
115    */
116    /**
117     * Cache constants
118     *
119     * $cache[self::VARIABLE] tells us whether or not the cached data is still valid.
120     */
121    const VARIABLE = 0;
122    /**
123     * $cache[self::DATA] contains the cached data.
124     */
125    const DATA = 1;
126    /**#@-*/
127
128    /**#@+
129     * Mode constants.
130     *
131     * @access private
132     * @see BigInteger::__construct()
133    */
134    /**
135     * To use the pure-PHP implementation
136     */
137    const MODE_INTERNAL = 1;
138    /**
139     * To use the BCMath library
140     *
141     * (if enabled; otherwise, the internal implementation will be used)
142     */
143    const MODE_BCMATH = 2;
144    /**
145     * To use the GMP library
146     *
147     * (if present; otherwise, either the BCMath or the internal implementation will be used)
148     */
149    const MODE_GMP = 3;
150    /**#@-*/
151
152    /**
153     * Karatsuba Cutoff
154     *
155     * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
156     *
157     * @access private
158     */
159    const KARATSUBA_CUTOFF = 25;
160
161    /**#@+
162     * Static properties used by the pure-PHP implementation.
163     *
164     * @see __construct()
165     */
166    protected static $base;
167    protected static $baseFull;
168    protected static $maxDigit;
169    protected static $msb;
170
171    /**
172     * $max10 in greatest $max10Len satisfying
173     * $max10 = 10**$max10Len <= 2**$base.
174     */
175    protected static $max10;
176
177    /**
178     * $max10Len in greatest $max10Len satisfying
179     * $max10 = 10**$max10Len <= 2**$base.
180     */
181    protected static $max10Len;
182    protected static $maxDigit2;
183    /**#@-*/
184
185    /**
186     * Holds the BigInteger's value.
187     *
188     * @var array
189     * @access private
190     */
191    var $value;
192
193    /**
194     * Holds the BigInteger's magnitude.
195     *
196     * @var bool
197     * @access private
198     */
199    var $is_negative = false;
200
201    /**
202     * Precision
203     *
204     * @see self::setPrecision()
205     * @access private
206     */
207    var $precision = -1;
208
209    /**
210     * Precision Bitmask
211     *
212     * @see self::setPrecision()
213     * @access private
214     */
215    var $bitmask = false;
216
217    /**
218     * Mode independent value used for serialization.
219     *
220     * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
221     * a variable that'll be serializable regardless of whether or not extensions are being used.  Unlike $this->value,
222     * however, $this->hex is only calculated when $this->__sleep() is called.
223     *
224     * @see self::__sleep()
225     * @see self::__wakeup()
226     * @var string
227     * @access private
228     */
229    var $hex;
230
231    /**
232     * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
233     *
234     * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
235     * two's compliment.  The sole exception to this is -10, which is treated the same as 10 is.
236     *
237     * Here's an example:
238     * <code>
239     * <?php
240     *    $a = new \phpseclib\Math\BigInteger('0x32', 16); // 50 in base-16
241     *
242     *    echo $a->toString(); // outputs 50
243     * ?>
244     * </code>
245     *
246     * @param int|string|resource $x base-10 number or base-$base number if $base set.
247     * @param int $base
248     * @return \phpseclib\Math\BigInteger
249     * @access public
250     */
251    function __construct($x = 0, $base = 10)
252    {
253        if (!defined('MATH_BIGINTEGER_MODE')) {
254            switch (true) {
255                case extension_loaded('gmp'):
256                    define('MATH_BIGINTEGER_MODE', self::MODE_GMP);
257                    break;
258                case extension_loaded('bcmath'):
259                    define('MATH_BIGINTEGER_MODE', self::MODE_BCMATH);
260                    break;
261                default:
262                    define('MATH_BIGINTEGER_MODE', self::MODE_INTERNAL);
263            }
264        }
265
266        if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
267            // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
268            $versions = array();
269
270            // avoid generating errors (even with suppression) when phpinfo() is disabled (common in production systems)
271            if (strpos(ini_get('disable_functions'), 'phpinfo') === false) {
272                ob_start();
273                @phpinfo();
274                $content = ob_get_contents();
275                ob_end_clean();
276
277                preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
278
279                if (!empty($matches[1])) {
280                    for ($i = 0; $i < count($matches[1]); $i++) {
281                        $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
282
283                        // Remove letter part in OpenSSL version
284                        if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
285                            $versions[$matches[1][$i]] = $fullVersion;
286                        } else {
287                            $versions[$matches[1][$i]] = $m[0];
288                        }
289                    }
290                }
291            }
292
293            // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
294            switch (true) {
295                case !isset($versions['Header']):
296                case !isset($versions['Library']):
297                case $versions['Header'] == $versions['Library']:
298                case version_compare($versions['Header'], '1.0.0') >= 0 && version_compare($versions['Library'], '1.0.0') >= 0:
299                    define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
300                    break;
301                default:
302                    define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
303            }
304        }
305
306        if (!defined('PHP_INT_SIZE')) {
307            define('PHP_INT_SIZE', 4);
308        }
309
310        if (empty(self::$base) && MATH_BIGINTEGER_MODE == self::MODE_INTERNAL) {
311            switch (PHP_INT_SIZE) {
312                case 8: // use 64-bit integers if int size is 8 bytes
313                    self::$base      = 31;
314                    self::$baseFull  = 0x80000000;
315                    self::$maxDigit  = 0x7FFFFFFF;
316                    self::$msb       = 0x40000000;
317                    self::$max10     = 1000000000;
318                    self::$max10Len  = 9;
319                    self::$maxDigit2 = pow(2, 62);
320                    break;
321                //case 4: // use 64-bit floats if int size is 4 bytes
322                default:
323                    self::$base      = 26;
324                    self::$baseFull  = 0x4000000;
325                    self::$maxDigit  = 0x3FFFFFF;
326                    self::$msb       = 0x2000000;
327                    self::$max10     = 10000000;
328                    self::$max10Len  = 7;
329                    self::$maxDigit2 = pow(2, 52); // pow() prevents truncation
330            }
331        }
332
333        switch (MATH_BIGINTEGER_MODE) {
334            case self::MODE_GMP:
335                switch (true) {
336                    case is_resource($x) && get_resource_type($x) == 'GMP integer':
337                    // PHP 5.6 switched GMP from using resources to objects
338                    case $x instanceof \GMP:
339                        $this->value = $x;
340                        return;
341                }
342                $this->value = gmp_init(0);
343                break;
344            case self::MODE_BCMATH:
345                $this->value = '0';
346                break;
347            default:
348                $this->value = array();
349        }
350
351        // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
352        // '0' is the only value like this per http://php.net/empty
353        if (empty($x) && (abs($base) != 256 || $x !== '0')) {
354            return;
355        }
356
357        switch ($base) {
358            case -256:
359                if (ord($x[0]) & 0x80) {
360                    $x = ~$x;
361                    $this->is_negative = true;
362                }
363            case 256:
364                switch (MATH_BIGINTEGER_MODE) {
365                    case self::MODE_GMP:
366                        $this->value = function_exists('gmp_import') ?
367                            gmp_import($x) :
368                            gmp_init('0x' . bin2hex($x));
369                        if ($this->is_negative) {
370                            $this->value = gmp_neg($this->value);
371                        }
372                        break;
373                    case self::MODE_BCMATH:
374                        // round $len to the nearest 4 (thanks, DavidMJ!)
375                        $len = (strlen($x) + 3) & 0xFFFFFFFC;
376
377                        $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
378
379                        for ($i = 0; $i < $len; $i+= 4) {
380                            $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
381                            $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
382                        }
383
384                        if ($this->is_negative) {
385                            $this->value = '-' . $this->value;
386                        }
387
388                        break;
389                    // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
390                    default:
391                        while (strlen($x)) {
392                            $this->value[] = $this->_bytes2int($this->_base256_rshift($x, self::$base));
393                        }
394                }
395
396                if ($this->is_negative) {
397                    if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
398                        $this->is_negative = false;
399                    }
400                    $temp = $this->add(new static('-1'));
401                    $this->value = $temp->value;
402                }
403                break;
404            case 16:
405            case -16:
406                if ($base > 0 && $x[0] == '-') {
407                    $this->is_negative = true;
408                    $x = substr($x, 1);
409                }
410
411                $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
412
413                $is_negative = false;
414                if ($base < 0 && hexdec($x[0]) >= 8) {
415                    $this->is_negative = $is_negative = true;
416                    $x = bin2hex(~pack('H*', $x));
417                }
418
419                switch (MATH_BIGINTEGER_MODE) {
420                    case self::MODE_GMP:
421                        $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
422                        $this->value = gmp_init($temp);
423                        $this->is_negative = false;
424                        break;
425                    case self::MODE_BCMATH:
426                        $x = (strlen($x) & 1) ? '0' . $x : $x;
427                        $temp = new static(pack('H*', $x), 256);
428                        $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
429                        $this->is_negative = false;
430                        break;
431                    default:
432                        $x = (strlen($x) & 1) ? '0' . $x : $x;
433                        $temp = new static(pack('H*', $x), 256);
434                        $this->value = $temp->value;
435                }
436
437                if ($is_negative) {
438                    $temp = $this->add(new static('-1'));
439                    $this->value = $temp->value;
440                }
441                break;
442            case 10:
443            case -10:
444                // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
445                // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
446                // [^-0-9].*: find any non-numeric characters and then any characters that follow that
447                $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
448                if (!strlen($x) || $x == '-') {
449                    $x = '0';
450                }
451
452                switch (MATH_BIGINTEGER_MODE) {
453                    case self::MODE_GMP:
454                        $this->value = gmp_init($x);
455                        break;
456                    case self::MODE_BCMATH:
457                        // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
458                        // results then doing it on '-1' does (modInverse does $x[0])
459                        $this->value = $x === '-' ? '0' : (string) $x;
460                        break;
461                    default:
462                        $temp = new static();
463
464                        $multiplier = new static();
465                        $multiplier->value = array(self::$max10);
466
467                        if ($x[0] == '-') {
468                            $this->is_negative = true;
469                            $x = substr($x, 1);
470                        }
471
472                        $x = str_pad($x, strlen($x) + ((self::$max10Len - 1) * strlen($x)) % self::$max10Len, 0, STR_PAD_LEFT);
473                        while (strlen($x)) {
474                            $temp = $temp->multiply($multiplier);
475                            $temp = $temp->add(new static($this->_int2bytes(substr($x, 0, self::$max10Len)), 256));
476                            $x = substr($x, self::$max10Len);
477                        }
478
479                        $this->value = $temp->value;
480                }
481                break;
482            case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
483            case -2:
484                if ($base > 0 && $x[0] == '-') {
485                    $this->is_negative = true;
486                    $x = substr($x, 1);
487                }
488
489                $x = preg_replace('#^([01]*).*#', '$1', $x);
490                $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
491
492                $str = '0x';
493                while (strlen($x)) {
494                    $part = substr($x, 0, 4);
495                    $str.= dechex(bindec($part));
496                    $x = substr($x, 4);
497                }
498
499                if ($this->is_negative) {
500                    $str = '-' . $str;
501                }
502
503                $temp = new static($str, 8 * $base); // ie. either -16 or +16
504                $this->value = $temp->value;
505                $this->is_negative = $temp->is_negative;
506
507                break;
508            default:
509                // base not supported, so we'll let $this == 0
510        }
511    }
512
513    /**
514     * Converts a BigInteger to a byte string (eg. base-256).
515     *
516     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
517     * saved as two's compliment.
518     *
519     * Here's an example:
520     * <code>
521     * <?php
522     *    $a = new \phpseclib\Math\BigInteger('65');
523     *
524     *    echo $a->toBytes(); // outputs chr(65)
525     * ?>
526     * </code>
527     *
528     * @param bool $twos_compliment
529     * @return string
530     * @access public
531     * @internal Converts a base-2**26 number to base-2**8
532     */
533    function toBytes($twos_compliment = false)
534    {
535        if ($twos_compliment) {
536            $comparison = $this->compare(new static());
537            if ($comparison == 0) {
538                return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
539            }
540
541            $temp = $comparison < 0 ? $this->add(new static(1)) : $this->copy();
542            $bytes = $temp->toBytes();
543
544            if (!strlen($bytes)) { // eg. if the number we're trying to convert is -1
545                $bytes = chr(0);
546            }
547
548            if ($this->precision <= 0 && (ord($bytes[0]) & 0x80)) {
549                $bytes = chr(0) . $bytes;
550            }
551
552            return $comparison < 0 ? ~$bytes : $bytes;
553        }
554
555        switch (MATH_BIGINTEGER_MODE) {
556            case self::MODE_GMP:
557                if (gmp_cmp($this->value, gmp_init(0)) == 0) {
558                    return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
559                }
560
561                if (function_exists('gmp_export')) {
562                    $temp = gmp_export($this->value);
563                } else {
564                    $temp = gmp_strval(gmp_abs($this->value), 16);
565                    $temp = (strlen($temp) & 1) ? '0' . $temp : $temp;
566                    $temp = pack('H*', $temp);
567                }
568
569                return $this->precision > 0 ?
570                    substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
571                    ltrim($temp, chr(0));
572            case self::MODE_BCMATH:
573                if ($this->value === '0') {
574                    return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
575                }
576
577                $value = '';
578                $current = $this->value;
579
580                if ($current[0] == '-') {
581                    $current = substr($current, 1);
582                }
583
584                while (bccomp($current, '0', 0) > 0) {
585                    $temp = bcmod($current, '16777216');
586                    $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
587                    $current = bcdiv($current, '16777216', 0);
588                }
589
590                return $this->precision > 0 ?
591                    substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
592                    ltrim($value, chr(0));
593        }
594
595        if (!count($this->value)) {
596            return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
597        }
598        $result = $this->_int2bytes($this->value[count($this->value) - 1]);
599
600        $temp = $this->copy();
601
602        for ($i = count($temp->value) - 2; $i >= 0; --$i) {
603            $temp->_base256_lshift($result, self::$base);
604            $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
605        }
606
607        return $this->precision > 0 ?
608            str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
609            $result;
610    }
611
612    /**
613     * Converts a BigInteger to a hex string (eg. base-16)).
614     *
615     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
616     * saved as two's compliment.
617     *
618     * Here's an example:
619     * <code>
620     * <?php
621     *    $a = new \phpseclib\Math\BigInteger('65');
622     *
623     *    echo $a->toHex(); // outputs '41'
624     * ?>
625     * </code>
626     *
627     * @param bool $twos_compliment
628     * @return string
629     * @access public
630     * @internal Converts a base-2**26 number to base-2**8
631     */
632    function toHex($twos_compliment = false)
633    {
634        return bin2hex($this->toBytes($twos_compliment));
635    }
636
637    /**
638     * Converts a BigInteger to a bit string (eg. base-2).
639     *
640     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
641     * saved as two's compliment.
642     *
643     * Here's an example:
644     * <code>
645     * <?php
646     *    $a = new \phpseclib\Math\BigInteger('65');
647     *
648     *    echo $a->toBits(); // outputs '1000001'
649     * ?>
650     * </code>
651     *
652     * @param bool $twos_compliment
653     * @return string
654     * @access public
655     * @internal Converts a base-2**26 number to base-2**2
656     */
657    function toBits($twos_compliment = false)
658    {
659        $hex = $this->toHex($twos_compliment);
660        $bits = '';
661        for ($i = strlen($hex) - 6, $start = strlen($hex) % 6; $i >= $start; $i-=6) {
662            $bits = str_pad(decbin(hexdec(substr($hex, $i, 6))), 24, '0', STR_PAD_LEFT) . $bits;
663        }
664        if ($start) { // hexdec('') == 0
665            $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8 * $start, '0', STR_PAD_LEFT) . $bits;
666        }
667        $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
668
669        if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) {
670            return '0' . $result;
671        }
672
673        return $result;
674    }
675
676    /**
677     * Converts a BigInteger to a base-10 number.
678     *
679     * Here's an example:
680     * <code>
681     * <?php
682     *    $a = new \phpseclib\Math\BigInteger('50');
683     *
684     *    echo $a->toString(); // outputs 50
685     * ?>
686     * </code>
687     *
688     * @return string
689     * @access public
690     * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
691     */
692    function toString()
693    {
694        switch (MATH_BIGINTEGER_MODE) {
695            case self::MODE_GMP:
696                return gmp_strval($this->value);
697            case self::MODE_BCMATH:
698                if ($this->value === '0') {
699                    return '0';
700                }
701
702                return ltrim($this->value, '0');
703        }
704
705        if (!count($this->value)) {
706            return '0';
707        }
708
709        $temp = $this->copy();
710        $temp->bitmask = false;
711        $temp->is_negative = false;
712
713        $divisor = new static();
714        $divisor->value = array(self::$max10);
715        $result = '';
716        while (count($temp->value)) {
717            list($temp, $mod) = $temp->divide($divisor);
718            $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', self::$max10Len, '0', STR_PAD_LEFT) . $result;
719        }
720        $result = ltrim($result, '0');
721        if (empty($result)) {
722            $result = '0';
723        }
724
725        if ($this->is_negative) {
726            $result = '-' . $result;
727        }
728
729        return $result;
730    }
731
732    /**
733     * Copy an object
734     *
735     * PHP5 passes objects by reference while PHP4 passes by value.  As such, we need a function to guarantee
736     * that all objects are passed by value, when appropriate.  More information can be found here:
737     *
738     * {@link http://php.net/language.oop5.basic#51624}
739     *
740     * @access public
741     * @see self::__clone()
742     * @return \phpseclib\Math\BigInteger
743     */
744    function copy()
745    {
746        $temp = new static();
747        $temp->value = $this->value;
748        $temp->is_negative = $this->is_negative;
749        $temp->precision = $this->precision;
750        $temp->bitmask = $this->bitmask;
751        return $temp;
752    }
753
754    /**
755     *  __toString() magic method
756     *
757     * Will be called, automatically, if you're supporting just PHP5.  If you're supporting PHP4, you'll need to call
758     * toString().
759     *
760     * @access public
761     * @internal Implemented per a suggestion by Techie-Michael - thanks!
762     */
763    function __toString()
764    {
765        return $this->toString();
766    }
767
768    /**
769     * __clone() magic method
770     *
771     * Although you can call BigInteger::__toString() directly in PHP5, you cannot call BigInteger::__clone() directly
772     * 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
773     * only syntax of $y = clone $x.  As such, if you're trying to write an application that works on both PHP4 and
774     * PHP5, call BigInteger::copy(), instead.
775     *
776     * @access public
777     * @see self::copy()
778     * @return \phpseclib\Math\BigInteger
779     */
780    function __clone()
781    {
782        return $this->copy();
783    }
784
785    /**
786     *  __sleep() magic method
787     *
788     * Will be called, automatically, when serialize() is called on a BigInteger object.
789     *
790     * @see self::__wakeup()
791     * @access public
792     */
793    function __sleep()
794    {
795        $this->hex = $this->toHex(true);
796        $vars = array('hex');
797        if ($this->precision > 0) {
798            $vars[] = 'precision';
799        }
800        return $vars;
801    }
802
803    /**
804     *  __wakeup() magic method
805     *
806     * Will be called, automatically, when unserialize() is called on a BigInteger object.
807     *
808     * @see self::__sleep()
809     * @access public
810     */
811    function __wakeup()
812    {
813        $temp = new static($this->hex, -16);
814        $this->value = $temp->value;
815        $this->is_negative = $temp->is_negative;
816        if ($this->precision > 0) {
817            // recalculate $this->bitmask
818            $this->setPrecision($this->precision);
819        }
820    }
821
822    /**
823     *  __debugInfo() magic method
824     *
825     * Will be called, automatically, when print_r() or var_dump() are called
826     *
827     * @access public
828     */
829    function __debugInfo()
830    {
831        $opts = array();
832        switch (MATH_BIGINTEGER_MODE) {
833            case self::MODE_GMP:
834                $engine = 'gmp';
835                break;
836            case self::MODE_BCMATH:
837                $engine = 'bcmath';
838                break;
839            case self::MODE_INTERNAL:
840                $engine = 'internal';
841                $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit';
842        }
843        if (MATH_BIGINTEGER_MODE != self::MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
844            $opts[] = 'OpenSSL';
845        }
846        if (!empty($opts)) {
847            $engine.= ' (' . implode('.', $opts) . ')';
848        }
849        return array(
850            'value' => '0x' . $this->toHex(true),
851            'engine' => $engine
852        );
853    }
854
855    /**
856     * Adds two BigIntegers.
857     *
858     * Here's an example:
859     * <code>
860     * <?php
861     *    $a = new \phpseclib\Math\BigInteger('10');
862     *    $b = new \phpseclib\Math\BigInteger('20');
863     *
864     *    $c = $a->add($b);
865     *
866     *    echo $c->toString(); // outputs 30
867     * ?>
868     * </code>
869     *
870     * @param \phpseclib\Math\BigInteger $y
871     * @return \phpseclib\Math\BigInteger
872     * @access public
873     * @internal Performs base-2**52 addition
874     */
875    function add($y)
876    {
877        switch (MATH_BIGINTEGER_MODE) {
878            case self::MODE_GMP:
879                $temp = new static();
880                $temp->value = gmp_add($this->value, $y->value);
881
882                return $this->_normalize($temp);
883            case self::MODE_BCMATH:
884                $temp = new static();
885                $temp->value = bcadd($this->value, $y->value, 0);
886
887                return $this->_normalize($temp);
888        }
889
890        $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
891
892        $result = new static();
893        $result->value = $temp[self::VALUE];
894        $result->is_negative = $temp[self::SIGN];
895
896        return $this->_normalize($result);
897    }
898
899    /**
900     * Performs addition.
901     *
902     * @param array $x_value
903     * @param bool $x_negative
904     * @param array $y_value
905     * @param bool $y_negative
906     * @return array
907     * @access private
908     */
909    function _add($x_value, $x_negative, $y_value, $y_negative)
910    {
911        $x_size = count($x_value);
912        $y_size = count($y_value);
913
914        if ($x_size == 0) {
915            return array(
916                self::VALUE => $y_value,
917                self::SIGN => $y_negative
918            );
919        } elseif ($y_size == 0) {
920            return array(
921                self::VALUE => $x_value,
922                self::SIGN => $x_negative
923            );
924        }
925
926        // subtract, if appropriate
927        if ($x_negative != $y_negative) {
928            if ($x_value == $y_value) {
929                return array(
930                    self::VALUE => array(),
931                    self::SIGN => false
932                );
933            }
934
935            $temp = $this->_subtract($x_value, false, $y_value, false);
936            $temp[self::SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
937                                          $x_negative : $y_negative;
938
939            return $temp;
940        }
941
942        if ($x_size < $y_size) {
943            $size = $x_size;
944            $value = $y_value;
945        } else {
946            $size = $y_size;
947            $value = $x_value;
948        }
949
950        $value[count($value)] = 0; // just in case the carry adds an extra digit
951
952        $carry = 0;
953        for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
954            $sum = $x_value[$j] * self::$baseFull + $x_value[$i] + $y_value[$j] * self::$baseFull + $y_value[$i] + $carry;
955            $carry = $sum >= self::$maxDigit2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
956            $sum = $carry ? $sum - self::$maxDigit2 : $sum;
957
958            $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
959
960            $value[$i] = (int) ($sum - self::$baseFull * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
961            $value[$j] = $temp;
962        }
963
964        if ($j == $size) { // ie. if $y_size is odd
965            $sum = $x_value[$i] + $y_value[$i] + $carry;
966            $carry = $sum >= self::$baseFull;
967            $value[$i] = $carry ? $sum - self::$baseFull : $sum;
968            ++$i; // ie. let $i = $j since we've just done $value[$i]
969        }
970
971        if ($carry) {
972            for (; $value[$i] == self::$maxDigit; ++$i) {
973                $value[$i] = 0;
974            }
975            ++$value[$i];
976        }
977
978        return array(
979            self::VALUE => $this->_trim($value),
980            self::SIGN => $x_negative
981        );
982    }
983
984    /**
985     * Subtracts two BigIntegers.
986     *
987     * Here's an example:
988     * <code>
989     * <?php
990     *    $a = new \phpseclib\Math\BigInteger('10');
991     *    $b = new \phpseclib\Math\BigInteger('20');
992     *
993     *    $c = $a->subtract($b);
994     *
995     *    echo $c->toString(); // outputs -10
996     * ?>
997     * </code>
998     *
999     * @param \phpseclib\Math\BigInteger $y
1000     * @return \phpseclib\Math\BigInteger
1001     * @access public
1002     * @internal Performs base-2**52 subtraction
1003     */
1004    function subtract($y)
1005    {
1006        switch (MATH_BIGINTEGER_MODE) {
1007            case self::MODE_GMP:
1008                $temp = new static();
1009                $temp->value = gmp_sub($this->value, $y->value);
1010
1011                return $this->_normalize($temp);
1012            case self::MODE_BCMATH:
1013                $temp = new static();
1014                $temp->value = bcsub($this->value, $y->value, 0);
1015
1016                return $this->_normalize($temp);
1017        }
1018
1019        $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
1020
1021        $result = new static();
1022        $result->value = $temp[self::VALUE];
1023        $result->is_negative = $temp[self::SIGN];
1024
1025        return $this->_normalize($result);
1026    }
1027
1028    /**
1029     * Performs subtraction.
1030     *
1031     * @param array $x_value
1032     * @param bool $x_negative
1033     * @param array $y_value
1034     * @param bool $y_negative
1035     * @return array
1036     * @access private
1037     */
1038    function _subtract($x_value, $x_negative, $y_value, $y_negative)
1039    {
1040        $x_size = count($x_value);
1041        $y_size = count($y_value);
1042
1043        if ($x_size == 0) {
1044            return array(
1045                self::VALUE => $y_value,
1046                self::SIGN => !$y_negative
1047            );
1048        } elseif ($y_size == 0) {
1049            return array(
1050                self::VALUE => $x_value,
1051                self::SIGN => $x_negative
1052            );
1053        }
1054
1055        // add, if appropriate (ie. -$x - +$y or +$x - -$y)
1056        if ($x_negative != $y_negative) {
1057            $temp = $this->_add($x_value, false, $y_value, false);
1058            $temp[self::SIGN] = $x_negative;
1059
1060            return $temp;
1061        }
1062
1063        $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
1064
1065        if (!$diff) {
1066            return array(
1067                self::VALUE => array(),
1068                self::SIGN => false
1069            );
1070        }
1071
1072        // switch $x and $y around, if appropriate.
1073        if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
1074            $temp = $x_value;
1075            $x_value = $y_value;
1076            $y_value = $temp;
1077
1078            $x_negative = !$x_negative;
1079
1080            $x_size = count($x_value);
1081            $y_size = count($y_value);
1082        }
1083
1084        // at this point, $x_value should be at least as big as - if not bigger than - $y_value
1085
1086        $carry = 0;
1087        for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
1088            $sum = $x_value[$j] * self::$baseFull + $x_value[$i] - $y_value[$j] * self::$baseFull - $y_value[$i] - $carry;
1089            $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
1090            $sum = $carry ? $sum + self::$maxDigit2 : $sum;
1091
1092            $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
1093
1094            $x_value[$i] = (int) ($sum - self::$baseFull * $temp);
1095            $x_value[$j] = $temp;
1096        }
1097
1098        if ($j == $y_size) { // ie. if $y_size is odd
1099            $sum = $x_value[$i] - $y_value[$i] - $carry;
1100            $carry = $sum < 0;
1101            $x_value[$i] = $carry ? $sum + self::$baseFull : $sum;
1102            ++$i;
1103        }
1104
1105        if ($carry) {
1106            for (; !$x_value[$i]; ++$i) {
1107                $x_value[$i] = self::$maxDigit;
1108            }
1109            --$x_value[$i];
1110        }
1111
1112        return array(
1113            self::VALUE => $this->_trim($x_value),
1114            self::SIGN => $x_negative
1115        );
1116    }
1117
1118    /**
1119     * Multiplies two BigIntegers
1120     *
1121     * Here's an example:
1122     * <code>
1123     * <?php
1124     *    $a = new \phpseclib\Math\BigInteger('10');
1125     *    $b = new \phpseclib\Math\BigInteger('20');
1126     *
1127     *    $c = $a->multiply($b);
1128     *
1129     *    echo $c->toString(); // outputs 200
1130     * ?>
1131     * </code>
1132     *
1133     * @param \phpseclib\Math\BigInteger $x
1134     * @return \phpseclib\Math\BigInteger
1135     * @access public
1136     */
1137    function multiply($x)
1138    {
1139        switch (MATH_BIGINTEGER_MODE) {
1140            case self::MODE_GMP:
1141                $temp = new static();
1142                $temp->value = gmp_mul($this->value, $x->value);
1143
1144                return $this->_normalize($temp);
1145            case self::MODE_BCMATH:
1146                $temp = new static();
1147                $temp->value = bcmul($this->value, $x->value, 0);
1148
1149                return $this->_normalize($temp);
1150        }
1151
1152        $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
1153
1154        $product = new static();
1155        $product->value = $temp[self::VALUE];
1156        $product->is_negative = $temp[self::SIGN];
1157
1158        return $this->_normalize($product);
1159    }
1160
1161    /**
1162     * Performs multiplication.
1163     *
1164     * @param array $x_value
1165     * @param bool $x_negative
1166     * @param array $y_value
1167     * @param bool $y_negative
1168     * @return array
1169     * @access private
1170     */
1171    function _multiply($x_value, $x_negative, $y_value, $y_negative)
1172    {
1173        //if ( $x_value == $y_value ) {
1174        //    return array(
1175        //        self::VALUE => $this->_square($x_value),
1176        //        self::SIGN => $x_sign != $y_value
1177        //    );
1178        //}
1179
1180        $x_length = count($x_value);
1181        $y_length = count($y_value);
1182
1183        if (!$x_length || !$y_length) { // a 0 is being multiplied
1184            return array(
1185                self::VALUE => array(),
1186                self::SIGN => false
1187            );
1188        }
1189
1190        return array(
1191            self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ?
1192                $this->_trim($this->_regularMultiply($x_value, $y_value)) :
1193                $this->_trim($this->_karatsuba($x_value, $y_value)),
1194            self::SIGN => $x_negative != $y_negative
1195        );
1196    }
1197
1198    /**
1199     * Performs long multiplication on two BigIntegers
1200     *
1201     * Modeled after 'multiply' in MutableBigInteger.java.
1202     *
1203     * @param array $x_value
1204     * @param array $y_value
1205     * @return array
1206     * @access private
1207     */
1208    function _regularMultiply($x_value, $y_value)
1209    {
1210        $x_length = count($x_value);
1211        $y_length = count($y_value);
1212
1213        if (!$x_length || !$y_length) { // a 0 is being multiplied
1214            return array();
1215        }
1216
1217        if ($x_length < $y_length) {
1218            $temp = $x_value;
1219            $x_value = $y_value;
1220            $y_value = $temp;
1221
1222            $x_length = count($x_value);
1223            $y_length = count($y_value);
1224        }
1225
1226        $product_value = $this->_array_repeat(0, $x_length + $y_length);
1227
1228        // the following for loop could be removed if the for loop following it
1229        // (the one with nested for loops) initially set $i to 0, but
1230        // doing so would also make the result in one set of unnecessary adds,
1231        // since on the outermost loops first pass, $product->value[$k] is going
1232        // to always be 0
1233
1234        $carry = 0;
1235
1236        for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
1237            $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
1238            $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1239            $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
1240        }
1241
1242        $product_value[$j] = $carry;
1243
1244        // the above for loop is what the previous comment was talking about.  the
1245        // following for loop is the "one with nested for loops"
1246        for ($i = 1; $i < $y_length; ++$i) {
1247            $carry = 0;
1248
1249            for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
1250                $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
1251                $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1252                $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
1253            }
1254
1255            $product_value[$k] = $carry;
1256        }
1257
1258        return $product_value;
1259    }
1260
1261    /**
1262     * Performs Karatsuba multiplication on two BigIntegers
1263     *
1264     * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1265     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
1266     *
1267     * @param array $x_value
1268     * @param array $y_value
1269     * @return array
1270     * @access private
1271     */
1272    function _karatsuba($x_value, $y_value)
1273    {
1274        $m = min(count($x_value) >> 1, count($y_value) >> 1);
1275
1276        if ($m < self::KARATSUBA_CUTOFF) {
1277            return $this->_regularMultiply($x_value, $y_value);
1278        }
1279
1280        $x1 = array_slice($x_value, $m);
1281        $x0 = array_slice($x_value, 0, $m);
1282        $y1 = array_slice($y_value, $m);
1283        $y0 = array_slice($y_value, 0, $m);
1284
1285        $z2 = $this->_karatsuba($x1, $y1);
1286        $z0 = $this->_karatsuba($x0, $y0);
1287
1288        $z1 = $this->_add($x1, false, $x0, false);
1289        $temp = $this->_add($y1, false, $y0, false);
1290        $z1 = $this->_karatsuba($z1[self::VALUE], $temp[self::VALUE]);
1291        $temp = $this->_add($z2, false, $z0, false);
1292        $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);
1293
1294        $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1295        $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
1296
1297        $xy = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1298        $xy = $this->_add($xy[self::VALUE], $xy[self::SIGN], $z0, false);
1299
1300        return $xy[self::VALUE];
1301    }
1302
1303    /**
1304     * Performs squaring
1305     *
1306     * @param array $x
1307     * @return array
1308     * @access private
1309     */
1310    function _square($x = false)
1311    {
1312        return count($x) < 2 * self::KARATSUBA_CUTOFF ?
1313            $this->_trim($this->_baseSquare($x)) :
1314            $this->_trim($this->_karatsubaSquare($x));
1315    }
1316
1317    /**
1318     * Performs traditional squaring on two BigIntegers
1319     *
1320     * Squaring can be done faster than multiplying a number by itself can be.  See
1321     * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
1322     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
1323     *
1324     * @param array $value
1325     * @return array
1326     * @access private
1327     */
1328    function _baseSquare($value)
1329    {
1330        if (empty($value)) {
1331            return array();
1332        }
1333        $square_value = $this->_array_repeat(0, 2 * count($value));
1334
1335        for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
1336            $i2 = $i << 1;
1337
1338            $temp = $square_value[$i2] + $value[$i] * $value[$i];
1339            $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1340            $square_value[$i2] = (int) ($temp - self::$baseFull * $carry);
1341
1342            // note how we start from $i+1 instead of 0 as we do in multiplication.
1343            for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
1344                $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
1345                $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1346                $square_value[$k] = (int) ($temp - self::$baseFull * $carry);
1347            }
1348
1349            // the following line can yield values larger 2**15.  at this point, PHP should switch
1350            // over to floats.
1351            $square_value[$i + $max_index + 1] = $carry;
1352        }
1353
1354        return $square_value;
1355    }
1356
1357    /**
1358     * Performs Karatsuba "squaring" on two BigIntegers
1359     *
1360     * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1361     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
1362     *
1363     * @param array $value
1364     * @return array
1365     * @access private
1366     */
1367    function _karatsubaSquare($value)
1368    {
1369        $m = count($value) >> 1;
1370
1371        if ($m < self::KARATSUBA_CUTOFF) {
1372            return $this->_baseSquare($value);
1373        }
1374
1375        $x1 = array_slice($value, $m);
1376        $x0 = array_slice($value, 0, $m);
1377
1378        $z2 = $this->_karatsubaSquare($x1);
1379        $z0 = $this->_karatsubaSquare($x0);
1380
1381        $z1 = $this->_add($x1, false, $x0, false);
1382        $z1 = $this->_karatsubaSquare($z1[self::VALUE]);
1383        $temp = $this->_add($z2, false, $z0, false);
1384        $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);
1385
1386        $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1387        $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
1388
1389        $xx = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1390        $xx = $this->_add($xx[self::VALUE], $xx[self::SIGN], $z0, false);
1391
1392        return $xx[self::VALUE];
1393    }
1394
1395    /**
1396     * Divides two BigIntegers.
1397     *
1398     * Returns an array whose first element contains the quotient and whose second element contains the
1399     * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
1400     * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
1401     * and the divisor (basically, the "common residue" is the first positive modulo).
1402     *
1403     * Here's an example:
1404     * <code>
1405     * <?php
1406     *    $a = new \phpseclib\Math\BigInteger('10');
1407     *    $b = new \phpseclib\Math\BigInteger('20');
1408     *
1409     *    list($quotient, $remainder) = $a->divide($b);
1410     *
1411     *    echo $quotient->toString(); // outputs 0
1412     *    echo "\r\n";
1413     *    echo $remainder->toString(); // outputs 10
1414     * ?>
1415     * </code>
1416     *
1417     * @param \phpseclib\Math\BigInteger $y
1418     * @return array
1419     * @access public
1420     * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
1421     */
1422    function divide($y)
1423    {
1424        switch (MATH_BIGINTEGER_MODE) {
1425            case self::MODE_GMP:
1426                $quotient = new static();
1427                $remainder = new static();
1428
1429                list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
1430
1431                if (gmp_sign($remainder->value) < 0) {
1432                    $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
1433                }
1434
1435                return array($this->_normalize($quotient), $this->_normalize($remainder));
1436            case self::MODE_BCMATH:
1437                $quotient = new static();
1438                $remainder = new static();
1439
1440                $quotient->value = bcdiv($this->value, $y->value, 0);
1441                $remainder->value = bcmod($this->value, $y->value);
1442
1443                if ($remainder->value[0] == '-') {
1444                    $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
1445                }
1446
1447                return array($this->_normalize($quotient), $this->_normalize($remainder));
1448        }
1449
1450        if (count($y->value) == 1) {
1451            list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
1452            $quotient = new static();
1453            $remainder = new static();
1454            $quotient->value = $q;
1455            $remainder->value = array($r);
1456            $quotient->is_negative = $this->is_negative != $y->is_negative;
1457            return array($this->_normalize($quotient), $this->_normalize($remainder));
1458        }
1459
1460        static $zero;
1461        if (!isset($zero)) {
1462            $zero = new static();
1463        }
1464
1465        $x = $this->copy();
1466        $y = $y->copy();
1467
1468        $x_sign = $x->is_negative;
1469        $y_sign = $y->is_negative;
1470
1471        $x->is_negative = $y->is_negative = false;
1472
1473        $diff = $x->compare($y);
1474
1475        if (!$diff) {
1476            $temp = new static();
1477            $temp->value = array(1);
1478            $temp->is_negative = $x_sign != $y_sign;
1479            return array($this->_normalize($temp), $this->_normalize(new static()));
1480        }
1481
1482        if ($diff < 0) {
1483            // if $x is negative, "add" $y.
1484            if ($x_sign) {
1485                $x = $y->subtract($x);
1486            }
1487            return array($this->_normalize(new static()), $this->_normalize($x));
1488        }
1489
1490        // normalize $x and $y as described in HAC 14.23 / 14.24
1491        $msb = $y->value[count($y->value) - 1];
1492        for ($shift = 0; !($msb & self::$msb); ++$shift) {
1493            $msb <<= 1;
1494        }
1495        $x->_lshift($shift);
1496        $y->_lshift($shift);
1497        $y_value = &$y->value;
1498
1499        $x_max = count($x->value) - 1;
1500        $y_max = count($y->value) - 1;
1501
1502        $quotient = new static();
1503        $quotient_value = &$quotient->value;
1504        $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
1505
1506        static $temp, $lhs, $rhs;
1507        if (!isset($temp)) {
1508            $temp = new static();
1509            $lhs =  new static();
1510            $rhs =  new static();
1511        }
1512        $temp_value = &$temp->value;
1513        $rhs_value =  &$rhs->value;
1514
1515        // $temp = $y << ($x_max - $y_max-1) in base 2**26
1516        $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
1517
1518        while ($x->compare($temp) >= 0) {
1519            // calculate the "common residue"
1520            ++$quotient_value[$x_max - $y_max];
1521            $x = $x->subtract($temp);
1522            $x_max = count($x->value) - 1;
1523        }
1524
1525        for ($i = $x_max; $i >= $y_max + 1; --$i) {
1526            $x_value = &$x->value;
1527            $x_window = array(
1528                isset($x_value[$i]) ? $x_value[$i] : 0,
1529                isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
1530                isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
1531            );
1532            $y_window = array(
1533                $y_value[$y_max],
1534                ($y_max > 0) ? $y_value[$y_max - 1] : 0
1535            );
1536
1537            $q_index = $i - $y_max - 1;
1538            if ($x_window[0] == $y_window[0]) {
1539                $quotient_value[$q_index] = self::$maxDigit;
1540            } else {
1541                $quotient_value[$q_index] = $this->_safe_divide(
1542                    $x_window[0] * self::$baseFull + $x_window[1],
1543                    $y_window[0]
1544                );
1545            }
1546
1547            $temp_value = array($y_window[1], $y_window[0]);
1548
1549            $lhs->value = array($quotient_value[$q_index]);
1550            $lhs = $lhs->multiply($temp);
1551
1552            $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
1553
1554            while ($lhs->compare($rhs) > 0) {
1555                --$quotient_value[$q_index];
1556
1557                $lhs->value = array($quotient_value[$q_index]);
1558                $lhs = $lhs->multiply($temp);
1559            }
1560
1561            $adjust = $this->_array_repeat(0, $q_index);
1562            $temp_value = array($quotient_value[$q_index]);
1563            $temp = $temp->multiply($y);
1564            $temp_value = &$temp->value;
1565            if (count($temp_value)) {
1566                $temp_value = array_merge($adjust, $temp_value);
1567            }
1568
1569            $x = $x->subtract($temp);
1570
1571            if ($x->compare($zero) < 0) {
1572                $temp_value = array_merge($adjust, $y_value);
1573                $x = $x->add($temp);
1574
1575                --$quotient_value[$q_index];
1576            }
1577
1578            $x_max = count($x_value) - 1;
1579        }
1580
1581        // unnormalize the remainder
1582        $x->_rshift($shift);
1583
1584        $quotient->is_negative = $x_sign != $y_sign;
1585
1586        // calculate the "common residue", if appropriate
1587        if ($x_sign) {
1588            $y->_rshift($shift);
1589            $x = $y->subtract($x);
1590        }
1591
1592        return array($this->_normalize($quotient), $this->_normalize($x));
1593    }
1594
1595    /**
1596     * Divides a BigInteger by a regular integer
1597     *
1598     * abc / x = a00 / x + b0 / x + c / x
1599     *
1600     * @param array $dividend
1601     * @param array $divisor
1602     * @return array
1603     * @access private
1604     */
1605    function _divide_digit($dividend, $divisor)
1606    {
1607        $carry = 0;
1608        $result = array();
1609
1610        for ($i = count($dividend) - 1; $i >= 0; --$i) {
1611            $temp = self::$baseFull * $carry + $dividend[$i];
1612            $result[$i] = $this->_safe_divide($temp, $divisor);
1613            $carry = (int) ($temp - $divisor * $result[$i]);
1614        }
1615
1616        return array($result, $carry);
1617    }
1618
1619    /**
1620     * Performs modular exponentiation.
1621     *
1622     * Here's an example:
1623     * <code>
1624     * <?php
1625     *    $a = new \phpseclib\Math\BigInteger('10');
1626     *    $b = new \phpseclib\Math\BigInteger('20');
1627     *    $c = new \phpseclib\Math\BigInteger('30');
1628     *
1629     *    $c = $a->modPow($b, $c);
1630     *
1631     *    echo $c->toString(); // outputs 10
1632     * ?>
1633     * </code>
1634     *
1635     * @param \phpseclib\Math\BigInteger $e
1636     * @param \phpseclib\Math\BigInteger $n
1637     * @return \phpseclib\Math\BigInteger
1638     * @access public
1639     * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
1640     *    and although the approach involving repeated squaring does vastly better, it, too, is impractical
1641     *    for our purposes.  The reason being that division - by far the most complicated and time-consuming
1642     *    of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
1643     *
1644     *    Modular reductions resolve this issue.  Although an individual modular reduction takes more time
1645     *    then an individual division, when performed in succession (with the same modulo), they're a lot faster.
1646     *
1647     *    The two most commonly used modular reductions are Barrett and Montgomery reduction.  Montgomery reduction,
1648     *    although faster, only works when the gcd of the modulo and of the base being used is 1.  In RSA, when the
1649     *    base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
1650     *    the product of two odd numbers is odd), but what about when RSA isn't used?
1651     *
1652     *    In contrast, Barrett reduction has no such constraint.  As such, some bigint implementations perform a
1653     *    Barrett reduction after every operation in the modpow function.  Others perform Barrett reductions when the
1654     *    modulo is even and Montgomery reductions when the modulo is odd.  BigInteger.java's modPow method, however,
1655     *    uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
1656     *    the other, a power of two - and recombine them, later.  This is the method that this modPow function uses.
1657     *    {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
1658     */
1659    function modPow($e, $n)
1660    {
1661        $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
1662
1663        if ($e->compare(new static()) < 0) {
1664            $e = $e->abs();
1665
1666            $temp = $this->modInverse($n);
1667            if ($temp === false) {
1668                return false;
1669            }
1670
1671            return $this->_normalize($temp->modPow($e, $n));
1672        }
1673
1674        if (MATH_BIGINTEGER_MODE == self::MODE_GMP) {
1675            $temp = new static();
1676            $temp->value = gmp_powm($this->value, $e->value, $n->value);
1677
1678            return $this->_normalize($temp);
1679        }
1680
1681        if ($this->compare(new static()) < 0 || $this->compare($n) > 0) {
1682            list(, $temp) = $this->divide($n);
1683            return $temp->modPow($e, $n);
1684        }
1685
1686        if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
1687            $components = array(
1688                'modulus' => $n->toBytes(true),
1689                'publicExponent' => $e->toBytes(true)
1690            );
1691
1692            $components = array(
1693                'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
1694                'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
1695            );
1696
1697            $RSAPublicKey = pack(
1698                'Ca*a*a*',
1699                48,
1700                $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
1701                $components['modulus'],
1702                $components['publicExponent']
1703            );
1704
1705            $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
1706            $RSAPublicKey = chr(0) . $RSAPublicKey;
1707            $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
1708
1709            $encapsulated = pack(
1710                'Ca*a*',
1711                48,
1712                $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)),
1713                $rsaOID . $RSAPublicKey
1714            );
1715
1716            $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
1717                             chunk_split(base64_encode($encapsulated)) .
1718                             '-----END PUBLIC KEY-----';
1719
1720            $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
1721
1722            if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
1723                return new static($result, 256);
1724            }
1725        }
1726
1727        if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
1728            $temp = new static();
1729            $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
1730
1731            return $this->_normalize($temp);
1732        }
1733
1734        if (empty($e->value)) {
1735            $temp = new static();
1736            $temp->value = array(1);
1737            return $this->_normalize($temp);
1738        }
1739
1740        if ($e->value == array(1)) {
1741            list(, $temp) = $this->divide($n);
1742            return $this->_normalize($temp);
1743        }
1744
1745        if ($e->value == array(2)) {
1746            $temp = new static();
1747            $temp->value = $this->_square($this->value);
1748            list(, $temp) = $temp->divide($n);
1749            return $this->_normalize($temp);
1750        }
1751
1752        return $this->_normalize($this->_slidingWindow($e, $n, self::BARRETT));
1753
1754        // the following code, although not callable, can be run independently of the above code
1755        // although the above code performed better in my benchmarks the following could might
1756        // perform better under different circumstances. in lieu of deleting it it's just been
1757        // made uncallable
1758
1759        // is the modulo odd?
1760        if ($n->value[0] & 1) {
1761            return $this->_normalize($this->_slidingWindow($e, $n, self::MONTGOMERY));
1762        }
1763        // if it's not, it's even
1764
1765        // find the lowest set bit (eg. the max pow of 2 that divides $n)
1766        for ($i = 0; $i < count($n->value); ++$i) {
1767            if ($n->value[$i]) {
1768                $temp = decbin($n->value[$i]);
1769                $j = strlen($temp) - strrpos($temp, '1') - 1;
1770                $j+= 26 * $i;
1771                break;
1772            }
1773        }
1774        // at this point, 2^$j * $n/(2^$j) == $n
1775
1776        $mod1 = $n->copy();
1777        $mod1->_rshift($j);
1778        $mod2 = new static();
1779        $mod2->value = array(1);
1780        $mod2->_lshift($j);
1781
1782        $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, self::MONTGOMERY) : new static();
1783        $part2 = $this->_slidingWindow($e, $mod2, self::POWEROF2);
1784
1785        $y1 = $mod2->modInverse($mod1);
1786        $y2 = $mod1->modInverse($mod2);
1787
1788        $result = $part1->multiply($mod2);
1789        $result = $result->multiply($y1);
1790
1791        $temp = $part2->multiply($mod1);
1792        $temp = $temp->multiply($y2);
1793
1794        $result = $result->add($temp);
1795        list(, $result) = $result->divide($n);
1796
1797        return $this->_normalize($result);
1798    }
1799
1800    /**
1801     * Performs modular exponentiation.
1802     *
1803     * Alias for modPow().
1804     *
1805     * @param \phpseclib\Math\BigInteger $e
1806     * @param \phpseclib\Math\BigInteger $n
1807     * @return \phpseclib\Math\BigInteger
1808     * @access public
1809     */
1810    function powMod($e, $n)
1811    {
1812        return $this->modPow($e, $n);
1813    }
1814
1815    /**
1816     * Sliding Window k-ary Modular Exponentiation
1817     *
1818     * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
1819     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}.  In a departure from those algorithims,
1820     * however, this function performs a modular reduction after every multiplication and squaring operation.
1821     * As such, this function has the same preconditions that the reductions being used do.
1822     *
1823     * @param \phpseclib\Math\BigInteger $e
1824     * @param \phpseclib\Math\BigInteger $n
1825     * @param int $mode
1826     * @return \phpseclib\Math\BigInteger
1827     * @access private
1828     */
1829    function _slidingWindow($e, $n, $mode)
1830    {
1831        static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
1832        //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
1833
1834        $e_value = $e->value;
1835        $e_length = count($e_value) - 1;
1836        $e_bits = decbin($e_value[$e_length]);
1837        for ($i = $e_length - 1; $i >= 0; --$i) {
1838            $e_bits.= str_pad(decbin($e_value[$i]), self::$base, '0', STR_PAD_LEFT);
1839        }
1840
1841        $e_length = strlen($e_bits);
1842
1843        // calculate the appropriate window size.
1844        // $window_size == 3 if $window_ranges is between 25 and 81, for example.
1845        for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) {
1846        }
1847
1848        $n_value = $n->value;
1849
1850        // precompute $this^0 through $this^$window_size
1851        $powers = array();
1852        $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
1853        $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
1854
1855        // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
1856        // in a 1.  ie. it's supposed to be odd.
1857        $temp = 1 << ($window_size - 1);
1858        for ($i = 1; $i < $temp; ++$i) {
1859            $i2 = $i << 1;
1860            $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
1861        }
1862
1863        $result = array(1);
1864        $result = $this->_prepareReduce($result, $n_value, $mode);
1865
1866        for ($i = 0; $i < $e_length;) {
1867            if (!$e_bits[$i]) {
1868                $result = $this->_squareReduce($result, $n_value, $mode);
1869                ++$i;
1870            } else {
1871                for ($j = $window_size - 1; $j > 0; --$j) {
1872                    if (!empty($e_bits[$i + $j])) {
1873                        break;
1874                    }
1875                }
1876
1877                // eg. the length of substr($e_bits, $i, $j + 1)
1878                for ($k = 0; $k <= $j; ++$k) {
1879                    $result = $this->_squareReduce($result, $n_value, $mode);
1880                }
1881
1882                $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
1883
1884                $i += $j + 1;
1885            }
1886        }
1887
1888        $temp = new static();
1889        $temp->value = $this->_reduce($result, $n_value, $mode);
1890
1891        return $temp;
1892    }
1893
1894    /**
1895     * Modular reduction
1896     *
1897     * For most $modes this will return the remainder.
1898     *
1899     * @see self::_slidingWindow()
1900     * @access private
1901     * @param array $x
1902     * @param array $n
1903     * @param int $mode
1904     * @return array
1905     */
1906    function _reduce($x, $n, $mode)
1907    {
1908        switch ($mode) {
1909            case self::MONTGOMERY:
1910                return $this->_montgomery($x, $n);
1911            case self::BARRETT:
1912                return $this->_barrett($x, $n);
1913            case self::POWEROF2:
1914                $lhs = new static();
1915                $lhs->value = $x;
1916                $rhs = new static();
1917                $rhs->value = $n;
1918                return $x->_mod2($n);
1919            case self::CLASSIC:
1920                $lhs = new static();
1921                $lhs->value = $x;
1922                $rhs = new static();
1923                $rhs->value = $n;
1924                list(, $temp) = $lhs->divide($rhs);
1925                return $temp->value;
1926            case self::NONE:
1927                return $x;
1928            default:
1929                // an invalid $mode was provided
1930        }
1931    }
1932
1933    /**
1934     * Modular reduction preperation
1935     *
1936     * @see self::_slidingWindow()
1937     * @access private
1938     * @param array $x
1939     * @param array $n
1940     * @param int $mode
1941     * @return array
1942     */
1943    function _prepareReduce($x, $n, $mode)
1944    {
1945        if ($mode == self::MONTGOMERY) {
1946            return $this->_prepMontgomery($x, $n);
1947        }
1948        return $this->_reduce($x, $n, $mode);
1949    }
1950
1951    /**
1952     * Modular multiply
1953     *
1954     * @see self::_slidingWindow()
1955     * @access private
1956     * @param array $x
1957     * @param array $y
1958     * @param array $n
1959     * @param int $mode
1960     * @return array
1961     */
1962    function _multiplyReduce($x, $y, $n, $mode)
1963    {
1964        if ($mode == self::MONTGOMERY) {
1965            return $this->_montgomeryMultiply($x, $y, $n);
1966        }
1967        $temp = $this->_multiply($x, false, $y, false);
1968        return $this->_reduce($temp[self::VALUE], $n, $mode);
1969    }
1970
1971    /**
1972     * Modular square
1973     *
1974     * @see self::_slidingWindow()
1975     * @access private
1976     * @param array $x
1977     * @param array $n
1978     * @param int $mode
1979     * @return array
1980     */
1981    function _squareReduce($x, $n, $mode)
1982    {
1983        if ($mode == self::MONTGOMERY) {
1984            return $this->_montgomeryMultiply($x, $x, $n);
1985        }
1986        return $this->_reduce($this->_square($x), $n, $mode);
1987    }
1988
1989    /**
1990     * Modulos for Powers of Two
1991     *
1992     * Calculates $x%$n, where $n = 2**$e, for some $e.  Since this is basically the same as doing $x & ($n-1),
1993     * we'll just use this function as a wrapper for doing that.
1994     *
1995     * @see self::_slidingWindow()
1996     * @access private
1997     * @param \phpseclib\Math\BigInteger $n
1998     * @return \phpseclib\Math\BigInteger
1999     */
2000    function _mod2($n)
2001    {
2002        $temp = new static();
2003        $temp->value = array(1);
2004        return $this->bitwise_and($n->subtract($temp));
2005    }
2006
2007    /**
2008     * Barrett Modular Reduction
2009     *
2010     * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
2011     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
2012     * so as not to require negative numbers (initially, this script didn't support negative numbers).
2013     *
2014     * Employs "folding", as described at
2015     * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
2016     * 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."
2017     *
2018     * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
2019     * usable on account of (1) its not using reasonable radix points as discussed in
2020     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
2021     * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
2022     * (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
2023     * comments for details.
2024     *
2025     * @see self::_slidingWindow()
2026     * @access private
2027     * @param array $n
2028     * @param array $m
2029     * @return array
2030     */
2031    function _barrett($n, $m)
2032    {
2033        static $cache = array(
2034            self::VARIABLE => array(),
2035            self::DATA => array()
2036        );
2037
2038        $m_length = count($m);
2039
2040        // if ($this->_compare($n, $this->_square($m)) >= 0) {
2041        if (count($n) > 2 * $m_length) {
2042            $lhs = new static();
2043            $rhs = new static();
2044            $lhs->value = $n;
2045            $rhs->value = $m;
2046            list(, $temp) = $lhs->divide($rhs);
2047            return $temp->value;
2048        }
2049
2050        // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
2051        if ($m_length < 5) {
2052            return $this->_regularBarrett($n, $m);
2053        }
2054
2055        // n = 2 * m.length
2056
2057        if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
2058            $key = count($cache[self::VARIABLE]);
2059            $cache[self::VARIABLE][] = $m;
2060
2061            $lhs = new static();
2062            $lhs_value = &$lhs->value;
2063            $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
2064            $lhs_value[] = 1;
2065            $rhs = new static();
2066            $rhs->value = $m;
2067
2068            list($u, $m1) = $lhs->divide($rhs);
2069            $u = $u->value;
2070            $m1 = $m1->value;
2071
2072            $cache[self::DATA][] = array(
2073                'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
2074                'm1'=> $m1 // m.length
2075            );
2076        } else {
2077            extract($cache[self::DATA][$key]);
2078        }
2079
2080        $cutoff = $m_length + ($m_length >> 1);
2081        $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
2082        $msd = array_slice($n, $cutoff);    // m.length >> 1
2083        $lsd = $this->_trim($lsd);
2084        $temp = $this->_multiply($msd, false, $m1, false);
2085        $n = $this->_add($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1
2086
2087        if ($m_length & 1) {
2088            return $this->_regularBarrett($n[self::VALUE], $m);
2089        }
2090
2091        // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
2092        $temp = array_slice($n[self::VALUE], $m_length - 1);
2093        // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
2094        // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
2095        $temp = $this->_multiply($temp, false, $u, false);
2096        // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
2097        // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
2098        $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1);
2099        // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
2100        // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
2101        $temp = $this->_multiply($temp, false, $m, false);
2102
2103        // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
2104        // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
2105        // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
2106
2107        $result = $this->_subtract($n[self::VALUE], false, $temp[self::VALUE], false);
2108
2109        while ($this->_compare($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) {
2110            $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $m, false);
2111        }
2112
2113        return $result[self::VALUE];
2114    }
2115
2116    /**
2117     * (Regular) Barrett Modular Reduction
2118     *
2119     * For numbers with more than four digits BigInteger::_barrett() is faster.  The difference between that and this
2120     * is that this function does not fold the denominator into a smaller form.
2121     *
2122     * @see self::_slidingWindow()
2123     * @access private
2124     * @param array $x
2125     * @param array $n
2126     * @return array
2127     */
2128    function _regularBarrett($x, $n)
2129    {
2130        static $cache = array(
2131            self::VARIABLE => array(),
2132            self::DATA => array()
2133        );
2134
2135        $n_length = count($n);
2136
2137        if (count($x) > 2 * $n_length) {
2138            $lhs = new static();
2139            $rhs = new static();
2140            $lhs->value = $x;
2141            $rhs->value = $n;
2142            list(, $temp) = $lhs->divide($rhs);
2143            return $temp->value;
2144        }
2145
2146        if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
2147            $key = count($cache[self::VARIABLE]);
2148            $cache[self::VARIABLE][] = $n;
2149            $lhs = new static();
2150            $lhs_value = &$lhs->value;
2151            $lhs_value = $this->_array_repeat(0, 2 * $n_length);
2152            $lhs_value[] = 1;
2153            $rhs = new static();
2154            $rhs->value = $n;
2155            list($temp, ) = $lhs->divide($rhs); // m.length
2156            $cache[self::DATA][] = $temp->value;
2157        }
2158
2159        // 2 * m.length - (m.length - 1) = m.length + 1
2160        $temp = array_slice($x, $n_length - 1);
2161        // (m.length + 1) + m.length = 2 * m.length + 1
2162        $temp = $this->_multiply($temp, false, $cache[self::DATA][$key], false);
2163        // (2 * m.length + 1) - (m.length - 1) = m.length + 2
2164        $temp = array_slice($temp[self::VALUE], $n_length + 1);
2165
2166        // m.length + 1
2167        $result = array_slice($x, 0, $n_length + 1);
2168        // m.length + 1
2169        $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
2170        // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
2171
2172        if ($this->_compare($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
2173            $corrector_value = $this->_array_repeat(0, $n_length + 1);
2174            $corrector_value[count($corrector_value)] = 1;
2175            $result = $this->_add($result, false, $corrector_value, false);
2176            $result = $result[self::VALUE];
2177        }
2178
2179        // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
2180        $result = $this->_subtract($result, false, $temp[self::VALUE], $temp[self::SIGN]);
2181        while ($this->_compare($result[self::VALUE], $result[self::SIGN], $n, false) > 0) {
2182            $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $n, false);
2183        }
2184
2185        return $result[self::VALUE];
2186    }
2187
2188    /**
2189     * Performs long multiplication up to $stop digits
2190     *
2191     * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
2192     *
2193     * @see self::_regularBarrett()
2194     * @param array $x_value
2195     * @param bool $x_negative
2196     * @param array $y_value
2197     * @param bool $y_negative
2198     * @param int $stop
2199     * @return array
2200     * @access private
2201     */
2202    function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
2203    {
2204        $x_length = count($x_value);
2205        $y_length = count($y_value);
2206
2207        if (!$x_length || !$y_length) { // a 0 is being multiplied
2208            return array(
2209                self::VALUE => array(),
2210                self::SIGN => false
2211            );
2212        }
2213
2214        if ($x_length < $y_length) {
2215            $temp = $x_value;
2216            $x_value = $y_value;
2217            $y_value = $temp;
2218
2219            $x_length = count($x_value);
2220            $y_length = count($y_value);
2221        }
2222
2223        $product_value = $this->_array_repeat(0, $x_length + $y_length);
2224
2225        // the following for loop could be removed if the for loop following it
2226        // (the one with nested for loops) initially set $i to 0, but
2227        // doing so would also make the result in one set of unnecessary adds,
2228        // since on the outermost loops first pass, $product->value[$k] is going
2229        // to always be 0
2230
2231        $carry = 0;
2232
2233        for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
2234            $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
2235            $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2236            $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
2237        }
2238
2239        if ($j < $stop) {
2240            $product_value[$j] = $carry;
2241        }
2242
2243        // the above for loop is what the previous comment was talking about.  the
2244        // following for loop is the "one with nested for loops"
2245
2246        for ($i = 1; $i < $y_length; ++$i) {
2247            $carry = 0;
2248
2249            for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
2250                $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
2251                $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2252                $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
2253            }
2254
2255            if ($k < $stop) {
2256                $product_value[$k] = $carry;
2257            }
2258        }
2259
2260        return array(
2261            self::VALUE => $this->_trim($product_value),
2262            self::SIGN => $x_negative != $y_negative
2263        );
2264    }
2265
2266    /**
2267     * Montgomery Modular Reduction
2268     *
2269     * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n.
2270     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be
2271     * improved upon (basically, by using the comba method).  gcd($n, 2) must be equal to one for this function
2272     * to work correctly.
2273     *
2274     * @see self::_prepMontgomery()
2275     * @see self::_slidingWindow()
2276     * @access private
2277     * @param array $x
2278     * @param array $n
2279     * @return array
2280     */
2281    function _montgomery($x, $n)
2282    {
2283        static $cache = array(
2284            self::VARIABLE => array(),
2285            self::DATA => array()
2286        );
2287
2288        if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
2289            $key = count($cache[self::VARIABLE]);
2290            $cache[self::VARIABLE][] = $x;
2291            $cache[self::DATA][] = $this->_modInverse67108864($n);
2292        }
2293
2294        $k = count($n);
2295
2296        $result = array(self::VALUE => $x);
2297
2298        for ($i = 0; $i < $k; ++$i) {
2299            $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key];
2300            $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2301            $temp = $this->_regularMultiply(array($temp), $n);
2302            $temp = array_merge($this->_array_repeat(0, $i), $temp);
2303            $result = $this->_add($result[self::VALUE], false, $temp, false);
2304        }
2305
2306        $result[self::VALUE] = array_slice($result[self::VALUE], $k);
2307
2308        if ($this->_compare($result, false, $n, false) >= 0) {
2309            $result = $this->_subtract($result[self::VALUE], false, $n, false);
2310        }
2311
2312        return $result[self::VALUE];
2313    }
2314
2315    /**
2316     * Montgomery Multiply
2317     *
2318     * Interleaves the montgomery reduction and long multiplication algorithms together as described in
2319     * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
2320     *
2321     * @see self::_prepMontgomery()
2322     * @see self::_montgomery()
2323     * @access private
2324     * @param array $x
2325     * @param array $y
2326     * @param array $m
2327     * @return array
2328     */
2329    function _montgomeryMultiply($x, $y, $m)
2330    {
2331        $temp = $this->_multiply($x, false, $y, false);
2332        return $this->_montgomery($temp[self::VALUE], $m);
2333
2334        // the following code, although not callable, can be run independently of the above code
2335        // although the above code performed better in my benchmarks the following could might
2336        // perform better under different circumstances. in lieu of deleting it it's just been
2337        // made uncallable
2338
2339        static $cache = array(
2340            self::VARIABLE => array(),
2341            self::DATA => array()
2342        );
2343
2344        if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
2345            $key = count($cache[self::VARIABLE]);
2346            $cache[self::VARIABLE][] = $m;
2347            $cache[self::DATA][] = $this->_modInverse67108864($m);
2348        }
2349
2350        $n = max(count($x), count($y), count($m));
2351        $x = array_pad($x, $n, 0);
2352        $y = array_pad($y, $n, 0);
2353        $m = array_pad($m, $n, 0);
2354        $a = array(self::VALUE => $this->_array_repeat(0, $n + 1));
2355        for ($i = 0; $i < $n; ++$i) {
2356            $temp = $a[self::VALUE][0] + $x[$i] * $y[0];
2357            $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2358            $temp = $temp * $cache[self::DATA][$key];
2359            $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2360            $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
2361            $a = $this->_add($a[self::VALUE], false, $temp[self::VALUE], false);
2362            $a[self::VALUE] = array_slice($a[self::VALUE], 1);
2363        }
2364        if ($this->_compare($a[self::VALUE], false, $m, false) >= 0) {
2365            $a = $this->_subtract($a[self::VALUE], false, $m, false);
2366        }
2367        return $a[self::VALUE];
2368    }
2369
2370    /**
2371     * Prepare a number for use in Montgomery Modular Reductions
2372     *
2373     * @see self::_montgomery()
2374     * @see self::_slidingWindow()
2375     * @access private
2376     * @param array $x
2377     * @param array $n
2378     * @return array
2379     */
2380    function _prepMontgomery($x, $n)
2381    {
2382        $lhs = new static();
2383        $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
2384        $rhs = new static();
2385        $rhs->value = $n;
2386
2387        list(, $temp) = $lhs->divide($rhs);
2388        return $temp->value;
2389    }
2390
2391    /**
2392     * Modular Inverse of a number mod 2**26 (eg. 67108864)
2393     *
2394     * Based off of the bnpInvDigit function implemented and justified in the following URL:
2395     *
2396     * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
2397     *
2398     * The following URL provides more info:
2399     *
2400     * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
2401     *
2402     * As for why we do all the bitmasking...  strange things can happen when converting from floats to ints. For
2403     * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
2404     * int(-2147483648).  To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
2405     * auto-converted to floats.  The outermost bitmask is present because without it, there's no guarantee that
2406     * the "residue" returned would be the so-called "common residue".  We use fmod, in the last step, because the
2407     * maximum possible $x is 26 bits and the maximum $result is 16 bits.  Thus, we have to be able to handle up to
2408     * 40 bits, which only 64-bit floating points will support.
2409     *
2410     * Thanks to Pedro Gimeno Fortea for input!
2411     *
2412     * @see self::_montgomery()
2413     * @access private
2414     * @param array $x
2415     * @return int
2416     */
2417    function _modInverse67108864($x) // 2**26 == 67,108,864
2418    {
2419        $x = -$x[0];
2420        $result = $x & 0x3; // x**-1 mod 2**2
2421        $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
2422        $result = ($result * (2 - ($x & 0xFF) * $result))  & 0xFF; // x**-1 mod 2**8
2423        $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
2424        $result = fmod($result * (2 - fmod($x * $result, self::$baseFull)), self::$baseFull); // x**-1 mod 2**26
2425        return $result & self::$maxDigit;
2426    }
2427
2428    /**
2429     * Calculates modular inverses.
2430     *
2431     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
2432     *
2433     * Here's an example:
2434     * <code>
2435     * <?php
2436     *    $a = new \phpseclib\Math\BigInteger(30);
2437     *    $b = new \phpseclib\Math\BigInteger(17);
2438     *
2439     *    $c = $a->modInverse($b);
2440     *    echo $c->toString(); // outputs 4
2441     *
2442     *    echo "\r\n";
2443     *
2444     *    $d = $a->multiply($c);
2445     *    list(, $d) = $d->divide($b);
2446     *    echo $d; // outputs 1 (as per the definition of modular inverse)
2447     * ?>
2448     * </code>
2449     *
2450     * @param \phpseclib\Math\BigInteger $n
2451     * @return \phpseclib\Math\BigInteger|false
2452     * @access public
2453     * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.
2454     */
2455    function modInverse($n)
2456    {
2457        switch (MATH_BIGINTEGER_MODE) {
2458            case self::MODE_GMP:
2459                $temp = new static();
2460                $temp->value = gmp_invert($this->value, $n->value);
2461
2462                return ($temp->value === false) ? false : $this->_normalize($temp);
2463        }
2464
2465        static $zero, $one;
2466        if (!isset($zero)) {
2467            $zero = new static();
2468            $one = new static(1);
2469        }
2470
2471        // $x mod -$n == $x mod $n.
2472        $n = $n->abs();
2473
2474        if ($this->compare($zero) < 0) {
2475            $temp = $this->abs();
2476            $temp = $temp->modInverse($n);
2477            return $this->_normalize($n->subtract($temp));
2478        }
2479
2480        extract($this->extendedGCD($n));
2481
2482        if (!$gcd->equals($one)) {
2483            return false;
2484        }
2485
2486        $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
2487
2488        return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
2489    }
2490
2491    /**
2492     * Calculates the greatest common divisor and Bezout's identity.
2493     *
2494     * Say you have 693 and 609.  The GCD is 21.  Bezout's identity states that there exist integers x and y such that
2495     * 693*x + 609*y == 21.  In point of fact, there are actually an infinite number of x and y combinations and which
2496     * combination is returned is dependent upon which mode is in use.  See
2497     * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
2498     *
2499     * Here's an example:
2500     * <code>
2501     * <?php
2502     *    $a = new \phpseclib\Math\BigInteger(693);
2503     *    $b = new \phpseclib\Math\BigInteger(609);
2504     *
2505     *    extract($a->extendedGCD($b));
2506     *
2507     *    echo $gcd->toString() . "\r\n"; // outputs 21
2508     *    echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
2509     * ?>
2510     * </code>
2511     *
2512     * @param \phpseclib\Math\BigInteger $n
2513     * @return \phpseclib\Math\BigInteger
2514     * @access public
2515     * @internal Calculates the GCD using the binary xGCD algorithim described in
2516     *    {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}.  As the text above 14.61 notes,
2517     *    the more traditional algorithim requires "relatively costly multiple-precision divisions".
2518     */
2519    function extendedGCD($n)
2520    {
2521        switch (MATH_BIGINTEGER_MODE) {
2522            case self::MODE_GMP:
2523                extract(gmp_gcdext($this->value, $n->value));
2524
2525                return array(
2526                    'gcd' => $this->_normalize(new static($g)),
2527                    'x'   => $this->_normalize(new static($s)),
2528                    'y'   => $this->_normalize(new static($t))
2529                );
2530            case self::MODE_BCMATH:
2531                // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
2532                // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway.  as is,
2533                // the basic extended euclidean algorithim is what we're using.
2534
2535                $u = $this->value;
2536                $v = $n->value;
2537
2538                $a = '1';
2539                $b = '0';
2540                $c = '0';
2541                $d = '1';
2542
2543                while (bccomp($v, '0', 0) != 0) {
2544                    $q = bcdiv($u, $v, 0);
2545
2546                    $temp = $u;
2547                    $u = $v;
2548                    $v = bcsub($temp, bcmul($v, $q, 0), 0);
2549
2550                    $temp = $a;
2551                    $a = $c;
2552                    $c = bcsub($temp, bcmul($a, $q, 0), 0);
2553
2554                    $temp = $b;
2555                    $b = $d;
2556                    $d = bcsub($temp, bcmul($b, $q, 0), 0);
2557                }
2558
2559                return array(
2560                    'gcd' => $this->_normalize(new static($u)),
2561                    'x'   => $this->_normalize(new static($a)),
2562                    'y'   => $this->_normalize(new static($b))
2563                );
2564        }
2565
2566        $y = $n->copy();
2567        $x = $this->copy();
2568        $g = new static();
2569        $g->value = array(1);
2570
2571        while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) {
2572            $x->_rshift(1);
2573            $y->_rshift(1);
2574            $g->_lshift(1);
2575        }
2576
2577        $u = $x->copy();
2578        $v = $y->copy();
2579
2580        $a = new static();
2581        $b = new static();
2582        $c = new static();
2583        $d = new static();
2584
2585        $a->value = $d->value = $g->value = array(1);
2586        $b->value = $c->value = array();
2587
2588        while (!empty($u->value)) {
2589            while (!($u->value[0] & 1)) {
2590                $u->_rshift(1);
2591                if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
2592                    $a = $a->add($y);
2593                    $b = $b->subtract($x);
2594                }
2595                $a->_rshift(1);
2596                $b->_rshift(1);
2597            }
2598
2599            while (!($v->value[0] & 1)) {
2600                $v->_rshift(1);
2601                if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) {
2602                    $c = $c->add($y);
2603                    $d = $d->subtract($x);
2604                }
2605                $c->_rshift(1);
2606                $d->_rshift(1);
2607            }
2608
2609            if ($u->compare($v) >= 0) {
2610                $u = $u->subtract($v);
2611                $a = $a->subtract($c);
2612                $b = $b->subtract($d);
2613            } else {
2614                $v = $v->subtract($u);
2615                $c = $c->subtract($a);
2616                $d = $d->subtract($b);
2617            }
2618        }
2619
2620        return array(
2621            'gcd' => $this->_normalize($g->multiply($v)),
2622            'x'   => $this->_normalize($c),
2623            'y'   => $this->_normalize($d)
2624        );
2625    }
2626
2627    /**
2628     * Calculates the greatest common divisor
2629     *
2630     * Say you have 693 and 609.  The GCD is 21.
2631     *
2632     * Here's an example:
2633     * <code>
2634     * <?php
2635     *    $a = new \phpseclib\Math\BigInteger(693);
2636     *    $b = new \phpseclib\Math\BigInteger(609);
2637     *
2638     *    $gcd = a->extendedGCD($b);
2639     *
2640     *    echo $gcd->toString() . "\r\n"; // outputs 21
2641     * ?>
2642     * </code>
2643     *
2644     * @param \phpseclib\Math\BigInteger $n
2645     * @return \phpseclib\Math\BigInteger
2646     * @access public
2647     */
2648    function gcd($n)
2649    {
2650        extract($this->extendedGCD($n));
2651        return $gcd;
2652    }
2653
2654    /**
2655     * Absolute value.
2656     *
2657     * @return \phpseclib\Math\BigInteger
2658     * @access public
2659     */
2660    function abs()
2661    {
2662        $temp = new static();
2663
2664        switch (MATH_BIGINTEGER_MODE) {
2665            case self::MODE_GMP:
2666                $temp->value = gmp_abs($this->value);
2667                break;
2668            case self::MODE_BCMATH:
2669                $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
2670                break;
2671            default:
2672                $temp->value = $this->value;
2673        }
2674
2675        return $temp;
2676    }
2677
2678    /**
2679     * Compares two numbers.
2680     *
2681     * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this is
2682     * demonstrated thusly:
2683     *
2684     * $x  > $y: $x->compare($y)  > 0
2685     * $x  < $y: $x->compare($y)  < 0
2686     * $x == $y: $x->compare($y) == 0
2687     *
2688     * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
2689     *
2690     * @param \phpseclib\Math\BigInteger $y
2691     * @return int that is < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
2692     * @access public
2693     * @see self::equals()
2694     * @internal Could return $this->subtract($x), but that's not as fast as what we do do.
2695     */
2696    function compare($y)
2697    {
2698        switch (MATH_BIGINTEGER_MODE) {
2699            case self::MODE_GMP:
2700                $r = gmp_cmp($this->value, $y->value);
2701                if ($r < -1) {
2702                    $r = -1;
2703                }
2704                if ($r > 1) {
2705                    $r = 1;
2706                }
2707                return $r;
2708            case self::MODE_BCMATH:
2709                return bccomp($this->value, $y->value, 0);
2710        }
2711
2712        return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
2713    }
2714
2715    /**
2716     * Compares two numbers.
2717     *
2718     * @param array $x_value
2719     * @param bool $x_negative
2720     * @param array $y_value
2721     * @param bool $y_negative
2722     * @return int
2723     * @see self::compare()
2724     * @access private
2725     */
2726    function _compare($x_value, $x_negative, $y_value, $y_negative)
2727    {
2728        if ($x_negative != $y_negative) {
2729            return (!$x_negative && $y_negative) ? 1 : -1;
2730        }
2731
2732        $result = $x_negative ? -1 : 1;
2733
2734        if (count($x_value) != count($y_value)) {
2735            return (count($x_value) > count($y_value)) ? $result : -$result;
2736        }
2737        $size = max(count($x_value), count($y_value));
2738
2739        $x_value = array_pad($x_value, $size, 0);
2740        $y_value = array_pad($y_value, $size, 0);
2741
2742        for ($i = count($x_value) - 1; $i >= 0; --$i) {
2743            if ($x_value[$i] != $y_value[$i]) {
2744                return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
2745            }
2746        }
2747
2748        return 0;
2749    }
2750
2751    /**
2752     * Tests the equality of two numbers.
2753     *
2754     * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
2755     *
2756     * @param \phpseclib\Math\BigInteger $x
2757     * @return bool
2758     * @access public
2759     * @see self::compare()
2760     */
2761    function equals($x)
2762    {
2763        switch (MATH_BIGINTEGER_MODE) {
2764            case self::MODE_GMP:
2765                return gmp_cmp($this->value, $x->value) == 0;
2766            default:
2767                return $this->value === $x->value && $this->is_negative == $x->is_negative;
2768        }
2769    }
2770
2771    /**
2772     * Set Precision
2773     *
2774     * Some bitwise operations give different results depending on the precision being used.  Examples include left
2775     * shift, not, and rotates.
2776     *
2777     * @param int $bits
2778     * @access public
2779     */
2780    function setPrecision($bits)
2781    {
2782        $this->precision = $bits;
2783        if (MATH_BIGINTEGER_MODE != self::MODE_BCMATH) {
2784            $this->bitmask = new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
2785        } else {
2786            $this->bitmask = new static(bcpow('2', $bits, 0));
2787        }
2788
2789        $temp = $this->_normalize($this);
2790        $this->value = $temp->value;
2791    }
2792
2793    /**
2794     * Logical And
2795     *
2796     * @param \phpseclib\Math\BigInteger $x
2797     * @access public
2798     * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2799     * @return \phpseclib\Math\BigInteger
2800     */
2801    function bitwise_and($x)
2802    {
2803        switch (MATH_BIGINTEGER_MODE) {
2804            case self::MODE_GMP:
2805                $temp = new static();
2806                $temp->value = gmp_and($this->value, $x->value);
2807
2808                return $this->_normalize($temp);
2809            case self::MODE_BCMATH:
2810                $left = $this->toBytes();
2811                $right = $x->toBytes();
2812
2813                $length = max(strlen($left), strlen($right));
2814
2815                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2816                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2817
2818                return $this->_normalize(new static($left & $right, 256));
2819        }
2820
2821        $result = $this->copy();
2822
2823        $length = min(count($x->value), count($this->value));
2824
2825        $result->value = array_slice($result->value, 0, $length);
2826
2827        for ($i = 0; $i < $length; ++$i) {
2828            $result->value[$i]&= $x->value[$i];
2829        }
2830
2831        return $this->_normalize($result);
2832    }
2833
2834    /**
2835     * Logical Or
2836     *
2837     * @param \phpseclib\Math\BigInteger $x
2838     * @access public
2839     * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2840     * @return \phpseclib\Math\BigInteger
2841     */
2842    function bitwise_or($x)
2843    {
2844        switch (MATH_BIGINTEGER_MODE) {
2845            case self::MODE_GMP:
2846                $temp = new static();
2847                $temp->value = gmp_or($this->value, $x->value);
2848
2849                return $this->_normalize($temp);
2850            case self::MODE_BCMATH:
2851                $left = $this->toBytes();
2852                $right = $x->toBytes();
2853
2854                $length = max(strlen($left), strlen($right));
2855
2856                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2857                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2858
2859                return $this->_normalize(new static($left | $right, 256));
2860        }
2861
2862        $length = max(count($this->value), count($x->value));
2863        $result = $this->copy();
2864        $result->value = array_pad($result->value, $length, 0);
2865        $x->value = array_pad($x->value, $length, 0);
2866
2867        for ($i = 0; $i < $length; ++$i) {
2868            $result->value[$i]|= $x->value[$i];
2869        }
2870
2871        return $this->_normalize($result);
2872    }
2873
2874    /**
2875     * Logical Exclusive-Or
2876     *
2877     * @param \phpseclib\Math\BigInteger $x
2878     * @access public
2879     * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2880     * @return \phpseclib\Math\BigInteger
2881     */
2882    function bitwise_xor($x)
2883    {
2884        switch (MATH_BIGINTEGER_MODE) {
2885            case self::MODE_GMP:
2886                $temp = new static();
2887                $temp->value = gmp_xor(gmp_abs($this->value), gmp_abs($x->value));
2888                return $this->_normalize($temp);
2889            case self::MODE_BCMATH:
2890                $left = $this->toBytes();
2891                $right = $x->toBytes();
2892
2893                $length = max(strlen($left), strlen($right));
2894
2895                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2896                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2897
2898                return $this->_normalize(new static($left ^ $right, 256));
2899        }
2900
2901        $length = max(count($this->value), count($x->value));
2902        $result = $this->copy();
2903        $result->is_negative = false;
2904        $result->value = array_pad($result->value, $length, 0);
2905        $x->value = array_pad($x->value, $length, 0);
2906
2907        for ($i = 0; $i < $length; ++$i) {
2908            $result->value[$i]^= $x->value[$i];
2909        }
2910
2911        return $this->_normalize($result);
2912    }
2913
2914    /**
2915     * Logical Not
2916     *
2917     * @access public
2918     * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2919     * @return \phpseclib\Math\BigInteger
2920     */
2921    function bitwise_not()
2922    {
2923        // calculuate "not" without regard to $this->precision
2924        // (will always result in a smaller number.  ie. ~1 isn't 1111 1110 - it's 0)
2925        $temp = $this->toBytes();
2926        if ($temp == '') {
2927            return $this->_normalize(new static());
2928        }
2929        $pre_msb = decbin(ord($temp[0]));
2930        $temp = ~$temp;
2931        $msb = decbin(ord($temp[0]));
2932        if (strlen($msb) == 8) {
2933            $msb = substr($msb, strpos($msb, '0'));
2934        }
2935        $temp[0] = chr(bindec($msb));
2936
2937        // see if we need to add extra leading 1's
2938        $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
2939        $new_bits = $this->precision - $current_bits;
2940        if ($new_bits <= 0) {
2941            return $this->_normalize(new static($temp, 256));
2942        }
2943
2944        // generate as many leading 1's as we need to.
2945        $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
2946        $this->_base256_lshift($leading_ones, $current_bits);
2947
2948        $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
2949
2950        return $this->_normalize(new static($leading_ones | $temp, 256));
2951    }
2952
2953    /**
2954     * Logical Right Shift
2955     *
2956     * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
2957     *
2958     * @param int $shift
2959     * @return \phpseclib\Math\BigInteger
2960     * @access public
2961     * @internal The only version that yields any speed increases is the internal version.
2962     */
2963    function bitwise_rightShift($shift)
2964    {
2965        $temp = new static();
2966
2967        switch (MATH_BIGINTEGER_MODE) {
2968            case self::MODE_GMP:
2969                static $two;
2970
2971                if (!isset($two)) {
2972                    $two = gmp_init('2');
2973                }
2974
2975                $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
2976
2977                break;
2978            case self::MODE_BCMATH:
2979                $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
2980
2981                break;
2982            default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
2983                     // and I don't want to do that...
2984                $temp->value = $this->value;
2985                $temp->_rshift($shift);
2986        }
2987
2988        return $this->_normalize($temp);
2989    }
2990
2991    /**
2992     * Logical Left Shift
2993     *
2994     * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
2995     *
2996     * @param int $shift
2997     * @return \phpseclib\Math\BigInteger
2998     * @access public
2999     * @internal The only version that yields any speed increases is the internal version.
3000     */
3001    function bitwise_leftShift($shift)
3002    {
3003        $temp = new static();
3004
3005        switch (MATH_BIGINTEGER_MODE) {
3006            case self::MODE_GMP:
3007                static $two;
3008
3009                if (!isset($two)) {
3010                    $two = gmp_init('2');
3011                }
3012
3013                $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
3014
3015                break;
3016            case self::MODE_BCMATH:
3017                $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
3018
3019                break;
3020            default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
3021                     // and I don't want to do that...
3022                $temp->value = $this->value;
3023                $temp->_lshift($shift);
3024        }
3025
3026        return $this->_normalize($temp);
3027    }
3028
3029    /**
3030     * Logical Left Rotate
3031     *
3032     * Instead of the top x bits being dropped they're appended to the shifted bit string.
3033     *
3034     * @param int $shift
3035     * @return \phpseclib\Math\BigInteger
3036     * @access public
3037     */
3038    function bitwise_leftRotate($shift)
3039    {
3040        $bits = $this->toBytes();
3041
3042        if ($this->precision > 0) {
3043            $precision = $this->precision;
3044            if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
3045                $mask = $this->bitmask->subtract(new static(1));
3046                $mask = $mask->toBytes();
3047            } else {
3048                $mask = $this->bitmask->toBytes();
3049            }
3050        } else {
3051            $temp = ord($bits[0]);
3052            for ($i = 0; $temp >> $i; ++$i) {
3053            }
3054            $precision = 8 * strlen($bits) - 8 + $i;
3055            $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
3056        }
3057
3058        if ($shift < 0) {
3059            $shift+= $precision;
3060        }
3061        $shift%= $precision;
3062
3063        if (!$shift) {
3064            return $this->copy();
3065        }
3066
3067        $left = $this->bitwise_leftShift($shift);
3068        $left = $left->bitwise_and(new static($mask, 256));
3069        $right = $this->bitwise_rightShift($precision - $shift);
3070        $result = MATH_BIGINTEGER_MODE != self::MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
3071        return $this->_normalize($result);
3072    }
3073
3074    /**
3075     * Logical Right Rotate
3076     *
3077     * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
3078     *
3079     * @param int $shift
3080     * @return \phpseclib\Math\BigInteger
3081     * @access public
3082     */
3083    function bitwise_rightRotate($shift)
3084    {
3085        return $this->bitwise_leftRotate(-$shift);
3086    }
3087
3088    /**
3089     * Generates a random BigInteger
3090     *
3091     * Byte length is equal to $length. Uses \phpseclib\Crypt\Random if it's loaded and mt_rand if it's not.
3092     *
3093     * @param int $size
3094     * @return \phpseclib\Math\BigInteger
3095     * @access private
3096     */
3097    function _random_number_helper($size)
3098    {
3099        if (class_exists('\phpseclib\Crypt\Random')) {
3100            $random = Random::string($size);
3101        } else {
3102            $random = '';
3103
3104            if ($size & 1) {
3105                $random.= chr(mt_rand(0, 255));
3106            }
3107
3108            $blocks = $size >> 1;
3109            for ($i = 0; $i < $blocks; ++$i) {
3110                // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
3111                $random.= pack('n', mt_rand(0, 0xFFFF));
3112            }
3113        }
3114
3115        return new static($random, 256);
3116    }
3117
3118    /**
3119     * Generate a random number
3120     *
3121     * Returns a random number between $min and $max where $min and $max
3122     * can be defined using one of the two methods:
3123     *
3124     * $min->random($max)
3125     * $max->random($min)
3126     *
3127     * @param \phpseclib\Math\BigInteger $arg1
3128     * @param \phpseclib\Math\BigInteger $arg2
3129     * @return \phpseclib\Math\BigInteger
3130     * @access public
3131     * @internal The API for creating random numbers used to be $a->random($min, $max), where $a was a BigInteger object.
3132     *           That method is still supported for BC purposes.
3133     */
3134    function random($arg1, $arg2 = false)
3135    {
3136        if ($arg1 === false) {
3137            return false;
3138        }
3139
3140        if ($arg2 === false) {
3141            $max = $arg1;
3142            $min = $this;
3143        } else {
3144            $min = $arg1;
3145            $max = $arg2;
3146        }
3147
3148        $compare = $max->compare($min);
3149
3150        if (!$compare) {
3151            return $this->_normalize($min);
3152        } elseif ($compare < 0) {
3153            // if $min is bigger then $max, swap $min and $max
3154            $temp = $max;
3155            $max = $min;
3156            $min = $temp;
3157        }
3158
3159        static $one;
3160        if (!isset($one)) {
3161            $one = new static(1);
3162        }
3163
3164        $max = $max->subtract($min->subtract($one));
3165        $size = strlen(ltrim($max->toBytes(), chr(0)));
3166
3167        /*
3168            doing $random % $max doesn't work because some numbers will be more likely to occur than others.
3169            eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
3170            would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
3171            not all numbers would be equally likely. some would be more likely than others.
3172
3173            creating a whole new random number until you find one that is within the range doesn't work
3174            because, for sufficiently small ranges, the likelihood that you'd get a number within that range
3175            would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
3176            would be pretty high that $random would be greater than $max.
3177
3178            phpseclib works around this using the technique described here:
3179
3180            http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
3181        */
3182        $random_max = new static(chr(1) . str_repeat("\0", $size), 256);
3183        $random = $this->_random_number_helper($size);
3184
3185        list($max_multiple) = $random_max->divide($max);
3186        $max_multiple = $max_multiple->multiply($max);
3187
3188        while ($random->compare($max_multiple) >= 0) {
3189            $random = $random->subtract($max_multiple);
3190            $random_max = $random_max->subtract($max_multiple);
3191            $random = $random->bitwise_leftShift(8);
3192            $random = $random->add($this->_random_number_helper(1));
3193            $random_max = $random_max->bitwise_leftShift(8);
3194            list($max_multiple) = $random_max->divide($max);
3195            $max_multiple = $max_multiple->multiply($max);
3196        }
3197        list(, $random) = $random->divide($max);
3198
3199        return $this->_normalize($random->add($min));
3200    }
3201
3202    /**
3203     * Generate a random prime number.
3204     *
3205     * If there's not a prime within the given range, false will be returned.
3206     * If more than $timeout seconds have elapsed, give up and return false.
3207     *
3208     * @param \phpseclib\Math\BigInteger $arg1
3209     * @param \phpseclib\Math\BigInteger $arg2
3210     * @param int $timeout
3211     * @return Math_BigInteger|false
3212     * @access public
3213     * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}.
3214     */
3215    function randomPrime($arg1, $arg2 = false, $timeout = false)
3216    {
3217        if ($arg1 === false) {
3218            return false;
3219        }
3220
3221        if ($arg2 === false) {
3222            $max = $arg1;
3223            $min = $this;
3224        } else {
3225            $min = $arg1;
3226            $max = $arg2;
3227        }
3228
3229        $compare = $max->compare($min);
3230
3231        if (!$compare) {
3232            return $min->isPrime() ? $min : false;
3233        } elseif ($compare < 0) {
3234            // if $min is bigger then $max, swap $min and $max
3235            $temp = $max;
3236            $max = $min;
3237            $min = $temp;
3238        }
3239
3240        static $one, $two;
3241        if (!isset($one)) {
3242            $one = new static(1);
3243            $two = new static(2);
3244        }
3245
3246        $start = time();
3247
3248        $x = $this->random($min, $max);
3249
3250        // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
3251        if (MATH_BIGINTEGER_MODE == self::MODE_GMP && extension_loaded('gmp')) {
3252            $p = new static();
3253            $p->value = gmp_nextprime($x->value);
3254
3255            if ($p->compare($max) <= 0) {
3256                return $p;
3257            }
3258
3259            if (!$min->equals($x)) {
3260                $x = $x->subtract($one);
3261            }
3262
3263            return $x->randomPrime($min, $x);
3264        }
3265
3266        if ($x->equals($two)) {
3267            return $x;
3268        }
3269
3270        $x->_make_odd();
3271        if ($x->compare($max) > 0) {
3272            // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
3273            if ($min->equals($max)) {
3274                return false;
3275            }
3276            $x = $min->copy();
3277            $x->_make_odd();
3278        }
3279
3280        $initial_x = $x->copy();
3281
3282        while (true) {
3283            if ($timeout !== false && time() - $start > $timeout) {
3284                return false;
3285            }
3286
3287            if ($x->isPrime()) {
3288                return $x;
3289            }
3290
3291            $x = $x->add($two);
3292
3293            if ($x->compare($max) > 0) {
3294                $x = $min->copy();
3295                if ($x->equals($two)) {
3296                    return $x;
3297                }
3298                $x->_make_odd();
3299            }
3300
3301            if ($x->equals($initial_x)) {
3302                return false;
3303            }
3304        }
3305    }
3306
3307    /**
3308     * Make the current number odd
3309     *
3310     * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
3311     *
3312     * @see self::randomPrime()
3313     * @access private
3314     */
3315    function _make_odd()
3316    {
3317        switch (MATH_BIGINTEGER_MODE) {
3318            case self::MODE_GMP:
3319                gmp_setbit($this->value, 0);
3320                break;
3321            case self::MODE_BCMATH:
3322                if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3323                    $this->value = bcadd($this->value, '1');
3324                }
3325                break;
3326            default:
3327                $this->value[0] |= 1;
3328        }
3329    }
3330
3331    /**
3332     * Checks a numer to see if it's prime
3333     *
3334     * Assuming the $t parameter is not set, this function has an error rate of 2**-80.  The main motivation for the
3335     * $t parameter is distributability.  BigInteger::randomPrime() can be distributed across multiple pageloads
3336     * on a website instead of just one.
3337     *
3338     * @param \phpseclib\Math\BigInteger $t
3339     * @return bool
3340     * @access public
3341     * @internal Uses the
3342     *     {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}.  See
3343     *     {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}.
3344     */
3345    function isPrime($t = false)
3346    {
3347        $length = strlen($this->toBytes());
3348
3349        if (!$t) {
3350            // see HAC 4.49 "Note (controlling the error probability)"
3351            // @codingStandardsIgnoreStart
3352                 if ($length >= 163) { $t =  2; } // floor(1300 / 8)
3353            else if ($length >= 106) { $t =  3; } // floor( 850 / 8)
3354            else if ($length >= 81 ) { $t =  4; } // floor( 650 / 8)
3355            else if ($length >= 68 ) { $t =  5; } // floor( 550 / 8)
3356            else if ($length >= 56 ) { $t =  6; } // floor( 450 / 8)
3357            else if ($length >= 50 ) { $t =  7; } // floor( 400 / 8)
3358            else if ($length >= 43 ) { $t =  8; } // floor( 350 / 8)
3359            else if ($length >= 37 ) { $t =  9; } // floor( 300 / 8)
3360            else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
3361            else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
3362            else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
3363            else                     { $t = 27; }
3364            // @codingStandardsIgnoreEnd
3365        }
3366
3367        // ie. gmp_testbit($this, 0)
3368        // ie. isEven() or !isOdd()
3369        switch (MATH_BIGINTEGER_MODE) {
3370            case self::MODE_GMP:
3371                return gmp_prob_prime($this->value, $t) != 0;
3372            case self::MODE_BCMATH:
3373                if ($this->value === '2') {
3374                    return true;
3375                }
3376                if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3377                    return false;
3378                }
3379                break;
3380            default:
3381                if ($this->value == array(2)) {
3382                    return true;
3383                }
3384                if (~$this->value[0] & 1) {
3385                    return false;
3386                }
3387        }
3388
3389        static $primes, $zero, $one, $two;
3390
3391        if (!isset($primes)) {
3392            $primes = array(
3393                3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,   41,   43,   47,   53,   59,
3394                61,   67,   71,   73,   79,   83,   89,   97,   101,  103,  107,  109,  113,  127,  131,  137,
3395                139,  149,  151,  157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,  227,
3396                229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  283,  293,  307,  311,  313,
3397                317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,  397,  401,  409,  419,
3398                421,  431,  433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,  509,
3399                521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,  599,  601,  607,  613,  617,
3400                619,  631,  641,  643,  647,  653,  659,  661,  673,  677,  683,  691,  701,  709,  719,  727,
3401                733,  739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,  829,
3402                839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,  919,  929,  937,  941,  947,
3403                953,  967,  971,  977,  983,  991,  997
3404            );
3405
3406            if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
3407                for ($i = 0; $i < count($primes); ++$i) {
3408                    $primes[$i] = new static($primes[$i]);
3409                }
3410            }
3411
3412            $zero = new static();
3413            $one = new static(1);
3414            $two = new static(2);
3415        }
3416
3417        if ($this->equals($one)) {
3418            return false;
3419        }
3420
3421        // see HAC 4.4.1 "Random search for probable primes"
3422        if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
3423            foreach ($primes as $prime) {
3424                list(, $r) = $this->divide($prime);
3425                if ($r->equals($zero)) {
3426                    return $this->equals($prime);
3427                }
3428            }
3429        } else {
3430            $value = $this->value;
3431            foreach ($primes as $prime) {
3432                list(, $r) = $this->_divide_digit($value, $prime);
3433                if (!$r) {
3434                    return count($value) == 1 && $value[0] == $prime;
3435                }
3436            }
3437        }
3438
3439        $n   = $this->copy();
3440        $n_1 = $n->subtract($one);
3441        $n_2 = $n->subtract($two);
3442
3443        $r = $n_1->copy();
3444        $r_value = $r->value;
3445        // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
3446        if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
3447            $s = 0;
3448            // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
3449            while ($r->value[strlen($r->value) - 1] % 2 == 0) {
3450                $r->value = bcdiv($r->value, '2', 0);
3451                ++$s;
3452            }
3453        } else {
3454            for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
3455                $temp = ~$r_value[$i] & 0xFFFFFF;
3456                for ($j = 1; ($temp >> $j) & 1; ++$j) {
3457                }
3458                if ($j != 25) {
3459                    break;
3460                }
3461            }
3462            $s = 26 * $i + $j;
3463            $r->_rshift($s);
3464        }
3465
3466        for ($i = 0; $i < $t; ++$i) {
3467            $a = $this->random($two, $n_2);
3468            $y = $a->modPow($r, $n);
3469
3470            if (!$y->equals($one) && !$y->equals($n_1)) {
3471                for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
3472                    $y = $y->modPow($two, $n);
3473                    if ($y->equals($one)) {
3474                        return false;
3475                    }
3476                }
3477
3478                if (!$y->equals($n_1)) {
3479                    return false;
3480                }
3481            }
3482        }
3483        return true;
3484    }
3485
3486    /**
3487     * Logical Left Shift
3488     *
3489     * Shifts BigInteger's by $shift bits.
3490     *
3491     * @param int $shift
3492     * @access private
3493     */
3494    function _lshift($shift)
3495    {
3496        if ($shift == 0) {
3497            return;
3498        }
3499
3500        $num_digits = (int) ($shift / self::$base);
3501        $shift %= self::$base;
3502        $shift = 1 << $shift;
3503
3504        $carry = 0;
3505
3506        for ($i = 0; $i < count($this->value); ++$i) {
3507            $temp = $this->value[$i] * $shift + $carry;
3508            $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
3509            $this->value[$i] = (int) ($temp - $carry * self::$baseFull);
3510        }
3511
3512        if ($carry) {
3513            $this->value[count($this->value)] = $carry;
3514        }
3515
3516        while ($num_digits--) {
3517            array_unshift($this->value, 0);
3518        }
3519    }
3520
3521    /**
3522     * Logical Right Shift
3523     *
3524     * Shifts BigInteger's by $shift bits.
3525     *
3526     * @param int $shift
3527     * @access private
3528     */
3529    function _rshift($shift)
3530    {
3531        if ($shift == 0) {
3532            return;
3533        }
3534
3535        $num_digits = (int) ($shift / self::$base);
3536        $shift %= self::$base;
3537        $carry_shift = self::$base - $shift;
3538        $carry_mask = (1 << $shift) - 1;
3539
3540        if ($num_digits) {
3541            $this->value = array_slice($this->value, $num_digits);
3542        }
3543
3544        $carry = 0;
3545
3546        for ($i = count($this->value) - 1; $i >= 0; --$i) {
3547            $temp = $this->value[$i] >> $shift | $carry;
3548            $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
3549            $this->value[$i] = $temp;
3550        }
3551
3552        $this->value = $this->_trim($this->value);
3553    }
3554
3555    /**
3556     * Normalize
3557     *
3558     * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
3559     *
3560     * @param \phpseclib\Math\BigInteger $result
3561     * @return \phpseclib\Math\BigInteger
3562     * @see self::_trim()
3563     * @access private
3564     */
3565    function _normalize($result)
3566    {
3567        $result->precision = $this->precision;
3568        $result->bitmask = $this->bitmask;
3569
3570        switch (MATH_BIGINTEGER_MODE) {
3571            case self::MODE_GMP:
3572                if ($this->bitmask !== false) {
3573                    $flip = gmp_cmp($result->value, gmp_init(0)) < 0;
3574                    if ($flip) {
3575                        $result->value = gmp_neg($result->value);
3576                    }
3577                    $result->value = gmp_and($result->value, $result->bitmask->value);
3578                    if ($flip) {
3579                        $result->value = gmp_neg($result->value);
3580                    }
3581                }
3582
3583                return $result;
3584            case self::MODE_BCMATH:
3585                if (!empty($result->bitmask->value)) {
3586                    $result->value = bcmod($result->value, $result->bitmask->value);
3587                }
3588
3589                return $result;
3590        }
3591
3592        $value = &$result->value;
3593
3594        if (!count($value)) {
3595            $result->is_negative = false;
3596            return $result;
3597        }
3598
3599        $value = $this->_trim($value);
3600
3601        if (!empty($result->bitmask->value)) {
3602            $length = min(count($value), count($this->bitmask->value));
3603            $value = array_slice($value, 0, $length);
3604
3605            for ($i = 0; $i < $length; ++$i) {
3606                $value[$i] = $value[$i] & $this->bitmask->value[$i];
3607            }
3608        }
3609
3610        return $result;
3611    }
3612
3613    /**
3614     * Trim
3615     *
3616     * Removes leading zeros
3617     *
3618     * @param array $value
3619     * @return \phpseclib\Math\BigInteger
3620     * @access private
3621     */
3622    function _trim($value)
3623    {
3624        for ($i = count($value) - 1; $i >= 0; --$i) {
3625            if ($value[$i]) {
3626                break;
3627            }
3628            unset($value[$i]);
3629        }
3630
3631        return $value;
3632    }
3633
3634    /**
3635     * Array Repeat
3636     *
3637     * @param array $input
3638     * @param mixed $multiplier
3639     * @return array
3640     * @access private
3641     */
3642    function _array_repeat($input, $multiplier)
3643    {
3644        return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
3645    }
3646
3647    /**
3648     * Logical Left Shift
3649     *
3650     * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
3651     *
3652     * @param string $x (by reference)
3653     * @param int $shift
3654     * @return string
3655     * @access private
3656     */
3657    function _base256_lshift(&$x, $shift)
3658    {
3659        if ($shift == 0) {
3660            return;
3661        }
3662
3663        $num_bytes = $shift >> 3; // eg. floor($shift/8)
3664        $shift &= 7; // eg. $shift % 8
3665
3666        $carry = 0;
3667        for ($i = strlen($x) - 1; $i >= 0; --$i) {
3668            $temp = ord($x[$i]) << $shift | $carry;
3669            $x[$i] = chr($temp);
3670            $carry = $temp >> 8;
3671        }
3672        $carry = ($carry != 0) ? chr($carry) : '';
3673        $x = $carry . $x . str_repeat(chr(0), $num_bytes);
3674    }
3675
3676    /**
3677     * Logical Right Shift
3678     *
3679     * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
3680     *
3681     * @param string $x (by referenc)
3682     * @param int $shift
3683     * @return string
3684     * @access private
3685     */
3686    function _base256_rshift(&$x, $shift)
3687    {
3688        if ($shift == 0) {
3689            $x = ltrim($x, chr(0));
3690            return '';
3691        }
3692
3693        $num_bytes = $shift >> 3; // eg. floor($shift/8)
3694        $shift &= 7; // eg. $shift % 8
3695
3696        $remainder = '';
3697        if ($num_bytes) {
3698            $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
3699            $remainder = substr($x, $start);
3700            $x = substr($x, 0, -$num_bytes);
3701        }
3702
3703        $carry = 0;
3704        $carry_shift = 8 - $shift;
3705        for ($i = 0; $i < strlen($x); ++$i) {
3706            $temp = (ord($x[$i]) >> $shift) | $carry;
3707            $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
3708            $x[$i] = chr($temp);
3709        }
3710        $x = ltrim($x, chr(0));
3711
3712        $remainder = chr($carry >> $carry_shift) . $remainder;
3713
3714        return ltrim($remainder, chr(0));
3715    }
3716
3717    // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
3718    // at 32-bits, while java's longs are 64-bits.
3719
3720    /**
3721     * Converts 32-bit integers to bytes.
3722     *
3723     * @param int $x
3724     * @return string
3725     * @access private
3726     */
3727    function _int2bytes($x)
3728    {
3729        return ltrim(pack('N', $x), chr(0));
3730    }
3731
3732    /**
3733     * Converts bytes to 32-bit integers
3734     *
3735     * @param string $x
3736     * @return int
3737     * @access private
3738     */
3739    function _bytes2int($x)
3740    {
3741        $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
3742        return $temp['int'];
3743    }
3744
3745    /**
3746     * DER-encode an integer
3747     *
3748     * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL
3749     *
3750     * @see self::modPow()
3751     * @access private
3752     * @param int $length
3753     * @return string
3754     */
3755    function _encodeASN1Length($length)
3756    {
3757        if ($length <= 0x7F) {
3758            return chr($length);
3759        }
3760
3761        $temp = ltrim(pack('N', $length), chr(0));
3762        return pack('Ca*', 0x80 | strlen($temp), $temp);
3763    }
3764
3765    /**
3766     * Single digit division
3767     *
3768     * Even if int64 is being used the division operator will return a float64 value
3769     * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't
3770     * have the precision of int64 this is a problem so, when int64 is being used,
3771     * we'll guarantee that the dividend is divisible by first subtracting the remainder.
3772     *
3773     * @access private
3774     * @param int $x
3775     * @param int $y
3776     * @return int
3777     */
3778    function _safe_divide($x, $y)
3779    {
3780        if (self::$base === 26) {
3781            return (int) ($x / $y);
3782        }
3783
3784        // self::$base === 31
3785        return ($x - ($x % $y)) / $y;
3786    }
3787}
3788