ILIAS  release_5-4 Revision v5.4.26-12-gabc799a52e6
BigInteger.php
Go to the documentation of this file.
1<?php
2
52
54
64{
75 const MONTGOMERY = 0;
79 const BARRETT = 1;
83 const POWEROF2 = 2;
87 const CLASSIC = 3;
91 const NONE = 4;
105 const VALUE = 0;
109 const SIGN = 1;
122 const VARIABLE = 0;
126 const DATA = 1;
138 const MODE_INTERNAL = 1;
144 const MODE_BCMATH = 2;
150 const MODE_GMP = 3;
161
167 protected static $base;
168 protected static $baseFull;
169 protected static $maxDigit;
170 protected static $msb;
171
176 protected static $max10;
177
182 protected static $max10Len;
183 protected static $maxDigit2;
193
200 var $is_negative = false;
201
208 var $precision = -1;
209
216 var $bitmask = false;
217
230 var $hex;
231
252 function __construct($x = 0, $base = 10)
253 {
254 if (!defined('MATH_BIGINTEGER_MODE')) {
255 switch (true) {
256 case extension_loaded('gmp'):
257 define('MATH_BIGINTEGER_MODE', self::MODE_GMP);
258 break;
259 case extension_loaded('bcmath'):
260 define('MATH_BIGINTEGER_MODE', self::MODE_BCMATH);
261 break;
262 default:
263 define('MATH_BIGINTEGER_MODE', self::MODE_INTERNAL);
264 }
265 }
266
267 if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
268 // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
269 ob_start();
270 @phpinfo();
271 $content = ob_get_contents();
272 ob_end_clean();
273
274 preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
275
276 $versions = array();
277 if (!empty($matches[1])) {
278 for ($i = 0; $i < count($matches[1]); $i++) {
279 $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
280
281 // Remove letter part in OpenSSL version
282 if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
283 $versions[$matches[1][$i]] = $fullVersion;
284 } else {
285 $versions[$matches[1][$i]] = $m[0];
286 }
287 }
288 }
289
290 // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
291 switch (true) {
292 case !isset($versions['Header']):
293 case !isset($versions['Library']):
294 case $versions['Header'] == $versions['Library']:
295 define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
296 break;
297 default:
298 define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
299 }
300 }
301
302 if (!defined('PHP_INT_SIZE')) {
303 define('PHP_INT_SIZE', 4);
304 }
305
306 if (empty(self::$base) && MATH_BIGINTEGER_MODE == self::MODE_INTERNAL) {
307 switch (PHP_INT_SIZE) {
308 case 8: // use 64-bit integers if int size is 8 bytes
309 self::$base = 31;
310 self::$baseFull = 0x80000000;
311 self::$maxDigit = 0x7FFFFFFF;
312 self::$msb = 0x40000000;
313 self::$max10 = 1000000000;
314 self::$max10Len = 9;
315 self::$maxDigit2 = pow(2, 62);
316 break;
317 //case 4: // use 64-bit floats if int size is 4 bytes
318 default:
319 self::$base = 26;
320 self::$baseFull = 0x4000000;
321 self::$maxDigit = 0x3FFFFFF;
322 self::$msb = 0x2000000;
323 self::$max10 = 10000000;
324 self::$max10Len = 7;
325 self::$maxDigit2 = pow(2, 52); // pow() prevents truncation
326 }
327 }
328
329 switch (MATH_BIGINTEGER_MODE) {
330 case self::MODE_GMP:
331 switch (true) {
332 case is_resource($x) && get_resource_type($x) == 'GMP integer':
333 // PHP 5.6 switched GMP from using resources to objects
334 case $x instanceof \GMP:
335 $this->value = $x;
336 return;
337 }
338 $this->value = gmp_init(0);
339 break;
341 $this->value = '0';
342 break;
343 default:
344 $this->value = array();
345 }
346
347 // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
348 // '0' is the only value like this per http://php.net/empty
349 if (empty($x) && (abs($base) != 256 || $x !== '0')) {
350 return;
351 }
352
353 switch ($base) {
354 case -256:
355 if (ord($x[0]) & 0x80) {
356 $x = ~$x;
357 $this->is_negative = true;
358 }
359 case 256:
360 switch (MATH_BIGINTEGER_MODE) {
361 case self::MODE_GMP:
362 $sign = $this->is_negative ? '-' : '';
363 $this->value = gmp_init($sign . '0x' . bin2hex($x));
364 break;
366 // round $len to the nearest 4 (thanks, DavidMJ!)
367 $len = (strlen($x) + 3) & 0xFFFFFFFC;
368
369 $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
370
371 for ($i = 0; $i < $len; $i+= 4) {
372 $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
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);
374 }
375
376 if ($this->is_negative) {
377 $this->value = '-' . $this->value;
378 }
379
380 break;
381 // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
382 default:
383 while (strlen($x)) {
384 $this->value[] = $this->_bytes2int($this->_base256_rshift($x, self::$base));
385 }
386 }
387
388 if ($this->is_negative) {
389 if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
390 $this->is_negative = false;
391 }
392 $temp = $this->add(new static('-1'));
393 $this->value = $temp->value;
394 }
395 break;
396 case 16:
397 case -16:
398 if ($base > 0 && $x[0] == '-') {
399 $this->is_negative = true;
400 $x = substr($x, 1);
401 }
402
403 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
404
405 $is_negative = false;
406 if ($base < 0 && hexdec($x[0]) >= 8) {
407 $this->is_negative = $is_negative = true;
408 $x = bin2hex(~pack('H*', $x));
409 }
410
411 switch (MATH_BIGINTEGER_MODE) {
412 case self::MODE_GMP:
413 $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
414 $this->value = gmp_init($temp);
415 $this->is_negative = false;
416 break;
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;
422 break;
423 default:
424 $x = (strlen($x) & 1) ? '0' . $x : $x;
425 $temp = new static(pack('H*', $x), 256);
426 $this->value = $temp->value;
427 }
428
429 if ($is_negative) {
430 $temp = $this->add(new static('-1'));
431 $this->value = $temp->value;
432 }
433 break;
434 case 10:
435 case -10:
436 // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
437 // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
438 // [^-0-9].*: find any non-numeric characters and then any characters that follow that
439 $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
440
441 switch (MATH_BIGINTEGER_MODE) {
442 case self::MODE_GMP:
443 $this->value = gmp_init($x);
444 break;
446 // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
447 // results then doing it on '-1' does (modInverse does $x[0])
448 $this->value = $x === '-' ? '0' : (string) $x;
449 break;
450 default:
451 $temp = new static();
452
453 $multiplier = new static();
454 $multiplier->value = array(self::$max10);
455
456 if ($x[0] == '-') {
457 $this->is_negative = true;
458 $x = substr($x, 1);
459 }
460
461 $x = str_pad($x, strlen($x) + ((self::$max10Len - 1) * strlen($x)) % self::$max10Len, 0, STR_PAD_LEFT);
462 while (strlen($x)) {
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);
466 }
467
468 $this->value = $temp->value;
469 }
470 break;
471 case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
472 case -2:
473 if ($base > 0 && $x[0] == '-') {
474 $this->is_negative = true;
475 $x = substr($x, 1);
476 }
477
478 $x = preg_replace('#^([01]*).*#', '$1', $x);
479 $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
480
481 $str = '0x';
482 while (strlen($x)) {
483 $part = substr($x, 0, 4);
484 $str.= dechex(bindec($part));
485 $x = substr($x, 4);
486 }
487
488 if ($this->is_negative) {
489 $str = '-' . $str;
490 }
491
492 $temp = new static($str, 8 * $base); // ie. either -16 or +16
493 $this->value = $temp->value;
494 $this->is_negative = $temp->is_negative;
495
496 break;
497 default:
498 // base not supported, so we'll let $this == 0
499 }
500 }
501
522 function toBytes($twos_compliment = false)
523 {
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) : '';
528 }
529
530 $temp = $comparison < 0 ? $this->add(new static(1)) : $this->copy();
531 $bytes = $temp->toBytes();
532
533 if (empty($bytes)) { // eg. if the number we're trying to convert is -1
534 $bytes = chr(0);
535 }
536
537 if (ord($bytes[0]) & 0x80) {
538 $bytes = chr(0) . $bytes;
539 }
540
541 return $comparison < 0 ? ~$bytes : $bytes;
542 }
543
544 switch (MATH_BIGINTEGER_MODE) {
545 case self::MODE_GMP:
546 if (gmp_cmp($this->value, gmp_init(0)) == 0) {
547 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
548 }
549
550 $temp = gmp_strval(gmp_abs($this->value), 16);
551 $temp = (strlen($temp) & 1) ? '0' . $temp : $temp;
552 $temp = pack('H*', $temp);
553
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) : '';
560 }
561
562 $value = '';
564
565 if ($current[0] == '-') {
566 $current = substr($current, 1);
567 }
568
569 while (bccomp($current, '0', 0) > 0) {
570 $temp = bcmod($current, '16777216');
571 $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
572 $current = bcdiv($current, '16777216', 0);
573 }
574
575 return $this->precision > 0 ?
576 substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
577 ltrim($value, chr(0));
578 }
579
580 if (!count($this->value)) {
581 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
582 }
583 $result = $this->_int2bytes($this->value[count($this->value) - 1]);
584
585 $temp = $this->copy();
586
587 for ($i = count($temp->value) - 2; $i >= 0; --$i) {
588 $temp->_base256_lshift($result, self::$base);
589 $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
590 }
591
592 return $this->precision > 0 ?
593 str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
594 $result;
595 }
596
617 function toHex($twos_compliment = false)
618 {
619 return bin2hex($this->toBytes($twos_compliment));
620 }
621
642 function toBits($twos_compliment = false)
643 {
644 $hex = $this->toHex($twos_compliment);
645 $bits = '';
646 for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
647 $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits;
648 }
649 if ($start) { // hexdec('') == 0
650 $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits;
651 }
652 $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
653
654 if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) {
655 return '0' . $result;
656 }
657
658 return $result;
659 }
660
677 function toString()
678 {
679 switch (MATH_BIGINTEGER_MODE) {
680 case self::MODE_GMP:
681 return gmp_strval($this->value);
683 if ($this->value === '0') {
684 return '0';
685 }
686
687 return ltrim($this->value, '0');
688 }
689
690 if (!count($this->value)) {
691 return '0';
692 }
693
694 $temp = $this->copy();
695 $temp->is_negative = false;
696
697 $divisor = new static();
698 $divisor->value = array(self::$max10);
699 $result = '';
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;
703 }
704 $result = ltrim($result, '0');
705 if (empty($result)) {
706 $result = '0';
707 }
708
709 if ($this->is_negative) {
710 $result = '-' . $result;
711 }
712
713 return $result;
714 }
715
728 function copy()
729 {
730 $temp = new static();
731 $temp->value = $this->value;
732 $temp->is_negative = $this->is_negative;
733 $temp->precision = $this->precision;
734 $temp->bitmask = $this->bitmask;
735 return $temp;
736 }
737
747 function __toString()
748 {
749 return $this->toString();
750 }
751
764 function __clone()
765 {
766 return $this->copy();
767 }
768
777 function __sleep()
778 {
779 $this->hex = $this->toHex(true);
780 $vars = array('hex');
781 if ($this->precision > 0) {
782 $vars[] = 'precision';
783 }
784 return $vars;
785 }
786
795 function __wakeup()
796 {
797 $temp = new static($this->hex, -16);
798 $this->value = $temp->value;
799 $this->is_negative = $temp->is_negative;
800 if ($this->precision > 0) {
801 // recalculate $this->bitmask
802 $this->setPrecision($this->precision);
803 }
804 }
805
813 function __debugInfo()
814 {
815 $opts = array();
816 switch (MATH_BIGINTEGER_MODE) {
817 case self::MODE_GMP:
818 $engine = 'gmp';
819 break;
821 $engine = 'bcmath';
822 break;
824 $engine = 'internal';
825 $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit';
826 }
827 if (MATH_BIGINTEGER_MODE != self::MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
828 $opts[] = 'OpenSSL';
829 }
830 if (!empty($opts)) {
831 $engine.= ' (' . implode($opts, ', ') . ')';
832 }
833 return array(
834 'value' => '0x' . $this->toHex(true),
835 'engine' => $engine
836 );
837 }
838
859 function add($y)
860 {
861 switch (MATH_BIGINTEGER_MODE) {
862 case self::MODE_GMP:
863 $temp = new static();
864 $temp->value = gmp_add($this->value, $y->value);
865
866 return $this->_normalize($temp);
868 $temp = new static();
869 $temp->value = bcadd($this->value, $y->value, 0);
870
871 return $this->_normalize($temp);
872 }
873
874 $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
875
876 $result = new static();
877 $result->value = $temp[self::VALUE];
878 $result->is_negative = $temp[self::SIGN];
879
880 return $this->_normalize($result);
881 }
882
893 function _add($x_value, $x_negative, $y_value, $y_negative)
894 {
895 $x_size = count($x_value);
896 $y_size = count($y_value);
897
898 if ($x_size == 0) {
899 return array(
900 self::VALUE => $y_value,
901 self::SIGN => $y_negative
902 );
903 } elseif ($y_size == 0) {
904 return array(
905 self::VALUE => $x_value,
906 self::SIGN => $x_negative
907 );
908 }
909
910 // subtract, if appropriate
911 if ($x_negative != $y_negative) {
912 if ($x_value == $y_value) {
913 return array(
914 self::VALUE => array(),
915 self::SIGN => false
916 );
917 }
918
919 $temp = $this->_subtract($x_value, false, $y_value, false);
920 $temp[self::SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
921 $x_negative : $y_negative;
922
923 return $temp;
924 }
925
926 if ($x_size < $y_size) {
927 $size = $x_size;
928 $value = $y_value;
929 } else {
930 $size = $y_size;
931 $value = $x_value;
932 }
933
934 $value[count($value)] = 0; // just in case the carry adds an extra digit
935
936 $carry = 0;
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;
939 $carry = $sum >= self::$maxDigit2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
940 $sum = $carry ? $sum - self::$maxDigit2 : $sum;
941
942 $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
943
944 $value[$i] = (int) ($sum - self::$baseFull * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
945 $value[$j] = $temp;
946 }
947
948 if ($j == $size) { // ie. if $y_size is odd
949 $sum = $x_value[$i] + $y_value[$i] + $carry;
950 $carry = $sum >= self::$baseFull;
951 $value[$i] = $carry ? $sum - self::$baseFull : $sum;
952 ++$i; // ie. let $i = $j since we've just done $value[$i]
953 }
954
955 if ($carry) {
956 for (; $value[$i] == self::$maxDigit; ++$i) {
957 $value[$i] = 0;
958 }
959 ++$value[$i];
960 }
961
962 return array(
963 self::VALUE => $this->_trim($value),
964 self::SIGN => $x_negative
965 );
966 }
967
988 function subtract($y)
989 {
990 switch (MATH_BIGINTEGER_MODE) {
991 case self::MODE_GMP:
992 $temp = new static();
993 $temp->value = gmp_sub($this->value, $y->value);
994
995 return $this->_normalize($temp);
997 $temp = new static();
998 $temp->value = bcsub($this->value, $y->value, 0);
999
1000 return $this->_normalize($temp);
1001 }
1002
1003 $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
1004
1005 $result = new static();
1006 $result->value = $temp[self::VALUE];
1007 $result->is_negative = $temp[self::SIGN];
1008
1009 return $this->_normalize($result);
1010 }
1011
1022 function _subtract($x_value, $x_negative, $y_value, $y_negative)
1023 {
1024 $x_size = count($x_value);
1025 $y_size = count($y_value);
1026
1027 if ($x_size == 0) {
1028 return array(
1029 self::VALUE => $y_value,
1030 self::SIGN => !$y_negative
1031 );
1032 } elseif ($y_size == 0) {
1033 return array(
1034 self::VALUE => $x_value,
1035 self::SIGN => $x_negative
1036 );
1037 }
1038
1039 // add, if appropriate (ie. -$x - +$y or +$x - -$y)
1040 if ($x_negative != $y_negative) {
1041 $temp = $this->_add($x_value, false, $y_value, false);
1042 $temp[self::SIGN] = $x_negative;
1043
1044 return $temp;
1045 }
1046
1047 $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
1048
1049 if (!$diff) {
1050 return array(
1051 self::VALUE => array(),
1052 self::SIGN => false
1053 );
1054 }
1055
1056 // switch $x and $y around, if appropriate.
1057 if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
1058 $temp = $x_value;
1059 $x_value = $y_value;
1060 $y_value = $temp;
1061
1062 $x_negative = !$x_negative;
1063
1064 $x_size = count($x_value);
1065 $y_size = count($y_value);
1066 }
1067
1068 // at this point, $x_value should be at least as big as - if not bigger than - $y_value
1069
1070 $carry = 0;
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;
1073 $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
1074 $sum = $carry ? $sum + self::$maxDigit2 : $sum;
1075
1076 $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
1077
1078 $x_value[$i] = (int) ($sum - self::$baseFull * $temp);
1079 $x_value[$j] = $temp;
1080 }
1081
1082 if ($j == $y_size) { // ie. if $y_size is odd
1083 $sum = $x_value[$i] - $y_value[$i] - $carry;
1084 $carry = $sum < 0;
1085 $x_value[$i] = $carry ? $sum + self::$baseFull : $sum;
1086 ++$i;
1087 }
1088
1089 if ($carry) {
1090 for (; !$x_value[$i]; ++$i) {
1091 $x_value[$i] = self::$maxDigit;
1092 }
1093 --$x_value[$i];
1094 }
1095
1096 return array(
1097 self::VALUE => $this->_trim($x_value),
1098 self::SIGN => $x_negative
1099 );
1100 }
1101
1121 function multiply($x)
1122 {
1123 switch (MATH_BIGINTEGER_MODE) {
1124 case self::MODE_GMP:
1125 $temp = new static();
1126 $temp->value = gmp_mul($this->value, $x->value);
1127
1128 return $this->_normalize($temp);
1129 case self::MODE_BCMATH:
1130 $temp = new static();
1131 $temp->value = bcmul($this->value, $x->value, 0);
1132
1133 return $this->_normalize($temp);
1134 }
1135
1136 $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
1137
1138 $product = new static();
1139 $product->value = $temp[self::VALUE];
1140 $product->is_negative = $temp[self::SIGN];
1141
1142 return $this->_normalize($product);
1143 }
1144
1155 function _multiply($x_value, $x_negative, $y_value, $y_negative)
1156 {
1157 //if ( $x_value == $y_value ) {
1158 // return array(
1159 // self::VALUE => $this->_square($x_value),
1160 // self::SIGN => $x_sign != $y_value
1161 // );
1162 //}
1163
1164 $x_length = count($x_value);
1165 $y_length = count($y_value);
1166
1167 if (!$x_length || !$y_length) { // a 0 is being multiplied
1168 return array(
1169 self::VALUE => array(),
1170 self::SIGN => false
1171 );
1172 }
1173
1174 return array(
1175 self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ?
1176 $this->_trim($this->_regularMultiply($x_value, $y_value)) :
1177 $this->_trim($this->_karatsuba($x_value, $y_value)),
1178 self::SIGN => $x_negative != $y_negative
1179 );
1180 }
1181
1192 function _regularMultiply($x_value, $y_value)
1193 {
1194 $x_length = count($x_value);
1195 $y_length = count($y_value);
1196
1197 if (!$x_length || !$y_length) { // a 0 is being multiplied
1198 return array();
1199 }
1200
1201 if ($x_length < $y_length) {
1202 $temp = $x_value;
1203 $x_value = $y_value;
1204 $y_value = $temp;
1205
1206 $x_length = count($x_value);
1207 $y_length = count($y_value);
1208 }
1209
1210 $product_value = $this->_array_repeat(0, $x_length + $y_length);
1211
1212 // the following for loop could be removed if the for loop following it
1213 // (the one with nested for loops) initially set $i to 0, but
1214 // doing so would also make the result in one set of unnecessary adds,
1215 // since on the outermost loops first pass, $product->value[$k] is going
1216 // to always be 0
1217
1218 $carry = 0;
1219
1220 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
1221 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
1222 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1223 $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
1224 }
1225
1226 $product_value[$j] = $carry;
1227
1228 // the above for loop is what the previous comment was talking about. the
1229 // following for loop is the "one with nested for loops"
1230 for ($i = 1; $i < $y_length; ++$i) {
1231 $carry = 0;
1232
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);
1237 }
1238
1239 $product_value[$k] = $carry;
1240 }
1241
1242 return $product_value;
1243 }
1244
1256 function _karatsuba($x_value, $y_value)
1257 {
1258 $m = min(count($x_value) >> 1, count($y_value) >> 1);
1259
1260 if ($m < self::KARATSUBA_CUTOFF) {
1261 return $this->_regularMultiply($x_value, $y_value);
1262 }
1263
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);
1268
1269 $z2 = $this->_karatsuba($x1, $y1);
1270 $z0 = $this->_karatsuba($x0, $y0);
1271
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);
1277
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]);
1280
1281 $xy = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1282 $xy = $this->_add($xy[self::VALUE], $xy[self::SIGN], $z0, false);
1283
1284 return $xy[self::VALUE];
1285 }
1286
1294 function _square($x = false)
1295 {
1296 return count($x) < 2 * self::KARATSUBA_CUTOFF ?
1297 $this->_trim($this->_baseSquare($x)) :
1298 $this->_trim($this->_karatsubaSquare($x));
1299 }
1300
1312 function _baseSquare($value)
1313 {
1314 if (empty($value)) {
1315 return array();
1316 }
1317 $square_value = $this->_array_repeat(0, 2 * count($value));
1318
1319 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
1320 $i2 = $i << 1;
1321
1322 $temp = $square_value[$i2] + $value[$i] * $value[$i];
1323 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1324 $square_value[$i2] = (int) ($temp - self::$baseFull * $carry);
1325
1326 // note how we start from $i+1 instead of 0 as we do in multiplication.
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);
1331 }
1332
1333 // the following line can yield values larger 2**15. at this point, PHP should switch
1334 // over to floats.
1335 $square_value[$i + $max_index + 1] = $carry;
1336 }
1337
1338 return $square_value;
1339 }
1340
1352 {
1353 $m = count($value) >> 1;
1354
1355 if ($m < self::KARATSUBA_CUTOFF) {
1356 return $this->_baseSquare($value);
1357 }
1358
1359 $x1 = array_slice($value, $m);
1360 $x0 = array_slice($value, 0, $m);
1361
1362 $z2 = $this->_karatsubaSquare($x1);
1363 $z0 = $this->_karatsubaSquare($x0);
1364
1365 $z1 = $this->_add($x1, false, $x0, false);
1366 $z1 = $this->_karatsubaSquare($z1[self::VALUE]);
1367 $temp = $this->_add($z2, false, $z0, false);
1368 $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);
1369
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]);
1372
1373 $xx = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1374 $xx = $this->_add($xx[self::VALUE], $xx[self::SIGN], $z0, false);
1375
1376 return $xx[self::VALUE];
1377 }
1378
1406 function divide($y)
1407 {
1408 switch (MATH_BIGINTEGER_MODE) {
1409 case self::MODE_GMP:
1410 $quotient = new static();
1411 $remainder = new static();
1412
1413 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
1414
1415 if (gmp_sign($remainder->value) < 0) {
1416 $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
1417 }
1418
1419 return array($this->_normalize($quotient), $this->_normalize($remainder));
1420 case self::MODE_BCMATH:
1421 $quotient = new static();
1422 $remainder = new static();
1423
1424 $quotient->value = bcdiv($this->value, $y->value, 0);
1425 $remainder->value = bcmod($this->value, $y->value);
1426
1427 if ($remainder->value[0] == '-') {
1428 $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
1429 }
1430
1431 return array($this->_normalize($quotient), $this->_normalize($remainder));
1432 }
1433
1434 if (count($y->value) == 1) {
1435 list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
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;
1441 return array($this->_normalize($quotient), $this->_normalize($remainder));
1442 }
1443
1444 static $zero;
1445 if (!isset($zero)) {
1446 $zero = new static();
1447 }
1448
1449 $x = $this->copy();
1450 $y = $y->copy();
1451
1452 $x_sign = $x->is_negative;
1453 $y_sign = $y->is_negative;
1454
1455 $x->is_negative = $y->is_negative = false;
1456
1457 $diff = $x->compare($y);
1458
1459 if (!$diff) {
1460 $temp = new static();
1461 $temp->value = array(1);
1462 $temp->is_negative = $x_sign != $y_sign;
1463 return array($this->_normalize($temp), $this->_normalize(new static()));
1464 }
1465
1466 if ($diff < 0) {
1467 // if $x is negative, "add" $y.
1468 if ($x_sign) {
1469 $x = $y->subtract($x);
1470 }
1471 return array($this->_normalize(new static()), $this->_normalize($x));
1472 }
1473
1474 // normalize $x and $y as described in HAC 14.23 / 14.24
1475 $msb = $y->value[count($y->value) - 1];
1476 for ($shift = 0; !($msb & self::$msb); ++$shift) {
1477 $msb <<= 1;
1478 }
1479 $x->_lshift($shift);
1480 $y->_lshift($shift);
1481 $y_value = &$y->value;
1482
1483 $x_max = count($x->value) - 1;
1484 $y_max = count($y->value) - 1;
1485
1486 $quotient = new static();
1487 $quotient_value = &$quotient->value;
1488 $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
1489
1490 static $temp, $lhs, $rhs;
1491 if (!isset($temp)) {
1492 $temp = new static();
1493 $lhs = new static();
1494 $rhs = new static();
1495 }
1496 $temp_value = &$temp->value;
1497 $rhs_value = &$rhs->value;
1498
1499 // $temp = $y << ($x_max - $y_max-1) in base 2**26
1500 $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
1501
1502 while ($x->compare($temp) >= 0) {
1503 // calculate the "common residue"
1504 ++$quotient_value[$x_max - $y_max];
1505 $x = $x->subtract($temp);
1506 $x_max = count($x->value) - 1;
1507 }
1508
1509 for ($i = $x_max; $i >= $y_max + 1; --$i) {
1510 $x_value = &$x->value;
1511 $x_window = array(
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
1515 );
1516 $y_window = array(
1517 $y_value[$y_max],
1518 ($y_max > 0) ? $y_value[$y_max - 1] : 0
1519 );
1520
1521 $q_index = $i - $y_max - 1;
1522 if ($x_window[0] == $y_window[0]) {
1523 $quotient_value[$q_index] = self::$maxDigit;
1524 } else {
1525 $quotient_value[$q_index] = $this->_safe_divide(
1526 $x_window[0] * self::$baseFull + $x_window[1],
1527 $y_window[0]
1528 );
1529 }
1530
1531 $temp_value = array($y_window[1], $y_window[0]);
1532
1533 $lhs->value = array($quotient_value[$q_index]);
1534 $lhs = $lhs->multiply($temp);
1535
1536 $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
1537
1538 while ($lhs->compare($rhs) > 0) {
1539 --$quotient_value[$q_index];
1540
1541 $lhs->value = array($quotient_value[$q_index]);
1542 $lhs = $lhs->multiply($temp);
1543 }
1544
1545 $adjust = $this->_array_repeat(0, $q_index);
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);
1550
1551 $x = $x->subtract($temp);
1552
1553 if ($x->compare($zero) < 0) {
1554 $temp_value = array_merge($adjust, $y_value);
1555 $x = $x->add($temp);
1556
1557 --$quotient_value[$q_index];
1558 }
1559
1560 $x_max = count($x_value) - 1;
1561 }
1562
1563 // unnormalize the remainder
1564 $x->_rshift($shift);
1565
1566 $quotient->is_negative = $x_sign != $y_sign;
1567
1568 // calculate the "common residue", if appropriate
1569 if ($x_sign) {
1570 $y->_rshift($shift);
1571 $x = $y->subtract($x);
1572 }
1573
1574 return array($this->_normalize($quotient), $this->_normalize($x));
1575 }
1576
1587 function _divide_digit($dividend, $divisor)
1588 {
1589 $carry = 0;
1590 $result = array();
1591
1592 for ($i = count($dividend) - 1; $i >= 0; --$i) {
1593 $temp = self::$baseFull * $carry + $dividend[$i];
1594 $result[$i] = $this->_safe_divide($temp, $divisor);
1595 $carry = (int) ($temp - $divisor * $result[$i]);
1596 }
1597
1598 return array($result, $carry);
1599 }
1600
1641 function modPow($e, $n)
1642 {
1643 $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
1644
1645 if ($e->compare(new static()) < 0) {
1646 $e = $e->abs();
1647
1648 $temp = $this->modInverse($n);
1649 if ($temp === false) {
1650 return false;
1651 }
1652
1653 return $this->_normalize($temp->modPow($e, $n));
1654 }
1655
1656 if (MATH_BIGINTEGER_MODE == self::MODE_GMP) {
1657 $temp = new static();
1658 $temp->value = gmp_powm($this->value, $e->value, $n->value);
1659
1660 return $this->_normalize($temp);
1661 }
1662
1663 if ($this->compare(new static()) < 0 || $this->compare($n) > 0) {
1664 list(, $temp) = $this->divide($n);
1665 return $temp->modPow($e, $n);
1666 }
1667
1668 if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
1669 $components = array(
1670 'modulus' => $n->toBytes(true),
1671 'publicExponent' => $e->toBytes(true)
1672 );
1673
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'])
1677 );
1678
1679 $RSAPublicKey = pack(
1680 'Ca*a*a*',
1681 48,
1682 $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
1683 $components['modulus'],
1684 $components['publicExponent']
1685 );
1686
1687 $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
1688 $RSAPublicKey = chr(0) . $RSAPublicKey;
1689 $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
1690
1691 $encapsulated = pack(
1692 'Ca*a*',
1693 48,
1694 $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)),
1695 $rsaOID . $RSAPublicKey
1696 );
1697
1698 $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
1699 chunk_split(base64_encode($encapsulated)) .
1700 '-----END PUBLIC KEY-----';
1701
1702 $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
1703
1704 if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
1705 return new static($result, 256);
1706 }
1707 }
1708
1709 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
1710 $temp = new static();
1711 $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
1712
1713 return $this->_normalize($temp);
1714 }
1715
1716 if (empty($e->value)) {
1717 $temp = new static();
1718 $temp->value = array(1);
1719 return $this->_normalize($temp);
1720 }
1721
1722 if ($e->value == array(1)) {
1723 list(, $temp) = $this->divide($n);
1724 return $this->_normalize($temp);
1725 }
1726
1727 if ($e->value == array(2)) {
1728 $temp = new static();
1729 $temp->value = $this->_square($this->value);
1730 list(, $temp) = $temp->divide($n);
1731 return $this->_normalize($temp);
1732 }
1733
1734 return $this->_normalize($this->_slidingWindow($e, $n, self::BARRETT));
1735
1736 // the following code, although not callable, can be run independently of the above code
1737 // although the above code performed better in my benchmarks the following could might
1738 // perform better under different circumstances. in lieu of deleting it it's just been
1739 // made uncallable
1740
1741 // is the modulo odd?
1742 if ($n->value[0] & 1) {
1743 return $this->_normalize($this->_slidingWindow($e, $n, self::MONTGOMERY));
1744 }
1745 // if it's not, it's even
1746
1747 // find the lowest set bit (eg. the max pow of 2 that divides $n)
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;
1752 $j+= 26 * $i;
1753 break;
1754 }
1755 }
1756 // at this point, 2^$j * $n/(2^$j) == $n
1757
1758 $mod1 = $n->copy();
1759 $mod1->_rshift($j);
1760 $mod2 = new static();
1761 $mod2->value = array(1);
1762 $mod2->_lshift($j);
1763
1764 $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, self::MONTGOMERY) : new static();
1765 $part2 = $this->_slidingWindow($e, $mod2, self::POWEROF2);
1766
1767 $y1 = $mod2->modInverse($mod1);
1768 $y2 = $mod1->modInverse($mod2);
1769
1770 $result = $part1->multiply($mod2);
1771 $result = $result->multiply($y1);
1772
1773 $temp = $part2->multiply($mod1);
1774 $temp = $temp->multiply($y2);
1775
1776 $result = $result->add($temp);
1777 list(, $result) = $result->divide($n);
1778
1779 return $this->_normalize($result);
1780 }
1781
1792 function powMod($e, $n)
1793 {
1794 return $this->modPow($e, $n);
1795 }
1796
1811 function _slidingWindow($e, $n, $mode)
1812 {
1813 static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
1814 //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
1815
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);
1821 }
1822
1823 $e_length = strlen($e_bits);
1824
1825 // calculate the appropriate window size.
1826 // $window_size == 3 if $window_ranges is between 25 and 81, for example.
1827 for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); ++$window_size, ++$i) {
1828 }
1829
1830 $n_value = $n->value;
1831
1832 // precompute $this^0 through $this^$window_size
1833 $powers = array();
1834 $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
1835 $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
1836
1837 // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
1838 // in a 1. ie. it's supposed to be odd.
1839 $temp = 1 << ($window_size - 1);
1840 for ($i = 1; $i < $temp; ++$i) {
1841 $i2 = $i << 1;
1842 $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
1843 }
1844
1845 $result = array(1);
1846 $result = $this->_prepareReduce($result, $n_value, $mode);
1847
1848 for ($i = 0; $i < $e_length;) {
1849 if (!$e_bits[$i]) {
1850 $result = $this->_squareReduce($result, $n_value, $mode);
1851 ++$i;
1852 } else {
1853 for ($j = $window_size - 1; $j > 0; --$j) {
1854 if (!empty($e_bits[$i + $j])) {
1855 break;
1856 }
1857 }
1858
1859 // eg. the length of substr($e_bits, $i, $j + 1)
1860 for ($k = 0; $k <= $j; ++$k) {
1861 $result = $this->_squareReduce($result, $n_value, $mode);
1862 }
1863
1864 $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
1865
1866 $i += $j + 1;
1867 }
1868 }
1869
1870 $temp = new static();
1871 $temp->value = $this->_reduce($result, $n_value, $mode);
1872
1873 return $temp;
1874 }
1875
1888 function _reduce($x, $n, $mode)
1889 {
1890 switch ($mode) {
1891 case self::MONTGOMERY:
1892 return $this->_montgomery($x, $n);
1893 case self::BARRETT:
1894 return $this->_barrett($x, $n);
1895 case self::POWEROF2:
1896 $lhs = new static();
1897 $lhs->value = $x;
1898 $rhs = new static();
1899 $rhs->value = $n;
1900 return $x->_mod2($n);
1901 case self::CLASSIC:
1902 $lhs = new static();
1903 $lhs->value = $x;
1904 $rhs = new static();
1905 $rhs->value = $n;
1906 list(, $temp) = $lhs->divide($rhs);
1907 return $temp->value;
1908 case self::NONE:
1909 return $x;
1910 default:
1911 // an invalid $mode was provided
1912 }
1913 }
1914
1925 function _prepareReduce($x, $n, $mode)
1926 {
1927 if ($mode == self::MONTGOMERY) {
1928 return $this->_prepMontgomery($x, $n);
1929 }
1930 return $this->_reduce($x, $n, $mode);
1931 }
1932
1944 function _multiplyReduce($x, $y, $n, $mode)
1945 {
1946 if ($mode == self::MONTGOMERY) {
1947 return $this->_montgomeryMultiply($x, $y, $n);
1948 }
1949 $temp = $this->_multiply($x, false, $y, false);
1950 return $this->_reduce($temp[self::VALUE], $n, $mode);
1951 }
1952
1963 function _squareReduce($x, $n, $mode)
1964 {
1965 if ($mode == self::MONTGOMERY) {
1966 return $this->_montgomeryMultiply($x, $x, $n);
1967 }
1968 return $this->_reduce($this->_square($x), $n, $mode);
1969 }
1970
1982 function _mod2($n)
1983 {
1984 $temp = new static();
1985 $temp->value = array(1);
1986 return $this->bitwise_and($n->subtract($temp));
1987 }
1988
2013 function _barrett($n, $m)
2014 {
2015 static $cache = array(
2016 self::VARIABLE => array(),
2017 self::DATA => array()
2018 );
2019
2020 $m_length = count($m);
2021
2022 // if ($this->_compare($n, $this->_square($m)) >= 0) {
2023 if (count($n) > 2 * $m_length) {
2024 $lhs = new static();
2025 $rhs = new static();
2026 $lhs->value = $n;
2027 $rhs->value = $m;
2028 list(, $temp) = $lhs->divide($rhs);
2029 return $temp->value;
2030 }
2031
2032 // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
2033 if ($m_length < 5) {
2034 return $this->_regularBarrett($n, $m);
2035 }
2036
2037 // n = 2 * m.length
2038
2039 if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
2040 $key = count($cache[self::VARIABLE]);
2041 $cache[self::VARIABLE][] = $m;
2042
2043 $lhs = new static();
2044 $lhs_value = &$lhs->value;
2045 $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
2046 $lhs_value[] = 1;
2047 $rhs = new static();
2048 $rhs->value = $m;
2049
2050 list($u, $m1) = $lhs->divide($rhs);
2051 $u = $u->value;
2052 $m1 = $m1->value;
2053
2054 $cache[self::DATA][] = array(
2055 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
2056 'm1'=> $m1 // m.length
2057 );
2058 } else {
2059 extract($cache[self::DATA][$key]);
2060 }
2061
2062 $cutoff = $m_length + ($m_length >> 1);
2063 $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
2064 $msd = array_slice($n, $cutoff); // m.length >> 1
2065 $lsd = $this->_trim($lsd);
2066 $temp = $this->_multiply($msd, false, $m1, false);
2067 $n = $this->_add($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1
2068
2069 if ($m_length & 1) {
2070 return $this->_regularBarrett($n[self::VALUE], $m);
2071 }
2072
2073 // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
2074 $temp = array_slice($n[self::VALUE], $m_length - 1);
2075 // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
2076 // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
2077 $temp = $this->_multiply($temp, false, $u, false);
2078 // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
2079 // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
2080 $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1);
2081 // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
2082 // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1)
2083 $temp = $this->_multiply($temp, false, $m, false);
2084
2085 // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
2086 // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop
2087 // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
2088
2089 $result = $this->_subtract($n[self::VALUE], false, $temp[self::VALUE], false);
2090
2091 while ($this->_compare($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) {
2092 $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $m, false);
2093 }
2094
2095 return $result[self::VALUE];
2096 }
2097
2111 {
2112 static $cache = array(
2113 self::VARIABLE => array(),
2114 self::DATA => array()
2115 );
2116
2117 $n_length = count($n);
2118
2119 if (count($x) > 2 * $n_length) {
2120 $lhs = new static();
2121 $rhs = new static();
2122 $lhs->value = $x;
2123 $rhs->value = $n;
2124 list(, $temp) = $lhs->divide($rhs);
2125 return $temp->value;
2126 }
2127
2128 if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
2129 $key = count($cache[self::VARIABLE]);
2130 $cache[self::VARIABLE][] = $n;
2131 $lhs = new static();
2132 $lhs_value = &$lhs->value;
2133 $lhs_value = $this->_array_repeat(0, 2 * $n_length);
2134 $lhs_value[] = 1;
2135 $rhs = new static();
2136 $rhs->value = $n;
2137 list($temp, ) = $lhs->divide($rhs); // m.length
2138 $cache[self::DATA][] = $temp->value;
2139 }
2140
2141 // 2 * m.length - (m.length - 1) = m.length + 1
2142 $temp = array_slice($x, $n_length - 1);
2143 // (m.length + 1) + m.length = 2 * m.length + 1
2144 $temp = $this->_multiply($temp, false, $cache[self::DATA][$key], false);
2145 // (2 * m.length + 1) - (m.length - 1) = m.length + 2
2146 $temp = array_slice($temp[self::VALUE], $n_length + 1);
2147
2148 // m.length + 1
2149 $result = array_slice($x, 0, $n_length + 1);
2150 // m.length + 1
2151 $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
2152 // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
2153
2154 if ($this->_compare($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
2155 $corrector_value = $this->_array_repeat(0, $n_length + 1);
2156 $corrector_value[count($corrector_value)] = 1;
2157 $result = $this->_add($result, false, $corrector_value, false);
2159 }
2160
2161 // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
2162 $result = $this->_subtract($result, false, $temp[self::VALUE], $temp[self::SIGN]);
2163 while ($this->_compare($result[self::VALUE], $result[self::SIGN], $n, false) > 0) {
2164 $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $n, false);
2165 }
2166
2167 return $result[self::VALUE];
2168 }
2169
2184 function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
2185 {
2186 $x_length = count($x_value);
2187 $y_length = count($y_value);
2188
2189 if (!$x_length || !$y_length) { // a 0 is being multiplied
2190 return array(
2191 self::VALUE => array(),
2192 self::SIGN => false
2193 );
2194 }
2195
2196 if ($x_length < $y_length) {
2197 $temp = $x_value;
2198 $x_value = $y_value;
2199 $y_value = $temp;
2200
2201 $x_length = count($x_value);
2202 $y_length = count($y_value);
2203 }
2204
2205 $product_value = $this->_array_repeat(0, $x_length + $y_length);
2206
2207 // the following for loop could be removed if the for loop following it
2208 // (the one with nested for loops) initially set $i to 0, but
2209 // doing so would also make the result in one set of unnecessary adds,
2210 // since on the outermost loops first pass, $product->value[$k] is going
2211 // to always be 0
2212
2213 $carry = 0;
2214
2215 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
2216 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
2217 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2218 $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
2219 }
2220
2221 if ($j < $stop) {
2222 $product_value[$j] = $carry;
2223 }
2224
2225 // the above for loop is what the previous comment was talking about. the
2226 // following for loop is the "one with nested for loops"
2227
2228 for ($i = 1; $i < $y_length; ++$i) {
2229 $carry = 0;
2230
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);
2235 }
2236
2237 if ($k < $stop) {
2238 $product_value[$k] = $carry;
2239 }
2240 }
2241
2242 return array(
2243 self::VALUE => $this->_trim($product_value),
2244 self::SIGN => $x_negative != $y_negative
2245 );
2246 }
2247
2263 function _montgomery($x, $n)
2264 {
2265 static $cache = array(
2266 self::VARIABLE => array(),
2267 self::DATA => array()
2268 );
2269
2270 if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
2271 $key = count($cache[self::VARIABLE]);
2272 $cache[self::VARIABLE][] = $x;
2273 $cache[self::DATA][] = $this->_modInverse67108864($n);
2274 }
2275
2276 $k = count($n);
2277
2278 $result = array(self::VALUE => $x);
2279
2280 for ($i = 0; $i < $k; ++$i) {
2281 $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key];
2282 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2283 $temp = $this->_regularMultiply(array($temp), $n);
2284 $temp = array_merge($this->_array_repeat(0, $i), $temp);
2285 $result = $this->_add($result[self::VALUE], false, $temp, false);
2286 }
2287
2288 $result[self::VALUE] = array_slice($result[self::VALUE], $k);
2289
2290 if ($this->_compare($result, false, $n, false) >= 0) {
2291 $result = $this->_subtract($result[self::VALUE], false, $n, false);
2292 }
2293
2294 return $result[self::VALUE];
2295 }
2296
2312 {
2313 $temp = $this->_multiply($x, false, $y, false);
2314 return $this->_montgomery($temp[self::VALUE], $m);
2315
2316 // the following code, although not callable, can be run independently of the above code
2317 // although the above code performed better in my benchmarks the following could might
2318 // perform better under different circumstances. in lieu of deleting it it's just been
2319 // made uncallable
2320
2321 static $cache = array(
2322 self::VARIABLE => array(),
2323 self::DATA => array()
2324 );
2325
2326 if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
2327 $key = count($cache[self::VARIABLE]);
2328 $cache[self::VARIABLE][] = $m;
2329 $cache[self::DATA][] = $this->_modInverse67108864($m);
2330 }
2331
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);
2336 $a = array(self::VALUE => $this->_array_repeat(0, $n + 1));
2337 for ($i = 0; $i < $n; ++$i) {
2338 $temp = $a[self::VALUE][0] + $x[$i] * $y[0];
2339 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2340 $temp = $temp * $cache[self::DATA][$key];
2341 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2342 $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
2343 $a = $this->_add($a[self::VALUE], false, $temp[self::VALUE], false);
2344 $a[self::VALUE] = array_slice($a[self::VALUE], 1);
2345 }
2346 if ($this->_compare($a[self::VALUE], false, $m, false) >= 0) {
2347 $a = $this->_subtract($a[self::VALUE], false, $m, false);
2348 }
2349 return $a[self::VALUE];
2350 }
2351
2363 {
2364 $lhs = new static();
2365 $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
2366 $rhs = new static();
2367 $rhs->value = $n;
2368
2369 list(, $temp) = $lhs->divide($rhs);
2370 return $temp->value;
2371 }
2372
2399 function _modInverse67108864($x) // 2**26 == 67,108,864
2400 {
2401 $x = -$x[0];
2402 $result = $x & 0x3; // x**-1 mod 2**2
2403 $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
2404 $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8
2405 $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
2406 $result = fmod($result * (2 - fmod($x * $result, self::$baseFull)), self::$baseFull); // x**-1 mod 2**26
2407 return $result & self::$maxDigit;
2408 }
2409
2437 function modInverse($n)
2438 {
2439 switch (MATH_BIGINTEGER_MODE) {
2440 case self::MODE_GMP:
2441 $temp = new static();
2442 $temp->value = gmp_invert($this->value, $n->value);
2443
2444 return ($temp->value === false) ? false : $this->_normalize($temp);
2445 }
2446
2447 static $zero, $one;
2448 if (!isset($zero)) {
2449 $zero = new static();
2450 $one = new static(1);
2451 }
2452
2453 // $x mod -$n == $x mod $n.
2454 $n = $n->abs();
2455
2456 if ($this->compare($zero) < 0) {
2457 $temp = $this->abs();
2458 $temp = $temp->modInverse($n);
2459 return $this->_normalize($n->subtract($temp));
2460 }
2461
2462 extract($this->extendedGCD($n));
2463
2464 if (!$gcd->equals($one)) {
2465 return false;
2466 }
2467
2468 $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
2469
2470 return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
2471 }
2472
2501 function extendedGCD($n)
2502 {
2503 switch (MATH_BIGINTEGER_MODE) {
2504 case self::MODE_GMP:
2505 extract(gmp_gcdext($this->value, $n->value));
2506
2507 return array(
2508 'gcd' => $this->_normalize(new static($g)),
2509 'x' => $this->_normalize(new static($s)),
2510 'y' => $this->_normalize(new static($t))
2511 );
2512 case self::MODE_BCMATH:
2513 // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
2514 // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is,
2515 // the basic extended euclidean algorithim is what we're using.
2516
2517 $u = $this->value;
2518 $v = $n->value;
2519
2520 $a = '1';
2521 $b = '0';
2522 $c = '0';
2523 $d = '1';
2524
2525 while (bccomp($v, '0', 0) != 0) {
2526 $q = bcdiv($u, $v, 0);
2527
2528 $temp = $u;
2529 $u = $v;
2530 $v = bcsub($temp, bcmul($v, $q, 0), 0);
2531
2532 $temp = $a;
2533 $a = $c;
2534 $c = bcsub($temp, bcmul($a, $q, 0), 0);
2535
2536 $temp = $b;
2537 $b = $d;
2538 $d = bcsub($temp, bcmul($b, $q, 0), 0);
2539 }
2540
2541 return array(
2542 'gcd' => $this->_normalize(new static($u)),
2543 'x' => $this->_normalize(new static($a)),
2544 'y' => $this->_normalize(new static($b))
2545 );
2546 }
2547
2548 $y = $n->copy();
2549 $x = $this->copy();
2550 $g = new static();
2551 $g->value = array(1);
2552
2553 while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) {
2554 $x->_rshift(1);
2555 $y->_rshift(1);
2556 $g->_lshift(1);
2557 }
2558
2559 $u = $x->copy();
2560 $v = $y->copy();
2561
2562 $a = new static();
2563 $b = new static();
2564 $c = new static();
2565 $d = new static();
2566
2567 $a->value = $d->value = $g->value = array(1);
2568 $b->value = $c->value = array();
2569
2570 while (!empty($u->value)) {
2571 while (!($u->value[0] & 1)) {
2572 $u->_rshift(1);
2573 if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
2574 $a = $a->add($y);
2575 $b = $b->subtract($x);
2576 }
2577 $a->_rshift(1);
2578 $b->_rshift(1);
2579 }
2580
2581 while (!($v->value[0] & 1)) {
2582 $v->_rshift(1);
2583 if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) {
2584 $c = $c->add($y);
2585 $d = $d->subtract($x);
2586 }
2587 $c->_rshift(1);
2588 $d->_rshift(1);
2589 }
2590
2591 if ($u->compare($v) >= 0) {
2592 $u = $u->subtract($v);
2593 $a = $a->subtract($c);
2594 $b = $b->subtract($d);
2595 } else {
2596 $v = $v->subtract($u);
2597 $c = $c->subtract($a);
2598 $d = $d->subtract($b);
2599 }
2600 }
2601
2602 return array(
2603 'gcd' => $this->_normalize($g->multiply($v)),
2604 'x' => $this->_normalize($c),
2605 'y' => $this->_normalize($d)
2606 );
2607 }
2608
2630 function gcd($n)
2631 {
2632 extract($this->extendedGCD($n));
2633 return $gcd;
2634 }
2635
2642 function abs()
2643 {
2644 $temp = new static();
2645
2646 switch (MATH_BIGINTEGER_MODE) {
2647 case self::MODE_GMP:
2648 $temp->value = gmp_abs($this->value);
2649 break;
2650 case self::MODE_BCMATH:
2651 $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
2652 break;
2653 default:
2654 $temp->value = $this->value;
2655 }
2656
2657 return $temp;
2658 }
2659
2678 function compare($y)
2679 {
2680 switch (MATH_BIGINTEGER_MODE) {
2681 case self::MODE_GMP:
2682 return gmp_cmp($this->value, $y->value);
2683 case self::MODE_BCMATH:
2684 return bccomp($this->value, $y->value, 0);
2685 }
2686
2687 return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
2688 }
2689
2701 function _compare($x_value, $x_negative, $y_value, $y_negative)
2702 {
2703 if ($x_negative != $y_negative) {
2704 return (!$x_negative && $y_negative) ? 1 : -1;
2705 }
2706
2707 $result = $x_negative ? -1 : 1;
2708
2709 if (count($x_value) != count($y_value)) {
2710 return (count($x_value) > count($y_value)) ? $result : -$result;
2711 }
2712 $size = max(count($x_value), count($y_value));
2713
2714 $x_value = array_pad($x_value, $size, 0);
2715 $y_value = array_pad($y_value, $size, 0);
2716
2717 for ($i = count($x_value) - 1; $i >= 0; --$i) {
2718 if ($x_value[$i] != $y_value[$i]) {
2719 return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
2720 }
2721 }
2722
2723 return 0;
2724 }
2725
2736 function equals($x)
2737 {
2738 switch (MATH_BIGINTEGER_MODE) {
2739 case self::MODE_GMP:
2740 return gmp_cmp($this->value, $x->value) == 0;
2741 default:
2742 return $this->value === $x->value && $this->is_negative == $x->is_negative;
2743 }
2744 }
2745
2755 function setPrecision($bits)
2756 {
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);
2760 } else {
2761 $this->bitmask = new static(bcpow('2', $bits, 0));
2762 }
2763
2764 $temp = $this->_normalize($this);
2765 $this->value = $temp->value;
2766 }
2767
2776 function bitwise_and($x)
2777 {
2778 switch (MATH_BIGINTEGER_MODE) {
2779 case self::MODE_GMP:
2780 $temp = new static();
2781 $temp->value = gmp_and($this->value, $x->value);
2782
2783 return $this->_normalize($temp);
2784 case self::MODE_BCMATH:
2785 $left = $this->toBytes();
2786 $right = $x->toBytes();
2787
2788 $length = max(strlen($left), strlen($right));
2789
2790 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2791 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2792
2793 return $this->_normalize(new static($left & $right, 256));
2794 }
2795
2796 $result = $this->copy();
2797
2798 $length = min(count($x->value), count($this->value));
2799
2800 $result->value = array_slice($result->value, 0, $length);
2801
2802 for ($i = 0; $i < $length; ++$i) {
2803 $result->value[$i]&= $x->value[$i];
2804 }
2805
2806 return $this->_normalize($result);
2807 }
2808
2817 function bitwise_or($x)
2818 {
2819 switch (MATH_BIGINTEGER_MODE) {
2820 case self::MODE_GMP:
2821 $temp = new static();
2822 $temp->value = gmp_or($this->value, $x->value);
2823
2824 return $this->_normalize($temp);
2825 case self::MODE_BCMATH:
2826 $left = $this->toBytes();
2827 $right = $x->toBytes();
2828
2829 $length = max(strlen($left), strlen($right));
2830
2831 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2832 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2833
2834 return $this->_normalize(new static($left | $right, 256));
2835 }
2836
2837 $length = max(count($this->value), count($x->value));
2838 $result = $this->copy();
2839 $result->value = array_pad($result->value, $length, 0);
2840 $x->value = array_pad($x->value, $length, 0);
2841
2842 for ($i = 0; $i < $length; ++$i) {
2843 $result->value[$i]|= $x->value[$i];
2844 }
2845
2846 return $this->_normalize($result);
2847 }
2848
2857 function bitwise_xor($x)
2858 {
2859 switch (MATH_BIGINTEGER_MODE) {
2860 case self::MODE_GMP:
2861 $temp = new static();
2862 $temp->value = gmp_xor($this->value, $x->value);
2863
2864 return $this->_normalize($temp);
2865 case self::MODE_BCMATH:
2866 $left = $this->toBytes();
2867 $right = $x->toBytes();
2868
2869 $length = max(strlen($left), strlen($right));
2870
2871 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2872 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2873
2874 return $this->_normalize(new static($left ^ $right, 256));
2875 }
2876
2877 $length = max(count($this->value), count($x->value));
2878 $result = $this->copy();
2879 $result->value = array_pad($result->value, $length, 0);
2880 $x->value = array_pad($x->value, $length, 0);
2881
2882 for ($i = 0; $i < $length; ++$i) {
2883 $result->value[$i]^= $x->value[$i];
2884 }
2885
2886 return $this->_normalize($result);
2887 }
2888
2896 function bitwise_not()
2897 {
2898 // calculuate "not" without regard to $this->precision
2899 // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0)
2900 $temp = $this->toBytes();
2901 if ($temp == '') {
2902 return '';
2903 }
2904 $pre_msb = decbin(ord($temp[0]));
2905 $temp = ~$temp;
2906 $msb = decbin(ord($temp[0]));
2907 if (strlen($msb) == 8) {
2908 $msb = substr($msb, strpos($msb, '0'));
2909 }
2910 $temp[0] = chr(bindec($msb));
2911
2912 // see if we need to add extra leading 1's
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));
2917 }
2918
2919 // generate as many leading 1's as we need to.
2920 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
2921 $this->_base256_lshift($leading_ones, $current_bits);
2922
2923 $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
2924
2925 return $this->_normalize(new static($leading_ones | $temp, 256));
2926 }
2927
2938 function bitwise_rightShift($shift)
2939 {
2940 $temp = new static();
2941
2942 switch (MATH_BIGINTEGER_MODE) {
2943 case self::MODE_GMP:
2944 static $two;
2945
2946 if (!isset($two)) {
2947 $two = gmp_init('2');
2948 }
2949
2950 $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
2951
2952 break;
2953 case self::MODE_BCMATH:
2954 $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
2955
2956 break;
2957 default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
2958 // and I don't want to do that...
2959 $temp->value = $this->value;
2960 $temp->_rshift($shift);
2961 }
2962
2963 return $this->_normalize($temp);
2964 }
2965
2976 function bitwise_leftShift($shift)
2977 {
2978 $temp = new static();
2979
2980 switch (MATH_BIGINTEGER_MODE) {
2981 case self::MODE_GMP:
2982 static $two;
2983
2984 if (!isset($two)) {
2985 $two = gmp_init('2');
2986 }
2987
2988 $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
2989
2990 break;
2991 case self::MODE_BCMATH:
2992 $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
2993
2994 break;
2995 default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
2996 // and I don't want to do that...
2997 $temp->value = $this->value;
2998 $temp->_lshift($shift);
2999 }
3000
3001 return $this->_normalize($temp);
3002 }
3003
3013 function bitwise_leftRotate($shift)
3014 {
3015 $bits = $this->toBytes();
3016
3017 if ($this->precision > 0) {
3019 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
3020 $mask = $this->bitmask->subtract(new static(1));
3021 $mask = $mask->toBytes();
3022 } else {
3023 $mask = $this->bitmask->toBytes();
3024 }
3025 } else {
3026 $temp = ord($bits[0]);
3027 for ($i = 0; $temp >> $i; ++$i) {
3028 }
3029 $precision = 8 * strlen($bits) - 8 + $i;
3030 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
3031 }
3032
3033 if ($shift < 0) {
3034 $shift+= $precision;
3035 }
3036 $shift%= $precision;
3037
3038 if (!$shift) {
3039 return $this->copy();
3040 }
3041
3042 $left = $this->bitwise_leftShift($shift);
3043 $left = $left->bitwise_and(new static($mask, 256));
3044 $right = $this->bitwise_rightShift($precision - $shift);
3045 $result = MATH_BIGINTEGER_MODE != self::MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
3046 return $this->_normalize($result);
3047 }
3048
3058 function bitwise_rightRotate($shift)
3059 {
3060 return $this->bitwise_leftRotate(-$shift);
3061 }
3062
3073 {
3074 if (class_exists('\phpseclib\Crypt\Random')) {
3075 $random = Random::string($size);
3076 } else {
3077 $random = '';
3078
3079 if ($size & 1) {
3080 $random.= chr(mt_rand(0, 255));
3081 }
3082
3083 $blocks = $size >> 1;
3084 for ($i = 0; $i < $blocks; ++$i) {
3085 // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
3086 $random.= pack('n', mt_rand(0, 0xFFFF));
3087 }
3088 }
3089
3090 return new static($random, 256);
3091 }
3092
3109 function random($arg1, $arg2 = false)
3110 {
3111 if ($arg1 === false) {
3112 return false;
3113 }
3114
3115 if ($arg2 === false) {
3116 $max = $arg1;
3117 $min = $this;
3118 } else {
3119 $min = $arg1;
3120 $max = $arg2;
3121 }
3122
3123 $compare = $max->compare($min);
3124
3125 if (!$compare) {
3126 return $this->_normalize($min);
3127 } elseif ($compare < 0) {
3128 // if $min is bigger then $max, swap $min and $max
3129 $temp = $max;
3130 $max = $min;
3131 $min = $temp;
3132 }
3133
3134 static $one;
3135 if (!isset($one)) {
3136 $one = new static(1);
3137 }
3138
3139 $max = $max->subtract($min->subtract($one));
3140 $size = strlen(ltrim($max->toBytes(), chr(0)));
3141
3142 /*
3143 doing $random % $max doesn't work because some numbers will be more likely to occur than others.
3144 eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
3145 would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
3146 not all numbers would be equally likely. some would be more likely than others.
3147
3148 creating a whole new random number until you find one that is within the range doesn't work
3149 because, for sufficiently small ranges, the likelihood that you'd get a number within that range
3150 would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
3151 would be pretty high that $random would be greater than $max.
3152
3153 phpseclib works around this using the technique described here:
3154
3155 http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
3156 */
3157 $random_max = new static(chr(1) . str_repeat("\0", $size), 256);
3158 $random = $this->_random_number_helper($size);
3159
3160 list($max_multiple) = $random_max->divide($max);
3161 $max_multiple = $max_multiple->multiply($max);
3162
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);
3167 $random = $random->add($this->_random_number_helper(1));
3168 $random_max = $random_max->bitwise_leftShift(8);
3169 list($max_multiple) = $random_max->divide($max);
3170 $max_multiple = $max_multiple->multiply($max);
3171 }
3172 list(, $random) = $random->divide($max);
3173
3174 return $this->_normalize($random->add($min));
3175 }
3176
3190 function randomPrime($arg1, $arg2 = false, $timeout = false)
3191 {
3192 if ($arg1 === false) {
3193 return false;
3194 }
3195
3196 if ($arg2 === false) {
3197 $max = $arg1;
3198 $min = $this;
3199 } else {
3200 $min = $arg1;
3201 $max = $arg2;
3202 }
3203
3204 $compare = $max->compare($min);
3205
3206 if (!$compare) {
3207 return $min->isPrime() ? $min : false;
3208 } elseif ($compare < 0) {
3209 // if $min is bigger then $max, swap $min and $max
3210 $temp = $max;
3211 $max = $min;
3212 $min = $temp;
3213 }
3214
3215 static $one, $two;
3216 if (!isset($one)) {
3217 $one = new static(1);
3218 $two = new static(2);
3219 }
3220
3221 $start = time();
3222
3223 $x = $this->random($min, $max);
3224
3225 // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
3226 if (MATH_BIGINTEGER_MODE == self::MODE_GMP && extension_loaded('gmp')) {
3227 $p = new static();
3228 $p->value = gmp_nextprime($x->value);
3229
3230 if ($p->compare($max) <= 0) {
3231 return $p;
3232 }
3233
3234 if (!$min->equals($x)) {
3235 $x = $x->subtract($one);
3236 }
3237
3238 return $x->randomPrime($min, $x);
3239 }
3240
3241 if ($x->equals($two)) {
3242 return $x;
3243 }
3244
3245 $x->_make_odd();
3246 if ($x->compare($max) > 0) {
3247 // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
3248 if ($min->equals($max)) {
3249 return false;
3250 }
3251 $x = $min->copy();
3252 $x->_make_odd();
3253 }
3254
3255 $initial_x = $x->copy();
3256
3257 while (true) {
3258 if ($timeout !== false && time() - $start > $timeout) {
3259 return false;
3260 }
3261
3262 if ($x->isPrime()) {
3263 return $x;
3264 }
3265
3266 $x = $x->add($two);
3267
3268 if ($x->compare($max) > 0) {
3269 $x = $min->copy();
3270 if ($x->equals($two)) {
3271 return $x;
3272 }
3273 $x->_make_odd();
3274 }
3275
3276 if ($x->equals($initial_x)) {
3277 return false;
3278 }
3279 }
3280 }
3281
3290 function _make_odd()
3291 {
3292 switch (MATH_BIGINTEGER_MODE) {
3293 case self::MODE_GMP:
3294 gmp_setbit($this->value, 0);
3295 break;
3296 case self::MODE_BCMATH:
3297 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3298 $this->value = bcadd($this->value, '1');
3299 }
3300 break;
3301 default:
3302 $this->value[0] |= 1;
3303 }
3304 }
3305
3320 function isPrime($t = false)
3321 {
3322 $length = strlen($this->toBytes());
3323
3324 if (!$t) {
3325 // see HAC 4.49 "Note (controlling the error probability)"
3326 // @codingStandardsIgnoreStart
3327 if ($length >= 163) { $t = 2; } // floor(1300 / 8)
3328 else if ($length >= 106) { $t = 3; } // floor( 850 / 8)
3329 else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8)
3330 else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8)
3331 else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8)
3332 else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8)
3333 else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8)
3334 else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8)
3335 else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
3336 else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
3337 else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
3338 else { $t = 27; }
3339 // @codingStandardsIgnoreEnd
3340 }
3341
3342 // ie. gmp_testbit($this, 0)
3343 // ie. isEven() or !isOdd()
3344 switch (MATH_BIGINTEGER_MODE) {
3345 case self::MODE_GMP:
3346 return gmp_prob_prime($this->value, $t) != 0;
3347 case self::MODE_BCMATH:
3348 if ($this->value === '2') {
3349 return true;
3350 }
3351 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3352 return false;
3353 }
3354 break;
3355 default:
3356 if ($this->value == array(2)) {
3357 return true;
3358 }
3359 if (~$this->value[0] & 1) {
3360 return false;
3361 }
3362 }
3363
3364 static $primes, $zero, $one, $two;
3365
3366 if (!isset($primes)) {
3367 $primes = array(
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
3379 );
3380
3381 if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
3382 for ($i = 0; $i < count($primes); ++$i) {
3383 $primes[$i] = new static($primes[$i]);
3384 }
3385 }
3386
3387 $zero = new static();
3388 $one = new static(1);
3389 $two = new static(2);
3390 }
3391
3392 if ($this->equals($one)) {
3393 return false;
3394 }
3395
3396 // see HAC 4.4.1 "Random search for probable primes"
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);
3402 }
3403 }
3404 } else {
3406 foreach ($primes as $prime) {
3407 list(, $r) = $this->_divide_digit($value, $prime);
3408 if (!$r) {
3409 return count($value) == 1 && $value[0] == $prime;
3410 }
3411 }
3412 }
3413
3414 $n = $this->copy();
3415 $n_1 = $n->subtract($one);
3416 $n_2 = $n->subtract($two);
3417
3418 $r = $n_1->copy();
3419 $r_value = $r->value;
3420 // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
3421 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
3422 $s = 0;
3423 // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
3424 while ($r->value[strlen($r->value) - 1] % 2 == 0) {
3425 $r->value = bcdiv($r->value, '2', 0);
3426 ++$s;
3427 }
3428 } else {
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) {
3432 }
3433 if ($j != 25) {
3434 break;
3435 }
3436 }
3437 $s = 26 * $i + $j - 1;
3438 $r->_rshift($s);
3439 }
3440
3441 for ($i = 0; $i < $t; ++$i) {
3442 $a = $this->random($two, $n_2);
3443 $y = $a->modPow($r, $n);
3444
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)) {
3449 return false;
3450 }
3451 }
3452
3453 if (!$y->equals($n_1)) {
3454 return false;
3455 }
3456 }
3457 }
3458 return true;
3459 }
3460
3469 function _lshift($shift)
3470 {
3471 if ($shift == 0) {
3472 return;
3473 }
3474
3475 $num_digits = (int) ($shift / self::$base);
3476 $shift %= self::$base;
3477 $shift = 1 << $shift;
3478
3479 $carry = 0;
3480
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);
3485 }
3486
3487 if ($carry) {
3488 $this->value[count($this->value)] = $carry;
3489 }
3490
3491 while ($num_digits--) {
3492 array_unshift($this->value, 0);
3493 }
3494 }
3495
3504 function _rshift($shift)
3505 {
3506 if ($shift == 0) {
3507 return;
3508 }
3509
3510 $num_digits = (int) ($shift / self::$base);
3511 $shift %= self::$base;
3512 $carry_shift = self::$base - $shift;
3513 $carry_mask = (1 << $shift) - 1;
3514
3515 if ($num_digits) {
3516 $this->value = array_slice($this->value, $num_digits);
3517 }
3518
3519 $carry = 0;
3520
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;
3525 }
3526
3527 $this->value = $this->_trim($this->value);
3528 }
3529
3541 {
3542 $result->precision = $this->precision;
3543 $result->bitmask = $this->bitmask;
3544
3545 switch (MATH_BIGINTEGER_MODE) {
3546 case self::MODE_GMP:
3547 if ($this->bitmask !== false) {
3548 $result->value = gmp_and($result->value, $result->bitmask->value);
3549 }
3550
3551 return $result;
3552 case self::MODE_BCMATH:
3553 if (!empty($result->bitmask->value)) {
3554 $result->value = bcmod($result->value, $result->bitmask->value);
3555 }
3556
3557 return $result;
3558 }
3559
3560 $value = &$result->value;
3561
3562 if (!count($value)) {
3563 return $result;
3564 }
3565
3566 $value = $this->_trim($value);
3567
3568 if (!empty($result->bitmask->value)) {
3569 $length = min(count($value), count($this->bitmask->value));
3570 $value = array_slice($value, 0, $length);
3571
3572 for ($i = 0; $i < $length; ++$i) {
3573 $value[$i] = $value[$i] & $this->bitmask->value[$i];
3574 }
3575 }
3576
3577 return $result;
3578 }
3579
3589 function _trim($value)
3590 {
3591 for ($i = count($value) - 1; $i >= 0; --$i) {
3592 if ($value[$i]) {
3593 break;
3594 }
3595 unset($value[$i]);
3596 }
3597
3598 return $value;
3599 }
3600
3609 function _array_repeat($input, $multiplier)
3610 {
3611 return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
3612 }
3613
3624 function _base256_lshift(&$x, $shift)
3625 {
3626 if ($shift == 0) {
3627 return;
3628 }
3629
3630 $num_bytes = $shift >> 3; // eg. floor($shift/8)
3631 $shift &= 7; // eg. $shift % 8
3632
3633 $carry = 0;
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;
3638 }
3639 $carry = ($carry != 0) ? chr($carry) : '';
3640 $x = $carry . $x . str_repeat(chr(0), $num_bytes);
3641 }
3642
3653 function _base256_rshift(&$x, $shift)
3654 {
3655 if ($shift == 0) {
3656 $x = ltrim($x, chr(0));
3657 return '';
3658 }
3659
3660 $num_bytes = $shift >> 3; // eg. floor($shift/8)
3661 $shift &= 7; // eg. $shift % 8
3662
3663 $remainder = '';
3664 if ($num_bytes) {
3665 $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
3666 $remainder = substr($x, $start);
3667 $x = substr($x, 0, -$num_bytes);
3668 }
3669
3670 $carry = 0;
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);
3676 }
3677 $x = ltrim($x, chr(0));
3678
3679 $remainder = chr($carry >> $carry_shift) . $remainder;
3680
3681 return ltrim($remainder, chr(0));
3682 }
3683
3684 // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
3685 // at 32-bits, while java's longs are 64-bits.
3686
3694 function _int2bytes($x)
3695 {
3696 return ltrim(pack('N', $x), chr(0));
3697 }
3698
3706 function _bytes2int($x)
3707 {
3708 $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
3709 return $temp['int'];
3710 }
3711
3722 function _encodeASN1Length($length)
3723 {
3724 if ($length <= 0x7F) {
3725 return chr($length);
3726 }
3727
3728 $temp = ltrim(pack('N', $length), chr(0));
3729 return pack('Ca*', 0x80 | strlen($temp), $temp);
3730 }
3731
3745 function _safe_divide($x, $y)
3746 {
3747 if (self::$base === 26) {
3748 return (int) ($x / $y);
3749 }
3750
3751 // self::$base === 31
3752 return ($x - ($x % $y)) / $y;
3753 }
3754}
$result
$n
Definition: RandomTest.php:85
$size
Definition: RandomTest.php:84
An exception for terminatinating execution or to throw for unit testing.
static string($length)
Generate a random string.
Definition: Random.php:54
multiply($x)
Multiplies two BigIntegers.
_karatsubaSquare($value)
Performs Karatsuba "squaring" on two BigIntegers.
static $max10Len
$max10Len in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base.
Definition: BigInteger.php:182
_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.
Definition: BigInteger.php:252
const DATA
$cache[self::DATA] contains the cached data.
Definition: BigInteger.php:126
divide($y)
Divides two BigIntegers.
__sleep()
__sleep() magic method
Definition: BigInteger.php:777
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.
copy()
Copy an object.
Definition: BigInteger.php:728
add($y)
Adds two BigIntegers.
Definition: BigInteger.php:859
const MODE_GMP
To use the GMP library.
Definition: BigInteger.php:150
const MONTGOMERY
#+ Reduction constants
Definition: BigInteger.php:75
_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.
Definition: BigInteger.php:176
_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.
Definition: BigInteger.php:167
_regularMultiply($x_value, $y_value)
Performs long multiplication on two BigIntegers.
toBits($twos_compliment=false)
Converts a BigInteger to a bit string (eg.
Definition: BigInteger.php:642
bitwise_or($x)
Logical Or.
_montgomery($x, $n)
Montgomery Modular Reduction.
toHex($twos_compliment=false)
Converts a BigInteger to a hex string (eg.
Definition: BigInteger.php:617
_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.
Definition: BigInteger.php:893
_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.
Definition: BigInteger.php:988
const SIGN
$result[self::SIGN] contains the sign.
Definition: BigInteger.php:109
bitwise_rightRotate($shift)
Logical Right Rotate.
__wakeup()
__wakeup() magic method
Definition: BigInteger.php:795
equals($x)
Tests the equality of two numbers.
__toString()
__toString() magic method
Definition: BigInteger.php:747
abs()
Absolute value.
bitwise_leftShift($shift)
Logical Left Shift.
_regularBarrett($x, $n)
(Regular) Barrett Modular Reduction
_normalize($result)
Normalize.
__debugInfo()
__debugInfo() magic method
Definition: BigInteger.php:813
_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.
Definition: BigInteger.php:522
const MODE_BCMATH
To use the BCMath library.
Definition: BigInteger.php:144
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.
Definition: BigInteger.php:216
_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
Definition: BigInteger.php:764
_rshift($shift)
Logical Right Shift.
toString()
Converts a BigInteger to a base-10 number.
Definition: BigInteger.php:677
_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.
$x
Definition: complexTest.php:9
$key
Definition: croninfo.php:18
for( $i=6;$i< 13;$i++) for($i=1; $i< 13; $i++) $d
Definition: date.php:296
$i
Definition: disco.tpl.php:19
$y
Definition: example_007.php:83
$r
Definition: example_031.php:79
$mask
Definition: example_042.php:90
$base
Definition: index.php:4
Pure-PHP arbitrary precision integer arithmetic library.
Pure-PHP arbitrary precision integer arithmetic library.
Definition: BigInteger.php:51
$s
Definition: pwgen.php:45
$start
Definition: bench.php:8
$engine
Definition: workflow.php:89