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 and 7
10 *
11 * Here's an example of how to use this library:
12 * <code>
13 * <?php
14 *    $a = new \phpseclib3\Math\BigInteger(2);
15 *    $b = new \phpseclib3\Math\BigInteger(3);
16 *
17 *    $c = $a->add($b);
18 *
19 *    echo $c->toString(); // outputs 5
20 * ?>
21 * </code>
22 *
23 * @author    Jim Wigginton <terrafrost@php.net>
24 * @copyright 2017 Jim Wigginton
25 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
26 */
27
28namespace phpseclib3\Math;
29
30use phpseclib3\Exception\BadConfigurationException;
31use phpseclib3\Math\BigInteger\Engines\Engine;
32
33/**
34 * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
35 * numbers.
36 *
37 * @author  Jim Wigginton <terrafrost@php.net>
38 */
39class BigInteger implements \JsonSerializable
40{
41    /**
42     * Main Engine
43     *
44     * @var class-string<Engine>
45     */
46    private static $mainEngine;
47
48    /**
49     * Selected Engines
50     *
51     * @var list<string>
52     */
53    private static $engines;
54
55    /**
56     * The actual BigInteger object
57     *
58     * @var object
59     */
60    private $value;
61
62    /**
63     * Mode independent value used for serialization.
64     *
65     * @see self::__sleep()
66     * @see self::__wakeup()
67     * @var string
68     */
69    private $hex;
70
71    /**
72     * Precision (used only for serialization)
73     *
74     * @see self::__sleep()
75     * @see self::__wakeup()
76     * @var int
77     */
78    private $precision;
79
80    /**
81     * Sets engine type.
82     *
83     * Throws an exception if the type is invalid
84     *
85     * @param string $main
86     * @param list<string> $modexps optional
87     * @return void
88     */
89    public static function setEngine($main, array $modexps = ['DefaultEngine'])
90    {
91        self::$engines = [];
92
93        $fqmain = 'phpseclib3\\Math\\BigInteger\\Engines\\' . $main;
94        if (!class_exists($fqmain) || !method_exists($fqmain, 'isValidEngine')) {
95            throw new \InvalidArgumentException("$main is not a valid engine");
96        }
97        if (!$fqmain::isValidEngine()) {
98            throw new BadConfigurationException("$main is not setup correctly on this system");
99        }
100        /** @var class-string<Engine> $fqmain */
101        self::$mainEngine = $fqmain;
102
103        $found = false;
104        foreach ($modexps as $modexp) {
105            try {
106                $fqmain::setModExpEngine($modexp);
107                $found = true;
108                break;
109            } catch (\Exception $e) {
110            }
111        }
112
113        if (!$found) {
114            throw new BadConfigurationException("No valid modular exponentiation engine found for $main");
115        }
116
117        self::$engines = [$main, $modexp];
118    }
119
120    /**
121     * Returns the engine type
122     *
123     * @return string[]
124     */
125    public static function getEngine()
126    {
127        self::initialize_static_variables();
128
129        return self::$engines;
130    }
131
132    /**
133     * Initialize static variables
134     */
135    private static function initialize_static_variables()
136    {
137        if (!isset(self::$mainEngine)) {
138            $engines = [
139                ['GMP', ['DefaultEngine']],
140                ['PHP64', ['OpenSSL']],
141                ['BCMath', ['OpenSSL']],
142                ['PHP32', ['OpenSSL']],
143                ['PHP64', ['DefaultEngine']],
144                ['PHP32', ['DefaultEngine']]
145            ];
146
147            foreach ($engines as $engine) {
148                try {
149                    self::setEngine($engine[0], $engine[1]);
150                    return;
151                } catch (\Exception $e) {
152                }
153            }
154
155            throw new \UnexpectedValueException('No valid BigInteger found. This is only possible when JIT is enabled on Windows and neither the GMP or BCMath extensions are available so either disable JIT or install GMP / BCMath');
156        }
157    }
158
159    /**
160     * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
161     *
162     * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
163     * two's compliment.  The sole exception to this is -10, which is treated the same as 10 is.
164     *
165     * @param string|int|Engine $x Base-10 number or base-$base number if $base set.
166     * @param int $base
167     */
168    public function __construct($x = 0, $base = 10)
169    {
170        self::initialize_static_variables();
171
172        if ($x instanceof self::$mainEngine) {
173            $this->value = clone $x;
174        } elseif ($x instanceof Engine) {
175            $this->value = new static("$x");
176            $this->value->setPrecision($x->getPrecision());
177        } else {
178            $this->value = new self::$mainEngine($x, $base);
179        }
180    }
181
182    /**
183     * Converts a BigInteger to a base-10 number.
184     *
185     * @return string
186     */
187    public function toString()
188    {
189        return $this->value->toString();
190    }
191
192    /**
193     *  __toString() magic method
194     */
195    public function __toString()
196    {
197        return (string)$this->value;
198    }
199
200    /**
201     *  __debugInfo() magic method
202     *
203     * Will be called, automatically, when print_r() or var_dump() are called
204     */
205    public function __debugInfo()
206    {
207        return $this->value->__debugInfo();
208    }
209
210    /**
211     * Converts a BigInteger to a byte string (eg. base-256).
212     *
213     * @param bool $twos_compliment
214     * @return string
215     */
216    public function toBytes($twos_compliment = false)
217    {
218        return $this->value->toBytes($twos_compliment);
219    }
220
221    /**
222     * Converts a BigInteger to a hex string (eg. base-16).
223     *
224     * @param bool $twos_compliment
225     * @return string
226     */
227    public function toHex($twos_compliment = false)
228    {
229        return $this->value->toHex($twos_compliment);
230    }
231
232    /**
233     * Converts a BigInteger to a bit string (eg. base-2).
234     *
235     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
236     * saved as two's compliment.
237     *
238     * @param bool $twos_compliment
239     * @return string
240     */
241    public function toBits($twos_compliment = false)
242    {
243        return $this->value->toBits($twos_compliment);
244    }
245
246    /**
247     * Adds two BigIntegers.
248     *
249     * @param BigInteger $y
250     * @return BigInteger
251     */
252    public function add(BigInteger $y)
253    {
254        return new static($this->value->add($y->value));
255    }
256
257    /**
258     * Subtracts two BigIntegers.
259     *
260     * @param BigInteger $y
261     * @return BigInteger
262     */
263    public function subtract(BigInteger $y)
264    {
265        return new static($this->value->subtract($y->value));
266    }
267
268    /**
269     * Multiplies two BigIntegers
270     *
271     * @param BigInteger $x
272     * @return BigInteger
273     */
274    public function multiply(BigInteger $x)
275    {
276        return new static($this->value->multiply($x->value));
277    }
278
279    /**
280     * Divides two BigIntegers.
281     *
282     * Returns an array whose first element contains the quotient and whose second element contains the
283     * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
284     * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
285     * and the divisor (basically, the "common residue" is the first positive modulo).
286     *
287     * Here's an example:
288     * <code>
289     * <?php
290     *    $a = new \phpseclib3\Math\BigInteger('10');
291     *    $b = new \phpseclib3\Math\BigInteger('20');
292     *
293     *    list($quotient, $remainder) = $a->divide($b);
294     *
295     *    echo $quotient->toString(); // outputs 0
296     *    echo "\r\n";
297     *    echo $remainder->toString(); // outputs 10
298     * ?>
299     * </code>
300     *
301     * @param BigInteger $y
302     * @return BigInteger[]
303     */
304    public function divide(BigInteger $y)
305    {
306        list($q, $r) = $this->value->divide($y->value);
307        return [
308            new static($q),
309            new static($r)
310        ];
311    }
312
313    /**
314     * Calculates modular inverses.
315     *
316     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
317     *
318     * @param BigInteger $n
319     * @return BigInteger
320     */
321    public function modInverse(BigInteger $n)
322    {
323        return new static($this->value->modInverse($n->value));
324    }
325
326    /**
327     * Calculates modular inverses.
328     *
329     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
330     *
331     * @param BigInteger $n
332     * @return BigInteger[]
333     */
334    public function extendedGCD(BigInteger $n)
335    {
336        extract($this->value->extendedGCD($n->value));
337        /**
338         * @var BigInteger $gcd
339         * @var BigInteger $x
340         * @var BigInteger $y
341         */
342        return [
343            'gcd' => new static($gcd),
344            'x' => new static($x),
345            'y' => new static($y)
346        ];
347    }
348
349    /**
350     * Calculates the greatest common divisor
351     *
352     * Say you have 693 and 609.  The GCD is 21.
353     *
354     * @param BigInteger $n
355     * @return BigInteger
356     */
357    public function gcd(BigInteger $n)
358    {
359        return new static($this->value->gcd($n->value));
360    }
361
362    /**
363     * Absolute value.
364     *
365     * @return BigInteger
366     */
367    public function abs()
368    {
369        return new static($this->value->abs());
370    }
371
372    /**
373     * Set Precision
374     *
375     * Some bitwise operations give different results depending on the precision being used.  Examples include left
376     * shift, not, and rotates.
377     *
378     * @param int $bits
379     */
380    public function setPrecision($bits)
381    {
382        $this->value->setPrecision($bits);
383    }
384
385    /**
386     * Get Precision
387     *
388     * Returns the precision if it exists, false if it doesn't
389     *
390     * @return int|bool
391     */
392    public function getPrecision()
393    {
394        return $this->value->getPrecision();
395    }
396
397    /**
398     * Serialize
399     *
400     * Will be called, automatically, when serialize() is called on a BigInteger object.
401     *
402     * __sleep() / __wakeup() have been around since PHP 4.0
403     *
404     * \Serializable was introduced in PHP 5.1 and deprecated in PHP 8.1:
405     * https://wiki.php.net/rfc/phase_out_serializable
406     *
407     * __serialize() / __unserialize() were introduced in PHP 7.4:
408     * https://wiki.php.net/rfc/custom_object_serialization
409     *
410     * @return array
411     */
412    public function __sleep()
413    {
414        $this->hex = $this->toHex(true);
415        $vars = ['hex'];
416        if ($this->getPrecision() > 0) {
417            $vars[] = 'precision';
418        }
419        return $vars;
420    }
421
422    /**
423     * Serialize
424     *
425     * Will be called, automatically, when unserialize() is called on a BigInteger object.
426     */
427    public function __wakeup()
428    {
429        $temp = new static($this->hex, -16);
430        $this->value = $temp->value;
431        if ($this->precision > 0) {
432            // recalculate $this->bitmask
433            $this->setPrecision($this->precision);
434        }
435    }
436
437    /**
438     * JSON Serialize
439     *
440     * Will be called, automatically, when json_encode() is called on a BigInteger object.
441     *
442     * @return array{hex: string, precision?: int]
443     */
444    #[\ReturnTypeWillChange]
445    public function jsonSerialize()
446    {
447        $result = ['hex' => $this->toHex(true)];
448        if ($this->precision > 0) {
449            $result['precision'] = $this->getPrecision();
450        }
451        return $result;
452    }
453
454    /**
455     * Performs modular exponentiation.
456     *
457     * @param BigInteger $e
458     * @param BigInteger $n
459     * @return BigInteger
460     */
461    public function powMod(BigInteger $e, BigInteger $n)
462    {
463        return new static($this->value->powMod($e->value, $n->value));
464    }
465
466    /**
467     * Performs modular exponentiation.
468     *
469     * @param BigInteger $e
470     * @param BigInteger $n
471     * @return BigInteger
472     */
473    public function modPow(BigInteger $e, BigInteger $n)
474    {
475        return new static($this->value->modPow($e->value, $n->value));
476    }
477
478    /**
479     * Compares two numbers.
480     *
481     * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this
482     * is demonstrated thusly:
483     *
484     * $x  > $y: $x->compare($y)  > 0
485     * $x  < $y: $x->compare($y)  < 0
486     * $x == $y: $x->compare($y) == 0
487     *
488     * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
489     *
490     * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.}
491     *
492     * @param BigInteger $y
493     * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
494     * @see self::equals()
495     */
496    public function compare(BigInteger $y)
497    {
498        return $this->value->compare($y->value);
499    }
500
501    /**
502     * Tests the equality of two numbers.
503     *
504     * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
505     *
506     * @param BigInteger $x
507     * @return bool
508     */
509    public function equals(BigInteger $x)
510    {
511        return $this->value->equals($x->value);
512    }
513
514    /**
515     * Logical Not
516     *
517     * @return BigInteger
518     */
519    public function bitwise_not()
520    {
521        return new static($this->value->bitwise_not());
522    }
523
524    /**
525     * Logical And
526     *
527     * @param BigInteger $x
528     * @return BigInteger
529     */
530    public function bitwise_and(BigInteger $x)
531    {
532        return new static($this->value->bitwise_and($x->value));
533    }
534
535    /**
536     * Logical Or
537     *
538     * @param BigInteger $x
539     * @return BigInteger
540     */
541    public function bitwise_or(BigInteger $x)
542    {
543        return new static($this->value->bitwise_or($x->value));
544    }
545
546    /**
547     * Logical Exclusive Or
548     *
549     * @param BigInteger $x
550     * @return BigInteger
551     */
552    public function bitwise_xor(BigInteger $x)
553    {
554        return new static($this->value->bitwise_xor($x->value));
555    }
556
557    /**
558     * Logical Right Shift
559     *
560     * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
561     *
562     * @param int $shift
563     * @return BigInteger
564     */
565    public function bitwise_rightShift($shift)
566    {
567        return new static($this->value->bitwise_rightShift($shift));
568    }
569
570    /**
571     * Logical Left Shift
572     *
573     * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
574     *
575     * @param int $shift
576     * @return BigInteger
577     */
578    public function bitwise_leftShift($shift)
579    {
580        return new static($this->value->bitwise_leftShift($shift));
581    }
582
583    /**
584     * Logical Left Rotate
585     *
586     * Instead of the top x bits being dropped they're appended to the shifted bit string.
587     *
588     * @param int $shift
589     * @return BigInteger
590     */
591    public function bitwise_leftRotate($shift)
592    {
593        return new static($this->value->bitwise_leftRotate($shift));
594    }
595
596    /**
597     * Logical Right Rotate
598     *
599     * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
600     *
601     * @param int $shift
602     * @return BigInteger
603     */
604    public function bitwise_rightRotate($shift)
605    {
606        return new static($this->value->bitwise_rightRotate($shift));
607    }
608
609    /**
610     * Returns the smallest and largest n-bit number
611     *
612     * @param int $bits
613     * @return BigInteger[]
614     */
615    public static function minMaxBits($bits)
616    {
617        self::initialize_static_variables();
618
619        $class = self::$mainEngine;
620        extract($class::minMaxBits($bits));
621        /** @var BigInteger $min
622         * @var BigInteger $max
623         */
624        return [
625            'min' => new static($min),
626            'max' => new static($max)
627        ];
628    }
629
630    /**
631     * Return the size of a BigInteger in bits
632     *
633     * @return int
634     */
635    public function getLength()
636    {
637        return $this->value->getLength();
638    }
639
640    /**
641     * Return the size of a BigInteger in bytes
642     *
643     * @return int
644     */
645    public function getLengthInBytes()
646    {
647        return $this->value->getLengthInBytes();
648    }
649
650    /**
651     * Generates a random number of a certain size
652     *
653     * Bit length is equal to $size
654     *
655     * @param int $size
656     * @return BigInteger
657     */
658    public static function random($size)
659    {
660        self::initialize_static_variables();
661
662        $class = self::$mainEngine;
663        return new static($class::random($size));
664    }
665
666    /**
667     * Generates a random prime number of a certain size
668     *
669     * Bit length is equal to $size
670     *
671     * @param int $size
672     * @return BigInteger
673     */
674    public static function randomPrime($size)
675    {
676        self::initialize_static_variables();
677
678        $class = self::$mainEngine;
679        return new static($class::randomPrime($size));
680    }
681
682    /**
683     * Generate a random prime number between a range
684     *
685     * If there's not a prime within the given range, false will be returned.
686     *
687     * @param BigInteger $min
688     * @param BigInteger $max
689     * @return false|BigInteger
690     */
691    public static function randomRangePrime(BigInteger $min, BigInteger $max)
692    {
693        $class = self::$mainEngine;
694        return new static($class::randomRangePrime($min->value, $max->value));
695    }
696
697    /**
698     * Generate a random number between a range
699     *
700     * Returns a random number between $min and $max where $min and $max
701     * can be defined using one of the two methods:
702     *
703     * BigInteger::randomRange($min, $max)
704     * BigInteger::randomRange($max, $min)
705     *
706     * @param BigInteger $min
707     * @param BigInteger $max
708     * @return BigInteger
709     */
710    public static function randomRange(BigInteger $min, BigInteger $max)
711    {
712        $class = self::$mainEngine;
713        return new static($class::randomRange($min->value, $max->value));
714    }
715
716    /**
717     * Checks a numer to see if it's prime
718     *
719     * Assuming the $t parameter is not set, this function has an error rate of 2**-80.  The main motivation for the
720     * $t parameter is distributability.  BigInteger::randomPrime() can be distributed across multiple pageloads
721     * on a website instead of just one.
722     *
723     * @param int|bool $t
724     * @return bool
725     */
726    public function isPrime($t = false)
727    {
728        return $this->value->isPrime($t);
729    }
730
731    /**
732     * Calculates the nth root of a biginteger.
733     *
734     * Returns the nth root of a positive biginteger, where n defaults to 2
735     *
736     * @param int $n optional
737     * @return BigInteger
738     */
739    public function root($n = 2)
740    {
741        return new static($this->value->root($n));
742    }
743
744    /**
745     * Performs exponentiation.
746     *
747     * @param BigInteger $n
748     * @return BigInteger
749     */
750    public function pow(BigInteger $n)
751    {
752        return new static($this->value->pow($n->value));
753    }
754
755    /**
756     * Return the minimum BigInteger between an arbitrary number of BigIntegers.
757     *
758     * @param BigInteger ...$nums
759     * @return BigInteger
760     */
761    public static function min(BigInteger ...$nums)
762    {
763        $class = self::$mainEngine;
764        $nums = array_map(function ($num) {
765            return $num->value;
766        }, $nums);
767        return new static($class::min(...$nums));
768    }
769
770    /**
771     * Return the maximum BigInteger between an arbitrary number of BigIntegers.
772     *
773     * @param BigInteger ...$nums
774     * @return BigInteger
775     */
776    public static function max(BigInteger ...$nums)
777    {
778        $class = self::$mainEngine;
779        $nums = array_map(function ($num) {
780            return $num->value;
781        }, $nums);
782        return new static($class::max(...$nums));
783    }
784
785    /**
786     * Tests BigInteger to see if it is between two integers, inclusive
787     *
788     * @param BigInteger $min
789     * @param BigInteger $max
790     * @return bool
791     */
792    public function between(BigInteger $min, BigInteger $max)
793    {
794        return $this->value->between($min->value, $max->value);
795    }
796
797    /**
798     * Clone
799     */
800    public function __clone()
801    {
802        $this->value = clone $this->value;
803    }
804
805    /**
806     * Is Odd?
807     *
808     * @return bool
809     */
810    public function isOdd()
811    {
812        return $this->value->isOdd();
813    }
814
815    /**
816     * Tests if a bit is set
817     *
818     * @param int $x
819     * @return bool
820     */
821    public function testBit($x)
822    {
823        return $this->value->testBit($x);
824    }
825
826    /**
827     * Is Negative?
828     *
829     * @return bool
830     */
831    public function isNegative()
832    {
833        return $this->value->isNegative();
834    }
835
836    /**
837     * Negate
838     *
839     * Given $k, returns -$k
840     *
841     * @return BigInteger
842     */
843    public function negate()
844    {
845        return new static($this->value->negate());
846    }
847
848    /**
849     * Scan for 1 and right shift by that amount
850     *
851     * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
852     *
853     * @param BigInteger $r
854     * @return int
855     */
856    public static function scan1divide(BigInteger $r)
857    {
858        $class = self::$mainEngine;
859        return $class::scan1divide($r->value);
860    }
861
862    /**
863     * Create Recurring Modulo Function
864     *
865     * Sometimes it may be desirable to do repeated modulos with the same number outside of
866     * modular exponentiation
867     *
868     * @return callable
869     */
870    public function createRecurringModuloFunction()
871    {
872        $func = $this->value->createRecurringModuloFunction();
873        return function (BigInteger $x) use ($func) {
874            return new static($func($x->value));
875        };
876    }
877
878    /**
879     * Bitwise Split
880     *
881     * Splits BigInteger's into chunks of $split bits
882     *
883     * @param int $split
884     * @return BigInteger[]
885     */
886    public function bitwise_split($split)
887    {
888        return array_map(function ($val) {
889            return new static($val);
890        }, $this->value->bitwise_split($split));
891    }
892}
893