1: <?php
2:
3: namespace Liberty;
4:
5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74:
75:
76: 77: 78: 79: 80: 81:
82: 83: 84: 85:
86: define('MATH_BIGINTEGER_MONTGOMERY', 0);
87: 88: 89:
90: define('MATH_BIGINTEGER_BARRETT', 1);
91: 92: 93:
94: define('MATH_BIGINTEGER_POWEROF2', 2);
95: 96: 97:
98: define('MATH_BIGINTEGER_CLASSIC', 3);
99: 100: 101:
102: define('MATH_BIGINTEGER_NONE', 4);
103:
104:
105: 106: 107: 108: 109: 110: 111: 112:
113: 114: 115:
116: define('MATH_BIGINTEGER_VALUE', 0);
117: 118: 119:
120: define('MATH_BIGINTEGER_SIGN', 1);
121:
122:
123: 124: 125: 126: 127:
128: 129: 130: 131: 132:
133: define('MATH_BIGINTEGER_VARIABLE', 0);
134: 135: 136:
137: define('MATH_BIGINTEGER_DATA', 1);
138:
139:
140: 141: 142: 143: 144: 145:
146: 147: 148:
149: define('MATH_BIGINTEGER_MODE_INTERNAL', 1);
150: 151: 152: 153: 154:
155: define('MATH_BIGINTEGER_MODE_BCMATH', 2);
156: 157: 158: 159: 160:
161: define('MATH_BIGINTEGER_MODE_GMP', 3);
162:
163:
164: 165: 166: 167: 168: 169: 170:
171: define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 25);
172:
173: 174: 175: 176: 177: 178: 179: 180: 181:
182: class BigInteger
183: {
184: 185: 186: 187: 188: 189:
190: var $value;
191:
192: 193: 194: 195: 196: 197:
198: var $is_negative = false;
199:
200: 201: 202: 203: 204: 205:
206: var $generator = 'mt_rand';
207:
208: 209: 210: 211: 212: 213:
214: var $precision = -1;
215:
216: 217: 218: 219: 220: 221:
222: var $bitmask = false;
223:
224: 225: 226: 227: 228: 229: 230: 231: 232: 233: 234: 235:
236: var $hex;
237:
238: 239: 240: 241: 242: 243: 244: 245: 246: 247: 248: 249: 250: 251: 252: 253: 254: 255: 256: 257: 258: 259:
260: function __construct($x = 0, $base = 10)
261: {
262: if ( !defined('MATH_BIGINTEGER_MODE') ) {
263: switch (true) {
264: case extension_loaded('gmp'):
265: define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP);
266: break;
267: case extension_loaded('bcmath'):
268: define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH);
269: break;
270: default:
271: define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL);
272: }
273: }
274:
275: if (function_exists('openssl_public_encrypt') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
276:
277: ob_start();
278: phpinfo();
279: $content = ob_get_contents();
280: ob_end_clean();
281:
282: preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
283:
284: $versions = array();
285: if (!empty($matches[1])) {
286: for ($i = 0; $i < count($matches[1]); $i++) {
287: $versions[$matches[1][$i]] = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
288: }
289: }
290:
291:
292: switch (true) {
293: case !isset($versions['Header']):
294: case !isset($versions['Library']):
295: case $versions['Header'] == $versions['Library']:
296: define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
297: break;
298: default:
299: define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
300: }
301: }
302:
303: if (!defined('PHP_INT_SIZE')) {
304: define('PHP_INT_SIZE', 4);
305: }
306:
307: if (!defined('MATH_BIGINTEGER_BASE') && MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL) {
308: switch (PHP_INT_SIZE) {
309: case 8:
310: define('MATH_BIGINTEGER_BASE', 31);
311: define('MATH_BIGINTEGER_BASE_FULL', 0x80000000);
312: define('MATH_BIGINTEGER_MAX_DIGIT', 0x7FFFFFFF);
313: define('MATH_BIGINTEGER_MSB', 0x40000000);
314:
315: define('MATH_BIGINTEGER_MAX10', 1000000000);
316: define('MATH_BIGINTEGER_MAX10_LEN', 9);
317:
318: define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 62));
319: break;
320:
321: default:
322: define('MATH_BIGINTEGER_BASE', 26);
323: define('MATH_BIGINTEGER_BASE_FULL', 0x4000000);
324: define('MATH_BIGINTEGER_MAX_DIGIT', 0x3FFFFFF);
325: define('MATH_BIGINTEGER_MSB', 0x2000000);
326:
327: define('MATH_BIGINTEGER_MAX10', 10000000);
328: define('MATH_BIGINTEGER_MAX10_LEN', 7);
329:
330:
331:
332: define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 52));
333: }
334: }
335:
336: switch ( MATH_BIGINTEGER_MODE ) {
337: case MATH_BIGINTEGER_MODE_GMP:
338: if (is_resource($x) && get_resource_type($x) == 'GMP integer') {
339: $this->value = $x;
340: return;
341: }
342: $this->value = gmp_init(0);
343: break;
344: case MATH_BIGINTEGER_MODE_BCMATH:
345: $this->value = '0';
346: break;
347: default:
348: $this->value = array();
349: }
350:
351:
352:
353: if (empty($x) && (abs($base) != 256 || $x !== '0')) {
354: return;
355: }
356:
357: switch ($base) {
358: case -256:
359: if (ord($x[0]) & 0x80) {
360: $x = ~$x;
361: $this->is_negative = true;
362: }
363: case 256:
364: switch ( MATH_BIGINTEGER_MODE ) {
365: case MATH_BIGINTEGER_MODE_GMP:
366: $sign = $this->is_negative ? '-' : '';
367: $this->value = gmp_init($sign . '0x' . bin2hex($x));
368: break;
369: case MATH_BIGINTEGER_MODE_BCMATH:
370:
371: $len = (strlen($x) + 3) & 0xFFFFFFFC;
372:
373: $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
374:
375: for ($i = 0; $i < $len; $i+= 4) {
376: $this->value = bcmul($this->value, '4294967296', 0);
377: $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
378: }
379:
380: if ($this->is_negative) {
381: $this->value = '-' . $this->value;
382: }
383:
384: break;
385:
386: default:
387: while (strlen($x)) {
388: $this->value[] = $this->_bytes2int($this->_base256_rshift($x, MATH_BIGINTEGER_BASE));
389: }
390: }
391:
392: if ($this->is_negative) {
393: if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
394: $this->is_negative = false;
395: }
396: $temp = $this->add(new BigInteger('-1'));
397: $this->value = $temp->value;
398: }
399: break;
400: case 16:
401: case -16:
402: if ($base > 0 && $x[0] == '-') {
403: $this->is_negative = true;
404: $x = substr($x, 1);
405: }
406:
407: $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
408:
409: $is_negative = false;
410: if ($base < 0 && hexdec($x[0]) >= 8) {
411: $this->is_negative = $is_negative = true;
412: $x = bin2hex(~pack('H*', $x));
413: }
414:
415: switch ( MATH_BIGINTEGER_MODE ) {
416: case MATH_BIGINTEGER_MODE_GMP:
417: $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
418: $this->value = gmp_init($temp);
419: $this->is_negative = false;
420: break;
421: case MATH_BIGINTEGER_MODE_BCMATH:
422: $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
423: $temp = new BigInteger(pack('H*', $x), 256);
424: $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
425: $this->is_negative = false;
426: break;
427: default:
428: $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
429: $temp = new BigInteger(pack('H*', $x), 256);
430: $this->value = $temp->value;
431: }
432:
433: if ($is_negative) {
434: $temp = $this->add(new BigInteger('-1'));
435: $this->value = $temp->value;
436: }
437: break;
438: case 10:
439: case -10:
440:
441:
442:
443: $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
444:
445: switch ( MATH_BIGINTEGER_MODE ) {
446: case MATH_BIGINTEGER_MODE_GMP:
447: $this->value = gmp_init($x);
448: break;
449: case MATH_BIGINTEGER_MODE_BCMATH:
450:
451:
452: $this->value = $x === '-' ? '0' : (string) $x;
453: break;
454: default:
455: $temp = new BigInteger();
456:
457: $multiplier = new BigInteger();
458: $multiplier->value = array(MATH_BIGINTEGER_MAX10);
459:
460: if ($x[0] == '-') {
461: $this->is_negative = true;
462: $x = substr($x, 1);
463: }
464:
465: $x = str_pad($x, strlen($x) + ((MATH_BIGINTEGER_MAX10_LEN - 1) * strlen($x)) % MATH_BIGINTEGER_MAX10_LEN, 0, STR_PAD_LEFT);
466: while (strlen($x)) {
467: $temp = $temp->multiply($multiplier);
468: $temp = $temp->add(new BigInteger($this->_int2bytes(substr($x, 0, MATH_BIGINTEGER_MAX10_LEN)), 256));
469: $x = substr($x, MATH_BIGINTEGER_MAX10_LEN);
470: }
471:
472: $this->value = $temp->value;
473: }
474: break;
475: case 2:
476: case -2:
477: if ($base > 0 && $x[0] == '-') {
478: $this->is_negative = true;
479: $x = substr($x, 1);
480: }
481:
482: $x = preg_replace('#^([01]*).*#', '$1', $x);
483: $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
484:
485: $str = '0x';
486: while (strlen($x)) {
487: $part = substr($x, 0, 4);
488: $str.= dechex(bindec($part));
489: $x = substr($x, 4);
490: }
491:
492: if ($this->is_negative) {
493: $str = '-' . $str;
494: }
495:
496: $temp = new BigInteger($str, 8 * $base);
497: $this->value = $temp->value;
498: $this->is_negative = $temp->is_negative;
499:
500: break;
501: default:
502:
503: }
504: }
505:
506: 507: 508: 509: 510: 511:
512: public function BigInteger($x = 0, $base = 10)
513: {
514: self::__construct($x, $base);
515: }
516:
517: 518: 519: 520: 521: 522: 523: 524: 525: 526: 527: 528: 529: 530: 531: 532: 533: 534: 535: 536: 537: 538:
539: function toBytes($twos_compliment = false)
540: {
541: if ($twos_compliment) {
542: $comparison = $this->compare(new BigInteger());
543: if ($comparison == 0) {
544: return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
545: }
546:
547: $temp = $comparison < 0 ? $this->add(new BigInteger(1)) : $this->copy();
548: $bytes = $temp->toBytes();
549:
550: if (empty($bytes)) {
551: $bytes = chr(0);
552: }
553:
554: if (ord($bytes[0]) & 0x80) {
555: $bytes = chr(0) . $bytes;
556: }
557:
558: return $comparison < 0 ? ~$bytes : $bytes;
559: }
560:
561: switch ( MATH_BIGINTEGER_MODE ) {
562: case MATH_BIGINTEGER_MODE_GMP:
563: if (gmp_cmp($this->value, gmp_init(0)) == 0) {
564: return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
565: }
566:
567: $temp = gmp_strval(gmp_abs($this->value), 16);
568: $temp = ( strlen($temp) & 1 ) ? '0' . $temp : $temp;
569: $temp = pack('H*', $temp);
570:
571: return $this->precision > 0 ?
572: substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
573: ltrim($temp, chr(0));
574: case MATH_BIGINTEGER_MODE_BCMATH:
575: if ($this->value === '0') {
576: return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
577: }
578:
579: $value = '';
580: $current = $this->value;
581:
582: if ($current[0] == '-') {
583: $current = substr($current, 1);
584: }
585:
586: while (bccomp($current, '0', 0) > 0) {
587: $temp = bcmod($current, '16777216');
588: $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
589: $current = bcdiv($current, '16777216', 0);
590: }
591:
592: return $this->precision > 0 ?
593: substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
594: ltrim($value, chr(0));
595: }
596:
597: if (!count($this->value)) {
598: return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
599: }
600: $result = $this->_int2bytes($this->value[count($this->value) - 1]);
601:
602: $temp = $this->copy();
603:
604: for ($i = count($temp->value) - 2; $i >= 0; --$i) {
605: $temp->_base256_lshift($result, MATH_BIGINTEGER_BASE);
606: $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
607: }
608:
609: return $this->precision > 0 ?
610: str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
611: $result;
612: }
613:
614: 615: 616: 617: 618: 619: 620: 621: 622: 623: 624: 625: 626: 627: 628: 629: 630: 631: 632: 633: 634: 635:
636: function toHex($twos_compliment = false)
637: {
638: return bin2hex($this->toBytes($twos_compliment));
639: }
640:
641: 642: 643: 644: 645: 646: 647: 648: 649: 650: 651: 652: 653: 654: 655: 656: 657: 658: 659: 660: 661: 662:
663: function toBits($twos_compliment = false)
664: {
665: $hex = $this->toHex($twos_compliment);
666: $bits = '';
667: for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
668: $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits;
669: }
670: if ($start) {
671: $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits;
672: }
673: $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
674:
675: if ($twos_compliment && $this->compare(new BigInteger()) > 0 && $this->precision <= 0) {
676: return '0' . $result;
677: }
678:
679: return $result;
680: }
681:
682: 683: 684: 685: 686: 687: 688: 689: 690: 691: 692: 693: 694: 695: 696: 697: 698: 699:
700: function toString()
701: {
702: switch ( MATH_BIGINTEGER_MODE ) {
703: case MATH_BIGINTEGER_MODE_GMP:
704: return gmp_strval($this->value);
705: case MATH_BIGINTEGER_MODE_BCMATH:
706: if ($this->value === '0') {
707: return '0';
708: }
709:
710: return ltrim($this->value, '0');
711: }
712:
713: if (!count($this->value)) {
714: return '0';
715: }
716:
717: $temp = $this->copy();
718: $temp->is_negative = false;
719:
720: $divisor = new BigInteger();
721: $divisor->value = array(MATH_BIGINTEGER_MAX10);
722: $result = '';
723: while (count($temp->value)) {
724: list($temp, $mod) = $temp->divide($divisor);
725: $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', MATH_BIGINTEGER_MAX10_LEN, '0', STR_PAD_LEFT) . $result;
726: }
727: $result = ltrim($result, '0');
728: if (empty($result)) {
729: $result = '0';
730: }
731:
732: if ($this->is_negative) {
733: $result = '-' . $result;
734: }
735:
736: return $result;
737: }
738:
739: 740: 741: 742: 743: 744: 745: 746: 747: 748: 749: 750:
751: function copy()
752: {
753: $temp = new BigInteger();
754: $temp->value = $this->value;
755: $temp->is_negative = $this->is_negative;
756: $temp->generator = $this->generator;
757: $temp->precision = $this->precision;
758: $temp->bitmask = $this->bitmask;
759: return $temp;
760: }
761:
762: 763: 764: 765: 766: 767: 768: 769: 770:
771: function __toString()
772: {
773: return $this->toString();
774: }
775:
776: 777: 778: 779: 780: 781: 782: 783: 784: 785: 786: 787:
788: function __clone()
789: {
790: return $this->copy();
791: }
792:
793: 794: 795: 796: 797: 798: 799: 800:
801: function __sleep()
802: {
803: $this->hex = $this->toHex(true);
804: $vars = array('hex');
805: if ($this->generator != 'mt_rand') {
806: $vars[] = 'generator';
807: }
808: if ($this->precision > 0) {
809: $vars[] = 'precision';
810: }
811: return $vars;
812:
813: }
814:
815: 816: 817: 818: 819: 820: 821: 822:
823: function __wakeup()
824: {
825: $temp = new BigInteger($this->hex, -16);
826: $this->value = $temp->value;
827: $this->is_negative = $temp->is_negative;
828: $this->setRandomGenerator($this->generator);
829: if ($this->precision > 0) {
830:
831: $this->setPrecision($this->precision);
832: }
833: }
834:
835: 836: 837: 838: 839: 840: 841: 842: 843: 844: 845: 846: 847: 848: 849: 850: 851: 852: 853: 854: 855: 856:
857: function add($y)
858: {
859: switch ( MATH_BIGINTEGER_MODE ) {
860: case MATH_BIGINTEGER_MODE_GMP:
861: $temp = new BigInteger();
862: $temp->value = gmp_add($this->value, $y->value);
863:
864: return $this->_normalize($temp);
865: case MATH_BIGINTEGER_MODE_BCMATH:
866: $temp = new BigInteger();
867: $temp->value = bcadd($this->value, $y->value, 0);
868:
869: return $this->_normalize($temp);
870: }
871:
872: $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
873:
874: $result = new BigInteger();
875: $result->value = $temp[MATH_BIGINTEGER_VALUE];
876: $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
877:
878: return $this->_normalize($result);
879: }
880:
881: 882: 883: 884: 885: 886: 887: 888: 889: 890:
891: function _add($x_value, $x_negative, $y_value, $y_negative)
892: {
893: $x_size = count($x_value);
894: $y_size = count($y_value);
895:
896: if ($x_size == 0) {
897: return array(
898: MATH_BIGINTEGER_VALUE => $y_value,
899: MATH_BIGINTEGER_SIGN => $y_negative
900: );
901: } else if ($y_size == 0) {
902: return array(
903: MATH_BIGINTEGER_VALUE => $x_value,
904: MATH_BIGINTEGER_SIGN => $x_negative
905: );
906: }
907:
908:
909: if ( $x_negative != $y_negative ) {
910: if ( $x_value == $y_value ) {
911: return array(
912: MATH_BIGINTEGER_VALUE => array(),
913: MATH_BIGINTEGER_SIGN => false
914: );
915: }
916:
917: $temp = $this->_subtract($x_value, false, $y_value, false);
918: $temp[MATH_BIGINTEGER_SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
919: $x_negative : $y_negative;
920:
921: return $temp;
922: }
923:
924: if ($x_size < $y_size) {
925: $size = $x_size;
926: $value = $y_value;
927: } else {
928: $size = $y_size;
929: $value = $x_value;
930: }
931:
932: $value[] = 0;
933:
934: $carry = 0;
935: for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
936: $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] + $y_value[$j] * MATH_BIGINTEGER_BASE_FULL + $y_value[$i] + $carry;
937: $carry = $sum >= MATH_BIGINTEGER_MAX_DIGIT2;
938: $sum = $carry ? $sum - MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
939:
940: $temp = (int) ($sum / MATH_BIGINTEGER_BASE_FULL);
941:
942: $value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp);
943: $value[$j] = $temp;
944: }
945:
946: if ($j == $size) {
947: $sum = $x_value[$i] + $y_value[$i] + $carry;
948: $carry = $sum >= MATH_BIGINTEGER_BASE_FULL;
949: $value[$i] = $carry ? $sum - MATH_BIGINTEGER_BASE_FULL : $sum;
950: ++$i;
951: }
952:
953: if ($carry) {
954: for (; $value[$i] == MATH_BIGINTEGER_MAX_DIGIT; ++$i) {
955: $value[$i] = 0;
956: }
957: ++$value[$i];
958: }
959:
960: return array(
961: MATH_BIGINTEGER_VALUE => $this->_trim($value),
962: MATH_BIGINTEGER_SIGN => $x_negative
963: );
964: }
965:
966: 967: 968: 969: 970: 971: 972: 973: 974: 975: 976: 977: 978: 979: 980: 981: 982: 983: 984: 985: 986: 987:
988: function subtract($y)
989: {
990: switch ( MATH_BIGINTEGER_MODE ) {
991: case MATH_BIGINTEGER_MODE_GMP:
992: $temp = new BigInteger();
993: $temp->value = gmp_sub($this->value, $y->value);
994:
995: return $this->_normalize($temp);
996: case MATH_BIGINTEGER_MODE_BCMATH:
997: $temp = new BigInteger();
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 BigInteger();
1006: $result->value = $temp[MATH_BIGINTEGER_VALUE];
1007: $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
1008:
1009: return $this->_normalize($result);
1010: }
1011:
1012: 1013: 1014: 1015: 1016: 1017: 1018: 1019: 1020: 1021:
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: MATH_BIGINTEGER_VALUE => $y_value,
1030: MATH_BIGINTEGER_SIGN => !$y_negative
1031: );
1032: } else if ($y_size == 0) {
1033: return array(
1034: MATH_BIGINTEGER_VALUE => $x_value,
1035: MATH_BIGINTEGER_SIGN => $x_negative
1036: );
1037: }
1038:
1039:
1040: if ( $x_negative != $y_negative ) {
1041: $temp = $this->_add($x_value, false, $y_value, false);
1042: $temp[MATH_BIGINTEGER_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: MATH_BIGINTEGER_VALUE => array(),
1052: MATH_BIGINTEGER_SIGN => false
1053: );
1054: }
1055:
1056:
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:
1069:
1070: $carry = 0;
1071: for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
1072: $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] - $y_value[$j] * MATH_BIGINTEGER_BASE_FULL - $y_value[$i] - $carry;
1073: $carry = $sum < 0;
1074: $sum = $carry ? $sum + MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
1075:
1076: $temp = (int) ($sum / MATH_BIGINTEGER_BASE_FULL);
1077:
1078: $x_value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp);
1079: $x_value[$j] = $temp;
1080: }
1081:
1082: if ($j == $y_size) {
1083: $sum = $x_value[$i] - $y_value[$i] - $carry;
1084: $carry = $sum < 0;
1085: $x_value[$i] = $carry ? $sum + MATH_BIGINTEGER_BASE_FULL : $sum;
1086: ++$i;
1087: }
1088:
1089: if ($carry) {
1090: for (; !$x_value[$i]; ++$i) {
1091: $x_value[$i] = MATH_BIGINTEGER_MAX_DIGIT;
1092: }
1093: --$x_value[$i];
1094: }
1095:
1096: return array(
1097: MATH_BIGINTEGER_VALUE => $this->_trim($x_value),
1098: MATH_BIGINTEGER_SIGN => $x_negative
1099: );
1100: }
1101:
1102: 1103: 1104: 1105: 1106: 1107: 1108: 1109: 1110: 1111: 1112: 1113: 1114: 1115: 1116: 1117: 1118: 1119: 1120: 1121: 1122:
1123: function multiply($x)
1124: {
1125: switch ( MATH_BIGINTEGER_MODE ) {
1126: case MATH_BIGINTEGER_MODE_GMP:
1127: $temp = new BigInteger();
1128: $temp->value = gmp_mul($this->value, $x->value);
1129:
1130: return $this->_normalize($temp);
1131: case MATH_BIGINTEGER_MODE_BCMATH:
1132: $temp = new BigInteger();
1133: $temp->value = bcmul($this->value, $x->value, 0);
1134:
1135: return $this->_normalize($temp);
1136: }
1137:
1138: $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
1139:
1140: $product = new BigInteger();
1141: $product->value = $temp[MATH_BIGINTEGER_VALUE];
1142: $product->is_negative = $temp[MATH_BIGINTEGER_SIGN];
1143:
1144: return $this->_normalize($product);
1145: }
1146:
1147: 1148: 1149: 1150: 1151: 1152: 1153: 1154: 1155: 1156:
1157: function _multiply($x_value, $x_negative, $y_value, $y_negative)
1158: {
1159:
1160:
1161:
1162:
1163:
1164:
1165:
1166: $x_length = count($x_value);
1167: $y_length = count($y_value);
1168:
1169: if ( !$x_length || !$y_length ) {
1170: return array(
1171: MATH_BIGINTEGER_VALUE => array(),
1172: MATH_BIGINTEGER_SIGN => false
1173: );
1174: }
1175:
1176: return array(
1177: MATH_BIGINTEGER_VALUE => min($x_length, $y_length) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
1178: $this->_trim($this->_regularMultiply($x_value, $y_value)) :
1179: $this->_trim($this->_karatsuba($x_value, $y_value)),
1180: MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
1181: );
1182: }
1183:
1184: 1185: 1186: 1187: 1188: 1189: 1190: 1191: 1192: 1193:
1194: function _regularMultiply($x_value, $y_value)
1195: {
1196: $x_length = count($x_value);
1197: $y_length = count($y_value);
1198:
1199: if ( !$x_length || !$y_length ) {
1200: return array();
1201: }
1202:
1203: if ( $x_length < $y_length ) {
1204: $temp = $x_value;
1205: $x_value = $y_value;
1206: $y_value = $temp;
1207:
1208: $x_length = count($x_value);
1209: $y_length = count($y_value);
1210: }
1211:
1212: $product_value = $this->_array_repeat(0, $x_length + $y_length);
1213:
1214:
1215:
1216:
1217:
1218:
1219:
1220: $carry = 0;
1221:
1222: for ($j = 0; $j < $x_length; ++$j) {
1223: $temp = $x_value[$j] * $y_value[0] + $carry;
1224: $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
1225: $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
1226: }
1227:
1228: $product_value[$j] = $carry;
1229:
1230:
1231:
1232: for ($i = 1; $i < $y_length; ++$i) {
1233: $carry = 0;
1234:
1235: for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
1236: $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
1237: $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
1238: $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
1239: }
1240:
1241: $product_value[$k] = $carry;
1242: }
1243:
1244: return $product_value;
1245: }
1246:
1247: 1248: 1249: 1250: 1251: 1252: 1253: 1254: 1255: 1256: 1257:
1258: function _karatsuba($x_value, $y_value)
1259: {
1260: $m = min(count($x_value) >> 1, count($y_value) >> 1);
1261:
1262: if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
1263: return $this->_regularMultiply($x_value, $y_value);
1264: }
1265:
1266: $x1 = array_slice($x_value, $m);
1267: $x0 = array_slice($x_value, 0, $m);
1268: $y1 = array_slice($y_value, $m);
1269: $y0 = array_slice($y_value, 0, $m);
1270:
1271: $z2 = $this->_karatsuba($x1, $y1);
1272: $z0 = $this->_karatsuba($x0, $y0);
1273:
1274: $z1 = $this->_add($x1, false, $x0, false);
1275: $temp = $this->_add($y1, false, $y0, false);
1276: $z1 = $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_VALUE]);
1277: $temp = $this->_add($z2, false, $z0, false);
1278: $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
1279:
1280: $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1281: $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
1282:
1283: $xy = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
1284: $xy = $this->_add($xy[MATH_BIGINTEGER_VALUE], $xy[MATH_BIGINTEGER_SIGN], $z0, false);
1285:
1286: return $xy[MATH_BIGINTEGER_VALUE];
1287: }
1288:
1289: 1290: 1291: 1292: 1293: 1294: 1295:
1296: function _square($x = false)
1297: {
1298: return count($x) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
1299: $this->_trim($this->_baseSquare($x)) :
1300: $this->_trim($this->_karatsubaSquare($x));
1301: }
1302:
1303: 1304: 1305: 1306: 1307: 1308: 1309: 1310: 1311: 1312: 1313:
1314: function _baseSquare($value)
1315: {
1316: if ( empty($value) ) {
1317: return array();
1318: }
1319: $square_value = $this->_array_repeat(0, 2 * count($value));
1320:
1321: for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
1322: $i2 = $i << 1;
1323:
1324: $temp = $square_value[$i2] + $value[$i] * $value[$i];
1325: $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
1326: $square_value[$i2] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
1327:
1328:
1329: for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
1330: $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
1331: $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
1332: $square_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
1333: }
1334:
1335:
1336:
1337: $square_value[$i + $max_index + 1] = $carry;
1338: }
1339:
1340: return $square_value;
1341: }
1342:
1343: 1344: 1345: 1346: 1347: 1348: 1349: 1350: 1351: 1352:
1353: function _karatsubaSquare($value)
1354: {
1355: $m = count($value) >> 1;
1356:
1357: if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
1358: return $this->_baseSquare($value);
1359: }
1360:
1361: $x1 = array_slice($value, $m);
1362: $x0 = array_slice($value, 0, $m);
1363:
1364: $z2 = $this->_karatsubaSquare($x1);
1365: $z0 = $this->_karatsubaSquare($x0);
1366:
1367: $z1 = $this->_add($x1, false, $x0, false);
1368: $z1 = $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE]);
1369: $temp = $this->_add($z2, false, $z0, false);
1370: $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
1371:
1372: $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1373: $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
1374:
1375: $xx = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
1376: $xx = $this->_add($xx[MATH_BIGINTEGER_VALUE], $xx[MATH_BIGINTEGER_SIGN], $z0, false);
1377:
1378: return $xx[MATH_BIGINTEGER_VALUE];
1379: }
1380:
1381: 1382: 1383: 1384: 1385: 1386: 1387: 1388: 1389: 1390: 1391: 1392: 1393: 1394: 1395: 1396: 1397: 1398: 1399: 1400: 1401: 1402: 1403: 1404: 1405: 1406: 1407: 1408: 1409:
1410: function divide($y)
1411: {
1412: switch ( MATH_BIGINTEGER_MODE ) {
1413: case MATH_BIGINTEGER_MODE_GMP:
1414: $quotient = new BigInteger();
1415: $remainder = new BigInteger();
1416:
1417: list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
1418:
1419: if (gmp_sign($remainder->value) < 0) {
1420: $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
1421: }
1422:
1423: return array($this->_normalize($quotient), $this->_normalize($remainder));
1424: case MATH_BIGINTEGER_MODE_BCMATH:
1425: $quotient = new BigInteger();
1426: $remainder = new BigInteger();
1427:
1428: $quotient->value = bcdiv($this->value, $y->value, 0);
1429: $remainder->value = bcmod($this->value, $y->value);
1430:
1431: if ($remainder->value[0] == '-') {
1432: $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
1433: }
1434:
1435: return array($this->_normalize($quotient), $this->_normalize($remainder));
1436: }
1437:
1438: if (count($y->value) == 1) {
1439: list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
1440: $quotient = new BigInteger();
1441: $remainder = new BigInteger();
1442: $quotient->value = $q;
1443: $remainder->value = array($r);
1444: $quotient->is_negative = $this->is_negative != $y->is_negative;
1445: return array($this->_normalize($quotient), $this->_normalize($remainder));
1446: }
1447:
1448: static $zero;
1449: if ( !isset($zero) ) {
1450: $zero = new BigInteger();
1451: }
1452:
1453: $x = $this->copy();
1454: $y = $y->copy();
1455:
1456: $x_sign = $x->is_negative;
1457: $y_sign = $y->is_negative;
1458:
1459: $x->is_negative = $y->is_negative = false;
1460:
1461: $diff = $x->compare($y);
1462:
1463: if ( !$diff ) {
1464: $temp = new BigInteger();
1465: $temp->value = array(1);
1466: $temp->is_negative = $x_sign != $y_sign;
1467: return array($this->_normalize($temp), $this->_normalize(new BigInteger()));
1468: }
1469:
1470: if ( $diff < 0 ) {
1471:
1472: if ( $x_sign ) {
1473: $x = $y->subtract($x);
1474: }
1475: return array($this->_normalize(new BigInteger()), $this->_normalize($x));
1476: }
1477:
1478:
1479: $msb = $y->value[count($y->value) - 1];
1480: for ($shift = 0; !($msb & MATH_BIGINTEGER_MSB); ++$shift) {
1481: $msb <<= 1;
1482: }
1483: $x->_lshift($shift);
1484: $y->_lshift($shift);
1485: $y_value = &$y->value;
1486:
1487: $x_max = count($x->value) - 1;
1488: $y_max = count($y->value) - 1;
1489:
1490: $quotient = new BigInteger();
1491: $quotient_value = &$quotient->value;
1492: $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
1493:
1494: static $temp, $lhs, $rhs;
1495: if (!isset($temp)) {
1496: $temp = new BigInteger();
1497: $lhs = new BigInteger();
1498: $rhs = new BigInteger();
1499: }
1500: $temp_value = &$temp->value;
1501: $rhs_value = &$rhs->value;
1502:
1503:
1504: $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
1505:
1506: while ( $x->compare($temp) >= 0 ) {
1507:
1508: ++$quotient_value[$x_max - $y_max];
1509: $x = $x->subtract($temp);
1510: $x_max = count($x->value) - 1;
1511: }
1512:
1513: for ($i = $x_max; $i >= $y_max + 1; --$i) {
1514: $x_value = &$x->value;
1515: $x_window = array(
1516: isset($x_value[$i]) ? $x_value[$i] : 0,
1517: isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
1518: isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
1519: );
1520: $y_window = array(
1521: $y_value[$y_max],
1522: ( $y_max > 0 ) ? $y_value[$y_max - 1] : 0
1523: );
1524:
1525: $q_index = $i - $y_max - 1;
1526: if ($x_window[0] == $y_window[0]) {
1527: $quotient_value[$q_index] = MATH_BIGINTEGER_MAX_DIGIT;
1528: } else {
1529: $quotient_value[$q_index] = (int) (
1530: ($x_window[0] * MATH_BIGINTEGER_BASE_FULL + $x_window[1])
1531: /
1532: $y_window[0]
1533: );
1534: }
1535:
1536: $temp_value = array($y_window[1], $y_window[0]);
1537:
1538: $lhs->value = array($quotient_value[$q_index]);
1539: $lhs = $lhs->multiply($temp);
1540:
1541: $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
1542:
1543: while ( $lhs->compare($rhs) > 0 ) {
1544: --$quotient_value[$q_index];
1545:
1546: $lhs->value = array($quotient_value[$q_index]);
1547: $lhs = $lhs->multiply($temp);
1548: }
1549:
1550: $adjust = $this->_array_repeat(0, $q_index);
1551: $temp_value = array($quotient_value[$q_index]);
1552: $temp = $temp->multiply($y);
1553: $temp_value = &$temp->value;
1554: $temp_value = array_merge($adjust, $temp_value);
1555:
1556: $x = $x->subtract($temp);
1557:
1558: if ($x->compare($zero) < 0) {
1559: $temp_value = array_merge($adjust, $y_value);
1560: $x = $x->add($temp);
1561:
1562: --$quotient_value[$q_index];
1563: }
1564:
1565: $x_max = count($x_value) - 1;
1566: }
1567:
1568:
1569: $x->_rshift($shift);
1570:
1571: $quotient->is_negative = $x_sign != $y_sign;
1572:
1573:
1574: if ( $x_sign ) {
1575: $y->_rshift($shift);
1576: $x = $y->subtract($x);
1577: }
1578:
1579: return array($this->_normalize($quotient), $this->_normalize($x));
1580: }
1581:
1582: 1583: 1584: 1585: 1586: 1587: 1588: 1589: 1590: 1591:
1592: function _divide_digit($dividend, $divisor)
1593: {
1594: $carry = 0;
1595: $result = array();
1596:
1597: for ($i = count($dividend) - 1; $i >= 0; --$i) {
1598: $temp = MATH_BIGINTEGER_BASE_FULL * $carry + $dividend[$i];
1599: $result[$i] = (int) ($temp / $divisor);
1600: $carry = (int) ($temp - $divisor * $result[$i]);
1601: }
1602:
1603: return array($result, $carry);
1604: }
1605:
1606:
1607:
1608: 1609: 1610: 1611: 1612: 1613: 1614: 1615: 1616: 1617: 1618: 1619: 1620: 1621: 1622: 1623: 1624: 1625: 1626: 1627: 1628:
1629: function legendre($p)
1630: {
1631: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP ) {
1632: $temp = new BigInteger();
1633: $temp->value = gmp_legendre($this->value, $p->value);
1634: return $this->_normalize($temp);
1635: }
1636:
1637: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
1638: $temp = new BigInteger();
1639:
1640: if ($p->value >= 3 && $p->value % 2 == 1) {
1641: $this->value = bcmod($this->value, $p->value);
1642: if($this->value == 0) {
1643: return 0;
1644: }
1645: if ($this->value == 1) {
1646: return 1;
1647: }
1648: $a1 = $this->value;
1649: $e = 0;
1650: while (bcmod($a1, 2) == 0) {
1651: $a1 = bcdiv($a1, 2);
1652: $e = bcadd($e, 1);
1653: }
1654: if (bcmod($e, 2) == 0 || bcmod($p->value, 8) == 1 || bcmod($p->value, 8) == 7) {
1655: $s = 1;
1656: } else {
1657: $s = -1;
1658: }
1659: if ($a1 == 1) {
1660: $temp->value = $s;
1661: return $this->_normalize($temp);
1662: }
1663: if (bcmod($p->value, 4) == 3 && bcmod($a1, 4) == 3) {
1664: $s = -$s;
1665: }
1666:
1667: $x = bcmod($p->value, $a1);
1668:
1669: $objx = new BigInteger($x);
1670: $obja1 = new BigInteger($a1);
1671:
1672: $temp->value = bcmul($s, $objx->legendre($obja1)->value);
1673: }
1674:
1675: return $this->_normalize($temp);
1676: }
1677:
1678:
1679:
1680: $temp = new BigInteger();
1681: $x = new BigInteger();
1682:
1683: if ($p->value >= 3 && $p->value % 2 == 1) {
1684: $temp = $this->mod($p);
1685:
1686: if($temp->value == 0) {
1687: return 0;
1688: }
1689: if ($temp->value == 1) {
1690: return 1;
1691: }
1692: $acopy = $temp->copy();
1693: $e = new BigInteger(0, 10);
1694: $one = new BigInteger(1, 10);
1695: $two = new BigInteger(2, 10);
1696: $four = new BigInteger(4, 10);
1697: $eight = new BigInteger(8, 10);
1698:
1699: while ($acopy->mod($two)->value == 0) {
1700: list($quo, $rem) = $acopy->divide($two);
1701: $acopy = $quo;
1702: $e = $e->add($one);
1703: }
1704: if ($e->mod($two)->value == 0 || $p->mod($eight)->value == 1 || $p->mod($eight)->value == 7) {
1705: $s = new BigInteger(1, 10);
1706: } else {
1707: $s = new BigInteger(-1, 10);
1708: }
1709: if ($acopy->value == 1) {
1710: return $s;
1711: }
1712: if ($p->mod($four)->value == 3 && $acopy->mod($four)->value == 3) {
1713: $s->value = -$s->value;
1714: }
1715:
1716: $x = $p->mod($acopy);
1717:
1718: $temp = $s->mul($x->legendre($acopy));
1719: }
1720:
1721: return $temp;
1722: }
1723:
1724:
1725:
1726:
1727:
1728: 1729: 1730: 1731: 1732: 1733: 1734: 1735: 1736: 1737: 1738: 1739: 1740: 1741: 1742: 1743: 1744: 1745: 1746: 1747: 1748:
1749: function mod($m)
1750: {
1751: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP ) {
1752: $temp = new BigInteger();
1753: $temp->value = gmp_mod($this->value, $m->value);
1754: return $this->_normalize($temp);
1755: }
1756:
1757: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
1758: $temp = new BigInteger();
1759: $temp->value = bcmod($this->value, $m->value);
1760: return $this->_normalize($temp);
1761: }
1762:
1763: list($quo, $rem) = $this->divide($m);
1764: return $this->subtract($quo->multiply($m));
1765: }
1766:
1767:
1768:
1769:
1770: 1771: 1772: 1773: 1774: 1775: 1776: 1777: 1778: 1779: 1780: 1781: 1782: 1783: 1784: 1785: 1786: 1787: 1788: 1789: 1790: 1791: 1792: 1793: 1794: 1795: 1796: 1797: 1798: 1799: 1800: 1801: 1802: 1803: 1804: 1805: 1806: 1807: 1808: 1809: 1810: 1811:
1812: function modPow($e, $n)
1813: {
1814: $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
1815:
1816: if ($e->compare(new BigInteger()) < 0) {
1817: $e = $e->abs();
1818:
1819: $temp = $this->modInverse($n);
1820: if ($temp === false) {
1821: return false;
1822: }
1823:
1824: return $this->_normalize($temp->modPow($e, $n));
1825: }
1826:
1827: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP ) {
1828: $temp = new BigInteger();
1829: $temp->value = gmp_powm($this->value, $e->value, $n->value);
1830:
1831: return $this->_normalize($temp);
1832: }
1833:
1834: if ($this->compare(new BigInteger()) < 0 || $this->compare($n) > 0) {
1835: list(, $temp) = $this->divide($n);
1836: return $temp->modPow($e, $n);
1837: }
1838:
1839: if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
1840: $components = array(
1841: 'modulus' => $n->toBytes(true),
1842: 'publicExponent' => $e->toBytes(true)
1843: );
1844:
1845: $components = array(
1846: 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
1847: 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
1848: );
1849:
1850: $RSAPublicKey = pack('Ca*a*a*',
1851: 48, $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
1852: $components['modulus'], $components['publicExponent']
1853: );
1854:
1855: $rsaOID = pack('H*', '300d06092a864886f70d0101010500');
1856: $RSAPublicKey = chr(0) . $RSAPublicKey;
1857: $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
1858:
1859: $encapsulated = pack('Ca*a*',
1860: 48, $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)), $rsaOID . $RSAPublicKey
1861: );
1862:
1863: $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
1864: chunk_split(base64_encode($encapsulated)) .
1865: '-----END PUBLIC KEY-----';
1866:
1867: $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
1868:
1869: if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
1870: return new BigInteger($result, 256);
1871: }
1872: }
1873:
1874: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
1875: $temp = new BigInteger();
1876: $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
1877:
1878: return $this->_normalize($temp);
1879: }
1880:
1881: if ( empty($e->value) ) {
1882: $temp = new BigInteger();
1883: $temp->value = array(1);
1884: return $this->_normalize($temp);
1885: }
1886:
1887: if ( $e->value == array(1) ) {
1888: list(, $temp) = $this->divide($n);
1889: return $this->_normalize($temp);
1890: }
1891:
1892: if ( $e->value == array(2) ) {
1893: $temp = new BigInteger();
1894: $temp->value = $this->_square($this->value);
1895: list(, $temp) = $temp->divide($n);
1896: return $this->_normalize($temp);
1897: }
1898:
1899: return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT));
1900:
1901:
1902: if ( $n->value[0] & 1 ) {
1903: return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY));
1904: }
1905:
1906:
1907:
1908: for ($i = 0; $i < count($n->value); ++$i) {
1909: if ( $n->value[$i] ) {
1910: $temp = decbin($n->value[$i]);
1911: $j = strlen($temp) - strrpos($temp, '1') - 1;
1912: $j+= 26 * $i;
1913: break;
1914: }
1915: }
1916:
1917:
1918: $mod1 = $n->copy();
1919: $mod1->_rshift($j);
1920: $mod2 = new BigInteger();
1921: $mod2->value = array(1);
1922: $mod2->_lshift($j);
1923:
1924: $part1 = ( $mod1->value != array(1) ) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new BigInteger();
1925: $part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2);
1926:
1927: $y1 = $mod2->modInverse($mod1);
1928: $y2 = $mod1->modInverse($mod2);
1929:
1930: $result = $part1->multiply($mod2);
1931: $result = $result->multiply($y1);
1932:
1933: $temp = $part2->multiply($mod1);
1934: $temp = $temp->multiply($y2);
1935:
1936: $result = $result->add($temp);
1937: list(, $result) = $result->divide($n);
1938:
1939: return $this->_normalize($result);
1940: }
1941:
1942: 1943: 1944: 1945: 1946: 1947: 1948: 1949: 1950: 1951:
1952: function powMod($e, $n)
1953: {
1954: return $this->modPow($e, $n);
1955: }
1956:
1957: 1958: 1959: 1960: 1961: 1962: 1963: 1964: 1965: 1966: 1967: 1968: 1969: 1970:
1971: function _slidingWindow($e, $n, $mode)
1972: {
1973: static $window_ranges = array(7, 25, 81, 241, 673, 1793);
1974:
1975:
1976: $e_value = $e->value;
1977: $e_length = count($e_value) - 1;
1978: $e_bits = decbin($e_value[$e_length]);
1979: for ($i = $e_length - 1; $i >= 0; --$i) {
1980: $e_bits.= str_pad(decbin($e_value[$i]), MATH_BIGINTEGER_BASE, '0', STR_PAD_LEFT);
1981: }
1982:
1983: $e_length = strlen($e_bits);
1984:
1985:
1986:
1987: for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); ++$window_size, ++$i);
1988:
1989: $n_value = $n->value;
1990:
1991:
1992: $powers = array();
1993: $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
1994: $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
1995:
1996:
1997:
1998: $temp = 1 << ($window_size - 1);
1999: for ($i = 1; $i < $temp; ++$i) {
2000: $i2 = $i << 1;
2001: $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
2002: }
2003:
2004: $result = array(1);
2005: $result = $this->_prepareReduce($result, $n_value, $mode);
2006:
2007: for ($i = 0; $i < $e_length; ) {
2008: if ( !$e_bits[$i] ) {
2009: $result = $this->_squareReduce($result, $n_value, $mode);
2010: ++$i;
2011: } else {
2012: for ($j = $window_size - 1; $j > 0; --$j) {
2013: if ( !empty($e_bits[$i + $j]) ) {
2014: break;
2015: }
2016: }
2017:
2018: for ($k = 0; $k <= $j; ++$k) {
2019: $result = $this->_squareReduce($result, $n_value, $mode);
2020: }
2021:
2022: $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
2023:
2024: $i+=$j + 1;
2025: }
2026: }
2027:
2028: $temp = new BigInteger();
2029: $temp->value = $this->_reduce($result, $n_value, $mode);
2030:
2031: return $temp;
2032: }
2033:
2034: 2035: 2036: 2037: 2038: 2039: 2040: 2041: 2042: 2043: 2044: 2045:
2046: function _reduce($x, $n, $mode)
2047: {
2048: switch ($mode) {
2049: case MATH_BIGINTEGER_MONTGOMERY:
2050: return $this->_montgomery($x, $n);
2051: case MATH_BIGINTEGER_BARRETT:
2052: return $this->_barrett($x, $n);
2053: case MATH_BIGINTEGER_POWEROF2:
2054: $lhs = new BigInteger();
2055: $lhs->value = $x;
2056: $rhs = new BigInteger();
2057: $rhs->value = $n;
2058: return $x->_mod2($n);
2059: case MATH_BIGINTEGER_CLASSIC:
2060: $lhs = new BigInteger();
2061: $lhs->value = $x;
2062: $rhs = new BigInteger();
2063: $rhs->value = $n;
2064: list(, $temp) = $lhs->divide($rhs);
2065: return $temp->value;
2066: case MATH_BIGINTEGER_NONE:
2067: return $x;
2068: default:
2069:
2070: }
2071: }
2072:
2073: 2074: 2075: 2076: 2077: 2078: 2079: 2080: 2081: 2082:
2083: function _prepareReduce($x, $n, $mode)
2084: {
2085: if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
2086: return $this->_prepMontgomery($x, $n);
2087: }
2088: return $this->_reduce($x, $n, $mode);
2089: }
2090:
2091: 2092: 2093: 2094: 2095: 2096: 2097: 2098: 2099: 2100: 2101:
2102: function _multiplyReduce($x, $y, $n, $mode)
2103: {
2104: if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
2105: return $this->_montgomeryMultiply($x, $y, $n);
2106: }
2107: $temp = $this->_multiply($x, false, $y, false);
2108: return $this->_reduce($temp[MATH_BIGINTEGER_VALUE], $n, $mode);
2109: }
2110:
2111: 2112: 2113: 2114: 2115: 2116: 2117: 2118: 2119: 2120:
2121: function _squareReduce($x, $n, $mode)
2122: {
2123: if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
2124: return $this->_montgomeryMultiply($x, $x, $n);
2125: }
2126: return $this->_reduce($this->_square($x), $n, $mode);
2127: }
2128:
2129: 2130: 2131: 2132: 2133: 2134: 2135: 2136: 2137: 2138: 2139:
2140: function _mod2($n)
2141: {
2142: $temp = new BigInteger();
2143: $temp->value = array(1);
2144: return $this->bitwise_and($n->subtract($temp));
2145: }
2146:
2147: 2148: 2149: 2150: 2151: 2152: 2153: 2154: 2155: 2156: 2157: 2158: 2159: 2160: 2161: 2162: 2163: 2164: 2165: 2166: 2167: 2168: 2169: 2170:
2171: function _barrett($n, $m)
2172: {
2173: static $cache = array(
2174: MATH_BIGINTEGER_VARIABLE => array(),
2175: MATH_BIGINTEGER_DATA => array()
2176: );
2177:
2178: $m_length = count($m);
2179:
2180:
2181: if (count($n) > 2 * $m_length) {
2182: $lhs = new BigInteger();
2183: $rhs = new BigInteger();
2184: $lhs->value = $n;
2185: $rhs->value = $m;
2186: list(, $temp) = $lhs->divide($rhs);
2187: return $temp->value;
2188: }
2189:
2190:
2191: if ($m_length < 5) {
2192: return $this->_regularBarrett($n, $m);
2193: }
2194:
2195:
2196:
2197: if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
2198: $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
2199: $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
2200:
2201: $lhs = new BigInteger();
2202: $lhs_value = &$lhs->value;
2203: $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
2204: $lhs_value[] = 1;
2205: $rhs = new BigInteger();
2206: $rhs->value = $m;
2207:
2208: list($u, $m1) = $lhs->divide($rhs);
2209: $u = $u->value;
2210: $m1 = $m1->value;
2211:
2212: $cache[MATH_BIGINTEGER_DATA][] = array(
2213: 'u' => $u,
2214: 'm1'=> $m1
2215: );
2216: } else {
2217: extract($cache[MATH_BIGINTEGER_DATA][$key]);
2218: }
2219:
2220: $cutoff = $m_length + ($m_length >> 1);
2221: $lsd = array_slice($n, 0, $cutoff);
2222: $msd = array_slice($n, $cutoff);
2223: $lsd = $this->_trim($lsd);
2224: $temp = $this->_multiply($msd, false, $m1, false);
2225: $n = $this->_add($lsd, false, $temp[MATH_BIGINTEGER_VALUE], false);
2226:
2227: if ($m_length & 1) {
2228: return $this->_regularBarrett($n[MATH_BIGINTEGER_VALUE], $m);
2229: }
2230:
2231:
2232: $temp = array_slice($n[MATH_BIGINTEGER_VALUE], $m_length - 1);
2233:
2234:
2235: $temp = $this->_multiply($temp, false, $u, false);
2236:
2237:
2238: $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], ($m_length >> 1) + 1);
2239:
2240:
2241: $temp = $this->_multiply($temp, false, $m, false);
2242:
2243:
2244:
2245:
2246:
2247: $result = $this->_subtract($n[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
2248:
2249: while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false) >= 0) {
2250: $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false);
2251: }
2252:
2253: return $result[MATH_BIGINTEGER_VALUE];
2254: }
2255:
2256: 2257: 2258: 2259: 2260: 2261: 2262: 2263: 2264: 2265: 2266: 2267:
2268: function _regularBarrett($x, $n)
2269: {
2270: static $cache = array(
2271: MATH_BIGINTEGER_VARIABLE => array(),
2272: MATH_BIGINTEGER_DATA => array()
2273: );
2274:
2275: $n_length = count($n);
2276:
2277: if (count($x) > 2 * $n_length) {
2278: $lhs = new BigInteger();
2279: $rhs = new BigInteger();
2280: $lhs->value = $x;
2281: $rhs->value = $n;
2282: list(, $temp) = $lhs->divide($rhs);
2283: return $temp->value;
2284: }
2285:
2286: if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
2287: $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
2288: $cache[MATH_BIGINTEGER_VARIABLE][] = $n;
2289: $lhs = new BigInteger();
2290: $lhs_value = &$lhs->value;
2291: $lhs_value = $this->_array_repeat(0, 2 * $n_length);
2292: $lhs_value[] = 1;
2293: $rhs = new BigInteger();
2294: $rhs->value = $n;
2295: list($temp, ) = $lhs->divide($rhs);
2296: $cache[MATH_BIGINTEGER_DATA][] = $temp->value;
2297: }
2298:
2299:
2300: $temp = array_slice($x, $n_length - 1);
2301:
2302: $temp = $this->_multiply($temp, false, $cache[MATH_BIGINTEGER_DATA][$key], false);
2303:
2304: $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], $n_length + 1);
2305:
2306:
2307: $result = array_slice($x, 0, $n_length + 1);
2308:
2309: $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
2310:
2311:
2312: if ($this->_compare($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]) < 0) {
2313: $corrector_value = $this->_array_repeat(0, $n_length + 1);
2314: $corrector_value[] = 1;
2315: $result = $this->_add($result, false, $corrector_value, false);
2316: $result = $result[MATH_BIGINTEGER_VALUE];
2317: }
2318:
2319:
2320: $result = $this->_subtract($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]);
2321: while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false) > 0) {
2322: $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false);
2323: }
2324:
2325: return $result[MATH_BIGINTEGER_VALUE];
2326: }
2327:
2328: 2329: 2330: 2331: 2332: 2333: 2334: 2335: 2336: 2337: 2338: 2339: 2340: 2341:
2342: function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
2343: {
2344: $x_length = count($x_value);
2345: $y_length = count($y_value);
2346:
2347: if ( !$x_length || !$y_length ) {
2348: return array(
2349: MATH_BIGINTEGER_VALUE => array(),
2350: MATH_BIGINTEGER_SIGN => false
2351: );
2352: }
2353:
2354: if ( $x_length < $y_length ) {
2355: $temp = $x_value;
2356: $x_value = $y_value;
2357: $y_value = $temp;
2358:
2359: $x_length = count($x_value);
2360: $y_length = count($y_value);
2361: }
2362:
2363: $product_value = $this->_array_repeat(0, $x_length + $y_length);
2364:
2365:
2366:
2367:
2368:
2369:
2370:
2371: $carry = 0;
2372:
2373: for ($j = 0; $j < $x_length; ++$j) {
2374: $temp = $x_value[$j] * $y_value[0] + $carry;
2375: $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
2376: $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
2377: }
2378:
2379: if ($j < $stop) {
2380: $product_value[$j] = $carry;
2381: }
2382:
2383:
2384:
2385:
2386: for ($i = 1; $i < $y_length; ++$i) {
2387: $carry = 0;
2388:
2389: for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
2390: $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
2391: $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
2392: $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
2393: }
2394:
2395: if ($k < $stop) {
2396: $product_value[$k] = $carry;
2397: }
2398: }
2399:
2400: return array(
2401: MATH_BIGINTEGER_VALUE => $this->_trim($product_value),
2402: MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
2403: );
2404: }
2405:
2406: 2407: 2408: 2409: 2410: 2411: 2412: 2413: 2414: 2415: 2416: 2417: 2418: 2419: 2420:
2421: function _montgomery($x, $n)
2422: {
2423: static $cache = array(
2424: MATH_BIGINTEGER_VARIABLE => array(),
2425: MATH_BIGINTEGER_DATA => array()
2426: );
2427:
2428: if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
2429: $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
2430: $cache[MATH_BIGINTEGER_VARIABLE][] = $x;
2431: $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($n);
2432: }
2433:
2434: $k = count($n);
2435:
2436: $result = array(MATH_BIGINTEGER_VALUE => $x);
2437:
2438: for ($i = 0; $i < $k; ++$i) {
2439: $temp = $result[MATH_BIGINTEGER_VALUE][$i] * $cache[MATH_BIGINTEGER_DATA][$key];
2440: $temp = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * ((int) ($temp / MATH_BIGINTEGER_BASE_FULL)));
2441: $temp = $this->_regularMultiply(array($temp), $n);
2442: $temp = array_merge($this->_array_repeat(0, $i), $temp);
2443: $result = $this->_add($result[MATH_BIGINTEGER_VALUE], false, $temp, false);
2444: }
2445:
2446: $result[MATH_BIGINTEGER_VALUE] = array_slice($result[MATH_BIGINTEGER_VALUE], $k);
2447:
2448: if ($this->_compare($result, false, $n, false) >= 0) {
2449: $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], false, $n, false);
2450: }
2451:
2452: return $result[MATH_BIGINTEGER_VALUE];
2453: }
2454:
2455: 2456: 2457: 2458: 2459: 2460: 2461: 2462: 2463: 2464: 2465: 2466: 2467: 2468:
2469: function _montgomeryMultiply($x, $y, $m)
2470: {
2471: $temp = $this->_multiply($x, false, $y, false);
2472: return $this->_montgomery($temp[MATH_BIGINTEGER_VALUE], $m);
2473:
2474: static $cache = array(
2475: MATH_BIGINTEGER_VARIABLE => array(),
2476: MATH_BIGINTEGER_DATA => array()
2477: );
2478:
2479: if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
2480: $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
2481: $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
2482: $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($m);
2483: }
2484:
2485: $n = max(count($x), count($y), count($m));
2486: $x = array_pad($x, $n, 0);
2487: $y = array_pad($y, $n, 0);
2488: $m = array_pad($m, $n, 0);
2489: $a = array(MATH_BIGINTEGER_VALUE => $this->_array_repeat(0, $n + 1));
2490: for ($i = 0; $i < $n; ++$i) {
2491: $temp = $a[MATH_BIGINTEGER_VALUE][0] + $x[$i] * $y[0];
2492: $temp = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * ((int) ($temp / MATH_BIGINTEGER_BASE_FULL)));
2493: $temp = $temp * $cache[MATH_BIGINTEGER_DATA][$key];
2494: $temp = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * ((int) ($temp / MATH_BIGINTEGER_BASE_FULL)));
2495: $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
2496: $a = $this->_add($a[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
2497: $a[MATH_BIGINTEGER_VALUE] = array_slice($a[MATH_BIGINTEGER_VALUE], 1);
2498: }
2499: if ($this->_compare($a[MATH_BIGINTEGER_VALUE], false, $m, false) >= 0) {
2500: $a = $this->_subtract($a[MATH_BIGINTEGER_VALUE], false, $m, false);
2501: }
2502: return $a[MATH_BIGINTEGER_VALUE];
2503: }
2504:
2505: 2506: 2507: 2508: 2509: 2510: 2511: 2512: 2513: 2514:
2515: function _prepMontgomery($x, $n)
2516: {
2517: $lhs = new BigInteger();
2518: $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
2519: $rhs = new BigInteger();
2520: $rhs->value = $n;
2521:
2522: list(, $temp) = $lhs->divide($rhs);
2523: return $temp->value;
2524: }
2525:
2526: 2527: 2528: 2529: 2530: 2531: 2532: 2533: 2534: 2535: 2536: 2537: 2538: 2539: 2540: 2541: 2542: 2543: 2544: 2545: 2546: 2547: 2548: 2549: 2550: 2551:
2552: function _modInverse67108864($x)
2553: {
2554: $x = -$x[0];
2555: $result = $x & 0x3;
2556: $result = ($result * (2 - $x * $result)) & 0xF;
2557: $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF;
2558: $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF;
2559: $result = fmod($result * (2 - fmod($x * $result, MATH_BIGINTEGER_BASE_FULL)), MATH_BIGINTEGER_BASE_FULL);
2560: return $result & MATH_BIGINTEGER_MAX_DIGIT;
2561: }
2562:
2563: 2564: 2565: 2566: 2567: 2568: 2569: 2570: 2571: 2572: 2573: 2574: 2575: 2576: 2577: 2578: 2579: 2580: 2581: 2582: 2583: 2584: 2585: 2586: 2587: 2588: 2589: 2590: 2591:
2592: function modInverse($n)
2593: {
2594: switch ( MATH_BIGINTEGER_MODE ) {
2595: case MATH_BIGINTEGER_MODE_GMP:
2596: $temp = new BigInteger();
2597: $temp->value = gmp_invert($this->value, $n->value);
2598:
2599: return ( $temp->value === false ) ? false : $this->_normalize($temp);
2600: }
2601:
2602: static $zero, $one;
2603: if (!isset($zero)) {
2604: $zero = new BigInteger();
2605: $one = new BigInteger(1);
2606: }
2607:
2608:
2609: $n = $n->abs();
2610:
2611: if ($this->compare($zero) < 0) {
2612: $temp = $this->abs();
2613: $temp = $temp->modInverse($n);
2614: return $this->_normalize($n->subtract($temp));
2615: }
2616:
2617: extract($this->extendedGCD($n));
2618:
2619: if (!$gcd->equals($one)) {
2620: return false;
2621: }
2622:
2623: $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
2624:
2625: return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
2626: }
2627:
2628: 2629: 2630: 2631: 2632: 2633: 2634: 2635: 2636: 2637: 2638: 2639: 2640: 2641: 2642: 2643: 2644: 2645: 2646: 2647: 2648: 2649: 2650: 2651: 2652: 2653: 2654: 2655: 2656: 2657:
2658: function extendedGCD($n)
2659: {
2660: switch ( MATH_BIGINTEGER_MODE ) {
2661: case MATH_BIGINTEGER_MODE_GMP:
2662: extract(gmp_gcdext($this->value, $n->value));
2663:
2664: return array(
2665: 'gcd' => $this->_normalize(new BigInteger($g)),
2666: 'x' => $this->_normalize(new BigInteger($s)),
2667: 'y' => $this->_normalize(new BigInteger($t))
2668: );
2669: case MATH_BIGINTEGER_MODE_BCMATH:
2670:
2671:
2672:
2673:
2674: $u = $this->value;
2675: $v = $n->value;
2676:
2677: $a = '1';
2678: $b = '0';
2679: $c = '0';
2680: $d = '1';
2681:
2682: while (bccomp($v, '0', 0) != 0) {
2683: $q = bcdiv($u, $v, 0);
2684:
2685: $temp = $u;
2686: $u = $v;
2687: $v = bcsub($temp, bcmul($v, $q, 0), 0);
2688:
2689: $temp = $a;
2690: $a = $c;
2691: $c = bcsub($temp, bcmul($a, $q, 0), 0);
2692:
2693: $temp = $b;
2694: $b = $d;
2695: $d = bcsub($temp, bcmul($b, $q, 0), 0);
2696: }
2697:
2698: return array(
2699: 'gcd' => $this->_normalize(new BigInteger($u)),
2700: 'x' => $this->_normalize(new BigInteger($a)),
2701: 'y' => $this->_normalize(new BigInteger($b))
2702: );
2703: }
2704:
2705: $y = $n->copy();
2706: $x = $this->copy();
2707: $g = new BigInteger();
2708: $g->value = array(1);
2709:
2710: while ( !(($x->value[0] & 1)|| ($y->value[0] & 1)) ) {
2711: $x->_rshift(1);
2712: $y->_rshift(1);
2713: $g->_lshift(1);
2714: }
2715:
2716: $u = $x->copy();
2717: $v = $y->copy();
2718:
2719: $a = new BigInteger();
2720: $b = new BigInteger();
2721: $c = new BigInteger();
2722: $d = new BigInteger();
2723:
2724: $a->value = $d->value = $g->value = array(1);
2725: $b->value = $c->value = array();
2726:
2727: while ( !empty($u->value) ) {
2728: while ( !($u->value[0] & 1) ) {
2729: $u->_rshift(1);
2730: if ( (!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1)) ) {
2731: $a = $a->add($y);
2732: $b = $b->subtract($x);
2733: }
2734: $a->_rshift(1);
2735: $b->_rshift(1);
2736: }
2737:
2738: while ( !($v->value[0] & 1) ) {
2739: $v->_rshift(1);
2740: if ( (!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1)) ) {
2741: $c = $c->add($y);
2742: $d = $d->subtract($x);
2743: }
2744: $c->_rshift(1);
2745: $d->_rshift(1);
2746: }
2747:
2748: if ($u->compare($v) >= 0) {
2749: $u = $u->subtract($v);
2750: $a = $a->subtract($c);
2751: $b = $b->subtract($d);
2752: } else {
2753: $v = $v->subtract($u);
2754: $c = $c->subtract($a);
2755: $d = $d->subtract($b);
2756: }
2757: }
2758:
2759: return array(
2760: 'gcd' => $this->_normalize($g->multiply($v)),
2761: 'x' => $this->_normalize($c),
2762: 'y' => $this->_normalize($d)
2763: );
2764: }
2765:
2766: 2767: 2768: 2769: 2770: 2771: 2772: 2773: 2774: 2775: 2776: 2777: 2778: 2779: 2780: 2781: 2782: 2783: 2784: 2785: 2786: 2787: 2788:
2789: function gcd($n)
2790: {
2791: extract($this->extendedGCD($n));
2792: return $gcd;
2793: }
2794:
2795: 2796: 2797: 2798: 2799: 2800:
2801: function abs()
2802: {
2803: $temp = new BigInteger();
2804:
2805: switch ( MATH_BIGINTEGER_MODE ) {
2806: case MATH_BIGINTEGER_MODE_GMP:
2807: $temp->value = gmp_abs($this->value);
2808: break;
2809: case MATH_BIGINTEGER_MODE_BCMATH:
2810: $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
2811: break;
2812: default:
2813: $temp->value = $this->value;
2814: }
2815:
2816: return $temp;
2817: }
2818:
2819: 2820: 2821: 2822: 2823: 2824: 2825: 2826: 2827: 2828: 2829: 2830: 2831: 2832: 2833: 2834: 2835: 2836:
2837: function compare($y)
2838: {
2839: switch ( MATH_BIGINTEGER_MODE ) {
2840: case MATH_BIGINTEGER_MODE_GMP:
2841: return gmp_cmp($this->value, $y->value);
2842: case MATH_BIGINTEGER_MODE_BCMATH:
2843: return bccomp($this->value, $y->value, 0);
2844: }
2845:
2846: return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
2847: }
2848:
2849: 2850: 2851: 2852: 2853: 2854: 2855: 2856: 2857: 2858: 2859:
2860: function _compare($x_value, $x_negative, $y_value, $y_negative)
2861: {
2862: if ( $x_negative != $y_negative ) {
2863: return ( !$x_negative && $y_negative ) ? 1 : -1;
2864: }
2865:
2866: $result = $x_negative ? -1 : 1;
2867:
2868: if ( count($x_value) != count($y_value) ) {
2869: return ( count($x_value) > count($y_value) ) ? $result : -$result;
2870: }
2871: $size = max(count($x_value), count($y_value));
2872:
2873: $x_value = array_pad($x_value, $size, 0);
2874: $y_value = array_pad($y_value, $size, 0);
2875:
2876: for ($i = count($x_value) - 1; $i >= 0; --$i) {
2877: if ($x_value[$i] != $y_value[$i]) {
2878: return ( $x_value[$i] > $y_value[$i] ) ? $result : -$result;
2879: }
2880: }
2881:
2882: return 0;
2883: }
2884:
2885: 2886: 2887: 2888: 2889: 2890: 2891: 2892: 2893: 2894:
2895: function equals($x)
2896: {
2897: switch ( MATH_BIGINTEGER_MODE ) {
2898: case MATH_BIGINTEGER_MODE_GMP:
2899: return gmp_cmp($this->value, $x->value) == 0;
2900: default:
2901: return $this->value === $x->value && $this->is_negative == $x->is_negative;
2902: }
2903: }
2904:
2905: 2906: 2907: 2908: 2909: 2910: 2911: 2912: 2913:
2914: function setPrecision($bits)
2915: {
2916: $this->precision = $bits;
2917: if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ) {
2918: $this->bitmask = new BigInteger(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
2919: } else {
2920: $this->bitmask = new BigInteger(bcpow('2', $bits, 0));
2921: }
2922:
2923: $temp = $this->_normalize($this);
2924: $this->value = $temp->value;
2925: }
2926:
2927: 2928: 2929: 2930: 2931: 2932: 2933: 2934:
2935: function bitwise_and($x)
2936: {
2937: switch ( MATH_BIGINTEGER_MODE ) {
2938: case MATH_BIGINTEGER_MODE_GMP:
2939: $temp = new BigInteger();
2940: $temp->value = gmp_and($this->value, $x->value);
2941:
2942: return $this->_normalize($temp);
2943: case MATH_BIGINTEGER_MODE_BCMATH:
2944: $left = $this->toBytes();
2945: $right = $x->toBytes();
2946:
2947: $length = max(strlen($left), strlen($right));
2948:
2949: $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2950: $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2951:
2952: return $this->_normalize(new BigInteger($left & $right, 256));
2953: }
2954:
2955: $result = $this->copy();
2956:
2957: $length = min(count($x->value), count($this->value));
2958:
2959: $result->value = array_slice($result->value, 0, $length);
2960:
2961: for ($i = 0; $i < $length; ++$i) {
2962: $result->value[$i]&= $x->value[$i];
2963: }
2964:
2965: return $this->_normalize($result);
2966: }
2967:
2968: 2969: 2970: 2971: 2972: 2973: 2974: 2975:
2976: function bitwise_or($x)
2977: {
2978: switch ( MATH_BIGINTEGER_MODE ) {
2979: case MATH_BIGINTEGER_MODE_GMP:
2980: $temp = new BigInteger();
2981: $temp->value = gmp_or($this->value, $x->value);
2982:
2983: return $this->_normalize($temp);
2984: case MATH_BIGINTEGER_MODE_BCMATH:
2985: $left = $this->toBytes();
2986: $right = $x->toBytes();
2987:
2988: $length = max(strlen($left), strlen($right));
2989:
2990: $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2991: $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2992:
2993: return $this->_normalize(new BigInteger($left | $right, 256));
2994: }
2995:
2996: $length = max(count($this->value), count($x->value));
2997: $result = $this->copy();
2998: $result->value = array_pad($result->value, $length, 0);
2999: $x->value = array_pad($x->value, $length, 0);
3000:
3001: for ($i = 0; $i < $length; ++$i) {
3002: $result->value[$i]|= $x->value[$i];
3003: }
3004:
3005: return $this->_normalize($result);
3006: }
3007:
3008: 3009: 3010: 3011: 3012: 3013: 3014: 3015:
3016: function bitwise_xor($x)
3017: {
3018: switch ( MATH_BIGINTEGER_MODE ) {
3019: case MATH_BIGINTEGER_MODE_GMP:
3020: $temp = new BigInteger();
3021: $temp->value = gmp_xor($this->value, $x->value);
3022:
3023: return $this->_normalize($temp);
3024: case MATH_BIGINTEGER_MODE_BCMATH:
3025: $left = $this->toBytes();
3026: $right = $x->toBytes();
3027:
3028: $length = max(strlen($left), strlen($right));
3029:
3030: $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
3031: $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
3032:
3033: return $this->_normalize(new BigInteger($left ^ $right, 256));
3034: }
3035:
3036: $length = max(count($this->value), count($x->value));
3037: $result = $this->copy();
3038: $result->value = array_pad($result->value, $length, 0);
3039: $x->value = array_pad($x->value, $length, 0);
3040:
3041: for ($i = 0; $i < $length; ++$i) {
3042: $result->value[$i]^= $x->value[$i];
3043: }
3044:
3045: return $this->_normalize($result);
3046: }
3047:
3048: 3049: 3050: 3051: 3052: 3053: 3054:
3055: function bitwise_not()
3056: {
3057:
3058:
3059: $temp = $this->toBytes();
3060: $pre_msb = decbin(ord($temp[0]));
3061: $temp = ~$temp;
3062: $msb = decbin(ord($temp[0]));
3063: if (strlen($msb) == 8) {
3064: $msb = substr($msb, strpos($msb, '0'));
3065: }
3066: $temp[0] = chr(bindec($msb));
3067:
3068:
3069: $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
3070: $new_bits = $this->precision - $current_bits;
3071: if ($new_bits <= 0) {
3072: return $this->_normalize(new BigInteger($temp, 256));
3073: }
3074:
3075:
3076: $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
3077: $this->_base256_lshift($leading_ones, $current_bits);
3078:
3079: $temp = str_pad($temp, ceil($this->bits / 8), chr(0), STR_PAD_LEFT);
3080:
3081: return $this->_normalize(new BigInteger($leading_ones | $temp, 256));
3082: }
3083:
3084: 3085: 3086: 3087: 3088: 3089: 3090: 3091: 3092: 3093:
3094: function bitwise_rightShift($shift)
3095: {
3096: $temp = new BigInteger();
3097:
3098: switch ( MATH_BIGINTEGER_MODE ) {
3099: case MATH_BIGINTEGER_MODE_GMP:
3100: static $two;
3101:
3102: if (!isset($two)) {
3103: $two = gmp_init('2');
3104: }
3105:
3106: $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
3107:
3108: break;
3109: case MATH_BIGINTEGER_MODE_BCMATH:
3110: $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
3111:
3112: break;
3113: default:
3114:
3115: $temp->value = $this->value;
3116: $temp->_rshift($shift);
3117: }
3118:
3119: return $this->_normalize($temp);
3120: }
3121:
3122: 3123: 3124: 3125: 3126: 3127: 3128: 3129: 3130: 3131:
3132: function bitwise_leftShift($shift)
3133: {
3134: $temp = new BigInteger();
3135:
3136: switch ( MATH_BIGINTEGER_MODE ) {
3137: case MATH_BIGINTEGER_MODE_GMP:
3138: static $two;
3139:
3140: if (!isset($two)) {
3141: $two = gmp_init('2');
3142: }
3143:
3144: $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
3145:
3146: break;
3147: case MATH_BIGINTEGER_MODE_BCMATH:
3148: $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
3149:
3150: break;
3151: default:
3152:
3153: $temp->value = $this->value;
3154: $temp->_lshift($shift);
3155: }
3156:
3157: return $this->_normalize($temp);
3158: }
3159:
3160: 3161: 3162: 3163: 3164: 3165: 3166: 3167: 3168:
3169: function bitwise_leftRotate($shift)
3170: {
3171: $bits = $this->toBytes();
3172:
3173: if ($this->precision > 0) {
3174: $precision = $this->precision;
3175: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
3176: $mask = $this->bitmask->subtract(new BigInteger(1));
3177: $mask = $mask->toBytes();
3178: } else {
3179: $mask = $this->bitmask->toBytes();
3180: }
3181: } else {
3182: $temp = ord($bits[0]);
3183: for ($i = 0; $temp >> $i; ++$i);
3184: $precision = 8 * strlen($bits) - 8 + $i;
3185: $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
3186: }
3187:
3188: if ($shift < 0) {
3189: $shift+= $precision;
3190: }
3191: $shift%= $precision;
3192:
3193: if (!$shift) {
3194: return $this->copy();
3195: }
3196:
3197: $left = $this->bitwise_leftShift($shift);
3198: $left = $left->bitwise_and(new BigInteger($mask, 256));
3199: $right = $this->bitwise_rightShift($precision - $shift);
3200: $result = MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
3201: return $this->_normalize($result);
3202: }
3203:
3204: 3205: 3206: 3207: 3208: 3209: 3210: 3211: 3212:
3213: function bitwise_rightRotate($shift)
3214: {
3215: return $this->bitwise_leftRotate(-$shift);
3216: }
3217:
3218: 3219: 3220: 3221: 3222: 3223: 3224: 3225:
3226: function setRandomGenerator($generator)
3227: {
3228: }
3229:
3230: 3231: 3232: 3233: 3234: 3235: 3236: 3237: 3238:
3239: function _random_number_helper($size)
3240: {
3241: $crypt_random = function_exists('crypt_random_string') || (!class_exists('Crypt_Random') && function_exists('crypt_random_string'));
3242: if ($crypt_random) {
3243: $random = crypt_random_string($size);
3244: } else {
3245: $random = '';
3246:
3247: if ($size & 1) {
3248: $random.= chr(mt_rand(0, 255));
3249: }
3250:
3251: $blocks = $size >> 1;
3252: for ($i = 0; $i < $blocks; ++$i) {
3253:
3254: $random.= pack('n', mt_rand(0, 0xFFFF));
3255: }
3256: }
3257:
3258: return new BigInteger($random, 256);
3259: }
3260:
3261: 3262: 3263: 3264: 3265: 3266: 3267: 3268:
3269: function random($min = false, $max = false)
3270: {
3271: if ($min === false) {
3272: $min = new BigInteger(0);
3273: }
3274:
3275: if ($max === false) {
3276: $max = new BigInteger(0x7FFFFFFF);
3277: }
3278:
3279: $compare = $max->compare($min);
3280:
3281: if (!$compare) {
3282: return $this->_normalize($min);
3283: } else if ($compare < 0) {
3284:
3285: $temp = $max;
3286: $max = $min;
3287: $min = $temp;
3288: }
3289:
3290: static $one;
3291: if (!isset($one)) {
3292: $one = new BigInteger(1);
3293: }
3294:
3295: $max = $max->subtract($min->subtract($one));
3296: $size = strlen(ltrim($max->toBytes(), chr(0)));
3297:
3298: 3299: 3300: 3301: 3302: 3303: 3304: 3305: 3306: 3307: 3308: 3309: 3310: 3311: 3312:
3313: $random_max = new BigInteger(chr(1) . str_repeat("\0", $size), 256);
3314: $random = $this->_random_number_helper($size);
3315:
3316: list($max_multiple) = $random_max->divide($max);
3317: $max_multiple = $max_multiple->multiply($max);
3318:
3319: while ($random->compare($max_multiple) >= 0) {
3320: $random = $random->subtract($max_multiple);
3321: $random_max = $random_max->subtract($max_multiple);
3322: $random = $random->bitwise_leftShift(8);
3323: $random = $random->add($this->_random_number_helper(1));
3324: $random_max = $random_max->bitwise_leftShift(8);
3325: list($max_multiple) = $random_max->divide($max);
3326: $max_multiple = $max_multiple->multiply($max);
3327: }
3328: list(, $random) = $random->divide($max);
3329:
3330: return $this->_normalize($random->add($min));
3331: }
3332:
3333: 3334: 3335: 3336: 3337: 3338: 3339: 3340: 3341: 3342: 3343: 3344: 3345:
3346: function randomPrime($min = false, $max = false, $timeout = false)
3347: {
3348: if ($min === false) {
3349: $min = new BigInteger(0);
3350: }
3351:
3352: if ($max === false) {
3353: $max = new BigInteger(0x7FFFFFFF);
3354: }
3355:
3356: $compare = $max->compare($min);
3357:
3358: if (!$compare) {
3359: return $min->isPrime() ? $min : false;
3360: } else if ($compare < 0) {
3361:
3362: $temp = $max;
3363: $max = $min;
3364: $min = $temp;
3365: }
3366:
3367: static $one, $two;
3368: if (!isset($one)) {
3369: $one = new BigInteger(1);
3370: $two = new BigInteger(2);
3371: }
3372:
3373: $start = time();
3374:
3375: $x = $this->random($min, $max);
3376:
3377:
3378: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP && function_exists('gmp_nextprime') ) {
3379: $p = new BigInteger();
3380: $p->value = gmp_nextprime($x->value);
3381:
3382: if ($p->compare($max) <= 0) {
3383: return $p;
3384: }
3385:
3386: if (!$min->equals($x)) {
3387: $x = $x->subtract($one);
3388: }
3389:
3390: return $x->randomPrime($min, $x);
3391: }
3392:
3393: if ($x->equals($two)) {
3394: return $x;
3395: }
3396:
3397: $x->_make_odd();
3398: if ($x->compare($max) > 0) {
3399:
3400: if ($min->equals($max)) {
3401: return false;
3402: }
3403: $x = $min->copy();
3404: $x->_make_odd();
3405: }
3406:
3407: $initial_x = $x->copy();
3408:
3409: while (true) {
3410: if ($timeout !== false && time() - $start > $timeout) {
3411: return false;
3412: }
3413:
3414: if ($x->isPrime()) {
3415: return $x;
3416: }
3417:
3418: $x = $x->add($two);
3419:
3420: if ($x->compare($max) > 0) {
3421: $x = $min->copy();
3422: if ($x->equals($two)) {
3423: return $x;
3424: }
3425: $x->_make_odd();
3426: }
3427:
3428: if ($x->equals($initial_x)) {
3429: return false;
3430: }
3431: }
3432: }
3433:
3434: 3435: 3436: 3437: 3438: 3439: 3440: 3441:
3442: function _make_odd()
3443: {
3444: switch ( MATH_BIGINTEGER_MODE ) {
3445: case MATH_BIGINTEGER_MODE_GMP:
3446: gmp_setbit($this->value, 0);
3447: break;
3448: case MATH_BIGINTEGER_MODE_BCMATH:
3449: if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3450: $this->value = bcadd($this->value, '1');
3451: }
3452: break;
3453: default:
3454: $this->value[0] |= 1;
3455: }
3456: }
3457:
3458: 3459: 3460: 3461: 3462: 3463: 3464: 3465: 3466: 3467: 3468: 3469: 3470: 3471:
3472: function isPrime($t = false)
3473: {
3474: $length = strlen($this->toBytes());
3475:
3476: if (!$t) {
3477:
3478:
3479: if ($length >= 163) { $t = 2; }
3480: else if ($length >= 106) { $t = 3; }
3481: else if ($length >= 81 ) { $t = 4; }
3482: else if ($length >= 68 ) { $t = 5; }
3483: else if ($length >= 56 ) { $t = 6; }
3484: else if ($length >= 50 ) { $t = 7; }
3485: else if ($length >= 43 ) { $t = 8; }
3486: else if ($length >= 37 ) { $t = 9; }
3487: else if ($length >= 31 ) { $t = 12; }
3488: else if ($length >= 25 ) { $t = 15; }
3489: else if ($length >= 18 ) { $t = 18; }
3490: else { $t = 27; }
3491:
3492: }
3493:
3494:
3495:
3496: switch ( MATH_BIGINTEGER_MODE ) {
3497: case MATH_BIGINTEGER_MODE_GMP:
3498: return gmp_prob_prime($this->value, $t) != 0;
3499: case MATH_BIGINTEGER_MODE_BCMATH:
3500: if ($this->value === '2') {
3501: return true;
3502: }
3503: if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3504: return false;
3505: }
3506: break;
3507: default:
3508: if ($this->value == array(2)) {
3509: return true;
3510: }
3511: if (~$this->value[0] & 1) {
3512: return false;
3513: }
3514: }
3515:
3516: static $primes, $zero, $one, $two;
3517:
3518: if (!isset($primes)) {
3519: $primes = array(
3520: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
3521: 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
3522: 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
3523: 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
3524: 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
3525: 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
3526: 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
3527: 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
3528: 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
3529: 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
3530: 953, 967, 971, 977, 983, 991, 997
3531: );
3532:
3533: if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL ) {
3534: for ($i = 0; $i < count($primes); ++$i) {
3535: $primes[$i] = new BigInteger($primes[$i]);
3536: }
3537: }
3538:
3539: $zero = new BigInteger();
3540: $one = new BigInteger(1);
3541: $two = new BigInteger(2);
3542: }
3543:
3544: if ($this->equals($one)) {
3545: return false;
3546: }
3547:
3548:
3549: if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL ) {
3550: foreach ($primes as $prime) {
3551: list(, $r) = $this->divide($prime);
3552: if ($r->equals($zero)) {
3553: return $this->equals($prime);
3554: }
3555: }
3556: } else {
3557: $value = $this->value;
3558: foreach ($primes as $prime) {
3559: list(, $r) = $this->_divide_digit($value, $prime);
3560: if (!$r) {
3561: return count($value) == 1 && $value[0] == $prime;
3562: }
3563: }
3564: }
3565:
3566: $n = $this->copy();
3567: $n_1 = $n->subtract($one);
3568: $n_2 = $n->subtract($two);
3569:
3570: $r = $n_1->copy();
3571: $r_value = $r->value;
3572:
3573: if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
3574: $s = 0;
3575:
3576: while ($r->value[strlen($r->value) - 1] % 2 == 0) {
3577: $r->value = bcdiv($r->value, '2', 0);
3578: ++$s;
3579: }
3580: } else {
3581: for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
3582: $temp = ~$r_value[$i] & 0xFFFFFF;
3583: for ($j = 1; ($temp >> $j) & 1; ++$j);
3584: if ($j != 25) {
3585: break;
3586: }
3587: }
3588: $s = 26 * $i + $j - 1;
3589: $r->_rshift($s);
3590: }
3591:
3592: for ($i = 0; $i < $t; ++$i) {
3593: $a = $this->random($two, $n_2);
3594: $y = $a->modPow($r, $n);
3595:
3596: if (!$y->equals($one) && !$y->equals($n_1)) {
3597: for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
3598: $y = $y->modPow($two, $n);
3599: if ($y->equals($one)) {
3600: return false;
3601: }
3602: }
3603:
3604: if (!$y->equals($n_1)) {
3605: return false;
3606: }
3607: }
3608: }
3609: return true;
3610: }
3611:
3612:
3613:
3614:
3615:
3616:
3617: 3618: 3619: 3620: 3621: 3622: 3623: 3624:
3625: function _lshift($shift)
3626: {
3627: if ( $shift == 0 ) {
3628: return;
3629: }
3630:
3631: $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
3632: $shift %= MATH_BIGINTEGER_BASE;
3633: $shift = 1 << $shift;
3634:
3635: $carry = 0;
3636:
3637: for ($i = 0; $i < count($this->value); ++$i) {
3638: $temp = $this->value[$i] * $shift + $carry;
3639: $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
3640: $this->value[$i] = (int) ($temp - $carry * MATH_BIGINTEGER_BASE_FULL);
3641: }
3642:
3643: if ( $carry ) {
3644: $this->value[] = $carry;
3645: }
3646:
3647: while ($num_digits--) {
3648: array_unshift($this->value, 0);
3649: }
3650: }
3651:
3652: 3653: 3654: 3655: 3656: 3657: 3658: 3659:
3660: function _rshift($shift)
3661: {
3662: if ($shift == 0) {
3663: return;
3664: }
3665:
3666: $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
3667: $shift %= MATH_BIGINTEGER_BASE;
3668: $carry_shift = MATH_BIGINTEGER_BASE - $shift;
3669: $carry_mask = (1 << $shift) - 1;
3670:
3671: if ( $num_digits ) {
3672: $this->value = array_slice($this->value, $num_digits);
3673: }
3674:
3675: $carry = 0;
3676:
3677: for ($i = count($this->value) - 1; $i >= 0; --$i) {
3678: $temp = $this->value[$i] >> $shift | $carry;
3679: $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
3680: $this->value[$i] = $temp;
3681: }
3682:
3683: $this->value = $this->_trim($this->value);
3684: }
3685:
3686: 3687: 3688: 3689: 3690: 3691: 3692: 3693: 3694: 3695:
3696: function _normalize($result)
3697: {
3698: $result->precision = $this->precision;
3699: $result->bitmask = $this->bitmask;
3700:
3701: switch ( MATH_BIGINTEGER_MODE ) {
3702: case MATH_BIGINTEGER_MODE_GMP:
3703: if (!empty($result->bitmask->value)) {
3704: $result->value = gmp_and($result->value, $result->bitmask->value);
3705: }
3706:
3707: return $result;
3708: case MATH_BIGINTEGER_MODE_BCMATH:
3709: if (!empty($result->bitmask->value)) {
3710: $result->value = bcmod($result->value, $result->bitmask->value);
3711: }
3712:
3713: return $result;
3714: }
3715:
3716: $value = &$result->value;
3717:
3718: if ( !count($value) ) {
3719: return $result;
3720: }
3721:
3722: $value = $this->_trim($value);
3723:
3724: if (!empty($result->bitmask->value)) {
3725: $length = min(count($value), count($this->bitmask->value));
3726: $value = array_slice($value, 0, $length);
3727:
3728: for ($i = 0; $i < $length; ++$i) {
3729: $value[$i] = $value[$i] & $this->bitmask->value[$i];
3730: }
3731: }
3732:
3733: return $result;
3734: }
3735:
3736: 3737: 3738: 3739: 3740: 3741: 3742: 3743: 3744:
3745: function _trim($value)
3746: {
3747: for ($i = count($value) - 1; $i >= 0; --$i) {
3748: if ( $value[$i] ) {
3749: break;
3750: }
3751: unset($value[$i]);
3752: }
3753:
3754: return $value;
3755: }
3756:
3757: 3758: 3759: 3760: 3761: 3762: 3763: 3764:
3765: function _array_repeat($input, $multiplier)
3766: {
3767: return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
3768: }
3769:
3770: 3771: 3772: 3773: 3774: 3775: 3776: 3777: 3778: 3779:
3780: function _base256_lshift(&$x, $shift)
3781: {
3782: if ($shift == 0) {
3783: return;
3784: }
3785:
3786: $num_bytes = $shift >> 3;
3787: $shift &= 7;
3788:
3789: $carry = 0;
3790: for ($i = strlen($x) - 1; $i >= 0; --$i) {
3791: $temp = ord($x[$i]) << $shift | $carry;
3792: $x[$i] = chr($temp);
3793: $carry = $temp >> 8;
3794: }
3795: $carry = ($carry != 0) ? chr($carry) : '';
3796: $x = $carry . $x . str_repeat(chr(0), $num_bytes);
3797: }
3798:
3799: 3800: 3801: 3802: 3803: 3804: 3805: 3806: 3807: 3808:
3809: function _base256_rshift(&$x, $shift)
3810: {
3811: if ($shift == 0) {
3812: $x = ltrim($x, chr(0));
3813: return '';
3814: }
3815:
3816: $num_bytes = $shift >> 3;
3817: $shift &= 7;
3818:
3819: $remainder = '';
3820: if ($num_bytes) {
3821: $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
3822: $remainder = substr($x, $start);
3823: $x = substr($x, 0, -$num_bytes);
3824: }
3825:
3826: $carry = 0;
3827: $carry_shift = 8 - $shift;
3828: for ($i = 0; $i < strlen($x); ++$i) {
3829: $temp = (ord($x[$i]) >> $shift) | $carry;
3830: $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
3831: $x[$i] = chr($temp);
3832: }
3833: $x = ltrim($x, chr(0));
3834:
3835: $remainder = chr($carry >> $carry_shift) . $remainder;
3836:
3837: return ltrim($remainder, chr(0));
3838: }
3839:
3840:
3841:
3842:
3843: 3844: 3845: 3846: 3847: 3848: 3849:
3850: function _int2bytes($x)
3851: {
3852: return ltrim(pack('N', $x), chr(0));
3853: }
3854:
3855: 3856: 3857: 3858: 3859: 3860: 3861:
3862: function _bytes2int($x)
3863: {
3864: $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
3865: return $temp['int'];
3866: }
3867:
3868: 3869: 3870: 3871: 3872: 3873: 3874: 3875: 3876: 3877:
3878: function _encodeASN1Length($length)
3879: {
3880: if ($length <= 0x7F) {
3881: return chr($length);
3882: }
3883:
3884: $temp = ltrim(pack('N', $length), chr(0));
3885: return pack('Ca*', 0x80 | strlen($temp), $temp);
3886: }
3887: }
3888: