254        if (!defined(
'MATH_BIGINTEGER_MODE')) {
 
  256                case extension_loaded(
'gmp'):
 
  257                    define(
'MATH_BIGINTEGER_MODE', self::MODE_GMP);
 
  259                case extension_loaded(
'bcmath'):
 
  260                    define(
'MATH_BIGINTEGER_MODE', self::MODE_BCMATH);
 
  263                    define(
'MATH_BIGINTEGER_MODE', self::MODE_INTERNAL);
 
  267        if (extension_loaded(
'openssl') && !defined(
'MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined(
'MATH_BIGINTEGER_OPENSSL_ENABLED')) {
 
  271            $content = ob_get_contents();
 
  274            preg_match_all(
'#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
 
  277            if (!empty($matches[1])) {
 
  278                for (
$i = 0; 
$i < count($matches[1]); 
$i++) {
 
  279                    $fullVersion = trim(str_replace(
'=>', 
'', strip_tags($matches[2][
$i])));
 
  282                    if (!preg_match(
'/(\d+\.\d+\.\d+)/i', $fullVersion, 
$m)) {
 
  283                        $versions[$matches[1][
$i]] = $fullVersion;
 
  285                        $versions[$matches[1][
$i]] = 
$m[0];
 
  292                case !isset($versions[
'Header']):
 
  293                case !isset($versions[
'Library']):
 
  294                case $versions[
'Header'] == $versions[
'Library']:
 
  295                    define(
'MATH_BIGINTEGER_OPENSSL_ENABLED', 
true);
 
  298                    define(
'MATH_BIGINTEGER_OPENSSL_DISABLE', 
true);
 
  302        if (!defined(
'PHP_INT_SIZE')) {
 
  303            define(
'PHP_INT_SIZE', 4);
 
  306        if (empty(
self::$base) && MATH_BIGINTEGER_MODE == self::MODE_INTERNAL) {
 
  307            switch (PHP_INT_SIZE) {
 
  310                    self::$baseFull  = 0x80000000;
 
  311                    self::$maxDigit  = 0x7FFFFFFF;
 
  312                    self::$msb       = 0x40000000;
 
  313                    self::$max10     = 1000000000;
 
  315                    self::$maxDigit2 = pow(2, 62);
 
  320                    self::$baseFull  = 0x4000000;
 
  321                    self::$maxDigit  = 0x3FFFFFF;
 
  322                    self::$msb       = 0x2000000;
 
  323                    self::$max10     = 10000000;
 
  325                    self::$maxDigit2 = pow(2, 52); 
 
  329        switch (MATH_BIGINTEGER_MODE) {
 
  332                    case is_resource(
$x) && get_resource_type(
$x) == 
'GMP integer':
 
  334                    case $x instanceof \GMP:
 
  338                $this->value = gmp_init(0);
 
  344                $this->value = array();
 
  355                if (ord(
$x[0]) & 0x80) {
 
  357                    $this->is_negative = 
true;
 
  360                switch (MATH_BIGINTEGER_MODE) {
 
  362                        $sign = $this->is_negative ? 
'-' : 
'';
 
  363                        $this->value = gmp_init($sign . 
'0x' . bin2hex(
$x));
 
  367                        $len = (strlen(
$x) + 3) & 0xFFFFFFFC;
 
  369                        $x = str_pad(
$x, $len, chr(0), STR_PAD_LEFT);
 
  371                        for (
$i = 0; 
$i < $len; 
$i+= 4) {
 
  372                            $this->value = bcmul($this->value, 
'4294967296', 0); 
 
  373                            $this->value = bcadd($this->value, 0x1000000 * ord(
$x[
$i]) + ((ord(
$x[
$i + 1]) << 16) | (ord(
$x[
$i + 2]) << 8) | ord(
$x[
$i + 3])), 0);
 
  376                        if ($this->is_negative) {
 
  388                if ($this->is_negative) {
 
  389                    if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
 
  390                        $this->is_negative = 
false;
 
  392                    $temp = $this->
add(
new static(
'-1'));
 
  393                    $this->value = $temp->value;
 
  398                if (
$base > 0 && 
$x[0] == 
'-') {
 
  399                    $this->is_negative = 
true;
 
  403                $x = preg_replace(
'#^(?:0x)?([A-Fa-f0-9]*).*#', 
'$1', 
$x);
 
  406                if (
$base < 0 && hexdec(
$x[0]) >= 8) {
 
  408                    $x = bin2hex(~pack(
'H*', 
$x));
 
  411                switch (MATH_BIGINTEGER_MODE) {
 
  413                        $temp = $this->is_negative ? 
'-0x' . 
$x : 
'0x' . 
$x;
 
  414                        $this->value = gmp_init($temp);
 
  415                        $this->is_negative = 
false;
 
  418                        $x = (strlen(
$x) & 1) ? 
'0' . 
$x : 
$x;
 
  419                        $temp = 
new static(pack(
'H*', 
$x), 256);
 
  420                        $this->value = $this->is_negative ? 
'-' . $temp->value : $temp->value;
 
  421                        $this->is_negative = 
false;
 
  424                        $x = (strlen(
$x) & 1) ? 
'0' . 
$x : 
$x;
 
  425                        $temp = 
new static(pack(
'H*', 
$x), 256);
 
  426                        $this->value = $temp->value;
 
  430                    $temp = $this->
add(
new static(
'-1'));
 
  431                    $this->value = $temp->value;
 
  439                $x = preg_replace(
'#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', 
'', 
$x);
 
  441                switch (MATH_BIGINTEGER_MODE) {
 
  443                        $this->value = gmp_init(
$x);
 
  448                        $this->value = 
$x === 
'-' ? 
'0' : (string) 
$x;
 
  451                        $temp = 
new static();
 
  453                        $multiplier = 
new static();
 
  454                        $multiplier->value = array(self::$max10);
 
  457                            $this->is_negative = 
true;
 
  461                        $x = str_pad(
$x, strlen(
$x) + ((self::$max10Len - 1) * strlen(
$x)) % self::$max10Len, 0, STR_PAD_LEFT);
 
  463                            $temp = $temp->multiply($multiplier);
 
  464                            $temp = $temp->add(
new static($this->
_int2bytes(substr(
$x, 0, self::$max10Len)), 256));
 
  465                            $x = substr(
$x, self::$max10Len);
 
  468                        $this->value = $temp->value;
 
  473                if (
$base > 0 && 
$x[0] == 
'-') {
 
  474                    $this->is_negative = 
true;
 
  478                $x = preg_replace(
'#^([01]*).*#', 
'$1', 
$x);
 
  479                $x = str_pad(
$x, strlen(
$x) + (3 * strlen(
$x)) % 4, 0, STR_PAD_LEFT);
 
  483                    $part = substr(
$x, 0, 4);
 
  484                    $str.= dechex(bindec($part));
 
  488                if ($this->is_negative) {
 
  492                $temp = 
new static($str, 8 * 
$base); 
 
  493                $this->value = $temp->value;
 
  494                $this->is_negative = $temp->is_negative;
 
  524        if ($twos_compliment) {
 
  525            $comparison = $this->
compare(
new static());
 
  526            if ($comparison == 0) {
 
  527                return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : 
'';
 
  530            $temp = $comparison < 0 ? $this->
add(
new static(1)) : $this->
copy();
 
  531            $bytes = $temp->toBytes();
 
  537            if (ord($bytes[0]) & 0x80) {
 
  538                $bytes = chr(0) . $bytes;
 
  541            return $comparison < 0 ? ~$bytes : $bytes;
 
  544        switch (MATH_BIGINTEGER_MODE) {
 
  546                if (gmp_cmp($this->value, gmp_init(0)) == 0) {
 
  547                    return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : 
'';
 
  550                $temp = gmp_strval(gmp_abs($this->value), 16);
 
  551                $temp = (strlen($temp) & 1) ? 
'0' . $temp : $temp;
 
  552                $temp = pack(
'H*', $temp);
 
  554                return $this->precision > 0 ?
 
  555                    substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
 
  556                    ltrim($temp, chr(0));
 
  558                if ($this->value === 
'0') {
 
  559                    return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : 
'';
 
  569                while (bccomp(
$current, 
'0', 0) > 0) {
 
  570                    $temp = bcmod(
$current, 
'16777216');
 
  571                    $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . 
$value;
 
  575                return $this->precision > 0 ?
 
  576                    substr(str_pad(
$value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
 
  580        if (!count($this->value)) {
 
  581            return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : 
'';
 
  585        $temp = $this->
copy();
 
  587        for (
$i = count($temp->value) - 2; 
$i >= 0; --
$i) {
 
  592        return $this->precision > 0 ?
 
  593            str_pad(substr(
$result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
 
  617    function toHex($twos_compliment = 
false)
 
  619        return bin2hex($this->
toBytes($twos_compliment));
 
  642    function toBits($twos_compliment = 
false)
 
  647            $bits = str_pad(decbin(hexdec(substr(
$hex, 
$i, 8))), 32, 
'0', STR_PAD_LEFT) . $bits;
 
  650            $bits = str_pad(decbin(hexdec(substr(
$hex, 0, 
$start))), 8, 
'0', STR_PAD_LEFT) . $bits;
 
  652        $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, 
'0');
 
  654        if ($twos_compliment && $this->
compare(
new static()) > 0 && $this->precision <= 0) {
 
  679        switch (MATH_BIGINTEGER_MODE) {
 
  681                return gmp_strval($this->value);
 
  683                if ($this->value === 
'0') {
 
  687                return ltrim($this->value, 
'0');
 
  690        if (!count($this->value)) {
 
  694        $temp = $this->
copy();
 
  695        $temp->is_negative = 
false;
 
  697        $divisor = 
new static();
 
  698        $divisor->value = array(self::$max10);
 
  700        while (count($temp->value)) {
 
  701            list($temp, $mod) = $temp->divide($divisor);
 
  702            $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : 
'', self::$max10Len, 
'0', STR_PAD_LEFT) . 
$result;
 
  709        if ($this->is_negative) {
 
  730        $temp = 
new static();
 
  766        return $this->
copy();
 
  779        $this->hex = $this->
toHex(
true);
 
  780        $vars = array(
'hex');
 
  781        if ($this->precision > 0) {
 
  782            $vars[] = 
'precision';
 
  798        $this->value = $temp->value;
 
  799        $this->is_negative = $temp->is_negative;
 
  800        if ($this->precision > 0) {
 
  816        switch (MATH_BIGINTEGER_MODE) {
 
  825                $opts[] = PHP_INT_SIZE == 8 ? 
'64-bit' : 
'32-bit';
 
  827        if (MATH_BIGINTEGER_MODE != self::MODE_GMP && defined(
'MATH_BIGINTEGER_OPENSSL_ENABLED')) {
 
  831            $engine.= 
' (' . implode($opts, 
', ') . 
')';
 
  834            'value' => 
'0x' . $this->
toHex(
true),
 
  861        switch (MATH_BIGINTEGER_MODE) {
 
  863                $temp = 
new static();
 
  864                $temp->value = gmp_add($this->value, 
$y->value);
 
  868                $temp = 
new static();
 
  869                $temp->value = bcadd($this->value, 
$y->value, 0);
 
  874        $temp = $this->
_add($this->value, $this->is_negative, 
$y->value, 
$y->is_negative);
 
  893    function _add($x_value, $x_negative, $y_value, $y_negative)
 
  895        $x_size = count($x_value);
 
  896        $y_size = count($y_value);
 
  900                self::VALUE => $y_value,
 
  901                self::SIGN => $y_negative
 
  903        } elseif ($y_size == 0) {
 
  905                self::VALUE => $x_value,
 
  906                self::SIGN => $x_negative
 
  911        if ($x_negative != $y_negative) {
 
  912            if ($x_value == $y_value) {
 
  914                    self::VALUE => array(),
 
  919            $temp = $this->
_subtract($x_value, 
false, $y_value, 
false);
 
  921                                          $x_negative : $y_negative;
 
  926        if ($x_size < $y_size) {
 
  937        for (
$i = 0, $j = 1; $j < 
$size; 
$i+=2, $j+=2) {
 
  938            $sum = $x_value[$j] * self::$baseFull + $x_value[
$i] + $y_value[$j] * self::$baseFull + $y_value[
$i] + $carry;
 
  942            $temp = 
self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
 
  944            $value[
$i] = (int) ($sum - self::$baseFull * $temp); 
 
  949            $sum = $x_value[
$i] + $y_value[
$i] + $carry;
 
  963            self::VALUE => $this->
_trim($value),
 
  964            self::SIGN => $x_negative
 
  990        switch (MATH_BIGINTEGER_MODE) {
 
  992                $temp = 
new static();
 
  993                $temp->value = gmp_sub($this->value, 
$y->value);
 
  997                $temp = 
new static();
 
  998                $temp->value = bcsub($this->value, 
$y->value, 0);
 
 1003        $temp = $this->
_subtract($this->value, $this->is_negative, 
$y->value, 
$y->is_negative);
 
 1022    function _subtract($x_value, $x_negative, $y_value, $y_negative)
 
 1024        $x_size = count($x_value);
 
 1025        $y_size = count($y_value);
 
 1029                self::VALUE => $y_value,
 
 1030                self::SIGN => !$y_negative
 
 1032        } elseif ($y_size == 0) {
 
 1034                self::VALUE => $x_value,
 
 1035                self::SIGN => $x_negative
 
 1040        if ($x_negative != $y_negative) {
 
 1041            $temp = $this->
_add($x_value, 
false, $y_value, 
false);
 
 1047        $diff = $this->
_compare($x_value, $x_negative, $y_value, $y_negative);
 
 1051                self::VALUE => array(),
 
 1057        if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
 
 1059            $x_value = $y_value;
 
 1062            $x_negative = !$x_negative;
 
 1064            $x_size = count($x_value);
 
 1065            $y_size = count($y_value);
 
 1071        for (
$i = 0, $j = 1; $j < $y_size; 
$i+=2, $j+=2) {
 
 1072            $sum = $x_value[$j] * self::$baseFull + $x_value[
$i] - $y_value[$j] * self::$baseFull - $y_value[
$i] - $carry;
 
 1076            $temp = 
self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
 
 1078            $x_value[
$i] = (int) ($sum - self::$baseFull * $temp);
 
 1079            $x_value[$j] = $temp;
 
 1082        if ($j == $y_size) { 
 
 1083            $sum = $x_value[
$i] - $y_value[
$i] - $carry;
 
 1090            for (; !$x_value[
$i]; ++
$i) {
 
 1097            self::VALUE => $this->
_trim($x_value),
 
 1098            self::SIGN => $x_negative
 
 1123        switch (MATH_BIGINTEGER_MODE) {
 
 1125                $temp = 
new static();
 
 1126                $temp->value = gmp_mul($this->value, 
$x->value);
 
 1130                $temp = 
new static();
 
 1131                $temp->value = bcmul($this->value, 
$x->value, 0);
 
 1136        $temp = $this->
_multiply($this->value, $this->is_negative, 
$x->value, 
$x->is_negative);
 
 1138        $product = 
new static();
 
 1155    function _multiply($x_value, $x_negative, $y_value, $y_negative)
 
 1164        $x_length = count($x_value);
 
 1165        $y_length = count($y_value);
 
 1167        if (!$x_length || !$y_length) { 
 
 1169                self::VALUE => array(),
 
 1175            self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ?
 
 1178            self::SIGN => $x_negative != $y_negative
 
 1194        $x_length = count($x_value);
 
 1195        $y_length = count($y_value);
 
 1197        if (!$x_length || !$y_length) { 
 
 1201        if ($x_length < $y_length) {
 
 1203            $x_value = $y_value;
 
 1206            $x_length = count($x_value);
 
 1207            $y_length = count($y_value);
 
 1210        $product_value = $this->
_array_repeat(0, $x_length + $y_length);
 
 1220        for ($j = 0; $j < $x_length; ++$j) { 
 
 1221            $temp = $x_value[$j] * $y_value[0] + $carry; 
 
 1222            $carry = 
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 
 1223            $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
 
 1226        $product_value[$j] = $carry;
 
 1230        for (
$i = 1; 
$i < $y_length; ++
$i) {
 
 1233            for ($j = 0, $k = 
$i; $j < $x_length; ++$j, ++$k) {
 
 1234                $temp = $product_value[$k] + $x_value[$j] * $y_value[
$i] + $carry;
 
 1235                $carry = 
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 
 1236                $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
 
 1239            $product_value[$k] = $carry;
 
 1242        return $product_value;
 
 1258        $m = min(count($x_value) >> 1, count($y_value) >> 1);
 
 1260        if (
$m < self::KARATSUBA_CUTOFF) {
 
 1264        $x1 = array_slice($x_value, 
$m);
 
 1265        $x0 = array_slice($x_value, 0, 
$m);
 
 1266        $y1 = array_slice($y_value, 
$m);
 
 1267        $y0 = array_slice($y_value, 0, 
$m);
 
 1272        $z1 = $this->
_add($x1, 
false, $x0, 
false);
 
 1273        $temp = $this->
_add($y1, 
false, $y0, 
false);
 
 1274        $z1 = $this->
_karatsuba($z1[self::VALUE], $temp[self::VALUE]);
 
 1275        $temp = $this->
_add($z2, 
false, $z0, 
false);
 
 1276        $z1 = $this->
_subtract($z1, 
false, $temp[self::VALUE], 
false);
 
 1278        $z2 = array_merge(array_fill(0, 2 * 
$m, 0), $z2);
 
 1279        $z1[
self::VALUE] = array_merge(array_fill(0, 
$m, 0), $z1[self::VALUE]);
 
 1281        $xy = $this->
_add($z2, 
false, $z1[self::VALUE], $z1[self::SIGN]);
 
 1282        $xy = $this->
_add($xy[self::VALUE], $xy[self::SIGN], $z0, 
false);
 
 1296        return count(
$x) < 2 * self::KARATSUBA_CUTOFF ?
 
 1319        for (
$i = 0, $max_index = count(
$value) - 1; 
$i <= $max_index; ++
$i) {
 
 1323            $carry = 
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 
 1324            $square_value[$i2] = (int) ($temp - self::$baseFull * $carry);
 
 1327            for ($j = 
$i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
 
 1328                $temp = $square_value[$k] + 2 * 
$value[$j] * 
$value[
$i] + $carry;
 
 1329                $carry = 
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 
 1330                $square_value[$k] = (int) ($temp - self::$baseFull * $carry);
 
 1335            $square_value[
$i + $max_index + 1] = $carry;
 
 1338        return $square_value;
 
 1355        if (
$m < self::KARATSUBA_CUTOFF) {
 
 1365        $z1 = $this->
_add($x1, 
false, $x0, 
false);
 
 1367        $temp = $this->
_add($z2, 
false, $z0, 
false);
 
 1368        $z1 = $this->
_subtract($z1, 
false, $temp[self::VALUE], 
false);
 
 1370        $z2 = array_merge(array_fill(0, 2 * 
$m, 0), $z2);
 
 1371        $z1[
self::VALUE] = array_merge(array_fill(0, 
$m, 0), $z1[self::VALUE]);
 
 1373        $xx = $this->
_add($z2, 
false, $z1[self::VALUE], $z1[self::SIGN]);
 
 1374        $xx = $this->
_add($xx[self::VALUE], $xx[self::SIGN], $z0, 
false);
 
 1408        switch (MATH_BIGINTEGER_MODE) {
 
 1410                $quotient = 
new static();
 
 1411                $remainder = 
new static();
 
 1413                list($quotient->value, $remainder->value) = gmp_div_qr($this->value, 
$y->value);
 
 1415                if (gmp_sign($remainder->value) < 0) {
 
 1416                    $remainder->value = gmp_add($remainder->value, gmp_abs(
$y->value));
 
 1421                $quotient = 
new static();
 
 1422                $remainder = 
new static();
 
 1424                $quotient->value = bcdiv($this->value, 
$y->value, 0);
 
 1425                $remainder->value = bcmod($this->value, 
$y->value);
 
 1427                if ($remainder->value[0] == 
'-') {
 
 1428                    $remainder->value = bcadd($remainder->value, 
$y->value[0] == 
'-' ? substr(
$y->value, 1) : 
$y->value, 0);
 
 1434        if (count(
$y->value) == 1) {
 
 1436            $quotient = 
new static();
 
 1437            $remainder = 
new static();
 
 1438            $quotient->value = $q;
 
 1439            $remainder->value = array(
$r);
 
 1440            $quotient->is_negative = $this->is_negative != 
$y->is_negative;
 
 1445        if (!isset($zero)) {
 
 1446            $zero = 
new static();
 
 1452        $x_sign = 
$x->is_negative;
 
 1453        $y_sign = 
$y->is_negative;
 
 1455        $x->is_negative = 
$y->is_negative = 
false;
 
 1457        $diff = 
$x->compare(
$y);
 
 1460            $temp = 
new static();
 
 1461            $temp->value = array(1);
 
 1462            $temp->is_negative = $x_sign != $y_sign;
 
 1475        $msb = 
$y->value[count(
$y->value) - 1];
 
 1479        $x->_lshift($shift);
 
 1480        $y->_lshift($shift);
 
 1481        $y_value = &
$y->value;
 
 1483        $x_max = count(
$x->value) - 1;
 
 1484        $y_max = count(
$y->value) - 1;
 
 1486        $quotient = 
new static();
 
 1487        $quotient_value = &$quotient->value;
 
 1488        $quotient_value = $this->
_array_repeat(0, $x_max - $y_max + 1);
 
 1490        static $temp, $lhs, $rhs;
 
 1491        if (!isset($temp)) {
 
 1492            $temp = 
new static();
 
 1493            $lhs =  
new static();
 
 1494            $rhs =  
new static();
 
 1496        $temp_value = &$temp->value;
 
 1497        $rhs_value =  &$rhs->value;
 
 1500        $temp_value = array_merge($this->
_array_repeat(0, $x_max - $y_max), $y_value);
 
 1502        while (
$x->compare($temp) >= 0) {
 
 1504            ++$quotient_value[$x_max - $y_max];
 
 1505            $x = 
$x->subtract($temp);
 
 1506            $x_max = count(
$x->value) - 1;
 
 1509        for (
$i = $x_max; 
$i >= $y_max + 1; --
$i) {
 
 1510            $x_value = &
$x->value;
 
 1512                isset($x_value[
$i]) ? $x_value[
$i] : 0,
 
 1513                isset($x_value[
$i - 1]) ? $x_value[
$i - 1] : 0,
 
 1514                isset($x_value[
$i - 2]) ? $x_value[
$i - 2] : 0
 
 1518                ($y_max > 0) ? $y_value[$y_max - 1] : 0
 
 1521            $q_index = 
$i - $y_max - 1;
 
 1522            if ($x_window[0] == $y_window[0]) {
 
 1526                    $x_window[0] * self::$baseFull + $x_window[1],
 
 1531            $temp_value = array($y_window[1], $y_window[0]);
 
 1533            $lhs->value = array($quotient_value[$q_index]);
 
 1534            $lhs = $lhs->multiply($temp);
 
 1536            $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
 
 1538            while ($lhs->compare($rhs) > 0) {
 
 1539                --$quotient_value[$q_index];
 
 1541                $lhs->value = array($quotient_value[$q_index]);
 
 1542                $lhs = $lhs->multiply($temp);
 
 1546            $temp_value = array($quotient_value[$q_index]);
 
 1547            $temp = $temp->multiply(
$y);
 
 1548            $temp_value = &$temp->value;
 
 1549            $temp_value = array_merge($adjust, $temp_value);
 
 1551            $x = 
$x->subtract($temp);
 
 1553            if (
$x->compare($zero) < 0) {
 
 1554                $temp_value = array_merge($adjust, $y_value);
 
 1555                $x = 
$x->add($temp);
 
 1557                --$quotient_value[$q_index];
 
 1560            $x_max = count($x_value) - 1;
 
 1564        $x->_rshift($shift);
 
 1566        $quotient->is_negative = $x_sign != $y_sign;
 
 1570            $y->_rshift($shift);
 
 1592        for (
$i = count($dividend) - 1; 
$i >= 0; --
$i) {
 
 1593            $temp = self::$baseFull * $carry + $dividend[
$i];
 
 1595            $carry = (int) ($temp - $divisor * 
$result[
$i]);
 
 1598        return array(
$result, $carry);
 
 1643        $n = $this->bitmask !== 
false && $this->bitmask->compare(
$n) < 0 ? $this->bitmask : 
$n->abs();
 
 1645        if ($e->compare(
new static()) < 0) {
 
 1649            if ($temp === 
false) {
 
 1656        if (MATH_BIGINTEGER_MODE == self::MODE_GMP) {
 
 1657            $temp = 
new static();
 
 1658            $temp->value = gmp_powm($this->value, $e->value, 
$n->value);
 
 1665            return $temp->modPow($e, 
$n);
 
 1668        if (defined(
'MATH_BIGINTEGER_OPENSSL_ENABLED')) {
 
 1669            $components = array(
 
 1670                'modulus' => 
$n->toBytes(
true),
 
 1671                'publicExponent' => $e->toBytes(
true)
 
 1674            $components = array(
 
 1675                'modulus' => pack(
'Ca*a*', 2, $this->
_encodeASN1Length(strlen($components[
'modulus'])), $components[
'modulus']),
 
 1676                'publicExponent' => pack(
'Ca*a*', 2, $this->
_encodeASN1Length(strlen($components[
'publicExponent'])), $components[
'publicExponent'])
 
 1679            $RSAPublicKey = pack(
 
 1682                $this->
_encodeASN1Length(strlen($components[
'modulus']) + strlen($components[
'publicExponent'])),
 
 1683                $components[
'modulus'],
 
 1684                $components[
'publicExponent']
 
 1687            $rsaOID = pack(
'H*', 
'300d06092a864886f70d0101010500'); 
 
 1688            $RSAPublicKey = chr(0) . $RSAPublicKey;
 
 1689            $RSAPublicKey = chr(3) . $this->
_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
 
 1691            $encapsulated = pack(
 
 1695                $rsaOID . $RSAPublicKey
 
 1698            $RSAPublicKey = 
"-----BEGIN PUBLIC KEY-----\r\n" .
 
 1699                             chunk_split(base64_encode($encapsulated)) .
 
 1700                             '-----END PUBLIC KEY-----';
 
 1702            $plaintext = str_pad($this->
toBytes(), strlen(
$n->toBytes(
true)) - 1, 
"\0", STR_PAD_LEFT);
 
 1704            if (openssl_public_encrypt($plaintext, 
$result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
 
 1705                return new static(
$result, 256);
 
 1709        if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
 
 1710            $temp = 
new static();
 
 1711            $temp->value = bcpowmod($this->value, $e->value, 
$n->value, 0);
 
 1716        if (empty($e->value)) {
 
 1717            $temp = 
new static();
 
 1718            $temp->value = array(1);
 
 1722        if ($e->value == array(1)) {
 
 1727        if ($e->value == array(2)) {
 
 1728            $temp = 
new static();
 
 1729            $temp->value = $this->
_square($this->value);
 
 1730            list(, $temp) = $temp->divide(
$n);
 
 1742        if (
$n->value[0] & 1) {
 
 1748        for (
$i = 0; 
$i < count(
$n->value); ++
$i) {
 
 1749            if (
$n->value[
$i]) {
 
 1750                $temp = decbin(
$n->value[
$i]);
 
 1751                $j = strlen($temp) - strrpos($temp, 
'1') - 1;
 
 1760        $mod2 = 
new static();
 
 1761        $mod2->value = array(1);
 
 1764        $part1 = ($mod1->value != array(1)) ? $this->
_slidingWindow($e, $mod1, self::MONTGOMERY) : 
new static();
 
 1767        $y1 = $mod2->modInverse($mod1);
 
 1768        $y2 = $mod1->modInverse($mod2);
 
 1770        $result = $part1->multiply($mod2);
 
 1773        $temp = $part2->multiply($mod1);
 
 1774        $temp = $temp->multiply($y2);
 
 1813        static $window_ranges = array(7, 25, 81, 241, 673, 1793); 
 
 1816        $e_value = $e->value;
 
 1817        $e_length = count($e_value) - 1;
 
 1818        $e_bits = decbin($e_value[$e_length]);
 
 1819        for (
$i = $e_length - 1; 
$i >= 0; --
$i) {
 
 1820            $e_bits.= str_pad(decbin($e_value[
$i]), 
self::$base, 
'0', STR_PAD_LEFT);
 
 1823        $e_length = strlen($e_bits);
 
 1827        for (
$i = 0, $window_size = 1; $e_length > $window_ranges[
$i] && 
$i < count($window_ranges); ++$window_size, ++
$i) {
 
 1830        $n_value = 
$n->value;
 
 1834        $powers[1] = $this->
_prepareReduce($this->value, $n_value, $mode);
 
 1835        $powers[2] = $this->
_squareReduce($powers[1], $n_value, $mode);
 
 1839        $temp = 1 << ($window_size - 1);
 
 1840        for (
$i = 1; 
$i < $temp; ++
$i) {
 
 1842            $powers[$i2 + 1] = $this->
_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
 
 1848        for (
$i = 0; 
$i < $e_length;) {
 
 1853                for ($j = $window_size - 1; $j > 0; --$j) {
 
 1854                    if (!empty($e_bits[
$i + $j])) {
 
 1860                for ($k = 0; $k <= $j; ++$k) {
 
 1870        $temp = 
new static();
 
 1896                $lhs = 
new static();
 
 1898                $rhs = 
new static();
 
 1900                return $x->_mod2(
$n);
 
 1902                $lhs = 
new static();
 
 1904                $rhs = 
new static();
 
 1906                list(, $temp) = $lhs->divide($rhs);
 
 1907                return $temp->value;
 
 1927        if ($mode == self::MONTGOMERY) {
 
 1946        if ($mode == self::MONTGOMERY) {
 
 1950        return $this->
_reduce($temp[self::VALUE], 
$n, $mode);
 
 1965        if ($mode == self::MONTGOMERY) {
 
 1984        $temp = 
new static();
 
 1985        $temp->value = array(1);
 
 2015        static $cache = array(
 
 2016            self::VARIABLE => array(),
 
 2017            self::DATA => array()
 
 2020        $m_length = count(
$m);
 
 2023        if (count(
$n) > 2 * $m_length) {
 
 2024            $lhs = 
new static();
 
 2025            $rhs = 
new static();
 
 2028            list(, $temp) = $lhs->divide($rhs);
 
 2029            return $temp->value;
 
 2033        if ($m_length < 5) {
 
 2039        if ((
$key = array_search(
$m, $cache[self::VARIABLE])) === 
false) {
 
 2040            $key = count($cache[self::VARIABLE]);
 
 2043            $lhs = 
new static();
 
 2044            $lhs_value = &$lhs->value;
 
 2045            $lhs_value = $this->
_array_repeat(0, $m_length + ($m_length >> 1));
 
 2047            $rhs = 
new static();
 
 2050            list($u, $m1) = $lhs->divide($rhs);
 
 2059            extract($cache[self::DATA][
$key]);
 
 2062        $cutoff = $m_length + ($m_length >> 1);
 
 2063        $lsd = array_slice(
$n, 0, $cutoff); 
 
 2064        $msd = array_slice(
$n, $cutoff);    
 
 2065        $lsd = $this->
_trim($lsd);
 
 2066        $temp = $this->
_multiply($msd, 
false, $m1, 
false);
 
 2067        $n = $this->
_add($lsd, 
false, $temp[self::VALUE], 
false); 
 
 2069        if ($m_length & 1) {
 
 2074        $temp = array_slice(
$n[self::VALUE], $m_length - 1);
 
 2077        $temp = $this->
_multiply($temp, 
false, $u, 
false);
 
 2080        $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1);
 
 2083        $temp = $this->
_multiply($temp, 
false, 
$m, 
false);
 
 2112        static $cache = array(
 
 2113            self::VARIABLE => array(),
 
 2114            self::DATA => array()
 
 2117        $n_length = count(
$n);
 
 2119        if (count(
$x) > 2 * $n_length) {
 
 2120            $lhs = 
new static();
 
 2121            $rhs = 
new static();
 
 2124            list(, $temp) = $lhs->divide($rhs);
 
 2125            return $temp->value;
 
 2128        if ((
$key = array_search(
$n, $cache[self::VARIABLE])) === 
false) {
 
 2129            $key = count($cache[self::VARIABLE]);
 
 2131            $lhs = 
new static();
 
 2132            $lhs_value = &$lhs->value;
 
 2135            $rhs = 
new static();
 
 2137            list($temp, ) = $lhs->divide($rhs); 
 
 2142        $temp = array_slice(
$x, $n_length - 1);
 
 2144        $temp = $this->
_multiply($temp, 
false, $cache[self::DATA][
$key], 
false);
 
 2146        $temp = array_slice($temp[self::VALUE], $n_length + 1);
 
 2149        $result = array_slice(
$x, 0, $n_length + 1);
 
 2154        if ($this->
_compare(
$result, 
false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
 
 2156            $corrector_value[count($corrector_value)] = 1;
 
 2186        $x_length = count($x_value);
 
 2187        $y_length = count($y_value);
 
 2189        if (!$x_length || !$y_length) { 
 
 2191                self::VALUE => array(),
 
 2196        if ($x_length < $y_length) {
 
 2198            $x_value = $y_value;
 
 2201            $x_length = count($x_value);
 
 2202            $y_length = count($y_value);
 
 2205        $product_value = $this->
_array_repeat(0, $x_length + $y_length);
 
 2215        for ($j = 0; $j < $x_length; ++$j) { 
 
 2216            $temp = $x_value[$j] * $y_value[0] + $carry; 
 
 2217            $carry = 
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 
 2218            $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
 
 2222            $product_value[$j] = $carry;
 
 2228        for (
$i = 1; 
$i < $y_length; ++
$i) {
 
 2231            for ($j = 0, $k = 
$i; $j < $x_length && $k < $stop; ++$j, ++$k) {
 
 2232                $temp = $product_value[$k] + $x_value[$j] * $y_value[
$i] + $carry;
 
 2233                $carry = 
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 
 2234                $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
 
 2238                $product_value[$k] = $carry;
 
 2243            self::VALUE => $this->
_trim($product_value),
 
 2244            self::SIGN => $x_negative != $y_negative
 
 2265        static $cache = array(
 
 2266            self::VARIABLE => array(),
 
 2267            self::DATA => array()
 
 2270        if ((
$key = array_search(
$n, $cache[self::VARIABLE])) === 
false) {
 
 2271            $key = count($cache[self::VARIABLE]);
 
 2280        for (
$i = 0; 
$i < $k; ++
$i) {
 
 2282            $temp = $temp - self::$baseFull * (
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
 
 2321        static $cache = array(
 
 2322            self::VARIABLE => array(),
 
 2323            self::DATA => array()
 
 2326        if ((
$key = array_search(
$m, $cache[self::VARIABLE])) === 
false) {
 
 2327            $key = count($cache[self::VARIABLE]);
 
 2332        $n = max(count(
$x), count(
$y), count(
$m));
 
 2333        $x = array_pad(
$x, 
$n, 0);
 
 2334        $y = array_pad(
$y, 
$n, 0);
 
 2335        $m = array_pad(
$m, 
$n, 0);
 
 2339            $temp = $temp - self::$baseFull * (
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
 
 2341            $temp = $temp - self::$baseFull * (
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
 
 2343            $a = $this->
_add($a[self::VALUE], 
false, $temp[self::VALUE], 
false);
 
 2344            $a[
self::VALUE] = array_slice($a[self::VALUE], 1);
 
 2346        if ($this->
_compare($a[self::VALUE], 
false, 
$m, 
false) >= 0) {
 
 2347            $a = $this->
_subtract($a[self::VALUE], 
false, 
$m, 
false);
 
 2364        $lhs = 
new static();
 
 2366        $rhs = 
new static();
 
 2369        list(, $temp) = $lhs->divide($rhs);
 
 2370        return $temp->value;
 
 2439        switch (MATH_BIGINTEGER_MODE) {
 
 2441                $temp = 
new static();
 
 2442                $temp->value = gmp_invert($this->value, 
$n->value);
 
 2444                return ($temp->value === 
false) ? false : $this->
_normalize($temp);
 
 2448        if (!isset($zero)) {
 
 2449            $zero = 
new static();
 
 2450            $one = 
new static(1);
 
 2456        if ($this->
compare($zero) < 0) {
 
 2457            $temp = $this->
abs();
 
 2458            $temp = $temp->modInverse(
$n);
 
 2464        if (!$gcd->equals($one)) {
 
 2468        $x = 
$x->compare($zero) < 0 ? 
$x->add(
$n) : 
$x;
 
 2503        switch (MATH_BIGINTEGER_MODE) {
 
 2505                extract(gmp_gcdext($this->value, 
$n->value));
 
 2525                while (bccomp($v, 
'0', 0) != 0) {
 
 2526                    $q = bcdiv($u, $v, 0);
 
 2530                    $v = bcsub($temp, bcmul($v, $q, 0), 0);
 
 2534                    $c = bcsub($temp, bcmul($a, $q, 0), 0);
 
 2538                    $d = bcsub($temp, bcmul($b, $q, 0), 0);
 
 2551        $g->value = array(1);
 
 2553        while (!((
$x->value[0] & 1)|| (
$y->value[0] & 1))) {
 
 2567        $a->value = 
$d->value = $g->value = array(1);
 
 2568        $b->value = 
$c->value = array();
 
 2570        while (!empty($u->value)) {
 
 2571            while (!($u->value[0] & 1)) {
 
 2573                if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
 
 2575                    $b = $b->subtract(
$x);
 
 2581            while (!($v->value[0] & 1)) {
 
 2583                if ((!empty(
$d->value) && (
$d->value[0] & 1)) || (!empty(
$c->value) && (
$c->value[0] & 1))) {
 
 2591            if ($u->compare($v) >= 0) {
 
 2592                $u = $u->subtract($v);
 
 2593                $a = $a->subtract(
$c);
 
 2594                $b = $b->subtract(
$d);
 
 2596                $v = $v->subtract($u);
 
 2597                $c = 
$c->subtract($a);
 
 2598                $d = 
$d->subtract($b);
 
 2603            'gcd' => $this->
_normalize($g->multiply($v)),
 
 2604            'x'   => $this->_normalize(
$c),
 
 2605            'y'   => $this->_normalize(
$d)
 
 2644        $temp = 
new static();
 
 2646        switch (MATH_BIGINTEGER_MODE) {
 
 2648                $temp->value = gmp_abs($this->value);
 
 2651                $temp->value = (bccomp($this->value, 
'0', 0) < 0) ? substr($this->value, 1) : 
$this->value;
 
 2680        switch (MATH_BIGINTEGER_MODE) {
 
 2682                return gmp_cmp($this->value, 
$y->value);
 
 2684                return bccomp($this->value, 
$y->value, 0);
 
 2687        return $this->
_compare($this->value, $this->is_negative, 
$y->value, 
$y->is_negative);
 
 2701    function _compare($x_value, $x_negative, $y_value, $y_negative)
 
 2703        if ($x_negative != $y_negative) {
 
 2704            return (!$x_negative && $y_negative) ? 1 : -1;
 
 2707        $result = $x_negative ? -1 : 1;
 
 2709        if (count($x_value) != count($y_value)) {
 
 2712        $size = max(count($x_value), count($y_value));
 
 2714        $x_value = array_pad($x_value, 
$size, 0);
 
 2715        $y_value = array_pad($y_value, 
$size, 0);
 
 2717        for (
$i = count($x_value) - 1; 
$i >= 0; --
$i) {
 
 2718            if ($x_value[
$i] != $y_value[
$i]) {
 
 2738        switch (MATH_BIGINTEGER_MODE) {
 
 2740                return gmp_cmp($this->value, 
$x->value) == 0;
 
 2742                return $this->value === 
$x->value && $this->is_negative == 
$x->is_negative;
 
 2757        $this->precision = $bits;
 
 2758        if (MATH_BIGINTEGER_MODE != self::MODE_BCMATH) {
 
 2759            $this->bitmask = 
new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
 
 2761            $this->bitmask = 
new static(bcpow(
'2', $bits, 0));
 
 2765        $this->value = $temp->value;
 
 2778        switch (MATH_BIGINTEGER_MODE) {
 
 2780                $temp = 
new static();
 
 2781                $temp->value = gmp_and($this->value, 
$x->value);
 
 2786                $right = 
$x->toBytes();
 
 2788                $length = max(strlen($left), strlen($right));
 
 2790                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
 
 2791                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
 
 2793                return $this->
_normalize(
new static($left & $right, 256));
 
 2798        $length = min(count(
$x->value), count($this->value));
 
 2802        for (
$i = 0; 
$i < $length; ++
$i) {
 
 2819        switch (MATH_BIGINTEGER_MODE) {
 
 2821                $temp = 
new static();
 
 2822                $temp->value = gmp_or($this->value, 
$x->value);
 
 2827                $right = 
$x->toBytes();
 
 2829                $length = max(strlen($left), strlen($right));
 
 2831                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
 
 2832                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
 
 2834                return $this->
_normalize(
new static($left | $right, 256));
 
 2837        $length = max(count($this->value), count(
$x->value));
 
 2840        $x->value = array_pad(
$x->value, $length, 0);
 
 2842        for (
$i = 0; 
$i < $length; ++
$i) {
 
 2859        switch (MATH_BIGINTEGER_MODE) {
 
 2861                $temp = 
new static();
 
 2862                $temp->value = gmp_xor($this->value, 
$x->value);
 
 2867                $right = 
$x->toBytes();
 
 2869                $length = max(strlen($left), strlen($right));
 
 2871                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
 
 2872                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
 
 2874                return $this->
_normalize(
new static($left ^ $right, 256));
 
 2877        $length = max(count($this->value), count(
$x->value));
 
 2880        $x->value = array_pad(
$x->value, $length, 0);
 
 2882        for (
$i = 0; 
$i < $length; ++
$i) {
 
 2904        $pre_msb = decbin(ord($temp[0]));
 
 2906        $msb = decbin(ord($temp[0]));
 
 2907        if (strlen(
$msb) == 8) {
 
 2910        $temp[0] = chr(bindec(
$msb));
 
 2913        $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
 
 2914        $new_bits = $this->precision - $current_bits;
 
 2915        if ($new_bits <= 0) {
 
 2916            return $this->
_normalize(
new static($temp, 256));
 
 2920        $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
 
 2923        $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
 
 2925        return $this->
_normalize(
new static($leading_ones | $temp, 256));
 
 2940        $temp = 
new static();
 
 2942        switch (MATH_BIGINTEGER_MODE) {
 
 2947                    $two = gmp_init(
'2');
 
 2950                $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
 
 2954                $temp->value = bcdiv($this->value, bcpow(
'2', $shift, 0), 0);
 
 2960                $temp->_rshift($shift);
 
 2978        $temp = 
new static();
 
 2980        switch (MATH_BIGINTEGER_MODE) {
 
 2985                    $two = gmp_init(
'2');
 
 2988                $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
 
 2992                $temp->value = bcmul($this->value, bcpow(
'2', $shift, 0), 0);
 
 2998                $temp->_lshift($shift);
 
 3017        if ($this->precision > 0) {
 
 3019            if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
 
 3020                $mask = $this->bitmask->subtract(
new static(1));
 
 3023                $mask = $this->bitmask->toBytes();
 
 3026            $temp = ord($bits[0]);
 
 3027            for (
$i = 0; $temp >> 
$i; ++
$i) {
 
 3039            return $this->
copy();
 
 3043        $left = $left->bitwise_and(
new static(
$mask, 256));
 
 3045        $result = MATH_BIGINTEGER_MODE != self::MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
 
 3074        if (class_exists(
'\phpseclib\Crypt\Random')) {
 
 3080                $random.= chr(mt_rand(0, 255));
 
 3083            $blocks = 
$size >> 1;
 
 3084            for (
$i = 0; 
$i < $blocks; ++
$i) {
 
 3086                $random.= pack(
'n', mt_rand(0, 0xFFFF));
 
 3090        return new static($random, 256);
 
 3111        if ($arg1 === 
false) {
 
 3115        if ($arg2 === 
false) {
 
 3123        $compare = $max->compare($min);
 
 3127        } elseif ($compare < 0) {
 
 3136            $one = 
new static(1);
 
 3139        $max = $max->subtract($min->subtract($one));
 
 3140        $size = strlen(ltrim($max->toBytes(), chr(0)));
 
 3157        $random_max = 
new static(chr(1) . str_repeat(
"\0", 
$size), 256);
 
 3160        list($max_multiple) = $random_max->divide($max);
 
 3161        $max_multiple = $max_multiple->multiply($max);
 
 3163        while ($random->compare($max_multiple) >= 0) {
 
 3164            $random = $random->subtract($max_multiple);
 
 3165            $random_max = $random_max->subtract($max_multiple);
 
 3166            $random = $random->bitwise_leftShift(8);
 
 3168            $random_max = $random_max->bitwise_leftShift(8);
 
 3169            list($max_multiple) = $random_max->divide($max);
 
 3170            $max_multiple = $max_multiple->multiply($max);
 
 3172        list(, $random) = $random->divide($max);
 
 3174        return $this->
_normalize($random->add($min));
 
 3192        if ($arg1 === 
false) {
 
 3196        if ($arg2 === 
false) {
 
 3204        $compare = $max->compare($min);
 
 3207            return $min->isPrime() ? $min : 
false;
 
 3208        } elseif ($compare < 0) {
 
 3217            $one = 
new static(1);
 
 3218            $two = 
new static(2);
 
 3226        if (MATH_BIGINTEGER_MODE == self::MODE_GMP && extension_loaded(
'gmp')) {
 
 3228            $p->value = gmp_nextprime(
$x->value);
 
 3230            if ($p->compare($max) <= 0) {
 
 3234            if (!$min->equals(
$x)) {
 
 3235                $x = 
$x->subtract($one);
 
 3238            return $x->randomPrime($min, 
$x);
 
 3241        if (
$x->equals($two)) {
 
 3246        if (
$x->compare($max) > 0) {
 
 3248            if ($min->equals($max)) {
 
 3255        $initial_x = 
$x->copy();
 
 3258            if ($timeout !== 
false && time() - 
$start > $timeout) {
 
 3262            if (
$x->isPrime()) {
 
 3268            if (
$x->compare($max) > 0) {
 
 3270                if (
$x->equals($two)) {
 
 3276            if (
$x->equals($initial_x)) {
 
 3292        switch (MATH_BIGINTEGER_MODE) {
 
 3294                gmp_setbit($this->value, 0);
 
 3297                if ($this->value[strlen($this->value) - 1] % 2 == 0) {
 
 3298                    $this->value = bcadd($this->value, 
'1');
 
 3302                $this->value[0] |= 1;
 
 3322        $length = strlen($this->
toBytes());
 
 3327                 if ($length >= 163) { 
$t =  2; } 
 
 3328            else if ($length >= 106) { 
$t =  3; } 
 
 3329            else if ($length >= 81 ) { 
$t =  4; } 
 
 3330            else if ($length >= 68 ) { 
$t =  5; } 
 
 3331            else if ($length >= 56 ) { 
$t =  6; } 
 
 3332            else if ($length >= 50 ) { 
$t =  7; } 
 
 3333            else if ($length >= 43 ) { 
$t =  8; } 
 
 3334            else if ($length >= 37 ) { 
$t =  9; } 
 
 3335            else if ($length >= 31 ) { 
$t = 12; } 
 
 3336            else if ($length >= 25 ) { 
$t = 15; } 
 
 3337            else if ($length >= 18 ) { 
$t = 18; } 
 
 3344        switch (MATH_BIGINTEGER_MODE) {
 
 3346                return gmp_prob_prime($this->value, 
$t) != 0;
 
 3348                if ($this->value === 
'2') {
 
 3351                if ($this->value[strlen($this->value) - 1] % 2 == 0) {
 
 3356                if ($this->value == array(2)) {
 
 3359                if (~$this->value[0] & 1) {
 
 3364        static $primes, $zero, $one, $two;
 
 3366        if (!isset($primes)) {
 
 3368                3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,   41,   43,   47,   53,   59,
 
 3369                61,   67,   71,   73,   79,   83,   89,   97,   101,  103,  107,  109,  113,  127,  131,  137,
 
 3370                139,  149,  151,  157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,  227,
 
 3371                229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  283,  293,  307,  311,  313,
 
 3372                317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,  397,  401,  409,  419,
 
 3373                421,  431,  433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,  509,
 
 3374                521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,  599,  601,  607,  613,  617,
 
 3375                619,  631,  641,  643,  647,  653,  659,  661,  673,  677,  683,  691,  701,  709,  719,  727,
 
 3376                733,  739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,  829,
 
 3377                839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,  919,  929,  937,  941,  947,
 
 3378                953,  967,  971,  977,  983,  991,  997
 
 3381            if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
 
 3382                for (
$i = 0; 
$i < count($primes); ++
$i) {
 
 3383                    $primes[
$i] = 
new static($primes[
$i]);
 
 3387            $zero = 
new static();
 
 3388            $one = 
new static(1);
 
 3389            $two = 
new static(2);
 
 3392        if ($this->
equals($one)) {
 
 3397        if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
 
 3398            foreach ($primes as $prime) {
 
 3399                list(, 
$r) = $this->
divide($prime);
 
 3400                if (
$r->equals($zero)) {
 
 3401                    return $this->
equals($prime);
 
 3406            foreach ($primes as $prime) {
 
 3415        $n_1 = 
$n->subtract($one);
 
 3416        $n_2 = 
$n->subtract($two);
 
 3419        $r_value = 
$r->value;
 
 3421        if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
 
 3424            while (
$r->value[strlen(
$r->value) - 1] % 2 == 0) {
 
 3425                $r->value = bcdiv(
$r->value, 
'2', 0);
 
 3429            for (
$i = 0, $r_length = count($r_value); 
$i < $r_length; ++
$i) {
 
 3430                $temp = ~$r_value[
$i] & 0xFFFFFF;
 
 3431                for ($j = 1; ($temp >> $j) & 1; ++$j) {
 
 3437            $s = 26 * 
$i + $j - 1;
 
 3442            $a = $this->
random($two, $n_2);
 
 3445            if (!
$y->equals($one) && !
$y->equals($n_1)) {
 
 3446                for ($j = 1; $j < 
$s && !
$y->equals($n_1); ++$j) {
 
 3447                    $y = 
$y->modPow($two, 
$n);
 
 3448                    if (
$y->equals($one)) {
 
 3453                if (!
$y->equals($n_1)) {
 
 3477        $shift = 1 << $shift;
 
 3481        for (
$i = 0; 
$i < count($this->value); ++
$i) {
 
 3482            $temp = $this->value[
$i] * $shift + $carry;
 
 3483            $carry = 
self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
 
 3484            $this->value[
$i] = (int) ($temp - $carry * self::$baseFull);
 
 3488            $this->value[count($this->value)] = $carry;
 
 3491        while ($num_digits--) {
 
 3492            array_unshift($this->value, 0);
 
 3513        $carry_mask = (1 << $shift) - 1;
 
 3516            $this->value = array_slice($this->value, $num_digits);
 
 3521        for (
$i = count($this->value) - 1; 
$i >= 0; --
$i) {
 
 3522            $temp = $this->value[
$i] >> $shift | $carry;
 
 3523            $carry = ($this->value[
$i] & $carry_mask) << $carry_shift;
 
 3524            $this->value[
$i] = $temp;
 
 3527        $this->value = $this->
_trim($this->value);
 
 3545        switch (MATH_BIGINTEGER_MODE) {
 
 3547                if ($this->bitmask !== 
false) {
 
 3553                if (!empty(
$result->bitmask->value)) {
 
 3568        if (!empty(
$result->bitmask->value)) {
 
 3569            $length = min(count(
$value), count($this->bitmask->value));
 
 3572            for (
$i = 0; 
$i < $length; ++
$i) {
 
 3611        return ($multiplier) ? array_fill(0, $multiplier, 
$input) : array();
 
 3630        $num_bytes = $shift >> 3; 
 
 3634        for (
$i = strlen(
$x) - 1; 
$i >= 0; --
$i) {
 
 3635            $temp = ord(
$x[
$i]) << $shift | $carry;
 
 3636            $x[
$i] = chr($temp);
 
 3637            $carry = $temp >> 8;
 
 3639        $carry = ($carry != 0) ? chr($carry) : 
'';
 
 3640        $x = $carry . 
$x . str_repeat(chr(0), $num_bytes);
 
 3656            $x = ltrim(
$x, chr(0));
 
 3660        $num_bytes = $shift >> 3; 
 
 3665            $start = $num_bytes > strlen(
$x) ? -strlen(
$x) : -$num_bytes;
 
 3667            $x = substr(
$x, 0, -$num_bytes);
 
 3671        $carry_shift = 8 - $shift;
 
 3672        for (
$i = 0; 
$i < strlen(
$x); ++
$i) {
 
 3673            $temp = (ord(
$x[
$i]) >> $shift) | $carry;
 
 3674            $carry = (ord(
$x[
$i]) << $carry_shift) & 0xFF;
 
 3675            $x[
$i] = chr($temp);
 
 3677        $x = ltrim(
$x, chr(0));
 
 3679        $remainder = chr($carry >> $carry_shift) . $remainder;
 
 3681        return ltrim($remainder, chr(0));
 
 3696        return ltrim(pack(
'N', 
$x), chr(0));
 
 3708        $temp = unpack(
'Nint', str_pad(
$x, 4, chr(0), STR_PAD_LEFT));
 
 3709        return $temp[
'int'];
 
 3724        if ($length <= 0x7F) {
 
 3725            return chr($length);
 
 3728        $temp = ltrim(pack(
'N', $length), chr(0));
 
 3729        return pack(
'Ca*', 0x80 | strlen($temp), $temp);
 
 3748            return (
int) (
$x / 
$y);
 
An exception for terminatinating execution or to throw for unit testing.
static string($length)
Generate a random string.
multiply($x)
Multiplies two BigIntegers.
bitwise_not()
Logical Not.
_karatsubaSquare($value)
Performs Karatsuba "squaring" on two BigIntegers.
static $max10Len
$max10Len in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base.
_mod2($n)
Modulos for Powers of Two.
__construct($x=0, $base=10)
Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
const DATA
$cache[self::DATA] contains the cached data.
divide($y)
Divides two BigIntegers.
__sleep()
__sleep() magic method
powMod($e, $n)
Performs modular exponentiation.
_baseSquare($value)
Performs traditional squaring on two BigIntegers.
_divide_digit($dividend, $divisor)
Divides a BigInteger by a regular integer.
_multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
Performs long multiplication up to $stop digits.
_prepareReduce($x, $n, $mode)
Modular reduction preperation.
_montgomeryMultiply($x, $y, $m)
Montgomery Multiply.
add($y)
Adds two BigIntegers.
const MODE_GMP
To use the GMP library.
const MONTGOMERY
#+ Reduction constants
_safe_divide($x, $y)
Single digit division.
_array_repeat($input, $multiplier)
Array Repeat.
_karatsuba($x_value, $y_value)
Performs Karatsuba multiplication on two BigIntegers.
_squareReduce($x, $n, $mode)
Modular square.
static $max10
$max10 in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base.
_bytes2int($x)
Converts bytes to 32-bit integers.
_subtract($x_value, $x_negative, $y_value, $y_negative)
Performs subtraction.
modPow($e, $n)
Performs modular exponentiation.
static $base
#+ Static properties used by the pure-PHP implementation.
_regularMultiply($x_value, $y_value)
Performs long multiplication on two BigIntegers.
toBits($twos_compliment=false)
Converts a BigInteger to a bit string (eg.
bitwise_or($x)
Logical Or.
_montgomery($x, $n)
Montgomery Modular Reduction.
toHex($twos_compliment=false)
Converts a BigInteger to a hex string (eg.
_base256_lshift(&$x, $shift)
Logical Left Shift.
bitwise_xor($x)
Logical Exclusive-Or.
_make_odd()
Make the current number odd.
_random_number_helper($size)
Generates a random BigInteger.
_prepMontgomery($x, $n)
Prepare a number for use in Montgomery Modular Reductions.
_multiply($x_value, $x_negative, $y_value, $y_negative)
Performs multiplication.
_add($x_value, $x_negative, $y_value, $y_negative)
Performs addition.
_modInverse67108864($x)
Modular Inverse of a number mod 2**26 (eg.
bitwise_rightShift($shift)
Logical Right Shift.
gcd($n)
Calculates the greatest common divisor.
subtract($y)
Subtracts two BigIntegers.
const SIGN
$result[self::SIGN] contains the sign.
bitwise_rightRotate($shift)
Logical Right Rotate.
__wakeup()
__wakeup() magic method
equals($x)
Tests the equality of two numbers.
__toString()
__toString() magic method
bitwise_leftShift($shift)
Logical Left Shift.
_regularBarrett($x, $n)
(Regular) Barrett Modular Reduction
_normalize($result)
Normalize.
__debugInfo()
__debugInfo() magic method
_slidingWindow($e, $n, $mode)
Sliding Window k-ary Modular Exponentiation.
random($arg1, $arg2=false)
Generate a random number.
setPrecision($bits)
Set Precision.
bitwise_and($x)
Logical And.
toBytes($twos_compliment=false)
Converts a BigInteger to a byte string (eg.
const MODE_BCMATH
To use the BCMath library.
randomPrime($arg1, $arg2=false, $timeout=false)
Generate a random prime number.
_base256_rshift(&$x, $shift)
Logical Right Shift.
bitwise_leftRotate($shift)
Logical Left Rotate.
$bitmask
Precision Bitmask.
_reduce($x, $n, $mode)
Modular reduction.
modInverse($n)
Calculates modular inverses.
_encodeASN1Length($length)
DER-encode an integer.
_square($x=false)
Performs squaring.
__clone()
__clone() magic method
_rshift($shift)
Logical Right Shift.
toString()
Converts a BigInteger to a base-10 number.
_barrett($n, $m)
Barrett Modular Reduction.
extendedGCD($n)
Calculates the greatest common divisor and Bezout's identity.
compare($y)
Compares two numbers.
isPrime($t=false)
Checks a numer to see if it's prime.
_int2bytes($x)
Converts 32-bit integers to bytes.
_lshift($shift)
Logical Left Shift.
_compare($x_value, $x_negative, $y_value, $y_negative)
Compares two numbers.
_multiplyReduce($x, $y, $n, $mode)
Modular multiply.
for( $i=6;$i< 13;$i++) for($i=1; $i< 13; $i++) $d
Pure-PHP arbitrary precision integer arithmetic library.
Pure-PHP arbitrary precision integer arithmetic library.