2 /* vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4: */
\r
5 * Pure-PHP arbitrary precision integer arithmetic library.
\r
7 * Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available,
\r
8 * and an internal implementation, otherwise.
\r
10 * PHP versions 4 and 5
\r
12 * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
\r
13 * {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
\r
15 * Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
\r
16 * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible
\r
17 * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
\r
18 * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
\r
19 * used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
\r
20 * which only supports integers. Although this fact will slow this library down, the fact that such a high
\r
21 * base is being used should more than compensate.
\r
23 * When PHP version 6 is officially released, we'll be able to use 64-bit integers. This should, once again,
\r
24 * allow bitwise operators, and will increase the maximum possible base to 2**31 (or 2**62 for addition /
\r
27 * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie.
\r
28 * (new Math_BigInteger(pow(2, 26)))->value = array(0, 1)
\r
30 * Useful resources are as follows:
\r
32 * - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
\r
33 * - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
\r
34 * - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
\r
36 * Here's an example of how to use this library:
\r
39 * include('Math/BigInteger.php');
\r
41 * $a = new Math_BigInteger(2);
\r
42 * $b = new Math_BigInteger(3);
\r
46 * echo $c->toString(); // outputs 5
\r
50 * LICENSE: Permission is hereby granted, free of charge, to any person obtaining a copy
\r
51 * of this software and associated documentation files (the "Software"), to deal
\r
52 * in the Software without restriction, including without limitation the rights
\r
53 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
\r
54 * copies of the Software, and to permit persons to whom the Software is
\r
55 * furnished to do so, subject to the following conditions:
\r
57 * The above copyright notice and this permission notice shall be included in
\r
58 * all copies or substantial portions of the Software.
\r
60 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
61 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
\r
62 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
\r
63 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
\r
64 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
\r
65 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
\r
69 * @package Math_BigInteger
\r
70 * @author Jim Wigginton <terrafrost@php.net>
\r
71 * @copyright MMVI Jim Wigginton
\r
72 * @license http://www.opensource.org/licenses/mit-license.html MIT License
\r
73 * @link http://pear.php.net/package/Math_BigInteger
\r
77 * Reduction constants
\r
80 * @see Math_BigInteger::_reduce()
\r
83 * @see Math_BigInteger::_montgomery()
\r
84 * @see Math_BigInteger::_prepMontgomery()
\r
86 define('MATH_BIGINTEGER_MONTGOMERY', 0);
\r
88 * @see Math_BigInteger::_barrett()
\r
90 define('MATH_BIGINTEGER_BARRETT', 1);
\r
92 * @see Math_BigInteger::_mod2()
\r
94 define('MATH_BIGINTEGER_POWEROF2', 2);
\r
96 * @see Math_BigInteger::_remainder()
\r
98 define('MATH_BIGINTEGER_CLASSIC', 3);
\r
100 * @see Math_BigInteger::__clone()
\r
102 define('MATH_BIGINTEGER_NONE', 4);
\r
108 * Rather than create a thousands and thousands of new Math_BigInteger objects in repeated function calls to add() and
\r
109 * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
\r
114 * $result[MATH_BIGINTEGER_VALUE] contains the value.
\r
116 define('MATH_BIGINTEGER_VALUE', 0);
\r
118 * $result[MATH_BIGINTEGER_SIGN] contains the sign.
\r
120 define('MATH_BIGINTEGER_SIGN', 1);
\r
125 * @see Math_BigInteger::_montgomery()
\r
126 * @see Math_BigInteger::_barrett()
\r
131 * $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
\r
133 define('MATH_BIGINTEGER_VARIABLE', 0);
\r
135 * $cache[MATH_BIGINTEGER_DATA] contains the cached data.
\r
137 define('MATH_BIGINTEGER_DATA', 1);
\r
144 * @see Math_BigInteger::Math_BigInteger()
\r
147 * To use the pure-PHP implementation
\r
149 define('MATH_BIGINTEGER_MODE_INTERNAL', 1);
\r
151 * To use the BCMath library
\r
153 * (if enabled; otherwise, the internal implementation will be used)
\r
155 define('MATH_BIGINTEGER_MODE_BCMATH', 2);
\r
157 * To use the GMP library
\r
159 * (if present; otherwise, either the BCMath or the internal implementation will be used)
\r
161 define('MATH_BIGINTEGER_MODE_GMP', 3);
\r
167 * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
\r
171 define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 25);
\r
174 * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
\r
177 * @author Jim Wigginton <terrafrost@php.net>
\r
178 * @version 1.0.0RC4
\r
180 * @package Math_BigInteger
\r
182 class Math_BigInteger {
\r
184 * Holds the BigInteger's value.
\r
192 * Holds the BigInteger's magnitude.
\r
197 var $is_negative = false;
\r
200 * Random number generator function
\r
202 * @see setRandomGenerator()
\r
205 var $generator = 'mt_rand';
\r
210 * @see setPrecision()
\r
213 var $precision = -1;
\r
216 * Precision Bitmask
\r
218 * @see setPrecision()
\r
221 var $bitmask = false;
\r
224 * Mode independent value used for serialization.
\r
226 * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
\r
227 * a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value,
\r
228 * however, $this->hex is only calculated when $this->__sleep() is called.
\r
238 * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
\r
240 * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
\r
241 * two's compliment. The sole exception to this is -10, which is treated the same as 10 is.
\r
243 * Here's an example:
\r
246 * include('Math/BigInteger.php');
\r
248 * $a = new Math_BigInteger('0x32', 16); // 50 in base-16
\r
250 * echo $a->toString(); // outputs 50
\r
254 * @param optional $x base-10 number or base-$base number if $base set.
\r
255 * @param optional integer $base
\r
256 * @return Math_BigInteger
\r
259 function Math_BigInteger($x = 0, $base = 10)
\r
261 if ( !defined('MATH_BIGINTEGER_MODE') ) {
\r
263 case extension_loaded('gmp'):
\r
264 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP);
\r
266 case extension_loaded('bcmath'):
\r
267 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH);
\r
270 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL);
\r
274 if (function_exists('openssl_public_encrypt') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
\r
275 define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
\r
278 if (!defined('PHP_INT_SIZE')) {
\r
279 define('PHP_INT_SIZE', 4);
\r
282 if (!defined('MATH_BIGINTEGER_BASE') && MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL) {
\r
283 switch (PHP_INT_SIZE) {
\r
284 case 8: // use 64-bit integers if int size is 8 bytes
\r
285 define('MATH_BIGINTEGER_BASE', 31);
\r
286 define('MATH_BIGINTEGER_BASE_FULL', 0x80000000);
\r
287 define('MATH_BIGINTEGER_MAX_DIGIT', 0x7FFFFFFF);
\r
288 define('MATH_BIGINTEGER_MSB', 0x40000000);
\r
289 // 10**9 is the closest we can get to 2**31 without passing it
\r
290 define('MATH_BIGINTEGER_MAX10', 1000000000);
\r
291 define('MATH_BIGINTEGER_MAX10_LEN', 9);
\r
292 // the largest digit that may be used in addition / subtraction
\r
293 define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 62));
\r
295 //case 4: // use 64-bit floats if int size is 4 bytes
\r
297 define('MATH_BIGINTEGER_BASE', 26);
\r
298 define('MATH_BIGINTEGER_BASE_FULL', 0x4000000);
\r
299 define('MATH_BIGINTEGER_MAX_DIGIT', 0x3FFFFFF);
\r
300 define('MATH_BIGINTEGER_MSB', 0x2000000);
\r
301 // 10**7 is the closest to 2**26 without passing it
\r
302 define('MATH_BIGINTEGER_MAX10', 10000000);
\r
303 define('MATH_BIGINTEGER_MAX10_LEN', 7);
\r
304 // the largest digit that may be used in addition / subtraction
\r
305 // we do pow(2, 52) instead of using 4503599627370496 directly because some
\r
306 // PHP installations will truncate 4503599627370496.
\r
307 define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 52));
\r
311 switch ( MATH_BIGINTEGER_MODE ) {
\r
312 case MATH_BIGINTEGER_MODE_GMP:
\r
313 if (is_resource($x) && get_resource_type($x) == 'GMP integer') {
\r
317 $this->value = gmp_init(0);
\r
319 case MATH_BIGINTEGER_MODE_BCMATH:
\r
320 $this->value = '0';
\r
323 $this->value = array();
\r
326 // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
\r
327 // '0' is the only value like this per http://php.net/empty
\r
328 if (empty($x) && (abs($base) != 256 || $x !== '0')) {
\r
334 if (ord($x[0]) & 0x80) {
\r
336 $this->is_negative = true;
\r
339 switch ( MATH_BIGINTEGER_MODE ) {
\r
340 case MATH_BIGINTEGER_MODE_GMP:
\r
341 $sign = $this->is_negative ? '-' : '';
\r
342 $this->value = gmp_init($sign . '0x' . bin2hex($x));
\r
344 case MATH_BIGINTEGER_MODE_BCMATH:
\r
345 // round $len to the nearest 4 (thanks, DavidMJ!)
\r
346 $len = (strlen($x) + 3) & 0xFFFFFFFC;
\r
348 $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
\r
350 for ($i = 0; $i < $len; $i+= 4) {
\r
351 $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
\r
352 $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
\r
355 if ($this->is_negative) {
\r
356 $this->value = '-' . $this->value;
\r
360 // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
\r
362 while (strlen($x)) {
\r
363 $this->value[] = $this->_bytes2int($this->_base256_rshift($x, MATH_BIGINTEGER_BASE));
\r
367 if ($this->is_negative) {
\r
368 if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
\r
369 $this->is_negative = false;
\r
371 $temp = $this->add(new Math_BigInteger('-1'));
\r
372 $this->value = $temp->value;
\r
377 if ($base > 0 && $x[0] == '-') {
\r
378 $this->is_negative = true;
\r
379 $x = substr($x, 1);
\r
382 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
\r
384 $is_negative = false;
\r
385 if ($base < 0 && hexdec($x[0]) >= 8) {
\r
386 $this->is_negative = $is_negative = true;
\r
387 $x = bin2hex(~pack('H*', $x));
\r
390 switch ( MATH_BIGINTEGER_MODE ) {
\r
391 case MATH_BIGINTEGER_MODE_GMP:
\r
392 $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
\r
393 $this->value = gmp_init($temp);
\r
394 $this->is_negative = false;
\r
396 case MATH_BIGINTEGER_MODE_BCMATH:
\r
397 $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
\r
398 $temp = new Math_BigInteger(pack('H*', $x), 256);
\r
399 $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
\r
400 $this->is_negative = false;
\r
403 $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
\r
404 $temp = new Math_BigInteger(pack('H*', $x), 256);
\r
405 $this->value = $temp->value;
\r
408 if ($is_negative) {
\r
409 $temp = $this->add(new Math_BigInteger('-1'));
\r
410 $this->value = $temp->value;
\r
415 // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
\r
416 // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
\r
417 // [^-0-9].*: find any non-numeric characters and then any characters that follow that
\r
418 $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
\r
420 switch ( MATH_BIGINTEGER_MODE ) {
\r
421 case MATH_BIGINTEGER_MODE_GMP:
\r
422 $this->value = gmp_init($x);
\r
424 case MATH_BIGINTEGER_MODE_BCMATH:
\r
425 // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
\r
426 // results then doing it on '-1' does (modInverse does $x[0])
\r
427 $this->value = $x === '-' ? '0' : (string) $x;
\r
430 $temp = new Math_BigInteger();
\r
432 $multiplier = new Math_BigInteger();
\r
433 $multiplier->value = array(MATH_BIGINTEGER_MAX10);
\r
435 if ($x[0] == '-') {
\r
436 $this->is_negative = true;
\r
437 $x = substr($x, 1);
\r
440 $x = str_pad($x, strlen($x) + ((MATH_BIGINTEGER_MAX10_LEN - 1) * strlen($x)) % MATH_BIGINTEGER_MAX10_LEN, 0, STR_PAD_LEFT);
\r
442 while (strlen($x)) {
\r
443 $temp = $temp->multiply($multiplier);
\r
444 $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr($x, 0, MATH_BIGINTEGER_MAX10_LEN)), 256));
\r
445 $x = substr($x, MATH_BIGINTEGER_MAX10_LEN);
\r
448 $this->value = $temp->value;
\r
451 case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
\r
453 if ($base > 0 && $x[0] == '-') {
\r
454 $this->is_negative = true;
\r
455 $x = substr($x, 1);
\r
458 $x = preg_replace('#^([01]*).*#', '$1', $x);
\r
459 $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
\r
462 while (strlen($x)) {
\r
463 $part = substr($x, 0, 4);
\r
464 $str.= dechex(bindec($part));
\r
465 $x = substr($x, 4);
\r
468 if ($this->is_negative) {
\r
472 $temp = new Math_BigInteger($str, 8 * $base); // ie. either -16 or +16
\r
473 $this->value = $temp->value;
\r
474 $this->is_negative = $temp->is_negative;
\r
478 // base not supported, so we'll let $this == 0
\r
483 * Converts a BigInteger to a byte string (eg. base-256).
\r
485 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
\r
486 * saved as two's compliment.
\r
488 * Here's an example:
\r
491 * include('Math/BigInteger.php');
\r
493 * $a = new Math_BigInteger('65');
\r
495 * echo $a->toBytes(); // outputs chr(65)
\r
499 * @param Boolean $twos_compliment
\r
502 * @internal Converts a base-2**26 number to base-2**8
\r
504 function toBytes($twos_compliment = false)
\r
506 if ($twos_compliment) {
\r
507 $comparison = $this->compare(new Math_BigInteger());
\r
508 if ($comparison == 0) {
\r
509 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
\r
512 $temp = $comparison < 0 ? $this->add(new Math_BigInteger(1)) : $this->copy();
\r
513 $bytes = $temp->toBytes();
\r
515 if (empty($bytes)) { // eg. if the number we're trying to convert is -1
\r
519 if (ord($bytes[0]) & 0x80) {
\r
520 $bytes = chr(0) . $bytes;
\r
523 return $comparison < 0 ? ~$bytes : $bytes;
\r
526 switch ( MATH_BIGINTEGER_MODE ) {
\r
527 case MATH_BIGINTEGER_MODE_GMP:
\r
528 if (gmp_cmp($this->value, gmp_init(0)) == 0) {
\r
529 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
\r
532 $temp = gmp_strval(gmp_abs($this->value), 16);
\r
533 $temp = ( strlen($temp) & 1 ) ? '0' . $temp : $temp;
\r
534 $temp = pack('H*', $temp);
\r
536 return $this->precision > 0 ?
\r
537 substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
\r
538 ltrim($temp, chr(0));
\r
539 case MATH_BIGINTEGER_MODE_BCMATH:
\r
540 if ($this->value === '0') {
\r
541 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
\r
545 $current = $this->value;
\r
547 if ($current[0] == '-') {
\r
548 $current = substr($current, 1);
\r
551 while (bccomp($current, '0', 0) > 0) {
\r
552 $temp = bcmod($current, '16777216');
\r
553 $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
\r
554 $current = bcdiv($current, '16777216', 0);
\r
557 return $this->precision > 0 ?
\r
558 substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
\r
559 ltrim($value, chr(0));
\r
562 if (!count($this->value)) {
\r
563 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
\r
565 $result = $this->_int2bytes($this->value[count($this->value) - 1]);
\r
567 $temp = $this->copy();
\r
569 for ($i = count($temp->value) - 2; $i >= 0; --$i) {
\r
570 $temp->_base256_lshift($result, MATH_BIGINTEGER_BASE);
\r
571 $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
\r
574 return $this->precision > 0 ?
\r
575 str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
\r
580 * Converts a BigInteger to a hex string (eg. base-16)).
\r
582 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
\r
583 * saved as two's compliment.
\r
585 * Here's an example:
\r
588 * include('Math/BigInteger.php');
\r
590 * $a = new Math_BigInteger('65');
\r
592 * echo $a->toHex(); // outputs '41'
\r
596 * @param Boolean $twos_compliment
\r
599 * @internal Converts a base-2**26 number to base-2**8
\r
601 function toHex($twos_compliment = false)
\r
603 return bin2hex($this->toBytes($twos_compliment));
\r
607 * Converts a BigInteger to a bit string (eg. base-2).
\r
609 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
\r
610 * saved as two's compliment.
\r
612 * Here's an example:
\r
615 * include('Math/BigInteger.php');
\r
617 * $a = new Math_BigInteger('65');
\r
619 * echo $a->toBits(); // outputs '1000001'
\r
623 * @param Boolean $twos_compliment
\r
626 * @internal Converts a base-2**26 number to base-2**2
\r
628 function toBits($twos_compliment = false)
\r
630 $hex = $this->toHex($twos_compliment);
\r
632 for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
\r
633 $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits;
\r
635 if ($start) { // hexdec('') == 0
\r
636 $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits;
\r
638 $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
\r
640 if ($twos_compliment && $this->compare(new Math_BigInteger()) > 0 && $this->precision <= 0) {
\r
641 return '0' . $result;
\r
648 * Converts a BigInteger to a base-10 number.
\r
650 * Here's an example:
\r
653 * include('Math/BigInteger.php');
\r
655 * $a = new Math_BigInteger('50');
\r
657 * echo $a->toString(); // outputs 50
\r
663 * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
\r
665 function toString()
\r
667 switch ( MATH_BIGINTEGER_MODE ) {
\r
668 case MATH_BIGINTEGER_MODE_GMP:
\r
669 return gmp_strval($this->value);
\r
670 case MATH_BIGINTEGER_MODE_BCMATH:
\r
671 if ($this->value === '0') {
\r
675 return ltrim($this->value, '0');
\r
678 if (!count($this->value)) {
\r
682 $temp = $this->copy();
\r
683 $temp->is_negative = false;
\r
685 $divisor = new Math_BigInteger();
\r
686 $divisor->value = array(MATH_BIGINTEGER_MAX10);
\r
688 while (count($temp->value)) {
\r
689 list($temp, $mod) = $temp->divide($divisor);
\r
690 $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', MATH_BIGINTEGER_MAX10_LEN, '0', STR_PAD_LEFT) . $result;
\r
692 $result = ltrim($result, '0');
\r
693 if (empty($result)) {
\r
697 if ($this->is_negative) {
\r
698 $result = '-' . $result;
\r
707 * PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee
\r
708 * that all objects are passed by value, when appropriate. More information can be found here:
\r
710 * {@link http://php.net/language.oop5.basic#51624}
\r
714 * @return Math_BigInteger
\r
718 $temp = new Math_BigInteger();
\r
719 $temp->value = $this->value;
\r
720 $temp->is_negative = $this->is_negative;
\r
721 $temp->generator = $this->generator;
\r
722 $temp->precision = $this->precision;
\r
723 $temp->bitmask = $this->bitmask;
\r
728 * __toString() magic method
\r
730 * Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call
\r
734 * @internal Implemented per a suggestion by Techie-Michael - thanks!
\r
736 function __toString()
\r
738 return $this->toString();
\r
742 * __clone() magic method
\r
744 * Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone()
\r
745 * directly in PHP5. You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5
\r
746 * only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and PHP5,
\r
747 * call Math_BigInteger::copy(), instead.
\r
751 * @return Math_BigInteger
\r
755 return $this->copy();
\r
759 * __sleep() magic method
\r
761 * Will be called, automatically, when serialize() is called on a Math_BigInteger object.
\r
768 $this->hex = $this->toHex(true);
\r
769 $vars = array('hex');
\r
770 if ($this->generator != 'mt_rand') {
\r
771 $vars[] = 'generator';
\r
773 if ($this->precision > 0) {
\r
774 $vars[] = 'precision';
\r
781 * __wakeup() magic method
\r
783 * Will be called, automatically, when unserialize() is called on a Math_BigInteger object.
\r
788 function __wakeup()
\r
790 $temp = new Math_BigInteger($this->hex, -16);
\r
791 $this->value = $temp->value;
\r
792 $this->is_negative = $temp->is_negative;
\r
793 $this->setRandomGenerator($this->generator);
\r
794 if ($this->precision > 0) {
\r
795 // recalculate $this->bitmask
\r
796 $this->setPrecision($this->precision);
\r
801 * Adds two BigIntegers.
\r
803 * Here's an example:
\r
806 * include('Math/BigInteger.php');
\r
808 * $a = new Math_BigInteger('10');
\r
809 * $b = new Math_BigInteger('20');
\r
811 * $c = $a->add($b);
\r
813 * echo $c->toString(); // outputs 30
\r
817 * @param Math_BigInteger $y
\r
818 * @return Math_BigInteger
\r
820 * @internal Performs base-2**52 addition
\r
824 switch ( MATH_BIGINTEGER_MODE ) {
\r
825 case MATH_BIGINTEGER_MODE_GMP:
\r
826 $temp = new Math_BigInteger();
\r
827 $temp->value = gmp_add($this->value, $y->value);
\r
829 return $this->_normalize($temp);
\r
830 case MATH_BIGINTEGER_MODE_BCMATH:
\r
831 $temp = new Math_BigInteger();
\r
832 $temp->value = bcadd($this->value, $y->value, 0);
\r
834 return $this->_normalize($temp);
\r
837 $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
\r
839 $result = new Math_BigInteger();
\r
840 $result->value = $temp[MATH_BIGINTEGER_VALUE];
\r
841 $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
\r
843 return $this->_normalize($result);
\r
847 * Performs addition.
\r
849 * @param Array $x_value
\r
850 * @param Boolean $x_negative
\r
851 * @param Array $y_value
\r
852 * @param Boolean $y_negative
\r
856 function _add($x_value, $x_negative, $y_value, $y_negative)
\r
858 $x_size = count($x_value);
\r
859 $y_size = count($y_value);
\r
861 if ($x_size == 0) {
\r
863 MATH_BIGINTEGER_VALUE => $y_value,
\r
864 MATH_BIGINTEGER_SIGN => $y_negative
\r
866 } else if ($y_size == 0) {
\r
868 MATH_BIGINTEGER_VALUE => $x_value,
\r
869 MATH_BIGINTEGER_SIGN => $x_negative
\r
873 // subtract, if appropriate
\r
874 if ( $x_negative != $y_negative ) {
\r
875 if ( $x_value == $y_value ) {
\r
877 MATH_BIGINTEGER_VALUE => array(),
\r
878 MATH_BIGINTEGER_SIGN => false
\r
882 $temp = $this->_subtract($x_value, false, $y_value, false);
\r
883 $temp[MATH_BIGINTEGER_SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
\r
884 $x_negative : $y_negative;
\r
889 if ($x_size < $y_size) {
\r
897 $value[] = 0; // just in case the carry adds an extra digit
\r
900 for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
\r
901 $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] + $y_value[$j] * MATH_BIGINTEGER_BASE_FULL + $y_value[$i] + $carry;
\r
902 $carry = $sum >= MATH_BIGINTEGER_MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
\r
903 $sum = $carry ? $sum - MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
\r
905 $temp = (int) ($sum / MATH_BIGINTEGER_BASE_FULL);
\r
907 $value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
\r
908 $value[$j] = $temp;
\r
911 if ($j == $size) { // ie. if $y_size is odd
\r
912 $sum = $x_value[$i] + $y_value[$i] + $carry;
\r
913 $carry = $sum >= MATH_BIGINTEGER_BASE_FULL;
\r
914 $value[$i] = $carry ? $sum - MATH_BIGINTEGER_BASE_FULL : $sum;
\r
915 ++$i; // ie. let $i = $j since we've just done $value[$i]
\r
919 for (; $value[$i] == MATH_BIGINTEGER_MAX_DIGIT; ++$i) {
\r
926 MATH_BIGINTEGER_VALUE => $this->_trim($value),
\r
927 MATH_BIGINTEGER_SIGN => $x_negative
\r
932 * Subtracts two BigIntegers.
\r
934 * Here's an example:
\r
937 * include('Math/BigInteger.php');
\r
939 * $a = new Math_BigInteger('10');
\r
940 * $b = new Math_BigInteger('20');
\r
942 * $c = $a->subtract($b);
\r
944 * echo $c->toString(); // outputs -10
\r
948 * @param Math_BigInteger $y
\r
949 * @return Math_BigInteger
\r
951 * @internal Performs base-2**52 subtraction
\r
953 function subtract($y)
\r
955 switch ( MATH_BIGINTEGER_MODE ) {
\r
956 case MATH_BIGINTEGER_MODE_GMP:
\r
957 $temp = new Math_BigInteger();
\r
958 $temp->value = gmp_sub($this->value, $y->value);
\r
960 return $this->_normalize($temp);
\r
961 case MATH_BIGINTEGER_MODE_BCMATH:
\r
962 $temp = new Math_BigInteger();
\r
963 $temp->value = bcsub($this->value, $y->value, 0);
\r
965 return $this->_normalize($temp);
\r
968 $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
\r
970 $result = new Math_BigInteger();
\r
971 $result->value = $temp[MATH_BIGINTEGER_VALUE];
\r
972 $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
\r
974 return $this->_normalize($result);
\r
978 * Performs subtraction.
\r
980 * @param Array $x_value
\r
981 * @param Boolean $x_negative
\r
982 * @param Array $y_value
\r
983 * @param Boolean $y_negative
\r
987 function _subtract($x_value, $x_negative, $y_value, $y_negative)
\r
989 $x_size = count($x_value);
\r
990 $y_size = count($y_value);
\r
992 if ($x_size == 0) {
\r
994 MATH_BIGINTEGER_VALUE => $y_value,
\r
995 MATH_BIGINTEGER_SIGN => !$y_negative
\r
997 } else if ($y_size == 0) {
\r
999 MATH_BIGINTEGER_VALUE => $x_value,
\r
1000 MATH_BIGINTEGER_SIGN => $x_negative
\r
1004 // add, if appropriate (ie. -$x - +$y or +$x - -$y)
\r
1005 if ( $x_negative != $y_negative ) {
\r
1006 $temp = $this->_add($x_value, false, $y_value, false);
\r
1007 $temp[MATH_BIGINTEGER_SIGN] = $x_negative;
\r
1012 $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
\r
1016 MATH_BIGINTEGER_VALUE => array(),
\r
1017 MATH_BIGINTEGER_SIGN => false
\r
1021 // switch $x and $y around, if appropriate.
\r
1022 if ( (!$x_negative && $diff < 0) || ($x_negative && $diff > 0) ) {
\r
1024 $x_value = $y_value;
\r
1027 $x_negative = !$x_negative;
\r
1029 $x_size = count($x_value);
\r
1030 $y_size = count($y_value);
\r
1033 // at this point, $x_value should be at least as big as - if not bigger than - $y_value
\r
1036 for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
\r
1037 $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] - $y_value[$j] * MATH_BIGINTEGER_BASE_FULL - $y_value[$i] - $carry;
\r
1038 $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
\r
1039 $sum = $carry ? $sum + MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
\r
1041 $temp = (int) ($sum / MATH_BIGINTEGER_BASE_FULL);
\r
1043 $x_value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp);
\r
1044 $x_value[$j] = $temp;
\r
1047 if ($j == $y_size) { // ie. if $y_size is odd
\r
1048 $sum = $x_value[$i] - $y_value[$i] - $carry;
\r
1049 $carry = $sum < 0;
\r
1050 $x_value[$i] = $carry ? $sum + MATH_BIGINTEGER_BASE_FULL : $sum;
\r
1055 for (; !$x_value[$i]; ++$i) {
\r
1056 $x_value[$i] = MATH_BIGINTEGER_MAX_DIGIT;
\r
1062 MATH_BIGINTEGER_VALUE => $this->_trim($x_value),
\r
1063 MATH_BIGINTEGER_SIGN => $x_negative
\r
1068 * Multiplies two BigIntegers
\r
1070 * Here's an example:
\r
1073 * include('Math/BigInteger.php');
\r
1075 * $a = new Math_BigInteger('10');
\r
1076 * $b = new Math_BigInteger('20');
\r
1078 * $c = $a->multiply($b);
\r
1080 * echo $c->toString(); // outputs 200
\r
1084 * @param Math_BigInteger $x
\r
1085 * @return Math_BigInteger
\r
1088 function multiply($x)
\r
1090 switch ( MATH_BIGINTEGER_MODE ) {
\r
1091 case MATH_BIGINTEGER_MODE_GMP:
\r
1092 $temp = new Math_BigInteger();
\r
1093 $temp->value = gmp_mul($this->value, $x->value);
\r
1095 return $this->_normalize($temp);
\r
1096 case MATH_BIGINTEGER_MODE_BCMATH:
\r
1097 $temp = new Math_BigInteger();
\r
1098 $temp->value = bcmul($this->value, $x->value, 0);
\r
1100 return $this->_normalize($temp);
\r
1103 $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
\r
1105 $product = new Math_BigInteger();
\r
1106 $product->value = $temp[MATH_BIGINTEGER_VALUE];
\r
1107 $product->is_negative = $temp[MATH_BIGINTEGER_SIGN];
\r
1109 return $this->_normalize($product);
\r
1113 * Performs multiplication.
\r
1115 * @param Array $x_value
\r
1116 * @param Boolean $x_negative
\r
1117 * @param Array $y_value
\r
1118 * @param Boolean $y_negative
\r
1122 function _multiply($x_value, $x_negative, $y_value, $y_negative)
\r
1124 //if ( $x_value == $y_value ) {
\r
1126 // MATH_BIGINTEGER_VALUE => $this->_square($x_value),
\r
1127 // MATH_BIGINTEGER_SIGN => $x_sign != $y_value
\r
1131 $x_length = count($x_value);
\r
1132 $y_length = count($y_value);
\r
1134 if ( !$x_length || !$y_length ) { // a 0 is being multiplied
\r
1136 MATH_BIGINTEGER_VALUE => array(),
\r
1137 MATH_BIGINTEGER_SIGN => false
\r
1142 MATH_BIGINTEGER_VALUE => min($x_length, $y_length) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
\r
1143 $this->_trim($this->_regularMultiply($x_value, $y_value)) :
\r
1144 $this->_trim($this->_karatsuba($x_value, $y_value)),
\r
1145 MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
\r
1150 * Performs long multiplication on two BigIntegers
\r
1152 * Modeled after 'multiply' in MutableBigInteger.java.
\r
1154 * @param Array $x_value
\r
1155 * @param Array $y_value
\r
1159 function _regularMultiply($x_value, $y_value)
\r
1161 $x_length = count($x_value);
\r
1162 $y_length = count($y_value);
\r
1164 if ( !$x_length || !$y_length ) { // a 0 is being multiplied
\r
1168 if ( $x_length < $y_length ) {
\r
1170 $x_value = $y_value;
\r
1173 $x_length = count($x_value);
\r
1174 $y_length = count($y_value);
\r
1177 $product_value = $this->_array_repeat(0, $x_length + $y_length);
\r
1179 // the following for loop could be removed if the for loop following it
\r
1180 // (the one with nested for loops) initially set $i to 0, but
\r
1181 // doing so would also make the result in one set of unnecessary adds,
\r
1182 // since on the outermost loops first pass, $product->value[$k] is going
\r
1187 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
\r
1188 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
\r
1189 $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
\r
1190 $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
\r
1193 $product_value[$j] = $carry;
\r
1195 // the above for loop is what the previous comment was talking about. the
\r
1196 // following for loop is the "one with nested for loops"
\r
1197 for ($i = 1; $i < $y_length; ++$i) {
\r
1200 for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
\r
1201 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
\r
1202 $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
\r
1203 $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
\r
1206 $product_value[$k] = $carry;
\r
1209 return $product_value;
\r
1213 * Performs Karatsuba multiplication on two BigIntegers
\r
1215 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
\r
1216 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
\r
1218 * @param Array $x_value
\r
1219 * @param Array $y_value
\r
1223 function _karatsuba($x_value, $y_value)
\r
1225 $m = min(count($x_value) >> 1, count($y_value) >> 1);
\r
1227 if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
\r
1228 return $this->_regularMultiply($x_value, $y_value);
\r
1231 $x1 = array_slice($x_value, $m);
\r
1232 $x0 = array_slice($x_value, 0, $m);
\r
1233 $y1 = array_slice($y_value, $m);
\r
1234 $y0 = array_slice($y_value, 0, $m);
\r
1236 $z2 = $this->_karatsuba($x1, $y1);
\r
1237 $z0 = $this->_karatsuba($x0, $y0);
\r
1239 $z1 = $this->_add($x1, false, $x0, false);
\r
1240 $temp = $this->_add($y1, false, $y0, false);
\r
1241 $z1 = $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_VALUE]);
\r
1242 $temp = $this->_add($z2, false, $z0, false);
\r
1243 $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
\r
1245 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
\r
1246 $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
\r
1248 $xy = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
\r
1249 $xy = $this->_add($xy[MATH_BIGINTEGER_VALUE], $xy[MATH_BIGINTEGER_SIGN], $z0, false);
\r
1251 return $xy[MATH_BIGINTEGER_VALUE];
\r
1255 * Performs squaring
\r
1261 function _square($x = false)
\r
1263 return count($x) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ?
\r
1264 $this->_trim($this->_baseSquare($x)) :
\r
1265 $this->_trim($this->_karatsubaSquare($x));
\r
1269 * Performs traditional squaring on two BigIntegers
\r
1271 * Squaring can be done faster than multiplying a number by itself can be. See
\r
1272 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
\r
1273 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
\r
1275 * @param Array $value
\r
1279 function _baseSquare($value)
\r
1281 if ( empty($value) ) {
\r
1284 $square_value = $this->_array_repeat(0, 2 * count($value));
\r
1286 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
\r
1289 $temp = $square_value[$i2] + $value[$i] * $value[$i];
\r
1290 $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
\r
1291 $square_value[$i2] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
\r
1293 // note how we start from $i+1 instead of 0 as we do in multiplication.
\r
1294 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
\r
1295 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
\r
1296 $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
\r
1297 $square_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
\r
1300 // the following line can yield values larger 2**15. at this point, PHP should switch
\r
1301 // over to floats.
\r
1302 $square_value[$i + $max_index + 1] = $carry;
\r
1305 return $square_value;
\r
1309 * Performs Karatsuba "squaring" on two BigIntegers
\r
1311 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
\r
1312 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
\r
1314 * @param Array $value
\r
1318 function _karatsubaSquare($value)
\r
1320 $m = count($value) >> 1;
\r
1322 if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
\r
1323 return $this->_baseSquare($value);
\r
1326 $x1 = array_slice($value, $m);
\r
1327 $x0 = array_slice($value, 0, $m);
\r
1329 $z2 = $this->_karatsubaSquare($x1);
\r
1330 $z0 = $this->_karatsubaSquare($x0);
\r
1332 $z1 = $this->_add($x1, false, $x0, false);
\r
1333 $z1 = $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE]);
\r
1334 $temp = $this->_add($z2, false, $z0, false);
\r
1335 $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
\r
1337 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
\r
1338 $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
\r
1340 $xx = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
\r
1341 $xx = $this->_add($xx[MATH_BIGINTEGER_VALUE], $xx[MATH_BIGINTEGER_SIGN], $z0, false);
\r
1343 return $xx[MATH_BIGINTEGER_VALUE];
\r
1347 * Divides two BigIntegers.
\r
1349 * Returns an array whose first element contains the quotient and whose second element contains the
\r
1350 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the
\r
1351 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder
\r
1352 * and the divisor (basically, the "common residue" is the first positive modulo).
\r
1354 * Here's an example:
\r
1357 * include('Math/BigInteger.php');
\r
1359 * $a = new Math_BigInteger('10');
\r
1360 * $b = new Math_BigInteger('20');
\r
1362 * list($quotient, $remainder) = $a->divide($b);
\r
1364 * echo $quotient->toString(); // outputs 0
\r
1366 * echo $remainder->toString(); // outputs 10
\r
1370 * @param Math_BigInteger $y
\r
1373 * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
\r
1375 function divide($y)
\r
1377 switch ( MATH_BIGINTEGER_MODE ) {
\r
1378 case MATH_BIGINTEGER_MODE_GMP:
\r
1379 $quotient = new Math_BigInteger();
\r
1380 $remainder = new Math_BigInteger();
\r
1382 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
\r
1384 if (gmp_sign($remainder->value) < 0) {
\r
1385 $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
\r
1388 return array($this->_normalize($quotient), $this->_normalize($remainder));
\r
1389 case MATH_BIGINTEGER_MODE_BCMATH:
\r
1390 $quotient = new Math_BigInteger();
\r
1391 $remainder = new Math_BigInteger();
\r
1393 $quotient->value = bcdiv($this->value, $y->value, 0);
\r
1394 $remainder->value = bcmod($this->value, $y->value);
\r
1396 if ($remainder->value[0] == '-') {
\r
1397 $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
\r
1400 return array($this->_normalize($quotient), $this->_normalize($remainder));
\r
1403 if (count($y->value) == 1) {
\r
1404 list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
\r
1405 $quotient = new Math_BigInteger();
\r
1406 $remainder = new Math_BigInteger();
\r
1407 $quotient->value = $q;
\r
1408 $remainder->value = array($r);
\r
1409 $quotient->is_negative = $this->is_negative != $y->is_negative;
\r
1410 return array($this->_normalize($quotient), $this->_normalize($remainder));
\r
1414 if ( !isset($zero) ) {
\r
1415 $zero = new Math_BigInteger();
\r
1418 $x = $this->copy();
\r
1421 $x_sign = $x->is_negative;
\r
1422 $y_sign = $y->is_negative;
\r
1424 $x->is_negative = $y->is_negative = false;
\r
1426 $diff = $x->compare($y);
\r
1429 $temp = new Math_BigInteger();
\r
1430 $temp->value = array(1);
\r
1431 $temp->is_negative = $x_sign != $y_sign;
\r
1432 return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger()));
\r
1435 if ( $diff < 0 ) {
\r
1436 // if $x is negative, "add" $y.
\r
1438 $x = $y->subtract($x);
\r
1440 return array($this->_normalize(new Math_BigInteger()), $this->_normalize($x));
\r
1443 // normalize $x and $y as described in HAC 14.23 / 14.24
\r
1444 $msb = $y->value[count($y->value) - 1];
\r
1445 for ($shift = 0; !($msb & MATH_BIGINTEGER_MSB); ++$shift) {
\r
1448 $x->_lshift($shift);
\r
1449 $y->_lshift($shift);
\r
1450 $y_value = &$y->value;
\r
1452 $x_max = count($x->value) - 1;
\r
1453 $y_max = count($y->value) - 1;
\r
1455 $quotient = new Math_BigInteger();
\r
1456 $quotient_value = &$quotient->value;
\r
1457 $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
\r
1459 static $temp, $lhs, $rhs;
\r
1460 if (!isset($temp)) {
\r
1461 $temp = new Math_BigInteger();
\r
1462 $lhs = new Math_BigInteger();
\r
1463 $rhs = new Math_BigInteger();
\r
1465 $temp_value = &$temp->value;
\r
1466 $rhs_value = &$rhs->value;
\r
1468 // $temp = $y << ($x_max - $y_max-1) in base 2**26
\r
1469 $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
\r
1471 while ( $x->compare($temp) >= 0 ) {
\r
1472 // calculate the "common residue"
\r
1473 ++$quotient_value[$x_max - $y_max];
\r
1474 $x = $x->subtract($temp);
\r
1475 $x_max = count($x->value) - 1;
\r
1478 for ($i = $x_max; $i >= $y_max + 1; --$i) {
\r
1479 $x_value = &$x->value;
\r
1480 $x_window = array(
\r
1481 isset($x_value[$i]) ? $x_value[$i] : 0,
\r
1482 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
\r
1483 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
\r
1485 $y_window = array(
\r
1487 ( $y_max > 0 ) ? $y_value[$y_max - 1] : 0
\r
1490 $q_index = $i - $y_max - 1;
\r
1491 if ($x_window[0] == $y_window[0]) {
\r
1492 $quotient_value[$q_index] = MATH_BIGINTEGER_MAX_DIGIT;
\r
1494 $quotient_value[$q_index] = (int) (
\r
1495 ($x_window[0] * MATH_BIGINTEGER_BASE_FULL + $x_window[1])
\r
1501 $temp_value = array($y_window[1], $y_window[0]);
\r
1503 $lhs->value = array($quotient_value[$q_index]);
\r
1504 $lhs = $lhs->multiply($temp);
\r
1506 $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
\r
1508 while ( $lhs->compare($rhs) > 0 ) {
\r
1509 --$quotient_value[$q_index];
\r
1511 $lhs->value = array($quotient_value[$q_index]);
\r
1512 $lhs = $lhs->multiply($temp);
\r
1515 $adjust = $this->_array_repeat(0, $q_index);
\r
1516 $temp_value = array($quotient_value[$q_index]);
\r
1517 $temp = $temp->multiply($y);
\r
1518 $temp_value = &$temp->value;
\r
1519 $temp_value = array_merge($adjust, $temp_value);
\r
1521 $x = $x->subtract($temp);
\r
1523 if ($x->compare($zero) < 0) {
\r
1524 $temp_value = array_merge($adjust, $y_value);
\r
1525 $x = $x->add($temp);
\r
1527 --$quotient_value[$q_index];
\r
1530 $x_max = count($x_value) - 1;
\r
1533 // unnormalize the remainder
\r
1534 $x->_rshift($shift);
\r
1536 $quotient->is_negative = $x_sign != $y_sign;
\r
1538 // calculate the "common residue", if appropriate
\r
1540 $y->_rshift($shift);
\r
1541 $x = $y->subtract($x);
\r
1544 return array($this->_normalize($quotient), $this->_normalize($x));
\r
1548 * Divides a BigInteger by a regular integer
\r
1550 * abc / x = a00 / x + b0 / x + c / x
\r
1552 * @param Array $dividend
\r
1553 * @param Array $divisor
\r
1557 function _divide_digit($dividend, $divisor)
\r
1560 $result = array();
\r
1562 for ($i = count($dividend) - 1; $i >= 0; --$i) {
\r
1563 $temp = MATH_BIGINTEGER_BASE_FULL * $carry + $dividend[$i];
\r
1564 $result[$i] = (int) ($temp / $divisor);
\r
1565 $carry = (int) ($temp - $divisor * $result[$i]);
\r
1568 return array($result, $carry);
\r
1572 * Performs modular exponentiation.
\r
1574 * Here's an example:
\r
1577 * include('Math/BigInteger.php');
\r
1579 * $a = new Math_BigInteger('10');
\r
1580 * $b = new Math_BigInteger('20');
\r
1581 * $c = new Math_BigInteger('30');
\r
1583 * $c = $a->modPow($b, $c);
\r
1585 * echo $c->toString(); // outputs 10
\r
1589 * @param Math_BigInteger $e
\r
1590 * @param Math_BigInteger $n
\r
1591 * @return Math_BigInteger
\r
1593 * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
\r
1594 * and although the approach involving repeated squaring does vastly better, it, too, is impractical
\r
1595 * for our purposes. The reason being that division - by far the most complicated and time-consuming
\r
1596 * of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
\r
1598 * Modular reductions resolve this issue. Although an individual modular reduction takes more time
\r
1599 * then an individual division, when performed in succession (with the same modulo), they're a lot faster.
\r
1601 * The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction,
\r
1602 * although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the
\r
1603 * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
\r
1604 * the product of two odd numbers is odd), but what about when RSA isn't used?
\r
1606 * In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a
\r
1607 * Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the
\r
1608 * modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however,
\r
1609 * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
\r
1610 * the other, a power of two - and recombine them, later. This is the method that this modPow function uses.
\r
1611 * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
\r
1613 function modPow($e, $n)
\r
1615 $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
\r
1617 if ($e->compare(new Math_BigInteger()) < 0) {
\r
1620 $temp = $this->modInverse($n);
\r
1621 if ($temp === false) {
\r
1625 return $this->_normalize($temp->modPow($e, $n));
\r
1628 if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP ) {
\r
1629 $temp = new Math_BigInteger();
\r
1630 $temp->value = gmp_powm($this->value, $e->value, $n->value);
\r
1632 return $this->_normalize($temp);
\r
1635 if ($this->compare(new Math_BigInteger()) < 0 || $this->compare($n) > 0) {
\r
1636 list(, $temp) = $this->divide($n);
\r
1637 return $temp->modPow($e, $n);
\r
1640 if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
\r
1641 $components = array(
\r
1642 'modulus' => $n->toBytes(true),
\r
1643 'publicExponent' => $e->toBytes(true)
\r
1646 $components = array(
\r
1647 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
\r
1648 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
\r
1651 $RSAPublicKey = pack('Ca*a*a*',
\r
1652 48, $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
\r
1653 $components['modulus'], $components['publicExponent']
\r
1656 $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
\r
1657 $RSAPublicKey = chr(0) . $RSAPublicKey;
\r
1658 $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
\r
1660 $encapsulated = pack('Ca*a*',
\r
1661 48, $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)), $rsaOID . $RSAPublicKey
\r
1664 $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
\r
1665 chunk_split(base64_encode($encapsulated)) .
\r
1666 '-----END PUBLIC KEY-----';
\r
1668 $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
\r
1670 if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
\r
1671 return new Math_BigInteger($result, 256);
\r
1675 if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
\r
1676 $temp = new Math_BigInteger();
\r
1677 $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
\r
1679 return $this->_normalize($temp);
\r
1682 if ( empty($e->value) ) {
\r
1683 $temp = new Math_BigInteger();
\r
1684 $temp->value = array(1);
\r
1685 return $this->_normalize($temp);
\r
1688 if ( $e->value == array(1) ) {
\r
1689 list(, $temp) = $this->divide($n);
\r
1690 return $this->_normalize($temp);
\r
1693 if ( $e->value == array(2) ) {
\r
1694 $temp = new Math_BigInteger();
\r
1695 $temp->value = $this->_square($this->value);
\r
1696 list(, $temp) = $temp->divide($n);
\r
1697 return $this->_normalize($temp);
\r
1700 return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT));
\r
1702 // is the modulo odd?
\r
1703 if ( $n->value[0] & 1 ) {
\r
1704 return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY));
\r
1706 // if it's not, it's even
\r
1708 // find the lowest set bit (eg. the max pow of 2 that divides $n)
\r
1709 for ($i = 0; $i < count($n->value); ++$i) {
\r
1710 if ( $n->value[$i] ) {
\r
1711 $temp = decbin($n->value[$i]);
\r
1712 $j = strlen($temp) - strrpos($temp, '1') - 1;
\r
1717 // at this point, 2^$j * $n/(2^$j) == $n
\r
1719 $mod1 = $n->copy();
\r
1720 $mod1->_rshift($j);
\r
1721 $mod2 = new Math_BigInteger();
\r
1722 $mod2->value = array(1);
\r
1723 $mod2->_lshift($j);
\r
1725 $part1 = ( $mod1->value != array(1) ) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger();
\r
1726 $part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2);
\r
1728 $y1 = $mod2->modInverse($mod1);
\r
1729 $y2 = $mod1->modInverse($mod2);
\r
1731 $result = $part1->multiply($mod2);
\r
1732 $result = $result->multiply($y1);
\r
1734 $temp = $part2->multiply($mod1);
\r
1735 $temp = $temp->multiply($y2);
\r
1737 $result = $result->add($temp);
\r
1738 list(, $result) = $result->divide($n);
\r
1740 return $this->_normalize($result);
\r
1744 * Performs modular exponentiation.
\r
1746 * Alias for Math_BigInteger::modPow()
\r
1748 * @param Math_BigInteger $e
\r
1749 * @param Math_BigInteger $n
\r
1750 * @return Math_BigInteger
\r
1753 function powMod($e, $n)
\r
1755 return $this->modPow($e, $n);
\r
1759 * Sliding Window k-ary Modular Exponentiation
\r
1761 * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
\r
1762 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims,
\r
1763 * however, this function performs a modular reduction after every multiplication and squaring operation.
\r
1764 * As such, this function has the same preconditions that the reductions being used do.
\r
1766 * @param Math_BigInteger $e
\r
1767 * @param Math_BigInteger $n
\r
1768 * @param Integer $mode
\r
1769 * @return Math_BigInteger
\r
1772 function _slidingWindow($e, $n, $mode)
\r
1774 static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
\r
1775 //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
\r
1777 $e_value = $e->value;
\r
1778 $e_length = count($e_value) - 1;
\r
1779 $e_bits = decbin($e_value[$e_length]);
\r
1780 for ($i = $e_length - 1; $i >= 0; --$i) {
\r
1781 $e_bits.= str_pad(decbin($e_value[$i]), MATH_BIGINTEGER_BASE, '0', STR_PAD_LEFT);
\r
1784 $e_length = strlen($e_bits);
\r
1786 // calculate the appropriate window size.
\r
1787 // $window_size == 3 if $window_ranges is between 25 and 81, for example.
\r
1788 for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); ++$window_size, ++$i);
\r
1790 $n_value = $n->value;
\r
1792 // precompute $this^0 through $this^$window_size
\r
1793 $powers = array();
\r
1794 $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
\r
1795 $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
\r
1797 // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
\r
1798 // in a 1. ie. it's supposed to be odd.
\r
1799 $temp = 1 << ($window_size - 1);
\r
1800 for ($i = 1; $i < $temp; ++$i) {
\r
1802 $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
\r
1805 $result = array(1);
\r
1806 $result = $this->_prepareReduce($result, $n_value, $mode);
\r
1808 for ($i = 0; $i < $e_length; ) {
\r
1809 if ( !$e_bits[$i] ) {
\r
1810 $result = $this->_squareReduce($result, $n_value, $mode);
\r
1813 for ($j = $window_size - 1; $j > 0; --$j) {
\r
1814 if ( !empty($e_bits[$i + $j]) ) {
\r
1819 for ($k = 0; $k <= $j; ++$k) {// eg. the length of substr($e_bits, $i, $j+1)
\r
1820 $result = $this->_squareReduce($result, $n_value, $mode);
\r
1823 $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
\r
1829 $temp = new Math_BigInteger();
\r
1830 $temp->value = $this->_reduce($result, $n_value, $mode);
\r
1836 * Modular reduction
\r
1838 * For most $modes this will return the remainder.
\r
1840 * @see _slidingWindow()
\r
1844 * @param Integer $mode
\r
1847 function _reduce($x, $n, $mode)
\r
1850 case MATH_BIGINTEGER_MONTGOMERY:
\r
1851 return $this->_montgomery($x, $n);
\r
1852 case MATH_BIGINTEGER_BARRETT:
\r
1853 return $this->_barrett($x, $n);
\r
1854 case MATH_BIGINTEGER_POWEROF2:
\r
1855 $lhs = new Math_BigInteger();
\r
1857 $rhs = new Math_BigInteger();
\r
1859 return $x->_mod2($n);
\r
1860 case MATH_BIGINTEGER_CLASSIC:
\r
1861 $lhs = new Math_BigInteger();
\r
1863 $rhs = new Math_BigInteger();
\r
1865 list(, $temp) = $lhs->divide($rhs);
\r
1866 return $temp->value;
\r
1867 case MATH_BIGINTEGER_NONE:
\r
1870 // an invalid $mode was provided
\r
1875 * Modular reduction preperation
\r
1877 * @see _slidingWindow()
\r
1881 * @param Integer $mode
\r
1884 function _prepareReduce($x, $n, $mode)
\r
1886 if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
\r
1887 return $this->_prepMontgomery($x, $n);
\r
1889 return $this->_reduce($x, $n, $mode);
\r
1893 * Modular multiply
\r
1895 * @see _slidingWindow()
\r
1900 * @param Integer $mode
\r
1903 function _multiplyReduce($x, $y, $n, $mode)
\r
1905 if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
\r
1906 return $this->_montgomeryMultiply($x, $y, $n);
\r
1908 $temp = $this->_multiply($x, false, $y, false);
\r
1909 return $this->_reduce($temp[MATH_BIGINTEGER_VALUE], $n, $mode);
\r
1915 * @see _slidingWindow()
\r
1919 * @param Integer $mode
\r
1922 function _squareReduce($x, $n, $mode)
\r
1924 if ($mode == MATH_BIGINTEGER_MONTGOMERY) {
\r
1925 return $this->_montgomeryMultiply($x, $x, $n);
\r
1927 return $this->_reduce($this->_square($x), $n, $mode);
\r
1931 * Modulos for Powers of Two
\r
1933 * Calculates $x%$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1),
\r
1934 * we'll just use this function as a wrapper for doing that.
\r
1936 * @see _slidingWindow()
\r
1938 * @param Math_BigInteger
\r
1939 * @return Math_BigInteger
\r
1941 function _mod2($n)
\r
1943 $temp = new Math_BigInteger();
\r
1944 $temp->value = array(1);
\r
1945 return $this->bitwise_and($n->subtract($temp));
\r
1949 * Barrett Modular Reduction
\r
1951 * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
\r
1952 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly,
\r
1953 * so as not to require negative numbers (initially, this script didn't support negative numbers).
\r
1955 * Employs "folding", as described at
\r
1956 * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from
\r
1957 * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."
\r
1959 * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
\r
1960 * usable on account of (1) its not using reasonable radix points as discussed in
\r
1961 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
\r
1962 * radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that
\r
1963 * (x >> 1) + (x >> 1) != x / 2 + x / 2. If x is even, they're the same, but if x is odd, they're not. See the in-line
\r
1964 * comments for details.
\r
1966 * @see _slidingWindow()
\r
1972 function _barrett($n, $m)
\r
1974 static $cache = array(
\r
1975 MATH_BIGINTEGER_VARIABLE => array(),
\r
1976 MATH_BIGINTEGER_DATA => array()
\r
1979 $m_length = count($m);
\r
1981 // if ($this->_compare($n, $this->_square($m)) >= 0) {
\r
1982 if (count($n) > 2 * $m_length) {
\r
1983 $lhs = new Math_BigInteger();
\r
1984 $rhs = new Math_BigInteger();
\r
1987 list(, $temp) = $lhs->divide($rhs);
\r
1988 return $temp->value;
\r
1991 // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
\r
1992 if ($m_length < 5) {
\r
1993 return $this->_regularBarrett($n, $m);
\r
1996 // n = 2 * m.length
\r
1998 if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
\r
1999 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
\r
2000 $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
\r
2002 $lhs = new Math_BigInteger();
\r
2003 $lhs_value = &$lhs->value;
\r
2004 $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
\r
2006 $rhs = new Math_BigInteger();
\r
2009 list($u, $m1) = $lhs->divide($rhs);
\r
2013 $cache[MATH_BIGINTEGER_DATA][] = array(
\r
2014 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
\r
2015 'm1'=> $m1 // m.length
\r
2018 extract($cache[MATH_BIGINTEGER_DATA][$key]);
\r
2021 $cutoff = $m_length + ($m_length >> 1);
\r
2022 $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
\r
2023 $msd = array_slice($n, $cutoff); // m.length >> 1
\r
2024 $lsd = $this->_trim($lsd);
\r
2025 $temp = $this->_multiply($msd, false, $m1, false);
\r
2026 $n = $this->_add($lsd, false, $temp[MATH_BIGINTEGER_VALUE], false); // m.length + (m.length >> 1) + 1
\r
2028 if ($m_length & 1) {
\r
2029 return $this->_regularBarrett($n[MATH_BIGINTEGER_VALUE], $m);
\r
2032 // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
\r
2033 $temp = array_slice($n[MATH_BIGINTEGER_VALUE], $m_length - 1);
\r
2034 // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
\r
2035 // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
\r
2036 $temp = $this->_multiply($temp, false, $u, false);
\r
2037 // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
\r
2038 // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
\r
2039 $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], ($m_length >> 1) + 1);
\r
2040 // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
\r
2041 // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1)
\r
2042 $temp = $this->_multiply($temp, false, $m, false);
\r
2044 // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
\r
2045 // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop
\r
2046 // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
\r
2048 $result = $this->_subtract($n[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
\r
2050 while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false) >= 0) {
\r
2051 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false);
\r
2054 return $result[MATH_BIGINTEGER_VALUE];
\r
2058 * (Regular) Barrett Modular Reduction
\r
2060 * For numbers with more than four digits Math_BigInteger::_barrett() is faster. The difference between that and this
\r
2061 * is that this function does not fold the denominator into a smaller form.
\r
2063 * @see _slidingWindow()
\r
2069 function _regularBarrett($x, $n)
\r
2071 static $cache = array(
\r
2072 MATH_BIGINTEGER_VARIABLE => array(),
\r
2073 MATH_BIGINTEGER_DATA => array()
\r
2076 $n_length = count($n);
\r
2078 if (count($x) > 2 * $n_length) {
\r
2079 $lhs = new Math_BigInteger();
\r
2080 $rhs = new Math_BigInteger();
\r
2083 list(, $temp) = $lhs->divide($rhs);
\r
2084 return $temp->value;
\r
2087 if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
\r
2088 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
\r
2089 $cache[MATH_BIGINTEGER_VARIABLE][] = $n;
\r
2090 $lhs = new Math_BigInteger();
\r
2091 $lhs_value = &$lhs->value;
\r
2092 $lhs_value = $this->_array_repeat(0, 2 * $n_length);
\r
2094 $rhs = new Math_BigInteger();
\r
2096 list($temp, ) = $lhs->divide($rhs); // m.length
\r
2097 $cache[MATH_BIGINTEGER_DATA][] = $temp->value;
\r
2100 // 2 * m.length - (m.length - 1) = m.length + 1
\r
2101 $temp = array_slice($x, $n_length - 1);
\r
2102 // (m.length + 1) + m.length = 2 * m.length + 1
\r
2103 $temp = $this->_multiply($temp, false, $cache[MATH_BIGINTEGER_DATA][$key], false);
\r
2104 // (2 * m.length + 1) - (m.length - 1) = m.length + 2
\r
2105 $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], $n_length + 1);
\r
2108 $result = array_slice($x, 0, $n_length + 1);
\r
2110 $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
\r
2111 // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
\r
2113 if ($this->_compare($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]) < 0) {
\r
2114 $corrector_value = $this->_array_repeat(0, $n_length + 1);
\r
2115 $corrector_value[] = 1;
\r
2116 $result = $this->_add($result, false, $corrector_value, false);
\r
2117 $result = $result[MATH_BIGINTEGER_VALUE];
\r
2120 // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
\r
2121 $result = $this->_subtract($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]);
\r
2122 while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false) > 0) {
\r
2123 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false);
\r
2126 return $result[MATH_BIGINTEGER_VALUE];
\r
2130 * Performs long multiplication up to $stop digits
\r
2132 * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
\r
2134 * @see _regularBarrett()
\r
2135 * @param Array $x_value
\r
2136 * @param Boolean $x_negative
\r
2137 * @param Array $y_value
\r
2138 * @param Boolean $y_negative
\r
2139 * @param Integer $stop
\r
2143 function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
\r
2145 $x_length = count($x_value);
\r
2146 $y_length = count($y_value);
\r
2148 if ( !$x_length || !$y_length ) { // a 0 is being multiplied
\r
2150 MATH_BIGINTEGER_VALUE => array(),
\r
2151 MATH_BIGINTEGER_SIGN => false
\r
2155 if ( $x_length < $y_length ) {
\r
2157 $x_value = $y_value;
\r
2160 $x_length = count($x_value);
\r
2161 $y_length = count($y_value);
\r
2164 $product_value = $this->_array_repeat(0, $x_length + $y_length);
\r
2166 // the following for loop could be removed if the for loop following it
\r
2167 // (the one with nested for loops) initially set $i to 0, but
\r
2168 // doing so would also make the result in one set of unnecessary adds,
\r
2169 // since on the outermost loops first pass, $product->value[$k] is going
\r
2174 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
\r
2175 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
\r
2176 $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
\r
2177 $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
\r
2181 $product_value[$j] = $carry;
\r
2184 // the above for loop is what the previous comment was talking about. the
\r
2185 // following for loop is the "one with nested for loops"
\r
2187 for ($i = 1; $i < $y_length; ++$i) {
\r
2190 for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
\r
2191 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
\r
2192 $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
\r
2193 $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry);
\r
2197 $product_value[$k] = $carry;
\r
2202 MATH_BIGINTEGER_VALUE => $this->_trim($product_value),
\r
2203 MATH_BIGINTEGER_SIGN => $x_negative != $y_negative
\r
2208 * Montgomery Modular Reduction
\r
2210 * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n.
\r
2211 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be
\r
2212 * improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function
\r
2213 * to work correctly.
\r
2215 * @see _prepMontgomery()
\r
2216 * @see _slidingWindow()
\r
2222 function _montgomery($x, $n)
\r
2224 static $cache = array(
\r
2225 MATH_BIGINTEGER_VARIABLE => array(),
\r
2226 MATH_BIGINTEGER_DATA => array()
\r
2229 if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
\r
2230 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
\r
2231 $cache[MATH_BIGINTEGER_VARIABLE][] = $x;
\r
2232 $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($n);
\r
2237 $result = array(MATH_BIGINTEGER_VALUE => $x);
\r
2239 for ($i = 0; $i < $k; ++$i) {
\r
2240 $temp = $result[MATH_BIGINTEGER_VALUE][$i] * $cache[MATH_BIGINTEGER_DATA][$key];
\r
2241 $temp = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * ((int) ($temp / MATH_BIGINTEGER_BASE_FULL)));
\r
2242 $temp = $this->_regularMultiply(array($temp), $n);
\r
2243 $temp = array_merge($this->_array_repeat(0, $i), $temp);
\r
2244 $result = $this->_add($result[MATH_BIGINTEGER_VALUE], false, $temp, false);
\r
2247 $result[MATH_BIGINTEGER_VALUE] = array_slice($result[MATH_BIGINTEGER_VALUE], $k);
\r
2249 if ($this->_compare($result, false, $n, false) >= 0) {
\r
2250 $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], false, $n, false);
\r
2253 return $result[MATH_BIGINTEGER_VALUE];
\r
2257 * Montgomery Multiply
\r
2259 * Interleaves the montgomery reduction and long multiplication algorithms together as described in
\r
2260 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
\r
2262 * @see _prepMontgomery()
\r
2263 * @see _montgomery()
\r
2270 function _montgomeryMultiply($x, $y, $m)
\r
2272 $temp = $this->_multiply($x, false, $y, false);
\r
2273 return $this->_montgomery($temp[MATH_BIGINTEGER_VALUE], $m);
\r
2275 static $cache = array(
\r
2276 MATH_BIGINTEGER_VARIABLE => array(),
\r
2277 MATH_BIGINTEGER_DATA => array()
\r
2280 if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
\r
2281 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
\r
2282 $cache[MATH_BIGINTEGER_VARIABLE][] = $m;
\r
2283 $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($m);
\r
2286 $n = max(count($x), count($y), count($m));
\r
2287 $x = array_pad($x, $n, 0);
\r
2288 $y = array_pad($y, $n, 0);
\r
2289 $m = array_pad($m, $n, 0);
\r
2290 $a = array(MATH_BIGINTEGER_VALUE => $this->_array_repeat(0, $n + 1));
\r
2291 for ($i = 0; $i < $n; ++$i) {
\r
2292 $temp = $a[MATH_BIGINTEGER_VALUE][0] + $x[$i] * $y[0];
\r
2293 $temp = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * ((int) ($temp / MATH_BIGINTEGER_BASE_FULL)));
\r
2294 $temp = $temp * $cache[MATH_BIGINTEGER_DATA][$key];
\r
2295 $temp = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * ((int) ($temp / MATH_BIGINTEGER_BASE_FULL)));
\r
2296 $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
\r
2297 $a = $this->_add($a[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false);
\r
2298 $a[MATH_BIGINTEGER_VALUE] = array_slice($a[MATH_BIGINTEGER_VALUE], 1);
\r
2300 if ($this->_compare($a[MATH_BIGINTEGER_VALUE], false, $m, false) >= 0) {
\r
2301 $a = $this->_subtract($a[MATH_BIGINTEGER_VALUE], false, $m, false);
\r
2303 return $a[MATH_BIGINTEGER_VALUE];
\r
2307 * Prepare a number for use in Montgomery Modular Reductions
\r
2309 * @see _montgomery()
\r
2310 * @see _slidingWindow()
\r
2316 function _prepMontgomery($x, $n)
\r
2318 $lhs = new Math_BigInteger();
\r
2319 $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
\r
2320 $rhs = new Math_BigInteger();
\r
2323 list(, $temp) = $lhs->divide($rhs);
\r
2324 return $temp->value;
\r
2328 * Modular Inverse of a number mod 2**26 (eg. 67108864)
\r
2330 * Based off of the bnpInvDigit function implemented and justified in the following URL:
\r
2332 * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
\r
2334 * The following URL provides more info:
\r
2336 * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
\r
2338 * As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For
\r
2339 * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
\r
2340 * int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
\r
2341 * auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that
\r
2342 * the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the
\r
2343 * maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to
\r
2344 * 40 bits, which only 64-bit floating points will support.
\r
2346 * Thanks to Pedro Gimeno Fortea for input!
\r
2348 * @see _montgomery()
\r
2353 function _modInverse67108864($x) // 2**26 == 67,108,864
\r
2356 $result = $x & 0x3; // x**-1 mod 2**2
\r
2357 $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
\r
2358 $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8
\r
2359 $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
\r
2360 $result = fmod($result * (2 - fmod($x * $result, MATH_BIGINTEGER_BASE_FULL)), MATH_BIGINTEGER_BASE_FULL); // x**-1 mod 2**26
\r
2361 return $result & MATH_BIGINTEGER_MAX_DIGIT;
\r
2365 * Calculates modular inverses.
\r
2367 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.
\r
2369 * Here's an example:
\r
2372 * include('Math/BigInteger.php');
\r
2374 * $a = new Math_BigInteger(30);
\r
2375 * $b = new Math_BigInteger(17);
\r
2377 * $c = $a->modInverse($b);
\r
2378 * echo $c->toString(); // outputs 4
\r
2382 * $d = $a->multiply($c);
\r
2383 * list(, $d) = $d->divide($b);
\r
2384 * echo $d; // outputs 1 (as per the definition of modular inverse)
\r
2388 * @param Math_BigInteger $n
\r
2389 * @return mixed false, if no modular inverse exists, Math_BigInteger, otherwise.
\r
2391 * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.
\r
2393 function modInverse($n)
\r
2395 switch ( MATH_BIGINTEGER_MODE ) {
\r
2396 case MATH_BIGINTEGER_MODE_GMP:
\r
2397 $temp = new Math_BigInteger();
\r
2398 $temp->value = gmp_invert($this->value, $n->value);
\r
2400 return ( $temp->value === false ) ? false : $this->_normalize($temp);
\r
2403 static $zero, $one;
\r
2404 if (!isset($zero)) {
\r
2405 $zero = new Math_BigInteger();
\r
2406 $one = new Math_BigInteger(1);
\r
2409 // $x mod -$n == $x mod $n.
\r
2412 if ($this->compare($zero) < 0) {
\r
2413 $temp = $this->abs();
\r
2414 $temp = $temp->modInverse($n);
\r
2415 return $this->_normalize($n->subtract($temp));
\r
2418 extract($this->extendedGCD($n));
\r
2420 if (!$gcd->equals($one)) {
\r
2424 $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
\r
2426 return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
\r
2430 * Calculates the greatest common divisor and Bezout's identity.
\r
2432 * Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that
\r
2433 * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which
\r
2434 * combination is returned is dependant upon which mode is in use. See
\r
2435 * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
\r
2437 * Here's an example:
\r
2440 * include('Math/BigInteger.php');
\r
2442 * $a = new Math_BigInteger(693);
\r
2443 * $b = new Math_BigInteger(609);
\r
2445 * extract($a->extendedGCD($b));
\r
2447 * echo $gcd->toString() . "\r\n"; // outputs 21
\r
2448 * echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
\r
2452 * @param Math_BigInteger $n
\r
2453 * @return Math_BigInteger
\r
2455 * @internal Calculates the GCD using the binary xGCD algorithim described in
\r
2456 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}. As the text above 14.61 notes,
\r
2457 * the more traditional algorithim requires "relatively costly multiple-precision divisions".
\r
2459 function extendedGCD($n)
\r
2461 switch ( MATH_BIGINTEGER_MODE ) {
\r
2462 case MATH_BIGINTEGER_MODE_GMP:
\r
2463 extract(gmp_gcdext($this->value, $n->value));
\r
2466 'gcd' => $this->_normalize(new Math_BigInteger($g)),
\r
2467 'x' => $this->_normalize(new Math_BigInteger($s)),
\r
2468 'y' => $this->_normalize(new Math_BigInteger($t))
\r
2470 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2471 // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
\r
2472 // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is,
\r
2473 // the basic extended euclidean algorithim is what we're using.
\r
2475 $u = $this->value;
\r
2483 while (bccomp($v, '0', 0) != 0) {
\r
2484 $q = bcdiv($u, $v, 0);
\r
2488 $v = bcsub($temp, bcmul($v, $q, 0), 0);
\r
2492 $c = bcsub($temp, bcmul($a, $q, 0), 0);
\r
2496 $d = bcsub($temp, bcmul($b, $q, 0), 0);
\r
2500 'gcd' => $this->_normalize(new Math_BigInteger($u)),
\r
2501 'x' => $this->_normalize(new Math_BigInteger($a)),
\r
2502 'y' => $this->_normalize(new Math_BigInteger($b))
\r
2507 $x = $this->copy();
\r
2508 $g = new Math_BigInteger();
\r
2509 $g->value = array(1);
\r
2511 while ( !(($x->value[0] & 1)|| ($y->value[0] & 1)) ) {
\r
2520 $a = new Math_BigInteger();
\r
2521 $b = new Math_BigInteger();
\r
2522 $c = new Math_BigInteger();
\r
2523 $d = new Math_BigInteger();
\r
2525 $a->value = $d->value = $g->value = array(1);
\r
2526 $b->value = $c->value = array();
\r
2528 while ( !empty($u->value) ) {
\r
2529 while ( !($u->value[0] & 1) ) {
\r
2531 if ( (!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1)) ) {
\r
2533 $b = $b->subtract($x);
\r
2539 while ( !($v->value[0] & 1) ) {
\r
2541 if ( (!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1)) ) {
\r
2543 $d = $d->subtract($x);
\r
2549 if ($u->compare($v) >= 0) {
\r
2550 $u = $u->subtract($v);
\r
2551 $a = $a->subtract($c);
\r
2552 $b = $b->subtract($d);
\r
2554 $v = $v->subtract($u);
\r
2555 $c = $c->subtract($a);
\r
2556 $d = $d->subtract($b);
\r
2561 'gcd' => $this->_normalize($g->multiply($v)),
\r
2562 'x' => $this->_normalize($c),
\r
2563 'y' => $this->_normalize($d)
\r
2568 * Calculates the greatest common divisor
\r
2570 * Say you have 693 and 609. The GCD is 21.
\r
2572 * Here's an example:
\r
2575 * include('Math/BigInteger.php');
\r
2577 * $a = new Math_BigInteger(693);
\r
2578 * $b = new Math_BigInteger(609);
\r
2580 * $gcd = a->extendedGCD($b);
\r
2582 * echo $gcd->toString() . "\r\n"; // outputs 21
\r
2586 * @param Math_BigInteger $n
\r
2587 * @return Math_BigInteger
\r
2592 extract($this->extendedGCD($n));
\r
2599 * @return Math_BigInteger
\r
2604 $temp = new Math_BigInteger();
\r
2606 switch ( MATH_BIGINTEGER_MODE ) {
\r
2607 case MATH_BIGINTEGER_MODE_GMP:
\r
2608 $temp->value = gmp_abs($this->value);
\r
2610 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2611 $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
\r
2614 $temp->value = $this->value;
\r
2621 * Compares two numbers.
\r
2623 * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is
\r
2624 * demonstrated thusly:
\r
2626 * $x > $y: $x->compare($y) > 0
\r
2627 * $x < $y: $x->compare($y) < 0
\r
2628 * $x == $y: $x->compare($y) == 0
\r
2630 * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).
\r
2632 * @param Math_BigInteger $y
\r
2633 * @return Integer < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
\r
2636 * @internal Could return $this->subtract($x), but that's not as fast as what we do do.
\r
2638 function compare($y)
\r
2640 switch ( MATH_BIGINTEGER_MODE ) {
\r
2641 case MATH_BIGINTEGER_MODE_GMP:
\r
2642 return gmp_cmp($this->value, $y->value);
\r
2643 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2644 return bccomp($this->value, $y->value, 0);
\r
2647 return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
\r
2651 * Compares two numbers.
\r
2653 * @param Array $x_value
\r
2654 * @param Boolean $x_negative
\r
2655 * @param Array $y_value
\r
2656 * @param Boolean $y_negative
\r
2661 function _compare($x_value, $x_negative, $y_value, $y_negative)
\r
2663 if ( $x_negative != $y_negative ) {
\r
2664 return ( !$x_negative && $y_negative ) ? 1 : -1;
\r
2667 $result = $x_negative ? -1 : 1;
\r
2669 if ( count($x_value) != count($y_value) ) {
\r
2670 return ( count($x_value) > count($y_value) ) ? $result : -$result;
\r
2672 $size = max(count($x_value), count($y_value));
\r
2674 $x_value = array_pad($x_value, $size, 0);
\r
2675 $y_value = array_pad($y_value, $size, 0);
\r
2677 for ($i = count($x_value) - 1; $i >= 0; --$i) {
\r
2678 if ($x_value[$i] != $y_value[$i]) {
\r
2679 return ( $x_value[$i] > $y_value[$i] ) ? $result : -$result;
\r
2687 * Tests the equality of two numbers.
\r
2689 * If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare()
\r
2691 * @param Math_BigInteger $x
\r
2696 function equals($x)
\r
2698 switch ( MATH_BIGINTEGER_MODE ) {
\r
2699 case MATH_BIGINTEGER_MODE_GMP:
\r
2700 return gmp_cmp($this->value, $x->value) == 0;
\r
2702 return $this->value === $x->value && $this->is_negative == $x->is_negative;
\r
2709 * Some bitwise operations give different results depending on the precision being used. Examples include left
\r
2710 * shift, not, and rotates.
\r
2712 * @param Integer $bits
\r
2715 function setPrecision($bits)
\r
2717 $this->precision = $bits;
\r
2718 if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ) {
\r
2719 $this->bitmask = new Math_BigInteger(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
\r
2721 $this->bitmask = new Math_BigInteger(bcpow('2', $bits, 0));
\r
2724 $temp = $this->_normalize($this);
\r
2725 $this->value = $temp->value;
\r
2731 * @param Math_BigInteger $x
\r
2733 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
\r
2734 * @return Math_BigInteger
\r
2736 function bitwise_and($x)
\r
2738 switch ( MATH_BIGINTEGER_MODE ) {
\r
2739 case MATH_BIGINTEGER_MODE_GMP:
\r
2740 $temp = new Math_BigInteger();
\r
2741 $temp->value = gmp_and($this->value, $x->value);
\r
2743 return $this->_normalize($temp);
\r
2744 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2745 $left = $this->toBytes();
\r
2746 $right = $x->toBytes();
\r
2748 $length = max(strlen($left), strlen($right));
\r
2750 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
\r
2751 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
\r
2753 return $this->_normalize(new Math_BigInteger($left & $right, 256));
\r
2756 $result = $this->copy();
\r
2758 $length = min(count($x->value), count($this->value));
\r
2760 $result->value = array_slice($result->value, 0, $length);
\r
2762 for ($i = 0; $i < $length; ++$i) {
\r
2763 $result->value[$i]&= $x->value[$i];
\r
2766 return $this->_normalize($result);
\r
2772 * @param Math_BigInteger $x
\r
2774 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
\r
2775 * @return Math_BigInteger
\r
2777 function bitwise_or($x)
\r
2779 switch ( MATH_BIGINTEGER_MODE ) {
\r
2780 case MATH_BIGINTEGER_MODE_GMP:
\r
2781 $temp = new Math_BigInteger();
\r
2782 $temp->value = gmp_or($this->value, $x->value);
\r
2784 return $this->_normalize($temp);
\r
2785 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2786 $left = $this->toBytes();
\r
2787 $right = $x->toBytes();
\r
2789 $length = max(strlen($left), strlen($right));
\r
2791 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
\r
2792 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
\r
2794 return $this->_normalize(new Math_BigInteger($left | $right, 256));
\r
2797 $length = max(count($this->value), count($x->value));
\r
2798 $result = $this->copy();
\r
2799 $result->value = array_pad($result->value, $length, 0);
\r
2800 $x->value = array_pad($x->value, $length, 0);
\r
2802 for ($i = 0; $i < $length; ++$i) {
\r
2803 $result->value[$i]|= $x->value[$i];
\r
2806 return $this->_normalize($result);
\r
2810 * Logical Exclusive-Or
\r
2812 * @param Math_BigInteger $x
\r
2814 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
\r
2815 * @return Math_BigInteger
\r
2817 function bitwise_xor($x)
\r
2819 switch ( MATH_BIGINTEGER_MODE ) {
\r
2820 case MATH_BIGINTEGER_MODE_GMP:
\r
2821 $temp = new Math_BigInteger();
\r
2822 $temp->value = gmp_xor($this->value, $x->value);
\r
2824 return $this->_normalize($temp);
\r
2825 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2826 $left = $this->toBytes();
\r
2827 $right = $x->toBytes();
\r
2829 $length = max(strlen($left), strlen($right));
\r
2831 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
\r
2832 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
\r
2834 return $this->_normalize(new Math_BigInteger($left ^ $right, 256));
\r
2837 $length = max(count($this->value), count($x->value));
\r
2838 $result = $this->copy();
\r
2839 $result->value = array_pad($result->value, $length, 0);
\r
2840 $x->value = array_pad($x->value, $length, 0);
\r
2842 for ($i = 0; $i < $length; ++$i) {
\r
2843 $result->value[$i]^= $x->value[$i];
\r
2846 return $this->_normalize($result);
\r
2853 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
\r
2854 * @return Math_BigInteger
\r
2856 function bitwise_not()
\r
2858 // calculuate "not" without regard to $this->precision
\r
2859 // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0)
\r
2860 $temp = $this->toBytes();
\r
2861 $pre_msb = decbin(ord($temp[0]));
\r
2863 $msb = decbin(ord($temp[0]));
\r
2864 if (strlen($msb) == 8) {
\r
2865 $msb = substr($msb, strpos($msb, '0'));
\r
2867 $temp[0] = chr(bindec($msb));
\r
2869 // see if we need to add extra leading 1's
\r
2870 $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
\r
2871 $new_bits = $this->precision - $current_bits;
\r
2872 if ($new_bits <= 0) {
\r
2873 return $this->_normalize(new Math_BigInteger($temp, 256));
\r
2876 // generate as many leading 1's as we need to.
\r
2877 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
\r
2878 $this->_base256_lshift($leading_ones, $current_bits);
\r
2880 $temp = str_pad($temp, ceil($this->bits / 8), chr(0), STR_PAD_LEFT);
\r
2882 return $this->_normalize(new Math_BigInteger($leading_ones | $temp, 256));
\r
2886 * Logical Right Shift
\r
2888 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
\r
2890 * @param Integer $shift
\r
2891 * @return Math_BigInteger
\r
2893 * @internal The only version that yields any speed increases is the internal version.
\r
2895 function bitwise_rightShift($shift)
\r
2897 $temp = new Math_BigInteger();
\r
2899 switch ( MATH_BIGINTEGER_MODE ) {
\r
2900 case MATH_BIGINTEGER_MODE_GMP:
\r
2903 if (!isset($two)) {
\r
2904 $two = gmp_init('2');
\r
2907 $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
\r
2910 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2911 $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
\r
2914 default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
\r
2915 // and I don't want to do that...
\r
2916 $temp->value = $this->value;
\r
2917 $temp->_rshift($shift);
\r
2920 return $this->_normalize($temp);
\r
2924 * Logical Left Shift
\r
2926 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
\r
2928 * @param Integer $shift
\r
2929 * @return Math_BigInteger
\r
2931 * @internal The only version that yields any speed increases is the internal version.
\r
2933 function bitwise_leftShift($shift)
\r
2935 $temp = new Math_BigInteger();
\r
2937 switch ( MATH_BIGINTEGER_MODE ) {
\r
2938 case MATH_BIGINTEGER_MODE_GMP:
\r
2941 if (!isset($two)) {
\r
2942 $two = gmp_init('2');
\r
2945 $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
\r
2948 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2949 $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
\r
2952 default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
\r
2953 // and I don't want to do that...
\r
2954 $temp->value = $this->value;
\r
2955 $temp->_lshift($shift);
\r
2958 return $this->_normalize($temp);
\r
2962 * Logical Left Rotate
\r
2964 * Instead of the top x bits being dropped they're appended to the shifted bit string.
\r
2966 * @param Integer $shift
\r
2967 * @return Math_BigInteger
\r
2970 function bitwise_leftRotate($shift)
\r
2972 $bits = $this->toBytes();
\r
2974 if ($this->precision > 0) {
\r
2975 $precision = $this->precision;
\r
2976 if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
\r
2977 $mask = $this->bitmask->subtract(new Math_BigInteger(1));
\r
2978 $mask = $mask->toBytes();
\r
2980 $mask = $this->bitmask->toBytes();
\r
2983 $temp = ord($bits[0]);
\r
2984 for ($i = 0; $temp >> $i; ++$i);
\r
2985 $precision = 8 * strlen($bits) - 8 + $i;
\r
2986 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
\r
2990 $shift+= $precision;
\r
2992 $shift%= $precision;
\r
2995 return $this->copy();
\r
2998 $left = $this->bitwise_leftShift($shift);
\r
2999 $left = $left->bitwise_and(new Math_BigInteger($mask, 256));
\r
3000 $right = $this->bitwise_rightShift($precision - $shift);
\r
3001 $result = MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
\r
3002 return $this->_normalize($result);
\r
3006 * Logical Right Rotate
\r
3008 * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
\r
3010 * @param Integer $shift
\r
3011 * @return Math_BigInteger
\r
3014 function bitwise_rightRotate($shift)
\r
3016 return $this->bitwise_leftRotate(-$shift);
\r
3020 * Set random number generator function
\r
3022 * This function is deprecated.
\r
3024 * @param String $generator
\r
3027 function setRandomGenerator($generator)
\r
3032 * Generate a random number
\r
3034 * @param optional Integer $min
\r
3035 * @param optional Integer $max
\r
3036 * @return Math_BigInteger
\r
3039 function random($min = false, $max = false)
\r
3041 if ($min === false) {
\r
3042 $min = new Math_BigInteger(0);
\r
3045 if ($max === false) {
\r
3046 $max = new Math_BigInteger(0x7FFFFFFF);
\r
3049 $compare = $max->compare($min);
\r
3052 return $this->_normalize($min);
\r
3053 } else if ($compare < 0) {
\r
3054 // if $min is bigger then $max, swap $min and $max
\r
3060 $max = $max->subtract($min);
\r
3061 $max = ltrim($max->toBytes(), chr(0));
\r
3062 $size = strlen($max) - 1;
\r
3064 $crypt_random = function_exists('crypt_random_string') || (!class_exists('Crypt_Random') && function_exists('crypt_random_string'));
\r
3065 if ($crypt_random) {
\r
3066 $random = crypt_random_string($size);
\r
3071 $random.= chr(mt_rand(0, 255));
\r
3074 $blocks = $size >> 1;
\r
3075 for ($i = 0; $i < $blocks; ++$i) {
\r
3076 // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
\r
3077 $random.= pack('n', mt_rand(0, 0xFFFF));
\r
3081 $fragment = new Math_BigInteger($random, 256);
\r
3082 $leading = $fragment->compare(new Math_BigInteger(substr($max, 1), 256)) > 0 ?
\r
3083 ord($max[0]) - 1 : ord($max[0]);
\r
3085 if (!$crypt_random) {
\r
3086 $msb = chr(mt_rand(0, $leading));
\r
3088 $cutoff = floor(0xFF / $leading) * $leading;
\r
3090 $msb = ord(crypt_random_string(1));
\r
3091 if ($msb <= $cutoff) {
\r
3099 $random = new Math_BigInteger($msb . $random, 256);
\r
3101 return $this->_normalize($random->add($min));
\r
3105 * Generate a random prime number.
\r
3107 * If there's not a prime within the given range, false will be returned. If more than $timeout seconds have elapsed,
\r
3108 * give up and return false.
\r
3110 * @param optional Integer $min
\r
3111 * @param optional Integer $max
\r
3112 * @param optional Integer $timeout
\r
3113 * @return Math_BigInteger
\r
3115 * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}.
\r
3117 function randomPrime($min = false, $max = false, $timeout = false)
\r
3119 if ($min === false) {
\r
3120 $min = new Math_BigInteger(0);
\r
3123 if ($max === false) {
\r
3124 $max = new Math_BigInteger(0x7FFFFFFF);
\r
3127 $compare = $max->compare($min);
\r
3130 return $min->isPrime() ? $min : false;
\r
3131 } else if ($compare < 0) {
\r
3132 // if $min is bigger then $max, swap $min and $max
\r
3138 static $one, $two;
\r
3139 if (!isset($one)) {
\r
3140 $one = new Math_BigInteger(1);
\r
3141 $two = new Math_BigInteger(2);
\r
3146 $x = $this->random($min, $max);
\r
3148 // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
\r
3149 if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP && function_exists('gmp_nextprime') ) {
\r
3150 $p->value = gmp_nextprime($x->value);
\r
3152 if ($p->compare($max) <= 0) {
\r
3156 if (!$min->equals($x)) {
\r
3157 $x = $x->subtract($one);
\r
3160 return $x->randomPrime($min, $x);
\r
3163 if ($x->equals($two)) {
\r
3168 if ($x->compare($max) > 0) {
\r
3169 // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
\r
3170 if ($min->equals($max)) {
\r
3173 $x = $min->copy();
\r
3177 $initial_x = $x->copy();
\r
3180 if ($timeout !== false && time() - $start > $timeout) {
\r
3184 if ($x->isPrime()) {
\r
3188 $x = $x->add($two);
\r
3190 if ($x->compare($max) > 0) {
\r
3191 $x = $min->copy();
\r
3192 if ($x->equals($two)) {
\r
3198 if ($x->equals($initial_x)) {
\r
3205 * Make the current number odd
\r
3207 * If the current number is odd it'll be unchanged. If it's even, one will be added to it.
\r
3209 * @see randomPrime()
\r
3212 function _make_odd()
\r
3214 switch ( MATH_BIGINTEGER_MODE ) {
\r
3215 case MATH_BIGINTEGER_MODE_GMP:
\r
3216 gmp_setbit($this->value, 0);
\r
3218 case MATH_BIGINTEGER_MODE_BCMATH:
\r
3219 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
\r
3220 $this->value = bcadd($this->value, '1');
\r
3224 $this->value[0] |= 1;
\r
3229 * Checks a numer to see if it's prime
\r
3231 * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the
\r
3232 * $t parameter is distributability. Math_BigInteger::randomPrime() can be distributed accross multiple pageloads
\r
3233 * on a website instead of just one.
\r
3235 * @param optional Integer $t
\r
3238 * @internal Uses the
\r
3239 * {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. See
\r
3240 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}.
\r
3242 function isPrime($t = false)
\r
3244 $length = strlen($this->toBytes());
\r
3247 // see HAC 4.49 "Note (controlling the error probability)"
\r
3248 if ($length >= 163) { $t = 2; } // floor(1300 / 8)
\r
3249 else if ($length >= 106) { $t = 3; } // floor( 850 / 8)
\r
3250 else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8)
\r
3251 else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8)
\r
3252 else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8)
\r
3253 else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8)
\r
3254 else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8)
\r
3255 else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8)
\r
3256 else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
\r
3257 else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
\r
3258 else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
\r
3262 // ie. gmp_testbit($this, 0)
\r
3263 // ie. isEven() or !isOdd()
\r
3264 switch ( MATH_BIGINTEGER_MODE ) {
\r
3265 case MATH_BIGINTEGER_MODE_GMP:
\r
3266 return gmp_prob_prime($this->value, $t) != 0;
\r
3267 case MATH_BIGINTEGER_MODE_BCMATH:
\r
3268 if ($this->value === '2') {
\r
3271 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
\r
3276 if ($this->value == array(2)) {
\r
3279 if (~$this->value[0] & 1) {
\r
3284 static $primes, $zero, $one, $two;
\r
3286 if (!isset($primes)) {
\r
3288 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
\r
3289 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
\r
3290 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
\r
3291 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
\r
3292 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
\r
3293 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
\r
3294 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
\r
3295 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
\r
3296 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
\r
3297 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
\r
3298 953, 967, 971, 977, 983, 991, 997
\r
3301 if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL ) {
\r
3302 for ($i = 0; $i < count($primes); ++$i) {
\r
3303 $primes[$i] = new Math_BigInteger($primes[$i]);
\r
3307 $zero = new Math_BigInteger();
\r
3308 $one = new Math_BigInteger(1);
\r
3309 $two = new Math_BigInteger(2);
\r
3312 if ($this->equals($one)) {
\r
3316 // see HAC 4.4.1 "Random search for probable primes"
\r
3317 if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL ) {
\r
3318 foreach ($primes as $prime) {
\r
3319 list(, $r) = $this->divide($prime);
\r
3320 if ($r->equals($zero)) {
\r
3321 return $this->equals($prime);
\r
3325 $value = $this->value;
\r
3326 foreach ($primes as $prime) {
\r
3327 list(, $r) = $this->_divide_digit($value, $prime);
\r
3329 return count($value) == 1 && $value[0] == $prime;
\r
3334 $n = $this->copy();
\r
3335 $n_1 = $n->subtract($one);
\r
3336 $n_2 = $n->subtract($two);
\r
3338 $r = $n_1->copy();
\r
3339 $r_value = $r->value;
\r
3340 // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
\r
3341 if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
\r
3343 // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
\r
3344 while ($r->value[strlen($r->value) - 1] % 2 == 0) {
\r
3345 $r->value = bcdiv($r->value, '2', 0);
\r
3349 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
\r
3350 $temp = ~$r_value[$i] & 0xFFFFFF;
\r
3351 for ($j = 1; ($temp >> $j) & 1; ++$j);
\r
3356 $s = 26 * $i + $j - 1;
\r
3360 for ($i = 0; $i < $t; ++$i) {
\r
3361 $a = $this->random($two, $n_2);
\r
3362 $y = $a->modPow($r, $n);
\r
3364 if (!$y->equals($one) && !$y->equals($n_1)) {
\r
3365 for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
\r
3366 $y = $y->modPow($two, $n);
\r
3367 if ($y->equals($one)) {
\r
3372 if (!$y->equals($n_1)) {
\r
3381 * Logical Left Shift
\r
3383 * Shifts BigInteger's by $shift bits.
\r
3385 * @param Integer $shift
\r
3388 function _lshift($shift)
\r
3390 if ( $shift == 0 ) {
\r
3394 $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
\r
3395 $shift %= MATH_BIGINTEGER_BASE;
\r
3396 $shift = 1 << $shift;
\r
3400 for ($i = 0; $i < count($this->value); ++$i) {
\r
3401 $temp = $this->value[$i] * $shift + $carry;
\r
3402 $carry = (int) ($temp / MATH_BIGINTEGER_BASE_FULL);
\r
3403 $this->value[$i] = (int) ($temp - $carry * MATH_BIGINTEGER_BASE_FULL);
\r
3407 $this->value[] = $carry;
\r
3410 while ($num_digits--) {
\r
3411 array_unshift($this->value, 0);
\r
3416 * Logical Right Shift
\r
3418 * Shifts BigInteger's by $shift bits.
\r
3420 * @param Integer $shift
\r
3423 function _rshift($shift)
\r
3425 if ($shift == 0) {
\r
3429 $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE);
\r
3430 $shift %= MATH_BIGINTEGER_BASE;
\r
3431 $carry_shift = MATH_BIGINTEGER_BASE - $shift;
\r
3432 $carry_mask = (1 << $shift) - 1;
\r
3434 if ( $num_digits ) {
\r
3435 $this->value = array_slice($this->value, $num_digits);
\r
3440 for ($i = count($this->value) - 1; $i >= 0; --$i) {
\r
3441 $temp = $this->value[$i] >> $shift | $carry;
\r
3442 $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
\r
3443 $this->value[$i] = $temp;
\r
3446 $this->value = $this->_trim($this->value);
\r
3452 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
\r
3454 * @param Math_BigInteger
\r
3455 * @return Math_BigInteger
\r
3459 function _normalize($result)
\r
3461 $result->precision = $this->precision;
\r
3462 $result->bitmask = $this->bitmask;
\r
3464 switch ( MATH_BIGINTEGER_MODE ) {
\r
3465 case MATH_BIGINTEGER_MODE_GMP:
\r
3466 if (!empty($result->bitmask->value)) {
\r
3467 $result->value = gmp_and($result->value, $result->bitmask->value);
\r
3471 case MATH_BIGINTEGER_MODE_BCMATH:
\r
3472 if (!empty($result->bitmask->value)) {
\r
3473 $result->value = bcmod($result->value, $result->bitmask->value);
\r
3479 $value = &$result->value;
\r
3481 if ( !count($value) ) {
\r
3485 $value = $this->_trim($value);
\r
3487 if (!empty($result->bitmask->value)) {
\r
3488 $length = min(count($value), count($this->bitmask->value));
\r
3489 $value = array_slice($value, 0, $length);
\r
3491 for ($i = 0; $i < $length; ++$i) {
\r
3492 $value[$i] = $value[$i] & $this->bitmask->value[$i];
\r
3502 * Removes leading zeros
\r
3504 * @param Array $value
\r
3505 * @return Math_BigInteger
\r
3508 function _trim($value)
\r
3510 for ($i = count($value) - 1; $i >= 0; --$i) {
\r
3511 if ( $value[$i] ) {
\r
3514 unset($value[$i]);
\r
3523 * @param $input Array
\r
3524 * @param $multiplier mixed
\r
3528 function _array_repeat($input, $multiplier)
\r
3530 return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
\r
3534 * Logical Left Shift
\r
3536 * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
\r
3538 * @param $x String
\r
3539 * @param $shift Integer
\r
3543 function _base256_lshift(&$x, $shift)
\r
3545 if ($shift == 0) {
\r
3549 $num_bytes = $shift >> 3; // eg. floor($shift/8)
\r
3550 $shift &= 7; // eg. $shift % 8
\r
3553 for ($i = strlen($x) - 1; $i >= 0; --$i) {
\r
3554 $temp = ord($x[$i]) << $shift | $carry;
\r
3555 $x[$i] = chr($temp);
\r
3556 $carry = $temp >> 8;
\r
3558 $carry = ($carry != 0) ? chr($carry) : '';
\r
3559 $x = $carry . $x . str_repeat(chr(0), $num_bytes);
\r
3563 * Logical Right Shift
\r
3565 * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
\r
3567 * @param $x String
\r
3568 * @param $shift Integer
\r
3572 function _base256_rshift(&$x, $shift)
\r
3574 if ($shift == 0) {
\r
3575 $x = ltrim($x, chr(0));
\r
3579 $num_bytes = $shift >> 3; // eg. floor($shift/8)
\r
3580 $shift &= 7; // eg. $shift % 8
\r
3584 $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
\r
3585 $remainder = substr($x, $start);
\r
3586 $x = substr($x, 0, -$num_bytes);
\r
3590 $carry_shift = 8 - $shift;
\r
3591 for ($i = 0; $i < strlen($x); ++$i) {
\r
3592 $temp = (ord($x[$i]) >> $shift) | $carry;
\r
3593 $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
\r
3594 $x[$i] = chr($temp);
\r
3596 $x = ltrim($x, chr(0));
\r
3598 $remainder = chr($carry >> $carry_shift) . $remainder;
\r
3600 return ltrim($remainder, chr(0));
\r
3603 // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
\r
3604 // at 32-bits, while java's longs are 64-bits.
\r
3607 * Converts 32-bit integers to bytes.
\r
3609 * @param Integer $x
\r
3613 function _int2bytes($x)
\r
3615 return ltrim(pack('N', $x), chr(0));
\r
3619 * Converts bytes to 32-bit integers
\r
3621 * @param String $x
\r
3625 function _bytes2int($x)
\r
3627 $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
\r
3628 return $temp['int'];
\r
3632 * DER-encode an integer
\r
3634 * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL
\r
3638 * @param Integer $length
\r
3641 function _encodeASN1Length($length)
\r
3643 if ($length <= 0x7F) {
\r
3644 return chr($length);
\r
3647 $temp = ltrim(pack('N', $length), chr(0));
\r
3648 return pack('Ca*', 0x80 | strlen($temp), $temp);
\r
projects / quix0rs-gnu-social.git / blob